С.В. Шалобанов - Моделирование систем управления (Управления и информатика в технических системах) (1039511), страница 5
Текст из файла (страница 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.
Посколькумы хотим рассмотреть всё множество достижимости, определим новыевершины в дереве достижимости для достижимых маркировок, получающихся в результате запуска каждого из этих двух переходов. Дерево достижимости – это исходящее дерево, вершинам которого соответствуют достижимые маркировки. Начальной маркировке соответствует корневая вершина. Если из вершины µ' в вершину µ" ведет дуга, то она взвешена переходом,переводящим сеть Петри из маркировки µ' в µ".
Тупиковым маркировкамсоответствуют висячие вершины. Необходимо отметить, что в таком определении дерево достижимости в общем случае является бесконечным, поскольку даже сеть с конечным множеством достижимости (рис. 2.13, а) может иметь бесконечное дерево достижимости (рис. 2.13, б).P1(1, 0)t2(0, 1)t2t1t1(1, 0)t2P2абРис. 2.13.
Сеть с конечным множеством достижимости (а)и бесконечным деревом достижимости (б)38Для анализируемой сети (см. рис. 2.12) дерево достижимости представлено на рис. 2.14.Всякий путь от корня в дереве соответствует допустимой последовательности переходов. Для превращения дерева в полезный инструмент анализа необходимо найти средства ограничения его до конечного размера, т.е.найти средства, которые ограничивают введение новых маркировок на каждом шаге построения.
В этом смысле выделяют пассивные (терминальные),дублирующие вершины и вершины с расширенной маркировкой.(1, 0, 0)t1(1, 3, 0)t1t1t2(1, 1, 0)(0, 1, 1)t1t2t3(1, 2, 0)(0, 2, 1)(0, 0, 1)t2t3(0, 3, 1)(0, 1, 1)ДублирующаяПассивная(тупик)(1, ω, 0)РасширеннаяРис. 2.14. Дерево достижимостиПассивная (или терминальная) вершина – это маркировка, в которойнет разрешенных переходов. Для анализируемого примера сети это маркировка (0, 0, 1) (см. рис. 2.12). Дублирующая вершина – это вершина с маркировкой, которая уже ранее встречалась в этом дереве достижимости.
Припоявлении дублирующей вершины нет необходимости производить из неедальнейшие построения, поскольку это приведет к появлению поддерева,полученного из места первого появления дублирующей вершины. В рассматриваемом примере маркировка (0, 1, 1), получившаяся после выполнения t1, t2, t3 не будет порождать какие-либо новые вершины, поскольку она39ранее была получена в дереве после выполнения t2 из начальной маркировки.Расширенная маркировка вводится, исходя из следующих соображений.Пусть существует последовательность запуска переходов σ, переводящаямаркировку µ в µ', причем маркировка µ' совпадает с µ за исключением того,что имеет дополнительные метки в некоторых позициях, т.е.µ' = µ + (µ' – µ) и µ' – µ > 0.Поскольку на запуск переходов лишние метки повлиять не могут, топоследовательность σ можно запустить еще раз из µ' и получить µ", причемµ'' = µ' + (µ' – µ) = µ + 2(µ' – µ).В общем случае можно запустить последовательность переходов σ n рази получитьµ''' = µ' + n(µ' – µ).Поскольку число n можно выбрать сколь угодно большим, в некоторыхпозициях сети разметка будет неограниченно возрастать.
При построениидерева достижимости этот фрагмент дерева можно ограничить, вводя символ ω, который означает «бесконечность» в соответствующей позиции разметки. Для рассматриваемого примера (см. рис. 2.14) последовательное срабатывание t1 приводит к нарастанию разметки в позиции р2, что приводит квведению расширенной маркировки (1, ω, 0).Кроме того, различают граничные вершины и внутренние. Граничнымивершинами называют вершины дерева достижимости, которые еще не обработаны алгоритмом построения дерева достижимости. В результате реализации алгоритма построения дерева достижимости граничные вершины превращаются в терминальные, дублирующие или внутренние.Наличие свойств безопасности и ограниченности легко проверяется издерева достижимости.
Сеть Петри ограничена тогда и только тогда, когдасимвол ω отсутствует в дереве достижимости. Если символа ω нет, то можно определить границу числа меток в позициях путем перебора вершин де40рева достижимости. Если в дереве достижимости присутствует символ ω, тодля того, чтобы сеть была сохраняющей по отношению к некоторому вектору взвешивания, необходимо, чтобы вес ωi позиции рi , имеющей в некоторой маркировке ω, был нулевым.2.5.2. Метод матричных уравненийЭтот подход основан на матричном представлении сетей Петри. Входная и выходная функции представляются матрицами D– и D+ соответственно. Элементы матриц определяются следующим образом:D– [i, j] = # (pi, I(tj));D+ [i, j] = # (pi, O(tj));i = 1, n;j = 1, m.Матричная форма представления сети C = 〈P, T, D–, D+〉 эквивалентнастандартной, но позволяет дать определения в терминах векторов и матриц.Пусть е[j] – m-вектор-столбец, содержащий все нули, за исключением jй позиции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
