Стратегии выборки. Их цель – определить, в какой момент следует переписать страницу или сегмент из вторичной памяти в первичную. Выборка по запросу (по требованию) предполагает, что система ждёт ссылки на страницу или сегмент от выполняющегося процесса и только после её появления начинает переписывать данную страницу или сегмент в первичную память. Выборка с упреждением (опережением) предполагает, что система пытается заблаговременно определить к каким страницам или сегментам будет обращаться процесс. В настоящее время в современных операционных системах используется стратегия выборки по требованию с кластеризацией. (см. принцип локальности)
Стратегии размещения. Их цель – определить, в какое место первичной памяти помещать поступающую страницу или сегмент. Стратегия первого подходящего, хотя могут быть и наиболее подходящего и наименее.
Стратегии замещения. Их цель – определить, какую страницу или сегмент следует удалить из первичной памяти, чтобы освободить место для помещения поступающей страницы или сегмента, если первичная память полностью занята.
Стратегии замещения страниц. Рассмотрим следующие стратегии:
1. – принцип оптимальности;
2. – замещение случайной страницы;
3. – замещение первой пришедшей страницы (принцип FIFO);
4. - замещение дольше всего не использовавшейся страницы (алгоритм вторая попытка - модификация принципа FIFO);
5. - замещение наименее часто использовавшейся страницы;
6. - замещение не использовавшейся в последнее время страницы (алгоритм часов).
1) принцип оптимальности говорит о том, что для обеспечения оптимальных скоростных характеристик и эффективного использования ресурсов следует заменять ту страницу, к которой в дальнейшем не будет новых обращений в течение наиболее длительного времени. Однако, реализовать её естественно нельзя, но будем наиболее близко подходить к принципу оптимальности применяя различные методы выталкивания страниц.
2) (замещение случайной страницы) Эта стратегия характеризуется малыми издержками. В этом случае все страницы, находящиеся в основной памяти, могут быть выбраны для выталкивания с равной вероятностью. В реальных системах она применяется редко.
3) (FIFO) При выталкивании страниц по этому принципу мы присваиваем каждой странице в момент поступления в основную память временную метку. В случае необходимости удаления из основной памяти какой-либо страницы выбирается та, которая находилась в памяти дольше других. Однако эта стратегия с достаточно большой вероятностью будет приводить к замещению активно используемых страниц, поскольку тот факт, что страница находится в основной памяти в течение длительного времени, вполне может означать, что она постоянно в работе.
4) (вторая попытка) Эта стратегия предусматривает, что для выталкивания следует выбирать ту страницу, которая не использовалась дольше других. Эта стратегия требует, чтобы каждой странице присваивался бит обращения. Если страница самая старая и к ней не было обращений, то она замещается. Если обращения были, то время ее загрузки обновляется и страница переносится в конец очереди претендентов на замещение. Используется в Windows NT.
5) (замещение наименее часто использовавшейся страницы) В этом случае необходимо контролировать интенсивность использования каждой страницы. Выталкивается та, обращения к которой наименее часты. Однако такой подход тоже может быть нерациональным. Например, наименее интенсивно используемой может оказаться та страница, которую только что переписали в основную память и к которой успели обратиться только один раз, в то время как к другим уже могли обращаться большее число раз. Windows 9x
6) (Алгоритм часов, Unix) Каждые 250 мс просыпается страничный демон, чтобы сравнить количество свободных страниц с 1/4 объема оперативной памяти. Если оказывается что свободной памяти меньше 1/4 объема оперативной памяти, то страничный демон начинает сканировать в цикле страничные блоки так как если бы они были расположены на циферблате часов. На первом проходе сбрасываются биты обращения страничных блоков. На втором проходе биты обращения проверяются и если обращений не было, то такой блок сбрасывается на диск.
Реализация этой стратегии допускает введение двух аппаратных битов-признаков на страницу. Это а) – бит-признак обращения = 0, если к странице не было обращений; = 1, если были обращения.
б) – бит-признак модификации = 0, если страница не изменялась; = 1, если страница изменялась.
При этом возможно существование 4 групп страниц:
1) Обращений не было, модификаций не было.
2) Обращений не было, модификация была.
3) Обращения были, модификаций не было.
4) Обращения были, модификация была.
Страницы групп с меньшим номером следует выталкивать в первую очередь.
