The design of the unix operating system by Maurice J
| Вид материала | Реферат |
- Лекция 10. Файловые системы Unix, 116.79kb.
- Уровни рассмотрения, 314.07kb.
- Курс по операционным системам (на примере ос windows) Основан на учебном курсе Windows, 29.21kb.
- Выполнил ученик 11 «А» класса, 443.51kb.
- Ос лекция 1 (2-й семестр – временно), 101.4kb.
- Operating System, 7686.97kb.
- Unix-подобные операционные системы, характеристики, особенности, разновидности, 40.63kb.
- 1. ms sql server. Общие сведения, 66.03kb.
- Shanti ananda maurice, 89.84kb.
- Методические материалы, 3002.45kb.
Maurice J. Bach
Архитектура Операционной СИСТЕМЫ UNIX
THE DESIGN OF THE UNIX OPERATING SYSTEM by Maurice J. Bach
(Перевод с английского к.т.н. Крюкова А.В.)
СОДЕРЖАНИЕ
ПРЕДИСЛОВИЕ ............................................... xi
ГЛАВА 1. ОБЩИЙ ОБЗОР ОСОБЕННОСТЕЙ СИСТЕМЫ ................. 1
1.1 ИСТОРИЯ ........................................... 1
1.2 СТРУКТУРА СИСТЕМЫ ................................. 4
1.3 ОБЗОР С ТОЧКИ ЗРЕНИЯ ПОЛЬЗОВАТЕЛЯ ................. 6
1.4 ФУНКЦИИ ОПЕРАЦИОННОЙ СИСТЕМЫ ...................... 14
1.5 ПРЕДПОЛАГАЕМАЯ АППАРАТНАЯ СРЕДА ................... 15
1.6 ВЫВОДЫ ............................................ 18
ГЛАВА 2. ВВЕДЕНИЕ В АРХИТЕКТУРУ ЯДРА ОПЕРАЦИОННОЙ СИСТЕМЫ . 19
2.1 АРХИТЕКТУРА ОПЕРАЦИОННОЙ СИСТЕМЫ UNIX ............. 19
2.2 ВВЕДЕНИЕ В ОСНОВНЫЕ ПОНЯТИЯ СИСТЕМЫ ............... 22
2.3 СТРУКТУРЫ ДАННЫХ ЯДРА ............................. 34
2.4 УПРАВЛЕНИЕ СИСТЕМОЙ ............................... 34
2.5 ВЫВОДЫ И ОБЗОР ПОСЛЕДУЮЩИХ ГЛАВ ................... 36
2.6 УПРАЖНЕНИЯ ........................................ 37
ГЛАВА 3. БУФЕР СВЕРХОПЕРАТИВНОЙ ПАМЯТИ (КЕШ) .............. 38
3.1 ЗАГОЛОВКИ БУФЕРА .................................. 39
3.2 СТРУКТУРА ОБЛАСТИ БУФЕРОВ (БУФЕРНОГО ПУЛА) ........ 40
3.3 МЕХАНИЗМ ПОИСКА БУФЕРА ............................ 42
3.4 ЧТЕНИЕ И ЗАПИСЬ ДИСКОВЫХ БЛОКОВ ................... 53
3.5 ПРЕИМУЩЕСТВА И НЕУДОБСТВА БУФЕРНОГО КЕША .......... 56
3.6 ВЫВОДЫ ............................................ 57
3.7 УПРАЖНЕНИЯ ........................................ 58
ГЛАВА 4. ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ ФАЙЛОВ .................. 60
4.1 ИНДЕКСЫ ........................................... 61
4.2 СТРУКТУРА ФАЙЛА ОБЫЧНОГО ТИПА ..................... 67
4.3 КАТАЛОГИ .......................................... 73
4.4 ПРЕВРАЩЕНИЕ СОСТАВНОГО ИМЕНИ ФАЙЛА (ПУТИ ПОИСКА)
В ИДЕНТИФИКАТОР ИНДЕКСА ........................... 74
4.5 СУПЕРБЛОК ......................................... 76
4.6 НАЗНАЧЕНИЕ ИНДЕКСА НОВОМУ ФАЙЛУ ................... 77
4.7 ВЫДЕЛЕНИЕ ДИСКОВЫХ БЛОКОВ ......................... 84
4.8 ДРУГИЕ ТИПЫ ФАЙЛОВ ................................ 88
4.9 ВЫВОДЫ ............................................ 88
4.10 УПРАЖНЕНИЯ ....................................... 89
ГЛАВА 5. СИСТЕМНЫЕ ОПЕРАЦИИ ДЛЯ РАБОТЫ С ФАЙЛОВОЙ СИСТЕМОЙ 91
5.1 OPEN .............................................. 92
5.2 READ .............................................. 96
5.3 WRITE .............................................101
5.4 ЗАХВАТ ФАЙЛА И ЗАПИСИ .............................103
5.5 УКАЗАНИЕ МЕСТА В ФАЙЛЕ, ГДЕ БУДЕТ ВЫПОЛНЯТЬСЯ
ВВОД-ВЫВОД - LSEEK ................................103
5.6 CLOSE .............................................103
5.7 СОЗДАНИЕ ФАЙЛА ....................................105
5.8 СОЗДАНИЕ СПЕЦИАЛЬНЫХ ФАЙЛОВ .......................107
5.9 СМЕНА ТЕКУЩЕГО И КОРНЕВОГО КАТАЛОГА ...............109
5.10 СМЕНА ВЛАДЕЛЬЦА И РЕЖИМА ДОСТУПА К ФАЙЛУ .........110
5.11 STAT И FSTAT .....................................110
5.12 КАНАЛЫ ...........................................111
5.13 DUP ..............................................117
5.14 МОНТИРОВАНИЕ И ДЕМОНТИРОВАНИЕ ФАЙЛОВЫХ СИСТЕМ ....119
5.15 LINK .............................................128
5.16 UNLINK ...........................................132
5.17 АБСТРАКТНЫЕ ОБРАЩЕНИЯ К ФАЙЛОВЫМ СИСТЕМАМ ........138
5.18 СОПРОВОЖДЕНИЕ ФАЙЛОВОЙ СИСТЕМЫ ...................139
5.19 ВЫВОДЫ ...........................................140
5.20 УПРАЖНЕНИЯ .......................................140
ГЛАВА 6. СТРУКТУРА ПРОЦЕССОВ ..............................146
6.1 СОСТОЯНИЯ ПРОЦЕССА И ПЕРЕХОДЫ МЕЖДУ НИМИ ..........147
6.2 ФОРМАТ ПАМЯТИ СИСТЕМЫ .............................151
6.3 КОНТЕКСТ ПРОЦЕССА .................................159
6.4 СОХРАНЕНИЕ КОНТЕКСТА ПРОЦЕССА .....................162
6.5 УПРАВЛЕНИЕ АДРЕСНЫМ ПРОСТРАНСТВОМ ПРОЦЕССА ........171
6.6 ПРИОСТАНОВКА ВЫПОЛНЕНИЯ ...........................182
6.7 ВЫВОДЫ ............................................188
6.8 УПРАЖНЕНИЯ ........................................189
ГЛАВА 7. УПРАВЛЕНИЕ ПРОЦЕССОМ .............................191
7.1 СОЗДАНИЕ ПРОЦЕССА .................................192
7.2 СИГНАЛЫ ...........................................200
7.3 ЗАВЕРШЕНИЕ ВЫПОЛНЕНИЯ ПРОЦЕССА ....................212
7.4 ОЖИДАНИЕ ЗАВЕРШЕНИЯ ВЫПОЛНЕНИЯ ПРОЦЕССА ...........213
7.5 ВЫЗОВ ДРУГИХ ПРОГРАММ .............................217
7.6 КОД ИДЕНТИФИКАЦИИ ПОЛЬЗОВАТЕЛЯ ПРОЦЕССА ...........227
7.7 ИЗМЕНЕНИЕ РАЗМЕРА ПРОЦЕССА ........................229
7.8 КОМАНДНЫЙ ПРОЦЕССОР SHELL .........................232
7.9 ЗАГРУЗКА СИСТЕМЫ И НАЧАЛЬНЫЙ ПРОЦЕСС ..............235
7.10 ВЫВОДЫ ...........................................238
7.11 УПРАЖНЕНИЯ .......................................239
ГЛАВА 8. ДИСПЕТЧЕРИЗАЦИЯ ПРОЦЕССОВ И ЕЕ ВРЕМЕННЫЕ
ХАРАКТЕРИСТИКИ ...................................247
8.1 ПЛАНИРОВАНИЕ ВЫПОЛНЕНИЯ ПРОЦЕССОВ .................248
8.2 СИСТЕМНЫЕ ОПЕРАЦИИ, СВЯЗАННЫЕ СО ВРЕМЕНЕМ .........258
8.3 ТАЙМЕР ............................................260
8.4 ВЫВОДЫ ............................................268
8.5 УПРАЖНЕНИЯ ........................................268
ГЛАВА 9. АЛГОРИТМЫ УПРАВЛЕНИЯ ПАМЯТЬЮ .....................271
9.1 СВОПИНГ ...........................................272
9.2 ПОДКАЧКА ПО ЗАПРОСУ ...............................285
9.3 СИСТЕМА СМЕШАННОГО ТИПА СО СВОПИНГОМ И ПОДКАЧКОЙ
ПО ЗАПРОСУ ........................................307
9.4 ВЫВОДЫ ............................................307
9.5 УПРАЖНЕНИЯ ........................................308
ГЛАВА 10. ПОДСИСТЕМА УПРАВЛЕНИЯ ВВОДОМ-ВЫВОДОМ ............312
10.1 ВЗАИМОДЕЙСТВИЕ ДРАЙВЕРОВ С ПРОГРАММНОЙ И
АППАРАТНОЙ СРЕДОЙ ................................313
10.2 ДИСКОВЫЕ ДРАЙВЕРЫ ................................325
10.3 ТЕРМИНАЛЬНЫЕ ДРАЙВЕРЫ ............................329
10.4 ПОТОКИ ...........................................344
10.5 ВЫВОДЫ ...........................................351
10.6 УПРАЖНЕНИЯ .......................................352
ГЛАВА 11. ВЗАИМОДЕЙСТВИЕ ПРОЦЕССОВ ........................355
11.1 ТРАССИРОВКА ПРОЦЕССОВ ............................356
11.2 ВЗАИМОДЕЙСТВИЕ ПРОЦЕССОВ В ВЕРСИИ V СИСТЕМЫ ......359
11.3 ВЗАИМОДЕЙСТВИЕ В СЕТИ ............................382
11.4 ГНЕЗДА ...........................................383
11.5 ВЫВОДЫ ...........................................388
11.6 УПРАЖНЕНИЯ .......................................389
ГЛАВА 12. МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ .......................391
12.1 ПРОБЛЕМЫ, СВЯЗАННЫЕ С МНОГОПРОЦЕССОРНЫМИ
СИСТЕМАМИ ........................................392
12.2 ГЛАВНЫЙ И ПОДЧИНЕННЫЙ ПРОЦЕССОРЫ .................393
12.3 СЕМАФОРЫ .........................................395
12.4 СИСТЕМА TUNIS ....................................410
12.5 УЗКИЕ МЕСТА В ФУНКЦИОНИРОВАНИИ МНОГОПРОЦЕССОРНЫХ
СИСТЕМ ...........................................410
12.6 УПРАЖНЕНИЯ .......................................410
ГЛАВА 13. РАСПРЕДЕЛЕННЫЕ СИСТЕМЫ ..........................412
13.1 ПЕРИФЕРИЙНЫЕ ПРОЦЕССОРЫ ..........................414
13.2 СВЯЗЬ ТИПА NEWCASTLE .............................422
13.3 "ПРОЗРАЧНЫЕ" РАСПРЕДЕЛЕННЫЕ ФАЙЛОВЫЕ СИСТЕМЫ .....426
13.4 РАСПРЕДЕЛЕННАЯ МОДЕЛЬ БЕЗ ПЕРЕДАТОЧНЫХ ПРОЦЕССОВ .429
13.5 ВЫВОДЫ ...........................................430
13.6 УПРАЖНЕНИЯ .......................................431
ПРИЛОЖЕНИЕ - СИСТЕМНЫЕ ОПЕРАЦИИ ...........................434
БИБЛИОГРАФИЯ ..............................................454
АЛФАВИТНЫЙ УКАЗАТЕЛЬ ......................................458
ПРЕДИСЛОВИЕ
Впервые система UNIX была описана в 1974 году в статье Кена
Томпсона и Дэнниса Ричи в журнале "Communications of the ACM"
[Thompson 74]. С этого времени она получила широкое распростране-
ние и завоевала широкую популярность среди производителей ЭВМ,
которые все чаще стали оснащать ею свои машины. Особой популяр-
ностью она пользуется в университетах, где довольно часто участ-
вует в исследовательском и учебном процессе.
Множество книг и статей посвящено описанию отдельных частей
системы; среди них два специальных выпуска "Bell System Technical
Journal" за 1978 год [BSTJ 78] и за 1984 год [BSTJ 84]. Во многих
книгах описывается пользовательский интерфейс, в частности ис-
пользование электронной почты, подготовка документации, работа с
командным процессором Shell; в некоторых книгах, таких как "The
UNIX Programming Environment" [Kernighan 84] и "Advanced UNIX
Programming" [Rochkind 85], описывается программный интерфейс.
Настоящая книга посвящена описанию внутренних алгоритмов и струк-
тур, составляющих основу операционной системы (т.н. "ядро"), и
объяснению их взаимосвязи с программным интерфейсом. Таким обра-
зом, она будет полезна для работающих в различных операционных
средах. Во-первых, она может использоваться в качестве учебного
пособия по курсу "Операционные системы" как для студентов послед-
него курса, так и для аспирантов первого года обучения. При рабо-
те с книгой было бы гораздо полезнее обращаться непосредственно к
исходному тексту системных программ, но книгу можно читать и не-
зависимо от него. Во-вторых, эта книга может служить в качестве
справочного руководства для системных программистов, из которого
последние могли бы лучше уяснить себе механизм работы ядра опера-
ционной системы и сравнить между собой алгоритмы, используемые в
UNIX, и алгоритмы, используемые в других операционных системах.
Наконец, программисты, работающие в среде UNIX, могут углубить
свое понимание механизма взаимодействия программ с операционной
системой и посредством этого прийти к написанию более эффективных
и совершенных программ.
Содержание и порядок построения материала в книге соответс-
твуют курсу лекций, подготовленному и прочитанному мной для сот-
рудников фирмы Bell Laboratories, входящей в состав корпорации AT
&T, между 1983 и 1984 гг. Несмотря на то, что главное внимание в
курсе лекций обращалось на исходный текст системных программ, я
обнаружил, что понимание исходного текста облегчается, если поль-
зователь имеет представление о системных алгоритмах. В книге я
пытался изложить описание алгоритмов как можно проще, чтобы и в
малом отразить простоту и изящество рассматриваемой операционной
системы. Таким образом, книга представляет собой не только под-
робное истолкование особенностей системы на английском языке; это
изображение общего механизма работы различных алгоритмов, и что
гораздо важнее, это отражение процесса их взаимодействия между
собой. Алгоритмы представлены на псевдокоде, похожем на язык Си,
поскольку читателю легче воспринимать описание на естественном
языке; наименования алгоритмов соответствуют именам процедур,
составляющих ядро операционной системы. Рисунки описывают взаимо-
действие различных информационных структур под управлением опера-
ционной системы. В последних главах многие системные понятия ил-
люстрируются с помощью небольших программ на языке Си. В целях
экономии места и обеспечения ясности изложения из этих примеров
исключен контроль возникновения ошибок, который обычно предусмат-
ривается при написании программ. Эти примеры прогонялись мною под
управлением версии V; за исключением программ, иллюстрирующих
особенности, присущие версии V, их можно выполнять под управлени-
ем других версий операционной системы.
Большое число упражнений, подготовленных первоначально для
курса лекций, приведено в конце каждой главы, они составляют клю-
чевую часть книги. Отдельные упражнения, иллюстрирующие основные
понятия, размещены непосредственно в тексте книги. Другая часть
упражнений отличается большей сложностью, поскольку их предназна-
чение состоит в том, чтобы помочь читателю углубить свое понима-
ние особенностей системы. И, наконец, часть упражнений является
по природе исследовательской, предназначенной для изучения от-
дельных проблем. Упражнения повышенной сложности помечены звез-
дочками.
Системное описание базируется на особенностях операционной
системы UNIX версия V редакция 2, распространением которой зани-
мается корпорация AT&T, с учетом отдельных особенностей редакции
3. Это та система, с которой я наиболее знаком, однако я поста-
рался отразить и интересные детали других разновидностей операци-
онных систем, в частности систем, распространяемых через
"Berkeley Software Distribution" (BSD). Я не касался вопросов,
связанных с характеристиками отдельных аппаратных средств, стара-
ясь только в общих чертах охватить процесс взаимодействия ядра
операционной системы с аппаратными средствами и игнорируя харак-
терные особенности физической конфигурации. Тем не менее, там,
где вопросы, связанные с машинными особенностями, представились
мне важными с точки зрения понимания механизма функционирования
ядра, оказалось уместным и углубление в детали. По крайней мере,
беглый просмотр затронутых в книге вопросов ясно указывает те
составные части операционной системы, которые являются наиболее
машинно-зависимыми.
Общение с книгой предполагает наличие у читателя опыта прог-
раммирования на одном из языков высокого уровня и желательно на
языке ассемблера. Читателю рекомендуется приобрести опыт работы с
операционной системой UNIX и познакомиться с языком программиро-
вания Си [Kernighan 78]. Тем не менее, я старался изложить мате-
риал в книге таким образом, чтобы читатель смог овладеть им даже
при отсутствии требуемых навыков. В приложении к книге приведено
краткое описание обращений к операционной системе, которого будет
достаточно для того, чтобы получить представление о содержании
книги, но которое не может служить в качестве полного справочного
руководства.
Материал в книге построен следующим образом. Глава 1 служит
введением, содержащим краткое, общее описание системных особен-
ностей с точки зрения пользователя и объясняющим структуру систе-
мы. В главе 2 дается общее представление об архитектуре ядра и
поясняются некоторые основные понятия. В остальной части книги
освещаются вопросы, связанные с общей архитектурой системы и опи-
санием ее различных компонент как блоков единой конструкции. В
ней можно выделить три раздела: файловая система, управление про-
цессами и вопросы, связанные с развитием. Файловая система предс-
тавлена первой, поскольку ее понимание легче по сравнению с уп-
равлением процессами. Так, глава 3 посвящена описанию механизма
функционирования системного буфера сверхоперативной памяти (ке-
ша), составляющего основу файловой системы. Глава 4 описывает ин-
формационные структуры и алгоритмы, используемые файловой систе-
мой. В этих алгоритмах используются методы, объясняемые в главе
3, для ведения внутренней "бухгалтерии", необходимой для управле-
ния пользовательскими файлами. Глава 5 посвящена описанию обраще-
ний к операционной системе, обслуживающих интерфейс пользователя
с файловой системой; для обеспечения доступа к пользовательским
файлам используются алгоритмы главы 4.
Основное внимание в главе 6 уделяется управлению процессами.
В ней определяется понятие контекста процесса и исследуются внут-
ренние составляющие ядра операционной системы, управляющие кон-
текстом процесса. В частности, рассматривается обращение к опера-
ционной системе, обработка прерываний и переключение контекста. В
главе 7 анализируются те системные операции, которые управляют
контекстом процесса. Глава 8 касается планирования процессов,
глава 9 - распределения памяти, включая системы подкачки и заме-
щения страниц.
В главе 10 дается обзор общих особенностей взаимодействия,
которое обеспечивают драйверы устройств, особое внимание уделяет-
ся дисковым и терминальным драйверам. Несмотря на то, что уст-
ройства логически входят в состав файловой системы, их рассмотре-
ние до этого момента откладывалось в связи с возникновением
вопросов, связанных с управлением процессами, при обсуждении тер-
минальных драйверов. Эта глава также служит мостиком к вопросам,
связанным с развитием системы, которые рассматриваются в конце
книги. Глава 11 касается взаимодействия процессов и организации
сетей, в том числе сообщений, используемых в версии V, разделения
памяти, семафоров и пакетов BSD. Глава 12 содержит компактное из-
ложение особенностей двухпроцессорной системы UNIX, в главе 13
исследуются двухмашинные распределенные вычислительные системы.
Материал, представленный в первых девяти главах, может быть
прочитан в процессе изучения курса "Операционные системы" в тече-
ние одного семестра, материал остальных глав следует изучать на
опережающих семинарах с параллельным выполнением практических за-
даний.
Теперь мне бы хотелось предупредить читателя о следующем. Я
не пытался оценить производительность системы в абсолютном выра-
жении, не касался и параметров конфигурации, необходимых для инс-
талляции системы. Эти данные меняются в зависимости от типа маши-
ны, конфигурации комплекса технических средств, версии и
реализации системы, состава задач. Кроме того, я сознательно из-
бегал любых предсказаний по поводу дальнейшего развития операци-
онной системы UNIX. Изложение вопросов, связанных с развитием, не
подкреплено обязательством корпорации AT&T обеспечить соответс-
твующие характеристики, даже не гарантируется то, что соответс-
твующие области являются объектом исследования.
Мне приятно выразить благодарность многим друзьям и коллегам
за помощь при написании этой книги и за конструктивные критичес-
кие замечания, высказанные при ознакомлении с рукописью. Я должен
выразить глубочайшую признательность Яну Джонстону, который посо-
ветовал мне написать эту книгу, оказал мне поддержку на начальном
этапе и просмотрел набросок первых глав. Ян открыл мне многие
секреты ремесла и я всегда буду в долгу перед ним. Дорис Райан
также поддерживала меня с самого начала, и я всегда буду ценить
ее доброту и внимательность. Дэннис Ричи добровольно ответил на
многочисленные вопросы, касающиеся исторического и технического
аспектов системы. Множество людей пожертвовали своим временем и
силами на ознакомление с вариантами рукописи, появление этой кни-
ги во многом обязано высказанным ими подробным замечаниям. Среди
них Дебби Бэч, Дуг Байер, Лэнни Брэндвейн, Стив Барофф, Том Бат-
лер, Рон Гомес, Месат Гандак, Лаура Изрейел, Дин Джегелс, Кейт
Келлеман, Брайан Керниган, Боб Мартин, Боб Митц, Дейв Новиц,
Майкл Попперс, Мэрилин Сэфран, Курт Шиммель, Зуи Спитц, Том Вэ-
ден, Билл Вебер, Лэрри Вэр и Боб Зэрроу. Мэри Фрустак помогала
подготовить рукопись к набору. Я хотел бы также поблагодарить мое
руководство за постоянную поддержку, которую я ощущал на всем
протяжении работы, и коллег за атмосферу, способствовавшую мне
в работе, и за замечательные условия, предоставленные фирмой AT&T
Bell Laboratories. Джон Вейт и персонал издательства