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

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


32



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


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

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

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

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

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

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


33

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


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



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

34

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

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

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

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

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


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



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

35

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


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



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

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

Запущен


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


36

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


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



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




37

    2.6 УПРАЖНЕНИЯ



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

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

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

grep main a.c b.c c.c | wc -1

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

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

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




















38