Алгоритм «второй шанс»

Простой модификацией алгоритма FIFO, исключающей проблему удаления часто востребуемой страницы, может стать проверка бита R самой старой страницы. Если его значение равно нулю, значит, страница не только старая, но и невостребованная, поэтому она тут же удаляется.
Если бит R имеет значение 1, он сбрасывается, а страница помещается в конец списка страниц и время ее загрузки обновляется, как будто она только что поступила в память. Затем поиск продолжается.

Действие этого алгоритма, названного «второй шанс», показано на рис. 3.14. Страницы с A по H содержатся в связанном списке отсортированными по времени их поступления в память.

Предположим, что ошибка отсутствия страницы возникла на отметке времени 20. Самой старой является страница A, время поступления которой соответствует началу процесса и равно 0. Если бит R для страницы A сброшен, страница либо удаляется из памяти с записью на диск (если она измененная), либо просто удаляется (если она неизмененная). Но если бит R установлен, то A помещается в конец списка и ее «время загрузки» переключается на текущее (20). Также при этом сбрасывается бит R. А поиск подходящей страницы продолжается со страницы B.

Рис. 3.14. Действие алгоритма «второй шанс»: а — страницы, отсортированные в порядке FIFO; б — список страниц при возникновении ошибки отсутствия страницы, показателе времени 20 и установленном в странице А бите R; числа над страницами — это время, когда они были загружены


Алгоритм «второй шанс» занимается поиском ранее загруженной в память страницы, к которой за только что прошедший интервал времени таймера не было обращений. Если обращения были ко всем страницам, то алгоритм «второй шанс» превращается в простой алгоритм FIFO. Представим, в частности, что у всех страниц на рис. 3.14, а бит R установлен. Операционная система поочередно перемещает страницы в конец списка, очищая бит R при каждом добавлении страницы к концу списка. В конце концов она возвращается к странице A, у которой бит R теперь уже сброшен. И тогда страница A выселяется. Таким образом, алгоритм всегда завершает свою работу.

3.4.3.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Алгоритм «второй шанс»:

  1. Спросите, а как отличить шанс от «не-шанса»?
  2. 3. Дайте себе шанс, прежде чем делать окончательный вывод.
  3. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  4. АЛГОРИТМ
  5. АЛГОРИТМ УДАЧИ
  6. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  7. Алгоритм исцеления:
  8. Алгоритм избавления от боли
  9. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  10. Алгоритм обработки результатов.
  11. 2. Специфика и алгоритмы работы с источниками.
  12. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  13. ВТОРОЙ ОТДЕЛ
  14. Второй принцип
  15. Второй закон
  16. Второй закон
  17. Второй ключ.
  18. ВТОРОЙ ОТДЕЛ О ПРАВАХ ВОТЧИННЫХ
  19. ОЧЕРК ВТОРОЙ СОЦИОЛОГИЧЕСКИЙ “СМЕХ”