Geum.ru

The design of the unix operating system by Maurice J

Вид материалаРеферат
2.3 Структуры данных ядра
2.4 Управление системой
2.5 Выводы и обзор последующих глав
Подобный материал:
1   2   3   4   5   6   7   8   9   ...   55

наоборот, оставаясь в контексте одного процесса, например, про-

цесса A.

Ядро обрабатывает прерывания в контексте прерванного процес-

са, пусть даже оно и не вызывало никакого прерывания. Прерванный

процесс мог при этом выполняться как в режиме задачи, так и в ре-

жиме ядра. Ядро сохраняет информацию, достаточную для того, чтобы

можно было позже возобновить выполнение прерванного процесса, и

обрабатывает прерывание в режиме ядра. Ядро не порождает и не

планирует порождение какого-то особого процесса по обработке пре-

рываний.


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


Время жизни процесса можно разделить на несколько состояний,

каждое из которых имеет определенные характеристики, описывающие

процесс. Все состояния процесса рассматриваются в главе 6, однако

представляется существенным для понимания перечислить некоторые

из состояний уже сейчас:

1. Процесс выполняется в режиме задачи.

2. Процесс выполняется в режиме ядра.

3. Процесс не выполняется, но готов к выполнению и ждет, ког-

да планировщик выберет его. В этом состоянии может находиться

много процессов, и алгоритм планирования устанавливает, какой из

процессов будет выполняться следующим.

4. Процесс приостановлен ("спит"). Процесс "впадает в сон",

когда он не может больше продолжать выполнение, например, когда

ждет завершения ввода-вывода.

Поскольку процессор в каждый момент времени выполняет только

один процесс, в состояниях 1 и 2 может находиться самое большее

один процесс. Эти два состояния соответствуют двум режимам выпол-

нения, режиму задачи и режиму ядра.


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


Состояния процесса, перечисленные выше, дают статическое

представление о процессе, однако процессы непрерывно переходят из

состояния в состояние в соответствии с определенными правилами.

Диаграмма переходов представляет собой ориентированный граф, вер-

шины которого представляют собой состояния, в которые может пе-

рейти процесс, а дуги - события, являющиеся причинами перехода

процесса из одного состояния в другое. Переход между двумя состо-

яниями разрешен, если существует дуга из первого состояния во

второе. Несколько дуг может выходить из одного состояния, однако

процесс переходит только по одной из них в зависимости от того,

какое событие произошло в системе. На Рисунке 2.6 представлена

диаграмма переходов для состояний, перечисленных выше.

Как уже говорилось выше, в режиме разделения времени может

выполняться одновременно несколько процессов, и все они могут од-

новременно работать в режиме ядра. Если им разрешить свободно вы-

полняться в режиме ядра, то они могут испортить глобальные инфор-

мационные структуры, принадлежащие ядру. Запрещая произвольное

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

защищает свою целостность.

Ядро разрешает переключение контекста только тогда, когда

процесс переходит из состояния "запуск в режиме ядра" в состояние

"сна в памяти". Процессы, запущенные в режиме ядра, не могут быть

выгружены другими процессами; поэтому иногда говорят, что ядро

невыгружаемо, при этом процессы, находящиеся в режиме задачи, мо-

гут выгружаться системой. Ядро поддерживает целостность своих ин-

формационных структур, поскольку оно невыгружаемо, таким образом

решая проблему "взаимного исключения" - обеспечения того, что

критические секции программы выполняются в каждый момент времени

в рамках самое большее одного процесса.


запуск --------┐

в режи- │ │

ме за- │ 1 │

дачи │ │

L-T------

│

обращение │ │ возврат

к системе │ │

или пре- │ │

рывание │ │

│ │

v │

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

в режи- │ │<---------┐ прерывание,

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

ра │ │<---------- прерывания

L-T------

│

приоста-│ │ процесс пла-

--------┐ нов │ │ нирования --------┐ готов-

ожида- │ │<----------- L------------+ │ ность

ние │ 4 │ │ 3 │ к выпол-

("сон")│ +--------------------------->│ │ нению

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

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

контекста до-

пустимо


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


В качестве примера рассмотрим программу (Рисунок 2.7) включе-

ния информационной структуры, чей адрес содержится в указателе

bp1, в список с использованием указателей после структуры, чей

адрес содержится в bp. Если система разрешила переключение кон-

текста при выполнении ядром фрагмента программы, возможно возник-

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

до комментариев и затем осуществляет переключение контекста. Спи-

сок с использованием сдвоенных указателей имеет противоречивый

вид: структура bp1 только наполовину входит в этот список. Если

процесс следует за передними указателями, он обнаружит bp1 в дан-

ном списке, но если он последует за фоновыми указателями, то во-

обще не найдет структуру bp1 (Рисунок 2.8). Если другие процессы

будут обрабатывать указатели в списке до момента повторного за-

пуска первого процесса, структура списка может постоянно разру-

шаться. Система UNIX предупреждает возникновение подобных

ситуаций, запрещая переключение контекстов на время выполнения

процесса в режиме ядра. Если процесс переходит в состояние "сна",

делая допустимым переключение контекста, алгоритмы ядра обеспечи-

вают защиту целостности информационных структур системы.


------------------------------------------------------------┐

│ struct queue { │

│ │

│ │

│ │

│ } *bp, *bp1; │

│ bp1 - > forp = bp - > forp; │

│ bp1 - > backp = bp; │

│ bp - > forp = bp1; │

│ /* здесь рассмотрите возможность переключения контекста */│

│ bp1 - > forp - > backp = bp1; │

L------------------------------------------------------------


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

ными указателями


--------┐

│ │

│ bp1 │

│ │

L--------

--------┐ --------┐

----->│ +------------------------------>│ +---->

│ bp │ │ │

<-----+ │<------------------------------+ │<----

L-------- L--------


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


--------┐ --------┐ --------┐

----->│ +---------->│ +---------->│ +---->

│ bp │ │ bp1 │ │ │

<-----+ │<----------+ │ ------+ │<----

L--------<----┐ L-------- │ L--------

L--------------------


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

чения контекста


Проблемой, которая может привести к нарушению целостности ин-

формации ядра, является обработка прерываний, могущая вносить из-

менения в информацию о состоянии ядра. Например, если ядро

выполняло программу, приведенную на Рисунке 2.7, и получило пре-

рывание по достижении комментариев, программа обработки прерыва-

ний может разрушить ссылки, если будет манипулировать указателя-

ми, как было показано ранее. Чтобы решить эту проблему, система

могла бы запретить все прерывания на время работы в режиме ядра,

но при этом затянулась бы обработка прерывания, что в конечном


счете нанесло бы ущерб производительности системы. Вместо этого

ядро повышает приоритет прерывания процессора, запрещая прерыва-

ния на время выполнения критических секций программы. Секция

программы является критической, если в процессе ее выполнения за-

пуск программ обработки произвольного прерывания может привести к

возникновению проблем, имеющих отношение к нарушению целостности.

Например, если программа обработки прерывания от диска работает с

буферными очередями, то часть прерываемой программы, при выполне-

нии которой ядро обрабатывает буферные очереди, является крити-

ческой секцией по отношению к программе обработки прерывания от

диска. Критические секции невелики по размеру и встречаются не-

часто, поэтому их существование не оказывает практически никакого

воздействия на производительность системы. В других операционных

системах данный вопрос решается путем запрещения любых прерываний

при работе в системных режимах или путем разработки схем блоки-

ровки, обеспечивающих целостность. В главе 12 мы еще вернемся к

этому вопросу, когда будем говорить о многопроцессорных системах,

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

Чтобы подвести черту, еще раз скажем, что ядро защищает свою

целостность, разрешая переключение контекста только тогда, когда

процесс переходит в состояние "сна", а также препятствуя воздейс-

твию одного процесса на другой с целью изменения состояния пос-

леднего. Оно также повышает приоритет прерывания процессора на

время выполнения критических секций программ, запрещая таким об-

разом прерывания, которые в противном случае могут вызвать нару-

шение целостности. Планировщик процессов периодически выгружает

процессы, выполняющиеся в режиме задачи, для того, чтобы процессы

не могли монопольно использовать центральный процессор.


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


Процесс, выполняющийся в режиме ядра, имеет значительную сте-

пень автономии в решении того, как ему следует реагировать на

возникновение системных событий. Процессы могут общаться между

собой и "предлагать" различные альтернативы, но при этом оконча-

тельное решение они принимают самостоятельно. Мы еще увидим, что

существует набор правил, которым подчиняется поведение процессов

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

следует этим правилам по своей собственной инициативе. Например,

если процесс должен временно приостановить выполнение ("перейти

ко сну"), он это делает по своей доброй воле. Следовательно,

программа обработки прерываний не может приостановить свое выпол-

нение, ибо если это случится, прерванный процесс должен был бы

"перейти ко сну" по умолчанию.

Процессы приостанавливают свое выполнение, потому что они

ожидают возникновения некоторого события, например, завершения

ввода-вывода на периферийном устройстве, выхода, выделения сис-

темных ресурсов и т.д. Когда говорят, что процесс приостановился

по событию, то имеется ввиду, что процесс находится в состоянии

"сна" до наступления события, после чего он пробудится и перейдет

в состояние "готовности к выполнению". Одновременно могут приос-

тановиться по событию много процессов; когда событие наступает,

все процессы, приостановленные по событию, пробуждаются, посколь-

ку значение условия, связанного с событием, больше не является

"истинным". Когда процесс пробуждается, он переходит из состояния

"сна" в состояние "готовности к выполнению", находясь в котором

он уже может быть выбран планировщиком; следует обратить внимание

на то, что он не выполняется немедленно. Приостановленные процес-

сы не занимают центральный процессор. Ядру системы нет надобности

постоянно проверять то, что процесс все еще приостановлен, т.к.

ожидает наступления события, и затем будить его.

Например, процесс, выполняемый в режиме ядра, должен иногда

блокировать структуру данных на случай приостановки в будущем;

процессы, пытающиеся обратиться к заблокированной структуре, обя-

заны проверить наличие блокировки и приостановить свое выполне-

ние, если структура заблокирована другим процессом. Ядро выполня-

ет блокировки такого рода следующим образом:

while (условие "истинно")

sleep (событие: условие принимает значение "ложь");

set condition true;

то есть:

пока (условие "истинно")

приостановиться (до наступления события, при котором

условие принимает значение "ложь");

присвоить условию значение "истина";

Ядро снимает блокировку и "будит" все процессы, приостанов-

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


set condition false;

wakeup (событие: условие "ложно");

то есть:

присвоить условию значение "ложь";

перезапуститься (при наступлении события, при котором условие

принимает значение "ложь");

На Рисунке 2.9 приведен пример, в котором три процесса, A, B

и C оспаривают заблокированный буфер. Переход в состояние "сна"

вызывается заблокированностью буфера. Процессы, однажды запустив-

шись, обнаруживают, что буфер заблокирован, и приостанавливают

свое выполнение до наступления события, по которому буфер будет

разблокирован. В конце концов блокировка с буфера снимается и все

процессы "пробуждаются", переходя в состояние "готовности к вы-

полнению". Ядро наконец выбирает один из процессов, скажем, B,

для выполнения. Процесс B, выполняя цикл "while", обнаруживает,

что буфер разблокирован, блокирует его и продолжает свое выполне-

ние. Если процесс B в дальнейшем снова приостановится без снятия

блокировки с буфера (например, ожидая завершения операции вво-

да-вывода), ядро сможет приступить к планированию выполнения дру-

гих процессов. Если будет при этом выбран процесс A, этот про-

цесс, выполняя цикл "while", обнаружит, что буфер заблокирован, и

снова перейдет в состояние "сна"; возможно то же самое произойдет

и с процессом C. В конце концов выполнение процесса B возобновит-

ся и блокировка с буфера будет снята, в результате чего процессы

A и C получат доступ к нему. Таким образом, цикл "while-sleep"

обеспечивает такое положение, при котором самое большее один про-

цесс может иметь доступ к ресурсу.

Алгоритмы перехода в состояние "сна" и пробуждения более под-

робно будут рассмотрены в главе 6. Тем временем они будут счи-

таться "неделимыми". Процесс переходит в состояние "сна"

мгновенно и находится в нем до тех пор, пока не будет "разбужен".

После того, как он приостанавливается, ядро системы начинает пла-

нировать выполнение следующего процесса и переключает контекст на

него.


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


Большинство информационных структур ядра размещается в табли-

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

Преимущество такого подхода состоит в том, что программа ядра

проста, но в ней ограничивается число элементов информационной

структуры до значения, предварительно заданного при генерации

системы. Если во время функционирования системы число элементов

информационной структуры ядра выйдет за указанное значение, ядро

не сможет динамически выделить место для новых элементов и должно

сообщить об ошибке пользователю, сделавшему запрос. Если, с дру-

гой стороны, ядро сгенерировано таким образом, что выход за гра-

ницы табличного пространства будет маловероятен, дополнительное

табличное пространство может не понадобиться, поскольку оно не

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

простота алгоритмов ядра представляется более важной, чем сжатие

последних байтов оперативной памяти. Обычно в алгоритмах для по-

иска свободных мест в таблицах используются несложные циклы и

этот метод более понятен и иногда более эффективен по сравнению с

более сложными схемами выделения памяти.


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


К управляющим процессам, грубо говоря, относятся те процессы,

которые выполняют различные функции по обеспечению благополучной

работы пользователей системы. К таким функциям относятся формати-

рование дисков, создание новых файловых систем, восстановление

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

точки зрения, между управляющими и пользовательскими процессами

нет разницы. Они используют один и тот же набор обращений к опе-

рационной системе, доступный для всех. Управляющие процессы отли-

чаются от обычных пользовательских процессов только правами и

привилегиями, которыми они обладают. Например, режимы разрешения

доступа к файлу могут предусматривать предоставление возможности

работы с файлами для управляющих процессов и отсутствие такой

возможности для обычных пользователей. Внутри системы ядро выде-

ляет особого пользователя, именуемого суперпользователем, и наде-

ляет его особыми привилегиями, о чем мы еще поговорим ниже. Поль-

зователь может стать суперпользователем, если соответствующим об-

разом зарегистрируется в системе или запустит специальную

программу. Привилегии суперпользователя будут рассмотрены в сле-

дующих главах. Если сказать коротко, ядро системы не выделяет уп-

равляющие процессы в отдельный класс.


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

--------------------------------------------------------------

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

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

│ .

│ .

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

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

│ . .

│ . .

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

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

│ -----------------------------------------------------------┐

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

│ L-----------------------------------------------------------

│ Готов к Готов к Готов к

│ выполнению выполнению выполнению

│ . .

│ . Запущен .

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

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

│ . . .

│ . . .

│ . . .

│ . . .

│ . . .

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

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

│ . . .

│ Запущен . .

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

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

│ . . .

│ . . Запущен

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

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

│ . . .

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

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

│ . буфера .

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

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

│

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


Запущен


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

вызванная блокировкой


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


В этой главе описана архитектура ядра операционной системы;

его основными компонентами выступают подсистема управления файла-

ми и подсистема управления процессами. Подсистема управления фай-

лами управляет хранением и выборкой данных в пользовательских

файлах. Файлы организованы в виде файловых систем, которые трак-

туются как логические устройства; физическое устройство, такое

как диск, может содержать несколько логических устройств (файло-

вых систем). Каждая файловая система имеет суперблок, в котором

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

в файловой системе описывается индексом, хранящим атрибуты файла.

Системные операции работают с файлами, используя индексы.

Процессы находятся в различных состояниях и переходят из сос-

тояния в состояние, следуя определенным правилам перехода. В

частности, процессы, выполняющиеся в режиме ядра, могут приоста-

новить свое выполнение и перейти в состояние "сна", но ни один

процесс не может перевести в это состояние другой процесс. Ядро

является невыгружаемым и это означает, что процесс, выполняющийся

в режиме ядра, будет продолжать свое выполнение до тех пор, пока

не перейдет в состояние "сна" или пока не вернется в режим зада-

чи. Ядро обеспечивает целостность своих информационных структур

благодаря своей невыгружаемости, а также путем блокирования пре-

рываний на время выполнения критических секций программы.