Файл: Tannenbaum.pdf

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

так же, как микропрограмма выполняет команду ADD. Однако когда программа вы-
полняет команду уровня архитектуры команд, эта команда выполняется непо-
средственно микроархитектурным уровнем без участия операционной системы.

В этой книге мы можем лишь очень кратко в общих чертах рассказать вам об

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

ввода-вывода. Это понятие более высокого уровня, чем команды ввода-вывода,
которые мы рассматривали в предыдущей главе. Третья особенность — параллель-
ная обработка (как несколько процессов могут выполняться, обмениваться инфор-

мацией и синхронизироваться). Понятие процесса является очень важным, и мы
подробно рассмотрим его ниже в этой главе. Под процессом можно понимать ра-
ботающую программу и всю информацию об ее состоянии (о памяти, регистрах,
счетчике команд, вводе-выводе и т. д.). После обсуждения этих основных характе-
ристик мы покажем, как они применяются к операционным системам двух машин
из трех наших примеров: Pentium II (Windows NT) и UltraSPARC II (UNIX). По-
скольку picojava II обычно используется для встроенных систем, у этой машины
нет операционной системы.

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

В первых компьютерах память была очнь мала по объему и к тому же дорого сто-
ила. IBM-650, ведущий компьютер того времени (конец 50-х годов), содержал все-
го 2000 слов памяти. Один из первых 60 компиляторов, ALGOL, был написан для
компьютера с размером памяти всего 1024 слова. Древняя система с разделением
времени прекрасно работала на компьютере PDP-1, общий размер памяти которо-
го составлял всего 4096 18-битных слов для операционной системы и пользова-

тельских программ. В те времена программисты тратили очень много времени на
то, чтобы впихнуть свои программы в крошечную память. Часто приходилось

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

Традиционным решением этой проблемы было использование вспомогатель-

ной памяти (например, диска). Программист делил программу на несколько час-
тей, так называемых

 оверлеев,

 каждый из которых помещался в память. Чтобы

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

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

Хотя эта технология широко использовалась на протяжении многих лет, она

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

В 1961 году группа исследователей из Манчестера (Англия) предложила метод

автоматического выполнения процесса наложения, при котором программист мог
вообще не знать об этом процессе [42]. Этот метод, который сейчас называется

виртуальной памятью,

 имел очевидное преимущество, поскольку освобождал про-

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

1

 на одной микросхеме, в том числе Pentium II и UltraSPARC II, со-

держат очень сложные системы виртуальной памяти. Мы рассмотрим их ниже
в этой главе.

Страничная организация памяти

Группа ученых из Манчестера выдвинула идею о разделении понятий адресного
пространства и адресов памяти. Рассмотрим в качестве примера типичный компью-
тер того времени с 16-битным полем адреса в командах и 4096 словами памяти.
Программа, работающая на таком компьютере, могла обращаться к 65536 словам
памяти (поскольку адреса были 16-битными, а 2

16

=65536). Обратите внимание,

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

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

 такого

компьютера состоит из чисел 0, 1, 2,..., 65535, так как это набор всех возможных
адресов. Однако в действительности компьютер мог иметь гораздо меньше слов
в памяти.

До изобретения виртуальной памяти приходилось проводить жесткое разли-

чие между теми адресами, которые меньше 4096, и теми, которые равны или боль-
ше 4096. Эти две части рассматривались как полезное адресное пространство и
бесполезное адресное пространство соответственно (адреса выше 4095 были бес-

полезными, поскольку они не соответствовали реальным адресам памяти). Ника-
кого различия между адресным пространством и адресами памяти не проводилось,
поскольку между ними подразумевалось взаимно-однозначное соответствие.

Идея разделения понятий адресного пространства и адресов памяти состоит в сле-

дующем. В любой момент времени можно получить прямой доступ к 4096 словам
памяти, но это не значит, что они непременно должны соответствовать адресам
памяти от 0 до 4095. Например, мы могли бы сообщить компьютеру, что при обра-
щении к адресу 4096 должно использоваться слово из памяти с адресом 0, при обра-

щении к адресу 4097 — слово из памяти с адресом 1, при обращении к адресу

 8191

 —

слово

 из памяти с адресом 4095 и т. д. Другими словами, мы определили отобра-

жение из адресного пространства в действительные адреса памяти (рис. 6.2).

1

 Строго говоря, сверхбольшие интегральные микросхемы, на которых сейчас располагают микропро-

цессоры, в том числе и упоминаемый автором процессор Pentium II, не являются компьютерами. Ком-
пьютер должен содержать помимо процессора память и контроллер управления ею, устройства вво-
да-вывода и соответствующие контроллеры для управления ими. —

 Примеч. научн. ред.

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

Адресное

пространство

Адрес X

8191
4096

0

^Отображение

 4

 К основной

памяти

-4095
-0

Рис. 6.2. Виртуальные адреса памяти с 4096 по 8191 отображаются

в адреса основной памяти с 0 по 4095

Возникает интересный вопрос: а что произойдет, если программа совершит пе-

реход в один из адресов с 8192 по 12287? В машине без виртуальной памяти про-
изойдет ошибка, на экране появится фраза «Несуществующий адрес памяти» и
выполнение программы остановится. В машине с виртуальной памятью будет иметь
место следующая последовательность шагов:

1. Слова с 4096 до 8191 будут размещены на диске.

2. Слова с 8192 до 12287 будут загружены в основную память.
3. Отображение адресов изменится: теперь адреса с 8192 до 12287 соответству-

ют ячейкам памяти с 0 по 4095.

4. Выполнение программы будет продолжаться, как будто ничего ужасного не

случилось.

Такая технология автоматического наложения называется

 страничной органи-

зацией памяти,

 а куски программы, которые считываются с диска, называются

 стра-

ницами.

Возможен и другой, более сложный способ отображения адресов из адресного

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

 виртуальным адресным пространством,

 а реальные

адреса памяти в аппаратном обеспечении —

 физическим адресным пространством.

Схема распределения памяти или таблица страниц соотносит виртуальные адреса
с физическими адресами. Предполагается, что на диске достаточно места для хра-
нения полного виртуального адресного пространства (или, по крайней мере, той
его части, которая используется в данный момент).

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

щения всего виртуального адресного пространства, даже если это не соответствует

действительности. Программы могут загружать слова из виртуального адресного

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

Позднее мы сопоставим страничную организацию памяти с процессом сегмен-

тации, при котором программист должен знать о существовании сегментов. Еще

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

раз подчеркнем, что страничная организация памяти создает иллюзию большой

линейной основной памяти такого же размера, как адресное пространство. В дей-

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

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

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

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

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

Реализация страничной организации памяти

Для виртуальной памяти требуется диск для хранения полной программы и всех
данных. Естественно, при изменении копии должен меняться и оригинал.

Виртуальное адресное пространство разбивается на ряд страниц равного раз-

мера, обычно от 512 до 64 Кбайт, хотя иногда встречается 4 Мбайт. Размер страни-
цы всегда должен быть степенью двойки. Физическое адресное пространство тоже
разбивается на части равного размера таким образом, чтобы каждая такая часть
основной памяти вмещала ровно одну страницу. Эти части основной памяти на-
зываются страничными кадрами. На рисунке 6.2 основная память содержит толь-

ко один страничный кадр. На практике обычно имеется несколько тысяч странич-
ных кадров.

На рисунке 6.3,

 а

 показан один из возможных вариантов разделения первых 64 К

виртуального адресного пространства на страницы по 4 К (отметим, что сейчас мы
говорим о 64 К и 4 К адресов). Адрес может быть байтом, но может быть словом
в компьютере, в котором последовательно расположенные слова имеют последова-
тельные адреса. Виртуальную память, изображенную на рис. 6.3, можно реализо-

вать посредством таблицы страниц, в которой количество элементов равно коли-
честву страниц в виртуальном адресном пространстве. Здесь для простоты мы
показали только первые 16 элементов. Когда программа пытается обратиться к сло-
ву из первых 64 К виртуальной памяти, чтобы вызвать команду или данные или
чтобы сохранить данные, сначала она порождает виртуальный адрес от 0 до 65532

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

4 4 2

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

Страница Виртуальный адрес

15
14
13
12

11

10

9
8
7
6
5
4
3
2

1

0

61440 Р 65535
57344 Р 61439
53248 Р 57343
49152 Р53247

45056 Р49151

40960 Р 45055
36864 Р 40959
32768 Р 36863
28672 Р 32767

24576 Р 28671

20480 Р 24575

16384 Р 20479
12288Р16383

8192 Р12287
4096 Р 8191

0 Р 4095

Нижние 32 К адресов

основной памяти

Страничный Физические

кадр адреса

7
6
5

4
3
2

1

0

28672 Р 32767

24576 Р 28671

20480 Р 24575

16384 Р 20479
12288Р16383

8192 Р12287
4096Р 8191

0 Р 4095

Рис. 6.3. Первые 64 К виртуального адресного пространства разделены на 16 страниц по 4 К

каждая (а); 32 К основной памяти разделены на 8 страничных кадров по 4 К каждый (б)

На рис. 6.3, б изображена физическая память, состоящая из восьми страничных

кадров по 4 К. Эту память можно ограничить до 32 К, поскольку: 1) это вся память
машины (для процессора, встроенного в стиральную машину или микроволновую
печь, этого достаточно), или 2) оставшаяся часть памяти занята другими про-
граммами.

А теперь рассмотрим, как можно 32-битный виртуальный адрес отобразить на

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

устройство называется

 контроллером управления памятью (MMU - Memory

Management Unit).

 Он может находиться на микросхеме процессора или на отдель-

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

Чтобы понять, как работает контроллер управления памятью, рассмотрим при-

мер на рис. 6.4. Когда в контроллер управления памятью поступает 32-битный вир-
туальный адрес, он разделяет этот адрес на 20-битный номер виртуальной страни-
цы и 12-битное смещение внутри этой страницы (поскольку страницы в нашем
примере по 4 К). Номер виртуальной страницы используется в качестве индекса
в таблице страниц для нахождения нужной страницы. На рис. 6.4 номер виртуаль-
ной страницы равен 3, поэтому из таблицы выбирается элемент 3.

Сначала контроллер управления памятью проверяет, находится ли нужная стра-

ница в текущий момент в памяти. Поскольку у нас есть 2

20

 виртуальных страниц и