| Предыдущий раздел | Оглавление | Следующий раздел |
4.5.4. Алгоритм «второй шанс»
Простой модификацией алгоритма FIFO, исключающей проблему удаления часто востребованной страницы, может стать проверка бита R самой старой страницы. Если его значение равно нулю, значит, страница не только старая, но и невостребованная, поэтому она тут же удаляется. Если бит R имеет значение 1, он сбрасывается, а страница помещается в конец списка страниц и время ее загрузки обновляется, как будто она только что поступила в память. Затем поиск продолжается.
Действие этого алгоритма, названного «второй шанс», показано на рис. 4.7. Страницы с A по H содержатся в связанном списке отсортированными по времени их поступления в память.
Предположим, что ошибка отсутствия страницы возникла на отметке времени 20. Самой старой является страница A, время поступления которой соответствует началу процесса и равно 0. Если бит R для страницы A сброшен, страница либо удаляется из памяти с записью на диск (если она измененная), либо просто удаляется (если она неизмененная). Но если бит R установлен, то A помещается в конец списка и ее «время загрузки» переключается на текущее (20). Также при этом сбрасывается бит R. А поиск подходящей страницы продолжается со страницы B.
Алгоритм «второй шанс» занимается поиском ранее загруженной в память страницы, к которой за только что прошедший интервал времени таймера не было обращений. Если обращения были ко всем страницам, то алгоритм «второй шанс» превращается в простой алгоритм FIFO. Представим, в частности, что у всех страниц на рис. 4.7, а бит R установлен. Операционная система поочередно перемещает страницы в конец списка, очищая бит R при каждом добавлении страницы к концу списка. В конце концов она возвращается к странице A, у которой бит R теперь уже сброшен. И тогда страница A выселяется. Таким образом, алгоритм всегда завершает свою работу.
| Предыдущий раздел | Оглавление | Следующий раздел |