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

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

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

2. Второй процесс считывает значение х из разделяемого объекта;

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

4. Второй процесс вычисляет новое значение х" = g(x);

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

6. Второй процесс записывает х" в разделяемый объект, уничтожая значение х'.

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

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

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

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

Задача о производителе/потребителе

В задаче о производителе/потребителе также присутствует совместно используемый объект, но в этом случае разделяемый объект точно определен и является буфером. Процесс-производитель создает объекты, которые помещаются в буфер. Потребитель ждет, пока объект не будет помещен в буфер, удаляет его оттуда и использует. Такая ситуация может быть промоделирована сетью Петри так, как показано на рис.5.11. Позиция B представляет собой буфер, каждая фишка соответствует элементу данных, который произведен, но еще не использован.

Рис.5.11. Задача о производителе/потреьителе

Один из вариантов этой задачи – это задача о нескольких производителях/нескольких потребителях. В этом случае несколько производителей порождают элементы данных, помещаемые в общий буфер, для нескольких потребителей. На рис.5.12 представлено решение этой задачи в виде сети Петри. Эта сеть совпадает с сетью на рис.5.11, за исключением того, что для представления s производителей и t потре­бителей мы начали выполнение сети с s фишками в начальной позиции процесса-производителя и t фишками в начальной позиции процесса-потребителя. Таким образом мы представляем s производителей и t потребителей, реализуемых реентерабельными совместно используемыми программами. Альтернативой было бы дублирование программного кода для процессов производителя и потребителя, однако результатом этого при том же самом поведении была бы гораздо большая сеть.

Рис.5.12.

В другом варианте задачи о производителе/потребителе ис­пользуется буфер ограниченного размера. При такой постановке задачи бу­фер между производителем и потребителем ограничен, т. е. имеет только n ячеек для элементов данных. Следовательно, производитель не может постоянно работать с той скоростью, которая ему нужна, а вынужден ждать, если потребитель работает медленно и буфер заполнен. На рис.5.13 показано решение этой проблемы. Ограниченному буферу сопоставляются две позиции: B представляет количество элементов данных, которые произ­ведены, но еще не использованы (число заполненных ячеек). B' – количество пустых ячеек в буфере. Первоначально B' имеет n фишек, а B фишек не имеет. Если буфер заполнен, то B' фишек не имеет, а B имеет n фишек. Если теперь производитель попытается поместить еще один элемент данных в буфер, то. он будет остановлен, так как в В' нет фишки, делающей этот переход разрешенным.

Рис.5.13.

Химические системы – другой пример систем, которые могут быть промоделированы сетями Петри. Химические уравнения моделируются переходами; вещества, участвующие в реакции, – позициями. Количество фишек в позиции указывает на количество данного вещества в системе. Например, сеть Петри на рис.5.14 представляет два химических уравнения:

Рис.5.14