Алгоритм замещения неиспользовавшейся в последнее время страницы (NRU)

Локальные и глобальные алгоритмы замещения страниц

IX. Алгоритмы замещения страниц

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

Этот подход требует, чтобы система хранила список физических страниц каждого процесса, который называют рабочим множеством процесса.

Большинство процессоров имеют простейшие аппаратные средства, позволяющие собирать некоторую статистику обращений к памяти. Эти средства включают два специальных флага на каждый элемент таблицы страниц: флаг обращения (reference бит), который автоматически устанавливается, когда происходит любое обращение к этой странице, и флаг изменения (modify бит), который устанавливается, если производится запись в эту страницу. Чтобы использовать эти возможности, операционная система должна периодически сбрасывать эти флаги.

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

Недостатки глобальных алгоритмов:

· делают одни процессы чувствительными к поведению других процессов (например, если один процесс в системе использует большое количество памяти, то все остальные процессы будут в результате ощущать замедление из-за недостатка памяти);

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

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

В алгоритме NRU (Not Recently Used)используются биты обращения (R-Referenced) и изменения (M-Modified) в таблице страниц. При обращении бит R выставляется в 1, через некоторое время ОС переводит его в 0. Бит M переводится в 0 только после записи на диск.

Благодаря этим битам можно получить четыре класса страниц:

· не было обращений и изменений (R=0, M=0);

· не было обращений, было изменение (R=0, M=1);

· было обращение, не было изменений (R=1, M=0);

· было обращение и изменение (R=1, M=1).