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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рабочее множество представляет собой концепцию, введенную Деннингом (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,б,с ростом резидентного множества процесса уровень генерации прерываний падает. Таким образом, вместо непосредственного отслеживания рабочего множества мы можем получить сравнимые результаты путем отслеживания уровня генерации прерываний. Если уровень генерации прерываний у какого-то процесса ниже некоторого минимального порога, система может выиграть, назначив данному процессу резидентное множество меньшего размера (и освободив кадры основной памяти для других процессов) без ущерба для этого процесса. Если же для некоторого процесса уровень генерации прерываний превысил некоторое максимальное пороговое значение, то следует, по возможности, увеличить размер его резидентного множества.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Управление загрузкой

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

Уровень многозадачности

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

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

Еще один подход, известный под названием критерий L=S, был предложен Деннингом (Denning) и его коллегами [DENNSOb]. При этом подходе уровень многозадачности настраивается таким образом, чтобы среднее время между прерываниями равнялось среднему времени, требующемуся для обработки прерывания. В результате исследований сделан вывод, что этот уровень многозадачности обеспечивает максимальную производительность процессора. Использование стратегии с аналогичным эффектом, предложенной в [LER076] и известной каккритерий 50%,способствует поддержке степени использования устройства хранения страниц на уровне 50%. Исследования показывают, что при этом также достигается максимальная степень использования процессора.

Еще один подход состоит в адаптации часового алгоритма замещения, описанного ранее (см. рис. 8.16). В [CARR84] описана методика с использованием глобальной области видимости, которая включает отслеживание частоты сканирования циклического буфера кадров. Если частота меньше предопределенного нижнего порога, это указывает на то, что возникла одна из следующих ситуаций.

1. Генерируется малое количество прерываний из-за отсутствия страницы, что приводит к малому количеству перемещений указателя.

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

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

Приостановка процессов

При снижении степени многозадачности один или несколько резидентных в настоящее время процессов должны быть приостановлены (выгружены во вторичную память). В [CARR84] перечислены шесть возможностей.

• Процесс с наименьшим приоритетом. Так реализована стратегия планировщика, не имеющая отношения к вопросам производительности.

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

• Последний активированный процесс.Маловероятно, что у этого процесса рабочее множество резидентно.

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

• Наибольший процесс.При этом выборе мы освобождаем большое количество кадров перегруженной процессами памяти, снижая тем самым количест­во процессов, которые должны быть деактивированы.

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

Как и во многих других областях разработки операционных систем, выбор стратегии основан на здравом смысле и зависит от множества факторов, как, на­пример, характеристик выполняемых в системе программ.