Задача о взаимном исключении

 

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

Процесс I Процесс 2

 

Рис. 5.4. Механизм взаимного исключения

 

Для правильной работы системы необходимо обеспечить механизм взаимного исключения, при котором одновременно не более чем один процесс имеет доступ к разделяемой переменной. Часть программного кода процесса, в котором выполняется доступ к разделяемой переменной и при этом требуется защита от доступа к разделяемой переменной другого процесса, называется критической секцией. Механизм взаимного исключения работает таким образом, что при выполнении критической секции какого-либо процесса, критические секции других процессов блокируются. Взаимодействие двух процессов через механизм взаимного исключения критических секций представлен сетью Петри на рис.5.4.

Переходы и находятся в конфликте за метку в позиции . Запуск, например, перехода , вынуждает 1-ый процесс ждать, пока 2-ой процесс выйдет из своей критической секции и возвратит метку в позицию .

 

 

Задача о производителе/потребителе

 

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

 

Производитель Потребитель

 

Рис.5.5. Механизм обмена через буфер

 

Буферу сопоставлены две позиции: В − указывает на количество компонентов данных размещенных в буфере, но еще не использованных, В° − количество свободных мест в буфере для размещения компонентов данных. Первоначально позиция В° имеет меток, а позиция В не имеет. Если буфер будет полностью заполнен, то в позиции В будет меток, а в В° − 0 меток. Таким образом, доступ процесса-производителя в заполненный буфер невозможен, так как в позиции В° будет 0 меток.

 

Задача об обедающих мудрецах

Мудрецы сидят за круглым столом и каждый из них может пребывать в одном из двух состояний: думает или обедает. На столе блюда китайской кухни, а между мудрецами лежит по одной палочке. Для приема пищи мудрец должен взять палочку слева и палочку справа. В этом случае соседи обедающего мудреца могут только думать и ждать, когда освободятся палочки, чтобы приступить к обеду. На рис.5.6 сетью Петри представлено взаимодействие трех процессов (трех мудрецов), состояния которых отражены позициями и : −обедает, − думает. Позиции представляют палочки для еды (разделяемые ресурсы). В исходной маркировке мудрецы думают, а все палочки свободны. При такой исходной маркировке любой из трех мудрецов может приступить к обеду, захватив палочки слева и справа.

Рис.5.6. Механизм разделения ресурса

 

Задача о чтении/записи

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

		Запись
	Чтение

Рис.5.7. Механизм взаимодействия процессов чтения и записи

 

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

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

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

 

Р − и V − операции над семафорами

 

Одним из распространенных механизмов синхронизации процессов являются Р - и V - операции над семафорами. Семафор − это переменная, которая может принимать только неотрицательные целые значения. V - операция увеличивает значение на единицу, а Р-операция уменьшает его на единицу. Р-операция может выполняться только в том случае, когда полученное значение семафора остается неотрицательным. Таким образом, если значение семафора равно 0, то Р-операция должна ждать, пока какой-нибудь другой процесс не выполнит V -операцию. Р- и V -операции определены как примитивные, то есть никакая другая операция не может изменять значения семафора одновременно с ними. На рис.5.8 показано как такие операции моделируются сетью Петри. Каждый семафор моделируется позицией, количество меток r в позиции показывает значение семафора. Р-операции используют позицию семафора в качестве входа, а V-операции в качестве выхода.

r

Рис.5.8. Механизм семафоров