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

4.5.2. Политики распределения памяти: локальная и глобальная

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

Обратим внимание на рис. 4.16, а. Здесь три процесса. А, В и С, составляют набор работоспособных процессов. Предположим, процесс А вызвал страничное прерывание. Должен ли алгоритм замещения страниц пытаться найти наиболее давно использовавшуюся страницу, учитывая только шесть страниц, предоставленные в данный момент процессу А, или же он должен рассматривать все страницы памяти? Если алгоритм производит поиск только среди страниц процесса А, наименьший возраст имеет страница А5, и мы получаем ситуацию, изображенную на рис. 4.16, б.

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

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

Рис. 4.1 е. Локальный алгоритм замещения страниц в сравнении с глобальным: а - исходная конфигурация; б - локальное замещение страниц; в - глобальное замещение страниц

Другой способ состоит в том, чтобы иметь в системе алгоритм для распределения страничных блоков между процессами. Например, можно периодически определять количество работающих процессов и предоставлять каждому равную часть памяти. Соответственно, при наличии доступных (то есть не принадлежащих операционной системе) 12 416 страничных блоков и 10 процессах каждый процесс получит 1241 блок. Оставшиеся шесть блоков поступают в резерв для использования в тот момент, когда происходит страничное прерывание.

Хотя этот метод кажется справедливым, существует небольшой шанс, что процессы размером 10 Кбайт и 300 Кбайт получат равные области памяти. Вместо этого можно предоставлять страницы пропорционально абсолютному размеру каждого процесса, тогда больший из этих двух процессов получит долю памяти в 30 раз больше, чем меньший процесс. Разумно отдавать каждому процессу некоторый минимум, чтобы он мог работать независимо от своего размера. На некоторых машинах, например, одиночная команда процессора, включающая в себя два операнда, может нуждаться в целых шести страницах, поскольку сама команда, операнд-источник и операнд-приемник могут располагаться на разных страницах. Если предоставить только пять страниц, программа, содержащая подобную инструкцию, вообще не сумеет выполниться.

Если используется глобальный алгоритм, допустимо запускать каждый процесс с некоторым количеством страниц, пропорциональным его размеру, но распределение памяти можно динамически изменять во время работы. Алгоритм PFF (Page Fault Frequency - частота страничных прерываний) предоставляет один из способов управления размещением процессов в памяти. Он говорит, когда увеличивать или уменьшать количество страниц, предоставленных процессу, но не упоминает о том, какую страницу замещать по прерыванию. Этот алгоритм только контролирует размер набора страниц, назначенных процессу.

Для большого класса схем замещения страниц, включая алгоритм LRU, известно, что частота прерываний уменьшается при увеличении числа предоставленных страниц, как мы обсуждали выше. Эта посылка лежит в основе алгоритма PFF. Данное свойство иллюстрирует рис. 4.17.

Количество предоставленных страничных блоков

Рис. 4.17. Частота страничных прерываний как функция от количества предоставленных процессу страничных блоков

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

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

4.5.3. Размер страницы

Зачастую размер страницы является параметром, выбираемым операционной системой. Даже если аппаратное обеспечение предусматривает, например, размер страницы 512 байт, операционная система может просто рассматривать страницы Ои 1,2иЗ, 4и5ит. д. как страницы размером 1 Кбайт, всегда предоставляя для них два последовательных страничных блока.