Виртуальная память
Идея виртуальной памяти далеко не нова. Сейчас многие полагают, что в основе этой идеи лежит необходимость обеспечения (при поддержке операционной системы) видимости практически неограниченной (32- или 64-разрядной) адресуемой пользовательской памяти при наличии основной памяти существенно меньших размеров. Конечно, этот аспект очень важен. Но также важно понимать, что виртуальная память поддерживалась и на компьютерах с 16-разрядной адресацией, в которых объем основной памяти зачастую существенно превышал 64 Кбайта.
Вспомните хотя бы 16-разрядный компьютер PDP-11/70, к которому можно было подключить до 2 Мбайт основной памяти. Другим примером может служить выдающаяся отечественная ЭВМ БЭСМ-6, в которой при 15-разрядной адресации 6-байтовых (48-разрядных) машинных слов объем основной памяти был доведен до 256 Кбайт. Операционные системы этих компьютеров тем не менее поддерживали виртуальную память, основным смыслом которой являлось обеспечение защиты пользовательских программ одной от другой и предоставление операционной системе возможности динамически гибко перераспределять основную память между одновременно поддерживаемыми пользовательскими процессами.
Хотя известны и чисто программные реализации виртуальной памяти, это направление получило наиболее широкое развитие после получения соответствующей аппаратной поддержки. Идея аппаратной части механизма виртуальной памяти состоит в том, что адрес памяти, вырабатываемый командой, интерпретируется аппаратурой не как реальный адрес некоторого элемента основной памяти, а как некоторая структура, разные поля которой обрабатываются разным образом.
В наиболее простом и наиболее часто используемом случае страничной виртуальной памяти каждая виртуальная память (виртуальная память каждого процесса) и физическая основная память представляются состоящими из наборов блоков или страниц одинакового размера. Для удобства реализации размер страницы всегда выбирается равным числу, являющемуся степенью 2. Тогда, если общая длина виртуального адреса есть N (в последние годы это тоже всегда некоторая степень 2 - 16, 32, 64), а размер страницы есть 2M), то виртуальный адрес рассматривается как структура, состоящая из двух полей: первое поле занимает (N-M+1) разрядов адреса и задает номер страницы виртуальной памяти, второе поле занимает (M-1) разрядов и задает смещение внутри страницы до адресуемого элемента памяти (в большинстве случаев - байта). Аппаратная интерпретация виртуального адреса показана на рисунке 3.1.
Рисунок иллюстрирует механизм на концептуальном уровне, не вдаваясь в детали по поводу того, что из себя представляет и где хранится таблица страниц. Мы не будем рассматривать возможные варианты, а лишь заметим, что в большинстве современных компьютеров со страничной организацией виртуальной памяти все таблицы страниц хранятся в основной памяти, а быстрота доступа к элементам таблицы текущей виртуальной памяти достигается за счет наличия сверхбыстродействующей буферной памяти (кэша).
Для полноты изложения, но не вдаваясь в детали, заметим, что существуют две другие схемы организации виртуальной памяти: сегментная и сегментно-страничная. При сегментной организации виртуальный адрес по-прежнему состоит из двух полей - номера сегмента и смещения внутри сегмента. Отличие от страничной организации состоит в том, что сегменты виртуальной памяти могут быть разного размера. В элементе таблицы сегментов помимо физического адреса начала сегмента (если виртуальный сегмент содержится в основной памяти) содержится длина сегмента. Если размер смещения в виртуальном адресе выходит за пределы размера сегмента, возникает прерывание. Понятно, что компьютер с сегментной организацией виртуальной памяти можно использовать как компьютер со страничной организацией, если использовать сегменты одного размера.
Рис. 3.1. Схема страничной организации виртуальной памяти
При сегментно-страничной организации виртуальной памяти происходит двухуровневая трансляция виртуального адреса в физический. В этом случае виртуальный адрес состоит из трех полей: номера сегмента виртуальной памяти, номера страницы внутри сегмента и смещения внутри страницы. Соответственно, используются две таблицы отображения - таблица сегментов, связывающая номер сегмента с таблицей страниц, и отдельная таблица страниц для каждого сегмента (рисунок 3.2).
Рис. 3.2. Схема сегментно-страничной организации виртуальной памяти
Сегментно-страничная организация виртуальной памяти позволяла совместно использовать одни и те же сегменты данных и программного кода в виртуальной памяти разных задач (для каждой виртуальной памяти существовала отдельная таблица сегментов, но для совместно используемых сегментов поддерживались общие таблицы страниц).
В дальнейшем рассмотрении мы ограничимся проблемами управления страничной виртуальной памяти. С небольшими коррективами все обсуждаемые ниже методы и алгоритмы относятся и к сегментной, и сегментно-страничной организациям.
Как же достигается возможность наличия виртуальной памяти с размером, существенно превышающим размер оперативной памяти? В элементе таблицы страниц может быть установлен специальный флаг (означающий отсутствие страницы), наличие которого заставляет аппаратуру вместо нормального отображения виртуального адреса в физический прервать выполнение команды и передать управление соответствующему компоненту операционной системы. Английский термин "demand paging" (листание по требованию) достаточно точно характеризует функции, выполняемые этим компонентом. Когда программа обращается к виртуальной странице, отсутствующей в основной памяти, т.е. "требует" доступа к данным или программному коду, операционная система удовлетворяет это требование путем выделения страницы основной памяти, перемещения в нее копии страницы, находящейся во внешней памяти, и соответствующей модификации элемента таблицы страниц. После этого происходит "возврат из прерывания", и команда, по "требованию" которой выполнялись эти действия, продолжает свое выполнение.
Наиболее ответственным действием описанного процесса является выделение страницы основной памяти для удовлетворения требования доступа к отсутствующей в основной памяти виртуальной странице. Напомним, что мы рассматриваем ситуацию, когда размер каждой виртуальной памяти может существенно превосходить размер основной памяти. Это означает, что при выделении страницы основной памяти с большой вероятностью не удастся найти свободную (не приписанную к какой-либо виртуальной памяти) страницу. В этом случае операционная система должна в соответствии с заложенными в нее критериями (совокупность этих критериев принято называть "политикой замещения", а основанный на них алгоритм замещения - "алгоритмом подкачки") найти некоторую занятую страницу основной памяти, переместить в случае надобности ее содержимое во внешнюю память, должным образом модифицировать соответствующий элемент соответствующей таблицы страниц и после этого продолжить процесс удовлетворения доступа к странице.
Существует большое количество разнообразных алгоритмов подкачки. Объем этого курса не позволяет рассмотреть их подробно. Соответствующий материал можно найти в изданных на русском языке книгах по операционным системам Цикритзиса и Бернстайна, Дейтела и Краковяка. Однако, чтобы вернуться к описанию конкретных методов управления виртуальной памятью, применяемых в ОС UNIX, мы все же приведем некоторую краткую классификацию алгоритмов подкачки.
Во-первых, алгоритмы подкачки делятся на глобальные и локальные. При использовании глобальных алгоритмов операционная система при потребности замещения ищет страницу основной памяти среди всех страниц, независимо от их принадлежности к какой-либо виртуальной памяти. Локальные алгоритмы предполагают, что если возникает требование доступа к отсутствующей в основной памяти странице виртуальной памяти ВП1, то страница для замещения будет искаться только среди страниц основной памяти, приписанных к той же виртуальной памяти ВП1.
Наиболее распространенными традиционными алгоритмами (как в глобальном, так в локальном вариантах) являются алгоритмы FIFO (First In First Out) и LRU (Least Recently Used). При использовании алгоритма FIFO для замещения выбирается страница, которая дольше всего остается приписанной к виртуальной памяти. Алгоритм LRU предполагает, что замещать следует ту страницу, к которой дольше всего не происходили обращения. Хотя интуитивно кажется, что критерий алгоритма LRU является более правильным, известны ситуации, в которых алгоритм FIFO работает лучше (и, кроме того, он гораздо более дешево реализуется).
Заметим еще, что при использовании глобальных алгоритмов, вне зависимости от конкретного применяемого алгоритма, возможны и теоретически неизбежны критические ситуации, которые называются по-английски thrashing (несмотря на множество попыток, хорошего русского эквивалента так и не удалось придумать). Рассмотрим простой пример. Пусть на компьютере в мультипрограммном режиме выполняются два процесса - П1 в виртуальной памяти ВП1 и П2 в виртуальной памяти ВП2, причем суммарный размер ВП1 и ВП2 больше размеров основной памяти. Предположим, что в момент времени t1 в процессе П1 возникает требование виртуальной страницы ВС1. Операционная система обрабатывает соответствующее прерывание и выбирает для замещения страницу основной памяти С2, приписанную к виртуальной странице ВС2 виртуальной памяти ВП2 (т.е. в элементе таблицы страниц, соответствующем ВС2, проставляется флаг отсутствия страницы). Для полной обработки требования доступа к ВС1 в общем случае потребуется два обмена с внешней памятью (первый, чтобы записать текущее содержимое С2, второй - чтобы прочитать копию ВС1). Поскольку операционная система поддерживает мультипрограммный режим работы, то во время выполнения обменов доступ к процессору получит процесс П2, и он, вполне вероятно, может потребовать доступа к своей виртуальной странице ВС2 (которую у него только что отняли). Опять будет обрабатываться прерывание, и ОС может заменить некоторую страницу основной памяти С3, которая приписана к виртуальной странице ВС3 в ВП1. Когда закончатся обмены, связанные с обработкой требования доступа к ВС1, возобновится процесс П1, и он, вполне вероятно, потребует доступа к своей виртуальной странице ВС3 (которую у него только что отобрали). И так далее. Общий эффект состоит в том, что непрерывно работает операционная система, выполняя бесчисленные и бессмысленные обмены с внешней памятью, а пользовательские процессы П1 и П2 практически не продвигаются.
Понятно, что при использовании локальных алгоритмов ситуация thrashing, затрагивающая несколько процессов, невозможна. Однако в принципе возможна аналогичная ситуация внутри одной виртуальной памяти: ОС может каждый раз замещать ту страницу, к которой процесс обратится в следующий момент времени.
Единственным алгоритмом, теоретически гарантирующим отсутствие thrashing, является так называемый "оптимальный алгоритм Биледи" (по имени придумавшего его венгерского математика). Алгоритм заключается в том, что для замещения следует выбирать страницу, к которой в будущем наиболее долго не будет обращений. Понятно, что в динамической среде операционной системы точное знание будущего невозможно, и в этом контексте алгоритм Биледи представляет только теоретический интерес (хотя он с успехом применяется практически, например, в компиляторах для планирования использования регистров).
В 1968 году американский исследователь Питер Деннинг сформулировал принцип локальности ссылок (называемый принципом Деннинга) и выдвинул идею алгоритма подкачки, основанного на понятии рабочего набора. В некотором смысле предложенный им подход является практически реализуемой аппроксимацией оптимального алгоритма Биледи. Принцип локальности ссылок (недоказуемый, но подтверждаемый на практике) состоит в том, что если в период времени (T-t, T) программа обращалась к страницам (С1, С2, ..., Сn), то при надлежащем выборе t с большой вероятностью эта программа будет обращаться к тем же страницам в период времени (T, T+t). Другими словами, принцип локальности утверждает, что если не слишком далеко заглядывать в будущее, то можно хорошо его прогнозировать исходя из прошлого. Набор страниц (С1, С2, ..., Сn) называется рабочим набором программы (или, правильнее, соответствующего процесса) в момент времени T. Понятно, что с течением времени рабочий набор процесса может изменяться (как по составу страниц, так и по их числу). Идея алгоритма подкачки Деннинга (иногда называемого алгоритмом рабочих наборов) состоит в том, что операционная система в каждый момент времени должна обеспечивать наличие в основной памяти текущих рабочих наборов всех процессов, которым разрешена конкуренция за доступ к процессору. Мы не будем вдаваться в технические детали алгоритма, а лишь заметим следующее. Во-первых, полная реализация алгоритма Деннинга практически гарантирует отсутствие thrashing. Во-вторых, алгоритм реализуем (известна, по меньшей мере, одна его полная реализация, которая однако потребовала специальной аппаратной поддержки). В-третьих, полная реализация алгоритма Деннинга вызывает очень большие накладные расходы.
Поэтому на практике применяются облегченные варианты алгоритмов подкачки, основанных на идее рабочего набора. Один из таких вариантов применяется и в ОС UNIX (насколько нам известно, во всех версиях системы, относящихся к ветви System V). Мы кратко опишем этот вариант в п. 3.1.3.
