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

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

Процесс P₁ считывает значение х из разделяемого объекта;

Процесс P₂ считывает значение х из разделяемого объекта;

Процесс P₁ вычисляет новое значение х' = f(x);

Процесс P₂ вычисляет новое значение х" = g(x);

Процесс P₁ записывает х' в разделяемый объект;

Процесс P₂ записывает х" в разделяемый объект, уничтожая значение х;

Результат вычисления процесса P₁ потерян.

Для исключения подобных проблем используется метод взаимного исключения, основанный на понятии критическая секция. Критическая секция – это участок кода процесса, на котором он осуществляет доступ к разделяемому объекту данных. Прежде, чем выполнить свою критическую секцию, процесс ждёт, пока другой процесс не закончит выполнение собственной критической секции (если такое выполнение имеет место). Затем он входит в критическую секцию и блокирует доступ для любого другого процесса к своей критической секции. После выполнения процессом критической секции деблокируется доступ для других процессов к разделяемому объекту данных.

Следующая сеть Петри (рис. 4.8) моделирует механизм взаимного исключения для двух процессов P₁ и P₂. Она легко обобщается на произвольное число процессов.

Позиция mпредставляет условие «критическая секция свободна», разрешающее вход в критическую секцию. Попытка процесса P₁ (P₂) войти в критическую секцию осуществляется после помещения фишки в его позицию s₁ (s₂). Такая попытка может увенчаться успехом, если в позиции mсодержится фишка. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы t₁ и t₂ вступят в конфликт, и только один из них сможет запуститься. Запуск t₁ запретит запуск перехода t₂, вынуждая процесс P₂ ждать, пока процесс P₁ выйдет из своей критической секции, и возвратит фишку обратно в позицию m.