8.3. Управление памятью bunix

Система управления памятью в UNIXварьируется в разных операционных системах. Ранние версииUNIXиспользовали переменное распределение памяти без применения виртуальной памяти. Современные реализации, включаяSVR4 иSolaris2-х, используют страничную виртуальную память.

В SVR4 и Solaris, по сути, имеются две раздельные схемы управления памятью. Страничная система обеспечивает реализацию возможностей виртуаль­ной памяти, распределяя кадры основной памяти среди процессов, а также сре­ди буферов диска. Хотя описанная схема эффективно работает с пользователь­скими процессами и дисковым вводом-выводом, страничная виртуальная память мало приспособлена для управления памятью ядра. Для этой цели используется распределение памяти ядра. Рассмотрим оба механизма.

Страничная система

Структуры данных

Для страничной виртуальной памяти UNIXиспользует ряд структур данных, которые (с минимальной коррекцией) являются машинно-независимыми (см.рис. 8.31 и табл. 8.6).

• Страница таблиц.Обычно для каждого процесса используется одна таблица страниц, в которой каждой странице виртуальной памяти процесса соответствует одна запись.

• Дескриптор дискового блока.В этой таблице каждой странице процесса соответствует запись, описывающая дисковую копию этой страницы.

• Таблица кадров.Описывает каждый кадр реальной памяти; таблица проиндексирована номерами кадров.

• Таблица использования свопинга.Для каждого устройства свопинга имеется своя таблица, в которой для каждой страницы на этом устройстве имеется своя запись.

Большинство полей, приведенных в табл. 8.6, не требуют пояснений. Поле возраста в записи таблицы страниц указывает, как давно программа не обращалась к этому кадру. Размер и частота обновления этого поля зависят от конкретной реализации. Таким образом, нет универсального использования операционной системой UNIXэтого поля при реализации стратегии замещения страниц.

Наличие поля типа памяти в дескрипторе дискового блока необходимо по следующей причине: когда выполнимый файл используется для создания нового процесса, в реальную память может быть загружена только часть кода и данных. Позже, при возникновении прерывания из-за отсутствия страницы, в память загружаются новые порции кода или данных. Страницы виртуальной памяти создаются и связываются с определенными положениями на устройстве свопинга только в момент первоначальной загрузки. В этот момент операционная система решает, следует ли очистить (установить равными 0) ячейки кадра страницы перед первой загрузкой блока кода или данных.

Замещение страниц

Для замещения страниц используется таблица кадров. Для создания списков в этой таблице применяются несколько указателей. Все доступные кадры объединены в один список свободных кадров, в которых могут размещаться страницы. Когда количество доступных страниц становится ниже некоторого порогового значения, ядро в качестве компенсации отдает ряд страниц загруженных процессов.

Алгоритм замещения страниц, использованный в SVR4, представляет собой усовершенствованный часовой алгоритм (см. рис. 8.16), известный под названием часового алгоритма с двумя стрелками (рис. 8.22). Этот алгоритм использует бит обращений из записи таблицы страниц для каждой из страниц памяти, которая может быть выгружена из основной памяти (т.е. не заблокирована). Этот бит устанавливается равным 0 при первоначальной загрузке страницы, и равным 1 — при обращении к ней для чтения или записи. Перед ний указатель проходит по страницам, содержащимся в списке пригодных для выгрузки страниц, и устанавливает бит обращений каждой из них равным 0. Несколько позже по тем же страницам проходит задний указатель и проверяет бит обращений. Если он равен 1, значит, к данной странице было обращение между проверками ее передним и задним указателями, и такая страница игнорируется. Страница же бит обращений которой остался равен 0, переносится в список выгружаемых страниц.

Работа алгоритма определяется двумя параметрами.

• Частота сканирования. Частота, с которой указатели сканируют список страниц (в кадрах в секунду).

• Охват. Интервал между передним и задним указателями.

Эти параметры в процессе загрузки операционной системы получают значения по умолчанию, основанные на количестве физической памяти. Частота сканирования в процессе работы может изменяться, чтобы соответствовать изменяющимся условиям работы системы. Параметр линейно изменяется от минимального значения до максимального, определенных при настройке системы, с изменением количества свободной памяти от максимального до минимального — иными словами, чем меньше свободной памяти в системе, чем чаще выполняется сканирование. Охват определяет интервал между указателями и вместе с частотой сканирования определяет промежуток времени, в течение которого к странице должно произойти обращение, чтобы она оставалась в основной памяти.

Распределение памяти ядра

Ядро в процессе работы часто генерирует и уничтожает маленькие таблицы и буфера, память для каждого из которых выделяется динамически. В [VAHA96] перечислены следующие примеры.

• Преобразование имени пути может запросить буфер для копирования имени из пользовательского пространства.

• Подпрограмма allocb( ) выделяет буфера произвольного размера.

• Ряд реализации UNIXвыделяют "зомби"-структуры для хранения информации о состоянии выхода и использовании ресурсов завершенными процессами.

• В SVR4 иSolarisядро динамически распределяет множество объектов (таких, как структуры процессов, блоки дескрипторов файлов и др.).

Размер большинства этих блоков гораздо меньше типичного размера страницы памяти и, соответственно, использование страничного механизма в данном случае крайне неэффективно. В SVR4 используется модификация системы двойников (описанной в разделе 7.2).

Стоимость выделения свободного блока памяти в системе двойников меньше, чем в случае использования стратегий первого или наилучшего подходящего [KNUT97]. Однако при управлении памятью ядра выделение и освобождение памяти должно выполняться с максимально возможной скоростью. Недостатком же системы двойников являются затраты времени на разделение и слияние блоков.

Беркли (Barkley) и Ли (Lee) из AT&T предложили модификацию, известную как "ленивая" система двойников [BARK89], которая принята в SVR4. Авторами замечено, чтоUNIXчасто демонстрирует устойчивое состояние памяти ядра, т.е. количество требующихся блоков определенного размера мало меняется со временем. Таким образом, вполне возможна ситуация, когда освобождающийся блок размером 2ⁱсливается со своим двойником в блок размером 2ⁱ⁺¹, который тут же вновь разделяется на два блока размером 2ⁱв соответствии с запросом системы. Чтобы избежать излишних слияний и разделений блоков, слияние освобожденных блоков откладывается до того момента, когда оно оказывается действительно необходимым (и тогда производится максимально возможное количество слияний блоков).

В модифицированной таким образом системе двойников используются следующие параметры:

N_i —текущее количество блоков размером 2ⁱ;

A_i— текущее количество занятых блоков размером 2ⁱ;

G_i— текущее количество глобально свободных блоков размером 2ⁱ(Это блоки, пригодные для слияния со своими двойниками. Когда двойник такого блока становится глобально свободным, эти два блока сливаются в глобально свободный блок размером 2ⁱ⁺¹. Все свободные блоки в системе двойников могут рассматриваться как глобально свободные);

L_i —текущее количество локально свободных блоков размером 2ⁱ(Это блоки, не пригодные для слияния. Даже если двойник такого блока становится свободным, эти два блока не сливаются, а остаются в ожидании последующих запросов на блоки данного размера.).

Выполняется следующее соотношение:

N_i= A_i+ G_i+ L_i

В целом данная система двойников пытается поддерживать пул локально свободных блоков и производит слияние, только когда количество локально свободных блоков превышает предопределенный порог (при наличии слишком большого количества локально свободных блоков возрастает вероятность недостатка блоков большего размера для удовлетворения требований системы). В основном при освобождении блока слияние не выполняется, что минимизирует накладные расходы. Никаких различий между локально и глобально свободными блоками при выделении блока в ответ на запрос системы не делается.

Для слияния используется критерий, согласно которому количество локально свободных блоков данного размера не должно превышать количество занятых блоков этого размера (т.е. должно выполняться условиеL_i <А_i). Это вполне разумный принцип для ограничения количества локально свободных блоков; эксперименты, описанные в [BARK89], подтверждают, что такая схема приводит к значительному снижению стоимости распределения памяти.

Для реализации описанной схемы ее авторы определили переменную задержки D_i= 4 –L_i=N_i- 2L_i–G_i. Алгоритм схемы приведен в листинге 8.1.