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

    На этом шаге мы рассмотрим задачу о взаимном исключении.

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

1. Первый процесс считывает значение x из разделяемого объекта;
2. Второй процесс считывает значение x из разделяемого объекта;
3. Первый процесс вычисляет новое значение x' = f(x);
4. Второй процесс вычисляет новое значение x'' = g(x);
5. Первый процесс записывает x' в разделяемый объект;
6. Второй процесс записывает x'' в разделяемый объект, уничтожая значение x'.

    Результат вычисления первого процесса потерян, так как теперь значением разделяемого объекта является g(x), в то время, как им должно быть либо g(f(x)), либо f(g(x)).

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

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

    Эта задача может быть решена сетью Петри, как показано на рисунке 1. Позиция m представляет собой разрешение для входа в критическую секцию. Для того, чтобы какой-либо процесс вошел в критическую секцию, он должен иметь фишку в p₁ или в p₂ соответственно, свидетельствующую о желании попасть в критическую секцию, а также должна существовать фишка в m, дающая разрешение на вход. Если оба процесса пытаются пройти в критическую секцию одновременно, то переходы t₁ и t₂ вступят в конфликт, и только один из них может запуститься. Запуск t₁ запретит переход t₂, вынуждая процесс 2 ждать, пока первый процесс выйдет из своей критической секции и возвратит фишку обратно в позицию m.

    На следующем шаге мы рассмотрим задачу о производителе/потребителе.

Предыдущий шаг Содержание Следующий шаг