Тема 4.2. Решение проблемы взаимного исключения

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

Определение 4.7. Те места в процессах, в которых происходит обращение к критическим ресурсам, называются критическими секциями или критическими интервалами.

Рис.4.3. Пример взаимодействующих процессов

На рис.4.3 А, В, С – разделяемый ресурс, Р1, Р2 – процессы.

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

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

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

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

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

Рис.4.5. Сеть Петри, моделирующая задачу «поставщик-потребитель»

Позиция B представляет буфер, каждая фишка соответствует сообщению, которое произведено, но еще не использовано.

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

· в любой момент времени только один процесс должен находиться в своей критической секции;

· ни один процесс не должен находиться в своей критической секции бесконечно долго;

· ни один процесс не должен ждать бесконечно долго входа в свой критический интервал. В частности:

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

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

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

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

- блокировка памяти,

- специальные команды типа «проверка и установка»,

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

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