Алгоритмы. Сети Петри. Модели вычислений

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

Например: два циклических процесса, каждый обращается к общей памяти. Необходимо выполнение следующих условий: 1) в каждый момент времени только один процесс может находиться в своем критическом интервале; 2) задержка любого процесса вне его критического интервала не должна влиять на ход исполнения других процессов; 3) решение, какой из процессов должен войти в свой критический интервал должно быть принято за конечное время.

Поведение системы процессов  с определенными в них одноименными критическими интервалами описывает сеть Петри на рисунке:

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

13. Семафоры (определение). Операции над семафорами. Пример сети Петри, моделирующей операции над семафорами.

Пусть есть два процесса с некоторыми критическими интервалами в каждом. Одновременно в критическом интервале может находиться только один процесс. Для реализации такой работы процессов используются специальные переменные типа integer: семафоры. Над семафором S определены две операции: P-операция и V-операция.

P(S)-операция эквивалентна уменьшению значения семафора на единицу, если он отличен от нуля (открывает критический интервал). В противном случае процесс замораживается до тех пор, пока значение семафора не станет больше нуля.

V(S)-операция выполняет увеличение значения семафора на единицу (закрывает критический интервал).

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

Если семафор может принимать значения 0 или 1, то он называется двоичным, иначе – общим.

Пример использования семафоров для циклических процессов с критической секцией:

Begin

Semaphore m:=1;

Parbegin

Pi: Li: begin

P(m);

{критическая секция i};

V(m);

{продолжить цикл i};

goto Li;

end;

parend;

end.

При доступе к семафору возмодна ситуация вечного ожидания – один из процессов постоянно не получет разрешения войти в свой критический интервал