Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 11
Текст из файла (страница 11)
На рис. 3.24 нллюстрируютса Сети Петри для лоделироеанил Рнс. 3.22. Блок-схема программы, изображенной на рис. 3.21. Ряс, 3.23. Интер претация дейстянй блок-схемы на рнс. 3.22, представляюшей программу с рис. 3.21 ° Лейоижие и Ь с и е Х Иигпнрпрета 1(ий !прИ(у,): )прп1 (ут); уз .= ); ~' О? осЫ(У1) ? УЗ: Уз Уа У1: У1 Ут:= У1* У~: У1.-У~ / 2; ОптРп1 (Уз); Глава в оьюисявнин т Рис. 3.24.
Перевод уэлен вычисления н принятия решения н блея-сиене в переходы в сети Петри. оба способа перевода. На рис. 3.25 показан перевод блок-схемы на рис. 3.22 в эквивалентную сеть Петри. Необходимо сделать замечания относительно того, что означают компоненты сети Петри на рис. 3.25. Что означают позиции? Для ответа рассмотрим интерпретацию фишек блок-схемы счетчиком команд. Фишка, находящаяся в позиции, означает, что счетчик команд установлен на готовность выполнения следующей инструкции.
Каждая позиция имеет единственный выходной переход, за исключением позиции, которая предшествует принятию решения; такие позиции имеют по два выходных перехода, соответствующих истинному и ложному значению предиката. Переходы, очевидно, связываются с действиями программы: вычислениями и принятиями решений. Для интерпретации сети Петри необходимо интерпретировать каждый переход.
Следует также отметить, что переходы для вычислений имеют один вход и один выход; переход, представляющий вычисления, не может находиться в конфликте, поскольку его входная позиция не является входной для какого-либо другого перехода. Действие же, связанное с принятием решения, вводит в сеть конфликт. Выбор способа разрешения конфликта либо недетермииирован, либо им можно управлять извне (предсказателем, вычисляющим истинность илн ложность предиката н вынуждакхцим запуск нужного перехода).
Различие между этими двумя способами разрешения конфликта— методологический вопрос. Сети Патри для моделирования Рнс. 3.25. Представленае сетью Петри программы на рнс. 3.21, полученное нз блок-схемы на рнс. 3.22. 3.4.2. Параллелизм Параллелизм (или одновременность) может быть введен несколькими способамн. Рассмотрим случай двух параллельных процессов, каждый из которых может быть представлен сетью Петри. Таким образом, составная сеть Петри, являющаяся просто обьедниеннем сетей Петри для каждого из двух процессов, может представлять одновременное выполнение двух процессов. Начальная маркировка составной сети Петри имеет две фишки, по одной в каждой сети, представляя первоначальный счетчик команд процесса Это вводит параллелизм, который, однако, не является еще полезным. Обычный подход основан на введении параллелизма в процесс в вычислительной системе.
Здесь имело место несколько предложений. Одно из них использует операции РОКК н ЛОЩ впервые предложенные Деннисом и Ван дорном ~76~. Операция РОКК у, выпол- Глстни .5 Рис. З,2о. Моделирование операций Г011К и 5015т5 сетью Петри. п — ГЮЯК 1аыпнлннеыаа на участке т соэдает даа новых процесса на участа к 5 н РЬ б — ЗОИЧ (соеднннет дна процесса, которые ааканчнаанттса на участнчк ~ и н а олин процесс, продолыаынтнасн на участке ц Рис. 3.27.
Моделировантте структуры рнгйеясл Яа Зг, —., Яо рогелт5 в сети Петри. Каждый квадрат есть представление сетью Петри утверждений Зь Ба и т. д. Здесь иллюстрируется также иерархическая природа моделирова- ния сетямн Петри. няемая в предложении 1', приводит к одновременному выполнению текущего процесса, начиная с предложения (1' + 1), и вновь созданного процесса — с предложения у. Операция Л01г1 соединяет два процесса в один или, что равнозначно, уничтожает один из них.
Эти операции моделируются в сети Петри, как показано на рис. 3.26. Другое предложение по введению параллелизма основано на операциях раг15еауи и рагеас1 Р91. Структура управления была предложена Дейкстрой и имеет вид рагйефл 81, Ве, ..., З„ригеи, где 81 — предложение. Смысл структуры ратЬедтlрагеп51 заключается в параллельном выполнении каждого из предложений 81, 5е, ...
.-., 8„. Эта конструкция может быть представлена сетью Петри, по.казанной на рис. 3.27. аз С«(и П«оеи для льве»иго«ьнич 3.4.3. Синхронизация Введение параллелизма полезно только в точ случае, когда кочпоненчы процессов могуг взаимодействовать прп получении решения задачи. Такое взаимодействие требует распределения ресурсов между процессами. Для гарантии правильности работы снстечы в целом распределением необходимо управлять. Проблемы синхронизации, возникающие прн взаимодействии процессов, иллюстрируются многочпсленнымн прнмерамп, приведенными в литерату ре. Среди задач синхронизации: задача о взаимном исключении [78[, производителе/потребителе [791, обедающих мудрецах [791, ч генншзаписи [58) и др.
Этн задачи стали классическими в области синхронизации; каждое новое предложение по механизму синхронизации должно решать их. И хотя сети Петри представляют собой схему моделирования„ а не механизм синхронизации, опи определенно способны моделировать механизмы синхронизации. Мы представляем здесь некоторые решения в виде сетей Петри. Такое представление основано частично на работе [561. 3.4.4.
Задача о взаимном исключении Предположим, что несколько процессов разделяют общую переменную, запись, файл или другой элемент данных. Этот разделяемый элемеят данных может использоваться процессами различными способами, упрощешю их можно классифицировать как чтение значения элемента данных или запись нового значения. Эти две операции являются часто единственными примитивными операциями. Это означает, что для обновления разделяемого элемента данных процесс должен сначала считать старое значение, затем вычислить новое и, наконец, записать его на то же место. Если два процесса в одно и то же время пытаются выполнить такую последовательность действий, то могут возникнуть трудности.
Возможна следующая последовательностгк 1. Первый процесс считывает значение х из разделяемого объекта; 2. Второй процесс считывает значение х ич разделяемого объекта; 3. Первый процесс вычисляет новое значение х' =- 1(х); 4. Второй процесс вычисляет новое значение х" — д(х); 6. Первый процесс записывает х' в разделяемый объект; 6.
Второй процесс записывает х«в разделяемый объект, уничтожая значение х'. Результат вычисления первого процесса потерян, так как теперь значением разделяемого объекта является п(х), в то время как им должно быть либо фЩ), либо )(д(х)). (Представьте себе, что д(х) «снять со счета х 1000 долл.», )(х) — «поместить на счет х 1000 долллч а процессы 1 и 2 — банковские операции.) Глава 3 /Гралаяяки лвял Прм г Процесс 1 Рис. 3.28, Взаимное исключение.
Управление доступом к критическим секциям двух процессов осуществляется таким образом, что оба процесса не могут одновременно выполнять свои критические секции. Для предотвращения проблем такого рода необходимо обеспечить механизм взаимного исключения. Вэаилиозл искаочеиие— это метод создания таких программ, что одновременно не более чем один процесс имеет доступ к разделяемому обьекту данных. Участок кода, в котором осуществляется доступ к разделяемому обьекту и который требует защиты от вмешательства других процессов, называется крилилтеской секцией. Идея состоит в том, что когда процесс готов выполнить свою критическую секцию, он сначала ждет, пока другой процесс не выполнит свою собственную критическую секцию. Затем он «блокируета доступ к критической секции, не даная возможности никакому другому процессу войти в свою критическую секцию.
Он входит в критическую секцию, выполняет ее и, выйдя из нее, освобождает ее для доступа со стороны других процессов. Эта задача может быть решена сетью Петри, как показано на рис. 3.28. Позиция т представляет собой разрешение для входа в критическую секцию. Для того чтобы какой-либо процесс вошел в критическую секцию, ои должен иметь фишку в р, или в р соответственно, свидетельствующую о желании попасть в критическую Сети Петри дяя моделирования секцию, а также должна существовать фишка в т, дающая разрешение на вход. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы 1е н 1 вступят в конфликт, и только один из них сможет запуститься.
Запуск уе запретит переход Ц, вынуждая процесс 2 ждать, пока первый процесс выйдет из своей критической секции и возвратит фишку обратно в позицию т. ЗА.5. Задача о производителе(потребителе В задаче о производителе/потребителе также присутствует совместно используемый объект, но в этом случае разделяемый объект точно определен и является буфером. Процесс-производитель создаег объекты, которые помещаются в буфер. Потребитель ждет, пока объект не будет помещен в буфер, удаляет его оттуда и использует.
Такая ситуация может быть промоделирована сетью Петри так, как показано на рис. 3.29. Позиция В представляет собой буфер, каждая фишка соответствует элементу данных, который произведен, но еще не использован. Одни из вариантов этой задачи — это задача о нескольких производителях/нескольких потребителях. В этом случае несколько производителей порождшот элементы данных, помещаемые в общий буфер, для нескольких потребителей. На рнс. 3.30 представлено ' решение этой задачи в виде сети Петри.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
