Глава 4 (1085728), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

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

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

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

Вместо нее используются различные аппроксимации. Применяемый в большин­стве случаев подход заключается в том, чтобы оставить идею подсчета k последних обращений к памяти и вместо этого использовать время выполнения программы. Например, вместо определения рабочего набора как множества страниц, на кото­рые ссылались при предыдущих 10 млн обращений к памяти, мы можем опреде­лить его как множество страниц, использовавшихся в течение последних 100 мс времени выполнения. На практике это определение имеет тот же смысл, но намно­го упрощает реализацию алгоритма. Заметим, что для" каждого процесса считается только его собственное время работы. Таким образом, если процесс стартовал во время T и занял процессор на 40 мс за реальное время Т + 100 мс, для определения рабочего набора его время равно 40 мс. Время работы процессора, которое фак­тически использовал процесс с момента запуска, часто называется текущим виртуальным временем. При таком приближении рабочий набор процесса — это множество страниц, к которому он обращался за последние t секунд виртуального времени.

Теперь рассмотрим алгоритм замещения страниц, основанный на рабочем на­боре. Его базовая идея заключается в том, чтобы найти страницу, не включенную в рабочий набор, и выгрузить ее. На рис. 4.20 изображена часть таблицы страниц для некоторой машины. Поскольку в качестве кандидатов на удаление рассматри­ваются только те страницы, которые в настоящее время находятся в памяти, от­сутствующие в памяти страницы этим алгоритмом игнорируются. Каждая запись содержит (по крайней мере) два элемента информации: приближенное время, в которое страница использовалась в последний раз, и бит R (обращения). Пустые белые прямоугольники символизируют другие поля, ненужные для данного алго­ритма, такие как номер страничного блока, биты защиты и бит М (изменения).

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

В процессе обработки каждой записи проверяется бит R. Если он равен 1, теку­щее виртуальное время записывается в поле Время последнего использования (Time of last use) в таблице страниц, указывая, что страница использовалась в тот момент, когда произошло прерывание. Так как к странице было обращение в течение дан­ного такта, ясно, что она находится в рабочем наборе и не является кандидатом на удаление (предполагается, что т охватывает несколько тиков часов).

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

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

Алгоритм WSClock

Исходный алгоритм «рабочий набор» громоздок, так как при каждом страничном прерывании следует проверять таблицу страниц до тех пор, пока не определится местоположение подходящего кандидата. Усовершенствованный алгоритм, осно­ванный на часовом алгоритме, но также использующий информацию рабочего на­бора, называется WSClock [54]. Благодаря простоте реализации и хорошей про­изводительности этот алгоритм широко используется на практике.

Д
ля него необходима структура данных в виде кольцевого списка страничных блоков, как в алгоритме «часы», что изображено на рис. 4.21, а. В исходном поло­жении этот список пустой. Когда загружается первая страница, она добавляется в список. По мере прихода страниц они поступают в список, формируя кольцо. Каждая запись, кроме бита R (показан) и бита М (не показан), содержит поле <<вре­мя последнего использования>> из базового алгоритма «рабочий набор».

Как и в случае алгоритма <<часы>>, при каждом страничном прерывании первой проверяется та страница, на которую указывает стрелка. Если бит R равен 1, это значит, что страница использовалась в течение последнего такта часов, поэтому она не является идеальным кандидатом на удаление. Тогда бит R устанавливается на 0, стрелка передвигается на следующую страницу и для нее повторяется алго­ритм. Состояние после такой последовательности действий продемонстрировано на рис. 4.21, б.

Теперь рассмотрим, что происходит, если страница, на которую указывает стрелка, имеет бит R = 0, как показано на рис. 4.21, в. Если возраст страницы боль­ше величины т и страница — чистая, то она не входит в рабочий набор и на диске есть ее действительная копия. Тогда в данный страничный блок просто загружается новая страница, как изображено на рис. 4.21, г. Если, напротив, страница «грязная», ее нельзя немедленно стереть, так как на диске нет ее последней копии. Чтобы из­бежать переключения процессов, запись на диск включается в график планирова­ния, но стрелка сдвигается на позицию, и алгоритм продолжает работу со следую­щей страницей. Несмотря на то что «грязная» страница может быть старше, чистая находится ближе в ряду страниц, которые можно использовать немедленно.

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

Что происходит, если стрелка обходит целый круг и возвращается к начальной точке? Существует два варианта:

1. Запланирована, по крайней мере, одна операция записи на диск.

2. Ни одной операции записи не запланировано.

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

Во втором случае все страницы находятся в рабочем наборе, иначе планирова­лась бы, по крайней мере, одна операция записи. За недостатком дополнительной информации проще всего предъявить права на любую чистую страницу и использо­вать ее. Расположение чистой страницы могло бы отслеживаться во время «чист­ки». Если в памяти нет чистых страниц, тогда выбирается текущая страница и пере­писывается на диск.

Алгоритмы замещения страниц, резюме

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

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

Алгоритм NRU (не использовавшаяся в последнее время страница) делит стра­ницы на четыре класса в зависимости от состояния битов R и М. Выбирается любая страница из класса с наименьшим номером. Этот алгоритм легко реализуется, но он является очень грубым. Существуют лучшие схемы.

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

Алгоритм «вторая попытка» — это модификация алгоритма FIFO, он перед уда­лением страницы из памяти проверяет, используется ли она в данный момент. Если да, то страница пропускается. Такое изменение сильно повышает произво­дительность. Алгоритм «часы» представляет собой всего лишь другое осуществ­ление алгоритма «второй попытки». Он имеет те же самые характеристики произ­водительности, но требует немного меньше времени на выполнение алгоритма.

Алгоритм LRU (страница, не использовавшаяся дольше всего) — это отличный алгоритм, но его нельзя осуществить без специального аппаратного обеспечения. Если подобное оборудование недоступно, алгоритм невозможно использовать. Алгоритм NFU (редко использовавшаяся страница) представляет собой грубую попытку аппроксимации алгоритма LRU. Он не очень хорош. Но существует ал­горитм «старения», который намного лучше аппроксимирует алгоритм LRU и мо­жет быть эффективно реализован. Это замечательный выбор.

Характеристики

Список файлов книги