Операционные системы. Управление ресурсами


Страничная модель - часть 4


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

Стратегия FIFO - первый на входе - первый на выходе - является простейшей. Согласно этой стратегии из реальной памяти вытесняется та страница, которая была раньше других в нее подкачана. Для реализации этой стратегии ОС достаточно организовать список-очередь страниц в реальной памяти с занесением подкачиваемой страницы в "голову" списка и выборкой страницы для вытеснения из "хвоста" списка. Хотя стратегия FIFO и лучше, чем RANDOM, она не учитывает частоты обращений: может быть вытеснена страница, к которой происходят постоянные обращения. Более того, при некоторых комбинациях страничных требований FIFO может давать аномальные результаты: увеличение числа страничных отказов при увеличении числа доступных страничных кадров (см. задания в конце главы).

Многие используемые в современных ОС стратегии вытеснения могут рассматриваться как разновидности стратегии LRU (least recently used) - наименее используемая в настоящее время: вытесняется та страница, к которой дольше всего не было обращений. Это можно рассматривать как попытку приближения к стратегии OPT путем экстраполяции потока страничных требований из прошлого на будущее.


Начало  Назад  Вперед



Книжный магазин