Файл: Оглавление Раздел I. Основные понятия.pdf

Раздел IV. Управление памятью
Лекция 10. Методы управления памятью
Типы адресов и их преобразований. Классификация методов управ- ления памятью. Методы управления памятью, использующие раз- делы. Страничный, сегментный и сегментно-страничный методы управления виртуальной памятью. Механизм свопинга. Принцип работы кэш-памяти.
В программе можно выделить три типа адресов: символьные имена, виртуальные адреса и физические адреса (рис.10.1). Сим- вольные имена являются идентификаторами переменных в про- грамме. Виртуальные адреса – это условные адреса, вырабатывае- мые транслятором исходного кода в объектный код. В простейшем случае транслятор может выполнять преобразование символьных имен непосредственно в физические адреса. Физические адреса – это номера ячеек в памяти. Данные номера выставляются централь- ным процессором на адресную шину при доступе к оперативной па- мяти.
Преобразование виртуального адреса в физический адрес мо- жет выполняться двумя способами. При загрузке программы в па- мять виртуальные адреса отображаются использованием перемеща- ющего загрузчика. Его работа состоит из загрузки программы в по- следовательные ячейки, начиная с некоторого базового адреса, и настройки смещений внутри программы относительно этого адреса
(рис. 10.2).
Динамическое преобразование происходит при каждом обра- щении по виртуальному адресу в темпе обращений. Для такого пре- образования используется аппаратура компьютера и операционная система.

87
Рис. 10.1. Типы адресов и их преобразований
Рис. 10.2. Схема работы перемещающего загрузчика
Символьные имена
Виртуальные адреса
Физические адреса
Транслятор преобразует идентификаторы в адреса
Перемещающий загрузчик
Динамическое преобразование
Виртуальное адресное пространство
Физическое адресное пространство
Jump #10
Jump #110
#0
#0
#100
Базовый адрес загрузки

88
Методы управления памятью. Существует два основных подхода к реализации процедур управления памятью: с использова- нием дискового пространства и без использования дискового про- странства. Методы фиксированных разделов, динамических разде- лов и перемещаемых разделов не используют дисковое простран- ство. Страничный, сегментный и сегментно-страничный метод ис- пользуют дисковую память. Специальными приемами управления памятью являются свопинг и кэширование.
Реализацию метода фиксированных разделов иллюстрирует рис. 10.3. Перед началом работы оператор разделяет физическую память на разделы заданного размера. Поступающие в систему зада- чи либо занимают свободный раздел подходящего размера, либо попадают в очередь. Очередь может быть общей для всех разделов или индивидуальной для каждого раздела.
Рис. 10.3. Метод фиксированных разделов
Достоинством данного метода является простота реализации.
Вместе с тем, присутствует недостаточная гибкость. Например, уро- вень мультипрограммирования жестко ограничен числом выделен- ных разделов. В современных операционных системах пользователь также может вручную управлять разделами внутри виртуального
Физическое адресное пространство
Раздел
ОС
Раздел 1
Раздел 2
Раздел 3
Раздел 4
Общая очередь задач к разделам
Индивидуальные очере- ди задач к разделам

89 адресного пространства процесса. Пример такого приема описан в лекции 12.
Динамические разделы. При использовании динамических разделов распределение памяти по разделам заранее неизвестно.
Операционная система ведет таблицы занятых и свободных разде- лов. При поступлении новой задачи для ее загрузки выбирается сво- бодный раздел подходящего размера. Возможны разные стратегии выбора свободного раздела: первый по порядку подходящий, наименьший по размеру подходящий, наибольший по размеру под- ходящий раздел.
Рис. 10.4. Метод динамических разделов, возникновение фрагментации
Достоинства способа – это большая гибкость по сравнению с методом фиксированных разделов и отсутствие зависимости уровня мультипрограммирования от начального разбиения на разделы. Не- достатком является эффект фрагментации памяти (рис. 10.4). Он за- ключается в появлении с течением времени большого числа не- больших несмежных сегментов. Суммарный объем свободной памя- ти, содержащийся в таких сегментах, может быть большим, однако малый размер каждого отдельного сегмента не позволяет загрузить
Физическое адресное пространство
ОС
ОС
ОС
ОС

90 программу. Варьирование стратегий выбора свободного раздела может уменьшить фрагментацию. В современных операционных системах такой способ используется для управления кучей (динами- ческой памятью) процесса.
Перемещаемые разделы. Данный способ расширяет управле- ние динамическими разделами путем добавления процедуры сжатия: перемещения занятых разделов в одну последовательную область старших или младших адресов. В результате свободная память раз- мещается в последовательно расположенных ячейках памяти. До- стоинством такой организации является отсутствие фрагментации памяти. Однако в отличие от предыдущих способов нельзя исполь- зовать перемещающий загрузчик. Процедура сжатия может быть затратной по времени. Поэтому обычно сжатие выполняется, когда не удается выполнить загрузку программы или во время простоя си- стемы.
Страничный способ. Мотивом использования дискового ад- ресного пространства является предоставление виртуальной памяти.
Виртуальная память – это совокупность программно-аппаратных средств, позволяющих исполнять программы, размер которых пре- восходит доступную оперативную память компьютера. Для при- кладного программиста механизм виртуальной памяти является про- зрачным. То есть он не требует от него дополнительных усилий по управлению памятью.
При страничной организации памяти виртуальное простран- ство процессов делится на страницы равного размера. Размер стра- ницы кратен степени двойки. Физическое адресное пространство делится на страницы такого же размера. Схема организации стра- ничной памяти показана на рис.10.5.
Страницы процесса при таком разбиении размещаются в фи- зическом адресном пространстве произвольным образом, необяза- тельно по непрерывным адресам. Часть адресного пространства процесса может быть выгружена во внешнюю память.

91
Рис. 10.5. Схема страничной организации памяти
Рис. 10.6. Схема преобразования адреса при страничной организации памяти
Обращение к памяти выполняется по следующей схеме. В слу- чае если виртуальная страница присутствует в физической памяти, старшие биты виртуального адреса (Р) содержат номер виртуальной страницы. По таблице страниц устанавливается соответствующий адрес физической страницы. Он конкатенируется с младшими k раз-
Виртуальные адресные пространства процессов
Страница 11
Страница12
Страница13
Страница 21
Страница22
Страница23
Физическое адресное пространство
Страница 13
Страница 22
Страница 11
Таблицы страниц процессов
11 12
ВП
13 21
ВП
22 23
ВП
Таблица активного процесса
ВП
Номер виртуальной страницы P
Смещение S
Таблица страниц процесса
P
Номер физической страницы P’
Номер физической страницы P’
Смещение S
k

92 рядами виртуального адреса. Получается физический адрес. Схема преобразования виртуального адреса в физический адрес показана на рис.10.6.
В случае если виртуальный адрес отсутствует в физической памяти (клетка ВП, содержимое располагается во внешней памяти), происходит страничное прерывание. Процесс переходит к ожида- нию на системном объекте ядра, запускается процедура загрузки страниц, а контекст переключается на следующий готовый процесс.
Для загрузки страниц определяется место в физической памя- ти. Если оно есть, то выполняется загрузка, коррекция таблицы страниц, перевод процесса в готовое состояние. В противном случае выбирается страница для вытеснения. Если страница была модифи- цирована, то предварительно необходимо записать страницу на диск, иначе содержание страницы переписывается загружаемой страницей. Кандидаты на выгрузку определяются управляющей ин- формацией операционной системы.
Сегментный способ. При страничном распределении памяти адресное пространство делится механически на страницы равного размера. При сегментном распределении памяти размеры сегментов произвольны, сегменты снабжены атрибутами, определяющими способ их использования. Разделение программы на сегменты опре- деляется программистом или компилятором. Атрибуты сегмента определяют способ его использования: для исполнения, чтения, за- писи. Также сегментное распределение позволяет разделять сегмен- ты между процессами.
В таблице сегментов указывается базовый адрес сегмента в физической памяти, а не номер, как в случае страничного способа.
Размер сегмента не фиксирован, в отличие от страничного способа адресации. Он хранится в таблице сегментов и используется для контроля выхода за границы сегмента. Из-за разницы в размерах сегментов, как и в случае с динамическими разделами, для сегмент- ного способа управления памятью характерно явление фрагмента- ции памяти.
Сегментно-страничный способ. Цель сегментно-страничной организации памяти: решить проблему фрагментации физической памяти, сохраняя преимущество сегментного распределения, кото- рое заключается в осмысленном распределении памяти.

93
Рис. 10.7. Схема преобразования адреса при сегментно-страничной организации памяти
При сегментно-страничной организации виртуальный адрес состоит из 3 частей: номера сегмента g, номера страницы в сегменте p и смещения внутри страницы S. Номер сегмента преобразуется с использованием таблицы сегментов, а номер страницы – с использо- ванием таблицы страниц (рис.10.7). В результате линейный физиче- ский адрес состоит из 2 частей: номера физической страницы n и смещения S.
Свопинг. Виртуализация памяти в ранних операционных си- стемах осуществлялась на основе свопинга. Свопинг (swapping) – способ управления памятью, при котором образы процессов выгру- жаются на диск и возвращаются в оперативную память целиком.
Свопинг представляет собой частный, более простой в реализации, вариант виртуальной памяти, позволяющий совместно использовать оперативную память и диск.
Цель применения свопинга в ранних многозадачных операци- онных системах иллюстрирует рис.10.8. Если на компьютере одно- временно выполняется большое число вычислительных задач и за- дач с интенсивным вводом/выводом, то удается добиться высокой эффективности использования центрального процессора. Это проис- ходит за счет того, что в такой конфигурации на время выполнения ввода/вывода одной задачи процессор можно переключить на дру-
Номер виртуальной страницы P
Смещение S
Номер сегмента G
Таблица сегментов
Таблица страниц
G
Таблица страниц сегмента
P
Номер физической страницы P’
Смещение S
Номер физической страницы P’

94 гую задачу. Так как положение участка насыщения на графике эф- фективности (рис.10.8) обычно находилось за пределами числа за- дач, которое можно было разместить в оперативной памяти, ожида- ющие завершения ввода/вывода задачи было целесообразно сбрасы- вать на диск.
Рис. 10.8. Повышение загрузки процессора при использовании свопинга
Кэш-память – способ организации совместной работы устройств хранения, различающихся стоимостью хранения единицы информации и скоростью доступа (рис.10.9). Цель применения кэш- памяти: увеличить скорость доступа и понизить стоимость хранения за счет размещения часто используемой информации в более быст- ром запоминающем устройстве. Механизм кэша, аналогично стра- ничному и сегментному способам управления памятью, прозрачен для пользователя.
Принцип работы кэша оперативной памяти заключается в сле- дующем (рис.10.10). Кэш одновременно с памятью «прослушивает» запрос центрального процессора, но если данные есть в самом кэше ответить успевает быстрее. Хранение информации в кэш-памяти ор- ганизуется по ассоциативному принципу. Ключом для доступа (те- гом) является адрес нескольких последовательно расположенных
100 %
Загрузка процессора
Число задач
С учетом свопинга
Только в ОЗУ

95
Рис. 10.9. К определению кэш-памяти ячеек. Последствия такой организации памяти для программиста: память разбивается на кэш-линии (несколько последовательных яче- ек, адресуемых одним тегом). Это приводит к тому, что в некоторых случаях для оптимизации скорости работы программ необходимо выполнять выравнивание данных по границе кэш-линии. Такая необходимость возникает, например, в случае возникновения эф- фекта ложного разделения (см. лекцию 7).
Рис. 10.10. Принцип работы кэш-памяти
Работа кэша основана на принципах пространственной и вре- менной локальности, обеспечивающих высокий процент «попада- ния» в кэш p. Это приводит к снижению среднего времени доступа к памяти: t доступа
=p·t кэш
+ (1-p)·t памяти
; p90%.
Кэш
Кэш
ВЗУ
ОЗУ
Регистры
Стоимость хранения
Скорость доступа
Тег (адрес)
Данные
Атрибуты
ЦП
Кэш
Память
«Медленный» ответ
«Быстрый» ответ
Адресная шина

96
Пространственная локальность – если в некоторый момент времени t происходит обращение по адресу A , то с большой долей вероятности в момент времени t+1 происходит обращение по адресу
А±1.
Временная локальность – если в некоторый момент времени t произошло обращение по адресу A, то существует большая вероят- ность того, что в течение некоторого временного интервала (t, t+τ] снова произойдет обращение по адресу А.
Лекция 11. Средства аппаратной поддержки
управления памятью в архитектуре x86_32
Режимы работы микропроцессора x86_32. Сегментный механизм, структуры данных, схема преобразования виртуального адреса.
Страничный механизм, структуры данных, схемы преобразования адреса. Средства вызова подпрограмм и задач.
Режимы работы микропроцессора i386. Общие принципы управления памятью с использованием внешней памяти представ- лены в лекции 10. Рассмотрим конкретный пример управления па- мятью в 32-разрядной архитектуре микропроцессоров семейства
Intel x86. Изложение ведется на примере микропроцессора i386.
Старшие модели 32 разрядных процессоров Intel имеют сходную архитектуру.
Микропроцессор i386 имеет два режима работы: реальный (re- al mode) и защищенный (protected mode). В защищенном режиме доступны сегментный и страничный механизмы виртуальной памя- ти. В реальном режиме процессор работает как 16-разрядный про- цессор 8086, но с расширенным набором команд. Размер адресуемо- го пространства в данном режиме составляет 1 Мб. Для работы в адресном пространстве 1Мб надо сформировать адрес определен- ным образом, как показано на рис. 11.1.

97
Рис. 11.1. Формирование адреса в реальном режиме
Реальный режим устанавливается по сбросу и используется для начальной инициализации системы. Путем записи управляющих битов в регистры командой MOV процессор переводится в защи- щенный режим. В защищенном режиме всегда включен сегментный механизм и может быть установлен режим v86 (virtual 86), при кото- ром процессор работает как несколько процессоров 8086 с общей памятью. Кроме того, в защищенном режиме может быть включен режим страничной адресации.
Сегментный механизм. В сегментном механизме управления памятью используются следующие структуры данных. Селектор – это структура данных, которая служит для выбора записи в глобаль- ной или локальной дескрипторной таблице (рис.11.2). Селекторы хранятся в сегментных регистрах и в некоторых типах записей внут- ри самих дескрипторных таблиц. Дескрипторные таблицы – это ана- лог таблицы сегментов (см. лекцию 10). Однако на практике кроме описания сегментов в них содержится дополнительная информация.
Рис. 11.2. Селектор
GDT – глобальная дескрипторная таблица
LDT – локальная дескрипторная таблица

98
Регистр GDTR описывает положение глобальной дескриптор- ной таблицы в физической памяти (рис.11.3). В нем также указыва- ется размер таблицы в байтах. Поскольку в сегментном регистре на указание индекса дескриптора сегмента отводится 13 бит, всего сег- ментов 2 13
= 8192.
Рис. 11.3. Регистр GDTR
Формат дескриптора сегмента данных и кода показан на рис.11.4.
Размер дескриптора 8 байт; с учетом 8192 возможных сегментов размер дескрипторной таблицы составит 8·8192 = 2 16
= 64 Кб. Бит G определяет способ изменения размера сегмента (в байтах – G=0, или в страницах – G=1). Если G=0, то размер сегмента 2 20
= 1 Мб (совме- стимость с 8086, используется в режиме v86). Если G=1, то при 4Кб страницах, 4Кб·2 20
= 4 Гб.
Рис. 11.4. Дескриптор сегмента данных и кода
16
База GDT в физи- ческой памяти
Размер (в байтах)
32

99
Бит D определяет выравнивание сегментов по 32-битной (D=1) или 16-битной границе (D=0).
Бит P – бит присутствия сегмента в физической памяти. Если он не установлен, то сегмент выгружен на диск. Обращение к сег- менту невозможно и приводит к прерыванию.
Биты DPL определяют уровень привилегий дескриптора, то есть возможность обращения к сегменту с данным уровнем приви- легий задачи. Если CPL≤DPL – доступ разрешен, иначе возникает прерывание.
Тип сегментов определяет бит S. Если S=0, то данный де- скриптор описывает системный сегмент или имеет специальное назначение. К системным сегментам, например, относятся LDT – локальная дескрипторная таблица, TSS – сегмент состояния задачи, в который отображается содержимое контекста при переключении задач. Дескрипторы специального назначения – ловушки (шлюзы) вызова, предназначенные для межсегментного вызова с повышени- ем уровня привилегий.
Пользовательские сегменты имеют бит S=1. К пользователь- ским сегментам относятся сегменты данных E=0 и сегменты кода
Е=1. В пользовательских сегментах имеются следующие управляю- щие биты. Бит ED – бит распространения сегмента. Если ED=0 сег- мент распространяется в сторону старших адресов, если ED=1 – в сторону младших адресов. В сторону младших адресов распростра- няются сегменты стека. Бит W – бит разрешения записи в сегмент.
Бит А – бит доступа к сегменту. Если А=1 – произошел доступ к сегменту. Анализ этого бита позволяет оценить интенсивность об- ращений к сегменту для выбора наименее используемого сегмента с целью вытеснения его на диск. Бит С – бит подчинения. Если C=1, то проверка CPL≤DPL игнорируется и можно вызвать более приви- легированный сегмент кода, чем тот сегмент кода, из которого вы- полняется вызов. Наконец, бит R используется для указания на воз- можность чтения кодового сегмента.

100
Рис. 11.5. Схема обращения к сегментам кода и данных
Рассмотрим схему обращения к сегментам кода и данных при использовании глобальных и локальных дескрипторных таб- лиц (рис. 11.5). Если используется адресация из таблицы GDT, то индекс сдвигается влево на 3 разряда, так как дескриптор имеет размер 8 б = 2 3
. Получается смещение в таблице GDT. Далее прове- ряется, не выходит ли смещение за границы таблицы. Для этого ана- лизируются младшие 16 разрядов GDTR, хранящих ее размер. Далее берется 32-битный адрес GDT и складывается с этим смещением. В итоге получается 32-битный адрес дескриптора в физической памя- ти. При этом определяется, присутствует ли сегмент в физической памяти и разрешен ли доступ к нему. Если доступ разрешен, то бе- рется базовый адрес сегмента из дескриптора (база) и складывается со смещением из команды. Также на этой стадии производится кон- троль выхода за границу сегмента. Результатом является 32-битный адрес в физической памяти.
Если обращение идет через локальную дескрипторную табли- цу LDT (см. соответствующий признак в селекторе), то используется

101 регистр LDTR, который указывает на дескриптор LDT в глобальной дескрипторной таблице GDT. С использованием этого дескриптора вычисляется базовый адрес LDT в физической памяти. Далее преоб- разование происходит аналогичным способом.
Для увеличения скорости преобразования адреса каждому из шести сегментных регистров соответствует теневой 8-байтный ре- гистр, хранящий дескриптор, соответствующий значению сегмент- ного регистра.
Таким образом, для инициализации системы в защищенном режиме необходимо как минимум создать дескрипторную таблицу с одним входом и проинициализировать GDTR.
Если включен страничный механизм, то вычисленный 32- битный адрес подвергается дальнейшему преобразованию блоком управления страничной памятью.

1   2   3   4   5   6   7   8

Страничный механизм. Структура данных, используемая для страничного механизма управления памятью – это дескриптор стра- ниц (рис.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. Структурированная обработка исключений. Файлы, отображаемые в память.

123

1   2   3   4   5   6   7   8