Реализация управления памятью

В операционной системе Windows 2000 поддерживается подгружаемое по тре­бованию одинарное линейное 4-гигабайтное адресное пространство для каждого процесса. Сегментация в любой форме не поддерживается. Теоретически размер страниц может быть любой степенью двух, вплоть до 64 Кбайт. На компьютерах с процессором Pentium страницы имеют фиксированный размер в 4 Кбайт. На компьютерах с процессором Itanium они могут быть 8 или 16 Кбайт. Кроме того, сама операционная система может использовать страницы по 4 Мбайт, чтобы снизить размеры таблицы страниц.

В отличие от планировщика, выбирающего отдельные потоки для запуска и не заботящегося о процессах, менеджер памяти занимается исключительно процесса­ми и не беспокоится о потоках, так как именно процессы, а не потоки вла­деют адресным пространством, которым занимается менеджер памяти. При выде­лении области виртуального адресного пространства менеджер памяти создает для нее описатель виртуаль­ной памяти VAD (Virtual Address Descriptor), в котором хранится информация о диапазоне отображаемых адресов, файле резервного хранения и смещении в файле для отображаемой части файла, а также режим доступа. Когда происходит обращение к первой странице, создается каталог таблиц страниц, а указатель на нее помещается в описатель виртуальной памяти. Адресное пространство полнос­тью описывается списком своих описателей виртуальной памяти. Такая схема по­зволяет поддерживать несплошные адресные пространства, так как неиспользуе­мые области между отображаемыми областями не потребляют ресурсов.

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

Страничные прерывания подразделяются на пять категорий:

1.Страница, к которой было обращение, не является фиксированной.

2.Произошло нарушение защиты.

3.Запись в совместно используемую страницу.

4.Стеку требуется дополнительная память.

5.Страница, к которой было обращение, является фиксированной, но в насто­ящий момент она не загружена в память.

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

Отметим, что операционная система Windows 2000 не читает отдельные страницы прямо с дис­ка. Вместо этого считывается несколько последовательных страниц, как правило, от 1 до 8, чтобы минимизировать количество обращений к диску. Для страниц, со­держащих код программы, используются серии из большего числа страниц, чем при считывании страниц данных.

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

В системе подкачки активно использует­ся понятие рабочего набора. У каждого процесса (не у каждого потока) есть рабо­чий набор. Этот набор состоит из отображенных страниц, находящихся в памяти, при обращении к которым, следовательно, не происходит страничных прерываний. Размер и состав рабочего набора, естественно, меняются по мере работы процесса. Рабочий набор каждого процесса описывается двумя параметрами: минималь­ным и максимальным размерами. Эти размеры не являются жесткими границами. Процесс может иметь в памяти меньше страниц, чем значение нижней границы, или (при определенных обстоятельствах) больше установленного максимума. Вначале эти границы одинаковы для каждого процесса, но они могут меняться со временем. Начальное значение минимума по умолчанию находится в диапазоне от 20 до 50 страниц, а начальное значение максимума по умолчанию находится в диапазоне от 45 до 345 страниц, в зависимости от общего объема оперативной па­мяти. Значения по умолчанию могут быть изменены системным администратором.

Если происходит страничное прерывание, а размер рабочего набора меньше минимального значения, то к рабочему набору добавляется страница. С другой стороны, если происходит страничное прерывание, а размер рабочего набора боль­ше максимального значения, то из рабочего набора (но не из памяти) изымается страница, чтобы выделить место для новой страницы. Этот алгоритм означает, что в операционной системе Windows 2000 используется локальный алгоритм, не по­зволяющий процессу получить слишком много памяти, что предотвращает при­чинение процессами ущерба друг другу. Однако система пытается настроить эти параметры. Например, если она замечает, что один процесс слишком активно за­нимается подкачкой (а остальные процессы нет), система может увеличить значе­ние максимального предела для рабочего набора. Таким образом, алгоритм пред­ставляет собой смесь локальных и глобальных решений. Тем не менее существует абсолютный предел размера рабочего набора: даже если в системе работает всего один процесс, он не может занять последние 512 страниц, чтобы оставить немного оперативной памяти для новых процессов.

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

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

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

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

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

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

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

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

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

Для отслеживания всех страниц и всех списков операционная система Win­dows 2000 содержит базу данных страничных блоков, состоящую из записей по числу страниц ОЗУ. Эта таблица проиндексирована по номеру физи­ческого страничного блока. Записи таблицы имеют фиксированную длину, но для различных типов записей используются различные форматы (например, для дей­ствительных записей и для недействительных). Действительные записи содержат информацию о состоянии страницы, а также счетчик, хранящий число ссылок на эту страницу в таблицах страниц. Этот счетчик позволяет системе определить, ког­да страница уже более не используется. Если страница находится в рабочем наборе, то в записи также указывается номер рабочего набора. Кроме того, в записи содер­жится указатель на таблицу страниц, в которой есть указатель на эту страницу (если такая таблица страниц есть). Страницы, используемые совместно, учитыва­ются особо. Также запись содержит ссылку на следующую страницу в списке (если такая есть) и различные другие поля и флаги, такие как «страница читается», «страница пишется» и т. д.

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

8.4. Ввод-вывод в системе Windows 2000