Морис Дж. Бах. Архитектура операционной системы Unix

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. В ней делается обзор исто- рии ее создания и намечаются контуры общей структуры системы. В следующей главе содержится более детальная вводная информация по операционной системе.

1.1 ИСТОРИЯ

В 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.2 СТРУКТУРА СИСТЕМЫ

На Рисунке 1.1 изображена архитектура верхнего уровня системы UNIX. Тех- нические средства, показанные в центре диаграммы, выполняют функции, обеспе- чивающие функционирование операционной системы и перечисленные в разделе 1.5. Операционная система взаимодействует с аппаратурой непосредственно

(**) А что же версия IV ? Модификация внутреннего варианта системы получила
название "версия V".
8
(***), обеспечивая обслуживание программ и их независимость от деталей аппа- ратной конфигурации. Если представить систему состоящей из пластов, в ней можно выделить системное ядро, изолированное от пользовательских

+---------+----------------------------------+
| | Другие прикладные программы |
| +----+-------+--------+-------+----+ |
| | срр| nroff | sh | who | | |
| | +-------+--------+-------+ a. | |
| +----+ Ядро |out | |
| | | +--------------+ | | |
| |coмр| | | +----+ |
| | | | Технические | | | |
| cc +----+ | | |date| |
| | | | средства | | | |
| | as | | | +----+ |
| | | +--------------+ | | |
| +----+ | | |
| | +-------+--------+-------+ wc | |
| | ld | vi | ed | grep | | |
| +----+-------+--------+-------+----+ |
| | Другие прикладные программы |
+---------+----------------------------------+

Рисунок 1.1. Архитектура системы UNIX

программ. Поскольку программы не зависят от аппаратуры, их легко переносить из одной системы UNIX в другую, функционирующую на другом комплексе техни- ческих средств, если только в этих программах не подразумевается работа с конкретным оборудованием. Например, программы, расчитанные на определенный размер машинного слова, гораздо труднее переводить на другие машины по срав- нению с программами, не требующими подобных установлений.
Программы, подобные командному процессору shell и редакторам (ed и vi) и показанные на внешнем по отношению к ядру слое, взаимодействуют с ядром при помощи хорошо определенного набора обращений к операционной системе. Обраще- ния к операционной системе понуждают ядро к выполнению различных операций, которых требует вызывающая программа, и обеспечивают обмен данными между яд- ром и программой. Некоторые из программ, приведенных на рисунке, в стандарт- ных конфигурациях системы известны как команды, однако на одном уровне с ни- ми могут располагаться и доступные пользователю программы, такие как прог- рамма a.out, стандартное имя для исполняемого файла, созданного компилятором с языка Си. Другие прикладные программы располагаются выше указанных прог- рамм, на верхнем уровне, как это показано на рисунке. Например, стандартный компилятор с языка Си, cc, располагается на самом внешнем слое: он вызывает препроцессор для Си, ассемблер и загрузчик (компоновщик), т.е. отдельные программы предыдущего уровня. Хотя на рисунке приведена двухуровневая иерар- хия прикладных программ, пользователь может расширить иерархическую структу- ру на столько уровней, сколько необходимо. В самом деле, стиль программиро-

(***) В некоторых реализациях системы UNIX операционная система взаимодейст-
вует с собственной операционной системой, которая, в свою очередь,
взаимодействует с аппаратурой и выполняет необходимые функции по обс-
луживанию системы. В таких реализациях допускается инсталляция других
операционных систем с загрузкой под их управлением прикладных программ
параллельно с системой UNIX. Классическим примером подобной реализации
явилась система MERT [Lycklama 78a]. Более новым примером могут слу-
жить реализации для компьютеров серии IBM 370 [Felton 84] и UNIVAC
1100 [Bodenstab 84].
9
вания, принятый в системе UNIX, допускает разработку комбинации программ, выполняющих одну и ту же, общую задачу.
Многие прикладные подсистемы и программы, составляющие верхний уровень системы, такие как командный процессор shell, редакторы, SCCS (система обра- ботки исходных текстов программ) и пакеты программ подготовки документации, постепенно становятся синонимом понятия "система UNIX". Однако все они поль- зуются услугами программ нижних уровней и в конечном счете ядра с помощью набора обращений к операционной системе. В версии V принято 64 типа обраще- ний к операционной системе, из которых немногим меньше половины используются часто. Они имеют несложные параметры, что облегчает их использование, пре- доставляя при этом большие возможности пользователю. Набор обращений к опе- рационной системе вместе с реализующими их внутренними алгоритмами составля- ют "тело" ядра, в связи с чем рассмотрение операционной системы UNIX в этой книге сводится к подробному изучению и анализу обращений к системе и их вза- имодействия между собой. Короче говоря, ядро реализует функции, на которых основывается выполнение всех прикладных программ в системе UNIX, и им же оп- ределяются эти функции. В книге часто употребляются термины "система UNIX", "ядро" или "система", однако при этом имеется ввиду ядро операционной систе- мы UNIX, что и должно вытекать из контекста.

1.3 ОБЗОР С ТОЧКИ ЗРЕНИЯ ПОЛЬЗОВАТЕЛЯ

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

1.3.1 Файловая система

Файловая система UNIX характеризуется:
* иерархической структурой,
* согласованной обработкой массивов данных,
* возможностью создания и удаления файлов,
* динамическим расширением файлов,
* защитой информации в файлах,
* трактовкой периферийных устройств (таких как терминалы и ленточные ус-
тройства) как файлов.
Файловая система организована в виде дерева с одной исходной вершиной, которая называется корнем (записывается: "/"); каждая вершина в древовидной структуре файловой системы, кроме листьев, является каталогом файлов, а фай-

/
+-------------+------------+---------+---------+---------+
| | | | | |
fsl bin etc usr unix dev
+-+-+ +---+---+ | +-+-+ +-+-+
| | | | | | | | | |
mjb maury sh date who passwd src bin tty00 tty01
|
|
cmd
+---+---+
| |
date.c who.c

Рисунок 1.2. Пример древовидной структуры файловой системы

10

лы, соответствующие дочерним вершинам, являются либо каталогами, либо обыч- ными файлами, либо файлами устройств. Имени файла предшествует указание пути поиска, который описывает место расположения файла в иерархической структуре файловой системы. Имя пути поиска состоит из компонент, разделенных между собой наклонной чертой (/); каждая компонента представляет собой набор символов, составляющих имя вершины (файла), которое является уникальным для каталога (предыдущей компоненты), в котором оно со- держится. Полное имя пути поиска начинается с указания наклонной черты и идентифицирует файл (вершину), поиск которого ведется от корневой вершины дерева файловой системы с обходом тех ветвей дерева файлов, которые соответ- ствуют именам отдельных компонент. Так, пути "/etc/passwd", "/bin/who" и "/usr/src/cmd/who.c" указывают на файлы, являющиеся вершинами дерева, изоб- раженного на Рисунке 1.2, а пути "/bin/passwd" и "/usr/ src/date.c" содержат неверный маршрут. Имя пути поиска необязательно должно начинаться с корня, в нем следует указывать маршрут относительно текущего для выполняемого процес- са каталога, при этом предыдущие символы "наклонная черта" в имени пути опускаются. Так, например, если мы находимся в каталоге "/dev", то путь "tty01" указывает файл, полное имя пути поиска для которого "/dev /tty01".
Программы, выполняемые под управлением системы UNIX, не содержат никакой информации относительно внутреннего формата, в котором ядро хранит файлы данных, данные в программах представляются как бесформатный поток байтов. Программы могут интерпретировать поток байтов по своему желанию, при этом любая интерпретация никак не будет связана с фактическим способом хранения данных в операционной системе. Так, синтаксические правила, определяющие за- дание метода доступа к данным в файле, устанавливаются системой и являются едиными для всех программ, однако семантика данных определяется конкретной программой. Например, программа форматирования текста troff ищет в конце каждой строки текста символы перехода на новую строку, а программа учета системных ресурсов acctcom работает с записями фиксированной длины. Обе программы пользуются одними и теми же системными средствами для осуществле- ния доступа к данным в файле как к потоку байтов, и внутри себя преобразуют этот поток по соответствующему формату. Если любая из программ обнаружит, что формат данных неверен, она принимает соответствующие меры.
Каталоги похожи на обычные файлы в одном отношении; система представляет информацию в каталоге набором байтов, но эта информация включает в себя име- на файлов в каталоге в объявленном формате для того, чтобы операционная сис- тема и программы, такие как ls (выводит список имен и атрибутов файлов), могли их обнаружить.
Права доступа к файлу регулируются установкой специальных битов разреше- ния доступа, связанных с файлом. Устанавливая биты разрешения доступа, можно независимо управлять выдачей разрешений на чтение, запись и выполнение для трех категорий пользователей: владельца файла, группового пользователя и прочих. Пользователи могут создавать файлы, если разрешен доступ к каталогу. Вновь созданные файлы становятся листьями в древовидной структуре файловой системы.
Для пользователя система UNIX трактует устройства так, как если бы они были файлами. Устройства, для которых назначены специальные файлы устройств, становятся вершинами в структуре файловой системы. Обращение программ к уст- ройствам имеет тот же самый синтаксис, что и обращение к обычным файлам; се- мантика операций чтения и записи по отношению к устройствам в большой степе- ни совпадает с семантикой операций чтения и записи обычных файлов. Способ защиты устройств совпадает со способом защиты обычных файлов: путем соответ- ствующей установки битов разрешения доступа к ним (файлам). Поскольку имена устройств выглядят так же, как и имена обычных файлов, и поскольку над уст- ройствами и над обычными файлами выполняются одни и те же операции, большин- ству программ нет необходимости различать внутри себя типы обрабатываемых файлов.

11

Например, рассмотрим программу на языке Си (Рисунок 1.3), в которой соз- дается новая копия существующего файла. Предположим, что исполняемая версия программы имеет наименование copy. Для запуска программы пользователь вводит с терминала:

copy oldfile newfile
где oldfile - имя существующего файла, а newfile - имя создаваемого файла. Система выполняет процедуру main, присваивая аргументу argc значение коли- чества параметров в списке argv, а каждому элементу массива argv значение параметра, сообщенного пользователем. В приведенном примере argc имеет зна- чение 3, элемент argv[0] содержит строку символов "copy" (имя программы ус- ловно является нулевым параметром), argv[1] - строку символов "oldfile", а argv[2] - строку символов "newfile". Затем программа проверяет, правильное ли количество параметров было указано при ее запуске. Если это так, запуска- ется операция open (открыть) для файла oldfile с параметром "read-only" (только для чтения), в случае успешного выполнения которой запускается опе- рация creat (открыть) для файла newfile. Режим доступа к вновь созданному файлу описывается числом 0666 (в восьмиричном коде), что означает разрешение доступа к файлу для чтения и записи для всех пользователей. Все обращения к операционной системе в случае неудачи возвращают код -1; если же неудачно завершаются операции open и creat, программа выдает сообщение и запускает операцию exit (выйти) с возвращением кода состояния, равного 1, завершая свою работу и указывая на возникновение ошибки.
Операции open и creat возвращают целое значение, являющееся дескриптором файла и используемое программой в последующих ссылках на файлы. После этого программа вызывает подпрограмму copy, выполняющую в цикле операцию read (чи- тать), по которой производится чтение в буфер порции символов из существую- щего файла, и операцию write (писать) для записи информации в новый файл. Операция read каждый раз возвращает количество прочитанных байтов (0 - если достигнут конец файла). Цикл завершается, если достигнут конец файла или ес- ли произошла ошибка при выполнении операции read (отсутствует контроль воз- никновения ошибок при выполнении операции write). Затем управление из подп- рограммы copy возвращается в основную программу и запускается операция exit с кодом состояния 0 в качестве параметра, что указывает на успешное заверше- ние выполнения программы.

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

copy copy.c newcopy.c
copy copy newcopy
являются допустимыми. Существующий файл также может быть каталогом. Напри- мер, по вызову:

copy . dircontents
копируется содержимое текущего каталога, обозначенного символом ".", в обыч- ный файл "dircontents"; информация в новом файле совпадает, вплоть до каждо- го байта, с содержимым каталога, только этот файл обычного типа (для созда- ния нового каталога предназначена операция mknod). Наконец, любой из файлов может быть файлом устройства. Например, программа, вызванная следующим обра- зом:

12

+------------------------------------------------------------+
| #include |
| char buffer[2048]; |
| int version = 1; /* будет объяснено в главе 2 */ |
| |
| main(argc,argv) |
| int argc; |
| char *argv[]; |
| { |
| int fdold,fdnew; |
| |
| if (argc != 3) |
| { |
| printf("need 2 arguments for copy program\n); |
| exit(1); |
| } |
| fdold = open(argv[1],O_RDONLY); /* открыть исходный |
| файл только для |
| чтения */ |
| if (fdold == -1) |
| { |
| printf("cannot open file %s\n",argv[1]); |
| exit(1); |
| } |
| fdnew = creat(argv[2],0666); /* создать новый файл с |
| разрешением чтения и |
| записи для всех поль-|
| зователей */ |
| if (fdnew == -1) |
| { |
| printf("cannot create file %s\n",argv[2]); |
| exit(1); |
| } |
| copy(fdold,fdnew); |
| exit(0); |
| } |
| |
| copy(old,new) |
| int old,new; |
| { |
| int count; |
| |
| while ((count = read(old,buffer,sizeof(buffer))) > 0) |
| write(new,buffer,count); |
| } |
+------------------------------------------------------------+

Рисунок 1.3. Программа копирования файла

copy /dev/tty terminalread
читает символы, вводимые с терминала (файл /dev/tty соответствует терминалу пользователя), и копирует их в файл terminalread, завершая работу только в том случае, если пользователь нажмет . Похожая форма запуска программы:

copy /dev/tty /dev/tty

13
вызывает чтение символов с терминала и их копирование обратно на терминал.

1.3.2 Среда выполнения процессов

Программой называется исполняемый файл, а процессом называется последо- вательность операций программы или часть программы при ее выполнении. В сис- теме UNIX может одновременно выполняться множество процессов (эту особен- ность иногда называют мультипрограммированием или многозадачным режимом), при чем их число логически не ограничивается, и множество частей программы (такой как copy) может одновременно находиться в системе. Различные систем- ные операции позволяют процессам порождать новые процессы, завершают процес- сы, синхронизируют выполнение этапов процесса и управляют реакцией на нас- тупление различных событий. Благодаря различным обращениям к операционной системе, процессы выполняются независимо друг от друга.
Например, процесс, выполняющийся в программе, приведенной на Рисунке 1.4, запускает операцию fork, чтобы породить новый процесс. Новый процесс, именуемый порожденным процессом, получает значение кода завершения операции fork, равное 0, и активизирует операцию execl, которая выполняет программу copy (Рисунок 1.3). Операция execl загружает файл "copy", который предполо- жительно находится в текущем каталоге, в адресное пространство порожденного процесса и запускает программу с параметрами, полученными от пользователя. В случае успешного выполнения операции execl управление в вызвавший ее процесс не возвращается, поскольку процесс выполняется в новом адресном пространстве (подробнее об этом в главе 7). Тем временем, процесс, запустивший операцию fork (родительский процесс), получает ненулевое значение кода завершения операции, вызывает операцию wait, которая приостанавливает его выполнение до тех пор, пока не закончится выполнение программы copy, и завершается (каждая программа имеет выход в конце главной процедуры, после которой располагаются программы стандартных библиотек Си, подключаемые в процессе компиляции). Например, если исполняемая программа называется run, пользователь запускает ее следующим образом:

+------------------------------------------------------------+
| main(argc,argv) |
| int argc; |
| char *argv[]; |
| { |
| /* предусмотрено 2 аргумента: исходный файл и новый файл */|
| if (fork() == 0) |
| execl("copy","copy",argv[1],argv[2],0); |
| wait((int *)0) |
| printf("copy done\n"); |
| } |
+------------------------------------------------------------+

Рисунок 1.4. Программа порождения нового процесса, выполняющего копиро-
вание файлов

run oldfile newfile
Процесс выполняет копирование файла с именем "oldfile" в файл с именем "newfile" и выводит сообщение. Хотя данная программа мало что добавила к программе "copy", в ней появились четыре основных обращения к операционной системе, управляющие выполнением процессов: fork, exec, wait и exit.
Вообще использование обращений к операционной системе дает возможность пользователю создавать программы, выполняющие сложные действия, и как следс- твие, ядро операционной системы UNIX не включает в себя многие функции, яв-

14
ляющиеся частью "ядра" в других системах. Такие функции, и среди них компи- ляторы и редакторы, в системе UNIX являются программами пользовательского уровня. Наиболее характерным примером подобной программы может служить ко- мандный процессор shell, с которым обычно взаимодействуют пользователи после входа в систему. Shell интерпретирует первое слово командной строки как имя команды: во многих командах, в том числе и в командах fork (породить новый процесс) и exec (выполнить порожденный процесс), сама команда ассоциируется с ее именем, все остальные слова в командной строке трактуются как параметры команды.
Shell обрабатывает команды трех типов. Во-первых, в качестве имени ко- манды может быть указано имя исполняемого файла в объектном коде, полученно- го в результате компиляции исходного текста программы (например, программы на языке Си). Во-вторых, именем команды может быть имя командного файла, со- держащего набор командных строк, обрабатываемых shell'ом. Наконец, команда может быть внутренней командой языка shell (в отличие от исполняемого фай- ла). Наличие внутренних команд делает shell языком программирования в допол- нение к функциям командного процессора; командный язык shell включает коман- ды организации циклов (for-in-do-done и while-do-done), команды выполнения по условиям (if-then-else-fi), оператор выбора, команду изменения текущего для процесса каталога (cd) и некоторые другие. Синтаксис shell'а допускает сравнение с образцом и обработку параметров. Пользователям, запускающим ко- манды, нет необходимости знать, какого типа эти команды.
Командный процессор shell ищет имена команд в указанном наборе катало- гов, который можно изменить по желанию пользователя, вызвав shell. Shell обычно исполняет команду синхронно, с ожиданием завершения выполнения коман- ды прежде, чем считать следующую командную строку. Тем не менее, допускается и асинхронное исполнение, когда очередная командная строка считывается и ис- полняется, не дожидаясь завершения выполнения предыдущей команды. О коман- дах, выполняемых асинхронно, говорят, что они выполняются на фоне других ко- манд. Например, ввод команды

who
вызывает выполнение системой программы, хранящейся в файле /bin/who (****) и осуществляющей вывод списка пользователей, ко- торые в настоящий момент работают с системой. Пока команда who выполняется, командный процессор shell ожидает завершения ее выполнения и только затем запрашивает у пользователя следующую команду. Если же ввести команду

who &
система выполнит программу who на фоне и shell готов немедленно принять сле- дующую команду.
В среду выполнения каждого процесса в системе UNIX включается текущий каталог. Текущий для процесса каталог является начальным каталогом, имя ко- торого присоединяется ко всем именам путей поиска, которые не начинаются с наклонной черты. Пользователь может запустить внутреннюю команду shell'а cd (изменить каталог) для перемещения по дереву файловой системы и для смены текущего каталога. Командная строка

cd /usr/src/uts
делает текущим каталог "/usr/src/uts". Командная строка

cd ../..

(****) Каталог "/bin" содержит большинство необходимых команд и обычно вхо-
дит в число каталогов, в которых ведет поиск командный процессор
shell.
15
делает текущим каталог, который на две вершины "ближе" к корню (корневому каталогу): параметр ".." относится к каталогу, являющемуся родительским для текущего.

Поскольку shell является пользовательской программой и не входит в сос- тав ядра операционной системы, его легко модифицировать и помещать в конк- ретные условия эксплуатации. Например, вместо командного процессора Баурна (называемого так по имени его создателя, Стива Баурна), являющегося частью версии V стандартной системы, можно использовать процессор команд Си, обес- печивающий работу механизма ведения истории изменений и позволяющий избегать повторного ввода только что использованных команд. В некоторых случаях при желании можно воспользоваться командным процессором shell с ограниченными возможностями, являющимся предыдущей версией обычного shell'а. Система может работать с несколькими командными процессорами одновременно. Пользователи имеют возможность запускать одновременно множество процессов, процессы же в свою очередь могут динамически порождать новые процессы и синхронизировать их выполнение. Все эти возможности обеспечиваются благодаря наличию мощных программных и аппаратных средств, составляющих среду выполнения процессов. Хотя привлекательность shell'а в наибольшей степени определяется его возмож- ностями как языка программирования и его возможностями в обработке аргумен- тов, в данном разделе основное внимание концентрируется на среде выполнения процессов, управление которой в системе возложено на командный процессор shell. Другие важные особенности shell'а выходят за рамки настоящей книги (подробное описание shell'а см. в [Bourne 78]).

1.3.3 Элементы конструкционных блоков

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

ls
выводит список всех файлов текущего каталога на устройство (в файл) стандар- тного вывода, а команда

ls > output
переназначает выводной поток со стандартного вывода в файл "output" в теку- щем каталоге, используя вышеупомянутый системный вызов creat. Подобным же образом, команда

mail mjb < letter
открывает (с помощью системного вызова open) файл "letter" в качестве файла стандартного ввода и пересылает его содержимое пользователю с именем "mjb". Процессы могут переназначать одновременно и ввод, и вывод, как, например, в командной строке:

16

nroff -mm < doc1 > doc1.out 2> errors
где программа форматирования nroff читает вводной файл doc1, в качестве фай- ла стандартного вывода задает файл doc1.out и выводит сообщения об ошибках в файл errors ("2>" означает переназначение вывода, предназначавшегося для файла с дескриптором 2, который соответствует стандартному файлу ошибок). Программы ls, mail и nroff не знают, какие файлы выбраны в качестве файлов стандартного ввода, стандартного вывода и записи сообщений об ошибках; ко- мандный процессор shell сам распознает символы "<", ">" и "2>" и назначает в соответствии с их указанием файлы для стандартного ввода, стандартного выво- да и записи сообщений об ошибках непосредственно перед запуском процессов.
Вторым конструкционным элементом является канал, механизм, обеспечиваю- щий информационный обмен между процессами, выполнение которых связано с опе- рациями чтения и записи. Процессы могут переназначать выводной поток со стандартного вывода на канал для чтения с него другими процессами, переназ- начившими на канал свой стандартный ввод. Данные, посылаемые в канал первыми процессами, являются входными для вторых процессов. Вторые процессы так же могут переназначить свой выводной поток и так далее, в зависимости от поже- ланий программиста. И снова, так же как и в вышеуказанном случае, процессам нет необходимости знать, какого типа файл используется в качестве файла стандартного вывода; их выполнение не зависит от того, будет ли файлом стан- дартного вывода обычный файл, канал или устройство. В процессе построения больших и сложных программ из конструкционных элементов меньшего размера программисты часто используют каналы и переназначение ввода-вывода при сбор- ке и соединении отдельных частей. И действительно, такой стиль программиро- вания находит поддержку в системе, благодаря чему новые программы могут ра- ботать вместе с существующими программами.
Например, программа grep производит поиск контекста в наборе файлов (яв- ляющихся параметрами программы) по следующему образцу:

grep main a.c b.c c.c
где "main" - подстрока, поиск которой производится в файлах a.c, b.c и c.c с выдачей в файл стандартного вывода тех строк, в которых она содержится. Со- держимое выводного файла может быть следующим:

a.c: main(argc,argv)
c.c: /* here is the main loop in the program */
c.c: main()
Программа wc с необязательным параметром -l подсчитывает число строк в файле стандартного ввода. Командная строка

grep main a.c b.c c.c | wc -l
вызовет подсчет числа строк в указанных файлах, где будет обнаружена подст- рока "main"; выводной поток команды grep поступит непосредственно на вход команды wc. Для предыдущего примера результат будет такой:
3
Использование каналов зачастую делает ненужным создание временных файлов.

1.4 ФУНКЦИИ ОПЕРАЦИОННОЙ СИСТЕМЫ

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

17
ций ядра можно отметить: * Управление выполнением процессов посредством их создания, завершения или
приостановки и организации взаимодействия между ними. * Планирование очередности предоставления выполняющимся процессам времени
центрального процессора (диспетчеризация). Процессы работают с центральным
процессором в режиме разделения времени: центральный процессор (*****) вы-
полняет процесс, по завершении отсчитываемого ядром кванта времени процесс
приостанавливается и ядро активизирует выполнение другого процесса. Позд-
нее ядро запускает приостановленный процесс. * Выделение выполняемому процессу оперативной памяти. Ядро операционной сис-
темы дает процессам возможность совместно использовать участки адресного
пространства на определенных условиях, защищая при этом адресное простран-
ство, выделенное процессу, от вмешательства извне. Если системе требуется
свободная память, ядро освобождает память, временно выгружая процесс на
внешние
запоминающие устройства, которые называют устройствами выгрузки. Если ядро
выгружает процессы на устройства выгрузки целиком, такая реализация систе-
мы UNIX называется системой со свопингом (подкачкой); если же на устройст-
во выгрузки выводятся страницы памяти, такая система называется системой с
замещением страниц. * Выделение внешней памяти с целью обеспечения эффективного хранения инфор-
мации и выборка данных пользователя. Именно в процессе реализации этой
функции создается файловая система. Ядро выделяет внешнюю память под поль-
зовательские файлы, мобилизует неиспользуемую память, структурирует файло-
вую систему в форме, доступной для понимания, и защищает пользовательские
файлы от несанкционированного доступа. * Управление доступом процессов к периферийным устройствам, таким как терми-
налы, ленточные устройства, дисководы и сетевое оборудование.
Выполнение ядром своих функций довольно очевидно. Например, оно узнает, что данный файл является обычным файлом или устройством, но скрывает это различие от пользовательских процессов. Так же оно, форматируя информацию файла для внутреннего хранения, защищает внутренний формат от пользователь- ских процессов, возвращая им неотформатированный поток байтов. Наконец, ядро реализует ряд необходимых функций по обеспечению выполнения процессов поль- зовательского уровня, за исключением функций, которые могут быть реализованы на самом пользовательском уровне. Например, ядро выполняет действия, необхо- димые shell'у как интерпретатору команд: оно позволяет процессору shell чи- тать вводимые с терминала данные, динамически порождать процессы, синхрони- зировать выполнение процессов, открывать каналы и переадресовывать ввод-вы- вод. Пользователи могут разрабатывать свои версии командного процессора shell с тем, чтобы привести рабочую среду в соответствие со своими требова- ниями, не затрагивая других пользователей. Такие программы пользуются теми же услугами ядра, что и стандартный процессор shell.

1.5 ПРЕДПОЛАГАЕМАЯ АППАРАТНАЯ СРЕДА

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

(*****) В главе 12 рассматриваются многопроцессорные системы; до того речь
будет идти об однопроцессорной модели.

18
система еще выполняет учетные операции, связанные с пользовательским процес- сом, обрабатывает прерывания, планирует процессы, управляет распределением памяти и т.д. Большинство вычислительных систем разнообразной архитектуры (и соответствующие им операционные системы) поддерживают большее число уровней, чем указано здесь, однако уже двух режимов, режима задачи и режима ядра, вполне достаточно для системы UNIX.
Основные различия между этими двумя режимами: * В режиме задачи процессы имеют доступ только к своим собственным инструк-
циям и данным, но не к инструкциям и данным ядра (либо других процессов).
Однако в режиме ядра процессам уже доступны адресные пространства ядра и
пользователей. Например, виртуальное адресное пространство процесса может
быть поделено на адреса, доступные только в режиме ядра, и на адреса, дос-
тупные в любом режиме. * Некоторые машинные команды являются привилегированными и вызывают возник-
новение ошибок при попытке их использования в режиме задачи. Например, в
машинном языке может быть команда, управляющая регистром состояния процес-
сора; процессам, выполняющимся в

Процессы

A B C D
+-------+-------+-------+-------+
Режим ядра | Я | | | Я |
+-------+-------+-------+-------+
Режим задачи | | З | З | |
+-------+-------+-------+-------+

Рисунок 1.5. Процессы и режимы их выполнения

режиме задачи, она недоступна.
Проще говоря, любое взаимодействие с аппаратурой описывается в терминах режима ядра и режима задачи и протекает одинаково для всех пользовательских программ, выполняющихся в этих режимах. Операционная система хранит внутрен- ние записи о каждом процессе, выполняющемся в системе. На Рисунке 1.5 пока- зано это разделение: ядро делит процессы A, B, C и D, расположенные вдоль горизонтальной оси, аппаратные средства вводят различия между режимами вы- полнения, расположенными по вертикали.
Несмотря на то, что система функционирует в одном из двух режимов, ядро действует от имени пользовательского процесса. Ядро не является какой-то особой совокупностью процессов, выполняющихся параллельно с пользовательски- ми, оно само выступает составной частью любого пользовательского процесса. Сделанный вывод будет скорее относиться к "ядру", распределяющему ресурсы, или к "ядру", производящему различные операции, и это будет означать, что процесс, выполняемый в режиме ядра, распределяет ресурсы и производит соот- ветствующие операции. Например, командный процессор shell считывает вводной поток с терминала с помощью запроса к операционной системе. Ядро операцион- ной системы, выступая от имени процессора shell, управляет функционированием терминала и передает вводимые символы процессору shell. Shell переходит в режим задачи, анализирует поток символов, введенных пользователем и выполня- ет заданную последовательность действий, которые могут потребовать выполне- ния и других системных операций.

1.5.1 Прерывания и особые ситуации

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

19
сора. По получении сигнала прерывания ядро операционной системы сохраняет свой текущий контекст (застывший образ выполняемого процесса), устанавливает причину прерывания и обрабатывает прерывание. После того, как прерывание бу- дет обработано ядром, прерванный контекст восстановится и работа продолжится так, как будто ничего не случилось. Устройствам обычно приписываются приори- теты в соответствии с очередностью обработки прерываний. В процессе обработ- ки прерываний ядро учитывает их приоритеты и блокирует обслуживание прерыва- ния с низким приоритетом на время обработки прерывания с более высоким прио- ритетом.
Особые ситуации связаны с возникновением незапланированных событий, выз- ванных процессом, таких как недопустимая адресация, задание привилегирован- ных команд, деление на ноль и т.д. Они отличаются от прерываний, которые вы- зываются событиями, внешними по отношению к процессу. Особые ситуации возни- кают прямо "посредине" выполнения команды, и система, обработав особую ситу- ацию, пытается перезапустить команду; считается, что прерывания возникают между выполнением двух команд, при этом система после обработки прерывания продолжает выполнение процесса уже начиная со следующей команды. Для обра- ботки прерываний и особых ситуаций в системе UNIX используется один и тот же механизм.

1.5.2 Уровни прерывания процессора

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

+------------------------------+ ^
| Машинные сбои | |
+------------------------------+ |
| Системные часы | Высокий приоритет
+------------------------------+ |
| Диск | |
+------------------------------+ |
| Сетевое оборудование | |
+------------------------------+ |
| Терминалы | Низкий приоритет
+------------------------------+ |
| Программные прерывания | |
+------------------------------+ v

Рисунок 1.6. Стандартные уровни прерываний

1.5.3 Распределение памяти

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

20
ющихся адресами переменных и информационных структур, а также адресами инст- рукций и функций. Компилятор генерирует адреса для виртуальной машины так, словно на физической машине не будет выполняться параллельно с транслируемой ни одна другая программа.
Когда программа запускается на выполнение, ядро выделяет для нее место в оперативной памяти, при этом совпадение виртуальных адресов, сгенерированных компилятором, с физическими адресами совсем необязательно. Ядро, взаимодейс- твуя с аппаратными средствами, транслирует виртуальные адреса в физические, т.е. отображает адреса, сгенерированные компилятором, в физические, машинные адреса. Такое отображение опирается на возможности аппаратных средств, поэ- тому компоненты системы UNIX, занимающиеся им, являются машинно-зависимыми. Например, отдельные вычислительные машины имеют специальное оборудование для подкачки выгруженных страниц памяти. Главы 6 и 9 посвящены более подробному рассмотрению вопросов, связанных с распределением памяти, и исследованию их соотношения с аппаратными средствами.

1.6 ВЫВОДЫ

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

21

ГЛАВА 2

ВВЕДЕНИЕ В АРХИТЕКТУРУ ЯДРА ОПЕРАЦИОННОЙ СИСТЕМЫ

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

2.1 АРХИТЕКТУРА ОПЕРАЦИОННОЙ СИСТЕМЫ UNIХ

Как уже ранее было замечено (см. [Christian 83], стр.239), в системе UNIX создается иллюзия того, что файловая система имеет "места" и что у про- цессов есть "жизнь". Обе сущности, файлы и процессы, являются центральными понятиями модели операционной системы UNIX. На Рисунке 2.1 представлена блок-схема ядра системы, отражающая состав модулей, из которых состоит ядро, и их взаимосвязи друг с другом. В частности, на ней слева изображена файло- вая подсистема, а справа подсистема управления процессами, две главные ком- поненты ядра. Эта схема дает логическое представление о ядре, хотя в дейст- вительности в структуре ядра имеются отклонения от модели, поскольку отдель- ные модули испытывают внутреннее воздействие со стороны других модулей.
Схема на Рисунке 2.1 имеет три уровня: уровень пользователя, уровень яд- ра и уровень аппаратуры. Обращения к операционной системе и библиотеки сос- тавляют границу между пользовательскими программами и ядром, проведенную на Рисунке 1.1. Обращения к операционной системе выглядят так же, как обычные вызовы функций в программах на языке Си, и библиотеки устанавливают соответ- ствие между этими вызовами функций и элементарными системными операция- ми, о чем более подробно см. в главе 6. При этом программы на ассемблере мо- гут обращаться к операционной системе непосредственно, без использования библиотеки системных вызовов. Программы часто обращаются к другим библиоте- кам, таким как библиотека стандартных подпрограмм ввода-вывода, достигая тем самым более полного использования системных услуг. Для этого во время компи- ляции библиотеки связываются с программами и частично включаются в программу пользователя. Далее мы проиллюстрируем эти моменты на примере.

На рисунке совокупность обращений к операционной системе разделена на те обращения, которые взаимодействуют с подсистемой управления файлами, и те, которые взаимодействуют с подсистемой управления процессами. Файловая под- система управляет файлами, размещает записи файлов, управляет свободным пространством, доступом к файлам и поиском данных для пользователей. Процес- сы взаимодействуют с подсистемой управления файлами, используя при этом со- вокупность специальных обращений к операционной системе, таких как open (для того, чтобы открыть файл на чтение или запись),close, read, write, stat (запросить атрибуты файла), chown (изменить запись с информацией о владельце файла) и chmod (изменить права доступа к файлу). Эти и другие операции расс- матриваются в главе 5.
Подсистема управления файлами обращается к данным, которые хранятся в файле, используя буферный механизм, управляющий потоком данных между ядром и устройствами внешней памяти. Буферный механизм, взаимодействуя с драйверами устройств ввода-вывода блоками, инициирует передачу данных к ядру и обратно. Драйверы устройств являются такими модулями в составе ядра, которые управля- ют работой периферийных устройств. Устройства ввода-вывода блоками относятся

22

программы пользователя
^
| +----------------------+
точка пере- | | библиотеки |
сечения ---------|------- +----------------------+
- | - ^ Уровень пользователя - | - | --------------------------|---------------------|----------------- Уровень ядра v v
+---------------------------------------------------+
| ^ обращения к операционной системе ^ |
+------+------------------------------------+-------+
| | +-----------------+---------------+ +----------------+---------+ | v | | v | | | | | | подсистема управле- | | ............| | ния файлами | | . взаимо- .| | <---+-+ | . действие .| | | | | . процессов.| | ^ ^ | | | подсистема ............| | | | | | | ............| +-------+--------------+----------+ | | . планиров-.|
| v +-+> управления . щик .|
| +--------------+ | ............|
| | буфер сверх- | | ............|
| | оперативной | | процессами . распреде-.|
| | памяти (кеш) | | . ление .|
| +--------------+ | . памяти .|
| ^ | ^ ............|
| | | | |
| v +-------+------------------+ +-------+----------------------+ | | v . | | | символ . блок | | | . | | +------------------------------+ | | | | | драйверы устройств | | | ^ | | +--------------+---------------+ |
| | +--------------+------------------------------+------------------+ | v аппаратный контроль v | +----------------------------------------------------------------+ Уровень ядра ------------------------------------------------------------------ Уровень аппаратуры +----------------------------------------------------------------+ | технические средства (аппаратура) | +----------------------------------------------------------------+

Рисунок 2.1. Блок-схема ядра операционной системы

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

23
мать это устройство как запоминающее устройство с произвольной выборкой. Подсистема управления файлами также непосредственно взаимодействует с драй- верами устройств "неструктурированного" ввода-вывода, без вмешательства бу- ферного механизма. К устройствам неструктурированного ввода-вывода, иногда именуемым устройствами посимвольного ввода-вывода (текстовыми), относятся устройства, отличные от устройств ввода-вывода блоками.
Подсистема управления процессами отвечает за синхронизацию процессов, взаимодействие процессов, распределение памяти и планирование выполнения процессов. Подсистема управления файлами и подсистема управления процессами взаимодействуют между собой, когда файл загружается в память на выполнение (см. главу 7): подсистема управления процессами читает в память исполняемые файлы перед тем, как их выполнить.
Примерами обращений к операционной системе, используемых при управлении процессами, могут служить fork (создание нового процесса), exec (наложение образа программы на выполняемый процесс), exit (завершение выполнения про- цесса), wait (синхронизация продолжения выполнения основного процесса с мо- ментом выхода из порожденного процесса), brk (управление размером памяти, выделенной процессу) и signal (управление реакцией процесса на возникновение экстраординарных событий). Глава 7 посвящена рассмотрению этих и других сис- темных вызовов.
Модуль распределения памяти контролирует выделение памяти процессам. Ес- ли в какой-то момент система испытывает недостаток в физической памяти для запуска всех процессов, ядро пересылает процессы между основной и внешней памятью с тем, чтобы все процессы имели возможность выполняться. В главе 9 описываются два способа управления распределением памяти: выгрузка (подкач- ка) и замещение страниц. Программу подкачки иногда называют планировщиком, т.к. она "планирует" выделение памяти процессам и оказывает влияние на рабо- ту планировщика центрального процессора. Однако в дальнейшем мы будем ста- раться ссылаться на нее как на "программу подкачки", чтобы избежать путаницы с планировщиком центрального процессора.
Модуль "планировщик" распределяет между процессами время центрального процессора. Он планирует очередность выполнения процессов до тех пор, пока они добровольно не освободят центральный процессор, дождавшись выделения к.-л. ресурса, или до тех пор, пока ядро системы не выгрузит их после того, как их время выполнения превысит заранее определенный квант времени. Плани- ровщик выбирает на выполнение готовый к запуску процесс с наивысшим приори- тетом; выполнение предыдущего процесса (приостановленного) будет продолжено тогда, когда его приоритет будет наивысшим среди приоритетов всех готовых к запуску процессов. Существует несколько форм взаимодействия процессов между собой, от асинхронного обмена сигналами о событиях до синхронного обмена со- общениями.
Наконец, аппаратный контроль отвечает за обработку прерываний и за связь с машиной. Такие устройства, как диски и терминалы, могут прерывать работу центрального процессора во время выполнения процесса. При этом ядро системы после обработки прерывания может возобновить выполнение прерванного процес- са. Прерывания обрабатываются не самими процессами, а специальными функциями ядра системы, перечисленными в контексте выполняемого процесса.

2.2 ВВЕДЕНИЕ В ОСНОВНЫЕ ПОНЯТИЯ СИСТЕМЫ

В это разделе дается обзор некоторых основных информационных структур, используемых ядром системы, и более подробно описывается функционирование модулей ядра, показанных на Рисунке 2.1.

2.2.1 Обзор особенностей подсистемы управления файлами

Внутреннее представление файла описывается в индексе, который содержит

24
описание размещения информации файла на диске и другую информацию, такую как владелец файла, права доступа к файлу и время доступа. Термин "индекс" (inode) широко используется в литературе по системе UNIX. Каждый файл имеет один индекс, но может быть связан с несколькими именами, которые все отража- ются в индексе. Каждое имя является указателем. Когда процесс обращается к файлу по имени, ядро системы анализирует по очереди каждую компоненту имени файла, проверяя права процесса на просмотр входящих в путь поиска каталогов, и в конце концов возвращает индекс файла. Например, если процесс обращается к системе:

open("/fs2/mjb/rje/sourcefile", 1);
ядро системы возвращает индекс для файла "/fs2/mjb/rje/sourcefile". Если процесс создает новый файл, ядро присваивает этому файлу неиспользуемый ин- декс. Индексы хранятся в файловой системе (и это мы еще увидим), однако при обработке файлов ядро заносит их в таблицу индексов в оперативной памяти.
Ядро поддерживает еще две информационные структуры, таблицу файлов и пользовательскую таблицу дескрипторов файла. Таблица файлов выступает гло- бальной структурой ядра, а пользовательская таблица дескрипторов файла выде- ляется под процесс. Если процесс открывает или создает файл, ядро выделяет в каждой таблице элемент, корреспондирующий с индексом файла. Элементы в этих трех структурах - в пользовательской таблице дескрипторов файла, в таблице файлов и в таблице индексов - хранят информацию о состоянии файла и о досту- пе пользователей к нему. В таблице файлов хранится смещение в байтах от на- чала файла до того места, откуда начнет выполняться следующая команда поль- зователя read или write,

Пользовательская
таблица дескрип- Таблица файлов Таблица индексов
торов файла
+---------+ +-----+ +-----+
| | | | | |
+---------+ | | | |
| --+---+ | | +-----+
+---------+ | | | +-------->| |
| --+-+ | +-----+ | +-----+
+---------+ | +-------->| --+---+ | |
| | | +-----+ | |
| | +--+ | ... | +-----+
| | | +-----+ +-------->| |
| | +------->| --+---+ +-----+
| | +-----+ | |
| | | | | |
+---------+ +-----+ +-----+

Рисунок 2.2. Таблицы файлов, дескрипторов файла и индексов

а также информация о правах доступа к открываемому процессу. Таблица деск- рипторов файла идентифицирует все открытые для процесса файлы. На Рисунке 2.2 показаны эти таблицы и связи между ними. В системных операциях open (от- крыть) и creat (создать) ядро возвращает дескриптор файла, которому соответ- ствует указатель в таблице дескрипторов файла. При выполнении операций read (читать) и write (писать) ядро использует дескриптор файла для входа в таб- лицу дескрипторов и, следуя указателям на таблицу файлов и на таблицу индек- сов, находит информацию в файле. Более подробно эти информационные структуры рассматриваются в главах 4 и 5. Сейчас достаточно сказать, что использование этих таблиц обеспечивает различную степень разделения доступа к файлу.
Обычные файлы и каталоги хранятся в системе UNIX на устройствах вво- да-вывода блоками, таких как магнитные ленты или диски. Поскольку существует

25
некоторое различие во времени доступа к этим устройствам, при установке сис- темы UNIX на лентах размещают файловые системы. С годами бездисковые автома- тизированные рабочие места станут общим случаем, и файлы будут располагаться в удаленной системе, доступ к которой будет осуществляться через сеть (см. главу 13). Для простоты, тем не менее, в последующем тексте подразумевается использование дисков. В системе может быть несколько физических дисков, на каждом из которых может размещаться одна и более файловых систем. Разбивка диска на несколько файловых систем облегчает администратору управление хра- нимыми данными. На логическом уровне ядро имеет дело с файловыми системами, а не с дисками, при этом каждая система трактуется как логическое устройст- во, идентифицируемое номером. Преобразование адресов логического устройства (файловой системы) в адреса физического устройства (диска) и обратно выпол- няется дисковым драйвером. Термин "устройство" в этой книге используется для обозначения логического устройства, кроме специально оговоренных случаев.
Файловая система состоит из последовательности логических блоков длиной 512, 1024, 2048 или другого числа байт, кратного 512, в зависимости от реа- лизации системы. Размер логического блока внутри одной файловой системы пос- тоянен, но может варьироваться в разных файловых системах в данной конфигу- рации. Использование логических блоков большого размера увеличивает скорость передачи данных между диском и памятью, поскольку ядро сможет передать боль- ше информации за одну дисковую операцию, и сокращает количество продолжи- тельных операций. Например, чтение 1 Кбайта с диска за одну операцию осущес- твляется быстрее, чем чтение 512 байт за две. Однако, если размер логическо- го блока слишком велик, полезный объем памяти может уменьшиться, это будет показано в главе 5. Для простоты термин "блок" в этой книге будет использо- ваться для обозначения логического блока, при этом подразумевается логичес- кий блок размером 1 Кбайт, кроме специально оговоренных случаев.

+---------+---------+-------------------+-----------------+
| блок | супер- | список | информационные |
|загрузки | блок | индексов | блоки |
+---------+---------+-------------------+-----------------+

Рисунок 2.3. Формат файловой системы

Файловая система имеет следующую структуру (Рисунок 2.3). * Блок загрузки располагается в начале пространства, отведенного под файло-
вую систему, обычно в первом секторе, и содержит программу начальной заг-
рузки, которая считывается в машину при загрузке или инициализации опера-
ционной системы. Хотя для запуска системы требуется только один блок заг-
рузки, каждая файловая система имеет свой (пусть даже пустой) блок загруз-
ки. * Суперблок описывает состояние файловой системы - какого она размера,
сколько файлов может в ней храниться, где располагается свободное прост-
ранство, доступное для файловой системы, и другая информация. * Список индексов в файловой системе располагается вслед за суперблоком. Ад-
министраторы указывают размер списка индексов при генерации файловой сис-
темы. Ядро операционной системы обращается к индексам, используя указатели
в списке индексов. Один из индексов является корневым индексом файловой
системы: это индекс, по которому осуществляется доступ к структуре катало-
гов файловой системы после выполнения системной операции mount (монтиро-
вать) (раздел 5.14). * Информационные блоки располагаются сразу после списка индексов и содержат
данные файлов и управляющие данные. Отдельно взятый информационный блок
может принадлежать одному и только одному файлу в файловой системе.

26

2.2.2 Процессы

В этом разделе мы рассмотрим более подробно подсистему управления про- цессами. Даются разъяснения по поводу структуры процесса и некоторых инфор- мационных структур, используемых при распределении памяти под процессы. За- тем дается предварительный обзор диаграммы состояния процессов и затрагива- ются различные вопросы, связанные с переходами из одного состояния в другое.
Процессом называется последовательность операций при выполнении програм- мы, которые представляют собой наборы байтов, интерпретируемые центральным процессором как машинные инструкции (т.н. "текст"), данные и стековые струк- туры. Создается впечатление, что одновременно выполняется множество процес- сов, поскольку их выполнение планируется ядром, и, кроме того, несколько процессов могут быть экземплярами одной программы. Выполнение процесса зак- лючается в точном следовании набору инструкций, который является замкнутым и не передает управление набору инструкций другого процесса; он считывает и записывает информацию в раздел данных и в стек, но ему недоступны данные и стеки других процессов. Одни процессы взаимодействуют с другими процессами и с остальным миром посредством обращений к операционной системе.
С практической точки зрения процесс в системе UNIX является объектом, создаваемым в результате выполнения системной операции fork. Каждый процесс, за исключением нулевого, порождается в результате запуска другим процессом операции fork. Процесс, запустивший операцию fork, называется родительским, а вновь созданный процесс - порожденным. Каждый процесс имеет одного родите- ля, но может породить много процессов. Ядро системы идентифицирует каждый процесс по его номеру, который называется идентификатором процесса (PID). Нулевой процесс является особенным процессом, который создается "вручную" в результате загрузки системы; после порождения нового процесса (процесс 1) нулевой процесс становится процессом подкачки. Процесс 1, известный под име- нем init, является предком любого другого процесса в системе и связан с каж- дым процессом особым образом, описываемым в главе 7.
Пользователь, транслируя исходный текст программы, создает исполняемый файл, который состоит из нескольких частей:
* набора "заголовков", описывающих атрибуты файла,
* текста программы,
* представления на машинном языке данных, имеющих начальные значения при запуске программы на выполнение, и указания на то, сколько пространства памяти ядро системы выделит под неинациализированные данные, так называемые bss (*) (ядро устанавливает их в 0 в момент запуска),
* других секций, таких как информация символических таблиц.
Для программы, приведенной на Рисунке 1.3, текст исполняемого файла представляет собой сгенерированный код для функций main и copy, к определен- ным данным относится переменная version (вставленная в программу для того, чтобы в последней имелись некоторые определенные данные), а к неопределенным - массив buffer. Компилятор с языка Си для системы версии V создает отдельно текстовую секцию по умолчанию, но не исключается возможность включения инст- рукций программы и в секцию данных, как в предыдущих версиях системы.
Ядро загружает исполняемый файл в память при выполнении системной опера- ции exec, при этом загруженный процесс состоит по меньшей мере из трех час- тей, так называемых областей: текста, данных и стека. Области текста и дан- ных корреспондируют с секциями текста и bss-данных исполняемого файла, а об- ласть стека создается автоматически и ее размер динамически устанавливается ядром системы во время выполнения. Стек состоит из логических записей акти- вации, помещаемых в стек при вызове функции и выталкиваемых из стека при возврате управления в вызвавшую процедуру; специальный регистр, именуемый указателем вершины стека, показывает текущую глубину стека. Запись активации включает параметры передавае-

(*) Сокращение bss имеет происхождение от ассемблерного псевдооператора для машины IBM 7090 и расшифровывается как "block started by symbol" ("блок, на- чинающийся с символа").
27
мые функции, ее локальные переменные, а также данные, необходимые для восс- тановления предыдущей записи активации, в том числе значения счетчика команд и указателя вершины стека в момент вызова функции. Текст программы включает

Стек задачи Направление Стек ядра
+--------------+ увеличения стека +------------------+
| Локальные | ^ | |
| переменные | | | ^ |
| (не показаны)| | | . |
|--------------| | | . |
|Адрес записи 2| | | . |
|--------------| | | . |
|Адрес возврата| | | . |
| после вызова | | | . |
| write | | | . |
|--------------| | | . |
|параметры, пе-| | | . |
| редаваемые | | | . |
| write | | | . |
|(new, buffer, | | | v |
| count) | Запись 3 | |
+--------------+ call write() Запись 3 +------------------+
| Локальные | | Локальные |
| переменные | | переменные |
| (count) | | |
|--------------| |------------------|
|Адрес записи 1| | Адрес записи 1 |
|--------------| |------------------|
|Адрес возврата| | Адрес возврата |
| после вызова | | после вызова |
| copy | | func2 |
|--------------| |------------------|
|параметры, пе-| | параметры, пере- |
| редаваемые | | даваемые функции |
| copy | | ядра func2 |
| (old, new) | Запись 2 Запись 2 | |
+--------------+ call copy() call func2() +------------------+
| Локальные | | Локальные |
| переменные | | переменные |
|(fdold, fdnew)| | |
|--------------| |------------------|
|Адрес записи 0| | Адрес записи 0 |
|--------------| |------------------|
|Адрес возврата| | Адрес возврата |
| после вызова | | после вызова |
| main | | func1 |
|--------------| |------------------|
|параметры, пе-| | параметры, пере- |
| редаваемые | | даваемые функции |
| main | | ядра func1 |
| (argc, argv) | Запись 1 Запись 1 | |
+--------------+ call main() call func1() +------------------+

Запись 0 Запись 0
Старт Интерфейс
обращений к операционной системе

Рисунок 2.4. Стеки задачи и ядра для программы копирования.

28
последовательности команд, управляющие увеличением стека, а ядро системы вы- деляет, если нужно, место под стек. В программе на Рисунке 1.3 параметры argc и argv, а также переменные fdold и fdnew, содержащиеся в вызове функции main, помещаются в стек, как только встретилось обращение к функции main (один раз в каждой программе, по условию), так же и параметры old и new и переменная count, содержащиеся в вызове функции copy, помещаются в стек в момент обращения к указанной функции.
Поскольку процесс в системе UNIX может выполняться в двух режимах, режи- ме ядра или режиме задачи, он пользуется в каждом из этих режимов отдельным стеком. Стек задачи содержит аргументы, локальные переменные и другую инфор- мацию относительно функций, выполняемых в режиме задачи. Слева на Рисунке 2.4 показан стек задачи для процесса, связанного с выполнением системной операции write в программе copy. Процедура запуска процесса (включенная в библиотеку) обратилась к функции main с передачей ей двух параметров, помес- тив в стек задачи запись 1; в записи 1 есть место для двух локальных пере- менных функции main. Функция main затем вызывает функцию copy с передачей ей двух параметров, old и new, и помещает в стек задачи запись 2; в записи 2 есть место для локальной переменной count. Наконец, процесс активизирует системную операцию write, вызвав библиотечную функцию с тем же именем. Каж- дой системной операции соответствует точка входа в библиотеке системных опе- раций; библиотека системных операций написана на языке ассемблера и включает специальные команды прерывания, которые, выполняясь, порождают "прерывание", вызывающее переключение аппаратуры в режим ядра. Процесс ищет в библиотеке точку входа, соответствующую отдельной системной операции, подобно тому, как он вызывает любую из функций, создавая при этом для библиотечной функции за- пись активации. Когда процесс выполняет специальную инструкцию, он переклю- чается в режим ядра, выполняет операции ядра и использует стек ядра.
Стек ядра содержит записи активации для функций, выполняющихся в режиме ядра. Элементы функций и данных в стеке ядра соответствуют функциям и дан- ным, относящимся к ядру, но не к программе пользователя, тем не менее, конс- трукция стека ядра подобна конструкции стека задачи. Стек ядра для процесса пуст, если процесс выполняется в режиме задачи. Справа на Рисунке 2.4 предс- тавлен стек ядра для процесса выполнения системной операции write в програм-

промежуточная
таблица облас- таблица
тей процессов областей
+---------------------+ +-------------+ +------------+
| часть адресного про-| | | | |
| странства задачи, | | | | |
| выделенная процессу | | | | |
+---------------------+ +-------------+ +------------+
^ +--+-> ---+-----+-> |
| | +-------------+ +-----+------+
+----------+----------+ +--+-> ---+--+ | | |
| | | | +-------------+ | | | |
| | | | | | | +-----+------+
+----------+----------+ | | | +--+-> | |
| v -----+--+ | | +-----+---+--+
+---------------------+ | | | | | |
| | +-------------+ +-----+---+--+
| | | |
+---------------------+ | |
таблица процессов +-------------------------+---+--+
| оперативная память v v |
+--------------------------------+

Рисунок 2.5. Информационные структуры для процессов

29

ме copy. Подробно алгоритмы выполнения системной операции write будут описа- ны в последующих разделах.
Каждому процессу соответствует точка входа в таблице процессов ядра, кроме того, каждому процессу выделяется часть оперативной памяти, отведенная под задачу пользователя. Таблица процессов включает в себя указатели на про- межуточную таблицу областей процессов, точки входа в которую служат в качес- тве указателей на собственно таблицу областей. Областью называется непрерыв- ная зона адресного пространства, выделяемая процессу для размещения текста, данных и стека. Точки входа в таблицу областей описывают атрибуты области, как напри- мер, хранятся ли в области текст программы или данные, закрытая ли эта об- ласть или же совместно используемая, и где конкретно в памяти размещается содержимое области. Внешний уровень косвенной адресации (через промежуточную таблицу областей, используемых процессами, к собственно таблице областей) позволяет независимым процессам совместно использовать области. Когда про- цесс запускает системную операцию exec, ядро системы выделяет области под ее текст, данные и стек, освобождая старые области, которые использовались про- цессом. Если процесс запускает операцию fork, ядро удваивает размер адресно- го пространства старого процесса, позволяя процессам совместно использовать области, когда это возможно, и, с другой стороны, производя физическое копи- рование. Если процесс запускает операцию exit, ядро освобождает области, ко- торые использовались процессом. На Рисунке 2.5 изображены информационные структуры, связанные с запуском процесса. Таблица процессов ссылается на промежуточную таблицу областей, используемых процессом, в которой содержатся указатели на записи в собственно таблице областей, соответствующие областям для текста, данных и стека процесса.
Запись в таблице процессов и часть адресного пространства задачи, выде- ленная процессу, содержат управляющую информацию и данные о состоянии про- цесса. Это адресное пространство является расширением соответствующей записи в таблице процессов, различия между данными объектами будут рассмотрены в главе 6. В качестве полей в таблице процессов, которые рассматриваются в последующих разделах, выступают:
* поле состояния,
* идентификаторы, которые характеризуют пользователя, являющегося вла- дельцем процесса (код пользователя или UID),
* значение дескриптора события, когда процесс приостановлен (находится в состоянии "сна").
Адресное пространство задачи, выделенное процессу, содержит описывающую процесс информацию, доступ к которой должен обеспечиваться только во время выполнения процесса. Важными полями являются:

* указатель на позицию в таблице процессов, соответствующую текущему процессу,
* параметры текущей системной операции, возвращаемые значения и коды ошибок,
* дескрипторы файла для всех открытых файлов,
* внутренние параметры ввода-вывода,
* текущий каталог и текущий корень (см. главу 5),
* границы файлов и процесса.
Ядро системы имеет непосредственный доступ к полям адресного пространст- ва задачи, выделенного выполняемому процессу, но не имеет доступ к соответс- твующим полям других процессов. С точки зрения внутреннего алгоритма, при обращении к адресному пространству задачи, выделенному выполняемому процес- су, ядро ссылается на структурную переменную u, и, когда запускается на вы- полнение другой процесс, ядро перенастраивает виртуальные адреса таким обра- зом, чтобы структурная переменная u указывала бы на адресное пространство задачи для нового процесса. В системной реализации предусмотрено облегчение идентификации текущего процесса благодаря наличию указателя на соответствую-

30
щую запись в таблице процессов из адресного пространства задачи.

2.2.2.1 Контекст процесса

Контекстом процесса является его состояние, определяемое текстом, значе- ниями глобальных переменных пользователя и информационными структурами, зна- чениями используемых машинных регистров, значениями, хранимыми в позиции таблицы процессов и в адресном пространстве задачи, а также содержимым сте- ков задачи и ядра, относящихся к данному процессу. Текст операций системы и ее глобальные информационные структуры совместно используются всеми процес- сами, но не являются составной частью контекста процесса.
Говорят, что при запуске процесса система исполняется в контексте про- цесса. Когда ядро системы решает запустить другой процесс, оно выполняет пе- реключение контекста с тем, чтобы система исполнялась в контексте другого процесса. Ядро осуществляет переключение контекста только при определенных условиях, что мы увидим в дальнейшем. Выполняя переключение контекста, ядро сохраняет информацию, достаточную для того, чтобы позднее переключиться вновь на первый процесс и возобновить его выполнение. Аналогичным образом, при переходе из режима задачи в режим ядра, ядро системы сохраняет информа- цию, достаточную для того, чтобы позднее вернуться в режим задачи и продол- жить выполнение с прерванного места. Однако, переход из режима задачи в ре- жим ядра является сменой режима, но не переключением контекста. Если обра- титься еще раз к Рисунку 1.5, можно сказать, что ядро выполняет переключение контекста, когда меняет контекст процесса A на контекст процесса B; оно ме- няет режим выполнения с режима задачи на режим ядра и наоборот, оставаясь в контексте одного процесса, например, процесса A.
Ядро обрабатывает прерывания в контексте прерванного процесса, пусть да- же оно и не вызывало никакого прерывания. Прерванный процесс мог при этом выполняться как в режиме задачи, так и в режиме ядра. Ядро сохраняет инфор- мацию, достаточную для того, чтобы можно было позже возобновить выполнение прерванного процесса, и обрабатывает прерывание в режиме ядра. Ядро не по- рождает и не планирует порождение какого-то особого процесса по обработке прерываний.

2.2.2.2 Состояния процесса

Время жизни процесса можно разделить на несколько состояний, каждое из которых имеет определенные характеристики, описывающие процесс. Все состоя- ния процесса рассматриваются в главе 6, однако представляется существенным для понимания перечислить некоторые из состояний уже сейчас:
1. Процесс выполняется в режиме задачи.
2. Процесс выполняется в режиме ядра.
3. Процесс не выполняется, но готов к выполнению и ждет, когда планиров- щик выберет его. В этом состоянии может находиться много процессов, и алго- ритм планирования устанавливает, какой из процессов будет выполняться следу- ющим.
4. Процесс приостановлен ("спит"). Процесс "впадает в сон", когда он не может больше продолжать выполнение, например, когда ждет завершения вво- да-вывода.
Поскольку процессор в каждый момент времени выполняет только один про- цесс, в состояниях 1 и 2 может находиться самое большее один процесс. Эти два состояния соответствуют двум режимам выполнения, режиму задачи и режиму ядра.

31

2.2.2.3 Переходы из состояния в состояние

Состояния процесса, перечисленные выше, дают статическое представление о процессе, однако процессы непрерывно переходят из состояния в состояние в соответствии с определенными правилами. Диаграмма переходов представляет со- бой ориентированный граф, вершины которого представляют собой состояния, в которые может перейти процесс, а дуги - события, являющиеся причинами пере- хода процесса из одного состояния в другое. Переход между двумя состояниями разрешен, если существует дуга из первого состояния во второе. Несколько дуг может выходить из одного состояния, однако процесс переходит только по одной из них в зависимости от того, какое событие произошло в системе. На Рисунке 2.6 представлена диаграмма переходов для состояний, перечисленных выше.
Как уже говорилось выше, в режиме разделения времени может выполняться одновременно несколько процессов, и все они могут одновременно работать в режиме ядра. Если им разрешить свободно выполняться в режиме ядра, то они могут испортить глобальные информационные структуры, принадлежащие ядру. Запрещая произвольное переключение контекстов и управляя возникновением со- бытий, ядро защищает свою целостность.
Ядро разрешает переключение контекста только тогда, когда процесс пере- ходит из состояния "запуск в режиме ядра" в состояние "сна в памяти". Про- цессы, запущенные в режиме ядра, не могут быть выгружены другими процессами; поэтому иногда говорят, что ядро невыгружаемо, при этом процессы, находящие- ся в режиме задачи, могут выгружаться системой. Ядро поддерживает целост- ность своих информационных структур, поскольку оно невыгружаемо, таким обра- зом решая проблему "взаимного исключения" - обеспечения того, что критичес- кие секции программы выполняются в каждый момент времени в рамках самое большее одного процесса.
В качестве примера рассмотрим программу (Рисунок 2.7) включения информа- ционной структуры, чей адрес содержится в указателе bp1, в список с исполь- зованием указателей после структуры, чей адрес содержится в bp. Если система разрешила переключение контекста при выполнении ядром фрагмента программы, возможно возникновение следующей ситуации. Предположим, ядро выполняет прог- рамму

запуск +-------+
в режи- | |
ме за- | 1 |
дачи | |
+-+-----+
обращение | ^ возврат
к системе | |
или пре- | |
рывание | |
v |
запуск +-----+-+
в режи- | |<---------+ прерывание,
ме яд- | 2 | | возврат из
ра | |<---------+ прерывания
+-+-----+
приоста-| ^ процесс пла-
+-------+ нов | | нирования +-------+
ожидание | |<----------+ +------------+ | готовность
("сон")| 4 +--------------------------->| 3 | к выполнению
+-------+ пробуждение +-------+
переключение
контекста допустимо

Рисунок 2.6. Состояния процесса и переходы между ними

32

до комментариев и затем осуществляет переключение контекста. Список с ис- пользованием сдвоенных указателей имеет противоречивый вид: структура bp1 только наполовину входит в этот список. Если процесс следует за передними указателями, он обнаружит bp1 в данном списке, но если он последует за фоно- выми указателями, то вообще не найдет структуру bp1 (Рисунок 2.8). Если дру- гие процессы будут обрабатывать указатели в списке до момента повторного за- пуска первого процесса, структура списка может постоянно разрушаться. Систе- ма UNIX предупреждает возникновение подобных ситуаций, запрещая переключение контекстов на время выполнения процесса в режиме ядра. Если процесс перехо- дит в состояние "сна", делая допустимым переключение контекста, алгоритмы ядра обеспечивают защиту целостности информационных структур системы.
Проблемой, которая может привести к нарушению целостности информации яд- ра, является обработка прерываний, могущая вносить изменения в информацию о состоянии ядра. Например, если ядро выполняло программу, приведенную на Ри- сунке 2.7, и получило прерывание по достижении комментариев, программа обра- ботки прерыва-

+-----------------------------------------------------------+
| struct queue { |
| |
| |
| |
| } *bp, *bp1; |
| bp1 - > forp = bp - > forp; |
| bp1 - > backp = bp; |
| bp - > forp = bp1; |
| /* здесь рассмотрите возможность переключения контекста */|
| bp1 - > forp - > backp = bp1; |
+-----------------------------------------------------------+

Рисунок 2.7. Пример программы, создающей список с двунаправленными указате-
лями

+-------+
| |
| bp1 |
| |
+-------+
+-------+ +-------+
----->| +------------------------------>| +---->
| bp | | |
<-----+ |<------------------------------+ |<----
+-------+ +-------+

Включение bp1 в список с двунаправленными указателями

+-------+ +-------+ +-------+
----->| +---------->| +---------->| +---->
| bp | | bp1 | | |
<-----+ |<----------+ | +-----+ |<----
+-------+<----+ +-------+ | +-------+
+-------------------+

Рисунок 2.8. Список с указателями, некорректный из-за переключения контек-
ста

33
ний может разрушить ссылки, если будет манипулировать указателями, как было показано ранее. Чтобы решить эту проблему, система могла бы запретить все прерывания на время работы в режиме ядра, но при этом затянулась бы обработ- ка прерывания, что в конечном счете нанесло бы ущерб производительности сис- темы. Вместо этого ядро повышает приоритет прерывания процессора, запрещая прерывания на время выполнения критических секций программы. Секция програм- мы является критической, если в процессе ее выполнения запуск программ обра- ботки произвольного прерывания может привести к возникновению проблем, имею- щих отношение к нарушению целостности. Например, если программа обработки прерывания от диска работает с буферными очередями, то часть прерываемой программы, при выполнении которой ядро обрабатывает буферные очереди, явля- ется критической секцией по отношению к программе обработки прерывания от диска. Критические секции невелики по размеру и встречаются нечасто, поэтому их существование не оказывает практически никакого воздействия на производи- тельность системы. В других операционных системах данный вопрос решается пу- тем запрещения любых прерываний при работе в системных режимах или путем разработки схем блокировки, обеспечивающих целостность. В главе 12 мы еще вернемся к этому вопросу, когда будем говорить о многопроцессорных системах, где применения указанных мер для решения проблемы недостаточно.
Чтобы подвести черту, еще раз скажем, что ядро защищает свою целост- ность, разрешая переключение контекста только тогда, когда процесс переходит в состояние "сна", а также препятствуя воздействию одного процесса на другой с целью изменения состояния последнего. Оно также повышает приоритет преры- вания процессора на время выполнения критических секций программ, запрещая таким образом прерывания, которые в противном случае могут вызвать нарушение целостности. Планировщик процессов периодически выгружает процессы, выполня- ющиеся в режиме задачи, для того, чтобы процессы не могли монопольно исполь- зовать центральный процессор.

2.2.2.4 "Сон" и пробуждение

Процесс, выполняющийся в режиме ядра, имеет значительную степень автоно- мии в решении того, как ему следует реагировать на возникновение системных событий. Процессы могут общаться между собой и "предлагать" различные аль- тернативы, но при этом окончательное решение они принимают самостоятельно. Мы еще увидим, что существует набор правил, которым подчиняется поведение процессов в различных обстоятельствах, но каждый процесс в конечном итоге следует этим правилам по своей собственной инициативе. Например, если про- цесс должен временно приостановить выполнение ("перейти ко сну"), он это де- лает по своей доброй воле. Следовательно, программа обработки прерываний не может приостановить свое выполнение, ибо если это случится, прерванный про- цесс должен был бы "перейти ко сну" по умолчанию.
Процессы приостанавливают свое выполнение, потому что они ожидают воз- никновения некоторого события, например, завершения ввода-вывода на перифе- рийном устройстве, выхода, выделения системных ресурсов и т.д. Когда гово- рят, что процесс приостановился по событию, то имеется ввиду, что процесс находится в состоянии "сна" до наступления события, после чего он пробудится и перейдет в состояние "готовности к выполнению". Одновременно могут приос- тановиться по событию много процессов; когда событие наступает, все процес- сы, приостановленные по событию, пробуждаются, поскольку значение условия, связанного с событием, больше не является "истинным". Когда процесс пробуж- дается, он переходит из состояния "сна" в состояние "готовности к выполне- нию", находясь в котором он уже может быть выбран планировщиком; следует об- ратить внимание на то, что он не выполняется немедленно. Приостановленные процессы не занимают центральный процессор. Ядру системы нет надобности пос- тоянно проверять то, что процесс все еще приостановлен, т.к. ожидает наступ- ления события, и затем будить его.
Например, процесс, выполняемый в режиме ядра, должен иногда блокировать

34
структуру данных на случай приостановки в будущем; процессы, пытающиеся об- ратиться к заблокированной структуре, обязаны проверить наличие блокировки и приостановить свое выполнение, если структура заблокирована другим процес- сом. Ядро выполняет блокировки такого рода следующим образом:

while (условие "истинно")
sleep (событие: условие принимает значение "ложь");
set condition true; то есть:
пока (условие "истинно")
приостановиться (до наступления события, при котором
условие принимает значение "ложь");
присвоить условию значение "истина";

Ядро снимает блокировку и "будит" все процессы, приостанов- ленные из-за этой блокировки, следующим образом:

set condition false;
wakeup (событие: условие "ложно"); то есть:
присвоить условию значение "ложь";
перезапуститься (при наступлении события, при котором условие
принимает значение "ложь");

На Рисунке 2.9 приведен пример, в котором три процесса, A, B и C оспари- вают заблокированный буфер. Переход в состояние "сна" вызывается заблокиро- ванностью буфера. Процессы, однажды запустившись, обнаруживают, что буфер заблокирован, и приостанавливают свое выполнение до наступления события, по которому буфер будет разблокирован. В конце концов блокировка с буфера сни- мается и все процессы "пробуждаются", переходя в состояние "готовности к вы- полнению". Ядро наконец выбирает один из процессов, скажем, B, для выполне- ния. Процесс B, выполняя цикл "while", обнаруживает, что буфер разблокиро- ван, блокирует его и продолжает свое выполнение. Если процесс B в дальнейшем снова приостановится без снятия блокировки с буфера (например, ожидая завер- шения операции ввода-вывода), ядро сможет приступить к планированию выполне- ния других процессов. Если будет при этом выбран процесс A, этот процесс, выполняя цикл "while", обнаружит, что буфер заблокирован, и снова перейдет в состояние "сна"; возможно то же самое произойдет и с процессом C. В конце концов выполнение процесса B возобновится и блокировка с буфера будет снята, в результате чего процессы A и C получат доступ к нему. Таким образом, цикл "while-sleep" обеспечивает такое положение, при котором самое большее один процесс может иметь доступ к ресурсу.
Алгоритмы перехода в состояние "сна" и пробуждения более подробно будут рассмотрены в главе 6. Тем временем они будут считаться "неделимыми". Про- цесс переходит в состояние "сна" мгновенно и находится в нем до тех пор, по- ка не будет "разбужен". После того, как он приостанавливается, ядро системы начинает планировать выполнение следующего процесса и переключает контекст на него.

2.3 СТРУКТУРЫ ДАННЫХ ЯДРА

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

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

2.4 УПРАВЛЕНИЕ СИСТЕМОЙ

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

Время Процесс A Процесс B Процесс C
+-------------------------------------------------------------
| Буфер заблокирован
| Приостановлен
| . Буфер заблокирован
| . Приостановлен
| . . Буфер заблокирован
| . . Приостановлен
| +----------------------------------------------------------+
| |Буфер разблокирован Пробуждение всех "спящих" процессов|
| +----------------------------------------------------------+
| Готов к Готов к Готов к
| выполнению выполнению выполнению
| . .
| . Запущен .
| . Буфер разблокирован .
| . Блокировка буфера .
| . . .
| . Приостановка по .
| . произвольной причине .
| . . .
| Запущен . .
| Буфер заблокирован . .
| Приостановка . .
| . . Запущен
| . . Буфер заблокирован
| . . Приостановка
| . Пробуждение .
| . Снятие блокировки .
| . буфера .
| Готов к Пробуждение всех Готов к
| выполнению "спящих" процессов выполнению
|
v Переключение контекста

Запущен

Рисунок 2.9. Многократная приостановка выполнения процессов, вызванная
блокировкой

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

2.5 ВЫВОДЫ И ОБЗОР ПОСЛЕДУЮЩИХ ГЛАВ

В этой главе описана архитектура ядра операционной системы; его основны- ми компонентами выступают подсистема управления файлами и подсистема управ- ления процессами. Подсистема управления файлами управляет хранением и выбор- кой данных в пользовательских файлах. Файлы организованы в виде файловых систем, которые трактуются как логические устройства; физическое устройство, такое как диск, может содержать несколько логических устройств (файловых систем). Каждая файловая система имеет суперблок, в котором описывается структура и содержимое файловой системы, каждый файл в файловой системе опи- сывается индексом, хранящим атрибуты файла. Системные операции работают с файлами, используя индексы.
Процессы находятся в различных состояниях и переходят из состояния в состояние, следуя определенным правилам перехода. В частности, процессы, вы- полняющиеся в режиме ядра, могут приостановить свое выполнение и перейти в состояние "сна", но ни один процесс не может перевести в это состояние дру- гой процесс. Ядро является невыгружаемым и это означает, что процесс, выпол- няющийся в режиме ядра, будет продолжать свое выполнение до тех пор, пока не перейдет в состояние "сна" или пока не вернется в режим задачи. Ядро обеспе- чивает целостность своих информационных структур благодаря своей невыгружае- мости, а также путем блокирования прерываний на время выполнения критических секций программы.
В остальных частях главы детально описываются подсистемы, изображенные на Рисунке 2.1, а также взаимодействие между ними, начиная с подсистемы уп- равления файлами и включая подсистему управления процессами. В следующей главе рассматривается буфер сверхоперативной памяти (кеш) и описываются ал- горитмы управления буфером, используемые в главах 4, 5 и 7. В главе 4 расс- матриваются внутренние алгоритмы файловой системы, включая обработку индек- сов, структуру файлов, преобразование имени пути в индекс. В главе 5 расс- матриваются системные операции, которые, используя приведенные в главе 4 ал- горитмы, обращаются к файловой системе, т.е. такие, как open, close, read и write. Глава 6 имеет дело с понятием контекста процесса и его адресным прос- транством, а глава 7 рассматривает системные операции, связанные с управле- нием процессами и использующие алгоритмы главы 6. Глава 8 касается планиро- вания выполнения процессов, в главе 9 обсуждаются алгоритмы распределения памяти. Глава 10 посвящена драйверам устройств, рассмотрение которых до того откладывалось, чтобы прежде объяснить связь драйвера терминала с управлением процессами. В главе 11 представлено несколько форм взаимодействия процессов. Наконец, в последних двух главах рассматриваются вопросы, связанные с углуб- ленным изучением особенностей системы, в частности, особенности многопроцес- сорных систем и распределенных систем.

37

2.6 УПРАЖНЕНИЯ

1. Рассмотрим следующий набор команд:

grep main a.c b.c c.c > grepout &
wc -1 < grepout &
rm grepout &

Амперсанд (символ "&") в конце каждой командной строки говорит командному
процессору shell о том, что команду следует выполнить на фоне, при этом
shell может выполнять все командные строки параллельно. Почему это не
равноценно следующей командной строке ?

grep main a.c b.c c.c | wc -1
2. Рассмотрим пример программы, приведенный на Рисунке 2.7. Предположим, что
в тот момент, когда при ее выполнении встретился комментарий, произошло
переключение контекста и другой процесс убрал содержимое буфера из списка
указателей с помощью следующих команд:

remove(gp)
struct queue *gp;
{
gp - > forp - > backp = gp - > backp;
gp - > backp - > forp = gp - > forp;
gp - > forp = gp - > backp = NULL;
}

Рассмотрим три случая:
- Процесс убирает из списка с указателями структуру bp1.
- Процесс убирает из списка с указателями структуру, следующую после
структуры bp1.
- Процесс убирает из списка структуру, которая первоначально следовала за
bp1 до того, как структура bp была наполовину включена в указанный спи-
сок.
В каком состоянии будет список после того, как первый процесс завершит
выполнение части программы, расположенной после комментариев ? 3. Что произошло бы в том случае, если ядро попыталось бы возобновить выпол-
нение всех процессов, приостановленных по событию, но в системе не было
бы к этому моменту ни одного такого процесса ?

38