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

Дипломна робота з програмування

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

ЗМІСТ

TOC \o «1-2» \u ВСТУП PAGEREF _Toc103085475 \h 4

Розділ 1 PAGEREF _Toc103085476 \h 6

1.1. ОБЧИСЛЮВАЛЬНІ ПРОЦЕСИ НАД ПАМЯТТЮ PAGEREF _Toc103085477 \h 6

1.2. СТРУКТУРИ КЕРУВАННЯ PAGEREF _Toc103085478 \h 14

1.3. А–СХЕМИ, А–ПРОГРАМИ PAGEREF _Toc103085479 \h 19

1.4. ПАРАЛЕЛЬНІ ОПЕРАТОРНІ СХЕМИ PAGEREF _Toc103085480 \h 24

1.5. МОДЕЛІ ПОТОКІВ ДАНИХ PAGEREF _Toc103085481 \h 28

Розділ 2 PAGEREF _Toc103085482 \h 33

МЕРЕЖІ ПЕТРІ PAGEREF _Toc103085483 \h 33

2.1 ЗАГАЛЬНІ ВІДОМОСТІ ПРО МЕРЕЖІ ПЕТРІ PAGEREF _Toc103085484 \h 33

2.2 ПРИНЦИП ФУНКЦІОНУВАННЯ МЕРЕЖІ ПЕТРІ PAGEREF _Toc103085485 \h 34

2.3 ПРОБЛЕМИ РОЗВ’ЯЗНОСТІ МЕРЕЖ ПЕТРІ PAGEREF _Toc103085486 \h 38

2.4 РОЗШИРЕНІ МЕРЕЖІ ПЕТРІ PAGEREF _Toc103085487 \h 41

Розділ 3 PAGEREF _Toc103085488 \h 44

3.1. ПЕРЕВІРКА МЕРЕЖІ ПЕТРІ НА ІСНУВАННЯ ТУПИКОВОЇ РОЗМІТКИ (ДЕДЛОКУ)
PAGEREF _Toc103085489 \h 44

3.2. КОРИСТУВАННЯ ПРОГРАМОЮ PAGEREF _Toc103085490 \h 52

ВИСНОВКИ PAGEREF _Toc103085491 \h 60

ЛІТЕРАТУРА PAGEREF _Toc103085492 \h 61

ДОДАТОК PAGEREF _Toc103085493 \h 63

ВСТУП

В наш час все більшого поширення набула проблема паралельного
обчислення. Разом з нею і виникло багато інших проблем серед яких і
моделювання розподілених обчислень. При моделюванні розподілених
обчислень розглядаються і класичні мережі Петрі, де і є проблема
виникнення тупикової розмітки (deadlock). Дослідження цієї проблеми і
зумовлює актуальність обраної теми.

Класичні мережі Петрі використовуються саме для проектування
розподілених обчислень і широко використовується при розробці
паралельних процесів та іншого. За допомогою класичних мереж Петрі
навіть моделюються операційні системи.

При розгляданні класичних мереж Петрі багато інформації наведено в таких
книгах: Алгоритмы, математическое обеспечение и архитектура
многопроцессорных вычислительных систем; Воеводин В.В. Математические
основы параллельных вычислений; Теория параллельного программирования:
Прикладные Аспекты.

При досліджені проблеми виникнення тупикової розмітки багато інформації
здобуто з наступних джерел: Элементы параллельного программирования;
Параллельные вычислительные системы.

Розглянуто також розширені мережі Петрі і описані вони в наступній
літературі: Разрешимость функциональной эквивалентности на подклассе
схем потоков данных.

Мета роботи – дослідження класичних мереж Петрі, вивчення їх недоліків
та проблем які виникають при їх використані, дослідження проблеми
досяжності тупикової розмітки.

Для досягнення мети в роботі потрібно вирішити такі задачі:

вивчити принцип роботи класичних мереж Петрі;

вивчити причини виникнення проблем при їх використанні мереж Петрі;

вивчити проблему досяжності тупикової розмітки в класичних мережах
Петрі.

Об’єкт дослідження: технологія розробки мереж Петрі та вирішення проблем
які виникають при їх використанні.

Предмет дослідження: можливості класичних мереж Петрі, виникнення тупи
кокової розмітки. Дослідження мереж Петрі на виникнення тупикової
розмітки.

Практична значущість: результатом дослідження є програма яка може бути
використана, як в практиці так і в начальному процесі.

Робота складається з вступу, трьох розділів та висновку. В кінці роботи
наведено список використаної літератури та додатки.

У вступі розкривається актуальність обраної теми, визначено об’єкт та
предмет дослідження та дається характеристика кожного розділу.

В першому розділі розглянуто базові поняття та принципи роботи
паралельного обчислення .

Другий розділ повністю присвячений розгляду класичних мереж Петрі.

Третій розділ присвячено опису програмного продукту, реалізація та
інструкція по використанню.

У висновках звертається увага на обґрунтування результатів дослідження,
узагальнюються окремі факти та ідеї, що формувалися під час дослідження.

В додатку наведено вихідні коди розробленого програмного продукту.

Розділ 1

1.1. ОБЧИСЛЮВАЛЬНІ ПРОЦЕСИ НАД ПАМЯТТЮ

Виразом інформаційних складових в наших моделях буде множина процесів,
які представляють собою послідовність включення і виключення деяких
операторів. В залежності від порядку включення і виключення процеси
можуть бути або послідовними або паралельними.

будуть позначати k-ту компоненту цих множин. Припускається, що
виконується умова

Таким чином, ніякі два виходи не виробляють одну і ту ж змінну. Крім
того, припускається, що F включає в себе два спеціальних символа: і –
для оператора вводу та о – для оператора виводу інформації.

Означення 1: описана пара множин (M, F) називається інформаційним
базисом.

Можливі і інші варіанти при описанні інформаційного базиса. Наприклад
іноді в якості входів і виходів оператора at зручно розглядати деякі
абстрактні елементи ta та at (індекс перед а означає вхід, а після

а – вихід). З кожним із таких елементів з допомогою деякого відображення
співставляється деяка своя змінна.

. Перший вказує на початок роботи оператора а, а другий на завершення
його роботи.

вимагається :

містить п символів виключення оператора а, то він містить не менше ніж
п операторів включення а. Ця аксіома виражає природну вимогу про те, що
виключення оператора не може бути раніше його включення.

скінчений, він містить включення і виключення оператора а. Також
природна вимога: після завершення „роботи” всі процеси які були
включені повинні бути завершені.

або нескінчений і тоді має не більше одного входження символа о, або
скінчений і тоді містить єдине входження цього символа. Помітимо, що ця
умова слабша, чим вимога про вихід із обчислення через оператор виводу:
останнє входження в процес не обов’язково о. Не рідко додатково потрібні
іще дві умови.

. Цю вимогу можна назвати відсутністю авто паралельності, тобто
одночасного виконання оператора а з самим собою.

Оператор а може включитися тільки тоді, коли вироблена інформація для
кожного із його входів попередніми операторами.

рис. 1. Приклад послідовної програми

.

Обчислювальні процеси зручно представляти в вигляді часових діаграм.
Нехай наприклад,

. Перший із них – послідовний (рис 1.), а другий паралельний (рис 2.).

рис. 2. Приклад паралельної програми

має два акта оператора а: 1-й між 1-им та 5-им, 2-й між 3-ім та 7-им
тактами.

, а стрілки проводяться в відповідності до наступних правил:

Стрілка може вести тільки з деякого виходу в деякий вхід.

, то стрілка веде із Outj(a) в Ink(b). Інших стрілок нема.

ізоморфні якщо існує взаємо однозначне відображення між їх вершинами,
при якому входам і виходам співставляється входи і виходи актів одно
іменних операторів і які узгоджені з стрілками інформаційної залежності.
Далі будемо говорити про рівність інформаційних графів з точністю до
ізоморфізму.

Інформаційний граф процесу вказує шляхи передачі інформації при
реалізації процесу ( над загальною пам’яттю. Інформація для деякого
входу береться завжди з останнього виробляючого відповідну змінну акту.
Для прикладу інформаційні графи процесів ( та ( показані на рис 3.

рис. 3. Інформаційні графи

.

, то х являється термом.

являється термом.

.

.

. Таким чином кожне виконання акта в базисі класу LL спричиняє за собою
зміну стану пам’яті. Ця властивість являється дуже важливою в теорії
паралельного програмування, в чому ми ще не раз переконаємося. Має місце
наступна фундаментальна лема про зв’язок різних атрибутів процесів.

Лема 1

Для довільних процесів ( та (:

, але супротивне не вірне.

, але супротивне не вірне.

випливає, що рівність терм-історії операторів виводу цих процесів, але
супротивне не вірне.

.

Скажемо декілька слів про значення цієї леми.

На формальних моделях розв’язуються різні за природою задачі. Так, одна
із них – перевірка не детермінованості деякої програмної або апаратної
моделі: чи гарантовано те, що на одних і тих же вхідних даних при любих
режимах обчислення видається однаковий результат. Друга важлива проблема
– перевірка еквівалентності двох моделей: чи реалізують вони одну і ту ж
функцію. Третя задача – розпаралелення програм – заключається в тому, що
по мірі паралельності чи навіть послідовній програмі будується
максимально паралельна, еквівалентна первинній. Не дивлячись на зовнішню
відмінність, у всіх трьох випадках потрібно потурбуватися про те, щоб
деякий набір процесів реалізував одну і ту ж функцію. В першому випадку
це набір процесів схеми, яка перевіряється на детермінованість, в
другому – сукупність процесів схем, для яких перевіряється відношення
еквівалентності, в третьому – множина процесів, яка розширює процеси
програми яка розпаралелюється.

Розглянемо деякі перетворення процесів, які зберігають вказані
інваріанти. Спочатку приведемо фундаментальну умову із теорії
паралельного програмування, яке було незалежно сформульоване Берштейном,
Раселлом та Наріньяні, але в літературі його частіше називають умовою
Бернштейна. Припустимо, що для операторів а та b виконується умова
Бернштейна, якщо

. (1.1)

Для скороченого запису цієї умови приймемо позначення а/b, а при
невиконанні його – позначення ‘a/b, якщо для деяких відрізків ( та (.

.

Лема 1.2

.

Розглянемо відповідне відношення еквівалентності ~: процеси ( та (
знаходяться в цьому відношенні якщо один отримується з іншого з
допомогою вказаних перестановок. Виявляється, воно близьке до відношення
еквівалентності по рівності історій комірок. Перед тим як показати це,
введемо одне дуже важливе поняття.

. Таким чином, кожне включення оператора відбувається на поновлених
даних. Звідси, випливає, що довільний оператор без входів зустрічається
не більше одного разу. Очевидна наступна лема.

Лема 1.3

тоді і тільки тоді, коли не містить двох актів з однаковою t-історією.

Спів відношення між еквівалентностями по історіям комірок та ~
встановлює наступну лему.

Лема 1.4

;

.

— відображення, яке перетворює оператор ний символ а в перетворювач
над пам’яттю. Під т розуміємо число входів, а під п число виходів
оператора а.

визначене, то

(1.2)

.

, тобто при початковому стані пам’яті в комірці х міститься терм х,

,

якщо останній є термом, і не визначений в супротивному випадку.

В даному випадку для інформаційного базису існує всього одна вільна
інтерпретація. В випадку інших моделей, як показано нижче, існує їх може
бути скінчена кількість. Вільна інтерпретація цікава тим, що її засобами
встановлюється прямий зв’язок між синтаксисом та семантикою процесів,
тобто правдива наступна лема.

Лема 1.5

. Доведення випливає із розгляду t-історії комірки і вмісту комірки при
вільній інтерпретації.

. В повній мірі значимість цього наслідку буде видна при розгляді
наступних моделей. Зараз же вона нам стане в нагоді доведення основного
твердження цього розділу.

Теорема 1.1

.

, видно , що при фіксованому процесі при любій інтерпретації інформація
для любого акта береться із одних і тих же виходів. Виходячи з цього при
любій інтерпретації формується режим переробки інформації, який
задається термом t звідки випливає рівність вмісту комірок із лівої
частини теореми.

Щойно доведена теорема носить назву теорема про вільну інтерпретацію.
Вона показує, що в деякому смислі вільна інтерпретація являється
представником всіх інтерпретацій даного інформаційного базису. Багато
подальших тверджень будемо формулювати з квантом все загальності І. Це
звичайний прийом теорії моделей програм і обчислень. І для того щоб їх
перевірити нема необхідності перебирати всі інтерпретації. Більш того,
це неможливо. Достатньо перевірити твердження по всіх вільних
інтерпретаціях. В випадку „некерованих” обчислювальних процесів вона
одна, в випадку інших моделей вільних інтерпретацій може бути довільне
число; головне, щоб всі вони будуть описуватись досить осяйно для
перевірки потрібних тверджень. Теорема 1.1 буде при цьому модифікуватися
і прийматиме специфічні відтінки, але в цілому її смисл залишиться. Вона
дозволяє позбутися або різко скоротити область дії квантора все
загальності для інтерпретацій.

1.2. СТРУКТУРИ КЕРУВАННЯ

Вище розглянуті процеси – послідовність деяких дій, які перетворюються
при задані інтерпретації в досить конкретні акти. Означення процесу не
було зв’язане з яким не будь способом генерації актів або обмеженнями на
їх появу в процесі. Можна вважати, що процес являється протоколом
спрацювання актів після того як на деяких початкових даних відпрацювала
деяка обчислювальна система, яка виконувала який не будь контроль при
обчислюванні, але цей контроль ніяк не відображений в протоколі. В
даному пункті буде розглянуто ця друга складова обчислення – контроль –
в „чистому” вигляді, без відношення до інформаційного складу актів,
керування якими буде вестись.

Най простішою структурою контролю являється орієнтований граф, в
конкретних моделях зазвичай називають управляючим графом. Якщо G=(W,A),
де W – множина вершин, А – множина стрілок, то в W виділяються вхідна і
вихідна вершини, а кожній стрілці співставляється символ включення або
виключення деякого оператора. Таким чином любому шляху із вхідної
вершини в вихідну або нескінченому співставляється послідовність
включень і виключень. Множину всіх послідовностей які з’являються
позначимо через Pass(a). Якщо люба така послідовність являється
процесом, то граф G називається правильним.

Перше питання яке виникає – це чи існує алгоритм перевірки правильності
графа. Оказується, що в випадку моделі яку ми розглядаємо множина
процесів які породжуються є регулярною, і відповідь проста. Такий
алгоритм є і оснований на тому, що якщо граф породжує деяку
послідовність (, на якій порушується люба аксіома процесу, то він
породжує деякий процес ((, яка не являється процесом, обмеженої довжини.
В якості границі для перевірки завжди можна взяти 2k|W|, де k – число
простих циклів в графі G. Доведення цього твердження основане на
скорочені ( виключенням з нього зайвих циклів.

Формування обчислювального процесу по графу G походить так, що при русі
із деяких вершин ми можемо піти в довільному але тільки одному
напрямку. Таким чином, контроль, який задається управляючим графом,
являється не детермінованим, але не паралельним. Паралелізм досягається
в наслідок розділення актів включення і виключення, і тільки. Інша більш
складна модель керування отримується якщо, допустити одночасний рух по
деяким стрілкам. Моделі такого типу отримали назву графових моделей
паралельних програм і вивчалися найбільш інтенсивно.

– множина функцій, які вибирають на основі поточного стану пам’яті
деяку альтернативу. Управляючий автомат над множиною символів включення
і виключення

визначена. Як завжди робота автомата полягає в переході із одного
стану в інший в відповідності з „вказівками” функції (. Рух починається
з початкового стану і закінчується в першому кінцевому стані який
зустрінеться. По скінченим автоматам є великий вибір книг.

. Користуючись цими позначеннями вже можна сформулювати основні
проблеми для структур керування.

1. Проблема детермінованості U. Нехай на множині обчислювальних процесів
задане деяке відношення еквівалентності ~, наприклад:

а) ( еквівалентне ( тоді і тільки тоді, коли (=(;

— еквівалентність по історіям комірок;

— еквівалентність по інформаційному графу;

— еквівалентність по t-історії;

— еквівалентність по кінцевим станам пам’яті;

— функціональна еквівалентність. Потрібно перевірити виконання формул:

.

.

2. Проблема еквівалентності структурU та U( (U~U(?):

.

.

Видно, що проблема детермінованості може розглядатися як частинний
випадок проблеми еквівалентності: схема являється детермінованою, якщо
вона еквівалентна сама собі.

3. Проблема обчислюваності для U та U( (U(>U?):

.

.

4. Проблема максимального (найбільшого) розпаралелення. Перетворити U в
U( , так щоб: 1) U( ~ U; 2) U( — максимальна (найбільша) по відношенню >
в класі всіх структур {U(( : U(( ~ U}. Якщо не мати на увазі тривіальну
еквівалентність а), яка властива тільки послідовним структурам
керування, то можна сказати наступне. В перших трьох проблемах присутні
дві постановки А та Б, при чому друга більш „тонка” оскільки враховує
інтерпретацію. Відповідне відношення називається інтерпретаційним, і не
важко помітити, що виконання Б завжди тягне за собою виконання А.
Проблеми в формулюванні Б стають часто нерозв’язними [12]. Четверту
проблему також можна сформулювати використовуючи відношення ~, > типу А
або Б. В роботі [5] показано, що в другому випадку для достатньо
нетривіальних моделей вона теж нерозв’язна. Розв’язність буде мати місце
або при деякому спрощені відношень ~ та >, або при переході до більш
вузьким класам моделей.

Враховуючи нерозв’язність багатьох проблем в загальному випадку цікавими
стають достатні умови для виконання тої чи іншої властивості. Для
проблеми детермінованості найбільш загальні результати в цьому
відношенні отримані в роботі [15].

Означення 11. Діаграмою назвемо трійку (Q, (, (), де Q – деяка множина
станів; ( – бінарне відношення на ньому; q ( q( означає наявність
переходу із стану q в стан q(; ( – деякий алфавіт, символи якого
приписані переходам.

.

Діаграма (Q, (, () має властивості:

а) (автоматна) детермінованість, якщо

;

б) комутативність, якщо

;

в) стійкості, якщо

;

г) Черча – Россера, якщо

.

Із перелічених властивостей перші три мають локальний характер і
взагалом піддаються ефективній перевірці, в той час як четверте для
кожної трійки станів q, q1, q2 потребує глобального аналізу діаграм.

В роботі [15] приведено використання даних властивостей і сформульована
наступна теорема.

Теорема 2.1

Виконання умов а), б), та в) в сукупності тягне за собою виконання умови
г). Таким чином теорема дає достатні умови локального типу для
забезпечення виконання глобальної умови. Вона цікава в паралельному
програмуванні в багатьох відношеннях.

1.3. А–СХЕМИ, А–ПРОГРАМИ

Розглянемо одну із найбільш представницьких моделей, яка розроблена в
колишньому радянському союзі: асинхронні схеми (А-схеми), та якщо
розглядати їх разом з інтерпретацією, асинхронні програми (А-програми)
[1, 7, 8, 9]. Різні означення А-схеми в різних роботах мають деяке
відхилення одне від одного.

.

Означення 13 Інтерпретована А-схема називається А-програмою і працює
наступним чином.

=1.

співпадають, але потребується щоб для довільних двох актів операторів
a, b не співпадали їх активні моменти. Ця умова дозволяє повністю
впорядкувати всі оператори включень і виключень модулів і розглядати їх
як процеси які визначені в пункті 1.

В довільний неактивний момент часу деякі модулі знаходяться в активному
стані, деякі – в неактивному. Тоді перевіряються спускові модулі всіх
неактивних модулів і любий із модулів, у якого спускова функція рівна 1,
може ввімкнутися і працювати довільний скінчений проміжок часу.
Ввімкнення в кожний момент часу дозволяється тільки одному модулю із-за
сформульованої вище вимоги не спів падання моментів включення. Дозвіл на
включення зберігається до тих пір поки не пройшло вимкнення деякого
акта. На протязі цього часу стан пам’яті не змінюється, і пере
обчислення спускових функцій приведе до того самого результату.

включають тільки змінні керування пам’яттю, то можна розглядати
інтерпретацію лише одної керуючої структури, не привертаючи
інтерпретацію пам’яті М в операторів.

Особливо складним для А-схеми являється питання детермінованості та
еквівалентності. Справа в тому, що модулі працюють абсолютно автономно,
асинхронно, без зв’язку з якою несуть послідовною структурою, як це
було, наприклад, з допомогою автомату. Тому важко прослідкувати
потенційно можливі послідовності актів та інформаційні зв’язки між ними.
Але для розпізнавання властивості не детермінованості по інформаційному
графу можна дати одну просту умову.

Лема 3.1

Якщо

(3.1)

то схема S не є детермінованою по інформаційному графу.

, при цьому, так як aта b конкурують над пам’яттю, зв’язки які будуть
сформовані будуть різними, що потягне за собою різницю в інформаційних
графах.

можна дати наступну достатню умову.

Лема 3.2

, то S(>S, де відношення розуміється в інтерпретаційному смислі.

Стандартні схеми можуть моделювати широкий клас програм, але більш
всього вони пристосовані для представлення алголоподібних конструкцій.
Нехай, наприклад задана наступна програма, яка обчислює вираз sin(x)/y2
і виводить повідомлення про нерозв’язність при y=0:

i: введення (x, y);

a: x=sin(x);

b: y=y(2;

c: якщо y=0 то на m1, інакше на m2;

m1: вивід („результат невизначений, так як y=0”);

d: на о;

m2: y=x/y;

o: вивід(y);

Блок схема цієї програми показана на рис. 4, а відповідна стандартна
схема на рис. 5 остання відмінна від блок-схеми тим, що всі її оператори
не інтепритовані, показані тільки вхідні і вихідні змінні і передача
керування.

рис. 4. Блок-схема програми

рис. 5. Стандартна схема

рис. 6. Схема передачі керуввання

Ця інформація використовується при алгоритмі перетворення стандартних
схем в А-схеми, який вирішує четверту задачу – задачу розпаралелюваня,
яка сформульована в другому пункті. При цьому в якості відношення
еквівалентності використовується еквівалентність по інформаційному
графу.

1.4. ПАРАЛЕЛЬНІ ОПЕРАТОРНІ СХЕМИ

Паралельні операторні схеми являються мабуть самою розгалуженою і
найбільш дослідженою моделлю паралельних програм. В одній із перших
робіт [13], в якій вони були запропоновані, розглядаються питання,
зв’язані з детермінованістю та еквівалентністю. В роботі [14],
вивчається проблема обчислювальності, а в [4, 6, 10]– проблема
максимального розпаралелення. Результати щодо нерозв’язних проблем
отримані в [3, 5, 12].

так, як він був визначений в пункті другому. Приклад операторної схеми
зображено на рис. 7. Для цієї схеми

. Множина префіксів цих процесів в відповідністю з пунктом другим
позначимо як Pref(S, I).

рис. 7. Приклад операторної схеми

Більш точно, в довільний момент часу робота схеми характеризується
вектор-станом, який має три компоненти: стан пам’яті (, стан
управляючого автомата q та сукупність наборів аргументів які
обробляються для кожного оператора ( та ((а) позначає чергу оператора а.

співставляє кожному оператору порожню послідовність. Формуючий процес,
або правильніше кажучи префікс процесу, являється порожньою множиною
символів включення і виключення ?.

Означення 14 Нехай задана схема S=(M, F, A).

.

Таким чином схема вільна, якщо довільна послідовність переходів
структури керування може бути реалізована при деякій інтерпретації. Далі
клас всіх вільних схем будемо позначати через F.

володіє властивістю RF.

Лема 4.1

. Таким чином, єдиною причиною відсутності свободи в схемі являється
порушення сформульованої вище властивості.

і схема вільна, то вона належить класу RF.

Теорема 4.1

Існує алгоритм розпізнавання належності довільної лічильникової схеми
класуRF.

Доведення: зводиться до проблеми досяжності для систем векторного
додавання, апарат який буде використовуватися нами при находженні
алгоритму розпізнавання обмеженості мереж Петрі (пункт 6). Будемо
говорити, що схема S належить класу або задовольняє властивості LL, якщо
базис (M, F) належить цьому класу.

Теорема 4.2

Для детермінованих схем класу RF , які задають реалізаціюз скінченим
числом станів, дозволена властивість „бути максимально паралельним”.

В роботі [14] вивчається також питання про ефективність побудови по
заданій схемі еквівалентній їй максимально паралельною. Виявляється, що
зазвичай процедура розпаралелювання виводить за межі класу схем, для
яких вона визначена. Наприклад, для схеми яка задається кінцевою
реалізацією (рис. 8), не існує еквівалентної максимально паралельної
схеми з кінцевою реалізацією, але для неї існує реалізація в вигляді
лічильної схеми.

рис. 8. Схема для якої не існує еквівалентної максимально паралельної
схеми з кінцевою реалізацією

. Моменти включення операторів в обчислювальному процесі не
відображені.

при деякій однозначності ефективній нумерації. Таким чином кожен
обчислений результат засилається в свої індивідуальні комірки.

Теорема 4.3

тоді і тільки тоді коли функція Lah( — ефективна. При цьому алгоритм
розпаралелення визначається по функції Lah( конструктивно.

Із теореми 4.3 отримується ряд наслідків два із яких сформульовані нище.

Наслідок 1. Для класу стандартних схем не існує алгоритму максимального
розпаралелення.

Наслідок 2. для класу кінцевих вільних схем. Келлера існує алгоритм
максимального розпаралелення.

1.5. МОДЕЛІ ПОТОКІВ ДАНИХ

Концепція потоків даних основана на тому, що послідовність обчислень
визначається наступними даними: оператор може виконуватись, як тільки
обчислені потрібні для нього операнди, тобто допускається експліцитна
залежність між операторами по даних. Оскільки доступність обчислених
операндів дозволяє одночасне виконання кількох операторів, паралельність
дій являється внутрішньою властивістю схем потоків даних.

Одна із перших моделей, яка неявно використовувала принцип потоку даних
, — це модель Карпа та Міллера [13]. дещо пізніше Родрігес ввів поняття
„програмних графів” [11] які лягли в основу потоків даних Деніса-Фоссіна
[11]. З останнім тісно пов’язані моделв Берса та Косинського; дещо
відмінна модель представлена Адамсом [17] який істотно використовував
поняття черги FIFO.

На схемах Карпа – Міллера були досліджені такі властивості паралельних
обчислень, як комутативність, стійкість, результативність,
безповоротність, однозначність та детермінованість. Основні результати
можна звести в наступні теореми.

Для схем Карпа – Міллера розв’язно:

Чи являється безповоротною схема з скінченим числом керуючих станів.

Чи являється обмеженою без повторна схема з кінцевим управлінням.

Чи виконується довільний оператор в без повторній схемі з кінцевим
управлінням скінчене число разів при любому обчислені.

Стійка, комутативна, без повторна, і результуюча схема з кінцевим
керуванням є детермінованою.

Нерозв’язно, чи еквівалентні дві стійкі схеми з кінцевим керуванням.

Нерозв’язно, чи еквівалентні дві обмежені схеми з кінцевим керуванням.

В моделі Адамса змінна також є чергою типу FIFO. З кожною чергою
зв’язується інформація про статус, яка використовується для управління
при безумовних і умовних переходах.

Якщо в моделі Карпа – Міллера оператор готовий до роботи тільки тоді
коли його вхідні черги не порожні, то в моделі Адамса ця умова неявна,
воно моделюється відповідними значеннями статусу. Адамс дозволяє в своїй
моделі і рекурсивні процедури. Якщо вхідні черги мають довжину більшу за
1 , тобто дозволяють оператору виконатися кілька разів, то створюється
необхідна кількість копії оператора, і всі вони можуть виконуватись
одночасно. Адамс доказав, що всі обчислення в його моделі детерміновані.

приведено на рис. 9.

рис. 9. Приклад схеми потоку даних

Означення 19 Схема потоку даних є дводольний орієнтований граф в якому
виділяється множина вершин і множина з’єднуючих їх дуг. Множини дуг
розбита на множини зв’язку і вершини актори. Є два типи вершин зв’язку:
зв’язку даних і керуючого зв’язку (рис. 10), та п’яти типів акторів:
оператори, розпізнавані, клапани типу „true” та „false”, вершини злиття
та вершини, які реалізують логічні функції (рис. 11). Множина дуг
складається із дуг даних і керуючих дуг в залежності від типу вершин з
яких вони виходять. Дуги являються каналами по яких пересилаються потоки
значень між вершинами.

рис. 10. Зв’язки даних та керуючі зв’язки

рис. 11. П’ять типів акторів

Серед всіх вершин схеми S виділяються дві не порожні кінцеві множини:
In(S) – вхідних та Out(S) – вихідних вершин зв’язку даних. Ніяка дуга S
не може закінчуватися ні одній із її вхідних вершин; по крайній мірі
одна із дуг S повинна виходити із кожної вершини зв’язку, яка не
являється вихідною вершиною.

Означення 20 Конфігурацією схеми потоку даних для інтерпретації з
областю визначення D являється:

Співставлення значень із D або символа null кожній дузі даних схеми S.

Співставлення одного із символів {true, false, null} кожній керуючій
дузі схеми.

Конфігурація зображається з допомогою фішок, які розставлені на дугах,
яким співставлено не порожнє значення, рядом записано саме його
значення.

Розділ 2

МЕРЕЖІ ПЕТРІ

2.1 ЗАГАЛЬНІ ВІДОМОСТІ ПРО МЕРЕЖІ ПЕТРІ

Мережі Петрі важко з впевненістю віднести до якоїсь категорії моделей,
які були розглянуто в другому пункті. З одної сторони керування
задається орієнтованим графом, тобто при переході від вершини до вершини
присутня компонента імперативності. З іншої сторони, спрацювання кожного
акта можна трактувати як виконання продукції з досить простими умовами –
наявністю всіх вхідних даних. Мережу Петрі можна використовувати і для
генерації одного обчислювального процесу, і для опису взаємодії між
різними процесами. Найбільш повний огляд по мережам Петрі можна знайти в
роботах [16, 17].

. Неформально функцію F можна трактувати як множину стрілок, які ведуть
із місць до переходів, а Н – множину стрілок, які ведуть від переходів
до місць. Компонента М0 – в означені початкова розмітка, яка
заключається в співставленні кожному місцю деякої кількості так званих
фішок.

, на і-й позиції якого знаходиться число, рівне числу фішок на і-му
місці. Так початкова розмітка, зображена на рис 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 Якщо при розмітці М можливе спрацювання переходу t і після
нього виникає нова розмітка М( , то будемо говорити, що М( слідує за
М, і писати М?М(.

Означення 23 Розмітку будемо називати просто досяжною, якщо вона досяжна
із початкової розмітки М0 з допомогою деякої послідовності переходів.
Через R(N) позначимо множину всіх розміток які можна досягти в мережі N.
При неформальній інтерпретації поняття досяжності визначає, в які стани
може потрапити система яка описана даною мережею. Наприклад, якщо в R(N)
входить тупикова розмітка, то це значить, що системі загрожує дедлок.
Тому знання інформації про множину R(N) дуже важливі.

Аналогічне означення можна ввести і для переходів. Так мова L(N) яка
породжена мережею N, по означенню є множиною послідовностей, які можуть
спрацювати із початкової розмітки.

Означення 24 Перехід називається живим, якщо він досяжний із любої
розмітки множини R(N). Мережа N – жива якщо всі переходи в ній живі.

На рис. 13, зображена мережа, в якій перехід а не є живим. Єдина фішка
може переміщатися в ній по верхньому циклу, але може провалитися в
нижній. Після цього на верхній рівень вона уже потрапити не може, і
перехід а більше ніколи не спрацює. В той же час перехід b є живим.

Поняття живості має дуже важливу роль в різного роду додатках. Дійсно ми
вже говорили, що мережі Петрі використовують в основному для моделювання
операційних систем (ОС) і відповідних керуючих відповідним апаратних
блоків. Із яких би модулів така система не складалася, по її характеру
не повинно бути так, що до якогось із з якогось моменту не буде
звертань. Потік оброблюваних завдань достатньо однорідний , і кожен
модуль ОС, якщо тільки він не виконує допоміжну роль, наприклад
завантажувальної функції, або він не відключається на профілактику або
ремонт, повинен на ньому більш-менш рівномірно задіяний. „Відмирання”
якоїсь частини системи свідчить, що вона не є правильною. Правильність
функціонування в цьому смислі і відображає поняття живості.

рис. 13. Приклад живості переходу b, та не живості а

, тобто в цьому місці при любому ході обчислення не може бути більше
фішок ніж k. Місце називається просто обмеженим, якщо воно k-обмежене
для деякого k. Мережа N k-обмежена, якщо всі її місця k-обмежені. В
якості прикладів обмежених мереж можна привести мережу яку зображено на
рис. 12. вона обмежена при к=1. Приклад необмеженої дає рис. 14. в місці
р2 може накопичитися довільна кількість фішок. Неформально властивість
обмеженості виражає властивість „не накопичувати черги„ необмеженої
довжини.

Зазвичай при керуванні мережею Петрі дії зображаються переходами, тобто
мова L(N) являється множиною всіх процесів, які генеруються мережею N.
Природним чином вводяться наступні означення еквівалентності мереж
Петрі. Мережа N еквівалентна мережі N(, якщо L(N)=L(N(). Таким чином
мережі називаються еквівалентними якщо породжують одну і ту ж множину
процесів, тобто неформально системи які вони моделюють виконують одну і
ту ж роботу. Наприклад, мережа, яка зображена на

рис. 15, а, еквівалентна мережі, яка зображена на рис. 15, б. Із
порівняння цих двох мереж видно, що відношення еквівалентності могло б
використовуватися як інваріант при спрощуючи перетвореннях мереж: перша
мережа має на одне місце та дві стрілки менше ніж друга, з цього
випливає, що вона краща.

рис. 14. Необмежена мережа Петрі

І так нами введено різні властивості мереж, які відображають ту чи іншу
практичну сторону системи яку ми модулюємо. Любий формалізм оцінюється
серед всього іншого і по тому, на скільки багато отримано в ньому
позитивних результатів.

2.3 ПРОБЛЕМИ РОЗВ’ЯЗНОСТІ МЕРЕЖ ПЕТРІ

Спираючись на введені означення, можна сформулювати наступні проблеми
розв’язності для мереж Петрі:

Проблема досяжності (тупикової) розмітки.

Проблема досяжності переходу.

Проблема життєвості.

Проблема еквівалентність.

Проблема рівності R(N)=R(N().

Проблема k-обмеженості.

Проблема обмеженості.

рис. 15. Приклад двох еквівалентних мереж

Ці проблеми мають різну важкість, вони взаємо зв’язні. Наприклад,
розв’язок 1-го автоматично дає розв’язок 2 та 3-го. Але нажаль, для
всього класу мереж на сьогоднішній день відомо розв’язок лише двох
останніх, досить простих, проблем. Решта проблем залишаються відкритими
або доведена їх нерозв’язність. Більш точно доведено нерозв’язність
проблем 4 та 5. що до перших трьох, то доведено їх рівносильність і
розв’язність для класу мереж, які мають не більше 5-ти місць.

Проблеми 6 та 7 розв’язуються з допомогою техніки, яка розвинена в
формалізмі так званих систем векторного складення. Введемо для цих цілей
необхідні означення.

, такі, що М?Мі.

Перше питання яке можна задати відносно d(N) – це в яких випадках воно
скінчене. На це питання є наступний результат.

Лема 6.1

Дерево d(N) скінчене тоді і тільки тоді, коли нема досяжної розмітки М
та не порожньої послідовності переходів (, таких, що М?М. Таким чином,
якщо мережа допускає цикл по переходам, то дерево d(N) буде рости до
безкінечності.

Нетривіальні мережі Петрі зазвичай мають цикли, оскільки вони і створені
для моделювання деяких нескінченних процесів, тому, якщо ми хочемо
працювати з d(N), потрібно шукати способи його кінцевого представлення.

Теорема 6.1

Процес побудови графа g(N) досяжних розміток обривається, і в
побудованому графі нема вершини-стану з компонентою, яка перевищує k
тоді і тільки тоді, коли мережа N k-обмежена.

, де n – число місць.

Теорема 6.1 дає простий спосіб перевірки властивості k-обмеженості. Але
тільки для фіксованого k. При невідомому k, тобто при перевірці
обмеженості мережі, невідомо, коли обірветься ріст графа g(N). Тому
введеними засобами ми можемо отримати лише рекурсивне перерахування, але
не розв’язок проблеми. Для отримання розв’язку необхідно модифікувати
означення графа допустимих розміток.

Означення 26 (-деревом деревом допустимих розміток назвемо дерево, яке
будується за наступними правилами:

Починається побудова з початкової розмітки М0.

Якщо побудована частина (-дерева та М – деяка його вершина, тоді: а) в
випадку існування розмітки М(=М, яка знаходиться на деякому шляху із М0
в М, то М оголошується кінцевою вершиною;

.

Теорема 6.2

Мережа N обмежена тоді і тільки тоді, коли (-дерево не містить символа (
ні в одній із позицій і ні в одній із вершин.

2.4 РОЗШИРЕНІ МЕРЕЖІ ПЕТРІ

Прості мережі Петрі, що були тут представлені, повністю забезпечують
цілий ряд різноманітних застосувань. Проте за допомогою трьох простих
розширень вони стають суттєво продуктивнішими. Як показано Хопкрофтом і
Ульманом, «розширені мережі Петрі (навіть без додатково введених нижче
вагі дуг) Зі, своєю ефективністю дорівнюють машині Тьюрінга [16], тобто
вони можуть застосовуватисі як загальна модель обчислюваності.

Розширення. 1. Багаторазове маркування

відповідає

4

Кожен вузол може мати будь-яку кількість маркувань (при зображенні
мережі Петрі допускається маркування коротко позначати числом). Правила
активізації та перемикань змінюються відповідно:

• перехід активізований тільки тоді, коли число, що відповідає кількості
маркувань кожного його вхідного вузла, є більшим за одиницю або дорівнює
їй;

• якщо активізований перехід перемикається, то числа-маркування усіх
вхідних вузлів цього переходу зменшуються на одиницю, а усіх вихідних
вузлів — збільшуються на одиницю.

За цим способом кількість маркувань одного вузла може бути як завгодно
великою, але відповідне число не може бути меншим від нуля.

2. Дуги-заперечення

Дуги-заперечення в мережах Петрі зображаються кружечком на кінці замість
стрілки (рис.16) і не мають дугової ваги; дуги, що були визначені
раніше, розглядаються як позитивні дуги.

рис. 16. Дуга-заперечення

Вони завжди можуть бути направлені тільки від деякого вузла до деякого
переходу, зворотного напрямку не дозволяється. Введення дуг-заперечень
зумовлює оновлені пристосування правил активізації та перемикань:

• перехід активізований тільки тоді, коли кількість маркувань кожного
вхідного вузла з позитивною дугою більша або дорівнює одиниці і коли
кількість маркувань кожного вхідного вузла з дугою-запереченням дорівнює
нулю (на рис. 16 перехід t активізований, якщо Р1 маркований і Р2 не
маркований);

• якщо активізований перехід перемикається, то кількість маркувань усіх
вхідних вузлів з позитивними дугами цього переходу зменшується на
одиницю, в той час як кількість маркувань вхідних вузлів з
дугами-запереченнями залишається незмінною. Числа, що відповідають
кількості маркувань усіх вихідних вузлів, як і раніше, збільшуються на
одиницю.

3. Вага дуг

Кожна дуга, що не є дугою-запереченням, може мати постійну цілочислову
вагу, що більша або дорівнює одиниці (число, що використовується по
замовчуванні, рис. 17). Для активізації і перемикання переходу як
правило:

• перехід активізований тоді і тільки тоді, коли кількісні маркувань
кожного його вхідного вузла більший або дорівнкх відповідній вазі дуги,
а для дуги заперечення дорівнює нулю,

рис. 17. Вартості дуг

• при перемиканні переходу кількість маркувань кожного вхідного вузла
зменшується на вазі відповідної вхідної дуги (вона залишається незмінною
для дуг-заперечень); кількість маркувань кожного вихідного вузла
збільшується на вагу відповідної вихідної дуги.

Розділ 3

3.1. ПЕРЕВІРКА МЕРЕЖІ ПЕТРІ НА ІСНУВАННЯ ТУПИКОВОЇ РОЗМІТКИ (ДЕДЛОКУ)

В зв’язку з виникненням проблем з використанням мереж Петрі потрібно
розробляти мережу таким чином, щоб в ній були відсутні різного роду
проблеми, наприклад проблема пере накопичення фішок в якомусь місці, або
виникнення такого явища як дедлок. Саме для цього була розроблена
програма яка перевіряє класичну мережу Петрі з заданою початковою
розміткою на існування дедлок. Працює вона наступним чином: задається
мережа, кількість місць, переходів, множина стрілок які йдуть від місць
до переходів та від переходів до місць, потім програма перебирає всі
можливі варіанти спрацювання переходів для отримання нової розмітки,
якщо жоден перехід не може більше спрацювати в нас отрималась розмітка
яка є тупиковою.

В нашому випадку розглянемо наступну мережу

рис 18. Приклад мережі Петрі

Ми маємо мережу Петрі з трьома вершинами, чотирма переходами, чотирма
стрілками які ведуть від вершин до переходів та чотирма стрілками, що
ведуть від переходів до вершин, тобто множини:

P {p1, p2, p3};

T {a, b, c, d,};

Чотири стрілки множини F;

Чотири стрілки множини H;

Та початкова розмітка, яку позначають вектором М0(1, 0, 3).

Для початку перевірки потрібно, задати ці множини в програму, в
відповідні поля які підписані і натиснути кнопку «Перевірити», для того
щоб програма візуально відображала роботу заданої мережі в процесі її
дослідження на існування тупікової розмітки, потрібно поставити галочку
напроти напису «візуальне представлення».

Після натиснення на кнопку «Перевірити» програма збирає дані з
відповідних полів і заносить їх значення в відповідні масиви:

type T=record

name:string[4];

num:integer;

end;

Даний тип використовується для створення масивів стрілок множин F та H.
В програмі вводяться обмеження на довжину назв як вершин так і
переходів, максимальна довжина 4 символи, цієї довжини достатньо. Поле
name використовується для зберігання назви переходу або вершини, а поле
num це співставлення даній вершині певного числового еквіваленту.
Програма працює саме з числами і через них відбувається зворотній
зв’язок з назвами вершин чи переходів якщо це необхідно.

M0=array[1..5]of integer;

Даний тип використовується для зберігання початкової розмітки.

F=array[1..20,1..2]of integer;

H=array[1..20,1..2]of integer;

Ці типи використовуються для роботи з вже числовими еквівалентами множин
F та Н.

var bol:boolean;

VCX: array [1..5] of integer;

VCY: array [1..5] of integer;

PCX: array [1..8] of integer;

PCY: array [1..8] of integer;

l1,l2,oldbkMode:integer;

rozmitka:M0;

Змінна використовується для роботи з початковою розміткою.

strDoPer:F;

strVidPer:H;

Ці змінні використовуються для роботи з стрілками.

mis:array[1..10]of T;

per:array[1..20]of T;

В цих змінних зберігаються назви вершин та переходів та їхні числові
еквіваленти.

s:string;

i:=1;

while form1.StringGrid4.Cells[i,1]<>» do

begin

if form1.StringGrid4.Cells[i,1]=» then exit;

mis[i].name:=form1.StringGrid4.Cells[i,1];

mis[i].num:=i;

kilk:=i;

inc(i)

end;

Даний фрагмент програми зберігає введену користувачем назву вершини та
співставляє йому унікальне число в нашому випадку це лічильник який
постійно змінюється на одиницю і не може повторюватись.

i:=1;

while form1.StringGrid5.Cells[i,1]<>» do

begin

if form1.StringGrid5.Cells[i,1]=» then exit;

per[i].name:=form1.StringGrid5.Cells[i,1];

per[i].num:=i;

kl:=i;

inc(i)

end;

Тут виконується те ж саме але вже для множини переходів.

for i:=1 to kilk do

rozmitka[i]:=strtoint(form1.StringGrid1.Cells[i,1]);

В даному фрагменті програми створюється множина початкової розмітки.

i:=1;

while form1.StringGrid2.Cells[i,1]<>» do

begin

if form1.StringGrid2.Cells[i,1]=» then exit;

for j:=1 to kilk do

begin

if form1.StringGrid2.Cells[i,1]=mis[j].name then

strdoper[i,1]:=mis[j].num;

end;

for j:=1 to kl do

begin

if form1.StringGrid2.Cells[i,2]=per[j].name then

strdoper[i,2]:=per[j].num;

end;

l1:=i;

inc(i)

end;

Наведений вище цикл виконує досить просту задачу, він створює
двовимірний масив в якому зберігається інформація про множину F. В
нашому випадку введений масив (зліва) перетворюється в еквівалентний але
з числовим представленням (з права).

P1 P2 P2 P3

a b c d

1 2 2 3

1 2 3 4

Реально програма працює саме з «правим масивом» оскільки комп’ютер
швидше справляється з операціями над числами, то доцільніше
використовувати не постійне символьне порівняння а числове, тобто
порівняння чисел.

while form1.StringGrid3.Cells[i,1]<>» do

begin

if form1.StringGrid3.Cells[i,1]=» then exit;

for j:=1 to kl do

begin

if form1.StringGrid3.Cells[i,1]=per[j].name then

strvidper[i,1]:=per[j].num;

end;

for j:=1 to kilk do

begin

if form1.StringGrid3.Cells[i,2]=mis[j].name then

strvidper[i,2]:=mis[j].num;

end;

l2:=i;

inc(i)

end;

Аналогічно створюється і масив Н, стрілок які ведуть від переходів до
місць.

procedure main(var bool:boolean);

var n,no,j:integer;

b:boolean;

str:string;

Begin

no:=1;

n:=0;j:=0;

str:=»;

while str<>‘deadlock’ do

begin

if n=10000 then begin bool:=true; form1.Memo1.lines.add(Дана мережа
не має DEADLOCK’); exit; end;

if no=0 then no:=1;

vukper(no,b,l1,l2,ver);

if not(b) then

if no<>kl then

no:=no+1

else no:=1;

j:=j+1;

if b then j:=0;

if j=kl then str:=’deadlock’;

if j=0 then n:=n+1;

end;

Дана процедура є самою основною в якій і перевіряється мережа на
наявність тупикової розмітки. В цій процедурі використовується ще одна
процедура, vukper яка перевіряє перехід на його спроможність спрацювати
і саме в ній змінюється розмітка. В ній перебираються всі переходи по
черзі і перевіряється кожен з них на робото здатність, тобто чи може
перехід спрацювати. Якщо процедура vukper повертає параметр b типу
Boolean рівний true це означає, що перехід може спрацювати і ми
лічильник j збиваємо на 0 ,якщо b рівний false то перехід з номером no
спрацювати не зміг і наш лічильник j збільшується на 1. Як тільки
довільний перехід зможе спрацювати то лічильник j збивається на 0.
Працює процедура main до тих пір поки о не стане рівним значенню
кількості переходів, тобто коли ми переберемо всі переходи і жоден з них
не зможе спрацювати, тоді і виникає в тупикова розмітка.

Розглянемо фрагменти процедури vukper.

procedure vukper(no:integer; var bl:boolean; l1:integer; l2:integer;
ver:integer);

Ми маємо параметри цієї процедури такі як:

no – номер переходу який ми перевіряємо;

bl – параметр типу Boolean який повертає значення true якщо перехід
спрацював, та false якщо це не можливо;

l1 – параметр який передає в процедуру кількість стрілок які ведуть від
вершин до переходів;

l2 – параметр який передає в процедуру кількість стрілок які ведуть від
переходів до вершин;

ver – кількість вершин в нашій мережі.

for i:=1 to l1 do

begin

if strdoper[i,2]=no then

begin

mas[j]:=strdoper[i,1];

j:=j+1;

end;

end;

Формується масив в якому зберігається всі вершини з яких стрілки
прямують до переходів.

klm:=j-1;

for i:=1 to klm do

if rozmitka[mas[i]]>0 then b:=true else begin b:=false; exit; end;

Цей фрагмент перевіряє чи у всіх вхідних вершинах є хоча б одна фішка,
тобто чи може спрацювати цей перехід.

if b then

begin

for i:=1 to l2 do

if strvidper[i,1]=no then begin

mas2[j]:=strvidper[i,2];

j:=j+1;

end;

klm2:=j-1;

for i:=1 to kilk do

for j:=1 to klm do

begin

form1.Memo2.Lines.add(s);

if i=mas[j] then begin

rozmitka[i]:=rozmitka[i]-1;

s:=inttostr(i)+’перехід спрацював;

end;

Тут якщо всі вхідні вершини мають принаймні одну фішку то ми з всіх
вхідних вершин забираємо по одній фішці. І перед цим створюється масив
mas2 в кому зберігаються всі вихідні вершини в які потім буде добавлено
по фішці як ми це можемо спостерігати в фрагменті програмного

коду наведеного нижче.

for i:=1 to kilk do

for j:=1 to klm2 do

begin

if i=mas2[j] then begin

rozmitka[i]:=rozmitka[i]+1;

else begin

s:=»;

s:=inttostr(i)+’не може спрацювати’;

form1.Memo2.Lines.Add(s);

bl:=false

end;

В інакшому випадку, як видно вище, нічого не відбувається і параметру bl
присвоюється значення false яке повертається в процедуру main.

3.2. КОРИСТУВАННЯ ПРОГРАМОЮ

Розроблено якомога простіший користувацький інтерфейс програми. Всі поля
підписані і вказано в якій послідовності потрібно вводити дані в
програму. Для того щоб було простіше користуватися програмою потрібно
попередньо ознайомитися з теорією класичних мереж Петрі, а потім вже
користуватися програмою.

Після запуску програми (:\meregi.exe) перед очима з’являється
вікно програми рис. 19 на якому розміщено 5 полів які необхідно по черзі
заповнити.

рис 19. Вікно програми з порожніми полями

Перед тим як вводити всі дані необхідно перевірити щоб розкладка на
клавіатурі була виставлена на англійську мову, і вводити всі дані або
латинськими літерами або цифрами, не використовуючи спеціальних
символів.

Спочатку потрібно ввести множину вершин, це робиться наступним чином:
встановлюємо курсор в полі над яким є напис «Введіть множину вершин» і
по черзі вводимо назви вершин, після введення кожної назви встановлюємо
курсор в наступну комірку яка знаходиться поруч не допускаючи порожніх
комірок між назвами вершин як це показано на рис 20. Переходам можна
присвоювати різні назви але назва не повинна перевищувати чотирьох
символів.

рис 20. Задання вершин мережі Петрі

Потім за цим ми повинні ввести множину переходів. Для цього нам
необхідно встановити курсор на полі над яким є напис «Ведіть множину
переходів» і аналогічно до задання вершин по черзі вводячи назви
переходів які в нас є в мережі Петрі, не допускаючи порожніх комірок між
назвами переходів як це вказано на рис. 21. Не бажано допускати
співпадання назв вершин та переходів, для більш наглядного задання
мережі та аналізу роботи мережі.

Наступним кроком є внесення початкової розмітки. Для цього потрібно
просто встановивши курсор в полі «Початкова розмітка» після чого
з’являться назви вершин, під якими будуть порожні клітинки і саме в них,
відповідно до назв вершин, потрібно ввести кількість фішок скільки
потрібно, якщо жодної фішки немає в якійсь вершині потрібно вказати 0,
як це показано на рис. 22.

рис. 21. Задання переходів мережі Петрі

рис. 22. Введення початкової розмітки

Після цього нам необхідно ввести множини F та Н. Для цього встановлюємо
спочатку курсор в полі над яким вказано літеру F та вводимо всю множину
стрілок які ведуть від вершин до переходів а потім встановлюємо курсор в
полі над яким вказано літеру Н і аналогічно вводимо всю множину Н тобто
множину стрілок які ведуть від переходів до вершин. Вводяться вони
наступним чином:

при внесені множини F в верхньому рядку ми вказуємо назву вершини з якої
виходить стрілка, а під нею назву переходу в який входить ця стрілка і
таким чином дуже уважно, нічого не пропустивши вводимо всі стрілки
множини F як це вказано на рис. 23;

при внесені множини Н аналогічно до внесення множини F уважно вводимо
всі стрілки і також не допускаючи порожніх комірок між назвами вершин чи
переходів, але тепер в верхньому рядку ми вказуємо назву переходу з
якого виходить стрілка, а під нею назву вершини в яку входить ця стрілка
як це вказано на рис. 24.

рис. 23. Внесення множини F.

рис. 24. Внесення множини Н.

Після цього всі необхідні данні внесено, і можна починати перевірку
нашої заданої мережі Петрі на існування тупикової розмітки. Для цього
потрібно натиснути кнопку з написом «Перевірити» рис. 25. Після чого нам
знадобиться зачекати деякий час і ми зможемо побачимо результат рис. 26,
який може бути або «Виник дедлок» або «Дана мережа не має дедлоку». Це і
є результат роботи програми. Якщо ви задали неправильну назву переходу,
вершини або забули вказати якусь вершину, перехід, тобто виникли певні
проблеми з заданими даними, які не підлягають правилам задання мережі
Петрі програма повідомить вас і ви зможете виправити свою помилку. Тому
будьте уважними при внесенні данних.

рис. 25. Запуск програми на перевірку

рис. 26. Результат роботи програми

В програмі є можливість візуального представлення роботи мережі Петрі,
для цього необхідно перед натисненням на кнопку «Перевірити» поставити
галочку біля напису «Візуальне представлення», а вже потім натиснути
«Перевірити» і в нас з’явиться нове вікно на якому і буде зображена
задана мережа Петрі і візуально представлена її робота рис. 27. Але при
цьому перевірка буде продовжуватися досить тривалий час, щоб його
прискорити потрібно натиснути на кнопку «Закрити» яка знаходиться в
лівому верхньому кутку, після цього візуальне представлення зникне і ми
повернемося до робочого вікна програми, після цього необхідно зняти
галочку з «Візуальне представлення» і процес прискориться.

рис. 27. Візуальне представлення роботи мережі Петрі

Після перевірки мережі Петрі на існування тупикової розмітки можна
продивитися весь хід роботи нашої мережі натиснувши на кнопку
«інформація» рис 28. Там можна побачити спочатку початкову розмітку,
потім назви всіх переходів які спрацювали або не змогли спрацювати і в
самому кінці кінцеву розмітку.

рис. 28. Інформація про роботу мережі Петрі

Для того щоб прибрати поле інформації потрібно натиснути на кнопку
«Сховати інформацію» яка знаходиться біля кнопки «Інформація». В
програмі є можливість «на льоту» змінювати початкову розмітку, кількість
та назви вершин та переходів, але з ними потрібно бути дуже уважними.

По всім питанням та пропозиціям прохання писати листи за адресою
HYPERLINK «mailto:skomisaruk@mail.ru» skomisaruk@mail.ru .

ВИСНОВКИ

Паралельне програмування набуває все більшого поширення і розвитку в
світі з появою потужних супер ЕОМ та комп’ютерних комплексів які
складаються з кількох комп’ютерів які об’єднані в мережу.

З цих передумов виникає проблема моделювання розподілених обчислень. При
використанні мереж Петрі для моделювання виникають ряд проблем, однією з
яких і є виникнення тупикової розмітки (deadlock). Після виникнення
проблемі відразу йде і пошук вирішення даної проблеми.

В роботі досліджено роботу класичних мереж Петрі, умови виникнення
різних проблем, однією з яких і є виникнення тупикової розмітки.

Для досягнення мети в роботі вирішено такі задачі:

досліджено і охарактеризовано роботу мереж Петрі;

розроблено програму яка перевіряє мережу Петрі на існування тупикової
розмітки;

ЛІТЕРАТУРА

Алгоритмы, математическое обеспечение и архитектура многопроцессорных
вычислительных систем / Под. Ред. В.Е. Котова, И. Маклошко.-М.:Наука,
1982.-212 c.

Анишев А.П., Ачасова С.М., Бандман О.Л. и др. Методы параллельного
микропрограммирования.-Новосибирск: Наука, 1981.-181с.

Буда А.О., Иткин В.Э., Термальная эквивалентностьсхем-програм.-В
кн.:Системное и теоритическое программирование. Новосибирск: ВЦ СО АН
СССР, 974, с. 152-203

Вальковский В.А. Об одном алгоритме десеквенции.-Кибернетика, 1974, №2,
с. 77-88

Вальковский В.А. О неразрешимости максимального распараллеливания.-там
же, 1976, №5, с. 140-148

Вальковский В.А. О вычислениях с упрежденинм.-Кибернетика, 1979, №6, с.
38-45

Вальковский В.А., Котов В.Е., Марчук А.Г., Элементы параллельного
программирования.-Радио и связь, 1983, с. 28-36

Котов В.Е. Теория параллельного программирования: Прикл.
Аспекты.-Кибернетика, 1974, №1, с. 1-16

Котов В.Е. Теория параллельного программирования: Прикл.
Аспекты.-Кибернетика, 1974, №2, с. 1-18

Тиришина Е.В. Разрешимость функциональной эквивалентности на подклассе
схем потоков данных.-Новосибирск: ВЦ СО АН СССР, 1982.-43с.

Корнеев В.В. Параллельные вычислительные системы.-М. Нолидж, 1999г.

Архитектура много процессорных вычислительных систем: Учебное пособие /
Козлов О.С., Метлицкий В.А., Экало В.А. и др.; Под редакцией
В.И.Тимохина:-Л.: — издательство Ленингр. ун-та, 1981 г.

Воеводин В.В. Математические основы параллельных вычислений. – М.: МГУ,
1991г.

Мультипроцессорные системы и параллельные вычисления / Под ред. Ф.Г.
Энслоу. – М.: Мир, 1976. – 384 с.

Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. – СПб.:
БХВ-Петербург, 2002. – 608 с.: ил.

Воеводин Вл.В. Теория и практика исследования параллелизма
последовательных программ // Программирование.- 1992.-№3.-с.38-53

Элементы параллельного программирования / Вальковский В.А., Котов В.Е.,
Марчук А.Г., Мироненко Н.Н.; Под ред. В.Е. Котова. – М.: Радио и связь,
1983.

ДОДАТОК

Лістіг програми яка перевіряє класичну мережу Петрі на існування
deadlock (тупикової розмітки) в заданій користувачем мережі Петрі
знаходиться на компакт диску, який додається і знаходиться на останній
сторінці в конверті який прикріплено до задньої титульної сторінки.
Програма написана на мові програмування Delphi 7.0.

PAGE

PAGE 59

введення

(x, y)

x:=sin(x)

y:=y(2

вивід

(. . . . .)

y=x/y

вивід

(y)

y=0?

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *