textbook, страница 5

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

На рис. 2.8 иллюстрируется решение задачи, когда количество процессов чтения ограниченочислом s (s < n).31Двойные стрелки указывают кратные дуги (n-кратность дуг). Первоначально имеется s процессов чтения и t процессов записи. Инициализацияпроцесса чтения моделируется запуском перехода t1 (удаление по однойметке из позиции р1 и р2). Тем самым исключается запуск перехода t2 (инициализация процесса запуска), поскольку число разрешающих меток в позиции р2 становится меньше кратности n дуг. Аналогично могут быть инициализированы все остальные s-1 процессов чтения и лишь по завершении ихвсех (при наличии n меток в позиции р2) возможен запуск перехода t2, т.е.инициализация записи.Р1Р3SНачалочтенияtt2n Р2ЧтениеОкончаниечтенияnt1НачалозаписиЗаписьt3nt4ОкончаниезаписиРис. 2.8.

Модель задачи о чтении-записи3. Моделирование двухстаночной системы с роботомманипуля-торомНа рис. 2.9 приведена модель двухстаночной системы, обслуживаемойроботом. Робот представлен динамическим элементом-меткой. Ее начальнаяпозиция р1 соответствует обслуживанию станка 1, а позиция р2 – обслуживанию станка 2.32Станок 1Р5Р4Р3t1Станок 2Р10Р7Р6Р8t3t2t7Р11Р9t4t5Р12t6t8Р2Р1Рис. 2.9. Модель двухстаночной системы, обслуживаемой роботомманипуляторомПартия обрабатываемых деталей помещается перед началом работы вбункер, моделируемый позицией р3.

Обработанные на первом станке деталипомещаются в накопитель (позиция р7). Переходы t1, t2 и t3 представляют соответственно операции загрузки, окончания обработки и разгрузки станка.Позиция р5 и ее управляющая метка создают условия для выполнения этихопераций только с одной деталью. Переход метки в позицию р4 соответствует окончанию загрузки станка, а в р6 – завершению обработки. Модель второго станка имеет аналогичную структуру, представляя соответствующиефазы обслуживания. Переход t7 моделирует транспортировку детали роботом от станка 1 к станку 2, а t8 – имитирует обратный ход робота от станка 2к станку 1.4.

Задача о распределении ресурсовС этой задачей тесно связана задача предотвращения тупиков. Рассмотрим задачу предотвращения тупика на следующем примере (рис. 2.10).33Процессы А и В нуждаются в ресурсах q(р4) и r(р5). Начальная маркировка показывает, что процессы готовы, а ресурсы доступны (метки в р1, р6,р4, р5). Если будут запущены последовательно переходы t1 и t4, то возникаетситуация взаимного блокирования процессов (состояние тупика) в результате того, что процесс А будет обладать ресурсом q(р4) и ждать ресурс r(р5), апроцесс В – наоборот.Р6Р1Р4t1t4Р7Р2t5t2Р5Р3Р8t6t3Процесс АПроцесс ВРис. 2.10. Модель задачи о распределении ресурсовАналогичная ситуация возникает при последовательном запуске сначала t4, затем t1. Для предотвращения тупиковых ситуаций необходимо внестиизменения в структуру модели, а значит и в алгоритм функционированиясистемы.

Например, введение дополнительных дуг – от р6 к t1, от р1 к t4, oт t3к р6, от t6, к р1 – при начальной разметке, приведенной на графе, устраняетпоявление тупиков, но при этом процессы А и В инициализируются поочередно.2.4. Свойства сетей ПетриРассмотрим свойства сетей Петри, наличие которых желательно с некоторых точек зрения для моделей систем логического управления. Метки в34позициях означают либо выполнение, какого-либо условия, например передачу управления некоторому блоку, либо непосредственно соответствуютнекоторым материальным объектам или информационным единицам. Этонакладывает определенные требования на максимально возможное количество меток в позициях сети.

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

Эти соображения приводят к понятиюограниченности сети.Позиция рi сети Петри C = 〈P, T, I, O〉 с начальной маркировкой µ называется n-ограниченной, если число меток в ней не может превышать целогочисла n, илиµ'(рi) ≤ n, ∀ µ' ∈ R(c, µ),где R(c, µ) – множество всех достижимых из начальной маркировки маркировок (множество достижимости).Каждая позиция может иметь свое значение n, если такое n вообще существует. Сеть Петри ограничена, если ограничены все ее позиции.

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

Безопасные позиции можно реализовать аппаратурно, используя для этого триггеры. Кроме того, безопасные позиции можно интерпретировать как логические условия: при наличии в них метки условие выполняется, при отсутствии – нет.Как было показано выше, сети Петри можно использовать для моделирования систем распределения ресурсов. Например, сеть может моделиро35вать запросы, распределения и освобождения устройств ввода-вывода в вычислительной системе. В этих моделях систем некоторые метки могут составлять ресурсы.

Для сетей такого типа в результате запуска переходовметки, представляющие ресурсы, не уничтожаются и не создаются, т.е. наблюдается своего рода сохранение меток.Сеть Петри C = 〈P, T, I, O〉с начальной маркировкой µ называетсястрого cохраняющей, еcли∑ µ′( pi ) = ∑ µ( pi ) ,pi ∈Ppi ∈P∀ µ' ∈ R(c, µ),т.е. общее количество меток в процессе выполнения сети остается постоянным. Строгое сохранение – это очень сильное ограничение. Из него немедленно следует, что число входов в каждый переход должно равняться числувыходов, т.е.│I(tj)│=│O(tj)│, ∀ j.Если бы это было не так, то запуск перехода изменил бы число меток всети.На рис. 2.11 приведен пример сети, не являющейся строго сохраняющей, поскольку запуск переходов t1 или t2 уменьшает число меток на единицу, а запуски переходов t3 или t4 увеличивают это количество на единицу.Сеть является два ограниченной, поскольку позиции р3 и р4 два ограничены,а остальные позиции один ограничены (безопасны).Сеть Петри с начальной маркировкой µ называется сохраняющей поотношению к вектору взвешивания ω = (ω1, ω2, ..., ωn), если∑ ωi µ' ( pi ) = ∑ ωi µ( pi ) ,i∀ µ' ∈ R(c, µ).iСтрого сохраняющая сеть является сохраняющей по отношению к вектору взвешивания ω = (1, 1, ..., 1).

Так рассматриваемая сеть (рис. 2.11) является сохраняющей по отношению к вектору взвешивания ω = (1, 1, 1, 1, 0).36Р1Р2t2t1Р5Р3Р4t3t4Рис. 2.11. Пример сети, иллюстрирующий свойстваограниченности и сохраненияРассмотренные свойства сетей Петри образуют основу подхода к моделированию путем построения модели по системе, анализа модели с цельюопределения характеристик системы и модификации системы, если характеристики неудовлетворительны.2.5.

Методы анализа сетей ПетриИзложим методы анализа сетей Петри, позволяющие определить наличие или отсутствие в них рассмотренных выше свойств. Рассмотрим два основных метода анализа:1.Построение дерева достижимости.2.Метод матричных уравнений.2.5.1. Построение дерева достижимостиРассмотрим маркированную сеть, представленную на pис.2.12. Её начальная маркировка µ0 = (1, 0, 0).37Р2t1t3Р1Р3t2Рис.

2.12. Пример маркированной сети для построениядерева достижимостиВ этой начальной маркировке разрешены два перехода t1, t2. Посколькумы хотим рассмотреть всё множество достижимости, определим новыевершины в дереве достижимости для достижимых маркировок, получающихся в результате запуска каждого из этих двух переходов. Дерево достижимости – это исходящее дерево, вершинам которого соответствуют достижимые маркировки.