Добавлен: 29.10.2018
Просмотров: 48080
Скачиваний: 190
256
Глава 3. Управление памятью
с диском может быть установлен лимит, позволяющий сбрасывать на диск максимум
n страниц. По достижении этого лимита новые записи на диск планироваться уже не
должны.
А что делать, если стрелка пройдет полный круг и вернется в начальную позицию?
Тогда следует рассмотреть два варианта.
1. Была запланирована хотя бы одна запись на диск.
2. Не было запланировано ни одной записи на диск.
В первом случае стрелка просто продолжит движение, выискивая неизмененную
страницу. Поскольку была запланирована одна или более записей на диск, со вре-
менем одна из записей завершится, и задействованная в ней страница будет помечена
неизмененной. Первая же неизмененная страница и будет удалена. Эта страница не
обязательно должна быть первой запланированной, поскольку драйвер диска может
изменить порядок записи, чтобы оптимизировать производительность его работы.
Во втором случае все страницы относятся к рабочему набору, иначе должна была быть
запланирована хотя бы одна запись. При недостатке дополнительной информации
простейшее, что можно сделать, — истребовать любую неизмененную страницу и вос-
пользоваться ею. Расположение неизмененной страницы может быть отслежено в про-
цессе оборота стрелки. Если неизмененных страниц не имеется, то в качестве жертвы
выбирается текущая страница, которая и сбрасывается на диск.
3.4.10. Краткая сравнительная характеристика алгоритмов
замещения страниц
Только что мы рассмотрели несколько различных алгоритмов замещения страниц.
В этом разделе дадим им краткую сравнительную характеристику. Список рассмотрен-
ных алгоритмов представлен в табл. 3.2.
Таблица 3.2. Список рассмотренных алгоритмов замещения страниц
Алгоритм
Особенности
Оптимальный
Не может быть реализован, но полезен в каче-
стве оценочного критерия
NRU (Not Recently Used) — алгоритм исключе-
ния недавно использовавшейся страницы
Является довольно грубым приближением
к алгоритму LRU
FIFO (First In, First Out) — алгоритм «первой
пришла, первой и ушла»
Может выгрузить важные страницы
Алгоритм «второй шанс»
Является существенным усовершенствовани-
ем алгоритма FIFO
Алгоритм «часы»
Вполне реализуемый алгоритм
LRU (Least Recently Used) — алгоритм заме-
щения наименее востребованной страницы
Очень хороший, но труднореализуемый во всех
тонкостях алгоритм
NFU (Not Frequently Used) — алгоритм неча-
стого востребования
Является довольно грубым приближением
к алгоритму LRU
Алгоритм старения
Вполне эффективный алгоритм, являющийся
неплохим приближением к алгоритму LRU
Алгоритм рабочего набора
Весьма затратный для реализации алгоритм
WSClock
Вполне эффективный алгоритм
3.5. Разработка систем страничной организации памяти
257
Оптимальный алгоритм удаляет страницу с самым отдаленным предстоящим обра-
щением. К сожалению, у нас нет способа определения, какая это будет страница, по-
этому на практике этот алгоритм использоваться не может. Но он полезен в качестве
оценочного критерия при рассмотрении других алгоритмов.
Алгоритм исключения недавно использованной страницы (NRU) делит страницы на
четыре класса в зависимости от состояния битов R и M. Затем выбирает произвольную
страницу из класса с самым низким номером. Этот алгоритм нетрудно реализовать, но
он слишком примитивен. Есть более подходящие алгоритмы.
Алгоритм FIFO предполагает отслеживание порядка, в котором страницы были за-
гружены в память, путем сохранения сведений об этих страницах в связанном списке.
Это упрощает удаление самой старой страницы, но она-то как раз и может все еще
использоваться, поэтому FIFO — неподходящий выбор.
Алгоритм «второй шанс» является модификацией алгоритма FIFO и перед удалением
страницы проверяет, не используется ли она в данный момент. Если страница все еще
используется, она остается в памяти. Эта модификация существенно повышает произ-
водительность. Алгоритм «часы» является простой разновидностью алгоритма «вто-
рой шанс». Он имеет такой же показатель производительности, но требует несколько
меньшего времени на свое выполнение.
Алгоритм LRU превосходен во всех отношениях, но не может быть реализован без
специального оборудования. Если такое оборудование недоступно, то он не может быть
использован. Алгоритм NFU является грубой попыткой приблизиться к алгоритму
LRU. Его нельзя признать удачным. А вот алгоритм старения — куда более удачное
приближение к алгоритму LRU, которое к тому же может быть эффективно реализо-
вано и считается хорошим выбором.
В двух последних алгоритмах используется рабочий набор. Алгоритм рабочего на-
бора обеспечивает приемлемую производительность, но его реализация обходится
слишком дорого. Алгоритм WSClock является вариантом, который не только обе-
спечивает неплохую производительность, но и может быть эффективно реализован.
В итоге наиболее приемлемыми алгоритмами являются алгоритм старения и алгоритм
WSClock. Они основаны на LRU и рабочем наборе соответственно. Оба обеспечивают
неплохую производительность страничной организации памяти и могут быть эффек-
тивно реализованы. Существует также ряд других хороших алгоритмов, но эти два,
наверное, имеют наибольшее практическое значение.
3.5. Разработка систем страничной
организации памяти
В предыдущих разделах мы объяснили, как работает страничная организация памяти,
и дали описание нескольких основных алгоритмов замещения страниц. Но знания
одних лишь базовых механизмов еще недостаточно. Для разработки работоспособной
системы необходимо расширить свой кругозор. Это похоже на разницу между зна-
нием порядка передвижения ладьи, коня, слона и других шахматных фигур и навы-
ком хорошей игры. В следующих разделах мы рассмотрим другие вопросы, которым
разработчики операционных систем должны уделять пристальное внимание, чтобы
добиться хорошей производительности от системы страничной организации памяти.
258
Глава 3. Управление памятью
3.5.1. Сравнительный анализ локальной
и глобальной политики
В предыдущих разделах мы рассмотрели несколько алгоритмов выбора удаляемой
страницы в случае возникновения ошибки отсутствия страницы.
Главный вопрос, связанный с этим выбором (который мы до сих пор тщательно об-
ходили стороной): как должна быть распределена память между конкурирующими
работоспособными процессами?
Посмотрите на рис. 3.20, а. На нем изображены три процесса: A, B и C, составляющие
набор работоспособных процессов. Предположим, что процесс A сталкивается с ошиб-
кой отсутствия страницы. Должен ли алгоритм замещения страниц попытаться найти
наиболее давно использованную страницу, рассматривая лишь шесть страниц, выде-
ленных на данный момент процессу A, или же он должен рассматривать все страницы,
имеющиеся в памяти? Если он осуществляет поиск только среди страниц, принад-
лежащих процессу A, то страницей с наименьшим значением возраста будет A5, и мы
получим ситуацию, показанную на рис. 3.20, б.
Рис. 3.20. Сравнение локального и глобального алгоритмов замещения страниц:
а — исходная конфигурация; б — работа локального алгоритма замещения страниц;
в — работа глобального алгоритма замещения страниц
В то же время, если страница с наименьшим значением возраста удаляется независимо
от того, какому процессу она принадлежит, то будет выбрана страница B3, и мы полу-
чим ситуацию, показанную на рис. 3.20, в. Алгоритм, чья работа показана на рис. 3.20, б,
называется локальным алгоритмом замещения страниц, а алгоритм, чья работа показа-
на на рис. 3.20, в, называется глобальным алгоритмом замещения страниц. Локальный
алгоритм хорошо подходит для выделения каждому процессу фиксированной доли
памяти. При использовании глобальных алгоритмов страничные блоки распределяют-
ся среди работоспособных процессов в динамическом режиме. Поэтому со временем
изменяется количество страничных блоков, выделенных каждому процессу.
3.5. Разработка систем страничной организации памяти
259
В целом глобальные алгоритмы работают лучше, особенно когда размер рабочего на-
бора может изменяться в течение жизненного цикла процесса. Если используется ло-
кальный алгоритм, а рабочий набор разрастается, то это приводит к пробуксовке даже
при избытке свободных страничных блоков. Если рабочий набор сужается, локальные
алгоритмы приводят к нерациональному использованию памяти. Если используется
глобальный алгоритм, система должна постоянно принимать решение о том, сколько
страничных блоков выделить каждому процессу. Одним из способов может стать от-
слеживание размера рабочего набора на основе показаний битов возраста, но не факт,
что этот подход предотвратит пробуксовку. Рабочий набор может изменять свой размер
за миллисекунды, в то время как весьма приблизительные показатели на основе битов
возраста складываются за несколько тактов системных часов.
Другой подход заключается в использовании алгоритма выделения процессам странич-
ных блоков. Один из способов заключается в периодическом определении количества
работающих процессов и выделении каждому процессу равной доли. Таким образом,
при наличии 12 416 доступных (то есть не принадлежащих операционной системе)
страничных блоков и 10 процессов каждый процесс получает 1241 страничный блок.
Оставшиеся шесть блоков переходят в резерв для использования в случае возникно-
вения ошибки отсутствия страницы.
Хотя этот метод может показаться справедливым, едва ли есть смысл предоставлять
одинаковые доли памяти процессу в 10 Кбайт и процессу в 300 Кбайт. Вместо этого
страницы должны быть распределены пропорционально общему размеру каждого про-
цесса, чтобы процессу в 300 Кбайт было выделено в 30 раз больше блоков, чем процессу
в 10 Кбайт. Наверное, разумно будет дать каждому процессу какое-то минимальное
количество, чтобы он мог запуститься независимо от того, насколько малым он будет.
К примеру, на некоторых машинах одиночная двухоперандная команда может нуждаться
не менее чем в шести страницах, потому что на границах страниц может оказаться все:
сама команда, операнд-источник и операнд-приемник. При выделении всего лишь пяти
страниц программа, содержащая подобные команды, вообще не сможет выполняться.
При использовании глобального алгоритма может появиться возможность запускать
каждый процесс с некоторым количеством страниц пропорционально размеру про-
цесса, но как только процессы будут запущены, распределение должно динамически
обновляться. Одним из способов управления распределением является использование
алгоритма частоты возникновения ошибки отсутствия страницы (Page Fault Frequency
(PFF)). Он подсказывает, когда нужно увеличивать или уменьшать количество выде-
ленных процессу страниц, но ничего не говорит о том, какую страницу следует удалить
в случае возникновения ошибки. Он всего лишь контролирует размер выделенного
набора.
Ранее уже говорилось, что для большого класса алгоритмов замещения страниц, вклю-
чая LRU, известно, что чем больше выделено страниц, тем меньше уровень ошибок.
Данное предположение положено в основу алгоритма PFF. Это свойство проиллю-
стрировано на рис. 3.21.
Измерение уровня ошибок отсутствия страниц осуществляется простым подсчетом
количества ошибок в секунду, можно также взять скользящее среднее за несколько про-
шедших секунд. Одним из простых методов осуществления подобного измерения яв-
ляется прибавление количества ошибок отсутствия страниц в течение только что про-
шедшей секунды к текущему значению скользящего среднего и деление результата на
два. Пунктирная линия, обозначенная буквой A, соответствует неприемлемо высокому
260
Глава 3. Управление памятью
Рис. 3.21. Уровень ошибок как функция от количества выделенных
страничных блоков
уровню ошибок отсутствия страницы, поэтому, чтобы снизить этот уровень, процесс,
в котором происходят ошибки, получает больше страничных блоков. Пунктирная
линия, обозначенная буквой B, соответствует слишком низкому уровню ошибок отсут-
ствия страницы, который позволяет предположить, что процессу выделено чрезмерно
много памяти. В этом случае страничные блоки у него могут быть отобраны. Таким
образом алгоритм PFF пытается сохранить для каждого процесса уровень подкачки
страниц в пределах приемлемых границ.
Важно отметить, что некоторые алгоритмы замещения страниц могут работать как
с локальной, так и с глобальной политикой замещения. Например, FIFO может заме-
нять самые старые страницы во всем пространстве памяти (глобальный алгоритм) или
самые старые страницы, принадлежащие текущему процессу (локальный алгоритм).
Точно так же алгоритм LRU или приближения к его реализации могут заменять наи-
более давно использованную страницу во всей памяти (глобальный алгоритм) или
наиболее давно использованную страницу, принадлежащую текущему процессу (ло-
кальный алгоритм). В некоторых случаях выбор локальной, а не глобальной стратегии
не зависит от алгоритма.
В то же время для других алгоритмов замещения страниц имеет смысл только ло-
кальная стратегия. В частности, алгоритмы рабочего набора и WSClock обращаются
к некоторым конкретным процессам и должны применяться в этом контексте. По сути,
не существует рабочего набора для всей машины, и при попытке воспользоваться объ-
единением всех рабочих наборов алгоритм утратит свойство локальности и не сможет
работать эффективно.
3.5.2. Управление загрузкой
Даже при самом лучшем алгоритме замещения страниц и оптимальной системе рас-
пределения страничных блоков между процессами система может пробуксовывать.
Фактически когда сумма рабочих наборов всех процессов превышает объем памяти,
можно ожидать пробуксовки. Одним из симптомов такой ситуации является показание
алгоритма PFF, свидетельствующее о том, что некоторые процессы нуждаются в до-
полнительной памяти, но ни одному из процессов не нужен ее меньший объем. В таком
случае нуждающимся процессам невозможно предоставить дополнительную память,
не «ущемляя» другие процессы. Единственным реальным решением станет избавление
от некоторых процессов.