управление памятью. Управление памятью. 6. 1 Основные понятия Менеджер памяти
 Скачать 193.52 Kb.
|
|
Управление памятью. Страничная организация. 6.1 Основные понятия Менеджер памяти - часть операционной системы, отвечающая за управление памятью. Основные методы распределения памяти: Без использования внешней памяти (например: HDD) С использованием внешней памяти 6.2 Методы без использования внешней памяти 6.2.1 Однозадачная система без подкачки на диск Память разделяется только между программой и операционной системой. Схемы разделения памяти:  Схемы разделения памяти Третий вариант используется в MS-DOS. Та часть, которая находится в ПЗУ, часто называется BIOS. 6.2.2 Распределение памяти с фиксированными разделами. Память просто разделяется на несколько разделов (возможно, не равных). Процессы могут быть разными, поэтому каждому разделу необходим разный размер памяти. Системы могут иметь: общую очередь ко всем разделам к каждому разделу отдельную очередь  Распределение памяти с фиксированными разделами Недостаток системы многих очередей очевиден, когда большой раздел может быть свободным, а к маленькому выстроилась очередь. Алгоритмы планирования в случае одной очереди: поочередный выбирается задача, которая максимально займет раздел Также может быть смешанная система. 6.2.3 Распределение памяти динамическими разделами В такой системе сначала память свободна, потом идет динамическое распределение памяти.  Распределение памяти динамическими разделами. Недостатки: Сложность Память фрагментируется Перемещаемые разделы Это один из методов борьбы с фрагментацией. Но на него уходит много времени.  Перемещаемые разделы Рост разделов Иногда процессу может понадобиться больше памяти, чем предполагалось изначально.  Рост разделов Настройка адресов и защита памяти В предыдущих примерах мы можем увидеть две основные проблемы. Настройка адресов или перемещение программ в памяти Защита адресного пространства каждой программы Решение обоих проблем заключается в оснащении машины специальными аппаратными регистрами. Базовый (указывает начало адресного пространства программы) Предельный (указывает конец адресного пространства программы) 6.3 Методы с использованием внешней памяти (свопинг и виртуальная память) Так как памяти, как правило, не хватает. Для выполнения процессов часто приходится использовать диск. Основные способы использования диска: Свопинг (подкачка) - процесс целиком загружается в память для работы Виртуальная память - процесс может быть частично загружен в память для работы 6.3.1 Свопинг (подкачка) При нехватке памяти процессы могут быть выгружены на диск.  т.к. процесс С очень большой, процесс А был выгружен временно на диск, после завершения процесса С он снова был загружен в память. Как мы видим процесс А второй раз загрузился в другое адресное пространство, должны создаваться такие условия, которые не повлияют на работу процесса. Свопер - планировщик, управляющий перемещением данных между памятью и диском. Этот метод был основным для UNIX до версии 3BSD. Управление памятью с помощью битовых массивов Вся память разбивается на блоки (например, по 32бита), массив содержит 1 или 0 (занят или незанят). Чтобы процессу в 32Кбита занять память, нужно набрать последовательность из 1000 свободных блоков. Такой алгоритм займет много времени.  битовые массивы и списки Управление памятью с помощью связных списков Этот способ отслеживает списки занятых (между процессами) и свободных (процессы) фрагментов памяти. Запись в списке указывает на: занят (P) или незанят (H) фрагмент адрес начала фрагмента длину фрагмента  Четыре комбинации соседей для завершения процесса X Алгоритмы выделения блока памяти: первый подходящий участок. следующий подходящий участок, стартует не сначала списка, а с того места на котором остановился в последний раз. самый подходящий участок (медленнее, но лучше использует память). самый неподходящий участок, расчет делается на то, что программа займет самый большой участок, а лишнее будет отделено в новый участок, и он будет достаточно большой для другой программы. 6.3.2 Виртуальная память Основная идея заключается в разбиении программы на части, и в память эти части загружаются по очереди. Программа при этом общается с виртуальной памятью, а не с физической.  Диспетчер памяти преобразует виртуальные адреса в физические. Страничная организация памяти Страницы - это части, на которые разбивается пространство виртуальных адресов. Страничные блоки - единицы физической памяти. Страницы всегда имеют фиксированный размер. Передача данных между ОЗУ и диском всегда происходит в страницах.  Х - обозначает не отображаемую страницу в физической памяти. Страничное прерывание - происходит, если процесс обратился к странице, которая не загружена в ОЗУ (т.е. Х). Процессор передается другому процессу, и параллельно страница загружается в память. Таблица страниц - используется для хранения соответствия адресов виртуальной страницы и страничного блока. Таблица может быть размещена: в аппаратных регистрах (преимущество: более высокое быстродействие, недостаток - стоимость) в ОЗУ  Типичная запись в таблице страниц Присутствие/отсутствие - загружена или незагружена в память Защита - виды доступа, например, чтение/запись. Изменение - изменилась ли страница, если да то при выгрузке записывается на диск, если нет, просто уничтожается. Обращение - было ли обращение к странице, если нет, то это лучший кандидат на освобождение памяти. Информация о адресе страницы когда она хранится на диске, в таблице не размещается. Для ускорения доступа к страницам в диспетчере памяти создают буфер быстрого преобразования адреса, в котором хранится информация о наиболее часто используемых страниц. Страничная организация памяти используется, и в UNIX, и в Windows. Хранение страничной памяти на диске Статическая область свопинга После запуска процесса он занимает определенную память, на диске сразу ему выделяется такое же пространство. Поэтому файл подкачки должен быть не меньше памяти. А в случае нехватки памяти даже больше. Как только процесс завершится, он освободит память и место на диске. На диске всегда есть дубликат страницы, которая находится в памяти. Этот механизм наиболее простой.  Статический и динамический методы организации свопинга. Динамическая область свопинга Предполагается не выделять страницам место на диске, а выделять только при выгрузке страницы, и как только страница вернется в память освобождать место на диске. Этот механизм сложнее, так как процессы не привязаны к какому-то пространству на диске, и нужно хранить информацию (карту диска) о местоположении на диске каждой страницы. Сегментация памяти. 8.1 Основные понятия сегментации Рассмотрим пример, когда программа использует одно адресное пространство.  программа использует одно адресное пространство Недостатки такой системы: Один участок может полностью заполниться, но при этом останутся свободные участки. Можно конечно перемещать участки, но это очень сложно. Эти проблемы можно решить, если дать каждому участку независимое адресное пространство, называемое сегментом. Рассмотрим то же пример с использованием сегментов:  Сегментированная память Каждый сегмент может расти или уменьшаться независимо от других. Сегмент - это логический объект. В этом случае адрес имеет две части: номер сегмента адрес в сегменте Преимущества сегментации: Сегменты не мешают друг другу. Начальный адрес процедуры всегда начинается с (n,0). Что упрощает программирование. Облегчает совместное использование процедур и данных. Раздельная защита каждого сегмента (чтение, запись). 8.2 Реализация сегментации Если страницы имеют фиксированный размер, то сегменты нет. У сегментов так же, как и у страниц, существует проблема фрагментации. Т.к. памяти часто не хватает, стали использовать страничную организацию сегментов. При которой в памяти может находиться только часть сегмента. 8.2.1 Сегментация с использованием страниц: MULTICS В одной из первых, где была применена страничная сегментация, была система MULTICS. Каждая программа обеспечивалась до 2^18 сегментов (более 250 000), каждый из которых мог быть до 65 536 (36-разрядных) слов длиной. Таблица сегментов - хранит дескриптор для каждого сегмента. У каждой программы своя таблица. Т.к. записей в таблице более 250 000, она сама разбита на страницы. Сама таблица является отдельным сегментом.  Сегмент с таблицей дескрипторов указывающих на таблицы страниц для каждого сегмента Нормальный размер страницы равен 1024 словам. Если сегмент меньше 1024, то он либо не разбит на страницы, либо разбит на страницы по 64 слова.  Дескриптор сегмента Когда происходит обращение к памяти, выполняется следующий алгоритм: По номеру сегмента находится дескриптор сегмента. Проверяется, находиться ли таблица страницы в памяти. Если в памяти, определяется ее расположение. Если нет, вызывается сегментное прерывание. Проверяется, находиться ли страница в памяти. Если в памяти, определяется ее расположение в памяти. Если нет в памяти, вызывается страничное прерывание. К адресу начала страницы прибавляется смещение, в результате получаем адрес нужного слова в оперативной памяти. Происходит запись или чтение.  Преобразование адреса в системе MULTICS Так как такой алгоритм будет работать достаточно медленно. Аппаратура системы MULTICS содержит высокоскоростной буфер быстрого преобразования адреса (TLB) размером в 16 слов. Адреса 16 наиболее часто использующихся страниц хранятся в буфере. 8.2.2 Сегментация с использованием страниц: Intel Pentium Каждая программа обеспечивается до 16К сегментов, каждый из которых может быть до 1 млдр 36-разрядных слов длиной. Основа виртуальной памяти системы Pentium состоит из двух таблиц: Локальная таблица дескрипторов LDT (Local Descriptor Table) - есть у каждой программы, и описывает сегменты программы. Глобальная таблица дескрипторов GDT (Global Descriptor Table) - одна для всех программ, и описывает системные сегменты (включая саму ОС). Каждый селектор (указывает на дескриптор) представляет собой 16-разрядный номер.  Селектор в системе Pentium 13 битов определяют номер записи в таблице дескрипторов, поэтому эти таблицы ограничены, каждая содержит 8К (2^13) сегментных дескрипторов. 1 бит указывает тип используемой таблицы дескрипторов LDT или GDT.  Уровни привилегированности в системе Pentium Уровни привилегированности запрещают выполняемому коду обратиться к более низкому уровню. С учетом максимального размера сегмента - 4 Гбайта - каждая задача, при чисто сегментной организации виртуальной памяти, работает в виртуальном адресном пространстве в 64 Тбайта (4 Гбайта * 16К, где 16К=8К*2 т.к. LDT и GDT).  Дескриптор программного (не данных) сегмента в системе Pentium (всего 8 байт (64 бита)). База (Base) - базовый адрес сегмента (32-бита), разделен на три части из-за совместимости с i286, в котором это поле имеет только 24 бита. Размер (Limit) - размер сегмента (20 бит), разнесен на две части. Если размер сегмента указан в страницах, он может достигать 2^32 байтов (2^20 * 4Кбайт (2^12) (размер страницы в Pentium)). Алгоритм получение физического адреса: Селектор загружается в регистр (для сегмента команд в CS, для сегмента данных в DS). Определяется глобальный или локальный сегмент (LDT или GDT). Дескриптор извлекается из LDT или GDT, и сохраняется в микропрограммных регистрах. Если дескриптор в памяти и смещение не выходит за пределы сегмента, программа может продолжить работу, если нет, происходит прерывание. Система Pentium прибавляет базовый адрес к смещению, и получает линейный адрес, - если страничная организация памяти не используется, то он является физическим адресом (адрес получен), - если страничная организация памяти используется, то он является виртуальным адресом. В случае, если используется страничная организация памяти, линейный адрес переводится в физический с помощью таблицы страниц.  Преобразование пары (селектора, смещение) в физический адрес При 32-разрядном (2^32=4Гбайт) адресе и 4Кбатной странице, сегмент может содержать 1 млн страниц (4Гбайт/4Кбайта). Поэтому используется двухуровневое отображение (создана таблица (страничный каталог) содержащая список из 1024 таблиц страниц), благодаря чему можно снизить количество записей в таблице страниц до 1024. В этом случае сегмент в 4 Мбайта (1024 записи по 4 Кбайта страницы), будет иметь страничный каталог только с одной записью (и 1024 в таблице страниц), вместо 1 млн в одной таблице.  Отображение линейного адреса на физический адрес В системе Pentium также есть буфер быстрого преобразования адреса (TLB), в котором хранятся наиболее часто используемые комбинации Каталог-Страница на физический адрес страничного блока. Только если комбинация в TLB отсутствует, выполняется это алгоритм. 8.3 Особенности реализации в UNIX В LUNIX системе на 32-разрядной машине каждый процесс получает 3Гбайта виртуального пространства для себя, и 1Гбайт для страничных таблиц и других данных ядра. На компьютерах Pentium, используется двухуровневые таблицы страниц, и размер страниц фиксирован 4Кбайта На компьютерах Alpha, используется трехуровневые таблицы страниц, и размер страниц фиксирован 8Кбайт Для каждой программы выделяется 3 сегмента: Код программы (только для чтения) Данные Стек |