Управление виртуальной памятью в Windows NT

Восьмидесятые годы благодаря появлению персональных компьютеров породили иллюзию простоты системного программирования. Нет вины инженеров компании Intel в том, что им удалось разместить на кристалле только то, что удалось разместить. Наоборот, их продукт следует считать величайшим техническим достижением, изменившим наш мир. Но факт остается фактом - процессор 8086 не предоставлял операционным системам тот сервис, который требовался согласно разработанным теориям создания операционных систем. В первую очередь это касалось систем управления памятью, планировщиков и систем защиты. Достаточно обратиться к классическим книгам того времени [1, 2], чтобы убедиться в том, что теория организации вычислительного процесса была хорошо разработана и реализована.

Но время диктует свои законы. Изменились микропроцессоры, и появились новые операционные системы. Однако у многих профессионалов осталась иллюзия того, что ОС от Microsoft - это лишь красивые картинки на экране и простейшее ядро внутри, а для серьезных задач требуются "серьезные" системы. На примере системы управления памятью покажем, что Windows NT - серьезная операционная система, построенная в соответствии с классическими принципами.

Организация виртуальной памяти

Страничное преобразование

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

Процессоры Intel начиная с Pentium Pro позволяют операционным системам применять одно-, двух- и трехступенчатые схемы. И даже разрешается одновременное использование страниц различного размера. Эта возможность, конечно, повысила бы эффективность страничного преобразования, будь она внедрена в Windows NT. Увы, эта ОС возникла раньше и поддерживает только двухступенчатую схему преобразования с фиксированным размером страниц. Размер страниц для платформы Intel составляет 4 Кбайт, а для DEC Alpha - 8 Кбайт. Схема страничного преобразования (рис. 1) выглядит так:

32-разрядный линейный адрес разбивается на три части. Старшие 10 разрядов адреса определяют номер одного из 1024 элементов в каталоге страниц, адрес которого находится в регистре процессора CR3. Этот элемент содержит физический адрес таблицы страниц. Следующие 10 разрядов линейного адреса определяют номер элемента таблицы. Элемент, в свою очередь, содержит физический адрес страницы виртуальной памяти. Размер страницы - 4 Кбайт, и младших 12 разрядов линейного адреса как раз хватает (212 = 4096), чтобы определить точный физический номер адресуемой ячейки памяти внутри этой страницы.

Рассмотрим отдельный элемент таблицы страниц (PTE - Page Table Element) более подробно, так как он содержит массу полезной информации (рис 2).

Старшие пять бит определяют тип страницы с точки зрения допустимых операций. Win32 API поддерживает три допустимых значения этого поля: PAGE_NOACCESS, PAGE_READONLY и PAGE_READWRITE. Следующие 20 бит определяют базовый физический адрес страницы в памяти. Если дополнить их 12 младшими разрядами линейного адреса, они образуют физический адрес ячейки памяти, к которой производится обращение. Следующие четыре бита PTE описывают используемый файл подкачки. Комбинацией этих битов ссылаются на один из 16 возможных в системе файлов. Последние три бита определяют состояние страницы в системе. Старший из них (T-Transition) отмечает страницу как переходную, следующий (D-Dirty) - как страницу, в которую была произведена запись. Информация об изменениях в странице необходима системе для того, чтобы принять решение о сохранении страницы в файле подкачки при ее вытеснении (принудительном освобождении занятой памяти). Действительно, если страница не изменялась в памяти после загрузки, то ее можно просто стереть, ведь в файле подкачки сохранилась ее копия. И наконец, младший бит (P-Present) определяет, присутствует ли страница в оперативной памяти или же она находится в файле подкачки. Конечно, 16 файлов подкачки явно недостаточно. В дальнейшем мы увидим, что в качестве файлов подкачки могут выступать исполняемые файлы, а также файлы, отображаемые в память. Официальная документация Microsoft весьма скупа на комментарии по этой ситуации. Отмечается лишь, что при отсутствии страницы в памяти 28 бит рассмотренного элемента таблицы страниц не несут никакой полезной информации и используются для определения местонахождения выгруженной страницы.

Для ускорения страничного преобразования в процессоре имеется специальная кэш-память, называемая TLB (Translation Lookaside Buffer). В ней хранятся наиболее часто используемые элементы каталога и таблиц страниц. Конечно, переключение процессов и даже потоков приводит к тому, что данные внутри этого буфера становятся неактуальными, т. е. недействительными. Это влечет за собой дополнительные потери производительности при переключении. К счастью, временной промежуток, выделяемый системой процессу, составляет 17 мс. Даже на машине с производительностью всего 20 MIPS за это время успеет выполниться непрерывный участок программы длиной (17 мс Ё 20 MIPS) 340 тыс. команд. Этого более чем достаточно, чтобы пренебречь потерями производительности при выполнении начального участка процесса.

Каждый процесс Windows NT имеет свой отдельный каталог страниц и свое собственное независимое адресное пространство, что очень хорошо с точки зрения защиты процессов друг от друга. Но за это удовольствие приходится платить ресурсами. Независимым процессам почти всегда приходится обмениваться информацией друг с другом. Windows NT предоставляет большое количество способов обмена, в том числе и при OLE. Но все они имеют в основе одно и то же действие: один процесс пишет нечто в некоторую ячейку памяти, а другой из нее читает. Это означает, что должны быть участки памяти, доступные разным процессам. На первый взгляд, это не проблема - могут же различные PTE ссылаться на одну и ту же страницу. Однако в каждом PTE хранятся атрибуты страницы, а ссылка на страницу со стороны PTE делается только в одну сторону. Это означает, что при изменении какого-либо атрибута в одном из PTE невозможно сделать то же самое для всех других PTE, ссылающихся на ту же страницу. Именно поэтому для совместно используемых страниц применяется механизм прототипов элементов таблицы страниц (Prototype Page Table Entry). Для совместно используемых страниц создается прототип PTE, который и содержит актуальные атрибуты страницы. Все PTE, принадлежащие различным процессам, ссылаются не на саму страницу, а на этот прототип, атрибуты которого и являются актуальными (рис. 3).

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

Отложенное копирование

Все гениальное - просто. Многие программисты получили истинное наслаждение, впервые ознакомившись с тем, как изящно в Unix реализовано порождение процессов. В результате исполнения системного вызова fork(), призванного создавать новые процессы, два независимых процесса начинают совместно использовать одну и ту же область кода. Прошло немало времени, прежде чем пытливая инженерная мысль нашла возможность совместно использовать одну и ту же область данных. Действительно, нет необходимости каждому процессу иметь отдельный экземпляр данных, если эти данные только читаются. Проблема состоит в том, как определить, будут ли данные читаться в будущем или нет. Неважно, области кода или данных принадлежит совместно используемая память. Существенно лишь то, производится или нет изменение данных процессами. Если процесс производит запись, он должен иметь свою отдельную копию изменяемых данных. Если же в записи нет необходимости, то он может совместно использовать данные с остальными процессами. Подобный подход называется отложенным копированием (lazy evaluation): решение о необходимости копирования страницы откладывается до того момента, когда процесс попытается что-либо записать в нее. Все страницы порожденного процесса защищаются от записи. При попытке изменения защищенной страницы возникает процессорное исключение, страница копируется системой, и только после этого в нее разрешается запись.

Данный механизм, едва появившись, сразу же стал классическим и сегодня является составной частью многих систем Unix. Нет ничего удивительного, что он изначально присутствует в архитектуре и более молодой системы Microsoft Windows NT. Наиболее активно он используется при работе различных процессов с совместно используемыми динамически загружаемыми библиотеками (DLL), а также при запуске программ.

Свопинг

Конечно, компьютер может и не иметь 4 Гбайт оперативной памяти, адресуемых процессорами Intel для того, чтобы обеспечить все линейное адресное пространство процесса физическими ячейками памяти. Windows NT, как и все другие операционные системы, применяет свопинг (swapping). Не используемые в конкретный момент страницы памяти могут быть вытеснены на диск в так называемый файл подкачки. В соответствующем элементе таблицы страниц эта страница помечается как отсутствующая, и при попытке обращения к ней возникает исключительная ситуация - "сбой" страницы. Обрабатывая ее, операционная система находит страницу на диске и переписывает ее в память, соответствующим образом подстраивая элемент таблицы страниц. После этого попытка выполнить команду, вызвавшую исключение, повторяется.

С понятием свопинга неразрывно связаны три стратегии: выборка (fetch), размещение (placement) и замещение (replacement).

• Выборка определяет, в какой момент необходимо переписать страницу с диска в память. В Windows NT используется классическая схема выборки с упреждением: система переписывает в память не только выбранную страницу, но и несколько следующих по принципу пространственной локальности, гласящему: наиболее вероятным является обращение к тем ячейкам памяти, которые находятся в непосредственной близости от ячейки, к которой производится обращение в настоящий момент. Поэтому вероятность того, что будут востребованы последовательные страницы, достаточна высока. Их упреждающая подкачка позволяет снизить накладные расходы, связанные с обработкой прерываний.
• Размещение определяет, в какое место оперативной памяти необходимо поместить подгружаемую страницу. Для систем со страничной организацией данная стратегия практически не имеет никакого значения, и поэтому Windows NT выбирает первую попавшуюся свободную страницу.
• Замещение начинает действовать с того момента, когда в оперативной памяти компьютера не остается свободного места для размещения подгружаемой страницы. В этом случае необходимо решить, какую страницу вытеснить из физической памяти в файл подкачки. Можно было бы отделаться общими словами [6], сказав, что в данном случае Windows NT использует алгоритм FIFO: вытесняется страница, загруженная раньше всех, т. е. самая "старая". Однако механизм замещения настолько интересен, что заслуживает более пристального внимания, и мы еще расскажем о нем.

Несомненный теоретический интерес представляет тот факт, что Windows NT - это система, в которую включены средства динамического анализа рабочего множества процесса, которые используются при организации свопинга. Но обо всем по порядку.

Часть ядра Windows NT, которая занимается управлением виртуальной памятью, называется VMM - Virtual Memory Manager. Это независимый привилегированный процесс, постоянно находящийся в оперативной памяти компьютера. VMM поддерживает специальную структуру, называемую базой данных страниц (page-frame database). В ней содержатся элементы для каждой страницы. Состояние каждой страницы описывается с помощью следующих категорий:

Valid - страница используется процессом. Она реально существует в памяти и помечена в PTE как присутствующая.

Modified - содержимое страницы было изменено. В PTE страница помечена как отсутствующая (P=0) и переходная (T=1).

Standby - содержимое страницы не изменялось. В PTE страница помечена как отсутствующая (P=0) и переходная (T=1).

Free - страница, на которую не ссылается ни один PTE. Страница свободна, но подлежит обнулению, прежде чем будет использована.

Zeroed - свободная и обнуленная страница, пригодная к непосредственному использованию любым процессом.

Bad - страница, которая вызывает аппаратные ошибки и не может быть использована ни одним процессом.

Все состояния, за исключением Modified и Standby, можно обнаружить в большинстве операционных систем. Страница, находящаяся в одном из этих состояний, реально располагается в памяти, в PTE содержится ее реальный адрес, но сама страница помечена как отсутствующая. При обращении к этой странице возникает аппаратное исключение, однако его обработка не вызывает больших временных затрат. Необходимо просто пометить страницу как присутствующую (Valid, P=1) и еще раз запустить последнюю команду.

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

Каждый элемент базы связан двунаправленной ссылкой с соответствующим элементом таблицы страниц для организации двустороннего доступа. Прототип не имеет доступа к PTE. Это и не нужно, поскольку именно он уполномочен представлять атрибуты страницы, а не PTE.

Важнейшее понятие при организации свопинга - рабочее множество процесса (working set). В соответствии с принципом локальности процесс не использует всю память одновременно. Состав и количество страниц, с которыми процесс работает, меняется на протяжении его жизни. Страницы, с которыми процесс работает в течение фиксированного интервала времени, есть его рабочее множество на этом интервале. Переход от одного рабочего множества к другому осуществляется не равномерно, а скачками. Это вызвано семантикой процесса: переходами от обработки одного массива к обработке другого, от подпрограммы к подпрограмме, от цикла к циклу и т. д. Не нужно, чтобы в оперативной памяти размещались все страницы процесса, однако необходимо, чтобы в ней помещалось его рабочее множество. В противном случае возникает режим интенсивной подкачки, называемый трешингом (trashing), с которым сталкивается любой пользователь PC, запустивший одновременно слишком много приложений. В таком режиме затраты системы на переписывание страниц с диска в память и обратно значительно превышают время, выделяемое на полезную деятельность. Фактически система перестает заниматься чем-либо, кроме перемещения головок жесткого диска.

Теперь настало время разрешить интригу, которая возникла несколько абзацев назад, и подробно рассмотреть стратегию замещения страниц Windows NT. В классической теории операционных систем идеальной считается следующая стратегия: замещению подлежит страница, которая не будет использоваться в будущем дольше других. В той же классической теории эта стратегия признается неосуществимой, поскольку нет никакого разумного способа определить, какая из страниц подпадает под этот критерий. К счастью, в мире еще есть инженеры, готовые ломать голову над неосуществимыми идеями. Программистам Microsoft удалось приблизиться к этой стратегии на основе анализа рабочего множества процесса. В Windows NT используется весьма близкая стратегия: из памяти вытесняются страницы, вышедшие из рабочего множества процесса. Как же VMM узнает, какие страницы больше не принадлежат рабочему множеству? А очень просто! Периодически VMM просматривает список страниц с атрибутом Valid и пытается похитить их у процесса. Он помечает их как отсутствующие (P=0), но на самом деле оставляет их на месте, только переводит в разряд Modified или Standby в зависимости от значения бита D из PTE. Если похищенная страница принадлежит рабочему множеству, то к ней в ближайшее время произойдет обращение. Это, конечно, вызовет исключение - ведь страница-то помечена как отсутствующая. Но VMM очень быстро сделает эту страницу вновь доступной процессу, поскольку она реально находится в памяти. Если страница находится вне рабочего множества, то обращений к ней не будет и она со временем перейдет в разряд Free, а затем Zeroed и станет доступна другим процессам системы.

Адресное пространство процесса

В Windows NT используется плоская (flat) модель памяти. Каждому процессу выделяется "личное" изолированное адресное пространство. На 32-разрядных компьютерах размер этого пространства составляет 4 Гбайт и может быть расширен до 32 Гбайт при работе Windows NT 5.0 на процессоре Alpha. Это пространство разбивается на регионы, различные для разных версий системы (рис. 5).

В Windows NT 4.0 младшие 2 Гбайт памяти выделяются процессу для произвольного использования, а старшие 2 Гбайт резервируются и используются операционной системой. В младшую часть адресного пространства помещаются и некоторые системные динамически связываемые библиотеки (DLL). Желание расширить доступное процессу адресное пространство привело к тому, что Windows NT 4.0 Enterprise процессу выделяется дополнительный 1 Гбайт за счет сокращения системной области (рис. 5).

Разработчики Windows NT 5.0 для платформы Alpha пошли дальше. Alpha - 64-разрядный процессор, но под управлением Windows NT версии до 4.0 включительно в его адресном пространстве используются только 2 Гбайт старших и 2 Гбайт младших адресов (рис. 5).

Дело в том, что в Win32 API для хранения адреса используются 32-разрядные переменные. Windows NT расширяет их до 64-разрядных с учетом знака. Спецификация VLM (Very Large Memory), которая будет реализована в Windows NT 5.0 для процессора Alpha, подразумевает использование 64-разрядных переменных для хранения адресов (рис. 5).

Если системе, которую вы разрабатываете, недостаточно для работы 32 Гбайт физической памяти, то, вероятно, вам стоит выбрать другую операционную систему. Если же вы готовы потесниться и произвести некоторую оптимизацию своего кода, то, возможно, вам подойдет и Windows NT.