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

ВСТУП

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Розділ 1

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

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

І так нехай задана множина М={x, y, xi, . . .} комірок пам’яті або змінних, які можуть бути з індексом, та множина F={a, b, ai, . . .} символів операторів, які там, не призводять до двозначності, будемо для скорочення називати просто операторами. Для кожного оператора визначені упорядковані множини , вхідних і вихідних змінних. Символи і будуть позначати k-ту компоненту цих множин. Припускається, що виконується умова

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

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

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

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

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

Означення 2: обчислювальним процесом над інформаційним базисом (M, F) називається скінчена або нескінчена послідовність де є або , або для деякого оператора а. Початковий відрізок позначимо як і назвемо його префіксом процесу. При цьому припущені від вимагається :

1.Для любих k та a, якщо префікс містить п символів виключення оператора а, то він містить не менше ніж п операторів включення а. Ця аксіома виражає природну вимогу про те, що виключення оператора не може бути раніше його включення.2.Для любого а, якщо процес скінчений, він містить включення і виключення оператора а. Також природна вимога: після завершення „роботи” всі процеси які були включені повинні бути завершені.

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

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

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

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

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

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

Тоді процесами являються ; . Перший із них – послідовний (рис 1.), а другий паралельний (рис 2.).

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

Всі виконання оператора а можна впорядкувати в часі по моментам ввімкнення, і тому далі будемо говорити про перший другий і т.д. актах оператора а або входження їх в обчислювальний процес . На них переносяться визначення входів і виходів, тобто можна говорити про входи і виходи обчислювального процесу . Наприклад, процес  має два акта оператора b кожен із яких має входом х а виходами y, z. Перший акт реалізується між 4-им та 5-им тактом, а другий акт між 7-им та 8-им. Якщо аксіома відсутності авто паралельності 4, то вважається, що акти виключаються в порядку їх включення. Так процес має два акта оператора а: 1-й між 1-им та 5-им, 2-й між 3-ім та 7-им тактами.

Означення 4: Інформаційним графом процесу називається орієнтований граф (можливо нескінчений), з вершинами якого являються входи та виходи актів процесу , а стрілки проводяться в відповідності до наступних правил:

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

2.Якщо послідовність , і при цьому для деяких j, k Outj(a)=Ink(b) і між та нема ні одного акта виключення с, такого, що , то стрілка веде із Outj(a) в Ink(b). Інших стрілок нема.

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

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

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

Означення 6: Визначимо поняття терма над множиною .

1.Якщо , то х являється термом.

2.Нехай , - терми, має вигляд , при чому або . Тоді являється термом.

Множина всіх термів над позначимо через .

Означення 7: Терм –історією або скорочено t-історією входження і в , називається терм , рівний , якщо і=1, і= , де ; для відповідного символа включення а , якщо попередньо визначене. Цей терм називається також терм-історією відповідного акта оператора а; , якщо визначені, , при чому , де - останнє входження в перед , яке виробляють .

Далі будемо вважати, що операторна множина F, а також інформаційний базис належать до класу LL (loss – less) [13, 14], якщо . Таким чином кожне виконання акта в базисі класу LL спричиняє за собою зміну стану пам’яті. Ця властивість являється дуже важливою в теорії паралельного програмування, в чому ми ще не раз переконаємося. Має місце наступна фундаментальна лема про зв’язок різних атрибутів процесів.

Лема 1

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

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

Б. спричиняє, що , але супротивне не вірне.

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

Г. t-історії процесів  та  співпадають тоді і тільки тоді, коли .

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

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

. (1.1)

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

, .

Лема 1.2

Якщо процес отримується із процесу з допомогою кінцевого числа перестановок актів операторів, які задовольняють умові (1.1), то .

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

Означення 8: Будемо говорити, що процес  належить класу RF або володіє властивістю RF (repetition-free), якщо для довільного його відрізка виду між входженнями а є таке входження , де b може бути рівним а, що . Таким чином, кожне включення оператора відбувається на поновлених даних. Звідси, випливає, що довільний оператор без входів зустрічається не більше одного разу. Очевидна наступна лема.

Лема 1.3

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

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

Лема 1.4

А) ;

Б) .

Означення 9: Інтерпретацією І інформаційного базису (M,F) називається трійка , де  деяка множина , яке будимо називати далі множиною значень; 0 – відображення із М в , тобто деякий початковий стан пам’яті; - відображення, яке перетворює оператор ний символ а в перетворювач над пам’яттю. Під т розуміємо число входів, а під п число виходів оператора а.

Визначимо проміжковий стан пам’яті після виконання префікса деякого процесу . Якщо то ; а якщо і визначене, то

(1.2)

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

Означення 10: Інтерпретація І0 називається вільною, якщо , тобто множиною значень є множина термів; , тобто при початковому стані пам’яті в комірці х міститься терм х,

,

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

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

Лема 1.5

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

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

Теорема 1.1

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

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

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

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

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

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

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

визначається як п’ятірка , де Q – деяке, зазвичай скінчена, множина станів; q0 – початковий стан; Q - множина кінцевих станів;  - частинна функція переходів, . Якщо функція - визначена, то і для довільного j функція визначена. Як завжди робота автомата полягає в переході із одного стану в інший в відповідності з „вказівками” функції . Рух починається з початкового стану і закінчується в першому кінцевому стані який зустрінеться. По скінченим автоматам є великий вибір книг.

Всі моделі які розглядатимуться нижче можна представляти і порівнювати в рамках деякої мета моделі [9]. Загальним для них є те, що вони в сукупності з інформаційним базисом (M, F) вони породжують, генерують або визначають яким не будь іншим способом множину так називаємих допустимих процесів. Множина допустимих процесів, яка виникає в наслідок дії керуючого процесу U позначимо через Proc (U), множина префіксів цих процесів – через Pref (U). В тих випадках, коли структура керування зв’язана з інтерпретацією та множина породжуємих процесів при різних І різне, для нього вводиться позначення Proc (U, I). Множина Proc (U) та Proc (U, I) зв’язані природним співвідношенням: . Користуючись цими позначеннями вже можна сформулювати основні проблеми для структур керування.

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. Позначення , де – послідовність символів із , приймемо для факту існування шляху із q в q по стрілкам з символами ; а буде означати досяжність вершини q із вершини q по будь якому шляху; позначення прийнято для скорочення формули .

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

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

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

;

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

;

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

.

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

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

Теорема 2.1

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

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

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

Означення 12 Будемо говорити, що задана А-схема, якщо в доповнені до пам’яті M і множині F задані: – деяка множина змінних, яку називають керуюча пам’яттю; –множина предикатних символів, які називаються символами спускових функцій. З кожним зв’язано множину ; – множина символів управляючих функцій. З кожним зв’язані .

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

1.В початковий момент часу перевіряється значення всіх спускових функцій на початковому стані пам’яттю Y, M і можуть включитися ті оператори а для яких =1.

2.Любий включив шийся оператор а працює на протязі довільного проміжку часу і в момент включення змінює стан інформаційної пам’яті М в відповідності з інтерпретацією І. Після цього спрацьовує оператор керування на тому стані, яке отрималось після моменту включення оператора а. Його спрацювання займає нульове значення часу. Таким чином моменти включення а моменти включення і виключення співпадають, але потребується щоб для довільних двох актів операторів a, b не співпадали їх активні моменти. Ця умова дозволяє повністю впорядкувати всі оператори включень і виключень модулів і розглядати їх як процеси які визначені в пункті 1.

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

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

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

Лема 3.1

Якщо

(3.1)

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

Доведення: достатньо очевидно: в ситуації яку опису формула (3.1), префікс може бути продовжений двома способами та , при цьому, так як aта b конкурують над пам’яттю, зв’язки які будуть сформовані будуть різними, що потягне за собою різницю в інформаційних графах.

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

Лема 3.2

Якщо схеми S та S відрізняються лише спусковими функціями та і виконується умова , то 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].

Нехай задано інформаційний базис (M, F) в тій модифікації, в якій він був визначений в другому пункті, тобто, що кожному операторному символу а співставлений не один а ціла множина символів виключення а. Будемо говорити, що над базисом (M, F) задана операторна схема S, якщо заданий автомат так, як він був визначений в пункті другому. Приклад операторної схеми зображено на рис. 7. Для цієї схеми

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

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

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

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

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

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

Означення 15 Схема називається вільною (free), якщо для довільного шляху  існує інтерпретація І, така, що .

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

Будемо говорити, що схема S буде належати до класу RF, якщо для любої інтерпретації І любий процес володіє властивістю RF.

Лема 4.1

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

Не важко помітити, що в найбільш типових випадках істинне і обернене включення, а саме: якщо і схема вільна, то вона належить класу RF.

Теорема 4.1

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

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

Теорема 4.2

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

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

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

Означення 16 Обчислювальний процес  визначається як послідовність актів операторів , де акт це трійка . Тут , де - змінна х з індексом k; . Акт виражає ввімкнення оператора а, який спрацював на входах із комірок , який заслав результат обчислень в комірки і видавшого альтернативу . Моменти включення операторів в обчислювальному процесі не відображені.

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

Теорема 4.3

Існує алгоритм, який співставляє кожній детермінованій схемі S деякого класу Ф детерміновану не збиткову схему S еквівалентну S і максимально паралельну в класі тоді і тільки тоді коли функція Lah - ефективна. При цьому алгоритм розпаралелення визначається по функції Lah конструктивно.Із теореми 4.3 отримується ряд наслідків два із яких сформульовані нище.

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

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

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

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

Одна із перших моделей, яка неявно використовувала принцип потоку даних , - це модель Карпа та Міллера [13]. дещо пізніше Родрігес ввів поняття „програмних графів” [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 Якщо при розмітці М можливе спрацювання переходу t і після нього виникає нова розмітка М , то будемо говорити, що М слідує за М, і писати М├М.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Означення 25 Деревом досяжних розміток d(N) мережі N називається дерево в смислі теорії графів з поміченими дугами, в корні якого знаходиться розмітка М0, і з кожної вершини М виходять дуги в вершини-приймачі , такі, що М├Мі.

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

Лема 6.1

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

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

Теорема 6.1

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

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

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

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

2.Якщо побудована частина -дерева та М – деяка його вершина, тоді: а) в випадку існування розмітки М=М, яка знаходиться на деякому шляху із М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. В нашому випадку введений масив (зліва) перетворюється в еквівалентний але з числовим представленням (з права).

P1P2P2P3

abcd

1223

1234

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

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 полів які необхідно по черзі заповнити.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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