Состояние состязания

В некоторых операционных системах процессы, работающие совместно, сообща используют некое общее хранилище данных. Каждый из процессов может счи­тывать что-либо из общего хранилища данных и записывать туда информацию. Это хранилище представляет собой участок в основной памяти (возможно, в струк­туре данных ядра) или файл общего доступа. Местоположение разделяемой па­мяти не влияет на суть взаимодействия и возникающие проблемы. Рассмотрим межпроцессное взаимодействие на простом, но очень распространенном приме­ре: систему буферизации — «спулер» — печати. Если процессу требуется вывес­ти на печать файл, он помещает имя файла в специальный каталог спулера. Дру­гой процесс, демон печати, периодически проверяет наличие поданных на печать файлов, печатает их и удаляет их имена из каталога.

Представьте, что каталог спулера состоит из большого числа сегментов, про­нумерованных последовательно (0, 1, 2,...), в каждом их которых может хра­ниться имя файла. Также есть две совместно используемые переменные: out, указывающая на следующий файл для печати, и in, указывающая на следующий свободный сегмент. Эти две переменные можно хранить в одном файле (состоя­щем из двух слов), доступном всем процессам. Пусть в данный момент сегменты с 0 по 3 пусты (эти файлы уже напечатаны), а сегменты с 4 по 6 заняты (эти фай­лы ждут своей очереди на печать). Более или менее одновременно процессы А и В решают поставить файл в очередь на печать. Описанная ситуация схемати­чески изображена на рис. 2.5.

Рис. 2.5. Два процесса хотят одновременно получить доступ

к совместно используемой памяти

В соответствии с законом Мерфи (он звучит примерно так: «Если что-то пло­хое может случиться, оно непременно случится»), возможна следующая ситуа­ция. Процесс А считывает значение (7) переменной in и сохраняет его в локаль­ной переменной next_free_slot. После этого происходит прерывание по таймеру, и процессор переключается на процесс В. Процесс В, в свою очередь, считывает значение переменной in и сохраняет его (опять 7) в своей локальной переменной next_free_slot. В данный момент оба процесса считают, что следующий свобод­ный сегмент — седьмой.

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

Наконец, управление переходит к процессу А, и он продолжает с того места, на котором остановился. Он обращается к переменной next_free__slot, считывает ее значение и записывает в седьмой сегмент имя файла (разумеется, удаляя при этом имя файла, помещенное туда процессом В). Затем он заменяет значение in на 8 (next_free_slot +1 = 8). Структура каталога спулера не нарушена, поэтому демон печати не заподозрит ничего плохого, но файл процесса В не будет напеча­тан. Пользователь, связанный с процессом В, может в этой ситуации полдня опи­сывать круги вокруг принтера, ожидая результата. Ситуации, в которых два (и более) процесса считывают или записывают данные одновременно и конеч­ный результат зависит от того, какой из них был первым, называются состоя­ниями состязания. Отладка программы, в которой вероятно возникновение состояния состязания, вряд ли может доставить удовольствие. Результаты большинства тестов будут хорошими, но изредка будет происходить нечто странное и необъяснимое.

Критические области

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

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

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

1. Два процесса не должны одновременно находиться в критических областях.
2. В программе не должно быть предположений о скорости или количестве
   процессоров.
3. Процесс, в состоянии вне критической области, не может блокировать
   другие процессы.
4. Недопустима ситуация, в которой процесс вечно ждет попадания в крити­
   ческую секцию.

Взаимное исключение
с активным ожиданием

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