Добавлен: 29.10.2018
Просмотров: 48074
Скачиваний: 190
3.3. Виртуальная память
241
блице верхнего уровня и извлекает запись 1, которая соответствует адресам от 4 Мбайт
до 8 Мбайт – 1. Затем он использует PT2 для обращения по индексу к таблице страниц
второго уровня, чтобы найти и извлечь запись 3, которая соответствует адресам от
12 288 до 16 383 внутри своего фрагмента размером 4 Мбайт (то есть соответствует
абсолютным адресам от 4 206 592 до 4 210 687). Эта запись содержит номер странич-
ного блока той страницы, которая содержит виртуальный адрес 0x00403004. Если эта
страница не присутствует в памяти, то бит присутствия-отсутствия в записи таблицы
страниц будет иметь нулевое значение, что вызовет ошибку отсутствия страницы.
Если страница присутствует в памяти, то номер страничного блока, взятый из таблицы
страниц второго уровня, объединяется со смещением (4) для построения физического
адреса. Этот адрес выставляется на шину и отправляется к блоку памяти.
В отношении изображения на рис. 3.12 следует отметить одну интересную деталь. Хотя
адресное пространство содержит более миллиона страниц, фактически востребованы
только четыре таблицы: таблица верхнего уровня и таблицы второго уровня для памяти
от 0 до 4 Мбайт – 1 (для текста программы), от 4 Мбайт до 8 Мбайт – 1 (для данных)
и для верхних 4 Мбайт (выделенных под стек). Биты присутствия-отсутствия в осталь-
ных 1021 записи таблицы страниц верхнего уровня установлены в нуль, что при любом
обращении к ним вызовет ошибку отсутствия страницы. При возникновении этой
ошибки операционная система поймет, что процесс пытается обратиться к той памяти,
обращение к которой не предполагалось, и предпримет соответствующие меры, напри-
мер пошлет ему сигнал или уничтожит этот процесс. В данном примере мы выбрали
для различных размеров округленные значения и размер поля PT1, равный размеру
поля PT2, но в реальных системах, конечно, возможны и другие значения.
Система, показанная на рис. 3.12, в которой используется двухуровневая таблица стра-
ниц, может быть расширена до трех, четырех и более уровней. Дополнительные уровни
придают ей бˆольшую гибкость. Например, 32-разрядный процессор Intel 80386 (выпу-
щенный в 1985 году) способен был адресовать до 4 Гбайт памяти, используя двухуров-
невую таблицу страниц, которая состоит из каталога страниц, чьи записи указывают
на таблицы страниц, которые, в свою очередь, указывают на фактические страничные
блоки размером 4 Кбайт. Как в каталоге, так и в таблицах страниц содержится по 1024
записи, что в целом, как и требуется, дает 2
10
· 2
10
· 2
12
= 2
32
адресуемых байтов.
Спустя 10 лет с выпуском процессора Pentium Pro был введен еще один уровень: таб-
лица указателей на каталоги страниц. Кроме всего прочего, каждая запись в каждом
уровне иерархии таблиц страниц была расширена с 32 до 64 разрядов, что позволяло
адресовать память за пределами 4-гигабайтной границы. Поскольку имелось всего
4 запи си в таблице указателей на каталоги страниц, 512 записей в каждом каталоге
страниц и 512 записей в каждой таблице страниц, общий объем возможной адресуе-
мой памяти был по-прежнему ограничен максимальным значением 4 Гбайт. Когда же
к семейству x86 была добавлена должная 64-разрядная поддержка (изначально это
было сделано компанией AMD), дополнительный уровень можно было бы назвать
указателем таблицы указателей на каталоги страниц. Это вполне вписалось бы в манеру
присваивания названий производителями микросхем. К счастью, этого не произошло.
И ими был выбран альтернативный вариант «страничное отображение уровня 4» (page
map level 4) — конечно, имя не самое броское, зато короткое и более понятное. В любом
случае, теперь эти процессоры используют все 512 записей во всех таблицах, выдавая
объем адресуемой памяти 2
9
· 2
9
· 2
9
· 2
9
· 2
12
= 2
48
байтов. Они могли бы добавить и еще
один уровень, но, возможно, подумали, что 256 Тбайт пока будет достаточно.
242
Глава 3. Управление памятью
Инвертированные таблицы страниц
Альтернатива постоянно растущим уровням иерархии страничной адресации назы-
вается инвертированными таблицами страниц. Впервые они использовались такими
процессорами, как PowerPC, UltraSPARC и Itanium (которые иногда называли Itanic,
поскольку успех, на который в связи с их выходом надеялась компания Intel, так и не был
достигнут). В данной конструкции имеется одна запись для каждого страничного блока
в реальной памяти, а не одна запись на каждую страницу в виртуальном адресном про-
странстве. Например, при использовании 64-разрядных виртуальных адресов, страниц
размером 4 Кбайт и оперативной памяти размером 4 Гбайт инвертированные таблицы
требовали только 1 048 576 записей. В каждой записи отслеживается, что именно на-
ходится в страничном блоке (процесс, виртуальная страница).
Хотя инвертированные таблицы страниц экономят значительное количество простран-
ства, по крайней мере в том случае, когда виртуальное адресное пространство намного
объемнее физической памяти, у них есть один серьезный недостаток: преобразование
виртуальных адресов в физические становится намного сложнее. Когда процесс n
обращается к виртуальной странице p, аппаратура уже не может найти физическую
страницу, используя p в качестве индекса внутри таблицы страниц. Вместо этого она
должна провести поиск записи (n, p) по всей инвертированной таблице страниц. Более
того, этот поиск должен быть проведен при каждом обращении к памяти, а не только
при ошибках отсутствия страницы. Вряд ли можно признать просмотр таблицы разме-
ром 256 K записей при каждом обращении к памяти способом сделать ваш компьютер
самым быстродействующим.
Решение этой дилеммы состоит в использовании TLB. Если в этом буфере можно
будет хранить информацию обо всех интенсивно используемых страницах, преобра-
зование может происходить так же быстро, как и при использовании обычных таблиц
страниц. Но при отсутствии нужной записи в TLB программа должна просмотреть
инвертированную таблицу страниц. Одним из приемлемых способов осуществления
этого поиска является ведение хэш-таблицы, созданной на основе виртуальных адресов.
На рис. 3.13 показано, что все находящиеся на данный момент в памяти виртуальные
Рис. 3.13. Сопоставление традиционной таблицы страниц с инвертированной
3.4. Алгоритмы замещения страниц
243
страницы, имеющие одинаковые хэш-значения, связываются в одну цепочку. Если
у хэш-таблицы столько же строк, сколько физических страниц у машины, средняя
цепочка будет длиной всего лишь в одну запись, позволяя существенно ускорить ото-
бражение. Как только будет найден номер страничного блока, в TLB будет введена
новая пара значений (виртуального, физического).
Инвертированные таблицы страниц нашли широкое применение на 64-разрядных
машинах, поскольку даже при очень больших размерах страниц количество записей
в обычных таблицах страниц будет для них просто гигантским. К примеру, при размере
страниц 4 Мбайт и 64-разрядных виртуальных адресах понадобится 2
42
записей в та-
блице страниц. Другие подходы к работе с большими объемами виртуальной памяти
можно найти в работе Таллури (Talluri et al., 1995).
3.4. Алгоритмы замещения страниц
При возникновении ошибки отсутствия страницы операционная система должна
выбрать выселяемую (удаляемую из памяти) страницу, чтобы освободить место для
загружаемой страницы. Если предназначенная для удаления страница за время своего
нахождения в памяти претерпела изменения, она должна быть переписана на диске,
чтобы привести дисковую копию в актуальное состояние. Но если страница не изме-
нялась (например, она содержала текст программы), дисковая копия не утратила своей
актуальности и перезапись не требуется. Тогда считываемая страница просто пишется
поверх выселяемой.
Если бы при каждой ошибке отсутствия страницы можно было выбирать для выселе-
ния произвольную страницу, то производительность системы была бы намного выше,
если бы выбор падал на редко востребуемую страницу. При удалении интенсивно ис-
пользуемой страницы высока вероятность того, что она в скором времени будет загру-
жена опять, что приведет к лишним издержкам. На выработку алгоритмов замещения
страниц было потрачено множество усилий как в теоретической, так и в эксперимен-
тальной областях. Далее мы рассмотрим некоторые из наиболее важных алгоритмов.
Следует заметить, что проблема «замещения страниц» имеет место и в других обла-
стях проектирования компьютеров. К примеру, у большинства компьютеров имеется
более одного кэша памяти, содержащих последние использованные 32- или 64-байтные
блоки памяти. При заполнении кэша нужно выбрать удаляемые блоки. Это проблема
в точности повторяет проблему замещения страниц, за исключением более короткого
времени (все должно быть сделано за несколько наносекунд, а не миллисекунд, как при
замещении страниц). Причиной необходимости более короткого времени является то,
что ненайденные блоки кэша берутся из оперативной памяти без затрат времени на
поиск и без задержек на раскрутку диска.
В качестве второго примера можно взять веб-сервер. В кэше памяти сервера может со-
держаться некоторое количество часто востребуемых веб-страниц. Но при заполнении
кэша памяти и обращении к новой странице должно быть принято решение о том, какую
веб-страницу нужно выселить. Здесь используются те же принципы, что и при работе со
страницами виртуальной памяти, за исключением того, что веб-страницы, находящиеся
в кэше, никогда не подвергаются модификации, поэтому на диске всегда имеется их
свежая копия. А в системе, использующей виртуальную память, страницы, находящиеся
в оперативной памяти, могут быть как измененными, так и неизмененными.
244
Глава 3. Управление памятью
Во всех рассматриваемых далее алгоритмах замещения страниц ставится вполне
определенный вопрос: когда возникает необходимость удаления страницы из памяти,
должна ли эта страница быть одной из тех, что принадлежат процессу, в работе кото-
рого произошла ошибка отсутствия страницы, или это может быть страница, принад-
лежащая другому процессу? В первом случае мы четко ограничиваем каждый процесс
фиксированным количеством используемых страниц, а во втором таких ограничений
не накладываем. Возможны оба варианта, а к этому вопросу мы еще вернемся.
3.4.1. Оптимальный алгоритм замещения страниц
Наилучший алгоритм замещения страниц несложно описать, но совершенно невозмож-
но реализовать. В нем все происходит следующим образом. На момент возникновения
ошибки отсутствия страницы в памяти находится определенный набор страниц. К не-
которым из этих страниц будет осуществляться обращение буквально из следующих
команд (эти команды содержатся на странице). К другим страницам обращения может
не быть и через 10, 100 или, возможно, даже 1000 команд. Каждая страница может
быть помечена количеством команд, которые должны быть выполнены до первого
обращения к странице.
Оптимальный алгоритм замещения страниц гласит, что должна быть удалена стра-
ница, имеющая пометку с наибольшим значением. Если какая-то страница не будет
использоваться на протяжении 8 млн команд, а другая какая-нибудь страница не будет
использоваться на протяжении 6 млн команд, то удаление первой из них приведет
к ошибке отсутствия страницы, в результате которой она будет снова выбрана с диска
в самом отдаленном будущем. Компьютеры, как и люди, пытаются по возможности
максимально отсрочить неприятные события.
Единственной проблемой такого алгоритма является невозможность его реализации.
К тому времени, когда произойдет ошибка отсутствия страницы, у операционной си-
стемы не будет способа узнать, когда каждая из страниц будет востребована в следую-
щий раз. (Подобная ситуация наблюдалась и ранее, когда мы рассматривали алгоритм
планирования, выбирающий сначала самое короткое задание, — как система может
определить, какое из заданий самое короткое?) Тем не менее при прогоне программы
на симуляторе и отслеживании всех обращений к страницам появляется возможность
реализовать оптимальный алгоритм замещения страниц при втором прогоне, вос-
пользовавшись информацией об обращении к страницам, собранной во время первого
прогона.
Таким образом появляется возможность сравнить производительность осуществи-
мых алгоритмов с наилучшим из возможных. Если операционная система достигает
производительности, скажем, на 1 % хуже, чем у оптимального алгоритма, то усилия,
затраченные на поиски более совершенного алгоритма, дадут не более 1 % улучшения.
Чтобы избежать любой возможной путаницы, следует уяснить, что подобная регистра-
ция обращений к страницам относится только к одной программе, прошедшей оценку,
и только при одном вполне определенном наборе входных данных. Таким образом,
полученный в результате этого алгоритм замещения страниц относится только к этой
конкретной программе и к конкретным входным данным. Хотя этот метод и применя-
ется для оценки алгоритмов замещения страниц, в реальных системах он бесполезен.
Далее мы будем рассматривать те алгоритмы, которые действительно полезны для
реальных систем.
3.4. Алгоритмы замещения страниц
245
3.4.2. Алгоритм исключения недавно
использовавшейся страницы
Чтобы позволить операционной системе осуществить сбор полезной статистики вос-
требованности страниц, большинство компьютеров, использующих виртуальную
память, имеют два бита состояния, R и M, связанных с каждой страницей. Бит R
устанавливается при каждом обращении к странице (при чтении или записи). Бит M
устанавливается, когда в страницу ведется запись (то есть когда она модифицируется).
Эти биты, как показано на рис. 3.11, присутствуют в каждой записи таблицы страниц.
Важно усвоить, что эти биты должны обновляться при каждом обращении к памяти,
поэтому необходимо, чтобы их значения устанавливались аппаратной частью. После
установки бита в 1 он сохраняет это значение до тех пор, пока не будет сброшен опе-
рационной системой.
Если у аппаратуры нет таких битов, они должны быть созданы искусственно с помо-
щью механизмов операционной системы ошибки отсутствия страницы и прерывания
таймера. При запуске процесса все записи в его таблице страниц помечаются отсут-
ствующими в памяти. Как только произойдет обращение к странице, возникнет ошиб-
ка отсутствия страницы. Тогда операционная система устанавливает бит R (в своих
внутренних таблицах), изменяет запись в таблице страниц, чтобы она указывала на
правильную страницу, с режимом доступа только для чтения (READ ONLY), и пере-
запускает команду. Если впоследствии страница модифицируется, возникает другая
ошибка страницы, позволяющая операционной системе установить бит M и изменить
режим доступа к странице на чтение-запись (READ/WRITE).
Биты R и M могут использоваться для создания следующего простого алгоритма заме-
щения страниц. При запуске процесса оба страничных бита для всех его страниц уста-
навливаются операционной системой в 0. Время от времени (например, при каждом
прерывании по таймеру) бит R сбрасывается, чтобы отличить те страницы, к которым
в последнее время не было обращений, от тех, к которым такие обращения были.
При возникновении ошибки отсутствия страницы операционная система просматрива-
ет все страницы и на основе текущих значений принадлежащих им битов R и M делит
их на четыре категории:
1. Класс 0: в последнее время не было ни обращений, ни модификаций.
2. Класс 1: обращений в последнее время не было, но страница модифицирована.
3. Класс 2: в последнее время были обращения, но модификаций не было.
4. Класс 3: в последнее время были и обращения, и модификации.
Хотя на первый взгляд страниц класса 1 быть не может, но они появляются в том
случае, если у страниц класса 3 бит R сбрасывается по прерыванию от таймера. Эти
прерывания не сбрасывают бит M, поскольку содержащаяся в нем информация необ-
ходима для того, чтобы узнать, нужно переписывать страницу, хранящуюся на диске,
или нет. Сброс бита R без сброса бита M и приводит к возникновению страниц класса 1.
Алгоритм исключения недавно использовавшейся страницы (Not Recently Used
(NRU)) удаляет произвольную страницу, относящуюся к самому низкому непустому
классу. В этот алгоритм заложена идея, суть которой в том, что лучше удалить моди-
фицированную страницу, к которой не было обращений по крайней мере за последний
такт системных часов (обычно это время составляет около 20 мс), чем удалить интен-