ПРЕДИСЛОВИЕ
Впервые система UNIX была описана в 1974 году в статье Кена Томпсона и Дэнниса Ричи в журнале «Communications of the ACM» [Thompson 74]. С этого времени она получила широкое распространение и завоевала широкую популярность среди производителей ЭВМ, которые все чаще стали оснащать ею свои машины. Особой популярностью она пользуется в университетах, где довольно часто участвует в исследовательском и учебном процессе.
Множество книг и статей посвящено описанию отдельных частей системы; среди них два специальных выпуска «Bell System Technical Journal» за 1978 год [BSTJ 78] и за 1984 год [BSTJ 84]. Во многих книгах описывается пользовательский интерфейс, в частности использование электронной почты, подготовка документации, работа с командным процессором Shell; в некоторых книгах, таких как «The UNIX Programming Environment» [Kernighan 84] и «Advanced UNIX Programming» [Rochkind 85], описывается программный интерфейс. Настоящая книга посвящена описанию внутренних алгоритмов и структур, составляющих основу операционной системы (т. н. «ядро»), и объяснению их взаимосвязи с программным интерфейсом. Таким образом, она будет полезна для работающих в различных операционных средах. Во-первых, она может использоваться в качестве учебного пособия по курсу «Операционные системы» как для студентов последнего курса, так и для аспирантов первого года обучения. При работе с книгой было бы гораздо полезнее обращаться непосредственно к исходному тексту системных программ, но книгу можно читать и независимо от него. Во-вторых, эта книга может служить в качестве справочного руководства для системных программистов, из которого последние могли бы лучше уяснить себе механизм работы ядра операционной системы и сравнить между собой алгоритмы, используемые в UNIX, и алгоритмы, используемые в других операционных системах. Наконец, программисты, работающие в среде UNIX, могут углубить свое понимание механизма взаимодействия программ с операционной системой и посредством этого прийти к написанию более эффективных и совершенных программ.
Содержание и порядок построения материала в книге соответствуют курсу лекций, подготовленному и прочитанному мной для сотрудников фирмы Bell Laboratories, входящей в состав корпорации AT&T, между 1983 и 1984 гг. Несмотря на то, что главное внимание в курсе лекций обращалось на исходный текст системных программ, я обнаружил, что понимание исходного текста облегчается, если пользователь имеет представление о системных алгоритмах. В книге я пытался изложить описание алгоритмов как можно проще, чтобы и в малом отразить простоту и изящество рассматриваемой операционной системы. Таким образом, книга представляет собой не только подробное истолкование особенностей системы на английском языке; это изображение общего механизма работы различных алгоритмов, и что гораздо важнее, это отражение процесса их взаимодействия между собой. Алгоритмы представлены на псевдокоде, похожем на язык Си, поскольку читателю легче воспринимать описание на естественном языке; наименования алгоритмов соответствуют именам процедур, составляющих ядро операционной системы. Рисунки описывают взаимодействие различных информационных структур под управлением операционной системы. В последних главах многие системные понятия иллюстрируются с помощью небольших программ на языке Си. В целях экономии места и обеспечения ясности изложения из этих примеров исключен контроль возникновения ошибок, который обычно предусматривается при написании программ. Эти примеры прогонялись мною под управлением версии V; за исключением программ, иллюстрирующих особенности, присущие версии V, их можно выполнять под управлением других версий операционной системы.
Большое число упражнений, подготовленных первоначально для курса лекций, приведено в конце каждой главы, они составляют ключевую часть книги. Отдельные упражнения, иллюстрирующие основные понятия, размещены непосредственно в тексте книги. Другая часть упражнений отличается большей сложностью, поскольку их предназначение состоит в том, чтобы помочь читателю углубить свое понимание особенностей системы. И, наконец, часть упражнений является по природе исследовательской, предназначенной для изучения отдельных проблем. Упражнения повышенной сложности помечены звездочками.
Системное описание базируется на особенностях операционной системы UNIX версия V редакция 2, распространением которой занимается корпорация AT&T, с учетом отдельных особенностей редакции 3. Это та система, с которой я наиболее знаком, однако я постарался отразить и интересные детали других разновидностей операционных систем, в частности систем, распространяемых через «Berkeley Software Distribution» (BSD). Я не касался вопросов, связанных с характеристиками отдельных аппаратных средств, стараясь только в общих чертах охватить процесс взаимодействия ядра операционной системы с аппаратными средствами и игнорируя характерные особенности физической конфигурации. Тем не менее, там, где вопросы, связанные с машинными особенностями, представились мне важными с точки зрения понимания механизма функционирования ядра, оказалось уместным и углубление в детали. По крайней мере, беглый просмотр затронутых в книге вопросов ясно указывает те составные части операционной системы, которые являются наиболее машинно-зависимыми.
ГЛАВА 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, Томпсон получил возможность изучить машину, однако условия разработки программ потребовали использования кросс-ассемблера для трансляции программы на машине с системой 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 с надбавкой к цене за дополнительные услуги,
С ростом популярности микропроцессоров другие компании стали переносить систему UNIX на новые машины, однако ее простота и ясность побудили многих разработчиков к самостоятельному развитию системы, в результате чего было создано несколько вариантов базисной системы. За период между 1977 и 1982 годом фирма Bell Laboratories объединила несколько вариантов, разработанных в корпорации AT&T, в один, получивший коммерческое название UNIX версия III. В дальнейшем фирма Bell Laboratories добавила в версию III несколько новых особенностей, назвав новый продукт UNIX версия V,
1.2 СТРУКТУРА СИСТЕМЫ
На Рисунке 1.1 изображена архитектура верхнего уровня системы UNIX. Технические средства, показанные в центре диаграммы, выполняют функции, обеспечивающие функционирование операционной системы и перечисленные в разделе 1.5. Операционная система взаимодействует с аппаратурой непосредственно,
[3]
обеспечивая обслуживание программ и их независимость от деталей аппаратной конфигурации. Если представить систему состоящей из пластов, в ней можно выделить системное ядро, изолированное от пользовательских программ. Поскольку программы не зависят от аппаратуры, их легко переносить из одной системы UNIX в другую, функционирующую на другом комплексе технических средств, если только в этих программах не подразумевается работа с конкретным оборудованием. Например, программы, рассчитанные на определенный размер машинного слова, гораздо труднее переводить на другие машины по сравнению с программами, не требующими подобных установлений.
Программы, подобные командному процессору shell и редакторам (ed и vi) и показанные на внешнем по отношению к ядру слое, взаимодействуют с ядром при помощи хорошо определенного набора обращений к операционной системе. Обращения к операционной системе понуждают ядро к выполнению различных операций, которых требует вызывающая программа, и обеспечивают обмен данными между ядром и программой. Некоторые из программ, приведенных на рисунке, в стандартных конфигурациях системы известны как команды, однако на одном уровне с ними могут располагаться и доступные пользователю программы, такие как программа a.out, стандартное имя для исполняемого файла, созданного компилятором с языка Си. Другие прикладные программы располагаются выше указанных программ, на верхнем уровне, как это показано на рисунке. Например, стандартный компилятор с языка Си, cc, располагается на самом внешнем слое: он вызывает препроцессор для Си, ассемблер и загрузчик (компоновщик), т. е. отдельные программы предыдущего уровня. Хотя на рисунке приведена двухуровневая иерархия прикладных программ, пользователь может расширить иерархическую структуру на столько уровней, сколько необходимо. В самом деле, стиль программирования, принятый в системе UNIX, допускает разработку комбинации программ, выполняющих одну и ту же, общую задачу.
Многие прикладные подсистемы и программы, составляющие верхний уровень системы, такие как командный процессор shell, редакторы, SCCS (система обработки исходных текстов программ) и пакеты программ подготовки документации, постепенно становятся синонимом понятия «система UNIX». Однако все они пользуются услугами программ нижних уровней и в конечном счете ядра с помощью набора обращений к операционной системе. В версии V принято 64 типа обращений к операционной системе, из которых немногим меньше половины используются часто. Они имеют несложные параметры, что облегчает их использование, предоставляя при этом большие возможности пользователю. Набор обращений к операционной системе вместе с реализующими их внутренними алгоритмами составляют «тело» ядра, в связи с чем рассмотрение операционной системы UNIX в этой книге сводится к подробному изучению и анализу обращений к системе и их взаимодействия между собой. Короче говоря, ядро реализует функции, на которых основывается выполнение всех прикладных программ в системе UNIX, и им же определяются эти функции. В книге часто употребляются термины «система UNIX», «ядро» или «система», однако при этом имеется ввиду ядро операционной системы UNIX, что и должно вытекать из контекста.
1.3 ОБЗОР С ТОЧКИ ЗРЕНИЯ ПОЛЬЗОВАТЕЛЯ
В этом разделе кратко рассматриваются главные детали системы UNIX, в частности файловая система, среда выполнения процессов и элементы структурных блоков (например, каналы). Подробное исследование взаимодействия этих деталей с ядром содержится в последующих главах.
1.3.1 Файловая система
Файловая система UNIX характеризуется:
• иерархической структурой,
• согласованной обработкой массивов данных,
• возможностью создания и удаления файлов,
• динамическим расширением файлов,
1.3.2 Среда выполнения процессов
Программой называется исполняемый файл, а процессом называется последовательность операций программы или часть программы при ее выполнении. В системе UNIX может одновременно выполняться множество процессов (эту особенность иногда называют мультипрограммированием или многозадачным режимом), при чем их число логически не ограничивается, и множество частей программы (такой как copy) может одновременно находиться в системе. Различные системные операции позволяют процессам порождать новые процессы, завершают процессы, синхронизируют выполнение этапов процесса и управляют реакцией на наступление различных событий. Благодаря различным обращениям к операционной системе, процессы выполняются независимо друг от друга.
Например, процесс, выполняющийся в программе, приведенной на Рисунке 1.4, запускает операцию fork, чтобы породить новый процесс. Новый процесс, именуемый порожденным процессом, получает значение кода завершения операции fork, равное 0, и активизирует операцию execl, которая выполняет программу copy (Рисунок 1.3). Операция execl загружает файл „copy“, который предположительно находится в текущем каталоге, в адресное пространство порожденного процесса и запускает программу с параметрами, полученными от пользователя. В случае успешного выполнения операции execl управление в вызвавший ее процесс не возвращается, поскольку процесс выполняется в новом адресном пространстве (подробнее об этом в главе 7). Тем временем, процесс, запустивший операцию fork (родительский процесс), получает ненулевое значение кода завершения операции, вызывает операцию wait, которая приостанавливает его выполнение до тех пор, пока не закончится выполнение программы copy, и завершается (каждая программа имеет выход в конце главной процедуры, после которой располагаются программы стандартных библиотек Си, подключаемые в процессе компиляции). Например, если исполняемая программа называется run, пользователь запускает ее следующим образом:
run oldfile newfile
1.3.3 Элементы конструкционных блоков
Как уже говорилось ранее, концепция разработки системы UNIX заключалась в построении операционной системы из элементов, которые позволили бы пользователю создавать небольшие программные модули, выступающие в качестве конструкционных блоков при создании более сложных программ. Одним из таких элементов, с которым часто сталкиваются пользователи при работе с командным процессором shell, является возможность переназначения ввода-вывода. Говоря условно, процессы имеют доступ к трем файлам: они читают из файла стандартного ввода, записывают в файл стандартного вывода и выводят сообщения об ошибках в стандартный файл ошибок. Процессы, запускаемые с терминала, обычно используют терминал вместо всех этих трех файлов, однако каждый файл независимо от других может быть «переназначен». Например, команда
ls
выводит список всех файлов текущего каталога на устройство (в файл) стандартного вывода, а команда
1.4 ФУНКЦИИ ОПЕРАЦИОННОЙ СИСТЕМЫ
На Рисунке 1.1 уровень ядра операционной системы изображен непосредственно под уровнем прикладных программ пользователя. Выполняя различные элементарные операции по запросам пользовательских процессов, ядро обеспечивает функционирование пользовательского интерфейса, описанного выше. Среди функций ядра можно отметить:
• Управление выполнением процессов посредством их создания, завершения или приостановки и организации взаимодействия между ними.
• Планирование очередности предоставления выполняющимся процессам времени центрального процессора (диспетчеризация). Процессы работают с центральным процессором в режиме разделения времени: центральный процессор
[5]
выполняет процесс, по завершении отсчитываемого ядром кванта времени процесс приостанавливается и ядро активизирует выполнение другого процесса. Позднее ядро запускает приостановленный процесс.
• Выделение выполняемому процессу оперативной памяти. Ядро операционной системы дает процессам возможность совместно использовать участки адресного пространства на определенных условиях, защищая при этом адресное пространство, выделенное процессу, от вмешательства извне. Если системе требуется свободная память, ядро освобождает память, временно выгружая процесс на внешние запоминающие устройства, которые называют устройствами выгрузки. Если ядро выгружает процессы на устройства выгрузки целиком, такая реализация системы UNIX называется системой со свопингом (подкачкой); если же на устройство выгрузки выводятся страницы памяти, такая система называется системой с замещением страниц.
• Выделение внешней памяти с целью обеспечения эффективного хранения информации и выборка данных пользователя. Именно в процессе реализации этой функции создается файловая система. Ядро выделяет внешнюю память под пользовательские файлы, мобилизует неиспользуемую память, структурирует файловую систему в форме, доступной для понимания, и защищает пользовательские файлы от несанкционированного доступа.