WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Технологія розробки мереж Петрі та вирішення проблем які виникають при їх використанні - Дипломна робота

Технологія розробки мереж Петрі та вирішення проблем які виникають при їх використанні - Дипломна робота

дещо пізніше Родрігес ввів поняття "програмних графів" [11] які лягли в основу потоків даних Деніса-Фоссіна [11]. З останнім тісно пов'язані моделв Берса та Косинського; дещо відмінна модель представлена Адамсом [17] який істотно використовував поняття черги FIFO.
На схемах Карпа - Міллера були досліджені такі властивості паралельних обчислень, як комутативність, стійкість, результативність, безповоротність, однозначність та детермінованість. Основні результати можна звести внаступні теореми.
Для схем Карпа - Міллера розв'язно:
1. Чи являється безповоротною схема з скінченим числом керуючих станів.
2. Чи являється обмеженою без повторна схема з кінцевим управлінням.
3. Чи виконується довільний оператор в без повторній схемі з кінцевим управлінням скінчене число разів при любому обчислені.
4. Стійка, комутативна, без повторна, і результуюча схема з кінцевим керуванням є детермінованою.
5. Нерозв'язно, чи еквівалентні дві стійкі схеми з кінцевим керуванням.
6. Нерозв'язно, чи еквівалентні дві обмежені схеми з кінцевим керуванням.
В моделі Адамса змінна також є чергою типу FIFO. З кожною чергою зв'язується інформація про статус, яка використовується для управління при безумовних і умовних переходах.
Якщо в моделі Карпа - Міллера оператор готовий до роботи тільки тоді коли його вхідні черги не порожні, то в моделі Адамса ця умова неявна, воно моделюється відповідними значеннями статусу. Адамс дозволяє в своїй моделі і рекурсивні процедури. Якщо вхідні черги мають довжину більшу за 1 , тобто дозволяють оператору виконатися кілька разів, то створюється необхідна кількість копії оператора, і всі вони можуть виконуватись одночасно. Адамс доказав, що всі обчислення в його моделі детерміновані.
Якщо у всіх розглянутих моделях ще на рівних існували два графа - граф керування, та граф інформаційної залежності, то в моделі Денніса - Фоссіна принцип потокового керування проведено уже в чистому вигляді: основу керування складає інформаційний граф в якому дуги потрібно вважати каналами, по яких переносяться потоки значень між вершинами. Вершини здійснюють виконання функції (операції) або обчислюють предикати або керують потоками даних. Проста схема потоку даних для обчислення функції приведено на рис. 9.
рис. 9. Приклад схеми потоку даних
Означення 19 Схема потоку даних є дводольний орієнтований граф в якому виділяється множина вершин і множина з'єднуючих їх дуг. Множини дуг розбита на множини зв'язку і вершини актори. Є два типи вершин зв'язку: зв'язку даних і керуючого зв'язку (рис. 10), та п'яти типів акторів: оператори, розпізнавані, клапани типу "true" та "false", вершини злиття та вершини, які реалізують логічні функції (рис. 11). Множина дуг складається із дуг даних і керуючих дуг в залежності від типу вершин з яких вони виходять. Дуги являються каналами по яких пересилаються потоки значень між вершинами.
рис. 10. Зв'язки даних та керуючі зв'язки
рис. 11. П'ять типів акторів
Серед всіх вершин схеми S виділяються дві не порожні кінцеві множини: In(S) - вхідних та Out(S) - вихідних вершин зв'язку даних. Ніяка дуга S не може закінчуватися ні одній із її вхідних вершин; по крайній мірі одна із дуг S повинна виходити із кожної вершини зв'язку, яка не являється вихідною вершиною.
Означення 20 Конфігурацією схеми потоку даних для інтерпретації з областю визначення D являється:
1. Співставлення значень із D або символа null кожній дузі даних схеми S.
2. Співставлення одного із символів {true, false, null} кожній керуючій дузі схеми.
Конфігурація зображається з допомогою фішок, які розставлені на дугах, яким співставлено не порожнє значення, рядом записано саме його значення.
Розділ 2
МЕРЕЖІ ПЕТРІ
2.1 ЗАГАЛЬНІ ВІДОМОСТІ ПРО МЕРЕЖІ ПЕТРІ
Мережі Петрі важко з впевненістю віднести до якоїсь категорії моделей, які були розглянуто в другому пункті. З одної сторони керування задається орієнтованим графом, тобто при переході від вершини до вершини присутня компонента імперативності. З іншої сторони, спрацювання кожного акта можна трактувати як виконання продукції з досить простими умовами - наявністю всіх вхідних даних. Мережу Петрі можна використовувати і для генерації одного обчислювального процесу, і для опису взаємодії між різними процесами. Найбільш повний огляд по мережам Петрі можна знайти в роботах [16, 17].
Означення 21 Мережею Петрі називається п'ятірка , в якій Р - деяка множина так званих місць, Т - множина переходів, F та H - функції інцидентності, . Неформально функцію F можна трактувати як множину стрілок, які ведуть із місць до переходів, а Н - множину стрілок, які ведуть від переходів до місць. Компонента М0 - в означені початкова розмітка, яка заключається в співставленні кожному місцю деякої кількості так званих фішок.
Приклад мережі Петрі приведено на рис. 12. в ній є три місця та чотири переходи a, b, c, d. Також є п'ять стрілок множини F та п'ять стрілок множини Н. Розмітка мережі Петрі зображається вектором , на і-й позиції якого знаходиться число, рівне числу фішок на і-му місці. Так початкова розмітка, зображена на рис 12, зображається вектором (1, 1, 0).
рис. 12. Приклад мережі Петрі
Нехай t - деякий перехід. Місце p називається вхідним для t, якщо F(p,t)=1, і вихідним якщо H(t,p)=1. місце може бути і вхідним і вихідним одночасно.
2.2 ПРИНЦИП ФУНКЦІОНУВАННЯ МЕРЕЖІ ПЕТРІ
Функціонування мережі Петрі заключається в переході від розмітки до розмітки по наступним правилам. Перехід t може спрацювати тоді якщо в кожному його вхідному місці є хоча б одна фішка. Спрацювання переходу заключається в вилучені із кожного вхідного місця по одній фішці, і добавлення по одній фішці в кожне вихідне місце. Так формується нова розмітка. Наприклад в мережі, яка зображена на рис. 12, при розмітці М0 може спрацювати перехід b, тоді нова розмітка М після спрацювання буде (0, 0, 1). Функціонування мережі закінчується якщо нема жодного переходу який міг би спрацювати. Розмітка при якій це стало можливим називається тупиковою. Наприклад якщо після розмітки М спрацює перехід с, то отримається розмітка М =(0, 1, 0), при якій для любого переходу не виконується умова спрацювання. Вона являється тупиковою.
Із опису роботи мережі Петрі видно, що вона може задавати одночасно виконання кількох процесів на різних своїх ділянках. Процеси виконуються асинхронно, але можлива і їх синхронізація. Наприклад, робота двох процесорів над загальною пам'яттю, описується мережею, яка зображена на рис. 13. місце р в ній має одну фішку, яка використовується то одним то іншим процесом на час запису в пам'ять, і тим самим блокує запис іншим процесом.
рис. 12. Приклад використання мережі Петрі (в ОС)
Перед тим як перейти до викладення основних властивостей мереж Петрі, дамо деякі означення.
Означення 22 Якщо при
Loading...

 
 

Цікаве