THE DESIGN OF THE UNIX OPERATING SYSTEM

by Maurice J. Bach

Системное описание базируется на особенностях операционной системы UNIX версия V редакция 2, распространением которой занимается корпорация AT&T, с учетом отдельных особенностей редакции 3. Это та система, с которой я наиболее знаком, однако я постарался отразить и интересные детали других разновидностей операционных систем, в частности систем, распространяемых через "Berkeley Software Distribution" (BSD). Я не касался вопросов, связанных с характеристиками отдельных аппаратных средств, стараясь только в общих чертах охватить процесс взаимодействия ядра операционной системы с аппаратными средствами и игнорируя характерные особенности физической конфигурации. Тем не менее, там, где вопросы, связанные с машинными особенностями, представились мне важными с точки зрения понимания механизма функционирования ядра, оказалось уместным и углубление в детали. По крайней мере, беглый просмотр затронутых в книге вопросов ясно указывает те составные части операционной системы, которые являются наиболее машинно-зависимыми.

Материал в книге построен следующим образом. Глава 1 служит введением, содержащим краткое, общее описание системных особенностей с точки зрения пользователя и объясняющий структуру системы. В главе 2 дается общее представление об архитектуре ядра и поясняются некоторые основные понятия. В остальной части книги освещаются вопросы, связанные с общей архитектурой системы и описанием ее различных компонент как блоков единой конструкции. В ней можно выделить три раздела: файловая система, управление процессами и вопросы, связанные с развитием. Файловая система представлена первой, поскольку ее понимание легче по сравнению с управлением процессами. Так, глава 3 посвящена описанию механизма функционирования системного буфера сверхоперативной памяти (кеша), составляющего основу файловой системы. Глава 4 описывает информационные структуры и алгоритмы, используемые файловой системой. В этих алгоритмах используются методы, объясняемые в главе 3, для ведения внутренней "бухгалтерии", необходимой для управления пользовательскими файлами. Глава 5 посвящена описанию обращений к операционной системе, обслуживающих интерфейс пользователя с файловой системой; для обеспечения доступа к пользовательским файлам используются алгоритмы главы 4.

Основное внимание в главе 6 уделяется управлению процессами. В ней определяется понятие контекста процесса и исследуются внутренние составляющие ядра операционной системы, управляющие контекстом процесса. В частности, рассматривается обращение к операционной системе, обработка прерываний и переключение контекста. В главе 7 анализируются те системные операции, которые управляют контекстом процесса. Глава 8 касается планирования процессов, глава 9 - распределения памяти, включая системы подкачки и замещения страниц.

В главе 10 дается обзор общих особенностей взаимодействия, которое обеспечивают драйверы устройств, особое внимание уделяется дисковым и терминальным драйверам. Несмотря на то, что устройства логически входят в состав файловой системы, их рассмотрение до этого момента откладывалось в связи с возникновением вопросов, связанных с управлением процессами, при обсуждении терминальных драйверов. Эта глава также служит мостиком к вопросам, связанным с развитием системы, которые рассматриваются в конце книги. Глава 11 касается взаимодействия процессов и организации сетей, в том числе сообщений, используемых в версии V, разделения памяти, семафоров и пакетов BSD. Глава 12 содержит компактное изложение особенностей двухпроцессорной системы UNIX, в главе 13 исследуются двухмашинные распределенные вычислительные системы.

Материал, представленный в первых девяти главах, может быть прочитан в процессе изучения курса "Операционные системы" в течение одного семестра, материал остальных глав следует изучать на опережающих семинарах с параллельным выполнением практических заданий.

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

В 1965 году фирма Bell Telephone Laboratories, объединив свои усилия с компанией General Electric и проектом MAC Массачусетского технологического института, приступили к разработке новой операционной системы, получившей название Multics [Organick 72]. Перед системой Multics были поставлены задачи - обеспечить одновременный доступ к ресурсам ЭВМ большого количества пользователей, обеспечить достаточную скорость вычислений и хранение данных и дать возможность пользователям в случае необходимости совместно использовать данные. Многие разработчики, впоследствии принявшие участие в создании ранних редакций системы UNIX, участвовали в работе над системой Multics в фирме Bell Laboratories. Хотя первая версия системы Multics и была запущена в 1969 году на ЭВМ GE 645, она не обеспечивала выполнение главных вычислительных задач, для решения которых она предназначалась, и не было даже ясно, когда цели разработки будут достигнуты. Поэтому фирма Bell Laboratories прекратила свое участие в проекте.

По окончании работы над проектом Multics сотрудники Исследовательского центра по информатике фирмы Bell Laboratories остались без "достаточно интерактивного вычислительного средства" [Ritchie 84a]. Пытаясь усовершенствовать среду программирования, Кен Томпсон, Дэннис Ричи и другие набросали на бумаге проект файловой системы, получивший позднее дальнейшее развитие в ранней версии файловой системы UNIX. Томпсоном были написаны программы, имитирующие поведение предложенной файловой системы в режиме подкачки данных по запросу, им было даже создано простейшее ядро операционной системы для ЭВМ GE 645. В то же время он написал на Фортране игровую программу "Space Travel" ("Космическое путешествие") для системы GECOS (Honeywell 635), но программа не смогла удовлетворить пользователей, поскольку управлять "космическим кораблем" оказалось сложно, кроме того, при загрузке программа занимала много места. Позже Томпсон обнаружил малоиспользуемый компьютер PDP-7, оснащенный хорошим графическим дисплеем и имеющий дешевое машинное время. Создавая программу "Космическое путешествие" для PDP-7, Томпсон получил возможность изучить машину, однако условия разработки программ потребовали использования кросс-ассемблера для трансляции программы на машине с системой GECOS и использования перфоленты для ввода в PDP-7. Для того, чтобы улучшить условия разработки, Томпсон и Ричи выполнили на PDP-7 свой проект системы, включивший первую версию файловой системы UNIX, подсистему управления процессами и небольшой набор утилит. В конце концов, новая система больше не нуждалась в поддержке со стороны системы GECOS в качестве операционной среды разработки и могла поддерживать себя сама. Новая система получила название UNIX, по сходству с Multics его придумал еще один сотрудник Исследовательского центра по информатике Брайан Керниган.

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

создано несколько вариантов базисной системы. За период между 1977 и 1982 годом фирма Bell Laboratories объединила несколько вариантов, разработанных в корпорации AT&T, в один, получивший коммерческое название UNIX версия III. В дальнейшем фирма Bell Laboratories добавила в версию III несколько новых особенностей, назвав новый продукт UNIX версия V , и эта версия стала официально распространяться корпорацией AT&T с января 1983 года. В то же время сотрудники Калифорнийского университета в Бэркли разработали вариант системы UNIX, получивший название BSD 4.3 для машин серии VAX и отличающийся некоторыми новыми, интересными особенностями. Основное внимание в этой книге концентрируется на описании системы UNIX версии V, однако время от времени мы будем касаться и особенностей системы BSD.

К началу 1984 года система UNIX была уже инсталлирована приблизительно на 100000 машин по всему миру, при чем на машинах с широким диапазоном вычислительных возможностей - от микропроцессоров до больших ЭВМ - и разных изготовителей. Ни о какой другой операционной системе нельзя было бы сказать того же. Популярность и успех системы UNIX объяснялись несколькими причинами:

• Система написана на языке высокого уровня, благодаря чему ее легко читать, понимать, изменять и переносить на другие машины. По оценкам, сделанным Ричи, первый вариант системы на Си имел на 20-40 % больший объем и работал медленнее по сравнению с вариантом на ассемблере, однако преимущества использования языка высокого уровня намного перевешивают недостатки (см. [Ritchie 78b], стр. 1965).
• Наличие довольно простого пользовательского интерфейса, в котором имеется возможность предоставлять все необходимые пользователю услуги.
• Наличие элементарных средств, позволяющих создавать сложные программы из более простых.
• Наличие иерархической файловой системы, легкой в сопровождении и эффективной в работе.
• Обеспечение согласования форматов в файлах, работа с последовательным потоком байтов, благодаря чему облегчается чтение прикладных программ.
• Наличие простого, последовательного интерфейса с периферийными устройствами.
• Система является многопользовательской, многозадачной; каждый пользователь может одновременно выполнять несколько процессов.
• Архитектура машины скрыта от пользователя, благодаря этому облегчен процесс написания программ, работающих на различных конфигурациях аппаратных средств.

Простота и последовательность вообще отличают систему UNIX и объясняют большинство из вышеприведенных доводов в ее пользу.

Хотя операционная система и большинство команд написаны на Си, система UNIX поддерживает ряд других языков, таких как Фортран, Бейсик, Паскаль, Ада, Кобол, Лисп и Пролог. Система UNIX может поддерживать любой язык программирования, для которого имеется компилятор или интерпретатор, и обеспечивать системный интерфейс, устанавливающий соответствие между пользовательскими запросами к операционной системе и набором запросов, принятых в UNIX.

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

+--------------------------------------------+

¦ ¦ Другие прикладные программы ¦

¦ +----+-----------------------------+ ¦

¦ ¦ cpp¦ nroff ¦ sh ¦ who ¦ ¦ ¦

¦ ¦ +------------------------¦ a. ¦ ¦

¦ +----¦ Ядро ¦out ¦ ¦

¦ ¦ ¦ +--------------+ ¦ ¦ ¦

¦ ¦comp¦ ¦ ¦ +----¦ ¦

¦ ¦ ¦ ¦ Технические ¦ ¦ ¦ ¦

¦ cc +----¦ ¦ ¦ ¦date¦ ¦

¦ ¦ ¦ ¦ средства ¦ ¦ ¦ ¦

¦ ¦ as ¦ ¦ ¦ +----¦ ¦

¦ ¦ ¦ +--------------+ ¦ ¦ ¦

¦ +----¦ ¦ ¦ ¦

¦ ¦ +------------------------¦ wc ¦ ¦

¦ ¦ ld ¦ vi ¦ ed ¦ grep ¦ ¦ ¦

¦ +----+-----------------------------+ ¦

¦ ¦ Другие прикладные программы ¦

+--------------------------------------------+

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

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

Многие прикладные подсистемы и программы, составляющие верхний уровень системы, такие как командный процессор shell, редакторы, SCCS (система обработки исходных текстов программ) и пакеты программ подготовки документации, постепенно становятся синонимом понятия "система UNIX". Однако все они пользуются услугами программ нижних уровней и в конечном счете ядра с помощью набора обращений к операционной системе. В версии V принято 64 типа обращений к операционной системе, из которых немногим меньше половины используются часто. Они имеют несложные параметры, что облегчает их использование, предоставляя при этом большие возможности пользователю. Набор обращений к операционной системе вместе с реализующими их внутренними алгоритмами составляют "тело" ядра, в связи с чем рассмотрение операционной системы UNIX в этой книге сводится к подробному изучению и анализу обращений к системе и их взаимодействия между собой. Короче говоря, ядро реализует функции, на которых основывается выполнение всех прикладных программ в системе UNIX, и им же определяются эти функции. В книге часто употребляются термины "система UNIX", "ядро" или "система", однако при этом имеется ввиду ядро операционной системы UNIX, что и должно вытекать из контекста.

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

Файловая система UNIX характеризуется:

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

Файловая система организована в виде дерева с одной исходной вершиной, которая называется корнем (записывается: "/"); каждая вершина в древовидной структуре файловой системы, кроме листьев, является каталогом файлов, а фай

/

+--------------------------+-----------------------------+

¦ ¦ ¦ ¦ ¦ ¦

fsl bin etc usr unix dev

+---+ +---+---+ ¦ +---+ +---+

¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦

mjb maury sh date who passwd src bin tty00 tty01

¦

¦

cmd

+-------+

¦ ¦

date.c who.c

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

Программы, выполняемые под управлением системы UNIX, не содержат никакой информации относительно внутреннего формата, в котором ядро хранит файлы данных, данные в программах представляются как бесформатный поток байтов. Программы могут интерпретировать поток байтов по своему желанию, при этом любая интерпретация никак не будет связана с фактическим способом хранения данных в операционной системе. Так, синтаксические правила, определяющие задание метода доступа к данным в файле, устанавливаются системой и являются едиными для всех программ, однако семантика данных определяется конкретной программой. Например, программа форматирования текста troff ищет в конце каждой строки текста символы перехода на новую строку, а программа учета системных ресурсов acctcom работает с записями фиксированной длины. Обе программы пользуются одними и теми же системными средствами для осуществления доступа к данным в файле как к потоку байтов, и внутри себя преобразуют этот поток по соответствующему формату. Если любая из программ обнаружит, что формат данных неверен, она принимает соответствующие меры.

Каталоги похожи на обычные файлы в одном отношении; система представляет информацию в каталоге набором байтов, но эта информация включает в себя имена файлов в каталоге в объявленном формате для того, чтобы операционная система и программы, такие как ls (выводит список имен и атрибутов файлов), могли их обнаружить.

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

copy oldfile newfile

Операции open и creat возвращают целое значение, являющееся дескриптором файла и используемое программой в последующих ссылках на файлы. После этого программа вызывает подпрограмму copy, выполняющую в цикле операцию read (читать), по которой производится чтение в буфер порции символов из существующего файла, и операцию write (писать) для записи информации в новый файл. Операция read каждый раз возвращает количество прочитанных байтов (0 - если достигнут конец файла). Цикл завершается, если достигнут конец файла или если произошла ошибка при выполнении операции read (отсутствует контроль возникновения ошибок при выполнении операции write). Затем управление из подпрограммы copy возвращается в основную программу и запускается операция exit с кодом состояния 0 в качестве параметра, что указывает на успешное завершение выполнения программы.

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

copy copy.c newcopy.c

copy copy newcopy

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

copy . dircontents

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

+------------------------------------------------------------+

¦ #include <fcntl.h> ¦

¦ char buffer[2048]; ¦

¦ ¦

¦ main(argc,argv) ¦

¦ int argc; ¦

¦ char *argv[]; ¦

¦ { ¦

¦ int fdold,fdnew; ¦

¦ ¦

¦ if (argc != 3) ¦

¦ { ¦

¦ printf("need 2 arguments for copy program\n); ¦

¦ exit(1); ¦

¦ } ¦

¦ файл только для ¦

¦ чтения */ ¦

¦ 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, завершая работу только в том случае, если пользователь нажмет.<Ctrl/d>. Похожая форма запуска программы:

copy /dev/tty /dev/tty

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

Программой называется исполняемый файл, а процессом называется последовательность операций программы или часть программы при ее выполнении. В системе 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 не включает в себя многие функции, являющиеся частью "ядра" в других системах. Такие функции, и среди них компиляторы и редакторы, в системе UNIX являются программами пользовательского уровня. Наиболее характерным примером подобной программы может служить командный процессор shell, с которым обычно взаимодействуют пользователи после входа в систему. Shell интерпретирует первое слово командной строки как имя команды: во многих командах, в том числе и в командах fork (породить новый процесс) и exec (выполнить порожденный процесс), сама команда ассоциируется с ее именем, все остальные слова в командной строке трактуются как параметры команды.

Командный процессор shell ищет имена команд в указанном наборе каталогов, который можно изменить по желанию пользователя, вызвав shell. Shell обычно исполняет команду синхронно, с ожиданием завершения выполнения команды прежде, чем считать следующую командную строку. Тем не менее, допускается и асинхронное исполнение, когда очередная командная строка считывается и исполняется, не дожидаясь завершения выполнения предыдущей команды. О командах, выполняемых асинхронно, говорят, что они выполняются на фоне других команд. Например, ввод команды who вызывает выполнение системой программы, хранящейся в файле /bin/who и осуществляющей вывод списка пользователей, которые в настоящий момент работают с системой. Пока команда who выполняется, командный процессор shell ожидает завершения ее выполнения и только затем запрашивает у пользователя следующую команду. Если же ввести команду who & система выполнит программу who на фоне и shell готов немедленно принять следующую команду.

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

cd /usr/src/uts

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

cd ../..

делает текущим каталог, который на две вершины "ближе" к корню (корневому каталогу): параметр ".." относится к каталогу, являющемуся родительским для текущего.

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

ls

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

ls > output

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

mail mjb < letter

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

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

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

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

Основные различия между этими двумя режимами:

ПРОЦЕССЫ

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

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

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

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

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

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

+------------------------------+ ^

¦ Машинные сбои ¦ ¦

+------------------------------¦ ¦

¦ Системные часы ¦ Высокий приоритет

+------------------------------¦ ¦

¦ Диск ¦ ¦

+------------------------------¦ ¦

¦ Сетевое оборудование ¦ ¦

+------------------------------¦ ¦

¦ Терминалы ¦ Низкий приоритет

+------------------------------¦ ¦

¦ Программные прерывания ¦ ¦

+------------------------------+ v

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

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

словно на физической машине не будет выполняться параллельно с транслируемой ни одна другая программа.

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

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

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

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

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

Схема на Рисунке 2.1 имеет три уровня: уровень пользователя, уровень ядра и уровень аппаратуры. Обращения к операционной системе и библиотеки составляют границу между пользовательскими программами и ядром, проведенную на Рисунке 1.1. Обращения к операционной системе выглядят так же, как обычные вызовы функций в программах на языке Си, и библиотеки устанавливают соответствие между этими вызовами функций и элементарными системными операциями, о чем более подробно см. в главе 6. При этом программы на ассемблере могут обращаться к операционной системе непосредственно, без использования библиотеки системных вызовов. Программы часто обращаются к другим библиотекам, таким как библиотека стандартных подпрограмм ввода-вывода, достигая тем самым более полного использования системных услуг. Для этого во время компиляции библиотеки связываются с программами и частично включаются в программу пользователя. Далее мы проиллюстрируем эти моменты на примере.

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

программы пользователя

^

¦ +----------------------+

точка пере- ¦ ¦ библиотеки ¦

сечения ·········¦······· +----------------------+

· ¦ · ^

Уровень пользователя · ¦ · ¦

--------------------------¦---------------------¦----------------Уровень ядра

v v

+---------------------------------------------------+

¦ ^ обращения к операционной системе ^ ¦

+------+------------------------------------+-------+

¦ ¦

+-----------------+---------------+ +----------------+---------+

¦ v ¦ ¦ v ¦

¦ ¦ ¦ ¦

¦ подсистема управле- ¦ ¦ ............¦

¦ ния файлами ¦ ¦ . взаимо- .¦

¦ <---+-+ ¦ . действие .¦

¦ ¦ ¦ ¦ . процессов.¦

¦ ^ ^ ¦ ¦ ¦ подсистема ............¦

¦ ¦ ¦ ¦ ¦ ¦ ............¦

+-------+--------------+----------+ ¦ ¦ . планиров-.¦

¦ v +-+> управления . щик .¦

¦ +--------------+ ¦ ............¦

¦ ¦ буфер сверх- ¦ ¦ ............¦

¦ ¦ оперативной ¦ ¦ процессами . распреде-.¦

¦ ¦ памяти (кеш) ¦ ¦ . ление .¦

¦ ^ ¦ ^ ............¦

¦ ¦ ¦ ¦ ¦

¦ v +-------+------------------+

+-------+----------------------+ ¦

¦ v . ¦ ¦

¦ символ . блок ¦ ¦

¦ . ¦ ¦

+------------------------------¦ ¦

¦ ¦ ¦

¦ драйверы устройств ¦ ¦

¦ ^ ¦ ¦

+--------------+---------------+ ¦

¦ ¦

+--------------+------------------------------+------------------+

¦ v аппаратный контроль v ¦

+----------------------------------------------------------------+

Уровень ядра

аппаратуры

+----------------------------------------------------------------+

¦ технические средства (аппаратура) ¦

+----------------------------------------------------------------+

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

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

Подсистема управления файлами также непосредственно взаимодействует с драйверами устройств "неструктурированного" ввода-вывода, без вмешательства буферного механизма. К устройствам неструктурированного ввода-вывода, иногда именуемым устройствами посимвольного ввода-вывода (текстовыми), относятся устройства, отличные от устройств ввода-вывода блоками.

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

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

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

Наконец, аппаратный контроль отвечает за обработку прерываний и за связь с машиной. Такие устройства, как диски и терминалы, могут прерывать работу центрального процессора во время выполнения процесса. При этом ядро системы после обработки прерывания может возобновить выполнение прерванного процесса. Прерывания обрабатываются не самими процессами, а специальными функциями ядра системы, перечисленными в контексте выполняемого процесса.

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

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

open("/fs2/mjb/rje/sourcefile", 1);

ядро системы возвращает индекс для файла "/fs2/mjb/rje/sourcefile". Если процесс создает новый файл, ядро присваивает этому файлу неиспользуемый индекс. Индексы хранятся в файловой системе (и это мы еще увидим), однако при обработке файлов ядро заносит их в таблицу индексов в оперативной памяти.

Пользовательская таблица дескрип- Таблица

Таблица торов файла файлов индексов

+---------+ +-----+ +-----+

¦ - + - + ¦ ¦ ¦ ¦

+---------¦ ¦ ¦ ¦ ¦

¦ - + + ¦ ¦ ¦ ¦ ¦

+---------¦ ¦ ¦ +-----¦

¦ - ++¦ + - - - ->+-----¦ + - - - ->¦ ¦

+---------¦ + - - - - ->¦ - + - + +-----¦

¦ ¦¦ +-----¦ ¦ ¦

¦ ¦+ - + ¦ ¦ ¦ ¦

¦ ¦ ¦ +-----¦ + - - - ->¦ ¦

¦ ¦ +- - - ->¦ - + - + +-----¦

¦ ¦ +-----¦ ¦ ¦

¦ ¦ ¦ ¦ ¦ ¦

+---------+ +-----+ +-----+

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

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

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

+---------------------------····----------------····------+

¦ ¦ ¦ ¦ ¦

+---------------------------····----------------····------+

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

загрузки блок блоки

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

Файловая система имеет следующую структуру (Рисунок 2.3).

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

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

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

Пользователь, транслируя исходный текст программы, создает исполняемый файл, который состоит из нескольких частей:

• набора "заголовков", описывающих атрибуты файла,
• текста программы,
• представления на машинном языке данных, имеющих начальные значения при запуске программы на выполнение, и указания на то, сколько пространства памяти ядро системы выделит под неинациализированные данные, так называемые bss (ядро устанавливает их в 0 в момент запуска),
• других секций, таких как информация символических таблиц.

Ядро загружает исполняемый файл в память при выполнении системной операции exec, при этом загруженный процесс состоит по меньшей мере из трех частей, так называемых областей: текста, данных и стека. Области текста и данных корреспондируют с секциями текста и bss-данных исполняемого файла, а область стека создается автоматически и ее размер динамически устанавливается ядром системы во время выполнения. Стек состоит из логических записей активации, помещаемых в стек при вызове функции и выталкиваемых из стека при возврате управления в вызвавшую процедуру; специальный регистр, именуемый указателем вершины стека, показывает текущую глубину стека. Запись активации включает параметры передаваемые функции, ее локальные переменные, а также данные, необходимые для восстановления предыдущей записи активации, в том числе значения счетчика команд и указателя вершины стека в момент вызова функции. Текст программы включает

Стек задачи Направление Стек ядра

¦ Локальные ¦ ^ ¦ ¦

¦ переменные ¦ ¦ ¦ ^ ¦

¦ (не показаны)¦ ¦ ¦ . ¦

¦--------------¦ ¦ ¦ . ¦

¦Адрес записи 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. Стеки задачи и ядра для программы копирования.

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

ме copy. Подробно алгоритмы выполнения системной операции write будут описаны в последующих разделах.

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

таблицу областей, используемых процессами, к собственно таблице областей) позволяет независимым процессам совместно использовать области. Когда процесс запускает системную операцию exec, ядро системы выделяет области под ее текст, данные и стек, освобождая старые области, которые использовались процессом. Если процесс запускает операцию fork, ядро удваивает размер адресного пространства старого процесса, позволяя процессам совместно использовать области, когда это возможно, и, с другой стороны, производя физическое копирование. Если процесс запускает операцию exit, ядро освобождает области, которые использовались процессом. На Рисунке 2.5 изображены информационные структуры, связанные с запуском процесса. Таблица процессов ссылается на промежуточную таблицу областей, используемых процессом, в которой содержатся указатели на записи в собственно таблице областей, соответствующие областям для текста, данных и стека процесса.

Запись в таблице процессов и часть адресного пространства задачи, выделенная процессу, содержат управляющую информацию и данные о состоянии процесса. Это адресное пространство является расширением соответствующей записи в таблице процессов, различия между данными объектами будут рассмотрены в главе 6. В качестве полей в таблице процессов, которые рассматриваются в последующих разделах, выступают:

• поле состояния,
• идентификаторы, которые характеризуют пользователя, являющегося владельцем процесса (код пользователя или UID),
• значение дескриптора события, когда процесс приостановлен (находится в состоянии "сна").

Адресное пространство задачи, выделенное процессу, содержит описывающую процесс информацию, доступ к которой должен обеспечиваться только во время выполнения процесса. Важными полями являются:

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

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

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

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

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

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

Поскольку процессор в каждый момент времени выполняет только один процесс, в состояниях 1 и 2 может находиться самое большее один процесс. Эти два состояния соответствуют двум режимам выполнения, режиму задачи и режиму ядра.

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

разрешен, если существует дуга из первого состояния во второе. Несколько дуг может выходить из одного состояния, однако процесс переходит только по одной из них в зависимости от того, какое событие произошло в системе. На Рисунке 2.6 представлена диаграмма переходов для состояний, перечисленных выше.

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

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

В качестве примера рассмотрим программу (Рисунок 2.7) включения информационной структуры, чей адрес содержится в указателе bp1, в список с использованием указателей после структуры, чей адрес содержится в bp. Если система разрешила переключение контекста при выполнении ядром фрагмента программы, возможно возникновение следующей ситуации. Предположим, ядро выполняет программу

запуск +-------+

в режи- ¦ ¦

ме за- ¦ 1 ¦

дачи ¦ ¦

+-------+

обращение ¦ ^ возврат

к системе ¦ ¦

или пре- ¦ ¦

рывание ¦ ¦

v ¦

запуск +-------+

в режи- ¦ ¦<---------+ прерывание,

ме яд- ¦ 2 ¦ ¦ возврат из

ра ¦ ¦<---------+ прерывания

+-------+

приоста-¦ ^ процесс пла

+-------+ нов ¦ ¦ нирования +-------+

ожидание ¦ ¦<----------+ +------------¦ ¦ готовность

("сон")¦ 4 +--------------------------->¦ 3 ¦ к выполнению

+-------+ пробуждение +-------+

переключение

контекста допустимо

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

до комментариев и затем осуществляет переключение контекста. Список с использованием сдвоенных указателей имеет противоречивый вид: структура 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. Список с указателями, некорректный из-за переключения контекста

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

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

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

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

Алгоритмы перехода в состояние "сна" и пробуждения более подробно будут рассмотрены в главе 6. Тем временем они будут считаться "неделимыми". Процесс переходит в состояние "сна" мгновенно и находится в нем до тех пор, пока не будет "разбужен". После того, как он приостанавливается, ядро системы начинает планировать выполнение следующего процесса и переключает контекст на него.

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

Время Процесс A Процесс B Процесс C

+------------------------------------------------------------ ¦ Буфер заблокирован

¦ Приостановлен

¦ . Буфер заблокирован

¦ . Приостановлен

¦ . . Приостановлен

¦ +----------------------------------------------------------+

¦ ¦Буфер разблокирован Пробуждение всех "спящих" процессов¦

¦ +----------------------------------------------------------+

¦ Готов к Готов к Готов к

¦ . .

¦ . Запущен .

¦ . Буфер разблокирован .

¦ . Блокировка буфера .

¦ . . .

¦ . Приостановка по .

¦ . произвольной причине .

¦ . . .

¦ Запущен . .

¦ Буфер заблокирован . .

¦ Приостановка . .

¦ . . Запущен

¦ . . Буфер заблокирован

¦ . . Приостановка

¦ . Пробуждение .

¦ . Снятие блокировки .

¦ . буфера .

¦ Готов к Пробуждение всех Готов к

¦ выполнению "спящих" процессов выполнению

¦

v Переключение контекста

Запущен

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

блокировкой

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

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

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

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

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. Что произошло бы в том случае, если ядро попыталось бы возобновить выполнение всех процессов, приостановленных по событию, но в системе не было

бы к этому моменту ни одного такого процесса ?