Страница:
THE DESIGN OF THE UNIX OPERATING SYSTEM by Maurice J. Bach
(Перевод с английского к.т.н. Крюкова А.В.)
Copyright c 1986 Корпорация Bell Telephone Laboratories.
Издано корпорацией Prentice-Hall.
Отделение Simon & Schuster
Энглвуд Клиффс, Нью-Джерси 07632
Серия книг по программному обеспечению издательства Prentice Hall.
Консультант Брайан В. Керниган
Настоящее издание предназначено для распространения в тех
странах, которые получили на это право от корпорации
Prentice-Hall International. Не подлежит вывозу и распространению
в США, Мексике и Канаде.
UNIX - зарегистрированная торговая марка корпорации AT&T.
DEC, PDP и VAX - торговые марки корпорации Digital Equipment
Corp. Series 32000 - торговая марка корпорации National
Semiconductor Corp. Ada - зарегистрированная торговая марка пра-
вительства США (Ada Joint Program Office). UNIVAC - торговая мар-
ка корпорации Sperry Corp.
Настоящий документ набран на фотонаборном устройстве APS-5
корпорации AUTOLOGIC с помощью форматера TROFF в операционной
среде UNIX ЭВМ AT&T 3B20.
В процессе подготовки книги ее автором и издателем было при-
ложено немало усилий. Эти усилия были связаны с проведением тео-
ретических разработок и исследований и с всесторонней проверкой
действенности теоретических выкладок и программ. Автор и издатель
не дают никаких гарантий, как ясно выраженных, так и подразумева-
ющихся, относительно включенных в книгу программ и документации.
Автор и издатель не отвечают за случайные или производные непо-
ладки, возникающие в связи или в результате установки, выполнения
или использования этих программ.
Все права сохраняются. Запрещается воспроизведение отдельных
частей книги без письменного разрешения издателя.
Отпечатано в Соединенных Штатах Америки.
10 9 8 7 6 5
ISBN 0-13-201757-1 025
Prentice-Hall International (UK) Limited, Лондон
Prentice-Hall of Australia Pty. Limited, Сидней
Prentice-Hall Canada Inc., Торонто
Prentice-Hall Hispanoamericana, S.A., Мехико
Prentice-Hall of India Private Limited, Нью-Дели
Prentice-Hall of Japan, Inc., Токио
Prentice-Hall of Southeast Asia Pte. Ltd., Сингапур
Editora Prentice-Hall do Brasil, Ltda., Рио-де-Жанейро
Prentice-Hall, Inc., Энглвуд Клиффс, Нью-Джерси
Впервые система 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, их
можно выполнять под управлением других версий операционной системы.
Большое число упражнений, подготовленных первоначально для курса лекций,
приведено в конце каждой главы, они составляют ключевую часть книги. Отдель-
ные упражнения, иллюстрирующие основные понятия, размещены непосредственно в
тексте книги. Другая часть упражнений отличается большей сложностью, пос-
кольку их предназначение состоит в том, чтобы помочь читателю углубить свое
понимание особенностей системы. И, наконец, часть упражнений является по
3
природе исследовательской, предназначенной для изучения отдельных проблем.
Упражнения повышенной сложности помечены звездочками.
Системное описание базируется на особенностях операционной системы 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,
4
в главе 13 исследуются двухмашинные распределенные вычислительные системы.
Материал, представленный в первых девяти главах, может быть прочитан в
процессе изучения курса "Операционные системы" в течение одного семестра,
материал остальных глав следует изучать на опережающих семинарах с парал-
лельным выполнением практических заданий.
Теперь мне бы хотелось предупредить читателя о следующем. Я не пытался
оценить производительность системы в абсолютном выражении, не касался и па-
раметров конфигурации, необходимых для инсталляции системы. Эти данные меня-
ются в зависимости от типа машины, конфигурации комплекса технических сред-
ств, версии и реализации системы, состава задач. Кроме того, я сознательно
избегал любых предсказаний по поводу дальнейшего развития операционной сис-
темы UNIX. Изложение вопросов, связанных с развитием, не подкреплено обяза-
тельством корпорации AT&T обеспечить соответствующие характеристики, даже не
гарантируется то, что соответствующие области являются объектом исследова-
ния.
Мне приятно выразить благодарность многим друзьям и коллегам за помощь
при написании этой книги и за конструктивные критические замечания, выска-
занные при ознакомлении с рукописью. Я должен выразить глубочайшую призна-
тельность Яну Джонстону, который посоветовал мне написать эту книгу, оказал
мне поддержку на начальном этапе и просмотрел набросок первых глав. Ян отк-
рыл мне многие секреты ремесла и я всегда буду в долгу перед ним. Дорис Ра-
йан также поддерживала меня с самого начала, и я всегда буду ценить ее доб-
роту и внимательность. Дэннис Ричи добровольно ответил на многочисленные
вопросы, касающиеся исторического и технического аспектов системы. Множество
людей пожертвовали своим временем и силами на ознакомление с вариантами ру-
кописи, появление этой книги во многом обязано высказанным ими подробным за-
мечаниям. Среди них Дебби Бэч, Дуг Байер, Лэнни Брэндвейн, Стив Барофф, Том
Батлер, Рон Гомес, Месат Гандак, Лаура Изрейел, Дин Джегелс, Кейт Келлеман,
Брайан Керниган, Боб Мартин, Боб Митц, Дейв Новиц, Майкл Попперс, Мэрилин
Сэфран, Курт Шиммель, Зуи Спитц, Том Вэден, Билл Вебер, Лэрри Вэр и Боб Зэр-
роу. Мэри Фрустак помогала подготовить рукопись к набору. Я хотел бы также
поблагодарить мое руководство за постоянную поддержку, которую я ощущал на
всем протяжении работы,и коллег за атмосферу, способствовавшую мне в работе,
и за замечательные условия, предоставленные фирмой AT&T Bell Laboratories.
Джон Вейт и персонал издательства Prentice-Hall оказали самую разнообразную
помощь в придании книге ее окончательного вида. Последней по списку, но не
по величине явилась помощь моей жены, Дебби, оказавшей мне эмоциональную
поддержку, без которой я бы не достиг успеха.
5
ГЛАВА 1
За время, прошедшее с момента ее появления в 1969 году, система UNIX
стала довольно популярной и получила распространение на машинах с различной
мощностью обработки, от микропроцессоров до больших ЭВМ, обеспечивая на них
общие условия выполнения программ. Система делится на две части. Одну часть
составляют программы и сервисные функции, то, что делает операционную среду
UNIX такой популярной; эта часть легко доступна пользователям, она включает
такие программы, как командный процессор, обмен сообщениями, пакеты обработ-
ки текстов и системы обработки исходных текстов программ. Другая часть вклю-
чает в себя собственно операционную систему, поддерживающую эти программы и
функции. В этой книге дается детальное описание собственно операционной сис-
темы. Основное внимание концентрируется на описании системы UNIX версии V,
распространением которой занимается корпорация AT&T, при этом рассматривают-
ся интересные особенности и других версий. Приводятся основные информацион-
ные структуры и алгоритмы, используемые в операционной системе и в конечном
итоге создающие условия для функционирования стандартного пользовательского
интерфейса.
Данная глава служит введением в систему UNIX. В ней делается обзор исто-
рии ее создания и намечаются контуры общей структуры системы. В следующей
главе содержится более детальная вводная информация по операционной системе.
В 1965 году фирма Bell Telephone Laboratories, объединив свои усилия с
компанией General Electric и проектом MAC Массачусетского технологического
института, приступили к разработке новой операционной системы, получившей
название Multics [Organick 72]. Перед системой Multics были поставлены зада-
чи - обеспечить одновременный доступ к ресурсам ЭВМ большого количества
пользователей, обеспечить достаточную скорость вычислений и хранение данных
и дать возможность пользователям в случае необходимости совместно использо-
вать данные. Многие разработчики, впоследствии принявшие участие в создании
ранних редакций системы UNIX, участвовали в работе над системой Multics в
фирме Bell Laboratories. Хотя первая версия системы Multics и была запущена
в 1969 году на ЭВМ GE 645, она не обеспечивала выполнение главных вычисли-
тельных задач, для решения которых она предназначалась, и не было даже ясно,
когда цели разработки будут достигнуты. Поэтому фирма Bell Laboratories
прекратила свое участие в проекте.
По окончании работы над проектом Multics сотрудники Исследовательского
центра по информатике фирмы Bell Laboratories остались без "достаточно инте-
рактивного вычислительного средства" [Ritchie 84a]. Пытаясь усовершенство-
вать среду программирования, Кен Томпсон, Дэннис Ричи и другие набросали на
бумаге проект файловой системы, получивший позднее дальнейшее развитие в
ранней версии файловой системы UNIX. Томпсоном были написаны программы, ими-
тирующие поведение предложенной файловой системы в режиме подкачки данных по
запросу, им было даже создано простейшее ядро операционной системы для ЭВМ
GE 645. В то же время он написал на Фортране игровую программу "Space
Travel" ("Космическое путешествие") для системы GECOS (Honeywell 635), но
программа не смогла удовлетворить пользователей, поскольку управлять "косми-
ческим кораблем" оказалось сложно, кроме того, при загрузке программа зани-
мала много места. Позже Томпсон обнаружил малоиспользуемый компьютер PDP-7,
оснащенный хорошим графическим дисплеем и имеющий дешевое машинное время.
Создавая программу "Космическое путешествие" для PDP-7, Томпсон получил воз-
можность изучить машину, однако условия разработки программ потребовали ис-
6
пользования кросс-ассемблера для трансляции программы на машине с системой
GECOS и использования перфоленты для ввода в PDP-7. Для того, чтобы улучшить
условия разработки, Томпсон и Ричи выполнили на PDP-7 свой проект системы,
включивший первую версию файловой системы UNIX, подсистему управления про-
цессами и небольшой набор утилит. В конце концов, новая система больше не
нуждалась в поддержке со стороны системы GECOS в качестве операционной среды
разработки и могла поддерживать себя сама. Новая система получила название
UNIX, по сходству с Multics его придумал еще один сотрудник Исследователь-
ского центра по информатике Брайан Керниган.
Несмотря на то, что эта ранняя версия системы UNIX уже была многообещаю-
щей, она не могла реализовать свой потенциал до тех пор, пока не получила
применение в реальном проекте. Так, для того, чтобы обеспечить функциониро-
вание системы обработки текстов для патентного отдела фирмы Bell
Laboratories, в 1971 году система UNIX была перенесена на ЭВМ PDP-11. Систе-
ма отличалась небольшим объемом: 16 Кбайт для системы, 8 Кбайт для программ
пользователей, обслуживала диск объемом 512 Кбайт и отводила под каждый файл
не более 64 Кбайт. После своего первого успеха Томпсон собрался было напи-
сать для новой системы транслятор с Фортрана, но вместо этого занялся языком
Би (B), предшественником которого явился язык BCPL [Richards 69]. Би был ин-
терпретируемым языком со всеми недостатками, присущими подобным языкам, поэ-
тому Ричи переделал его в новую разновидность, получившую название Си (C) и
разрешающую генерировать машинный код, объявлять типы данных и определять
структуру данных. В 1973 году система была написана заново на Си, это был
шаг, неслыханный для того времени, но имевший огромный резонанс среди сто-
ронних пользователей. Количество машин фирмы Bell Laboratories, на которых
была инсталлирована система, возросло до 25, в результате чего была создана
группа по системному сопровождению UNIX внутри фирмы.
В то время корпорация AT&T не могла заниматься продажей компьютерных
продуктов в связи с соответствующим соглашением, подписанным ею с федераль-
ным правительством в 1956 году, и распространяла систему UNIX среди универ-
ситетов, которым она была нужна в учебных целях. Следуя букве соглашения,
корпорация AT&T не рекламировала, не продавала и не сопровождала систему.
Несмотря на это, популярность системы устойчиво росла. В 1974 году Томпсон и
Ричи опубликовали статью, описывающую систему UNIX, в журнале Communications
of the ACM [Thompson 74], что дало еще один импульс к распространению систе-
мы. К 1977 году количество машин, на которых функционировала система UNIX,
увеличилось до 500, при чем 125 из них работали в университетах. Система
UNIX завоевала популярность среди телефонных компаний, поскольку обеспечива-
ла хорошие условия для разработки программ, обслуживала работу в сети в ре-
жиме диалога и работу в реальном масштабе времени (с помощью системы MERT
[Lycklama 78a]). Помимо университетов, лицензии на систему UNIX были переда-
ны коммерческим организациям. В 1977 году корпорация Interactive Systems
стала первой организацией, получившей права на перепродажу системы UNIX с
надбавкой к цене за дополнительные услуги (*), которые заключались в адапта-
ции системы к функционированию в автоматизированных системах управления уч-
режденческой деятельностью. 1977 год также был отмечен "переносом" системы
UNIX на машину, отличную от PDP (благодаря чему стал возможен запуск системы
на другой машине без изменений или с небольшими изменениями), а именно на
Interdata 8/32.
С ростом популярности микропроцессоров другие компании стали переносить
систему UNIX на новые машины, однако ее простота и ясность побудили многих
разработчиков к самостоятельному развитию системы, в результате чего было
---------------------------
(*) Организации, получившие права на перепродажу с надбавкой к цене за до-
полнительные услуги, оснащают вычислительную систему прикладными прог-
раммами, касающимися конкретных областей применения, стремясь удовлет-
ворить требования рынка. Такие организации чаще продают прикладные
программы, нежели операционные системы, под управлением которых эти
программы работают.
7
создано несколько вариантов базисной системы. За период между 1977 и 1982
годом фирма Bell Laboratories объединила несколько вариантов, разработанных
в корпорации AT&T, в один, получивший коммерческое название UNIX версия III.
В дальнейшем фирма Bell Laboratories добавила в версию III несколько новых
особенностей, назвав новый продукт UNIX версия V (**), и эта версия стала
официально распространяться корпорацией AT&T с января 1983 года. В то же
время сотрудники Калифорнийского университета в Бэркли разработали вариант
системы UNIX, получивший название BSD 4.3 для машин серии VAX и отличающийся
некоторыми новыми, интересными особенностями. Основное внимание в этой книге
концентрируется на описании системы UNIX версии V, однако время от времени
мы будем касаться и особенностей системы BSD.
К началу 1984 года система UNIX была уже инсталлирована приблизительно
на 100000 машин по всему миру, при чем на машинах с широким диапазоном вы-
числительных возможностей - от микропроцессоров до больших ЭВМ - и разных
изготовителей. Ни о какой другой операционной системе нельзя было бы сказать
того же. Популярность и успех системы UNIX объяснялись несколькими причина-
ми:
* Система написана на языке высокого уровня, благодаря чему ее легко читать,
понимать, изменять и переносить на другие машины. По оценкам, сделанным
Ричи, первый вариант системы на Си имел на 20-40 % больший объем и работал
медленнее по сравнению с вариантом на ассемблере, однако преимущества ис-
пользования языка высокого уровня намного перевешивают недостатки (см.
[Ritchie 78b], стр. 1965).
* Наличие довольно простого пользовательского интерфейса, в котором имеется
возможность предоставлять все необходимые пользователю услуги.
* Наличие элементарных средств, позволяющих создавать сложные программы из
более простых.
* Наличие иерархической файловой системы, легкой в сопровождении и эффектив-
ной в работе.
* Обеспечение согласования форматов в файлах, работа с последовательным по-
током байтов, благодаря чему облегчается чтение прикладных программ.
* Наличие простого, последовательного интерфейса с периферийными устройства-
ми.
* Система является многопользовательской, многозадачной; каждый пользователь
может одновременно выполнять несколько процессов.
* Архитектура машины скрыта от пользователя, благодаря этому облегчен про-
цесс написания программ, работающих на различных конфигурациях аппаратных
средств.
Простота и последовательность вообще отличают систему UNIX и объясняют
большинство из вышеприведенных доводов в ее пользу.
Хотя операционная система и большинство команд написаны на Си, система
UNIX поддерживает ряд других языков, таких как Фортран, Бейсик, Паскаль,
Ада, Кобол, Лисп и Пролог. Система UNIX может поддерживать любой язык прог-
раммирования, для которого имеется компилятор или интерпретатор, и обеспечи-
вать системный интерфейс, устанавливающий соответствие между пользователь-
скими запросами к операционной системе и набором запросов, принятых в UNIX.
На Рисунке 1.1 изображена архитектура верхнего уровня системы UNIX. Тех-
нические средства, показанные в центре диаграммы, выполняют функции, обеспе-
чивающие функционирование операционной системы и перечисленные в разделе
1.5. Операционная система взаимодействует с аппаратурой непосредственно
---------------------------
(**) А что же версия IV ? Модификация внутреннего варианта системы получила
название "версия V".
8
(***), обеспечивая обслуживание программ и их независимость от деталей аппа-
ратной конфигурации. Если представить систему состоящей из пластов, в ней
можно выделить системное ядро, изолированное от пользовательских
+---------+----------------------------------+
| | Другие прикладные программы |
| +----+-------+--------+-------+----+ |
| | срр| nroff | sh | who | | |
| | +-------+--------+-------+ a. | |
| +----+ Ядро |out | |
| | | +--------------+ | | |
| |coмр| | | +----+ |
| | | | Технические | | | |
| cc +----+ | | |date| |
(Перевод с английского к.т.н. Крюкова А.В.)
Copyright c 1986 Корпорация Bell Telephone Laboratories.
Издано корпорацией Prentice-Hall.
Отделение Simon & Schuster
Энглвуд Клиффс, Нью-Джерси 07632
Серия книг по программному обеспечению издательства Prentice Hall.
Консультант Брайан В. Керниган
Настоящее издание предназначено для распространения в тех
странах, которые получили на это право от корпорации
Prentice-Hall International. Не подлежит вывозу и распространению
в США, Мексике и Канаде.
UNIX - зарегистрированная торговая марка корпорации AT&T.
DEC, PDP и VAX - торговые марки корпорации Digital Equipment
Corp. Series 32000 - торговая марка корпорации National
Semiconductor Corp. Ada - зарегистрированная торговая марка пра-
вительства США (Ada Joint Program Office). UNIVAC - торговая мар-
ка корпорации Sperry Corp.
Настоящий документ набран на фотонаборном устройстве APS-5
корпорации AUTOLOGIC с помощью форматера TROFF в операционной
среде UNIX ЭВМ AT&T 3B20.
В процессе подготовки книги ее автором и издателем было при-
ложено немало усилий. Эти усилия были связаны с проведением тео-
ретических разработок и исследований и с всесторонней проверкой
действенности теоретических выкладок и программ. Автор и издатель
не дают никаких гарантий, как ясно выраженных, так и подразумева-
ющихся, относительно включенных в книгу программ и документации.
Автор и издатель не отвечают за случайные или производные непо-
ладки, возникающие в связи или в результате установки, выполнения
или использования этих программ.
Все права сохраняются. Запрещается воспроизведение отдельных
частей книги без письменного разрешения издателя.
Отпечатано в Соединенных Штатах Америки.
10 9 8 7 6 5
ISBN 0-13-201757-1 025
Prentice-Hall International (UK) Limited, Лондон
Prentice-Hall of Australia Pty. Limited, Сидней
Prentice-Hall Canada Inc., Торонто
Prentice-Hall Hispanoamericana, S.A., Мехико
Prentice-Hall of India Private Limited, Нью-Дели
Prentice-Hall of Japan, Inc., Токио
Prentice-Hall of Southeast Asia Pte. Ltd., Сингапур
Editora Prentice-Hall do Brasil, Ltda., Рио-де-Жанейро
Prentice-Hall, Inc., Энглвуд Клиффс, Нью-Джерси
Впервые система 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, их
можно выполнять под управлением других версий операционной системы.
Большое число упражнений, подготовленных первоначально для курса лекций,
приведено в конце каждой главы, они составляют ключевую часть книги. Отдель-
ные упражнения, иллюстрирующие основные понятия, размещены непосредственно в
тексте книги. Другая часть упражнений отличается большей сложностью, пос-
кольку их предназначение состоит в том, чтобы помочь читателю углубить свое
понимание особенностей системы. И, наконец, часть упражнений является по
3
природе исследовательской, предназначенной для изучения отдельных проблем.
Упражнения повышенной сложности помечены звездочками.
Системное описание базируется на особенностях операционной системы 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,
4
в главе 13 исследуются двухмашинные распределенные вычислительные системы.
Материал, представленный в первых девяти главах, может быть прочитан в
процессе изучения курса "Операционные системы" в течение одного семестра,
материал остальных глав следует изучать на опережающих семинарах с парал-
лельным выполнением практических заданий.
Теперь мне бы хотелось предупредить читателя о следующем. Я не пытался
оценить производительность системы в абсолютном выражении, не касался и па-
раметров конфигурации, необходимых для инсталляции системы. Эти данные меня-
ются в зависимости от типа машины, конфигурации комплекса технических сред-
ств, версии и реализации системы, состава задач. Кроме того, я сознательно
избегал любых предсказаний по поводу дальнейшего развития операционной сис-
темы UNIX. Изложение вопросов, связанных с развитием, не подкреплено обяза-
тельством корпорации AT&T обеспечить соответствующие характеристики, даже не
гарантируется то, что соответствующие области являются объектом исследова-
ния.
Мне приятно выразить благодарность многим друзьям и коллегам за помощь
при написании этой книги и за конструктивные критические замечания, выска-
занные при ознакомлении с рукописью. Я должен выразить глубочайшую призна-
тельность Яну Джонстону, который посоветовал мне написать эту книгу, оказал
мне поддержку на начальном этапе и просмотрел набросок первых глав. Ян отк-
рыл мне многие секреты ремесла и я всегда буду в долгу перед ним. Дорис Ра-
йан также поддерживала меня с самого начала, и я всегда буду ценить ее доб-
роту и внимательность. Дэннис Ричи добровольно ответил на многочисленные
вопросы, касающиеся исторического и технического аспектов системы. Множество
людей пожертвовали своим временем и силами на ознакомление с вариантами ру-
кописи, появление этой книги во многом обязано высказанным ими подробным за-
мечаниям. Среди них Дебби Бэч, Дуг Байер, Лэнни Брэндвейн, Стив Барофф, Том
Батлер, Рон Гомес, Месат Гандак, Лаура Изрейел, Дин Джегелс, Кейт Келлеман,
Брайан Керниган, Боб Мартин, Боб Митц, Дейв Новиц, Майкл Попперс, Мэрилин
Сэфран, Курт Шиммель, Зуи Спитц, Том Вэден, Билл Вебер, Лэрри Вэр и Боб Зэр-
роу. Мэри Фрустак помогала подготовить рукопись к набору. Я хотел бы также
поблагодарить мое руководство за постоянную поддержку, которую я ощущал на
всем протяжении работы,и коллег за атмосферу, способствовавшую мне в работе,
и за замечательные условия, предоставленные фирмой AT&T Bell Laboratories.
Джон Вейт и персонал издательства Prentice-Hall оказали самую разнообразную
помощь в придании книге ее окончательного вида. Последней по списку, но не
по величине явилась помощь моей жены, Дебби, оказавшей мне эмоциональную
поддержку, без которой я бы не достиг успеха.
5
ГЛАВА 1
За время, прошедшее с момента ее появления в 1969 году, система UNIX
стала довольно популярной и получила распространение на машинах с различной
мощностью обработки, от микропроцессоров до больших ЭВМ, обеспечивая на них
общие условия выполнения программ. Система делится на две части. Одну часть
составляют программы и сервисные функции, то, что делает операционную среду
UNIX такой популярной; эта часть легко доступна пользователям, она включает
такие программы, как командный процессор, обмен сообщениями, пакеты обработ-
ки текстов и системы обработки исходных текстов программ. Другая часть вклю-
чает в себя собственно операционную систему, поддерживающую эти программы и
функции. В этой книге дается детальное описание собственно операционной сис-
темы. Основное внимание концентрируется на описании системы UNIX версии V,
распространением которой занимается корпорация AT&T, при этом рассматривают-
ся интересные особенности и других версий. Приводятся основные информацион-
ные структуры и алгоритмы, используемые в операционной системе и в конечном
итоге создающие условия для функционирования стандартного пользовательского
интерфейса.
Данная глава служит введением в систему UNIX. В ней делается обзор исто-
рии ее создания и намечаются контуры общей структуры системы. В следующей
главе содержится более детальная вводная информация по операционной системе.
В 1965 году фирма Bell Telephone Laboratories, объединив свои усилия с
компанией General Electric и проектом MAC Массачусетского технологического
института, приступили к разработке новой операционной системы, получившей
название Multics [Organick 72]. Перед системой Multics были поставлены зада-
чи - обеспечить одновременный доступ к ресурсам ЭВМ большого количества
пользователей, обеспечить достаточную скорость вычислений и хранение данных
и дать возможность пользователям в случае необходимости совместно использо-
вать данные. Многие разработчики, впоследствии принявшие участие в создании
ранних редакций системы UNIX, участвовали в работе над системой Multics в
фирме Bell Laboratories. Хотя первая версия системы Multics и была запущена
в 1969 году на ЭВМ GE 645, она не обеспечивала выполнение главных вычисли-
тельных задач, для решения которых она предназначалась, и не было даже ясно,
когда цели разработки будут достигнуты. Поэтому фирма Bell Laboratories
прекратила свое участие в проекте.
По окончании работы над проектом Multics сотрудники Исследовательского
центра по информатике фирмы Bell Laboratories остались без "достаточно инте-
рактивного вычислительного средства" [Ritchie 84a]. Пытаясь усовершенство-
вать среду программирования, Кен Томпсон, Дэннис Ричи и другие набросали на
бумаге проект файловой системы, получивший позднее дальнейшее развитие в
ранней версии файловой системы UNIX. Томпсоном были написаны программы, ими-
тирующие поведение предложенной файловой системы в режиме подкачки данных по
запросу, им было даже создано простейшее ядро операционной системы для ЭВМ
GE 645. В то же время он написал на Фортране игровую программу "Space
Travel" ("Космическое путешествие") для системы GECOS (Honeywell 635), но
программа не смогла удовлетворить пользователей, поскольку управлять "косми-
ческим кораблем" оказалось сложно, кроме того, при загрузке программа зани-
мала много места. Позже Томпсон обнаружил малоиспользуемый компьютер PDP-7,
оснащенный хорошим графическим дисплеем и имеющий дешевое машинное время.
Создавая программу "Космическое путешествие" для PDP-7, Томпсон получил воз-
можность изучить машину, однако условия разработки программ потребовали ис-
6
пользования кросс-ассемблера для трансляции программы на машине с системой
GECOS и использования перфоленты для ввода в PDP-7. Для того, чтобы улучшить
условия разработки, Томпсон и Ричи выполнили на PDP-7 свой проект системы,
включивший первую версию файловой системы UNIX, подсистему управления про-
цессами и небольшой набор утилит. В конце концов, новая система больше не
нуждалась в поддержке со стороны системы GECOS в качестве операционной среды
разработки и могла поддерживать себя сама. Новая система получила название
UNIX, по сходству с Multics его придумал еще один сотрудник Исследователь-
ского центра по информатике Брайан Керниган.
Несмотря на то, что эта ранняя версия системы UNIX уже была многообещаю-
щей, она не могла реализовать свой потенциал до тех пор, пока не получила
применение в реальном проекте. Так, для того, чтобы обеспечить функциониро-
вание системы обработки текстов для патентного отдела фирмы Bell
Laboratories, в 1971 году система UNIX была перенесена на ЭВМ PDP-11. Систе-
ма отличалась небольшим объемом: 16 Кбайт для системы, 8 Кбайт для программ
пользователей, обслуживала диск объемом 512 Кбайт и отводила под каждый файл
не более 64 Кбайт. После своего первого успеха Томпсон собрался было напи-
сать для новой системы транслятор с Фортрана, но вместо этого занялся языком
Би (B), предшественником которого явился язык BCPL [Richards 69]. Би был ин-
терпретируемым языком со всеми недостатками, присущими подобным языкам, поэ-
тому Ричи переделал его в новую разновидность, получившую название Си (C) и
разрешающую генерировать машинный код, объявлять типы данных и определять
структуру данных. В 1973 году система была написана заново на Си, это был
шаг, неслыханный для того времени, но имевший огромный резонанс среди сто-
ронних пользователей. Количество машин фирмы Bell Laboratories, на которых
была инсталлирована система, возросло до 25, в результате чего была создана
группа по системному сопровождению UNIX внутри фирмы.
В то время корпорация AT&T не могла заниматься продажей компьютерных
продуктов в связи с соответствующим соглашением, подписанным ею с федераль-
ным правительством в 1956 году, и распространяла систему UNIX среди универ-
ситетов, которым она была нужна в учебных целях. Следуя букве соглашения,
корпорация AT&T не рекламировала, не продавала и не сопровождала систему.
Несмотря на это, популярность системы устойчиво росла. В 1974 году Томпсон и
Ричи опубликовали статью, описывающую систему UNIX, в журнале Communications
of the ACM [Thompson 74], что дало еще один импульс к распространению систе-
мы. К 1977 году количество машин, на которых функционировала система UNIX,
увеличилось до 500, при чем 125 из них работали в университетах. Система
UNIX завоевала популярность среди телефонных компаний, поскольку обеспечива-
ла хорошие условия для разработки программ, обслуживала работу в сети в ре-
жиме диалога и работу в реальном масштабе времени (с помощью системы MERT
[Lycklama 78a]). Помимо университетов, лицензии на систему UNIX были переда-
ны коммерческим организациям. В 1977 году корпорация Interactive Systems
стала первой организацией, получившей права на перепродажу системы UNIX с
надбавкой к цене за дополнительные услуги (*), которые заключались в адапта-
ции системы к функционированию в автоматизированных системах управления уч-
режденческой деятельностью. 1977 год также был отмечен "переносом" системы
UNIX на машину, отличную от PDP (благодаря чему стал возможен запуск системы
на другой машине без изменений или с небольшими изменениями), а именно на
Interdata 8/32.
С ростом популярности микропроцессоров другие компании стали переносить
систему UNIX на новые машины, однако ее простота и ясность побудили многих
разработчиков к самостоятельному развитию системы, в результате чего было
---------------------------
(*) Организации, получившие права на перепродажу с надбавкой к цене за до-
полнительные услуги, оснащают вычислительную систему прикладными прог-
раммами, касающимися конкретных областей применения, стремясь удовлет-
ворить требования рынка. Такие организации чаще продают прикладные
программы, нежели операционные системы, под управлением которых эти
программы работают.
7
создано несколько вариантов базисной системы. За период между 1977 и 1982
годом фирма Bell Laboratories объединила несколько вариантов, разработанных
в корпорации AT&T, в один, получивший коммерческое название UNIX версия III.
В дальнейшем фирма Bell Laboratories добавила в версию III несколько новых
особенностей, назвав новый продукт UNIX версия V (**), и эта версия стала
официально распространяться корпорацией AT&T с января 1983 года. В то же
время сотрудники Калифорнийского университета в Бэркли разработали вариант
системы UNIX, получивший название BSD 4.3 для машин серии VAX и отличающийся
некоторыми новыми, интересными особенностями. Основное внимание в этой книге
концентрируется на описании системы UNIX версии V, однако время от времени
мы будем касаться и особенностей системы BSD.
К началу 1984 года система UNIX была уже инсталлирована приблизительно
на 100000 машин по всему миру, при чем на машинах с широким диапазоном вы-
числительных возможностей - от микропроцессоров до больших ЭВМ - и разных
изготовителей. Ни о какой другой операционной системе нельзя было бы сказать
того же. Популярность и успех системы UNIX объяснялись несколькими причина-
ми:
* Система написана на языке высокого уровня, благодаря чему ее легко читать,
понимать, изменять и переносить на другие машины. По оценкам, сделанным
Ричи, первый вариант системы на Си имел на 20-40 % больший объем и работал
медленнее по сравнению с вариантом на ассемблере, однако преимущества ис-
пользования языка высокого уровня намного перевешивают недостатки (см.
[Ritchie 78b], стр. 1965).
* Наличие довольно простого пользовательского интерфейса, в котором имеется
возможность предоставлять все необходимые пользователю услуги.
* Наличие элементарных средств, позволяющих создавать сложные программы из
более простых.
* Наличие иерархической файловой системы, легкой в сопровождении и эффектив-
ной в работе.
* Обеспечение согласования форматов в файлах, работа с последовательным по-
током байтов, благодаря чему облегчается чтение прикладных программ.
* Наличие простого, последовательного интерфейса с периферийными устройства-
ми.
* Система является многопользовательской, многозадачной; каждый пользователь
может одновременно выполнять несколько процессов.
* Архитектура машины скрыта от пользователя, благодаря этому облегчен про-
цесс написания программ, работающих на различных конфигурациях аппаратных
средств.
Простота и последовательность вообще отличают систему UNIX и объясняют
большинство из вышеприведенных доводов в ее пользу.
Хотя операционная система и большинство команд написаны на Си, система
UNIX поддерживает ряд других языков, таких как Фортран, Бейсик, Паскаль,
Ада, Кобол, Лисп и Пролог. Система UNIX может поддерживать любой язык прог-
раммирования, для которого имеется компилятор или интерпретатор, и обеспечи-
вать системный интерфейс, устанавливающий соответствие между пользователь-
скими запросами к операционной системе и набором запросов, принятых в UNIX.
На Рисунке 1.1 изображена архитектура верхнего уровня системы UNIX. Тех-
нические средства, показанные в центре диаграммы, выполняют функции, обеспе-
чивающие функционирование операционной системы и перечисленные в разделе
1.5. Операционная система взаимодействует с аппаратурой непосредственно
---------------------------
(**) А что же версия IV ? Модификация внутреннего варианта системы получила
название "версия V".
8
(***), обеспечивая обслуживание программ и их независимость от деталей аппа-
ратной конфигурации. Если представить систему состоящей из пластов, в ней
можно выделить системное ядро, изолированное от пользовательских
+---------+----------------------------------+
| | Другие прикладные программы |
| +----+-------+--------+-------+----+ |
| | срр| nroff | sh | who | | |
| | +-------+--------+-------+ a. | |
| +----+ Ядро |out | |
| | | +--------------+ | | |
| |coмр| | | +----+ |
| | | | Технические | | | |
| cc +----+ | | |date| |