Алгоритмы управления памятью в ОС UNIX, Linux. Замещение страниц

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

Сначала свопинг рассматривал блокированные процессы, либо процессы, находящиеся в памяти долгое время. Если блокированных процессов не было. То выбирался готовый к выполнению процесс. Начиная с версии 3BSD в системе управления памятью появился механизм страничной подкачки, что позволяло выполняться программам самых больших размеров.

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

Страничный демон периодически сравнивает количество свободных блоков с ¼ V ОП и если окажется что, что число свободных блоков меньше этого объема, то страничный демон начинает перемещать страницы из памяти на диск до тех пор, пока количество свободных блоков не сравняется с ¼ объемом ОП.

Страничный демон использует модифицированную версию алгоритма часов. Это глобальный алгоритм, т.те. при замещении страницы он не учитывает к какому процессу относится эта страница.

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

Изначально в Юникс использовался основной механизм, но потом обнаружилось что при большом объеме ОП проход занимает много времени, тогда основной алгоритм часов был заменен на алгоритм часов с 2 стрелками.

При работе страничный демон сначала очищал бит использования первой стрелкой,, а потом проверял бит использования задней стрелкой. При каждом запуске стрелки проходили неполный оборот, а сколько нужно чтобы количество свободных блоков равнялось ¼ ОП.

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

Алгорим свопинга следующий:

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

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

В system5 в отличие от bsd можно выделить 2 отличия в алгоритме страничной подкачки:

1)Вместо алгоритма с 2 стрелками и спользуется алгоритм с одной. Более того страницы помещаются в список свободных страниц если она не использовалась в течении нескольких проходов. При таком решении страницы не высвобождается быстро. Зато увеличивается вероятность, что после замещения она туту же не потребуется вновь

2) Вместо одной переменной LOSTFREE появились 2 переменные max и min.

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

Управление памятью в Linux

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

Алгоритм замещения страниц работает следующим образом:

ОС Линукс пытается поддерживать некоторое количество страниц свободными, чтобы их можно было использовать для загрузки некоторого процсаа. Во время загрузки ОС процесс INIT запускает страничного демона, который работает 1 раз в секунду и проверяет есть ли достаточное количество страниц. Страничный демон состоит из цикла который выполняется до 6 раз с возрастающей срочностью. Тело цикла обращается к 3 процедурам, каждая из которых пытается получить различные типы страниц. Значение срочности передается в качестве параметра к процедуре и означает сколько страниц надо проверить. Сначала этот алгоритм получает легкодоступные страницы, затем труднодоступные.

1 процедура- пытается определить те страницы из страниц КЭША к которым в последнее время никто не обращался для этого используется алгоритм часов.

2 процедура – ищет совместно используемые страницы. Которыми никто из пользователей активно не пользуется.

3 Процедура- выполняет цикл по всем процессам в поиске процесса, у которого в данный момент времени больше всего страниц находится в памяти и к нему применяется алгоритм часов.

Если страница выбранная для замещения чистая (не было модификации), то она удаляется немедленно. Если была произведена модификация страницы. То она становится в очередь записи на диск.