3.2.7.Взаимоисключение

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

У каждой задачи есть копия кода

mov ax, strok inc mov strok, ax

Пусть strok = 21678. Одна из задач начинает выполнять команды и после inc у нее кончается квант. Содержимое регистров сохраняется в блоке управления задачей. Управление передается следующей задаче и она успевает выполнить все команды. Значение strok становится 21679. В некоторый момент времени восстанавливается первая задача и выполняется последняя команда mov со значением 21679. А должно быть 21680.

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

Требования к критическому участку:

1. В любой момент времени только один процесс может находиться внутри критического участка.

2. Ни один процесс не может оставаться внутри критического участка бесконечно долго.

3. Ни один процесс не должен ждать бесконечно долго входа в критический участок.

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

program АлгоритмДеккера;

var ИзбранныйПроцесс: (первый, второй);

Процесс1ХочетВойти, Процесс2ХочетВойти: boolean;

procedure Process1

begin

while true do

begin

Процесс1ХочетВойти:= true;

while Процесс2ХочетВойти do

if ИзбранныйПроцесс = второй tНen

begin

Процесс1ХочетВойти:= false;

while ИзбранныйПроцесс= второй do;

Процесс1ХочетВойти:= true;

end;

КритическийУчасток1;

ИзбранныйПроцесс:= второй;

Процесс1ХочетВойти:= false;

ПрочиеОператоры1;

end;

end;

procedure Process2

begin

while true do

begin

Процесс2ХочетВойти:= true;

while Процесс1ХочетВойти do

if Избранный_Процесс = первый tНen

begin

Процесс2ХочетВойти:= false;

while ИзбранныйПроцесс= первый do;

Процесс2ХочетВойти:= true;

end;

КритическийУчасток2;

ИзбранныйПроцесс:= первый;

Процесс2ХочетВойти:= false;

ПрочиеОператоры2;

end;

end;

end;

begin

Процесс1ХочетВойти:= false;

Процесс2ХочетВойти:= false;

Избранный_Процесс:= первый;

parbegin

Process1;

Process2;

parend;

end.

Увеличение количества задач, требующих синхронизации, значительно усложняет алгоритм. Существуют варианты алгоритма для n процессов, которые разработал Дейкстра, например "алгоритм кондитера".