Страничный механизм. Структура данных, используемая для страничного механизма управления памятью – это дескриптор стра- ниц (рис.11.6).
Рис. 11.6. Дескриптор страниц
Общее число страниц, адресуемых через дескриптор страниц, составляет 2 20
= 1 Мб. Часть линейного адреса, отводимая под сме- щение внутри страницы, таким образом, составляет 32-20 = 12 бит.
Размер страницы составляет 2 12
= 4 Кб.
Поля в структуре дескриптора станиц имеют следующее назначение: AVL – резерв ОС; D – признак модификации; А – при- знак того, был ли доступ; PCD, PWT – биты управления кэширова- нием страницы; U – пользователь/супервизор; W – разрешение запи- си в страницу; Р – бит присутствия страницы в физической памяти.
Так как дескриптор занимает в памяти 4 байта, а всего де- скрипторов 1 М, для хранения таблицы страниц в физической памя- ти потребуется 4 Мб оперативной памяти. Хранение таблицы стра-
102 ниц целиком привело бы к нерациональному использованию физи- ческой памяти. Поэтому в архитектуре i386 используется двухуров- невый механизм преобразования линейного виртуального адреса в физический. Схема такого преобразования адреса показана на рис.11.7.
Рис. 11.7. Схема преобразования линейного виртуального адреса в физический
Идея механизма состоит в том, чтобы использовать странич- ный механизм для управления самой таблицей страниц. То есть ча- сти таблицы страниц могут храниться во внешней памяти и подгру- жаться в оперативную память по мере необходимости.
Таблица страниц состоит из каталога разделов и разделов.
Старшие 10 бит линейного виртуального адреса используются для адресации раздела внутри каталога разделов. Следующие 10 бит ис- пользуются для адресации страницы внутри раздела. Таким образом, каталог разделов, так же как и раздел, может включать в себя 1024
(2 10
) дескриптора. Размер дескриптора равен 4 б и каталог разделов целиком умещается в физическую страницу (4 Кб). Каталог разделов всегда присутствует в физической памяти, его адрес содержится в управляющем регистре CR3. Старшие 10 бит умножаются на 4 (т.к.
10 10 12
Линейный виртуальный адрес
20
Каталог разделов
Номер физиче- ской страницы
20
Раздел таблицы страниц
Номер физической страницы
Физическая память запрашиваемая страница страница раздела страница каталога
+
+
+
+
CR3
Адрес ката- лога разде- лов
103 дескриптор имеет размер 4 б = 2 2
) и складываются с адресом в CR3, получается адрес дескриптора раздела в физической памяти. В нем содержится номер физической страницы раздела. С его использова- нием вычисляется адрес дескриптора запрашиваемой страницы внутри раздела. Наконец, этот дескриптор содержит адрес запраши- ваемой физической страницы.
Для ускорения описанного преобразования линейного адреса в блоке управления страницами кэшируется 20 последних комбина- ций номеров виртуальной и физической страницы.
Средства вызова подпрограмм и задач. Существуют внут- рисегментные и межсегментные вызовы, которые осуществляются командами CALL и JMP. Внутрисегментные вызовы не имеют осо- бенностей. Различаются межсегментные вызовы с использованием дескриптора сегмента кода, шлюза вызова и вызова с переключени- ем задачи через TSS (сегмент состояния задачи). Схема непосред- ственного вызова через дескриптор кода показана на рис.11.8.
Рис. 11.8. Вызов через дескриптор кода
При вызове может указываться дескриптор сегмента кода. В этом случае возможны подчиненный и неподчиненный вызовы. При подчиненном вызове (С=1) можно вызвать сегмент кода с более вы-
Виртуальное или физическое адресное пространство селектор смещение
:
GDT или LDT
Дескриптор сегментного кода база размер
С
DPL
+
+
CALL
104 соким уровнем привилегий, чем CPL, при этом текущий уровень привилегий не изменяется. При неподчиненном вызове (C=0) вызов осуществляется только в случае CPL≤DPL. Недостаток этого меха- низма в том, что он не обеспечивает защиту операционной системы: можно задать произвольную точку входа в кодовый сегмент опера- ционной системы; отсутствует защита ее стека вызовов.
Защищенный вызов с повышением уровня привилегий обес- печивает шлюз вызовов (рис.11.9).
Рис. 11.9. Формат дескриптора шлюза
На рис.11.9 используются следующие обозначения. Селектор – селектор сегмента кода, в котором находится вызываемая процедура или TSS. Смещение – точка входа в процедуру. Счетчик слов пока- зывает, сколько слов требуется скопировать из стека текущего уров- ня привилегий в стек уровня привилегий вызываемой подпрограм- мы. Вызов разрешен, если CPL≤DPL, но DPL сегмента, на
который указывает селектор, может быть любым. При удачном вызове про- цедура выполняется именно с указанным в требуемом сегменте уровнем привилегий DPL. Схема вызова через шлюз вызова показа- на на рис. 11.10.
В команде CALL также может быть непосредственно указан селектор сегмента TSS, хранящий полное состояние задачи, на кото- рую выполняется переключение. Состояние текущей задачи запоми- нается в сегменте TSS, на который указывает регистр TR.
Смещение (16-32)
Селектор (0-15)
Смещение (0-15)
D DPL S=0 C/4 0
-4 сегмент ОС (см. дескриптор сегмента) счетчик слов
105
Рис. 11.10. Схема вызова через шлюз
Лекция 12. Обзор алгоритмов замещения страниц
Оптимальный алгоритм; простые алгоритмы замещения, основан- ные на статистике использования страниц: алгоритм NRU, алгоритм
FIFO, алгоритм «вторая попытка», алгоритм «часы»; алгоритмы вы- грузки страницы, не использовавшейся дольше всех LRU: аппарат- ные реализации LRU, алгоритм NFU, алгоритм старения; алгоритмы, использующие понятие «рабочий набор».
Алгоритмы замещения страниц преследуют цель сделать осмысленный выбор удаляемой страницы для повышения произво- дительности работы операционной системы. Когда происходит страничное прерывание и в памяти не оказывается свободного места
(свободного страничного блока) для размещения запрашиваемой
+
Дескриптор шлюза
GDT или LDT селектор
<не исп.>
:
CALL селектор смещение п/п база размер
Дескриптор
Виртуальное или физическое адресное пространство
106 страницы, требуется освободить место для её загрузки, удалив неко- торую страницу из памяти. Хотя каждый раз для удаления можно выбирать случайную страницу, производительность системы замет- но повысится, если удалить редко используемую страницу. Если же удалить страницу, обращение к которой происходят часто, велика вероятность, что вскоре потребуется вернуть её в память, и возник- нут дополнительные издержки.
Проблемы, похожие на проблему замещения страниц при управлении страничной памятью, возникают и в смежных областях.
Например, сходные проблемы возникают при проектировании аппа- ратных кэшей процессоров или кэшировании web-страниц в прокси- серверах.
Оптимальный алгоритм. Допустим, что нам известно поведение программы в любой момент времени в будущем, то есть в произвольный момент исполнения программы нам известна будущая последовательность выполняемых программой команд и обращений к памяти. Если так, то в любой момент времени для любой страницы
P программы мы можем определить число команд K(P), после выполнения которых наступит обращение к данной странице.
Очевидно, что выгрузить следует страницу с наибольшим значением признака K(P).
Данный алгоритм иллюстрирует принцип выбора замещаемой страницы и имеет только теоретическое значение. Действительно, информацию, необходимую для работы оптимального алгоритма, можно получить лишь при повторном запуске программы, притом с теми же исходными данными. Этот алгоритм может использоваться для оценки эффективности работы реализуемых на практике алгоритмов.
Алгоритм определения не использовавшейся в последнее
время страницы (NRU).
Алгоритм NRU (Not Recently Used) предполагает наличие таймера и аппаратно управляемых статусных битов страницы R и M.
Бит R (Referenced) устанавливается аппаратно всякий раз при обращении к странице. Бит M (Modified) устанавливается аппаратно, если обращение выполняется для записи в страницу. Те же статусные биты могут называться A (Access – признак доступа) и D
(Dirty – признак загрязнения). Заметим, что при отсутствии таких
107 битов их можно смоделировать путем обработки прерываний по ошибке доступа к странице.
Алгоритм NRU работает следующим образом. Периодически по прерыванию от таймера сбрасывается в 0 значение бита R. В момент возникновения страничного прерывания все страницы, в зависимости от состояния битов R и M, относят к 4-м классам: класс
0 – R=0 и M=0; класс 1 – R=0 и M=1; класс 2: R=1 и M=0; класс 3 –
R=1 и M=1. Для выгрузки выбирается произвольная страница из не пустого класса с минимальным номером.
Алгоритм предполагает, что лучше выгрузить изменённую страницу, к которой не было обращений в течение одного тика таймера (из класса 1), чем стереть часто используемую страницу (из класса 2). Достоинством алгоритма является лёгкость для понимания и реализации. Его производительность не оптимальна, но может оказаться достаточной для некоторых приложений.
Алгоритм FIFO. Это подход к проектированию класса алго- ритмов с небольшими накладными расходами на функционирование, основанный на использовании очереди с дисциплиной обслужива- ния FIFO (First-In-First-Out). Операционная система поддерживает список всех страниц в списке FIFO. Страницы попадают в конец очереди при загрузке в память. При страничном прерывании для выгрузки берётся страница из головы очереди. Проблемой данной упрощённой реализации является то, что выгруженной может оказаться часто используемая страница.
Алгоритм «вторая попытка». Простейшим усовершенст- вованием алгоритма FIFO, позволяющим избежать выгрузки часто используемой страницы, является использование бита обращения к странице R. Так же, как и в алгоритме NRU, данный бит устанавливается аппаратно при доступе к странице и периодически сбрасывается по прерыванию от таймера. При страничном прерывании берётся страница из головы очереди. Однако она выгружается только в случае, если R=0. Если R=1, то значение бита этой страницы устанавливается в R:=0 и она помещается в хвост очереди. Для анализа извлекается следующая страница из головы очереди. Алгоритм получил своё название «вторая попытка» (second chance) потому, что если все страницы имеют установленный бит
R=1, то происходит «вторая попытка» выгрузки первой страницы по исходному алгоритму FIFO.
108
Алгоритм «часы». Можно заметить, что алгоритм «вторая попытка» эффективнее реализуется на основе кольцевого списка с указателем, перемещающимся по элементам данного списка. Такую структуру можно мысленно представить в виде циферблата часов с движущейся стрелкой. Когда происходит страничное прерывание, проверяется та страница, на которую указывает стрелка вообра- жаемых часов. Если требуется выгрузка (
R=0), то новая страница замещает выгружаемую страницу в памяти (и позиции списка, указываемой стрелкой), а сама стрелка перемещается на следующую запись в списке. На этом обработка страничного прерывания завершается. Если выгрузка страницы не требуется, то выполняется модификация бита (
R:=0); стрелка перемещается на следующую запись в списке и снова выполняется проверка условия выгрузки
R=0.
Дольше всех не использовавшаяся страница (LRU). В основе LRU (the Least Recently Used) аппроксимации оптимального алгоритма лежит статистическая закономерность, верная для большинства программ: страницы, к которым были многократные обращения в нескольких последних командах, также часто будут использоваться в последующих командах. Эта идея приводит к следующему реализуемому алгоритму: когда происходит страничное прерывание, выгружается страница, которая не использовалась дольше всего.
Для эффективной реализации алгоритма LRU требуется аппаратная поддержка в архитектуре компьютера. Например, можно использовать аппаратный счетчик, который в начале исполнения программы равен нулю и автоматически возрастает после каждой команды. Каждая запись в таблице страниц должна содержать специальное поле для хранения значения счетчика. После каждого обращения к памяти значение счетчика записывается в поле стра- ницы, к которой произошло обращение. Если произошло страничное прерывание, операционная система проверяет все значения счетчиков, сохранённые в таблице страниц. Страница с наименьшим значением поля счетчика удаляется, если нет свободных страничных блоков для размещения в памяти запрашиваемой страницы.
Ещё один вариант оборудования LRU – это
специальное устройство, которое хранит и управляет изменением значений битовой матрицы размера
N x
N, где
N – количество страничных
109 блоков в компьютере. Всякий раз, когда происходит обращение к страничному блоку k, вначале производится заполнение всех элементов строки k матрицы единицами, а затем заполнение всех элементов столбца k матрицы нулями. Оказывается, что строка матрицы, имеющая наименьшее значение (если её представить как двоичную запись числа), будет соответствовать наиболее давно использовавшейся станице памяти, как показано на рис. 12.1.
№ страницы
№ страницы
№ страницы
№ страницы
№ страницы
№ 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0
1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0
2 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 0 1
3 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0
Обращение 0 Обращение 1 Обращение 2 Обращение 3 Обращение 2
Рис. 12.1. Работа алгоритма LRU, использующего матрицу
Алгоритм NFU. Ввиду редкости аппаратной поддержки метода LRU интерес представляют его программные реализации, использующие стандартную аппаратуру большинства компьютеров.
Одна из разновидностей программных реализаций LRU называется алгоритмом NFU (Not Frequently Used – редко использовавшаяся страница). Для него необходим программный счетчик, связанный с каждой страницей в памяти, изначально равный нулю. Во время прерывания от таймера операционная система исследует все записи в таблице страниц. Бит R каждой страницы прибавляется к значению счетчика страницы, затем сбрасывается в ноль. При страничном прерывании для замещения выбирается страница с наименьшим значением счетчика.
Проблемой алгоритма является то, что он не забывает значе- ния счетчика обращений с течением времени. Работа многих прог- рамм состоит из фаз. Например, такие фазы присутствуют в много- проходном компиляторе. После выполнения первой фазы страницы кода этой фазы будут иметь большие значения счетчика обращений.
Во второй фазе страницы с кодом первой фазы использоваться не
110 будут, но будут иметь низкую вероятность выгрузки, провоцируя выгрузку страниц с кодом второй фазы с малыми значениями счетчика обращений.
Алгоритм старения. Необходимые изменения алгоритма NFU при обработке прерываний от таймера состоят из двух частей. Во- первых, каждый счетчик вначале сдвигается вправо на один разряд.
Во-вторых, значение бита R не прибавляется, а записывается в крайний левый бит счетчика. Работа видоизменённого алгоритма, известного под названием «старение» (aging), показана на рис. 12.2.
R
101011 110010 110101 100010 011000
№ страницы
0 10000000 11000000 11100000 11110000 01111000 1
00000000 10000000 11000000 01100000 10110000 2
10000000 01000000 00100000 00010000 10001000 3
00000000 00000000 10000000 01000000 00100000 4
10000000 11000000 01100000 10110000 01011000 5
10000000 01000000 10100000 01010000 00101000
а)
б)
в)
г)
д)
Рис. 12.2. Работа алгоритма старения после пяти тиков таймера от (а) до (д)
Когда происходит страничное прерывание, удаляется страница с наименьшим значением счетчика. Например, счетчик страницы, к которой не было обращений 4 тика, будет иметь 4 нуля справа. То есть он будет иметь меньшее значение, чем счетчик страницы, к которой не было обращений 3 тика таймера с 3 нулями справа.
Алгоритм может принять неправильное решение о времени последнего использования страницы в двух случаях. Рассмотрим момент времени д) на рис. 12.2. К страницам 3 и 5 не было обращений 2 тика таймера подряд. Согласно алгоритму старения для вытеснения следует выбрать страницу 3 с меньшим значение счётчика. Однако мы не знаем к третьей или пятой странице 3 тика назад произошло обращение позже, ввиду недостаточности
111 разрешения таймера. Согласно правилу LRU для вытеснения следует выбрать страницу 5, если к ней 3 тика назад произошло обращение позже, что противоречит алгоритму старения.
Другой случай возникает, когда у двух или более счетчиков значения равны нулю. Алгоритм старения выбирает произвольную страницу, хотя время последнего доступа у таких страниц может значительно отличаться. На практике, при использовании времени тика 20 мс и 8 битов счетчика, отсутствие обращений в течение 160 мс означает, что с большой вероятностью страница не важна и её можно выгрузить без потери эффективности.
Понятие «рабочий набор». Множество страниц, которое процесс использует в данный момент, называется рабочим набором.
Если рабочий набор
целиком находится в оперативной памяти, то процесс не вызывает страничных прерываний, пока выполнение не перейдёт к следующей фазе (например, к следующему проходу компиляции) и рабочий набор не изменится. Знать состав рабочего набора процесса важно в момент загрузки процесса для того, чтобы сразу загрузить все страницы рабочего набора, выполнив опережающую подкачку (prepaging). Если этого не делать и поло- житься на загрузку по запросу (demand paging), то вначале работы процесса эффективность выполнения окажется низкой из-за частых страничных прерываний. Поэтому актуально отслеживать состав рабочего набора. Из приведённых рассуждений также следует, что при возникновении страничного прерывания нужно в первую очередь выгружать из памяти страницы, не входящие в рабочий набор.
Для использования в алгоритме замещения страниц требуется точное определение рабочего набора. Формально рабочий набор в момент времени
t – это множество страниц
w(
k,
t), в которое входят все страницы, использовавшиеся за
k последних обращений к памя- ти. Как обычно, в качестве аппроксимации количества обращений к памяти удобно использовать время вычисления. При этом учиты- вается только время, в течение которого процесс выполнялся. Оно называется виртуальным временем процесса.
Алгоритм WSClock. В алгоритме WSClock используется значение текущего виртуального времени процесса, биты
R и
M.
Записи о страничных блоках процесса организованы в виде кольцевого списка с указателем. Определено также предельное
112 время нахождения страницы в рабочем наборе k. Время последнего обращения к странице фиксируется обычным образом: по прерыванию от таймера проводится сканирование записей страничных блоков, у блоков с R=1 обновляется время последнего использования текущим значением виртуального времени процесса и бит R сбрасывается в ноль.
При возникновении страничного прерывания начинается обход кольцевого списка, начиная с текущей позиции указателя. Во время обхода выполняются следующие действия. Если R=1, то выполняется присваивание R:=0 и переход к следующей записи.
Если R=0 и возраст страницы больше k, то страница не входит в рабочий набор и может быть замещена. Если у этой страницы M=0, то страница переписывается замещаемой страницей и обработка страничного прерывания завершается. Иначе у этой страницы M=1, поэтому запускается асинхронный сброс содержимого страницы на диск, а сканирование кольцевого списка продолжается.
Если при обходе кольцевого списка происходит возврат к исходной позиции указателя, то возможны два состояния:
1) запланирована, по крайней мере, одна операция сброса страницы на диск;
2) не запланировано ни одной операции сброса.
В первом случае, так как запланированные операции сброса со временем завершатся и установят бит M:=0 у сбрасываемых на диск страниц, требуется продолжать сканирование. Сканирование, в конце концов, приведет к замещению страничного блока содержи- мым запрашиваемой страницы и выходу из процедуры обработки страничного прерывания. Во втором случае все страницы находятся в рабочем наборе. Если есть чистая страница (M=0), то для выгрузки выбирается она, иначе выбирается произвольная грязная страница (c
M=1), и обработка страничного прерывания завершается.
Положение последней по порядку обхода чистой страницы должно отслеживаться в цикле обхода. Число планируемых асинх- ронных операций выгрузки грязных страниц ограничивают некото- рым разумным пределом, по достижении которого планирование не происходит.
Рассмотрены основные алгоритмы замещения страниц, имеющие теоретическое и практическое значение. Из приведённых алгоритмов, благодаря простой реализации и хорошей произво-
113 дительности, на практике чаще всего используются алгоритм старения и алгоритм WSClock.
Лекция 13. Управление виртуальной памятью
в ОС Windows
Структура виртуального адресного пространства процесса. Обзор мето- дов управления памятью в OC Windows. Применение функции
VirtualAlloc. Обработка страничных прерываний с использованием струк- турированной обработки исключений. Файлы, отображаемые в память.
Структура виртуального адресного пространства процес-
са. Виртуальное адресное пространство процесса 32-разрядных вер- сий Windows устроено следующим образом. Существует 3 варианта структур адресного пространства в зависимости от версии операци- онной системы и системных настроек.
Серверные версии ОС (например, Win2k Advanced Server) имеют следующее распределение памяти. В область старших адре- сов проецируется код и данные операционной системы. Однако прямой доступ из процесса пользователя к ним невозможен и вызы- вает прерывание. Младшие 3 Гб оперативной памяти принадлежат пользователю (рис. 12.1).
Рис. 12.1. Распределение памяти в системе Win2k Advanced Server
1Г
3Г
ОС пользователь
0
FFFF FFFF
114
В «десктопных» 32-разрядных версиях (например, Win NT/2k) пользователю выделяются младшие 2 Гб адресного пространства
(рис. 12.2).
Рис. 12.2. Распределение памяти в системе Win NT/2k
Распределение памяти в ранних 32-разрядных операционных системах Win 95/98/ME показано на рис. 12.3.
Рис. 12.3. Распределение памяти в системах Win 95/98/ME
2Г
2Г
ОС пользователь
0
FFFF FFFF
Системный код
ОС
Пользователь
Память, разделяемая процессами
Резерв для совместимости с MS-DOS
0
FFFF FFFF
System.dll
64К-4М
0-64К
MS-DOS (только чтение)
115
Таким образом, в 32-разрядных операционных системах се- мейства Windows пользователь может выделить блок памяти, распо- лагающийся по непрерывным адресам размером 2-3 Гб в зависимо- сти от настройки и версии, так как код и данные операционной си- стемы помещаются (проецируются) в адресное пространство каждо- го процесса. В Windows 95/98/ME не используется защита памяти от ошибочных или злонамеренных действий пользователя. В версиях на базе ядра NT механизм защиты реализован полностью.
Средствами операционной системы поддерживаются несколь- ко механизмов управления памятью. Простейшим является меха- низм динамической памяти. Процесс может иметь один или не- сколько разделов динамической памяти внутри пользовательской части виртуального адресного пространства (несколько куч процес- сов). К кучам может быть организован синхронизированный доступ из нескольких потоков. Кучи можно создавать динамически и уда- лять целиком. Они предназначены для создания большого количе- ства относительно малых по размеру блоков памяти. Функции для работы с кучами имеют префикс Heap в своих названиях, например
HeapAlloc.
Существуют некоторые специфические ситуации в практике программирования, когда использование возможностей библиотеки времени исполнения и куч операционной системы оказывается не- достаточным. Например, при обработке массивов данных большого размера, не умещающихся в оперативной памяти целиком, в чис- ленном моделировании, при обработке большеформатных изобра- жений. В данном случае необходимо воспользоваться средствами управления виртуальной памятью. В Windows такое управление ре- ализуется функцией VirtualAlloc и другими вспомогательными функциями API. Совместно с функцией VirtualAlloc обычно исполь- зуется механизм структурированной обработки исключений.
Для управления большими объемами данных, организации межпроцессного взаимодействия через общую (разделяемую) па- мять используется механизм отображения файлов на виртуальную память процессов. На данном механизме основана работа самой операционной системы при загрузке исполняемых файлов и дина- мической компоновке библиотек.
Дополнительно 32-разрядным приложениям Windows досту- пен программный интерфейс Address Windowing Extensions (AWE),
116 позволяющий получить доступ ко всему физическому адресному пространству компьютера (если его размер превышает 4 Гб) через адресное окно в пределах пользовательских 2-3 Гб в виртуальном адресном пространстве процесса. В современных 64-разрядных вер- сиях операционных систем объем пользовательского адресного про- странства, как правило, значительно превышает объем оперативной памяти и в использовании механизма AWE не возникает необходи- мости.
В качестве примера работы с виртуальной памятью рассмот- рим реализацию поиска простых чисел методом решета Эратосфена.
В алгоритме используется массив флагов arr размером MAXNUM, где MAXNUM граница числового диапазона, внутри которого ищутся все простые числа. Метод заключается в постепенном вы- черкивании всех составных чисел установкой флагов arr[num]=1.
Все не помеченные флагами числа будут являться простыми. Для нас в данном алгоритме представляет интерес организация сканиро- вания массива размером около 1 Гб.
Объявления и инициализация.
#include "stdafx.h"
DWORD i,j,num;
DWORD MAXNUM=1024*1024;
LPSTR arr;
DWORD dwPageSize;
VOID ErrorExit(LPTSTR);
INT PageFaultExceptionFilter(DWORD); int main(intargc, char* argv[])
{
BOOL bSuccess;
SYSTEM_INFO sSysInfo; int num_MB=1; printf("Amount of memory in MB:"); scanf("%d",&num_MB); printf("Getting %d MB...\n",num_MB);
MAXNUM*=num_MB;
117
GetSystemInfo(&sSysInfo); dwPageSize = sSysInfo.dwPageSize; arr =
(LPSTR)VirtualAlloc(NULL,MAXNUM,MEM_RESERVE,
PAGE_NOACCESS); if (arr == NULL) ErrorExit("VirtualAlloc reserve failed"); else printf("VirtualAlloc successful\n");
Для работы программы нам потребуется подключить некото- рые заголовочные файлы, среди которых
. На массив флагов указывает переменная arr, размер массива хранится в пере- менной MAXNUM. При ее инициализации пользователю программы предлагается ввести размер массива в мегабайтах. Также в начале работы вычисляется размер страницы с использованием функции
GetSystemInfo и выполняется резервирование памяти размером
MAXNUM в произвольной области виртуальной памяти процесса под массив флагов.
Резервирование необходимо по следующей причине. Фактиче- ски запущенной программе разрешен доступ только к незначитель- ной части адресов из ее пространства в 2 Гб. Это области, где нахо- дится код программы, ее ресурсы, статические переменные, стеки и кучи. Обращения к остальной части адресов пространства пользова- теля вызовет прерывания. Страницы, соответствующие этим адре- сам, отсутствуют в оперативной памяти. Более того, операционная система автоматически не поддерживает структуры для управления такими страницами. Управление всем 2 Гб адресным пространством у каждого запущенного процесса было бы крайне накладно с точки зрения используемых ресурсов.
С точки зрения системного программиста виртуальная память процесса разделена на страницы, которые могут находиться в трех состояниях.
Свободная страница (free). Доступ к таким страницам запре- щен. Операционная система не поддерживает структуры для управ- ления свободными страницами, при обращении к ним возникает страничное прерывание.
Зарезервированная страница (reserve). Операционная система подготавливает необходимые управляющие структуры для этих
118 страниц, но физическая память не выделена. При обращении также возникает страничное прерывание.
Выделенная страница (committed). Страница присутствует в физической памяти, при обращении прерывание не происходит.
Последняя часть инициализирующего кода выполняет резер- вирование блока памяти из последовательно расположенных стра- ниц по произвольному начальному адресу в виртуальном адресном пространстве процесса. Адрес начала блока присваивается перемен- ной arr.
__try
{ for(i=0;i{ num=i;if(arr[num])continue; printf("%d\n",i); for(j=i*2;j}
}
__except ( PageFaultExceptionFilter(
GetExcetionCode() ) )
{
ExitProcess(GetLastError() );
} bSuccess = VirtualFree(arr,0,MEM_RELEASE); printf ("Release was %s.\n", bSuccess ?
"successful" : "unsuccessful" ); return 0;
}
Далее сам алгоритм реализуется обычным способом, однако он помещается внутри блока структурированной обработки исклю- чений. В блоке выполняется обращение к массиву arr – как будто память действительно выделена. Цель такой организации кода: пе- рехватить прерывания, возникающие при обращении к странице па-
119 мяти, принадлежащей массиву arr; вручную выполнить загрузку страницы в оперативную память; передать управление в точку воз- никновения прерывания.
Стандартная конструкция C++ для перехвата исключений catch(ExceptionType C) {…}. В отличие от нее, фильтр исключения
__except(…) содержит выражение, вычисляемое в момент исключе- ния. Значение этого выражения управляет передачей управления при возникновении исключения. Особенностью структурированной обработки является наличие семантики продолжения, которую мы используем в примере.
Еще одной особенностью фильтра исключений и тела обра- ботчика исключений является то, что в них используются специаль- ные встроенные псевдофункции (intrinsic function), обрабатываемые непосредственно компилятором. В примере такой функцией являет- ся функция GetExceptionCode(), которая возвращает код исключе- ния. Ее использование бессмысленно вне контекста исключения и вызывает ошибку компиляции.
Код обработчика исключений выглядит следующим образом:
INT PageFaultExceptionFilter(DWORD dwCode)
{
LPVOID lpvResult;
DWORD comSize; if (dwCode != EXCEPTION_ACCESS_VIOLATION)
{ printf("Exception code = %d\n", dwCode); return EXCEPTION_EXECUTE_HANDLER;
}
//printf("Exception is a page fault\n"); if(MAXNUM-num>dwPageSize)comSize=dwPageSize; else comSize=MAXNUM-num; lpvResult = VirtualAlloc(
&arr[num],comSize,MEM_COMMIT,PAGE_READWRITE); if (lpvResult == NULL )
{
120 printf("VirtualAlloc failed\n"); return EXCEPTION_EXECUTE_HANDLER;
} else {
//printf ("Allocating another page.\n");
} return EXCEPTION_CONTINUE_EXECUTION;
}
Обработчик получает код исключения и возвращает значение, определяющее передачу управления после обработки. Мы используем следующие возвращаемые значения: EXCEPTION_EXECUTE_
HANDLER для возврата управления в тело обработчика исключений в секции __except и аварийному завершению; EXCEPTION_
CONTINUE_EXECUTION для возврата к месту возникновения страничного прерывания и повторной попытки обращения к памяти.
Для передачи управления следующему обработчику в иерархии мо- жет использоваться значение EXCEPTION_CONTINUE_ SEARCH.
Загрузку страницы в физическую память выполняет вызов
VirtualAlloc с параметром MEM_COMMIT. Код загрузки имеет сле- дующие особенности. Страница, в которой произошло исключение, вычисляется с использованием глобальной переменной num, выпол- няющей роль индекса по массиву arr. Доступ к массиву выполняется только с использованием данной переменной. Способ, не требую- щий глобальной переменной num, состоит в получении адреса, по которому возникло исключение при помощи еще одной встроенной псевдофункции GetExceptionInformation().
Другой особенностью является коррекция запрашиваемого к загрузке размера памяти comSize. Она необходима при сканирова- нии последней страницы массива, чтобы не выйти за пределы заре- зервированной под массив arr области.
Наконец, после использования, аналогично кучам, виртуаль- ная память требует очистки, которая выполняется вызовом
VirtualFree(arr,0,MEM_RELEASE).
Кратко рассмотрим работу с файлами, отображаемыми в па- мять процесса. Работа состоит из следующих этапов.
Вначале нужно получить описатель файла, куда при работе механизма отображения будут сбрасываться страницы памяти. Данный этап можно пропу- стить, если используется файл подкачки.
121
Далее создается объект отображения при помощи вызова hMapFile = CreateFileMapping(hFile,// описатель файла
NULL, // безопасность
PAGE_READWRITE, // желаемый доступ
0, 0, // размер объекта и файла
“name”); // имя объекта
Сконструированный объект ядра с описателем hMapFile может использоваться для организации взаимодействия процессов через разделяемую память. Для этого нужно передать описатель другому процессу рассмотренными ранее способами.
Далее выполняется собственно проецирование при помощи вызова вида lpMapAddress = MapViewOfFile(hMapFile,
FILE_MAP_ALL_ACCESS, 0, 0, 0).
В приведенном примере отображается весь файл целиком. Ра- бота с файлами большого размера осуществляется через адресное окно, о чем говорит название функции (map view of file). Функция возвращает адрес начала области памяти, в которую было выполне- но отображение файла. Косвенное обращение по этому адресу, например
*((LPDWORD) pMapAddress) = 1000; позволяет как считывать, так и записывать информацию непосред- ственно в файл без использования функций ввода-вывода. Запись- чтение выполняется механизмом управления страничной памятью
(лекции 10, 11).
После окончания работы с отображением выполняется очист- ка при помощи вызова функции UnMapViewOfFile и закрытия опи- сателей созданных объектов ядра вызовом CloseHandle.
122
Экзаменационные вопросы по разделу IV
1. Методы управления памятью без использования внешней памя- ти. Фиксированные, динамические и перемещаемые разделы.
2. Методы управления памятью с использованием внешней памяти.
Сегментный, страничный, сегментно-страничный способ.
3. Назначение, принцип работы механизма свопинга.
4. Назначение, принцип работы механизма кэширования.
5. Реализация сегментного механизма управления памятью в про- цессорах семейства x86_32.
6. Реализация страничного механизма управления памятью в про- цессорах семейства x86_32. Размер и основные поля структур данных, особенности реализации.
7. Принцип работы алгоритмов замещения страниц, оптимальный алгоритм. Простые аппроксимации оптимального алгоритма: ал- горитм NRU, алгоритм FIFO, алгоритм «вторая попытка», алго- ритм «часы».
8. Алгоритмы выгрузки дольше всех не использовавшейся страни- цы LRU: аппаратные реализации LRU, алгоритм NFU, алгоритм старения.
9. Понятие «рабочий набор», алгоритм WSClock.
10. Средства ОС Windows для управления виртуальной памятью процесса. Функция VirtualAlloc. Структурированная обработка исключений. Файлы, отображаемые в память.
Скачать 2.09 Mb.