Файл: Tannenbaum.pdf

Виртуальная память

453

уплотнения состоит в том, что на этот процесс тратится некоторое количество вре-
мени. Совершать уплотнение после появления каждой дырки невыгодно.

Сегмент 4

(7К)

Сегмент 3

(8К)

Сегмент 2

(5К)

Сегмент 1

(8К)

Сегмент О

(4К)

Сегмент 4

(7К)

Сегмент 3

(8К)

Сегмент 2

(5К)

'(ЗК)

Сегмент 7

(5К)

Сегмент О

(4К)

Сегмент 5

(4К)

Сегмент 3

(8К)

Сегмент 2

(5К)

(3K)

Сегмент 7

(5К)

Сегмент О

(4К)

у/

Сегмент 5

(4К)

Сегмент 6

(4К)

Сегмент 2

(5К)

Сегмент 7

(5К)

Сегмент О

(4К)

Сегмент 5

(4К)

Сегмент 6

(4К)

Сегмент 2

(5К)

Сегмент 7

(5К)

Сегмент О

(4К)

Рис. 6.8. Динамика внешней фрагментации (а, б,

 в,

 г); удаление

внешней сегментации путем уплотнения (д)

Если на уплотнение памяти требуется слишком много времени, нужен специ-

альный агоритм для определения, какую именно «дырку» лучше использовать для
определенного сегмента. Для этого требуется список адресов и размеров всех «ды-
рок». Популярный алгоритм

 оптимальной подгонки

 выбирает самую маленькую

«дырку», в которую помещается нужный сегмент. Цель этого алгоритма — соотне-

сти «дырки» и сегменты, чтобы избежать «отламывания» куска большой

 «дырки»,

который может понадобиться позже для большого сегмента.

Другой популярный алгоритм по кругу просматривает список «дырок» и выби-

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

 [74].

Оба алгоритма сокращают средний размер «дырки». Всякий раз, когда сегмент

помещается в «дырку», которая больше, чем этот сегмент, что бывает практически
всегда (точные попадания очень редки), «дырка» делится на две части. Одну часть
занимает сегмент, а вторая часть — это новая «дырка». Новая «дырка» всегда меньше,
чем старая. Без воссоздания больших «дырок» из маленьких оба алгоритма в ко-

нечном итоге будут наполнять память маленькими неиспользованными «дырками».

Опишем один из таких процессов. Всякий раз, когда сегмент удаляется из па-

мяти, а одна или обе соседние области этого сегмента — «дырки», а не сегменты,
смежные неиспользованные пространства можно слить в одну большую «дырку».
Если из рис. 6.8,

 г

 удалить сегмент 5, то две соседние «дырки» и 4 К, которые ис-

пользовались данным сегментом, будут слиты в одну «дырку» в 11 К.

4 5 4 Глава 6. Уровень операционной системы

В начале этого раздела мы говорили, что реализовать сегментацию можно дву-

мя способами: подкачкой и разбиением на страницы. До сих пор речь шла о под-
качке. При таком подходе по необходимости между памятью и диском перемеща-
ются целые сегменты.

Второй способ реализации — разделить каждый сегмент на страницы фиксиро-

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

MULTICS (Multiplexed Information and Computing Service — служба общей

информации и вычислений)

 — это древняя операционная система, которая совме-

щала сегментацию с разбиением на страницы. Она была разработана Массачу-
сетским технологическим институтом совместно с компаниями Bell Labs и General

Electric [28, 106]. Адреса в MULTICS состоят из двух частей: номера сегмента и

адреса внутри сегмента. Для каждого процесса существовал сегмент дескриптора,
который содержал дескриптор для каждого сегмента. Когда аппаратное обеспече-
ние получало виртуальный адрес, номер сегмента использовался в качестве ин-
декса в сегмент дескриптора для нахождения дескриптора нужного сегмента
(рис. 6.9). Дескриптор указывал на таблицу страниц, что позволяло разбивать на
страницы каждый сегмент обычным способом. Для повышения производительно-
сти недавно используемые комбинации сегмента и страницы помещались в ассо-
циативную память из 16 элементов. Операционная система MULTICS уже давно
не применяется, но виртуальная память всех процессоров Intel, начиная с 386-го,
очень похожа на эту систему.

10-битное смещение

внутри страницы

18-битный номер сегмента

Адрес системы MULTICS, состоящий из двух частей

Рис. 6.9. Превращение адреса системы MULTICS, состоящего

из двух частей, в адрес основной памяти

Виртуальная память 455

Виртуальная память в процессоре Pentium II

Pentium II имеет сложную систему виртуальной памяти, которая поддерживает
вызов страниц по требованию, чистую сегментацию и сегментацию с разбиением
на страницы. Виртуальная память состоит из двух таблиц:

 LDT (Local Descriptor

Table — локальная таблица дескрипторов)

 и

 GDT (Global Descriptor Table

 —

глобальная таблица дескрипторов).

 Каждая программа имеет свою собственную

локальную таблицу дескрипторов, а единственная глобальная таблица дескрипто-
ров разделяется всеми программами компьютера. Локальная таблица дескрипто-
ров LDT описывает локальные сегменты каждой программы (ее код, данные, стек
и т. д.), а глобальная таблица дескрипторов GDT описывает системные сегменты,
в том числе саму операционную систему.

Как мы уже говорили в главе 5, чтобы получить доступ к сегменту, Pentium II

сначала загружает селектор для сегмента в один из сегментных регистров. Во вре-
мя выполнения программы регистр CS содержит селектор для сегмента кода, DS
содержит селектор для сегмента данных и т. д. Каждый селектор представляет со-
бой 16-битное число (рис. 6.10).

Один из битов селектора показывает, является сегмент локальным или глобаль-

ным (то есть в какой из двух таблиц он находится: в локальной таблице дескрипто-
ров или в глобальной таблице дескрипторов). Еще 13 битов определяют номер эле-
мента в локальной или глобальной таблице дескрипторов, поэтому объем каждой
из этих таблиц ограничен до 8 К (2

13

) сегментных дескрипторов. Оставшиеся два

бита связаны с защитой. Мы опишем их позже.

Биты  1 3  1 2

ИНДЕКС

0 = GDT

1=LDT

Уровень привилегий (0-3)

Рис. 6.10. Селектор в машине Pentium II

Дескриптор 0 недействителен и вызывает ловушку. Его можно загрузить в ре-

гистр сегмента, чтобы показать, что регистр сегмента в данный момент недосту-
пен, но если попытаться использовать дескриптор 0, он вызовет ловушку.

Когда селектор загружается в сегментный регистр, соответствующий дескрип-

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

(рис. 6.11).

Формат селектора был выбран таким образом, чтобы упростить нахождение

дескриптора. Сначала на основе бита 2 в селекторе выбирается локальная таблица
дескрипторов LDT или глобальная таблица дескрипторов GDT. Затем селектор

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

4 5 6 Глава 6. Уровень операционной системы

ров или из глобальной таблицы дескрипторов (который хранится во внутренних
регистрах контроллера управления памятью), и в результате получается указатель
на дескриптор. Например, селектор 72 обращается к элементу 9 в глобальной таб-

лице дескрипторов, который находится в ячейке с адресом GDT+72.

• 32 бита

Относительный

— • - адрес

BASE 0-15

BASE 24-31 G D О

LIMIT 16-19

LIMIT

P DPL

TYPE

BASE 16-23

Тип сегмента и защита

Уровень привилегий (0-3)

0: Сегмент отсутствует в памяти

1: Сегмент присутствует в памяти

0: содержимое поля"

LIMIT в байтах

1: содержимое поля

LIMIT в страницах

0: 16-битный

сегмент

1: 32-битный

сегмент

Рис.  6 . 1 1 . Дескриптор сегмента кода в процессоре Pentium II.

Сегменты данных практически ничем не различаются

Давайте проследим, каким образом пара (селектор, смещение) превращается

в физический адрес. Как только аппаратное обеспечение определяет, какой именно
регистр сегмента используется, оно может найти полный дескриптор, соответ-
ствующий данному селектору во внутренних регистрах. Если такого сегмента не
существует (селектор 0) или в данный момент он не находится в памяти (Р=0),
вызывается системное прерывание (ловушка). В первом случае — это ошибка про-
граммирования; второй случай требует, чтобы операционная система вызвала нуж-
ный сегмент.

Затем аппаратное обеспечение проверяет, не выходит ли смещение за пределы

сегмента. Если выходит, то снова происходит ловушка. По логике вещей в де-
скрипторе должно быть 32-битное поле для определения размера сегмента, но там
в наличии имеется всего 20 битов, поэтому в данном случае используется совер-
шенно другая схема. Если поле G (Granularity — степень детализации) равно 0,
то поле LIMIT дает точный размер сегмента (до 1 Мбайт). Если поле G равно 1,

то поле LIMIT указывает размер сегмента в страницах, а не в байтах. Размер страни-
цы в компьютере Pentium II никогда не бывает меньше 4 Кбайт, поэтому 20 битов
достаточно для сегментов до 2

32

 байтов.

Если сегмент находится в памяти, а смещение не выходит за границу сегмента,

Pentium II прибавляет 32-битное поле BASE в дескрипторе к смещению, в ре-

зультате чего получается

 линейный адрес

 (рис. 6.12). Поле BASE разбивается на

три части и разносится по дескриптору, чтобы обеспечить совместимость с про-
цессором 80286, в котором размер BASE составляет всего 24 бита. Поэтому каж-
дый сегмент может начинаться с произвольного места в 32-битном адресном про-
странстве.

Виртуальная память

457

Селектор

Смещение

Дескриптор

Базовый адрес

Максимальное

значение

Другие поля

32-битный линейный адрес

Рис. 6.12.

 Преобразование пары (селектор, смещение) в линейный адрес

Если разбиение на страницы блокировано (это определяется по биту в регист-

ре глобального управления), линейный адрес интерпретируется как физический
адрес и отправляется в память для чтения или записи. Таким образом, при блоки-
ровке разбиения на страницы мы имеем чистую схему сегментации, где каждый
базовый адрес сегмента дан в его дескрипторе. Допускается перекрытие сегмен-
тов, поскольку было бы слишком утомительно тратить много времени на провер-
ку, чтобы все сегменты были непересекающимися.

С другой стороны, если разбиение на страницы разрешено, линейный адрес ин-

терпретируется как виртуальный адрес и отображается на физический адрес с ис-
пользованием таблиц страниц, почти как в наших примерах. Единственная слож-
ность состоит в том, что при 32-битном виртуальном адресе и страницах на 4 К
сегмент может содержать 1 миллион страниц. Поэтому, чтобы сократить размер таб-
лицы страниц для маленьких сегментов, применяется двухуровневое отображение.

Каждая работающая программа имеет специальную

 таблицу страниц,

 которая

состоит из 1024 32-битных элементов. Ее адрес указывается глобальным регист-
ром. Каждый элемент в этой таблице указывает на таблицу страниц, которая так-
же содержит 1024 32-битных элементов. Элементы таблицы страниц указывают
на страничные кадры. Схема изображена на рис. 6.13.

На рис. 6.13,

 а

 мы видим линейный адрес, разбитый на три поля: DIR, PAGE

и OFF. Поле DIR используется в качестве индекса в директории страниц для
нахождения указателя на нужную таблицу страниц. Поле PAGE используется
в качестве индекса в таблице страниц для нахождения физического адреса странич-
ного кадра. Наконец, поле OFF прибавляется к адресу страничного кадра, и полу-
чается физический адрес нужного байта или слова.

Размер каждого элемента таблицы страниц — 32 бита, 20 из которых содержат

номер страничного кадра. Оставшиеся биты включают бит доступа и бит измене-
ния, которые устанавливаются аппаратным обеспечением для помощи операци-
онной системе, биты защиты и некоторые другие биты.

В каждой таблице страниц содержатся элементы для 1024 страничных кадров

по 4 К каждый, поэтому одна таблица страниц работает с 4 Мбайт памяти. Сегмент
короче 4 Мбайт будет иметь директорию страниц с одним элементом (указателем

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

держки для коротких сегментов составляют всего две страницы, а не миллион стра-

ниц, как было бы в одноуровневой таблице страниц.