Реализация управления памятью в UNIX

До версии 3BSD большинство систем UNIX основывались на свопинге (подкач­ке), работавшем следующим образом. Когда загружалось больше процессов, чем могло поместиться в памяти, некоторые из них выгружались на диск. Выгружае­мый процесс всегда выгружался на диск целиком (исключение представляли толь­ко совместно используемые текстовые сегменты). Таким образом, процесс мог быть либо в памяти, либо на диске.

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

1. Системному вызову fork требовалась память для дочернего процесса.

2. Системный вызов brk собирался расширить сегмент данных.

3. Разросшемуся стеку требовалась дополнительная память.

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

Каждые несколько секунд свопер исследовал список выгруженных процессов, проверяя, не готов ли какой-либо из этих процессов к работе. Если процессы в со­стоянии готовности обнаруживались, из них выбирался процесс, дольше всех нахо­дящийся на диске. Затем свопер проверял, будет ли это легкий свопинг или тяже­лый. Легким свопингом считался тот, для которого не требовалось дополнительное высвобождение памяти. При этом нужно было всего лишь загрузить выгружен­ный на диск процесс. Тяжелым свопингом назывался свопинг, при котором для загрузки в память выгруженного на диск процесса из нее требовалось удалить один или несколько других процессов. Затем весь этот алгоритм повторялся до тех пор, пока не выполнялось одно из следующих двух условий: на диске не оставалось процессов, готовых к работе, или в памяти не оставалось места для новых процессов. Чтобы не терять боль­шую часть производительности системы на свопинг, ни один процесс не выгру­жался на диск, если он пробыл в памяти менее 2 с. Свободное место в памяти и на устройстве перекачки учитывалось при помо­щи связного списка свободных пространств. Когда требовалось свободное про­странство в памяти или на диске, из списка выбиралось первое подходящее сво­бодное пространство. После этого в список возвращался остаток от свободного пространства.

Начиная с версии 3BSD к системе была добавлена страничная подкачка, чтобы предоставить возможность работать с программами больших размеров. Практически во всех версиях системы UNIX теперь есть страничная подкачка по требованию, появившаяся впервые в версии 3BSD. Ниже описывается реализация этого механизма в версии 4BSD. Такая реализация во многом соответствует и версии System V, которая основана на 4BSD.

Идея, лежащая в основе страничной подкачки в системе 4BSD, состоит в том, что процессу для работы не нужно целиком находиться в памяти. Все, что в действи­тельности требуется, – это структура пользователя и таблицы страниц. Если они загружены, то процесс считается находящимся в памяти и может быть запущен планировщиком. Страницы с сегментами текста, данных и стека загружаются в па­мять динамически, по мере обращения к ним. Если пользовательской структуры и таблицы страниц нет в памяти, то процесс не может быть запущен, пока свопер не загрузит их.

Страничная подкачка реализуется частично ядром и частично новым про­цессом, называемым страничным демоном. Как и все демоны, страничный демон периодически запускается и смотрит, есть ли для него работа. Если он обнаруживает, что количество страниц в списке свободных стра­ниц слишком мало, страничный демон инициирует действия по освобождению дополнительных страниц.

Память в 4BSD делится на три части. Первые две части, ядро операционной системы и карта памяти, фиксированы в фи­зической памяти (то есть никогда не выгружаются). Остальная память машины делится на страничные блоки, каждый из которых может содержать либо страницу текста, данных или стека, либо находиться в списке свободных страниц.

Карта памяти содержит информацию о содержимом страничных блоков. Для каждого страничного блока в карте памяти есть запись фиксированной длины. При килобайтных страничных блоках и 16-байтовых записях карты памяти на нее расходуется менее 2 % от общего объема памяти. Первые два поля записи карты памяти используются только тогда, когда соответствующий страничный блок находится в списке свободных страниц. В этом случае они сшивают свобод­ные страницы в двусвязный список. Следующие три записи используются, когда страничный блок содержит информацию. У каждой страницы в памяти есть фик­сированное место хранения на диске, в которое она помещается, когда выгружает­ся из памяти. Еще три поля содержат ссылку на запись в таблице процессов, тип хранящегося в странице сегмента и смещение в сегменте процесса. Последнее поле содержит некоторые флаги, нужные для алгоритма страничной подкачки. При запуске процесс может вызвать страничное прерывание, если одной или нескольких его страниц не окажется в памяти. При страничном прерывании опе­рационная система берет первый страничный блок из списка свободных страниц, удаляет его из списка и считывает в него требуемую страницу. Если список сво­бодных страниц пуст, выполнение процесса приостанавливается до тех пор, пока страничный демон не освободит страничный блок.

Алгоритм замещения страниц выполняется страничным демоном. Раз в 250 мс он сравнивает количество свободных страничных блоков с систем­ным параметром lotsfree (равным, как правило, 1/4 объема памяти). Если число свободных страничных блоков меньше, чем значение этого параметра, страничный демон начинает переносить страницы из памяти на диск, пока количество свобод­ных страничных блоков не станет равно lotsfree. Если же количество свободных страничных блоков больше или равно lotsfree, тогда страничный демон ничего не предпринимает. Если в машине много памяти и мало активных процессов, страничный демон практически все время бездействует.

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

Изначально в версии UNIX 4BSD использовался основной алгоритм часов, но затем он был заменен более эффективным алгоритмом часов с двумя стрелками. В этом алгоритме страничный демон под­держивает два указателя на карту памяти. При работе он сначала очищает бит использования передней стрелкой, а затем проверяет этот бит задней стрелкой. После чего перемещает обе стрелки. Если две стрелки находятся близко друг от друга, то только у очень активно используемых страниц появляется шанс, что к ним будет обращение между проходами двух стрелок. Если же стрелки разнесены на 359 градусов (то есть задняя стрелка находится слегка впереди передней), то по сути снова получается исходный алгоритм часов. При каждом запуске страничного демона стрелки проходят не полный оборот, а столько, сколько необходимо, что­бы количество страниц в списке свободных страниц было не менее lotsfree.

Если операционная система обнаруживает, что частота подкачки страниц слишком высока, а количество свободных страниц все время ниже lotsfree, свопер начинает удалять из памяти один или несколько процессов, чтобы остановить состязание за свободные страничные блоки. Свопинг в системе 4BSD осуществляется по следующему алгоритму. Сначала свопер проверяет, есть ли процесс, который бездействовал в течение 20 и более секунд. Если такие процессы есть, из них выбирается бездей­ствовавший в течение максимального срока и выгружается на диск. Если таких процессов нет, изучаются четыре самых больших процесса, из которых выбирает­ся тот, который находился в памяти дольше всех, и выгружается на диск. При не­обходимости этот алгоритм повторяется до тех пор, пока не будет высвобождено достаточное количество памяти.

Каждые несколько секунд свопер проверяет, есть ли на диске готовые процес­сы, которые следует загрузить в память. Каждому процессу на диске присваива­ется значение, зависящее от времени его пребывания в выгруженном состоянии, размера, значения, использовавшегося при обращении к системному вызову nice (если такое обращение было), и от того, как долго этот процесс бездействовал, прежде чем был выгружен на диск. Эта функция обычно взвешивается так, чтобы загружать в память процесс, дольше всех находящийся в выгруженном состоянии, если толь­ко он не крайне большой. Теория утверждает, что загружать большие процессы дорого, поэтому их не следует перемещать с диска в память и обратно слишком часто. Загрузка про­цесса производится только при условии наличия достаточного количества свобод­ных страниц, чтобы, когда случится неизбежное страничное прерывание, для него нашлись свободные страничные блоки. Свопер загружает в память только струк­туру пользователя и таблицы страниц. Страницы с текстом, данными и стеком подгружаются при помощи обычной страничной подкачки.

У каждого сегмента каждого активного процесса есть место на диске, где он располагается, когда его страницы удаляются из памяти. Сегменты данных и сте­ка сохраняются на временном устройстве, но текст программы подгружается из самого исполняемого двоичного файла. Для текста программы временная копия не используется.

Страничная подкачка в версии System V во многом схожа с применяемой в системе 4BSD, но тем не менее между этими версиями операционной системы есть интересные различия. Во-первых, в System V вместо алгоритма часов с двумя стрелками использует­ся оригинальный алгоритм часов с одной стрелкой. Более того, вместо того чтобы помещать страницу в список свободных страниц на втором проходе, страница по­мещается туда только в случае, если она не использовалась в течение нескольких последовательных проходов. Хотя при таком решении страницы не освобождаются так быстро, как это делается алгоритмом в 4BSD, оно значительно увели­чивает вероятность того, что освобожденная страница не потребуется тут же снова. Во-вторых, вместо единственной переменной lotsfree в System V используются две переменные: min и max. Когда количество свободных страниц опускается ниже min, страничный демон начинает освобождать страницы. Демон продолжает рабо­тать до тех пор, пока число свободных страниц не сравняется со значением max. Такой подход позволяет избежать неустойчивости, возможной в системе 4DSD, например, в ситуации, когда количество свободных страниц на единицу мень­ше, чем lotsfree. При этом страничный демон освобождает одну страницу, чтобы привести количество свободных страниц в соответствие со значением lotsfree. Затем происходит еще одно страничное прерывание, и количество свободных страниц опять становится на единицу меньше lotsfree, в результате страничный демон сно­ва начинает работать. Если установить значение max существенно большим, чем min, страничный демон, завершив освобождение страниц, создает достаточный за­пас для своего бездействмя в течение относительно продолжительного времени.

7.4. Ввод-вывод в системе UNIX