Морис Дж. Бах
Архитектура операционной системы UNIX
ПРЕДИСЛОВИЕ
Впервые система 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. Джон Вейт и персонал издательства Prentice-Hall оказали самую разнообразную помощь в придании книге ее окончательного вида. Последней по списку, но не по величине явилась помощь моей жены, Дебби, оказавшей мне эмоциональную поддержку, без которой я бы не достиг успеха.
ГЛАВА 1. ОБЩИЙ ОБЗОР ОСОБЕННОСТЕЙ СИСТЕМЫ
За время, прошедшее с момента ее появления в 1969 году, система UNIX стала довольно популярной и получила распространение на машинах с различной мощностью обработки, от микропроцессоров до больших ЭВМ, обеспечивая на них общие условия выполнения программ. Система делится на две части. Одну часть составляют программы и сервисные функции, то, что делает операционную среду UNIX такой популярной; эта часть легко доступна пользователям, она
