Переменное распределение, локальная область видимости

С помощью данной стратегии делается попытка преодолеть проблемы, возникающие при использовании стратегии глобальной области видимости. Вкратце ее можно описать следующим образом.

1. При загрузке нового процесса в основную память ему в качестве резидентного множества выделяется некоторое количество кадров страниц; количество кадров определяется исходя из типа приложения, запроса программы или на основе других критериев. Для заполнения резидентного множества используется стратегия выборки по требованию либо предварительная выборка.

2. При возникновении прерывания из-за отсутствия страницы страница для замещения выбирается среди резидентного множества процесса, сгенерировавшего прерывание.

Время от времени выполняется переоценка распределения памяти процессам, которая приводит к увеличению или уменьшению размера выделяемой процессу памяти для повышения общей производительности системы.

При использовании данной стратегии решение об увеличении или уменьшении размера резидентного множества принимается на основе оценки ожидаемых требований активных процессов. Такая оценка делает эту стратегию более сложной, чем простая стратегия глобального замещения, но приводит к повышению производительности системы.

Ключевыми элементами стратегии переменного распределения с локальной областью видимости являются критерии, используемые для определения размера резидентного множества и момента внесения изменений. Одна из стратегий, чаще других упоминаемая в литературе, известна как стратегия рабочего множества (working set strategy). Хотя ее реализация очень сложна, следует изучить данную стратегию хотя бы как критерий для оценки других.

Рабочее множество представляет собой концепцию, введенную Деннингом (Denning) и популяризованную в работах [DENN68, DENN70, DENNSOb]; эта концепция оказала большое влияние на разработку систем управления виртуальной памятью. Рабочее множество с параметром процесса в вирту­альный момент времени t представляет собой множество страниц, к которым процесс обращался за последние единиц виртуального времени. Здесь мы ис­пользуем концепцию виртуального времени, которое является временем реаль­ного выполнения процесса. Его можно измерять в командах процессора — каж­дая команда представляет собой одну единицу виртуального времени.

Рассмотрим каждую из двух переменных W. Переменная — это "окно", сквозь которое мы наблюдаем за процессом. Размер рабочего множества пред­ставляет собой неубывающую функцию от размера окна. В табл. 8.5 (взятойиз [ВАСН85]) показаны последовательности обращений процесса к страницам. Точ­ки в таблице обозначают моменты времени, когда рабочее множество не изменялось. Обратите внимание — чем больше размер окна, тем больше и рабочее множество. Это можно выразить следующим соотношением:

Таблица 8.5. Зависимость размера рабочего множества процесса от размера окна

Рабочее множество является также функцией и от времени. Если продолжи­тельность процесса более единиц времени и он использует только одну страницу, то = 1. Рабочее множество процесса может расти с той же скоростью,что иколичество страниц процесса N, если приего выполнении происходят обращения к различным страницам и если это позволяет выбранный размер окна,т.е.

На рис. 8.19 показан один из вариантов изменения во времени размера рабочего множества при фиксированном значении Д. Для многих программ периоды относительно стабильного рабочего множества чередуются с периодами быстрых изменений. В начале выполнения процесса рабочее множество быстро растет за счет обращения к новым страницам. В итоге в соответствии с принципом локализации процесс должен стабилизироваться с определенным множеством страниц. Последующие переходные периоды отражают изменение стабильного состояния. В это время некоторые старые страницы все еще остаются в пределах окна , вызывая всплеск рабочего множества при обращении процесса к новым страницам. Постепенно старые страницы уходятиз окна, и в окне остаются только страницы, соответствующие новой локализации процесса.

Концепция рабочего множества может использоваться стратегией определения размера резидентного множества.

1. Отслеживаем рабочее множество каждого процесса.

2. Периодически удаляем из резидентного множества страницы, не входящие в рабочее множество.

3. Процесс может выполняться только тогда, когда его рабочее множество находится в основной памяти (т.е. его резидентное множество включает рабочее множество).

Эта стратегия, использующая принцип локализации, должна минимизировать количество прерываний из-за отсутствия страниц, но, к сожалению, при этом возникает ряд проблем.

1. По прошлому не всегда можно судить о будущем. Как размер рабочего множества, так и его состав время от времени изменяются (см., например, рис. 8.19).

2. Определение рабочего множества каждого процесса непрактично. Для этого необходимо помечать время обращения каждого процесса к каждой странице с использованием виртуального времени процесса, а также поддерживать упорядоченную по времени обращения очередь страниц для каждого процесса.

3. Оптимальное значениенеизвестно и для разных ситуаций может быть различным.

Тем не менее, сама идея данной стратегии вполне корректна, и ряд операционных систем пытаются к ней приблизиться. Один из способов сделать это заключается не в работе с конкретными обращениями к страницам, а в работе с уровнем генерации данным процессом прерываний из-за отсутствия страницы. Как показано на рис. 8.11,б, с ростом резидентного множества процесса уровень генерации прерываний падает. Таким образом, вместо непосредственного отслеживания рабочего множества мы можем получить сравнимые результаты путем отслеживания уровня генерации прерываний. Если уровень генерации прерываний у какого-то процесса ниже некоторого минимального порога, система может выиграть, назначив данному процессу резидентное множество меньшего размера (и освободив кадры основной памяти для других процессов) без ущерба для этого процесса. Если же для некоторого процесса уровень генерации прерываний превысил некоторое максимальное пороговое значение, то следует, по возможности, увеличить размер его резидентного множества.

Соответствующий этой стратегии алгоритм называется алгоритмомчастоты прерываний обращения к странице (page fault frequency — PFF) [CHU72, GUPT78]. Этот алгоритм требует наличия у каждой страницы в основной памяти бита использования, устанавливаемого равным 1 при обращении к странице. Когда возникает прерывание обращения к странице, операционная система замечает виртуальное время с момента последней генерации прерывания из-за отсутствия страницы данным процессом; это осуществляется посредством счетчика обращений к страницам. Если прошедшее с момента последнего прерывания время меньше определенного порога F, то страница добавляется к резидентному множеству процесса. В противном случае все страницы с битом использования, равным 0, сбрасываются, и, соответственно, уменьшается резидентное множество процесса. В этот же момент битам использования всех оставшихся страниц присваивается нулевое значение. Стратегия может быть усовершенствована с помощью двух пороговых значений — верхнего порога, используемого для роста резидентного множества, и нижнего, по достижении которого резидентное множество уменьшается.

Промежутки времени между прерываниями обращения к странице соответствуют частоте генерации прерываний. Хотя лучшим методом представляется измерение средней частоты генерации прерываний обращения к странице, измерение промежутков времени между ними представляет собой вполне разумный компромисс, позволяющий принимать решения о размере резидентного множества. При использовании такой стратегии совместно с буферизацией страниц должны получаться неплохие результаты.

Тем не менее, этот подход имеет один существенный недостаток, заключаю­щийся в его неработоспособности в момент перехода процесса из одного локали­зованного состояния в другое. В этот момент частота генерации прерываний об­ращения к страницам резко возрастает, что, в соответствии с рассмотренным ал­горитмом. вызывает резкое увеличение размера резидентного множества и может привести к таким нежелательным результатам, как деактивация и сво­пинг других процессов.

Обойтись небольшими накладными расходами в переходные периоды при­звана стратегиярабочего множества с переменным пробным интервалом (variable-interval sampled working set — VSWS) [FERR83]. Эта стратегия вычисляет размер рабочего множества процесса по пробным образцам на основе истекшего виртуального времени. В начале пробного интервала бит использования всех резидентных страниц процесса сбрасывается; в конце интервала бит использования установлен только у тех страниц, к которым в этом интервале было обращение. Эти страницы остаются в резидентном множестве в течение следующего интервала времени; остальные страницы сбрасываются. Таким образом, размер резидентного множества может уменьшаться только в конце каждого интервала. В течение интервала страницы, вызвавшие ошибку обращения, добавляются к резидентному множеству (таким образом, в это время размер резидентного множества не убывает).

Стратегия VSWS руководствуется тремя параметрами:

M — минимальная продолжительность пробного интервала;

L — максимальная продолжительность пробного интервала;

Q — допустимое количество прерываний обращения к странице, которые могут произойти между пробными интервалами.

Стратегия VSWS работает следующим образом.

1. Если виртуальный промежуток времени с момента последнего пробного интервала достиг L, процесс приостанавливается и выполняется сканирование битов использования.

2. Если до истечения виртуального времени L произошло Q прерываний обращения, то:

а) если виртуальное время с момента последнего пробного интервала меньше М, мы ожидаем, пока не пройдет этот промежуток времени, чтобы приступить к сканированиюбитов использования;

б) если же это время не меньше М, процесс приостанавливается и начинается сканирование битов использования.

Значения параметров выбираются такими, чтобы обычно процесс сканирования запускался по достижении Q-го прерывания обращения к странице; остальные два параметра служат граничными значениями для исключительных условий. С помощью стратегии VSWS делается попытка снизить пиковые требования к памяти, вызываемые переходами процесса от одной локализации к другой путем сброса неиспользуемых страниц при учащении генерации прерываний обращения. Опыт использования этой стратегии в операционной системе для мейнфреймов GCOS 8 показывает, что стратегия VSWS столь же проста в реализации, как и стратегия PFF, но при этом более эффективна [PIZZ89].

Стратегия очистки

Стратегия очистки является противоположностью стратегии выборки. Ее задача состоит в определении момента, когда измененная страница должна быть записана во вторичную память. Два основных ее метода — очистка по требованию и предварительная очистка. При очистке по требованию страница записывается во вторичную память только тогда, когда она выбирается для замещения. Предварительная очистка записывает модифицированные страницы до того, как потребуются занимаемые ими кадры, так что эти страницы могут записываться пакетами.

Имеется опасность прямолинейного следования любой из стратегий. При предварительной очистке записанная страница остается в основной памяти до тех пор, пока ее не удалит оттуда алгоритм замещения. Предварительная очистка позволяет записывать страницы пакетами, но не имеет смысла записывать сотни или тысячи страниц только для того, чтобы убедиться, что до замещения они вновь успели модифицироваться. Пропускная способность вторичной памяти ограничена и не должна засоряться излишними операциями очистки.

С другой стороны, при очистке по требованию запись модифицированной страницы сопровождается чтением новой страницы, так что, несмотря на минимизацию записей страниц, прерывание обращения может вызывать пересылку двух страниц между основной и вторичной памятью и тем самым снижать эффективность использования процессора.

Улучшенный подход включает буферизацию страниц, что позволяет принять следующую стратегию: очищать только замещаемые страницы, но при этом разделить операции очистки и замещения. При использовании буферизации страниц замещаемые страницы могут находиться в двух списках: модифицированных и немодифицированных страниц. Страницы из списка модифицированных могут периодически записываться пакетами и переноситься в список немодифицированных. Страница из списка немодифицированных страниц может либо быть удалена из негопри обращении к ней, либо потеряна при загрузке в ее кадр новой страницы.