Алгоритм «второй шанс»
Действие этого алгоритма, названного «второй шанс», показано на рис. 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.
Еще по теме Алгоритм «второй шанс»:
- Спросите, а как отличить шанс от «не-шанса»?
- 3. Дайте себе шанс, прежде чем делать окончательный вывод.
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- Алгоритм исцеления:
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- 2. Специфика и алгоритмы работы с источниками.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- ВТОРОЙ ОТДЕЛ
- Второй принцип
- Второй закон
- Второй закон
- Второй ключ.
- ВТОРОЙ ОТДЕЛ О ПРАВАХ ВОТЧИННЫХ
- ОЧЕРК ВТОРОЙ СОЦИОЛОГИЧЕСКИЙ “СМЕХ”