Страница:
ляется под процесс. Если процесс открывает или создает файл, ядро выделяет в
каждой таблице элемент, корреспондирующий с индексом файла. Элементы в этих
трех структурах - в пользовательской таблице дескрипторов файла, в таблице
файлов и в таблице индексов - хранят информацию о состоянии файла и о досту-
пе пользователей к нему. В таблице файлов хранится смещение в байтах от на-
чала файла до того места, откуда начнет выполняться следующая команда поль-
зователя read или write,
Пользовательская
таблица дескрип- Таблица файлов Таблица индексов
торов файла
+---------+ +-----+ +-----+
| | | | | |
+---------+ | | | |
| --+---+ | | +-----+
+---------+ | | | +-------->| |
| --+-+ | +-----+ | +-----+
+---------+ | +-------->| --+---+ | |
| | | +-----+ | |
| | +--+ | ... | +-----+
| | | +-----+ +-------->| |
| | +------->| --+---+ +-----+
| | +-----+ | |
| | | | | |
+---------+ +-----+ +-----+
Рисунок 2.2. Таблицы файлов, дескрипторов файла и индексов
а также информация о правах доступа к открываемому процессу. Таблица деск-
рипторов файла идентифицирует все открытые для процесса файлы. На Рисунке
2.2 показаны эти таблицы и связи между ними. В системных операциях open (от-
крыть) и creat (создать) ядро возвращает дескриптор файла, которому соответ-
ствует указатель в таблице дескрипторов файла. При выполнении операций read
(читать) и write (писать) ядро использует дескриптор файла для входа в таб-
лицу дескрипторов и, следуя указателям на таблицу файлов и на таблицу индек-
сов, находит информацию в файле. Более подробно эти информационные структуры
рассматриваются в главах 4 и 5. Сейчас достаточно сказать, что использование
этих таблиц обеспечивает различную степень разделения доступа к файлу.
Обычные файлы и каталоги хранятся в системе UNIX на устройствах вво-
да-вывода блоками, таких как магнитные ленты или диски. Поскольку существует
25
некоторое различие во времени доступа к этим устройствам, при установке сис-
темы UNIX на лентах размещают файловые системы. С годами бездисковые автома-
тизированные рабочие места станут общим случаем, и файлы будут располагаться
в удаленной системе, доступ к которой будет осуществляться через сеть (см.
главу 13). Для простоты, тем не менее, в последующем тексте подразумевается
использование дисков. В системе может быть несколько физических дисков, на
каждом из которых может размещаться одна и более файловых систем. Разбивка
диска на несколько файловых систем облегчает администратору управление хра-
нимыми данными. На логическом уровне ядро имеет дело с файловыми системами,
а не с дисками, при этом каждая система трактуется как логическое устройст-
во, идентифицируемое номером. Преобразование адресов логического устройства
(файловой системы) в адреса физического устройства (диска) и обратно выпол-
няется дисковым драйвером. Термин "устройство" в этой книге используется для
обозначения логического устройства, кроме специально оговоренных случаев.
Файловая система состоит из последовательности логических блоков длиной
512, 1024, 2048 или другого числа байт, кратного 512, в зависимости от реа-
лизации системы. Размер логического блока внутри одной файловой системы пос-
тоянен, но может варьироваться в разных файловых системах в данной конфигу-
рации. Использование логических блоков большого размера увеличивает скорость
передачи данных между диском и памятью, поскольку ядро сможет передать боль-
ше информации за одну дисковую операцию, и сокращает количество продолжи-
тельных операций. Например, чтение 1 Кбайта с диска за одну операцию осущес-
твляется быстрее, чем чтение 512 байт за две. Однако, если размер логическо-
го блока слишком велик, полезный объем памяти может уменьшиться, это будет
показано в главе 5. Для простоты термин "блок" в этой книге будет использо-
ваться для обозначения логического блока, при этом подразумевается логичес-
кий блок размером 1 Кбайт, кроме специально оговоренных случаев.
+---------+---------+-------------------+-----------------+
| блок | супер- | список | информационные |
|загрузки | блок | индексов | блоки |
+---------+---------+-------------------+-----------------+
Рисунок 2.3. Формат файловой системы
Файловая система имеет следующую структуру (Рисунок 2.3).
* Блок загрузки располагается в начале пространства, отведенного под файло-
вую систему, обычно в первом секторе, и содержит программу начальной заг-
рузки, которая считывается в машину при загрузке или инициализации опера-
ционной системы. Хотя для запуска системы требуется только один блок заг-
рузки, каждая файловая система имеет свой (пусть даже пустой) блок загруз-
ки.
* Суперблок описывает состояние файловой системы - какого она размера,
сколько файлов может в ней храниться, где располагается свободное прост-
ранство, доступное для файловой системы, и другая информация.
* Список индексов в файловой системе располагается вслед за суперблоком. Ад-
министраторы указывают размер списка индексов при генерации файловой сис-
темы. Ядро операционной системы обращается к индексам, используя указатели
в списке индексов. Один из индексов является корневым индексом файловой
системы: это индекс, по которому осуществляется доступ к структуре катало-
гов файловой системы после выполнения системной операции mount (монтиро-
вать) (раздел 5.14).
* Информационные блоки располагаются сразу после списка индексов и содержат
данные файлов и управляющие данные. Отдельно взятый информационный блок
может принадлежать одному и только одному файлу в файловой системе.
26
В этом разделе мы рассмотрим более подробно подсистему управления про-
цессами. Даются разъяснения по поводу структуры процесса и некоторых инфор-
мационных структур, используемых при распределении памяти под процессы. За-
тем дается предварительный обзор диаграммы состояния процессов и затрагива-
ются различные вопросы, связанные с переходами из одного состояния в другое.
Процессом называется последовательность операций при выполнении програм-
мы, которые представляют собой наборы байтов, интерпретируемые центральным
процессором как машинные инструкции (т.н. "текст"), данные и стековые струк-
туры. Создается впечатление, что одновременно выполняется множество процес-
сов, поскольку их выполнение планируется ядром, и, кроме того, несколько
процессов могут быть экземплярами одной программы. Выполнение процесса зак-
лючается в точном следовании набору инструкций, который является замкнутым и
не передает управление набору инструкций другого процесса; он считывает и
записывает информацию в раздел данных и в стек, но ему недоступны данные и
стеки других процессов. Одни процессы взаимодействуют с другими процессами и
с остальным миром посредством обращений к операционной системе.
С практической точки зрения процесс в системе UNIX является объектом,
создаваемым в результате выполнения системной операции fork. Каждый процесс,
за исключением нулевого, порождается в результате запуска другим процессом
операции fork. Процесс, запустивший операцию fork, называется родительским,
а вновь созданный процесс - порожденным. Каждый процесс имеет одного родите-
ля, но может породить много процессов. Ядро системы идентифицирует каждый
процесс по его номеру, который называется идентификатором процесса (PID).
Нулевой процесс является особенным процессом, который создается "вручную" в
результате загрузки системы; после порождения нового процесса (процесс 1)
нулевой процесс становится процессом подкачки. Процесс 1, известный под име-
нем init, является предком любого другого процесса в системе и связан с каж-
дым процессом особым образом, описываемым в главе 7.
Пользователь, транслируя исходный текст программы, создает исполняемый
файл, который состоит из нескольких частей:
* набора "заголовков", описывающих атрибуты файла,
* текста программы,
* представления на машинном языке данных, имеющих начальные
значения при запуске программы на выполнение, и указания на то, сколько
пространства памяти ядро системы выделит под неинациализированные данные,
так называемые bss (*) (ядро устанавливает их в 0 в момент запуска),
* других секций, таких как информация символических таблиц.
Для программы, приведенной на Рисунке 1.3, текст исполняемого файла
представляет собой сгенерированный код для функций main и copy, к определен-
ным данным относится переменная version (вставленная в программу для того,
чтобы в последней имелись некоторые определенные данные), а к неопределенным
- массив buffer. Компилятор с языка Си для системы версии V создает отдельно
текстовую секцию по умолчанию, но не исключается возможность включения инст-
рукций программы и в секцию данных, как в предыдущих версиях системы.
Ядро загружает исполняемый файл в память при выполнении системной опера-
ции exec, при этом загруженный процесс состоит по меньшей мере из трех час-
тей, так называемых областей: текста, данных и стека. Области текста и дан-
ных корреспондируют с секциями текста и bss-данных исполняемого файла, а об-
ласть стека создается автоматически и ее размер динамически устанавливается
ядром системы во время выполнения. Стек состоит из логических записей акти-
вации, помещаемых в стек при вызове функции и выталкиваемых из стека при
возврате управления в вызвавшую процедуру; специальный регистр, именуемый
указателем вершины стека, показывает текущую глубину стека. Запись активации
включает параметры передавае-
------------------------------------------------
(*) Сокращение bss имеет происхождение от ассемблерного псевдооператора для
машины IBM 7090 и расшифровывается как "block started by symbol" ("блок, на-
чинающийся с символа").
27
мые функции, ее локальные переменные, а также данные, необходимые для восс-
тановления предыдущей записи активации, в том числе значения счетчика команд
и указателя вершины стека в момент вызова функции. Текст программы включает
Стек задачи Направление Стек ядра
+--------------+ увеличения стека +------------------+
| Локальные | ^ | |
| переменные | | | ^ |
| (не показаны)| | | . |
|--------------| | | . |
|Адрес записи 2| | | . |
|--------------| | | . |
|Адрес возврата| | | . |
| после вызова | | | . |
| write | | | . |
|--------------| | | . |
|параметры, пе-| | | . |
| редаваемые | | | . |
| write | | | . |
|(new, buffer, | | | v |
| count) | Запись 3 | |
+--------------+ call write() Запись 3 +------------------+
| Локальные | | Локальные |
| переменные | | переменные |
| (count) | | |
|--------------| |------------------|
|Адрес записи 1| | Адрес записи 1 |
|--------------| |------------------|
|Адрес возврата| | Адрес возврата |
| после вызова | | после вызова |
| copy | | func2 |
|--------------| |------------------|
|параметры, пе-| | параметры, пере- |
| редаваемые | | даваемые функции |
| copy | | ядра func2 |
| (old, new) | Запись 2 Запись 2 | |
+--------------+ call copy() call func2() +------------------+
| Локальные | | Локальные |
| переменные | | переменные |
|(fdold, fdnew)| | |
|--------------| |------------------|
|Адрес записи 0| | Адрес записи 0 |
|--------------| |------------------|
|Адрес возврата| | Адрес возврата |
| после вызова | | после вызова |
| main | | func1 |
|--------------| |------------------|
|параметры, пе-| | параметры, пере- |
| редаваемые | | даваемые функции |
| main | | ядра func1 |
| (argc, argv) | Запись 1 Запись 1 | |
+--------------+ call main() call func1() +------------------+
Запись 0 Запись 0
Старт Интерфейс
обращений к операционной системе
Рисунок 2.4. Стеки задачи и ядра для программы копирования.
28
последовательности команд, управляющие увеличением стека, а ядро системы вы-
деляет, если нужно, место под стек. В программе на Рисунке 1.3 параметры
argc и argv, а также переменные fdold и fdnew, содержащиеся в вызове функции
main, помещаются в стек, как только встретилось обращение к функции main
(один раз в каждой программе, по условию), так же и параметры old и new и
переменная count, содержащиеся в вызове функции copy, помещаются в стек в
момент обращения к указанной функции.
Поскольку процесс в системе UNIX может выполняться в двух режимах, режи-
ме ядра или режиме задачи, он пользуется в каждом из этих режимов отдельным
стеком. Стек задачи содержит аргументы, локальные переменные и другую инфор-
мацию относительно функций, выполняемых в режиме задачи. Слева на Рисунке
2.4 показан стек задачи для процесса, связанного с выполнением системной
операции write в программе copy. Процедура запуска процесса (включенная в
библиотеку) обратилась к функции main с передачей ей двух параметров, помес-
тив в стек задачи запись 1; в записи 1 есть место для двух локальных пере-
менных функции main. Функция main затем вызывает функцию copy с передачей ей
двух параметров, old и new, и помещает в стек задачи запись 2; в записи 2
есть место для локальной переменной count. Наконец, процесс активизирует
системную операцию write, вызвав библиотечную функцию с тем же именем. Каж-
дой системной операции соответствует точка входа в библиотеке системных опе-
раций; библиотека системных операций написана на языке ассемблера и включает
специальные команды прерывания, которые, выполняясь, порождают "прерывание",
вызывающее переключение аппаратуры в режим ядра. Процесс ищет в библиотеке
точку входа, соответствующую отдельной системной операции, подобно тому, как
он вызывает любую из функций, создавая при этом для библиотечной функции за-
пись активации. Когда процесс выполняет специальную инструкцию, он переклю-
чается в режим ядра, выполняет операции ядра и использует стек ядра.
Стек ядра содержит записи активации для функций, выполняющихся в режиме
ядра. Элементы функций и данных в стеке ядра соответствуют функциям и дан-
ным, относящимся к ядру, но не к программе пользователя, тем не менее, конс-
трукция стека ядра подобна конструкции стека задачи. Стек ядра для процесса
пуст, если процесс выполняется в режиме задачи. Справа на Рисунке 2.4 предс-
тавлен стек ядра для процесса выполнения системной операции write в програм-
промежуточная
таблица облас- таблица
тей процессов областей
+---------------------+ +-------------+ +------------+
| часть адресного про-| | | | |
| странства задачи, | | | | |
| выделенная процессу | | | | |
+---------------------+ +-------------+ +------------+
^ +--+-> ---+-----+-> |
| | +-------------+ +-----+------+
+----------+----------+ +--+-> ---+--+ | | |
| | | | +-------------+ | | | |
| | | | | | | +-----+------+
+----------+----------+ | | | +--+-> | |
| v -----+--+ | | +-----+---+--+
+---------------------+ | | | | | |
| | +-------------+ +-----+---+--+
| | | |
+---------------------+ | |
таблица процессов +-------------------------+---+--+
| оперативная память v v |
+--------------------------------+
Рисунок 2.5. Информационные структуры для процессов
29
ме copy. Подробно алгоритмы выполнения системной операции write будут описа-
ны в последующих разделах.
Каждому процессу соответствует точка входа в таблице процессов ядра,
кроме того, каждому процессу выделяется часть оперативной памяти, отведенная
под задачу пользователя. Таблица процессов включает в себя указатели на про-
межуточную таблицу областей процессов, точки входа в которую служат в качес-
тве указателей на собственно таблицу областей. Областью называется непрерыв-
ная зона
адресного пространства, выделяемая процессу для размещения текста, данных и
стека. Точки входа в таблицу областей описывают атрибуты области, как напри-
мер, хранятся ли в области текст программы или данные, закрытая ли эта об-
ласть или же совместно используемая, и где конкретно в памяти размещается
содержимое области. Внешний уровень косвенной адресации (через промежуточную
таблицу областей, используемых процессами, к собственно таблице областей)
позволяет независимым процессам совместно использовать области. Когда про-
цесс запускает системную операцию exec, ядро системы выделяет области под ее
текст, данные и стек, освобождая старые области, которые использовались про-
цессом. Если процесс запускает операцию fork, ядро удваивает размер адресно-
го пространства старого процесса, позволяя процессам совместно использовать
области, когда это возможно, и, с другой стороны, производя физическое копи-
рование. Если процесс запускает операцию exit, ядро освобождает области, ко-
торые использовались процессом. На Рисунке 2.5 изображены информационные
структуры, связанные с запуском процесса. Таблица процессов ссылается на
промежуточную таблицу областей, используемых процессом, в которой содержатся
указатели на записи в собственно таблице областей, соответствующие областям
для текста, данных и стека процесса.
Запись в таблице процессов и часть адресного пространства задачи, выде-
ленная процессу, содержат управляющую информацию и данные о состоянии про-
цесса. Это адресное пространство является расширением соответствующей записи
в таблице процессов, различия между данными объектами будут рассмотрены в
главе 6. В качестве полей в таблице процессов, которые рассматриваются в
последующих разделах, выступают:
* поле состояния,
* идентификаторы, которые характеризуют пользователя, являющегося вла-
дельцем процесса (код пользователя или UID),
* значение дескриптора события, когда процесс приостановлен (находится в
состоянии "сна").
Адресное пространство задачи, выделенное процессу, содержит описывающую
процесс информацию, доступ к которой должен обеспечиваться только во время
выполнения процесса. Важными полями являются:
* указатель на позицию в таблице процессов, соответствующую текущему
процессу,
* параметры текущей системной операции, возвращаемые значения и коды
ошибок,
* дескрипторы файла для всех открытых файлов,
* внутренние параметры ввода-вывода,
* текущий каталог и текущий корень (см. главу 5),
* границы файлов и процесса.
Ядро системы имеет непосредственный доступ к полям адресного пространст-
ва задачи, выделенного выполняемому процессу, но не имеет доступ к соответс-
твующим полям других процессов. С точки зрения внутреннего алгоритма, при
обращении к адресному пространству задачи, выделенному выполняемому процес-
су, ядро ссылается на структурную переменную u, и, когда запускается на вы-
полнение другой процесс, ядро перенастраивает виртуальные адреса таким обра-
зом, чтобы структурная переменная u указывала бы на адресное пространство
задачи для нового процесса. В системной реализации предусмотрено облегчение
идентификации текущего процесса благодаря наличию указателя на соответствую-
30
щую запись в таблице процессов из адресного пространства задачи.
Контекстом процесса является его состояние, определяемое текстом, значе-
ниями глобальных переменных пользователя и информационными структурами, зна-
чениями используемых машинных регистров, значениями, хранимыми в позиции
таблицы процессов и в адресном пространстве задачи, а также содержимым сте-
ков задачи и ядра, относящихся к данному процессу. Текст операций системы и
ее глобальные информационные структуры совместно используются всеми процес-
сами, но не являются составной частью контекста процесса.
Говорят, что при запуске процесса система исполняется в контексте про-
цесса. Когда ядро системы решает запустить другой процесс, оно выполняет пе-
реключение контекста с тем, чтобы система исполнялась в контексте другого
процесса. Ядро осуществляет переключение контекста только при определенных
условиях, что мы увидим в дальнейшем. Выполняя переключение контекста, ядро
сохраняет информацию, достаточную для того, чтобы позднее переключиться
вновь на первый процесс и возобновить его выполнение. Аналогичным образом,
при переходе из режима задачи в режим ядра, ядро системы сохраняет информа-
цию, достаточную для того, чтобы позднее вернуться в режим задачи и продол-
жить выполнение с прерванного места. Однако, переход из режима задачи в ре-
жим ядра является сменой режима, но не переключением контекста. Если обра-
титься еще раз к Рисунку 1.5, можно сказать, что ядро выполняет переключение
контекста, когда меняет контекст процесса A на контекст процесса B; оно ме-
няет режим выполнения с режима задачи на режим ядра и наоборот, оставаясь в
контексте одного процесса, например, процесса A.
Ядро обрабатывает прерывания в контексте прерванного процесса, пусть да-
же оно и не вызывало никакого прерывания. Прерванный процесс мог при этом
выполняться как в режиме задачи, так и в режиме ядра. Ядро сохраняет инфор-
мацию, достаточную для того, чтобы можно было позже возобновить выполнение
прерванного процесса, и обрабатывает прерывание в режиме ядра. Ядро не по-
рождает и не планирует порождение какого-то особого процесса по обработке
прерываний.
Время жизни процесса можно разделить на несколько состояний, каждое из
которых имеет определенные характеристики, описывающие процесс. Все состоя-
ния процесса рассматриваются в главе 6, однако представляется существенным
для понимания перечислить некоторые из состояний уже сейчас:
1. Процесс выполняется в режиме задачи.
2. Процесс выполняется в режиме ядра.
3. Процесс не выполняется, но готов к выполнению и ждет, когда планиров-
щик выберет его. В этом состоянии может находиться много процессов, и алго-
ритм планирования устанавливает, какой из процессов будет выполняться следу-
ющим.
4. Процесс приостановлен ("спит"). Процесс "впадает в сон", когда он не
может больше продолжать выполнение, например, когда ждет завершения вво-
да-вывода.
Поскольку процессор в каждый момент времени выполняет только один про-
цесс, в состояниях 1 и 2 может находиться самое большее один процесс. Эти
два состояния соответствуют двум режимам выполнения, режиму задачи и режиму
ядра.
31
Состояния процесса, перечисленные выше, дают статическое представление о
процессе, однако процессы непрерывно переходят из состояния в состояние в
соответствии с определенными правилами. Диаграмма переходов представляет со-
бой ориентированный граф, вершины которого представляют собой состояния, в
которые может перейти процесс, а дуги - события, являющиеся причинами пере-
хода процесса из одного состояния в другое. Переход между двумя состояниями
разрешен, если существует дуга из первого состояния во второе. Несколько дуг
может выходить из одного состояния, однако процесс переходит только по одной
из них в зависимости от того, какое событие произошло в системе. На Рисунке
2.6 представлена диаграмма переходов для состояний, перечисленных выше.
Как уже говорилось выше, в режиме разделения времени может выполняться
одновременно несколько процессов, и все они могут одновременно работать в
режиме ядра. Если им разрешить свободно выполняться в режиме ядра, то они
могут испортить глобальные информационные структуры, принадлежащие ядру.
Запрещая произвольное переключение контекстов и управляя возникновением со-
бытий, ядро защищает свою целостность.
Ядро разрешает переключение контекста только тогда, когда процесс пере-
ходит из состояния "запуск в режиме ядра" в состояние "сна в памяти". Про-
цессы, запущенные в режиме ядра, не могут быть выгружены другими процессами;
поэтому иногда говорят, что ядро невыгружаемо, при этом процессы, находящие-
ся в режиме задачи, могут выгружаться системой. Ядро поддерживает целост-
ность своих информационных структур, поскольку оно невыгружаемо, таким обра-
зом решая проблему "взаимного исключения" - обеспечения того, что критичес-
кие секции программы выполняются в каждый момент времени в рамках самое
большее одного процесса.
В качестве примера рассмотрим программу (Рисунок 2.7) включения информа-
ционной структуры, чей адрес содержится в указателе bp1, в список с исполь-
зованием указателей после структуры, чей адрес содержится в bp. Если система
разрешила переключение контекста при выполнении ядром фрагмента программы,
возможно возникновение следующей ситуации. Предположим, ядро выполняет прог-
рамму
запуск +-------+
в режи- | |
ме за- | 1 |
дачи | |
+-+-----+
обращение | ^ возврат
к системе | |
или пре- | |
рывание | |
v |
запуск +-----+-+
в режи- | |<---------+ прерывание,
ме яд- | 2 | | возврат из
ра | |<---------+ прерывания
каждой таблице элемент, корреспондирующий с индексом файла. Элементы в этих
трех структурах - в пользовательской таблице дескрипторов файла, в таблице
файлов и в таблице индексов - хранят информацию о состоянии файла и о досту-
пе пользователей к нему. В таблице файлов хранится смещение в байтах от на-
чала файла до того места, откуда начнет выполняться следующая команда поль-
зователя read или write,
Пользовательская
таблица дескрип- Таблица файлов Таблица индексов
торов файла
+---------+ +-----+ +-----+
| | | | | |
+---------+ | | | |
| --+---+ | | +-----+
+---------+ | | | +-------->| |
| --+-+ | +-----+ | +-----+
+---------+ | +-------->| --+---+ | |
| | | +-----+ | |
| | +--+ | ... | +-----+
| | | +-----+ +-------->| |
| | +------->| --+---+ +-----+
| | +-----+ | |
| | | | | |
+---------+ +-----+ +-----+
Рисунок 2.2. Таблицы файлов, дескрипторов файла и индексов
а также информация о правах доступа к открываемому процессу. Таблица деск-
рипторов файла идентифицирует все открытые для процесса файлы. На Рисунке
2.2 показаны эти таблицы и связи между ними. В системных операциях open (от-
крыть) и creat (создать) ядро возвращает дескриптор файла, которому соответ-
ствует указатель в таблице дескрипторов файла. При выполнении операций read
(читать) и write (писать) ядро использует дескриптор файла для входа в таб-
лицу дескрипторов и, следуя указателям на таблицу файлов и на таблицу индек-
сов, находит информацию в файле. Более подробно эти информационные структуры
рассматриваются в главах 4 и 5. Сейчас достаточно сказать, что использование
этих таблиц обеспечивает различную степень разделения доступа к файлу.
Обычные файлы и каталоги хранятся в системе UNIX на устройствах вво-
да-вывода блоками, таких как магнитные ленты или диски. Поскольку существует
25
некоторое различие во времени доступа к этим устройствам, при установке сис-
темы UNIX на лентах размещают файловые системы. С годами бездисковые автома-
тизированные рабочие места станут общим случаем, и файлы будут располагаться
в удаленной системе, доступ к которой будет осуществляться через сеть (см.
главу 13). Для простоты, тем не менее, в последующем тексте подразумевается
использование дисков. В системе может быть несколько физических дисков, на
каждом из которых может размещаться одна и более файловых систем. Разбивка
диска на несколько файловых систем облегчает администратору управление хра-
нимыми данными. На логическом уровне ядро имеет дело с файловыми системами,
а не с дисками, при этом каждая система трактуется как логическое устройст-
во, идентифицируемое номером. Преобразование адресов логического устройства
(файловой системы) в адреса физического устройства (диска) и обратно выпол-
няется дисковым драйвером. Термин "устройство" в этой книге используется для
обозначения логического устройства, кроме специально оговоренных случаев.
Файловая система состоит из последовательности логических блоков длиной
512, 1024, 2048 или другого числа байт, кратного 512, в зависимости от реа-
лизации системы. Размер логического блока внутри одной файловой системы пос-
тоянен, но может варьироваться в разных файловых системах в данной конфигу-
рации. Использование логических блоков большого размера увеличивает скорость
передачи данных между диском и памятью, поскольку ядро сможет передать боль-
ше информации за одну дисковую операцию, и сокращает количество продолжи-
тельных операций. Например, чтение 1 Кбайта с диска за одну операцию осущес-
твляется быстрее, чем чтение 512 байт за две. Однако, если размер логическо-
го блока слишком велик, полезный объем памяти может уменьшиться, это будет
показано в главе 5. Для простоты термин "блок" в этой книге будет использо-
ваться для обозначения логического блока, при этом подразумевается логичес-
кий блок размером 1 Кбайт, кроме специально оговоренных случаев.
+---------+---------+-------------------+-----------------+
| блок | супер- | список | информационные |
|загрузки | блок | индексов | блоки |
+---------+---------+-------------------+-----------------+
Рисунок 2.3. Формат файловой системы
Файловая система имеет следующую структуру (Рисунок 2.3).
* Блок загрузки располагается в начале пространства, отведенного под файло-
вую систему, обычно в первом секторе, и содержит программу начальной заг-
рузки, которая считывается в машину при загрузке или инициализации опера-
ционной системы. Хотя для запуска системы требуется только один блок заг-
рузки, каждая файловая система имеет свой (пусть даже пустой) блок загруз-
ки.
* Суперблок описывает состояние файловой системы - какого она размера,
сколько файлов может в ней храниться, где располагается свободное прост-
ранство, доступное для файловой системы, и другая информация.
* Список индексов в файловой системе располагается вслед за суперблоком. Ад-
министраторы указывают размер списка индексов при генерации файловой сис-
темы. Ядро операционной системы обращается к индексам, используя указатели
в списке индексов. Один из индексов является корневым индексом файловой
системы: это индекс, по которому осуществляется доступ к структуре катало-
гов файловой системы после выполнения системной операции mount (монтиро-
вать) (раздел 5.14).
* Информационные блоки располагаются сразу после списка индексов и содержат
данные файлов и управляющие данные. Отдельно взятый информационный блок
может принадлежать одному и только одному файлу в файловой системе.
26
В этом разделе мы рассмотрим более подробно подсистему управления про-
цессами. Даются разъяснения по поводу структуры процесса и некоторых инфор-
мационных структур, используемых при распределении памяти под процессы. За-
тем дается предварительный обзор диаграммы состояния процессов и затрагива-
ются различные вопросы, связанные с переходами из одного состояния в другое.
Процессом называется последовательность операций при выполнении програм-
мы, которые представляют собой наборы байтов, интерпретируемые центральным
процессором как машинные инструкции (т.н. "текст"), данные и стековые струк-
туры. Создается впечатление, что одновременно выполняется множество процес-
сов, поскольку их выполнение планируется ядром, и, кроме того, несколько
процессов могут быть экземплярами одной программы. Выполнение процесса зак-
лючается в точном следовании набору инструкций, который является замкнутым и
не передает управление набору инструкций другого процесса; он считывает и
записывает информацию в раздел данных и в стек, но ему недоступны данные и
стеки других процессов. Одни процессы взаимодействуют с другими процессами и
с остальным миром посредством обращений к операционной системе.
С практической точки зрения процесс в системе UNIX является объектом,
создаваемым в результате выполнения системной операции fork. Каждый процесс,
за исключением нулевого, порождается в результате запуска другим процессом
операции fork. Процесс, запустивший операцию fork, называется родительским,
а вновь созданный процесс - порожденным. Каждый процесс имеет одного родите-
ля, но может породить много процессов. Ядро системы идентифицирует каждый
процесс по его номеру, который называется идентификатором процесса (PID).
Нулевой процесс является особенным процессом, который создается "вручную" в
результате загрузки системы; после порождения нового процесса (процесс 1)
нулевой процесс становится процессом подкачки. Процесс 1, известный под име-
нем init, является предком любого другого процесса в системе и связан с каж-
дым процессом особым образом, описываемым в главе 7.
Пользователь, транслируя исходный текст программы, создает исполняемый
файл, который состоит из нескольких частей:
* набора "заголовков", описывающих атрибуты файла,
* текста программы,
* представления на машинном языке данных, имеющих начальные
значения при запуске программы на выполнение, и указания на то, сколько
пространства памяти ядро системы выделит под неинациализированные данные,
так называемые bss (*) (ядро устанавливает их в 0 в момент запуска),
* других секций, таких как информация символических таблиц.
Для программы, приведенной на Рисунке 1.3, текст исполняемого файла
представляет собой сгенерированный код для функций main и copy, к определен-
ным данным относится переменная version (вставленная в программу для того,
чтобы в последней имелись некоторые определенные данные), а к неопределенным
- массив buffer. Компилятор с языка Си для системы версии V создает отдельно
текстовую секцию по умолчанию, но не исключается возможность включения инст-
рукций программы и в секцию данных, как в предыдущих версиях системы.
Ядро загружает исполняемый файл в память при выполнении системной опера-
ции exec, при этом загруженный процесс состоит по меньшей мере из трех час-
тей, так называемых областей: текста, данных и стека. Области текста и дан-
ных корреспондируют с секциями текста и bss-данных исполняемого файла, а об-
ласть стека создается автоматически и ее размер динамически устанавливается
ядром системы во время выполнения. Стек состоит из логических записей акти-
вации, помещаемых в стек при вызове функции и выталкиваемых из стека при
возврате управления в вызвавшую процедуру; специальный регистр, именуемый
указателем вершины стека, показывает текущую глубину стека. Запись активации
включает параметры передавае-
------------------------------------------------
(*) Сокращение bss имеет происхождение от ассемблерного псевдооператора для
машины IBM 7090 и расшифровывается как "block started by symbol" ("блок, на-
чинающийся с символа").
27
мые функции, ее локальные переменные, а также данные, необходимые для восс-
тановления предыдущей записи активации, в том числе значения счетчика команд
и указателя вершины стека в момент вызова функции. Текст программы включает
Стек задачи Направление Стек ядра
+--------------+ увеличения стека +------------------+
| Локальные | ^ | |
| переменные | | | ^ |
| (не показаны)| | | . |
|--------------| | | . |
|Адрес записи 2| | | . |
|--------------| | | . |
|Адрес возврата| | | . |
| после вызова | | | . |
| write | | | . |
|--------------| | | . |
|параметры, пе-| | | . |
| редаваемые | | | . |
| write | | | . |
|(new, buffer, | | | v |
| count) | Запись 3 | |
+--------------+ call write() Запись 3 +------------------+
| Локальные | | Локальные |
| переменные | | переменные |
| (count) | | |
|--------------| |------------------|
|Адрес записи 1| | Адрес записи 1 |
|--------------| |------------------|
|Адрес возврата| | Адрес возврата |
| после вызова | | после вызова |
| copy | | func2 |
|--------------| |------------------|
|параметры, пе-| | параметры, пере- |
| редаваемые | | даваемые функции |
| copy | | ядра func2 |
| (old, new) | Запись 2 Запись 2 | |
+--------------+ call copy() call func2() +------------------+
| Локальные | | Локальные |
| переменные | | переменные |
|(fdold, fdnew)| | |
|--------------| |------------------|
|Адрес записи 0| | Адрес записи 0 |
|--------------| |------------------|
|Адрес возврата| | Адрес возврата |
| после вызова | | после вызова |
| main | | func1 |
|--------------| |------------------|
|параметры, пе-| | параметры, пере- |
| редаваемые | | даваемые функции |
| main | | ядра func1 |
| (argc, argv) | Запись 1 Запись 1 | |
+--------------+ call main() call func1() +------------------+
Запись 0 Запись 0
Старт Интерфейс
обращений к операционной системе
Рисунок 2.4. Стеки задачи и ядра для программы копирования.
28
последовательности команд, управляющие увеличением стека, а ядро системы вы-
деляет, если нужно, место под стек. В программе на Рисунке 1.3 параметры
argc и argv, а также переменные fdold и fdnew, содержащиеся в вызове функции
main, помещаются в стек, как только встретилось обращение к функции main
(один раз в каждой программе, по условию), так же и параметры old и new и
переменная count, содержащиеся в вызове функции copy, помещаются в стек в
момент обращения к указанной функции.
Поскольку процесс в системе UNIX может выполняться в двух режимах, режи-
ме ядра или режиме задачи, он пользуется в каждом из этих режимов отдельным
стеком. Стек задачи содержит аргументы, локальные переменные и другую инфор-
мацию относительно функций, выполняемых в режиме задачи. Слева на Рисунке
2.4 показан стек задачи для процесса, связанного с выполнением системной
операции write в программе copy. Процедура запуска процесса (включенная в
библиотеку) обратилась к функции main с передачей ей двух параметров, помес-
тив в стек задачи запись 1; в записи 1 есть место для двух локальных пере-
менных функции main. Функция main затем вызывает функцию copy с передачей ей
двух параметров, old и new, и помещает в стек задачи запись 2; в записи 2
есть место для локальной переменной count. Наконец, процесс активизирует
системную операцию write, вызвав библиотечную функцию с тем же именем. Каж-
дой системной операции соответствует точка входа в библиотеке системных опе-
раций; библиотека системных операций написана на языке ассемблера и включает
специальные команды прерывания, которые, выполняясь, порождают "прерывание",
вызывающее переключение аппаратуры в режим ядра. Процесс ищет в библиотеке
точку входа, соответствующую отдельной системной операции, подобно тому, как
он вызывает любую из функций, создавая при этом для библиотечной функции за-
пись активации. Когда процесс выполняет специальную инструкцию, он переклю-
чается в режим ядра, выполняет операции ядра и использует стек ядра.
Стек ядра содержит записи активации для функций, выполняющихся в режиме
ядра. Элементы функций и данных в стеке ядра соответствуют функциям и дан-
ным, относящимся к ядру, но не к программе пользователя, тем не менее, конс-
трукция стека ядра подобна конструкции стека задачи. Стек ядра для процесса
пуст, если процесс выполняется в режиме задачи. Справа на Рисунке 2.4 предс-
тавлен стек ядра для процесса выполнения системной операции write в програм-
промежуточная
таблица облас- таблица
тей процессов областей
+---------------------+ +-------------+ +------------+
| часть адресного про-| | | | |
| странства задачи, | | | | |
| выделенная процессу | | | | |
+---------------------+ +-------------+ +------------+
^ +--+-> ---+-----+-> |
| | +-------------+ +-----+------+
+----------+----------+ +--+-> ---+--+ | | |
| | | | +-------------+ | | | |
| | | | | | | +-----+------+
+----------+----------+ | | | +--+-> | |
| v -----+--+ | | +-----+---+--+
+---------------------+ | | | | | |
| | +-------------+ +-----+---+--+
| | | |
+---------------------+ | |
таблица процессов +-------------------------+---+--+
| оперативная память v v |
+--------------------------------+
Рисунок 2.5. Информационные структуры для процессов
29
ме copy. Подробно алгоритмы выполнения системной операции write будут описа-
ны в последующих разделах.
Каждому процессу соответствует точка входа в таблице процессов ядра,
кроме того, каждому процессу выделяется часть оперативной памяти, отведенная
под задачу пользователя. Таблица процессов включает в себя указатели на про-
межуточную таблицу областей процессов, точки входа в которую служат в качес-
тве указателей на собственно таблицу областей. Областью называется непрерыв-
ная зона
адресного пространства, выделяемая процессу для размещения текста, данных и
стека. Точки входа в таблицу областей описывают атрибуты области, как напри-
мер, хранятся ли в области текст программы или данные, закрытая ли эта об-
ласть или же совместно используемая, и где конкретно в памяти размещается
содержимое области. Внешний уровень косвенной адресации (через промежуточную
таблицу областей, используемых процессами, к собственно таблице областей)
позволяет независимым процессам совместно использовать области. Когда про-
цесс запускает системную операцию exec, ядро системы выделяет области под ее
текст, данные и стек, освобождая старые области, которые использовались про-
цессом. Если процесс запускает операцию fork, ядро удваивает размер адресно-
го пространства старого процесса, позволяя процессам совместно использовать
области, когда это возможно, и, с другой стороны, производя физическое копи-
рование. Если процесс запускает операцию exit, ядро освобождает области, ко-
торые использовались процессом. На Рисунке 2.5 изображены информационные
структуры, связанные с запуском процесса. Таблица процессов ссылается на
промежуточную таблицу областей, используемых процессом, в которой содержатся
указатели на записи в собственно таблице областей, соответствующие областям
для текста, данных и стека процесса.
Запись в таблице процессов и часть адресного пространства задачи, выде-
ленная процессу, содержат управляющую информацию и данные о состоянии про-
цесса. Это адресное пространство является расширением соответствующей записи
в таблице процессов, различия между данными объектами будут рассмотрены в
главе 6. В качестве полей в таблице процессов, которые рассматриваются в
последующих разделах, выступают:
* поле состояния,
* идентификаторы, которые характеризуют пользователя, являющегося вла-
дельцем процесса (код пользователя или UID),
* значение дескриптора события, когда процесс приостановлен (находится в
состоянии "сна").
Адресное пространство задачи, выделенное процессу, содержит описывающую
процесс информацию, доступ к которой должен обеспечиваться только во время
выполнения процесса. Важными полями являются:
* указатель на позицию в таблице процессов, соответствующую текущему
процессу,
* параметры текущей системной операции, возвращаемые значения и коды
ошибок,
* дескрипторы файла для всех открытых файлов,
* внутренние параметры ввода-вывода,
* текущий каталог и текущий корень (см. главу 5),
* границы файлов и процесса.
Ядро системы имеет непосредственный доступ к полям адресного пространст-
ва задачи, выделенного выполняемому процессу, но не имеет доступ к соответс-
твующим полям других процессов. С точки зрения внутреннего алгоритма, при
обращении к адресному пространству задачи, выделенному выполняемому процес-
су, ядро ссылается на структурную переменную u, и, когда запускается на вы-
полнение другой процесс, ядро перенастраивает виртуальные адреса таким обра-
зом, чтобы структурная переменная u указывала бы на адресное пространство
задачи для нового процесса. В системной реализации предусмотрено облегчение
идентификации текущего процесса благодаря наличию указателя на соответствую-
30
щую запись в таблице процессов из адресного пространства задачи.
Контекстом процесса является его состояние, определяемое текстом, значе-
ниями глобальных переменных пользователя и информационными структурами, зна-
чениями используемых машинных регистров, значениями, хранимыми в позиции
таблицы процессов и в адресном пространстве задачи, а также содержимым сте-
ков задачи и ядра, относящихся к данному процессу. Текст операций системы и
ее глобальные информационные структуры совместно используются всеми процес-
сами, но не являются составной частью контекста процесса.
Говорят, что при запуске процесса система исполняется в контексте про-
цесса. Когда ядро системы решает запустить другой процесс, оно выполняет пе-
реключение контекста с тем, чтобы система исполнялась в контексте другого
процесса. Ядро осуществляет переключение контекста только при определенных
условиях, что мы увидим в дальнейшем. Выполняя переключение контекста, ядро
сохраняет информацию, достаточную для того, чтобы позднее переключиться
вновь на первый процесс и возобновить его выполнение. Аналогичным образом,
при переходе из режима задачи в режим ядра, ядро системы сохраняет информа-
цию, достаточную для того, чтобы позднее вернуться в режим задачи и продол-
жить выполнение с прерванного места. Однако, переход из режима задачи в ре-
жим ядра является сменой режима, но не переключением контекста. Если обра-
титься еще раз к Рисунку 1.5, можно сказать, что ядро выполняет переключение
контекста, когда меняет контекст процесса A на контекст процесса B; оно ме-
няет режим выполнения с режима задачи на режим ядра и наоборот, оставаясь в
контексте одного процесса, например, процесса A.
Ядро обрабатывает прерывания в контексте прерванного процесса, пусть да-
же оно и не вызывало никакого прерывания. Прерванный процесс мог при этом
выполняться как в режиме задачи, так и в режиме ядра. Ядро сохраняет инфор-
мацию, достаточную для того, чтобы можно было позже возобновить выполнение
прерванного процесса, и обрабатывает прерывание в режиме ядра. Ядро не по-
рождает и не планирует порождение какого-то особого процесса по обработке
прерываний.
Время жизни процесса можно разделить на несколько состояний, каждое из
которых имеет определенные характеристики, описывающие процесс. Все состоя-
ния процесса рассматриваются в главе 6, однако представляется существенным
для понимания перечислить некоторые из состояний уже сейчас:
1. Процесс выполняется в режиме задачи.
2. Процесс выполняется в режиме ядра.
3. Процесс не выполняется, но готов к выполнению и ждет, когда планиров-
щик выберет его. В этом состоянии может находиться много процессов, и алго-
ритм планирования устанавливает, какой из процессов будет выполняться следу-
ющим.
4. Процесс приостановлен ("спит"). Процесс "впадает в сон", когда он не
может больше продолжать выполнение, например, когда ждет завершения вво-
да-вывода.
Поскольку процессор в каждый момент времени выполняет только один про-
цесс, в состояниях 1 и 2 может находиться самое большее один процесс. Эти
два состояния соответствуют двум режимам выполнения, режиму задачи и режиму
ядра.
31
Состояния процесса, перечисленные выше, дают статическое представление о
процессе, однако процессы непрерывно переходят из состояния в состояние в
соответствии с определенными правилами. Диаграмма переходов представляет со-
бой ориентированный граф, вершины которого представляют собой состояния, в
которые может перейти процесс, а дуги - события, являющиеся причинами пере-
хода процесса из одного состояния в другое. Переход между двумя состояниями
разрешен, если существует дуга из первого состояния во второе. Несколько дуг
может выходить из одного состояния, однако процесс переходит только по одной
из них в зависимости от того, какое событие произошло в системе. На Рисунке
2.6 представлена диаграмма переходов для состояний, перечисленных выше.
Как уже говорилось выше, в режиме разделения времени может выполняться
одновременно несколько процессов, и все они могут одновременно работать в
режиме ядра. Если им разрешить свободно выполняться в режиме ядра, то они
могут испортить глобальные информационные структуры, принадлежащие ядру.
Запрещая произвольное переключение контекстов и управляя возникновением со-
бытий, ядро защищает свою целостность.
Ядро разрешает переключение контекста только тогда, когда процесс пере-
ходит из состояния "запуск в режиме ядра" в состояние "сна в памяти". Про-
цессы, запущенные в режиме ядра, не могут быть выгружены другими процессами;
поэтому иногда говорят, что ядро невыгружаемо, при этом процессы, находящие-
ся в режиме задачи, могут выгружаться системой. Ядро поддерживает целост-
ность своих информационных структур, поскольку оно невыгружаемо, таким обра-
зом решая проблему "взаимного исключения" - обеспечения того, что критичес-
кие секции программы выполняются в каждый момент времени в рамках самое
большее одного процесса.
В качестве примера рассмотрим программу (Рисунок 2.7) включения информа-
ционной структуры, чей адрес содержится в указателе bp1, в список с исполь-
зованием указателей после структуры, чей адрес содержится в bp. Если система
разрешила переключение контекста при выполнении ядром фрагмента программы,
возможно возникновение следующей ситуации. Предположим, ядро выполняет прог-
рамму
запуск +-------+
в режи- | |
ме за- | 1 |
дачи | |
+-+-----+
обращение | ^ возврат
к системе | |
или пре- | |
рывание | |
v |
запуск +-----+-+
в режи- | |<---------+ прерывание,
ме яд- | 2 | | возврат из
ра | |<---------+ прерывания