Теория операционных систем
Поиск жертвы
| ..И вот мы образовались вашему приходу,-
может, вы согласитесь принести себя в жертву А. Тутуола |
Естественно, для того чтобы автоматизировать процесс удаления барахла"
— редко используемых данных и программ — мы должны иметь какой-то легко
формализуемый критерий, по которому определяется, какие данные считаются
редко используемыми.
Один критерий выбора очевиден — при прочих равных условиях, в первую очередь
мы должны выбирать в качестве "жертвы" (victim) для удаления
тот объект, который не был изменен за время жизни в быстрой памяти. Действительно,
вы скорее удалите с винчестера саму игрушку (если у вас есть ее копия
на дискетах), чем файлы сохранения!
Для ручного переноса данных очевиден и другой критерий: нужно удалять (Для блоков данных, которые не подверглись изменению за время пребывания в быстрой памяти, удаление будет состоять в уничтожении копии. Для модифицированных же блоков новое значение данных должно быть скопировано обратно в медленную память, и только после этого можно произвести собственно удаление.) то, что дольше всего не будет использоваться в будущем. Конечно, любые предположения о будущем имеют условный характер, все может неожиданно измениться. Мы делаем предположения о том, что будет использоваться, только на основании накопленной статистики обращений к страницам. Такая экстраполяция не совсем корректна логически, поэтому может оказаться целесообразным смириться с некоторой неточностью или неполнотой этой статистики.
Самая простая стратегия — выбрасывать случайно выбранный объект. При этом не надо собирать никакой статистики о частоте использования и т. д., важно лишь обеспечить равномерность распределения генерируемых псевдослучайных чисел. Очевидно, что при этом удаленный объект совершенно необязательно будет ненужным
Можно также удалять то, что дольше всего находится в памяти. Это называется алгоритмом FIFO (First In, First Out, первый вошел, первый вышел). Видно, что это уже чуть сложнее случайного удаления — нужно запоминать, когда мы что загружали.
Поиск жертвы в VAX/VMS и Windows NT/2000/XP
В VAX/VMS и Windows NT/2000/XP применяется любопытный вариант этого алгоритма.
В этих системах страница, объявленная жертвой, исключается из адресного
пространства задачи (у соответствующего дескриптора выставляется бит отсутствия),
но не отдается немедленно под другие нужды. Вместо этого страницы, помеченные
как отсутствующие, помещаются в пул свободных страниц, который, по совместительству,
используется и для дискового кэша и может занимать более половины оперативной
памяти. У VAX/VMS этот пул состоит из трех очередей (рис. 5.19).
1. Очередь модифицированных страниц, ждущих записи на
диск (по мере записи, эти страницы переходят во вторую очередь).
2. Очередь немодифицированных страниц.
3. Очередь свободных страниц (освобожденных прикладной программой или
освободившихся после ее завершения).
Жертвой с равной вероятностью может быть объявлена как модифицированная,
так и немодифицированная страница, однако для запросов прикладных программ
и буферов дискового кэша используются только страницы из второй и третьей
очередей.
Рис. 5.19. Виртуальная память VAX/VMS
Обрабатывая страничный отказ, система не обращается к диску
за содержимым требуемой страницы, а сначала пытается найти ее в одной
из очередей пула. Если страница там, ее без дальнейших вопросов включают
в адресное пространство задачи (рис. 5.20).
Такой алгоритм порождает много лишних страничных отказов, но обеспечивает
большую экономию обращений к диску. У VAX/VMS эта стратегия сочетается
с управлением объемом пула страниц: у каждого пользователя есть квота
на объем рабочего множества запущенных им программ. При превышении квоты
ОС и осуществляет поиск жертвы среди адресных пространств задач этого
пользователя. При разумном управлении этими квотами система обеспечивает
весьма хорошие показатели даже при небольших объемах оперативной памяти.
Windows NT (и более поздние версии этой системы, 2000/ХР) пытается управлять
пулом свободных страниц динамически, не предоставляя администратору никаких
средств для прямой настройки. Поэтому на нехватку ОЗУ или нетипичный режим
использования памяти эта система реагирует резким падением производительности.
По-видимому, это падение обусловлено развитием автоколебаний в динамической
настройке пула свободных страниц.
Так, автору удавалось привести в неработоспособное состояние Windows 2000
Wokrstation с 256 Мбайт ОЗУ, всего лишь открыв по ошибке для редактирования
в far файл объемом 64 Мбайт. Файл не превосходил 1/4 доступной оперативной
памяти. Тем не менее, машина "впала в кому", не реагируя даже
на <Ctrl>+<Alt>+<Del>, и находилась в этом состоянии
достаточно долго для того,чтобы собрать вокруг нее консилиум системных
администраторов и, в конце концов, решить, что проще нажать на кнопку
системного сброса.
Рис. 5.20. Обработка страничного отказа (блок-схема)
Фирма Microsoft вполне сознает ущербность принятой стратегии управления памятью и официально не рекомендует запускаыть на серверах под управлением Windows NT/2000/XP более одного приложения или ресурсоемкого сервиса.
Пул свободных страниц, в который входят как действительно свободные,
так и отобранные у задач в качестве "жертв" страницы, в той
или иной форме поддерживают все ОС, использующие страничный обмен, однако
обычно этот пул отделяют от дискового кэша и при полной загрузке он не
превосходит нескольких процентов ОЗУ. При запросах ядра и страничных отказах
система выделяет страницы из этого пула, и только при падении его объема
ниже некоторого предела, начинает поиск жертв в адресных пространствах
активных процессов.
Шиболее справедливым будет удалять тот объект, к которому дольше всего
не было обращений в прошлом 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-бит и признак модификации. Признак модификации устанавливается при первой записи в страницу/сегмент, в дескрипторе которой этот признак был сброшен.
Имитация clock-алгоритма
Ранние версии процессора VAX не имели аппаратно реализованного clock-бита.
BSD Unix на этих процессорах реализовал clock-алгоритм, используя для
этого бит отсутствия страницы.
Читателю предлагается детально представить себе алгоритм такого использования
и найти отличия между этой стратегией и FIFO-алгоритмом в исполнении VAX/VMS.
Экспериментааьные исследования показывают, что реальная производительность
системы довольно слабо зависит от применяемого алгоритма поиска жертвы.
Статистика исполнения реальных программ говорит о том, что каждая программа
имеет некоторый набор страниц, называемый рабочим
множеством, который ей в данный момент действительно нужен. Размер
такого набора сильно зависит от алгоритма программы, он изменяется на
различных этапах исполнения и т. д.. но в большинстве моментов мы модем
довольно точно указать его.
Если рабочий набор запущенных программ превосходит оперативную память,
частота страничных отказов резко возрастает. При нехватке памяти программе
почти на каждой команде требуется новая страница, и производительность
системы катастрофически падает. Это состояние по-английски называется
thrashing (общепринятого перевода для этого
слова нет) и является крайне нежелательным.
В системах коллективного пользования размер памяти часто выбирают так,
чтобы система балансировала где-то между состоянием, когда все программы
держат свое рабочее множество в ОЗУ, и трэшингом.
Точное положение точки балансировки определяется в зависимости от соотношения
между скоростью процессора и скоростью обмена с диском, а также от потребностей
прикладных программ. Во многих старых учебниках рекомендуется подбирать
объем памяти так, чтобы канал дискового обмена был загружен на 50% [Краковяк
1987].
Еще одно эмпирическое правило приводится в документации фирмы Amdahl:
сбалансированная система должна иметь по мегабайту памяти на каждый MIPS
(Million of Instructions Per Second — миллион операций в секунду) производительности
центрального процессора. Если система не использует память, определенную
по этой формуле, есть основания считать, что процессор также работает
с недогрузкой. Иными словами, это означает, что вы купили слишком мощный
для ваших целей процессор и заплатили лишние деньги.
Это правило было выработано на основе опыта эксплуатации больших компьютеров
четвертого поколения, в основном на задачах управления базами данных.
Скорость дисковой подсистемы в этих машинах была примерно сравнима с дисковыми
контроллерами современных персональных компьютеров, поэтому в первом приближении
этот критерий применим и к ПК, особенно работающим под управлением систем
с виртуальной памятью — OS/2, Windows NT и системами семейства Unix. В
любом случае, для выдачи рекомендаций требуется анализ смеси приложений,
которая будет исполняться в системе, и других требований к ней.
В современных персональных системах пользователь, как правило, работает
в каждый момент только с одной-двумя программами, и задержки в исполнении
этих программ существенно снижают наблюдаемую скорость системы. Поэтому
в таких системах память обычно ставят с большим запасом, так, чтобы при
обычной деятельности рабочие множества программ даже близко не подходили
к размеру ОЗУ. Отчасти это обусловлено тем, что в наше время динамическая
память становится все дешевле и дешевле.
