The design of the UNIX Operating System 57 страница
Существует большое количество разнообразных алгоритмов замещения страниц. Все они делятся на ло-кальные и глобальные. Локальные алгоритмы, в отличие от глобальных, распределяют фиксированное или динамически настраиваемое число страниц для каждого процесса. Когда процесс израсходует все предназначенные ему страницы, система будет удалять из физической памяти одну из его страниц, а не из страниц других процессов. Глобальный же алгоритм замещения в случае возникновения исключи-тельной ситуации удовлетворится освобождением любой физической страницы, независимо от того, ка-кому процессу она принадлежала.
|
|
|
Глобальные алгоритмы имеют ряд недостатков. Во-первых, они делают одни процессы чувствительными к поведению других процессов. Например, если один процесс в системе одновременно использует боль-шое количество страниц памяти, то все остальные приложения будут в результате ощущать сильное за-медление из-за недостатка кадров памяти для своей работы. Во-вторых , некорректно работающее прило-жение может подорвать работу всей системы (если, конечно, в системе не предусмотрено ограничение на размер памяти, выделяемой процессу), пытаясь захватить больше памяти. Поэтому в многозадачной сис-теме иногда приходится использовать более сложные локальные алгоритмы. Применение локальных ал-горитмов требует хранения в операционной системе списка физических кадров, выделенных каждому процессу. Этот список страниц иногда называют резидентным множеством процесса. В одном из сле-дующих разделов рассмотрен вариант алгоритма подкачки, основанный на приведении резидентного множества в соответствие так называемому рабочему набору процесса.
|
|
|
|
|
|
|
|
|
Эффективность алгоритма обычно оценивается на конкретной последовательности ссылок к памяти, для которой подсчитывается число возникающих page faults. Эта последовательность называется строкой обращений (reference string).Мы можем генерировать строку обращений искусственным образом припомощи датчика случайных чисел или трассируя конкретную систему. Последний метод дает слишком много ссылок, для уменьшения числа которых можно сделать две вещи:
• для конкретного размера страниц можно запоминать только их номера, а не адреса, на которые идет ссылка;
• несколько подряд идущих ссылок на одну страницу можно фиксировать один раз.
Как уже говорилось, большинство процессоров имеют простейшие аппаратные средства, позволяющие собирать некоторую статистику обращений к памяти. Эти средства обычно включают два специальных флага на каждый элемент таблицы страниц . Флаг ссылки (reference бит) автоматически устанавливается, когда происходит любое обращение к этой странице, а уже рассмотренный выше флаг изменения (modify бит) устанавливается , если производится запись в эту страницу. Операционная система периодически проверяет установку таких флагов, для того чтобы выделить активно используемые страницы, после чего значения этих флагов сбрасываются.
Рассмотрим ряд алгоритмов замещения страниц.
Алгоритм FIFO. Выталкивание первой пришедшей страницы
| Основы операционных систем | 91 |
Простейший алгоритм. Каждой странице присваивается временная метка. Реализуется это просто созда-нием очереди страниц, в конец которой страницы попадают, когда загружаются в физическую память, а из начала берутся, когда требуется освободить память. Для замещения выбирается старейшая страница. К сожалению, эта стратегия с достаточной вероятностью будет приводить к замещению активно исполь-зуемых страниц, например страниц кода текстового процессора при редактировании файла. Заметим, что при замещении активных страниц все работает корректно, но page fault происходит немедленно.
Дата добавления: 2021-01-21; просмотров: 96; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!