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

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

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

Одним из таких решений является инвертированная таблица страниц. В этой модели таблица содержит по одной записи на страничный блок в реальной памя­ти, а не на страницу в виртуальном адресном пространстве. Например, при 64-раз­рядных виртуальных адресах, размере страниц 4 Кбайт и 256 Мбайт оперативной памяти инвертированная таблица страниц потребует всего лишь 65 536 записей. Каждая запись отслеживает, что (процесс, виртуальная страница) расположено в данном страничном блоке.

Хотя инвертированные таблицы страниц экономят значительное количество места, по крайней мере, когда виртуальное адресное пространство намного боль­ше, чем физическая память, они имеют серьезный недостаток: перевод виртуаль­ного адреса в физический становится намного сложнее. Когда процесс n обраща­ется к виртуальной странице p, аппаратное обеспечение не может больше найти физическую страницу, используя номер p в качестве индекса в таблице страниц. Вместо этого оно должно производить поиск записи (n, р) во всей инвертирован­ной таблице страниц. Более того, этот поиск должен выполняться при каждом обращении к памяти, а не только при страничном прерывании. Операция поиска в таблице размером 64 К при каждой ссылке к памяти вовсе не увеличит скорость вашей машины.

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

Инвертированные таблицы страниц в настоящее время используются на неко­торых рабочих станциях компаний IBM и Hewlett-Packard и будут встречаться все чаще, так как 64-разрядные машины получают все более широкое распростра­нение.

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

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

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

Следует отметить, что проблема «страничного обмена» также встает и в других областях конструирования компьютеров. Например, у большинства компьютеров есть один или несколько кэшей, состоящих из используемых в последнее время 32-байтовых или 64-байтовых блоков памяти. Когда кэш заполнен, необходимо выбрать некоторые блоки для удаления. Эта проблема практически аналогична замещению страниц лишь с одной разницей, заключающейся в меньшем масштабе времени (операция должна быть выполнена за несколько наносекунд, а не милли­секунд, как для замены страниц). Причиной для более короткого промежутка вре­мени является то, что неудачный поиск блока в кэше обрабатывается из основной памяти, в которой не тратится время на поиск нужного цилиндра диска и нет за­держки из-за его вращения.

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

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

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

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

С этим алгоритмом связана только одна проблема: он невыполним. В момент страничного прерывания операционная система не имеет возможности узнать, когда произойдет следующее обращение к каждой странице. (Мы рассматривали аналогичную ситуацию раньше, когда обсуждали алгоритм планирования «кратчай­шая задача — первая»: как система может сказать, какая из задач самая короткая?) Тем не менее, выполняя программу на модели и следя за всеми обращениями к стра­ницам, оптимальную замену можно осуществить при втором запуске, используя информацию о ссылках на страницы, собранную во время первого запуска.

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

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

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

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

Если аппаратное обеспечение не поддерживает эти биты, их можно смодели­ровать следующим образом. Когда процесс запускается, все его записи в таблице страниц помечаются как отсутствующие в памяти. Как только происходит обра­щение к странице, происходит страничное прерывание. Затем операционная сис­тема устанавливает бит R (в своих внутренних таблицах); изменяет запись в таб­лице страниц, чтобы она указывала на корректную страницу с режимом READ ONLY (только для чтения), и перезапускает команду. Если страница позднее за­писывается, происходит другое страничное прерывание, позволяющее операцион­ной системе установить бит М и изменить состояние страницы на READ/WRITE (чтение/запись).

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

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

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

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

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

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

Другим требующим небольших издержек алгоритмом является FIFO (First-In, First-Out — «первым прибыл — первым обслужен»). Чтобы проиллюстрировать его работу, рассмотрим универсам, на полках которого можно выставить ровно k различных продуктов. Он предлагает новую удобную пищу: растворимый, глубо­ко замороженный, экологически чистый йогурт, который можно мгновенно при­готовить в микроволновой печи. Покупатели тут же обратили внимание на этот продукт, поэтому наш ограниченный в размерах супермаркет, для того чтобы про­давать йогурт, должен избавиться от одного из старых товаров.

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

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

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

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

Работа этого алгоритма, называемого «второй попыткой» (second chance), показана на рис. 4.15, а. Здесь изображены страницы от А до Н, хранящиеся в свя­занном списке и отсортированные по времени их поступления в память. Числа над страницами обозначают их время загрузки в память.

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

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

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