Состояние состязания. Межпроцессное взаимодействие. Очередь печати. Критические области. Взаимное исключение с активным ожиданием. Запрещение прерываний. Переменные блокировки. Строгое чередование.

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

Важно понимать, что два из трех описанных пунктов в равной мере относятся и к потокам. Первый — передача информации — в случае потоков проблемой не является, поскольку у потоков общее адресное пространство. Остальные два с тем же успехом касаются потоков: те же проблемы, и те же решения. Очередь печати. В некоторых операционных системах процессы, работающие совместно, могут сообща использовать некое общее хранилище данных. Каждый из процессов может считывать из общего хранилища данных и записывать туда информацию. Это хранилище представляет собой участок в основной памяти или файл общего доступа. Местоположение совместно используемой памяти не влияет на суть взаимодействия и возникающие проблемы. Рассмотрим межпроцессное взаимодействие на простом, но очень распространенном примере: спулер печати. Если процессу требуется вывести на печать файл, он помещает имя файла в специальный каталог спулера. Другой процесс периодически проверяет наличие файлов, которые нужно печатать, печатает файл и удаляет его имя из каталога.Представьте, что каталог спулера состоит из большого числа сегментов, пронумерованных 0, 1, 2,..., в каждом из которых может храниться имя файла. Также есть две совместно используемые переменные: out, указывающая на следующий файл для печати, и in, указывающая на следующий свободный сегмент. Эти две переменные можно хранить в одном файле (состоящем из двух слов), доступном всем процессам. Пусть в данный момент сегменты с 0 по 3 пусты (эти файлы уже напечатаны), а сегменты с 4 по 6 заняты (эти файлы ждут своей очереди на печать). Более или менее одновременно процессы А и В решают поставить файл в очередь на печать.Возможна следующая ситуация. Процесс А считывает значение переменной in (7) и сохраняет его в локальной переменной next_freejslot. После этого происходит прерывание по таймеру, и процессор переключается на процесс В. Процесс В, в свою очередь, считывает значение переменной in и сохраняет его (7) в своей локальной переменной next_free_slot. В данный момент оба процесса считают, что следующий свободный сегмент — седьмой.Процесс В сохраняет в каталоге spooler’a имя файла и заменяет значение in на 8, затем продолжает заниматься своими задачами, не связанными с печатью.

Наконец управление переходит к процессу А, и он продолжает с того места, на котором остановился. Он обращается к переменной next_Free_slot, считывает ее значение и записывает в седьмой сегмент имя файла (разумеется, удаляя при этом имя файла, записанное туда процессом В). Затем он заменяет значение in на 8 (next_free_slot +1=8). Структура каталога спулера не нарушена, так что демон печати не заподозрит ничего плохого, но файл процесса В не будет напечатан. Ситуации, в которых два (и более) процесса считывают или записывают данные одновременно и конечный результат зависит от того, какой из них был первым, называются состояниями состязания. Критические области. Как избежать состязания? Основным способом предотвращения проблем в этой и любой другой ситуации, связанной с совместным использованием памяти, файлов и чего-либо еще, является запрет одновременной записи и чтения разделяемых данных более чем одним процессом. Говоря иными словами, необходимо взаимное исключение. Это означает, что в тот момент, когда один процесс использует разделенные данные, другому процессу это делать будет запрещено.Часть программы, в которой есть обращение к совместно используемым данным, называется критической областью или критической секцией. Если нам удастся избежать одновременного нахождения двух процессов в критических областях, мы сможем избежать состязаний. Несмотря на то, что это требование исключает состязание, его недостаточно для правильной совместной работы параллельных процессов и эффективного использования общих данных. Для этого необходимо выполнение четырех условий:

1. Два процесса не должны одновременно находиться в критических областях.

2. В программе не должно быть предположений о скорости или количестве процессоров.

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

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

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

Запрещение прерываний.

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

Переменные блокировки.

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

Строгое чередование.

Третий метод: целая переменная turn, изначально равная 0, отслеживает, чья очередь входить в критическую область. Вначале процесс 0 проверяет значение turn, считывает 0 и входит в критическую область. Процесс 1 также проверяет значение turn, считывает 0 и после этого входит в цикл, непрерывно проверяя, когда же значение turn будет равно 1. Постоянная проверка значения переменной в ожидании некоторого значения называется активным ожиданием. Активное ожидание используется только в случае, когда есть уверенность в небольшом времени ожидания. Блокировка, использующая активное ожидание, называется спин-блокировкой.Когда процесс 0 покидает критическую область, он изменяет значение turn на 1, позволяя процессу 1 попасть в критическую область. Предположим, что процесс 1 быстро покидает свою критическую область, так что оба процесса теперь находятся вне критической области, и значение turn равно 0. Теперь процесс 0 выполняет весь цикл быстро, выходит из критической области и устанавливает значение turn равным 1. В этот момент значение turn равно 1, и оба процесса находятся вне критической области.Неожиданно процесс 0 завершает работу вне критической области и возвращается к началу цикла. Но войти в критическую область он не может, поскольку значение turn равно 1 и процесс 1 находится вне критической области. Процесс 0 зависнет в своем цикле while, ожидая, пока процесс 1 изменит значение turn наО. Получается, что метод поочередного доступа к критической области не слишком удачен, если один процесс существенно медленнее другого.