Размещение страниц.
Куда разместить страницу?
Если есть свободное место в ОЗУ, то используем его. Если все занято, то решаем задачу замещения или выталкивания.
Замещение (выталкивание) страниц.
1. Принцип оптимальности.
Надо выталкивать ту страницу, к которой дольше всего не будет обращений. Как это можно определить? Никак!
Стратегия не реализуется.
2. Выталкивание случайной страницы.
Достоинство: быстрое решение с маленькими накладными расходами.
Недостатки: может возрасти частота прерываний (выталкиваем нужную страницу).
Используется крайне редко.
3. Принцип FIFO. Красивое решение, обоснования нет.
Достоинство: достаточно быстрое решение. Недостатки: возможна т.н. аномалия FIFO.
Используется достаточно часто.
4. Выталкивание дольше всего не использовавшейся страницы. LRU (Least Recently Used)
Достоинство: временной анализ.
Недостатки: - накладные расходы на поддержку временных меток
- смотрит назад, а не вперед. Используется достаточно редко.
5. Выталкивание реже всего использовавшейся страницы. LFU (Least Frequently Used)
Будем считать число обращений к странице на заданном интервале.
Достоинство: временной анализ.
Недостатки: - накладные расходы на поддержку временных меток;
-можно вытолкнуть «свежую» страницу;
-трудно вытолкнуть «заслуженного ветерана», страницу которая
сразу набрала много обращений Используется достаточно редко.
5. Выталкивание не использовавшейся в последнее время страницы.
NUR (Not Used Recently)
Будем периодически обновлять счетчик обращений.
Достоинство: устраняем недостаток LFU. Недостатки:- можно вытолкнуть «свежую» страницу; - Используется достаточно редко.
Концепция локальности.
Частота
прерываний
|
|
|
|
|
время |
детство |
|
взрослый |
|
старость |
|
|
|
|
|||
|
|
|
Если процесс перешел в фазу «взрослый», в памяти надо держать страницы относящиеся к его «рабочему множеству».
Локальность (по Деннингу) бывает:
Временная – процесс может вернуться к текущей ячейке, т.к. в программе присутствуют циклы.
Пространственная – процесс переходит к следующей ячейке благодаря своей последовательной структуре.
Fint |
|
Out of mem |
Равновероятное обращение к страницам |
1,0 |
|
|
Процесс с локализованными обращениями |
0,5 |
|
Доля страниц процесса в ОЗУ
0,5 1,0
Как найти рабочее множество? Только мониторинг!
Некоторые выводы:
1.Чем меньше размер страницы, тем больше объем Page Table
2.Чем больше объем страницы, тем больше доля «лишней» информации
3.Чем больше объем страницы, тем быстрее пройдет загрузка программы
4.Чем меньше объем страницы, тем легче составить «правильное» рабочее множество.
Оптимальны страницы относительно небольшого объема – 1 килобайт