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

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

Оптимальный алгоритм

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

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

С этим алгоритмом связана только одна проблема: он невыполним.

Алгоритм NRU — не использовавшаяся в последнее время страница

Бит R (Referenced — обращения) устанавливается всякий раз, когда происходит обращение к странице (чтение или запись). Бит М (Modified — изменение) устанавливается, когда страница записывается (то есть изменяется). Биты содержатся в каждом элементе таблицы страниц,. Важно реализовать обновление этих битов при каждом обращении к памяти, по­этому необходимо, чтобы они задавались аппаратно. Если однажды бит был уста­новлен в 1, то он остается равным 1 до тех пор, пока операционная система про­граммно не вернет его в состояние 0.

Биты R и М могут использоваться для построения простого алгоритма замещения страниц, описанного ниже. Когда процесс запускается, оба страничных бита для всех его страниц операционной системой установлены на 0. Периодически (например, при каждом прерывании по таймеру) бит R очищается, чтобы отличить страницы, к которым давно не происходило обращения от тех, на которые были ссылки.

Когда возникает страничное прерывание, операционная система проверяет все страницы и делит их на четыре категории на основании текущих значений битов RuM:

Класс 0: не было обращений и изменений.

Класс 1: не было обращений, страница изменена.

Класс 2: было обращение, страница не изменена.

Класс 3: произошло и обращение, и изменение.

Алгоритм NRU (Not Recently Used — не использовавшийся в последнее время) удаляет страницу с помощью случайного поиска в непустом классе с наименьшим номером. В этом алгоритме подразумевается, что лучше выгрузить измененную страницу, к которой не было обращений по крайней мере в течение одного тика системных часов (обычно 20 мс), чем стереть часто используемую страницу. При­влекательность алгоритма NRU заключается в том, что он легок для понимания, умеренно сложен в реализации и дает производительность, которая, конечно, не оптимальна, но может вполне оказаться достаточной.

Алгоритм FIFO — первым прибыл — первым обслужен

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

Алгоритм «вторая попытка»

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

Алгоритм «вторая попытка» ищет в списке самую старую страницу, к кото­рой не было обращений в предыдущем временном интервале. Если же происхо­дили ссылки на все страницы, то «вторая попытка» превращается в обычный алгоритм FIFO.

Алгоритм «часы»

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

Когда происходит страничное прерывание, проверяется та страница, на кото­рую направлена стрелка. Если ее бит R равен 0, страница выгружается, на ее место в часовой круг встает новая страница, а стрелка сдвигается вперед на одну пози­цию. Если бит R равен 1, то он сбрасывается, стрелка перемещается к следующей странице. Этот процесс повторяется до тех пор, пока не находится та страница, у которой бит R = 0.

Алгоритм LRU — страница, не использовавшаяся дольше всего

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

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

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

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

Программное моделирование алгоритма NFU

Одна из разновидностей схемы LRU называется алгоритмом NFU (Not Frequently Used — редко использовавшаяся страница). Для него необходим программный счетчик, связанный с каждой страницей в памяти, изначально равный нулю. Во время каждого прерывания по таймеру операционная система исследует все страницы памяти. Бит R каждой страницы (он равен 0 или 1) прибавляется к счетчику. В сущности, счетчики пытаются отследить, как часто происходило обра­щение к каждой странице. При страничном прерывании для замещения выбира­ется страница с наименьшим значением счетчика.

Когда происходит страничное прерывание, удаляется та страница, чей счетчик имеет наименьшую величину.

«Старениe» заключается в том, что счетчик имеет конечное число разрядов, например 8. При прерывании от таймера значение сдвигается вправо на 1 бит, а бит оставляем слева. Предположим, что каждая из двух страниц имеет значение счетчика, равное 0. В данной ситуа­ции мы только случайным образом можем выбрать одну из них. На самом деле может оказаться, что к одной странице в последний раз обращались 9 тиков назад, а к другой — 1000. И мы не имеем возможности увидеть это. На практике, однако, обычно достаточно 8 битов при тике системных часов около 20 мс. Если к страни­це не обращались в течение 160 мс, очень вероятно, что она не важна.

Алгоритм «рабочий набор»

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

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

многие системы со страничной организацией пытаются отслеживать рабочий набор каждого процесса и обеспечивают его нахождение в памяти до запуска процесса. Такой подход носит название модели рабочего набора [91]. Он разработан для того, чтобы значительно снизить процент страничных преры­ваний. Загрузка страниц перед тем, как разрешить процессу работать, также назы­вается опережающей подкачкой страниц (prepaging). рабочий на­бор изменяется с течением времени.

В любой момент времени t существует множество стра­ниц, использовавшихся за к последних обращений к памяти. Это множество w(k, t) и есть рабочий набор. Так как все недавние обращения к памяти для к > 1 обяза­тельно должны были обращаться ко всем страницам, использовавшимся для к = 1 обращения к памяти, то есть к последней и, возможно, еще к некоторым страни­цам, w(k, t) является монотонно неубывающей функцией от к. Функция w(k, t) ограничена для больших к, потому что программа не может обращаться к боль­шему количеству страниц, чем содержится в ее адресном пространстве, кроме того, редкие программы обращаются ко всем страницам адресного пространства.

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

Для осуществ­ления алгоритма «рабочий набор» заранее нужно назначить значение к.

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

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

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

Алгоритм WSCIock

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

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

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

Моделирование алгоритмов замещения страниц

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

Участие операционной системы в процессе подкачки страниц

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

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

Когда процесс планируется для исполнения, для нового процесса требуется сброс диспетчера памяти (MMU), а содержимое буфера быстрого преобразования адреса (TLB) должно быть очищено, чтобы избавиться от следов предыдущего процесса. Таблицу страниц нового процесса нужно сделать текущей. Часть страниц процесса или они все могут быть считаны в память, чтобы уменьшить изначальное количество страничных прерываний.

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

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