Поиск жертвы
…И вот мы обрадовались вашему приходу, – может, вы согласитесь принести себя в жертву?
А. Тутуола
Естественно, для того чтобы автоматизировать процесс удаления барахла" – редко используемых данных и программ – мы должны иметь какой-то легко формализуемый критерий, по которому определяется, какие данные считаются редко используемыми.
Один критерий выбора очевиден – при прочих равных условиях, в первую очередь мы должны выбирать в качестве "жертвы" (victim) для удаления тот объект, который не был изменен за время жизни в быстрой памяти. Действительно, вы скорее удалите с винчестера саму игрушку (если у вас есть ее копия на дискетах), чем файлы сохранения!
Для ручного переноса данных очевиден и другой критерий: нужно удалять (Для блоков данных, которые не подверглись изменению за время пребывания в быстрой памяти, удаление будет состоять в уничтожении копии. Для модифицированных же блоков новое значение данных должно быть скопировано обратно в медленную память, и только после этого можно произвести собственно удаление.) то, что дольше всего не будет использоваться в будущем. Конечно, любые предположения о будущем имеют условный характер, все может неожиданно измениться.
Мы делаем предположения о том, что будет использоваться, только на основании накопленной статистики обращений к страницам. Такая экстраполяция не совсем корректна логически, поэтому может оказаться целесообразным смириться с некоторой неточностью или неполнотой этой статистики.
Самая простая стратегия – выбрасывать случайно выбранный объект. При этом не надо собирать никакой статистики о частоте использования и т. д., важно лишь обеспечить равномерность распределения генерируемых псевдослучайных чисел. Очевидно, что при этом удаленный объект совершенно необязательно будет ненужным.
Можно также удалять то, что дольше всего находится в памяти. Это называется алгоритмом FIFO (First In, First Out, первый вошел, первый вышел). Видно, что это уже чуть сложнее случайного удаления – нужно запоминать, когда мы что загружали.
Поиск жертвы в VAX/VMS и Windows NT/2000/XP
В VAX/VMS и Windows NT/2000/XP применяется любопытный вариант этого алгоритма. В этих системах страница, объявленная жертвой, исключается из адресного пространства задачи (у соответствующего дескриптора выставляется бит отсутствия), но не отдается немедленно под другие нужды. Вместо этого страницы, помеченные как отсутствующие, помещаются в пул свободных страниц, который, по совместительству, используется и для дискового кэша и может занимать более половины оперативной памяти.
У VAX/VMS этот пул состоит из трех очередей (рис. 5.19):
- Очередь модифицированных страниц, ждущих записи на диск (по мере записи, эти страницы переходят во вторую очередь).
- Очередь немодифицированных страниц.
- Очередь свободных страниц (освобожденных прикладной программой или освободившихся после ее завершения).
Жертвой с равной вероятностью может быть объявлена как модифицированная, так и немодифицированная страница, однако для запросов прикладных программ и буферов дискового кэша используются только страницы из второй и третьей очередей.
Рис. 5.19. Виртуальная память VAX/VMS