Файл: Tannenbaum.pdf

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

8. Указатель на имя текущего каталога нового процесса.
9. Указатель на структуру, которая описывает исходное окно экрана.

10. Указатель на структуру, которая возвращает 18 значений вызывающей про-

цедуре.

В NT нет никакой иерархии типа порождающий—порожденный. Все процессы

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

Каждый процесс в NT создается с одним потоком, но позднее этот процесс может

создать еще несколько потоков. Создание потока проще, чем создание процесса, по-
скольку

 CreateThread

 имеет всего 6 параметров вместо 10: дескриптор защиты, раз-

мер стека, начальный адрес, определяемый пользователем параметр, начальное

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

Создание потоков производится ядром (то есть потоки реализуются не в пользо-

вательском пространстве, как в некоторых других системах).

Когда ядро совершает распределение, оно вызывает не только процесс, кото-

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

Создавать потоки в NT довольно расточительно, поскольку для создания пото-

ка требуется войти в ядро, а затем выйти из него. Чтобы избежать этого, в NT пре-
дусмотрены

 нити

 (fibers), которые похожи на потоки, но распределяются в пользо-

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

Процессы могут взаимодействовать друг с другом разными способами: через

каналы, именованные каналы, почтовые ящики, сокеты (sockets), удаленные вызо-
вы процедур и общие файлы. Каналы бывают двух видов: байтовые каналы и кана-
лы сообщений. Тип выбирается во время создания. Байтовые каналы работают так
же, как в системе UNIX. Каналы сообщений сохраняют границы сообщений, поэто-
му четыре записи по 128 байтов будут прочитаны как четыре сообщения по 128 бай-
тов (а не как одно сообщение на 512 байтов, как в случае с байтовыми каналами).
Кроме того, существуют именованные каналы, которые тоже бывают двух видов.
Именованные каналы могут использоваться в сети, а обычные каналы — нет.

Примеры операционных систем 509

Почтовые ящики

 есть только в NT (в системе UNIX их нет).

 Они

 во многом

похожи на каналы, хотя не во всем. Во-первых, они односторонние, а каналы —

двусторонние. Их можно использовать в сети, но они не гарантируют доставку.

Наконец, они позволяют отправлять сообщение нескольким получателям, а не только
одному.

Сокеты похожи на каналы, но они обычно связывают процессы на разных маши-

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

Удаленные вызовы процедур позволяют процессу А приказать процессу В со-

вершить вызов процедуры в адресном пространстве В от имени А и возвратить
результат процессу А. Здесь существуют различные ограничения на параметры.
Например, не имеет никакого смысла передача указателя другому процессу.

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

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

NT предоставляет множество механизмов синхронизации (семафоры, мьютек-

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

Семафор создается с помощью функции API

 CreateSemaphore,

 которая может

установить его на определенное значение и определить его максимальное значе-
ние. Семафоры являются объектами ядра, поэтому они имеют дескрипторы за-
щиты и идентификаторы (handles). Идентификатор для семафора может дуб-
лироваться с помощью

 DuplicateHandle

 и передаваться другому процессу, поэтому

на одном семафоре можно синхронизировать несколько процессов. Присутству-
ют функции

 up

 и

 down,

 хотя они имеют особые названия:

 ReleaseSemaphore (up)

и

 WaitForSingleObject (down).

 Можно определить для функции

 WaitForSingleObject

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

Мьютексы тоже являются объектами ядра, но они проще семафоров, посколь-

ку у них нет счетчиков. Они, по сути, представляют собой объекты с функциями
API для блокирования

 (WaitForSingleObject)

 и разблокирования

 (ReleaseMutex).

Идентификаторы мьютексов, как и идентификаторы семафоров, можно дублиро-
вать и передавать другим процессам, так что потоки из разных процессов могут
иметь доступ к одному и тому же мьютексу.

Третий механизм синхронизации основан на

 критических секциях,

 которые

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

 EnterCriticalSection

 и

 Leave CriticalSection

 соответственно. Так как эти фун-

кции API выполняются целиком в пользовательском пространстве, они работают
гораздо быстрее, чем мьютексы.

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

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

ются

 событиями.

 Если потоку нужно дождаться какого-то события, он вызывает

WaitForSingleObject.

 Можно разблокировать один ожидающий поток с помощью

SetEvent

 или все ожидающие потоки с помощью

 PulseEvent.

 Существует несколько

видов событий, которые имеют несколько опций.

События, мьютексы и семафоры можно назвать определенным образом и хра-

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

Краткое содержание главы

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

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

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

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

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

ничную организацию.

Самой важной абстракцией ввода-вывода на этом уровне является файл. Файл

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

В системах часто поддерживается параллельная обработка. Для этого путем

разделения времени в одном процессоре моделируется несколько процессов.

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

UNIX и NT являются сложными операционными системами. Обе системы под-

держивают страничную организацию памяти и отображаемые в память файлы.

Вопросы и задания 511

Кроме того, они поддерживают иерархические системы файлов, в которых файлы

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

Вопросы и задания

1. Почему операционная система интепретирует только некоторые команды

третьего уровня, тогда как микропрограмма интерпретирует все команды
этого уровня (уровня архитектуры команд)?

2. Машина содержит 32-битное виртуальное адресное пространство с побай-

товой адресацией. Размер страницы составляет 8 Кбайт. Сколько существу-
ет страниц виртуального адресного пространства?

3. Виртуальная память содержит 8 виртуальных страниц и 4 физических стра-

ничных кадра. Размер страницы составляет 1024 слова. Ниже приведена таб-

лица страниц:

Виртуальная страница Страничный кадр

0

 3

1 1

2 Нет в основной памяти
3 Нет в основной памяти
4 2
5 Нет в основной памяти
6 О
7 Нет в основной памяти

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

зывать ошибку из-за отсутствия страницы.

2. Каковы физические адреса для 0, 3728, 1023, 1024,1025, 7800 и 4096?

4. Компьютер имеет 16 страниц виртуального адресного пространства и толь-

ко 4 страничных кадра. Изначально память пуста. Программа обращается
к виртуальным страницам в следующем порядке:
0,7,2,7,5,8,9,2,4
а. Какие из обращений вызовут ошибку с алгоритмом LRU?
б. Какие из обращений вызовут ошибку с алгоритмом FIFO?

5. В разделе «Политика замещения страниц» был предложен алогоритм за-

мещения страниц FIFO. Разработайте более эффективный алгоритм.

 Под-

сказка:

 можно обновлять счетчик во вновь загружаемой странице, оставляя

все другие.

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

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

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

занимает некоторые страницы и может быть удален при определенных обсто-

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

7. Не все компьютеры содержат специальный бит, который автоматически

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

какие страницы изменялись, а какие — нет?

8. Сегментированная память содержит страничные сегменты. Каждый вирту-

альный адрес содержит 2-битный номер сегмента, 2-битный номер страни-
цы и 11-битное смещение внутри страницы. Основная память содержит
32 Кбайт, которые разделены на страницы по 2 Кбайт. Каждый сегмент раз-
решается либо только читать, либо читать и выполнять, либо читать и запи-
сывать, либо читать, записывать и выполнять. Таблицы страниц с указани-
ем на защиту приведены ниже:

Сегмент 0

Только для чтения

Вирту-
альная
страница

0

1

2
3

Странич-
ный кадр

9
3

На диске
12

Сегмент 1 Сегмент 2

Чтение/выполнение

Вирту-
альная
страница

0

1
2

3

Странич-
ный кадр

На диске
0

15

8

Сегмент 3

Чтение/запись/
выполнение

Таблицы
страниц нет

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

Чтение/запись

Вирту-
альная
странице

0

1

2
3

Странич-
ный кадр

1

14
1

6
На диске

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

Доступ

1. Вызов данных

2. Вызов данных
3. Вызов данных
4. Сохранение данных
5. Сохранение данных
6. Сохранени данных
7. Переход
8. Вызов данных
9. Вызов данных

10. Переход

Сегмент Страница Смещение внутри страницы

1

1

3

1
1

0
3
2
0
0

1
10

2047
4
2

14
100

50
5
60