/>Зміст
Вступ
1. Мережі Петрі
1.1 Визначення мережі
1.2 Розмітка мережі
2. Розширення мереж Петрі
3. Приклади подання елементів виробничихсистем
Література
Вступ
Тема контрольноїроботи "Імітація процесів ГВС за допомогою апарата мереж Петрі".
Сучасний рівеньрозвитку обчислювальних засобів характеризується широким застосуванням методівта алгоритмів автоматизованного проектування. В цих умовах підготовкаспеціалістів, здатних визначати задачі направлені на скорочення часупроектування та впровадження електронної техніки в режимі безперервногонарощування темпів виробництва є необхідно актуальною.
В курсі «Основиавтоматизованого проектування засобів обчислювальнної техніки» вивчаютьсяметоди, алгоритими та основні підходи до проектування сучасних обчислювальнихзасобів. Дисципліна базується на матеріалі курсів «Вища математика», «Програмування»,«Чисельні методи» та ін. Методи постановки й рішення завданьавтоматизації широко використовують апарат теорії графів і математичногопрограмування.
Найбільшоюскладністю при вивченні даної дисципліни є багатоплановість розглядаємогоматеріалу, сполучення абстрактних понять і моделей з практичною спрямованосттюцих моделей для рішення різноманітних задач проектування.
Мета роботи – навчитисязастосовувати мережі Петрі для моделювання процесів у ГВС.
1.Мережі Петрі
Компонентибудь-якої системи і їхньої дії можна представити абстрактними подіями. Подіяможе відбутися один раз, повторитися багаторазово, породжуючи конкретні дії,або не відбутися жодного разу. Сукупність дій, що виникають як реалізації подій,утворюють процес. У загальному випадку та сама система може функціонувати в тихсамих умовах по-різному, породжуючи деяку множину процесів.
Реальна системафункціонує в часі, події відбуваються в деякі моменти часу й діють якийсь час.Якщо строго враховувати час, то такий підхід до моделювання великих паралельнихсистем буде мати ряд недоліків.
У великій системідоводиться враховувати стан всіх компонентів при кожній зміні її загальногостану, що робить модель громіздкою.
Зникає інформаціяпро причинно-наслідкові зв'язки між подіями в системі. Якщо дві події прифункціонуванні системи відбулися одночасно, то ми не знаємо, чи відбулося цевипадково, чи ні. Такі поняття, як конфлікти між компонентами системи абоочікування одним з них результатів роботи інших, важко виражаються в термінахзміни станів системи.
Події можутьвідбуватися усередині невиразно великих інтервалів часу, заздалегідь важко абоне можна вказати точно час їхнього початку, кінця й тривалість.
Виходом можеслужити відмова від введення в моделі дискретних систем часу й тактованихпослідовностей змін станів, і заміна їхніми причинно-наслідковими зв'язками міжподіями. Моделі такого типу добре описуються термінами мережі Петрі.
Імітація процесів- це інтерпретація послідовності здійснення подій кожна з яких характеризуєтьсямоментами запуску й закінчення.
Відзначимоособливості процесів гнучких виробничих систем (ГВС) із погляду функціонування:
- паралелізм;
- асинхронність;
- іерархичність.
Інтерпретаціямереж Петрі заснована на поняттях умови й події. Стан системи описуєтьсясукупністю умов. Функціонування системи складається в здійсненні послідовностіподій. Для виникнення події необхідне виконання деяких умов, називаних предумовами.Виникнення подій може привести до виконання умов, називаних постумовами. Умережі Петрі умови моделюються позиціями, події — переходами. Предумови подіїпредставляються вхідними позиціями відповідного переходу, постумови — вихіднимипозиціями.
Виробничі процесипо своїй природі є динамічними, отже, при їхньому моделюванні доцільновикористовувати динамічні мережні моделі, що реалізують умовно-подійні системи.Такі системи являють собою мережу, доповнену правилами зміни умов у результатіреалізації подій. Динамічна модель процесу може бути побудована з використанняммережі Петрі.
Оскільки подіїякі моделюються мережею Петрі є миттєвими і неодночасними, і їхнійвзаємозв'язок асинхронний, це зручний апарат для моделювання множини взаємозалежнихі паралельних процесів. Використання мереж Петрі в завданнях, пов'язаних зрозподілом ресурсів, привабливо наочністю, адекватністю й технологічністю приреалізації моделей на ЕОМ.
Мережі Петрі — цематематична модель, що має широке застосування для опису поводження паралельнихпристроїв і процесів. У цей час визначені й вивчені різноманітні класи мережПетрі. Ми розглянемо загальні поняття й можливості використання мереж Петрі длязавдання прямого керування в паралельних програмах.
1.1 Визначеннямережі
Мережа Петріє двочастковий орієнтованийграф. Двочастковий граф — це такий граф, множина вершин якого розбивається надві підмножини й не існує дуги, що з'єднує дві вершини з однієї підмножини.Отже, мережа Петрі — це набір
N = (T,P,A), T Ç Р = Ø, (1.1)
де Т = {t1,t2,...,tn}- підмножина вершин, що називаються переходами; Р = {p1, р2,..., pm} — підмножина вершин, що називаються (подіями)місцями; АÍ (T×P) – множина орієнтованихдуг.
По визначенню,дуга з'єднує або місце з переходом, або перехід з місцем.
Приклад
На рис. 1.1наведений приклад мережі Петрі в графічному поданні. Переходи позначенірисками, а місця — окружностями. Кожен перехід t має набір вхідних in{t}і набір вихідних out{t} дуг. Мережі Петрі можуть представлятися також уформі продукційних правил (рис. 1.1, б).
Найцікавішімережі Петрі тим, що вони дозволяють представляти й вивчати в динаміціповодження системи паралельних процесів у програмі або в будь-якому іншомудискретному пристрої.
/>/>
Рис 1.1 Прикладмережі Петрі в графічному поданні
1.2 Розміткамережі
Мережі Петріможна розуміти (інтерпретувати) по-різному. Можна уявити собі, що місцяпредставляють умови (буфер порожній, файл закритий і т.п.), а переходи — події(посилка або одержання повідомлення в буфер, запис у файл).
Стан мережі Петрів кожен сучасний момент визначається системою умов. Для того щоб стало можливізручним задавати умови типу «у буфері перебуває 3 записи», у модельмережі Петрі додаються фішки. Фішки зображуються крапками усерединімісця. У застосуванні до програмування можна уявляти собі переходи якпроцедури, а місця — як змінні або буфер.
Фішка свідчитьпро те, що змінна/буфер має значення, а якщо місце має, приміром, 3 фішки, теце може інтерпретуватися як наявність трьох різних значень у буфері.
Якщо місцемістить фішку, то місце маркіроване й мережа називається маркірованою. Початковийрозподіл фішок задає початкове маркування М0мережі. Маркуваннямережі визначає її поточний стан.
Мережа на рис.1.2у початковому стані містить одну фішку в місці р3.
/>
Рис 1.2 Послідовністьстанів мережі Петрі
Маркуванняформально задається функцією М: Р → I, I = {0,1,2,..}, а функція Мпредставляється вектором, у якому i-й компонент задає маркування місця pi.
Наприклад,початкове маркування мережі на рис. 1.2 представляється вектором М0= {1,0,0}.
На рис. 1.2 показанапослідовність станів мережі Петрі в ході спрацьовування переходів. Початковарозмітка М0= (1,0,0) показана на рис1.2, а.
У цьому станіможе спрацювати тільки перехід t1. Розмітка мережі M1 =(1,1,1) після спрацьовування t1 показана на рис.1.2, б. Останнядозволяє одночасно спрацювати переходам t1 й t2,розмітка М2 = (1,2,3) після їхнього спрацьовування показана на рис.1.2, в.
Мережа переходитьіз одного стану в інше (від одного маркування до іншого), коли відбуваєтьсяподія – спрацьовування переходу.
Перехід можеспрацювати, якщо є хоча б одна фішка у всіх його вхідних місцях (рис.1.3)
/>
Рис 1.3 Схемаспрацьовування переходів
Спрацьовуванняпереходу складається з того, що із всіх вхідних місць забирається по однійфішці й в усі вихідні місця додається по одній фішці.
Якщо уявити собіперехід як процедуру, то вона коректно виконується при наявності значень всіхсвоїх аргументів і виробляє значення всіх вихідних змінних.
В іншійінтерпретації перехід може представляти деякий пристрій. Пристрій може (але неповинен) спрацювати, якщо виконалися всі вхідні умови.
Якщо кількапереходів готові спрацювати, то спрацьовує один з них (кожен), або деякі з них,або всі (рис.1.4).
/>
Рис 1.4 Варіантиспрацьовування мережі
Приклад
Розглянемоприклад конвеєра. Нехай є три обробні пристрої t0, t1, t2організовані у вигляді конвеєра. Це можуть бути, наприклад, верстати на заводіабо функціональні пристрої конвеєрного процесора й взагалі будь-який конвеєр, уякому кожен обробний пристрій виконує лише частину загальної роботи, арезультат буде вироблений лише останнім з них.
Особливістюнашого конвеєра є обмеженість ємності місць p1 і р2;місце p1 може вмістити лише два результати (місце p1мережі є 2-обмеженим) попереднього етапу роботи конвеєра (виробляєтьсяпереходом t0), а місце p2 — 3-обмеженим.
Символ n умісці р0означає наявність n фішок у ньому, n — цілепозитивної число.
Мережа Петрі, щозабезпечує необхідне пряме керування, наведена на рис.1.5. Зрозуміло, що вмісці p1 не може нагромадитися більше 2 фішок при будь-яких порядкахспрацьовування переходів мережі.
Місця p1і р2 часто ще називають асинхронними каналами, з їхньою допомогоюреалізується програмування засобами асинхронного message passing interface.
/>
Рис 1.5Імітаційна модель необхідного прямого керування
Мережа Петрі, уякій всі місця 1-обмежені, називається безпечною. Такою мережею можназадавати пряме керування в програмах.
Безпечна мережаніколи, не допустить, щоб у змінну було покладено нове значення, якщо старе щене було використано по призначенню. Порушення цього правила часто є причиноюпомилок у паралельних програмах.
2.Розширення мереж Петрі
Для того, щобвикористати мережі Петрі для моделювання стохастичних процесів, були здійсненінаступні розширення:
Використаннячасу (стохастичні Мережі Петрі)
Для моделюваннярізних процесів необхідно кількісно розглядати час. У стандарті мереж Петрі дляцього немає механізмів. Стохастичні мережі Петрі як розширення стандарту мережПетрі можуть розглядати час. У принципі будь-які елементи мережі Петрі можнаоб'єднати з компонентом часу. Так, час могло б розташовуватися в позиціях,мітках, дугах й/або переходах.
Для SimNet часустановлюється в перехід (синхронізовані мережі Петрі). Таким чином, дії, щопоглинають час, описуються переходами, оскільки стани описуються позиціями.Якщо мітки деяких позицій будуть інтерпретуватися як послуги, що виробляютьсяза деякий номінальний час, то такі позиції можуть замінятися переходом. Крімтого, у цьому випадку мітки таких переходів не затримуються в ньому протягомчасу роботи, але встановлюються як недоступні (зарезервовані) у вихіднихпозиціях. Це допомагає уникнути ситуації, коли через паралельні процесиспрацьовування переходу стає неможливим протягом часу послуги. Це повинневимагати повернення міток на вхідні позиції, які відбивають реальні процеси йне пристосовані до односпрямованого поняття потоку, яке використовується встандарті мереж Петрі.
Оскільки дляопису реальних процесів потрібно не тільки фіксований час, але також час,описуваний статистичними розподілами, то використовуються стохастичні мережіПетрі як спеціальний тип часу, що оцінює роботу мережі Петрі.
Коли перехідодержує можливість спрацьовування, він спрацьовує негайно. Мітки, узяті увхідних позиціях, установлюються у вихідні позиції.
Час послуги можеописуватися кожним з наступних розподілів:
постійнийрозподіл; однорідний розподіл;
експонентнийрозподіл; розподіл Эрланга;
пуасоновськийрозподіл; нормальний розподіл;
розподіл Вейбулла;бета-розподіл;
трикутнийрозподіл (симетричне); гамма-розподіл.
Пофарбовані(кольорові) мережі Петри
Для багатьохзавдань моделювання необхідно розрізняти різні типи інформації й істотнихпотоків, які зустрічаються в системі. У відомій мірі це може досягатисяокремими структурами мереж Петрі для кожного з типів потоку, якісинхронізуються тільки в переходах. Але із цим методом модель губить своюподібність із вихідною системою, де різні типи потоків часто використаютьоднакові маршрути передачі. Додаткові проблеми виникають, коли різним типампотоків потрібно поширювати обмежені ресурси.
Щоб моделі різнихпотоків мали взаємозалежності, розподіл типів потоків окремими позиціями йдугами неможливий. Тому бажано, щоб однорідні мітки одного потоку відрізнялисявід однорідних міток іншого потоку. Це розширення стандарту мережі Петріназване пофарбованою або кольоровою мережею Петрі.
РішенняКонфлікту.
Два переходивступають у конфлікт, якщо обоє мають можливість спрацьовування, але післязапуску одного переходу предумови або постумови іншого переходу стаютьнездійсненними. У цьому випадку перехід, що дійсно повинен спрацювати,визначається однією з наступних стратегій:
Пріоритет:
Пріоритетпереходу може перебувати в проміжку значень [0, 255]. Величина 0 означає самийверхній, 255 — найнижчий пріоритет. Якщо різні переходи можуть спрацювати в тойсамий час, спочатку спрацьовує перехід із самим верхнім пріоритетом, а потім,можливо, інші переходи в міру зменшення пріоритетів, якщо умови їхньогоспрацьовування усе ще виконуються.
Якщо дійсно мавмісце конфлікт переходів, із запуском переходу із самим верхнім пріоритетомможливість спрацьовування переходу з нижнім пріоритетом виключається.
Імовірність:
Для кожногопереходу може бути оголошена ймовірність спрацьовування. Якщо різні переходитого самого пріоритету можуть спрацювати в той самий час, спочатку спрацьовуєтой перехід, у якого ймовірність спрацьовування вище. Таким чином, крім дозволуконфлікту, також можуть бути описані ймовірності для переходів.
3.Приклади подання елементів виробничихсистем
Розглянемо ГВМ(рис.1.6, а).Послідовність взаємодії його елементів полягає внаступному: переміщення за допомогою робота R заготівлі від конвеєра CV1на конвеєр (або тактовий стіл) CV2; пересування заготівлі конвеєром CV2на верстат М; обробка заготівлі на верстаті; пересування обробленоїдеталі від верстата на конвеєр (стіл) CV2; транспортування деталі роботомR від конвеєра CV2 на конвеєр CV3.
Вважаємо, щокожний з компонентів ГВМ — верстат М, робот R і конвеєр CV2 можебути завантажений тільки однією деталлю. Елементи модуля виконують своїоперації незалежно друг від друга, тобто робот починає свої транспортніоперації, коли на одному з конвеєрів, CV1 або CV2, перебуваєдеталь; конвеєр CV2, що одержав деталь від робота, починає пересуватисяв напрямку верстата; завантажений заготівлею верстат М починає операціюобробки; оброблена деталь переміщається незавантаженим конвеєром CV2 у позицію розвантаження роботом.
Модель взаємодіїелементів ГВМ і виконання виробничого процесу може бути інтерпретована мережеюПетрі (рис.1.6, б). Компоненти структури мережі інтерпретуються в такий спосіб.
Позиції р2--р6відображають окремі операції виробничого процесу відповідно:
— транспортування заготівлі роботом доконвеєраСV2,
— пересування заготівлі до верстатаконвеєром,
— обробку,
— пересування обробленої деталіконвеєром CV2 до робота,
— транспортування деталі роботом ірозміщення її на конвеєрі CV3.
Наявність мітки водній з позицій відповідає стану виконання якоїсь із технологічних операцій.Позиції р7… р9 відображають відповідно станукомпонентів ГВМ: робота, конвеєра CV2 і верстату. Позиція р1інтерпретується як склад заготівель. Наявність мітки в одній з позицій р7… р9відповідає ситуації, у якій деякі з компонентів ГВМ виконують певну виробничуоперацію.
Наприклад,маркування (2, 0, 0, 1, 0, 0, 0, 0, 1), досяжне з початкового маркування (3, 0,0, 0, 0, 0, 0, 0, 0) внаслідок послідовності спрацьовувань переходів. Т відповідаєстану системи, у якому перша заготівля обробляється на верстаті, тоді як іншізаготівлі чекають своєї черги на складі.
Переходи tv..ttsвідповідають подіям, що відбивають початок або завершення моделюємихоперацій. Наприклад, перехід t2 інтерпретується як подія,пов'язана із завершенням операції транспортування заготівлі роботом й установкиїї на конвеєрі CV2, а також з початком операції переміщення заготівліконвеєром CV2 до верстата.
У даному прикладітехнологічні операції моделюються позиціями. Іноді використовуються моделі, уяких виконання операції моделюється переходами. Як ілюстраці. такого підходу розглянемо модульавтоматичного пакування (рис. 1.7, а). Технологічні операції виробничогопроцесу виконуються в такій послідовності:
— операція заповнення конвеєром CV1 накопичувача(локального складу);
— заповнення роботом R тари,розміщеної на палеті;
— пересування палети з пакувальноютарою уздовж конвеєра
Мережна модельскладського модуля представленана рис.1.6, б.
/>
Рис. 1.6. Схемамодуля автоматичного пакування об'єктів виробництва (а), мережна модельскладського модуля (б) і дерево досяжних маркувань (в)
Переходи tl3t2, tsвідображають виконання технологічних операційвідповідно:
- заповненнянакопичувача;
- пересуванняй установку пляшок у тару роботом R;
- переміщенняпалети із заповненою тарою уздовж конвеєра CV2.
Позиції рь,pit рьвідображають стан основних компонентів модуля:конвеєра CV1, робота R і конвеєра CV2. Відсутність мітки водній з розглянутих позицій означає, що відповідний компонент виконує певнутехнологічну операцію.
Позиції р1, р2відображають відповідно накопичувач С и заповнювану тару.
Число міток, щоперебувають у цих позиціях, відображає кількість пляшок, які заповнюютьнакопичувач або впакованих у тарі. Наприклад, маркування (2, 4, I, 1, 1),досяжне з початкового маркування i0= (0, 0, 1, 1, 1).
Література
1. Системы автоматизированного проектирования. В 9-тикн.Учебное пособие для вузов. Под редакцией Норенкова И.П. М.: Высш. шк., 1986.
2. Норенков И.П. Введение в автоматизированное проектированиетехнических устройств и систем. Учебное пособие для вузов. — М.: Высш. шк.,1986.
3. П. Шеннен и др. Математика и САПР. т.1. М.: Мир, 1988.
4. Батищев Д.И. Методы оптимального проектирования. М.: Радиои связь, 1984.
5.Системы автоматизированного проектирования врадиоэлектронике. Справочник. М.: Радио и связь, 1986.
6. Погребной В.К. О декомпозиции графов на классы изоморфныхподграфов. В кн.: Вопросы программирования и автоматизации проектирования. Изд.ТГУ, 1979, с. 82-96.
7. Петренко А.И. Основы автоматизации проектирования. К.: Техника, 1982. — 295 с.
8. Ильин В.Н… Основы автоматизации схемотехнического проектирования. Г.:Энергия, 1979. — 392 с.
9. Демидович Б.П., Марон И.А. Основы вычислительной математики. Г.: Изд-во «Наука»,1966. — 664 с.
10.Разевиг В.Д. Система сквозного проектирования электронных устройствDesignLab 8.0.- М.: Изд-во «Солон»,1999. — 698 с.
11. Автоматизация схемотехнического проектирования на мини-эвм: Учебноепособие/ Под ред. Проф. Анисимова. Л. Изд-во ЛГУ, 1983. — 200 с.
12. Чуа Л.О., Пен-Мин Линь. Машинный анализ электронных схем: Алгоритмы ивычислительные методы. Пер с англ. Г.: Энергия, 1980. – 640 с.
13. Математическое и программное обеспечение САПР радиоэлектроннойаппаратуры: Учебное пособие/ Огороднейчук И.Ф., Семенец В.В., Куник Э.Г. и др.К.: УМК ВО, 1988. — 104 с.