Поиск жертвы
Наиболее справедливым будет удалять тот объект, к которому дольше всего не было обращений в прошлом LRU (Leasr Recently Used). Такой подход требует набора сведений обо всех обращениях. Например, диспетчер памяти должен поддерживать в дескрипторе каждой страницы счетчик обращений, и при каждой операции чтения или записи над этой страницей увеличивать этот счетчик на единицу. Это требует довольно больших накладных расходов – в ряде работ, например, в [Краковяк 1987], утверждается, что они будут недопустимо большими.
Остроумным приближением к алгоритму LRU является так называемый clock-алгоритм, применяемый во многих современных ОС, в том числе в системах семейства Unix. Он состоит в следующем (рис. 5.21).
- Дескриптор каждой страницы содержит бит, указывающий, что к данной странице было обращение. Этот бит называют clock-битом.
- При первом обращении к странице, в которой clock-бит был сброшен, диспетчер памяти устанавливает этот бит.
- Программа, занимающаяся поиском жертвы, циклически просматривает все дескрипторы страниц. Если clock-бит сброшен, данная страница объявляется жертвой, и просмотр заканчивается до появления потребности в новой странице. Если clock-бит установлен, то программа сбрасывает его и продолжает поиск.
Рис. 5.21. Clock-алгоритм (блок-схема)
Название clock, по-видимому, происходит от внешнего сходства процесса циклического просмотра с движением стрелки часов (рис. 5.22). Очевидно что вероятность оказаться жертвой для страницы, к которой часто происходят обращения, существенно ниже. Накладные расходы этого алгоритма гораздо меньше, чем у LRU: вместо счетчика мы храним только один бит и изменяем его не при каждом обращении к странице, а только при первом обращении после прохода "стрелки".
Рис. 5.22. Работа clock-алгоритма
Практически все известные автору современные диспетчеры памяти предполагают использование clock-алгоритма. Такие диспетчеры хранят в дескрипторе страницы или сегмента два бита – clock-бит и признак модификации. Признак модификации устанавливается при первой записи в страницу/сегмент, в дескрипторе которой этот признак был сброшен.