Лабораторна робота 4 Вивчення способів аналізу мп-моделей

Мета роботи. Вивчення матричних способів подання мереж Петрі (МП) і методів дослідження МП-моделей на основі матричних рівнянь і дерева досяжних розміток (ДДР).

Постановка завдання. Мережа Петрі це двочастковий, орієнтований мультиграф N = (Р, Т, F, Н, ₀), де Р - кінцева непорожня множина елементів, званих позиціями; Т - кінцева непорожня множина елементів, званих переходами; F:Р×T→{0,1,2,...} і H:T×Р→{0,1,2,...} – функції інцидентності; ₀:Р→{0,1,2,...} – початкова розмітка.

МП зазвичай представляють у вигляді геометричного об'єкта. При цьому позиції зображуються кружечками, переходи – рисками або прямокутниками. Дуга проводиться від позиції р_i до переходу t_j в тому випадку, якщо F(p_i, t_j) ≥1, а від переходу t_j до позиції р_i якщо H (t_j, p_i) ≥1.

Якщо F(p_i, t_j) ≥1, то позицію р_i називають вхідною до переходу t_j, а перехід t_j вихідним до позиції p_i. Множина вхідних позицій до переходу t_j визначається виразом

pre(t_j) = {p:F(p, t_j)≥1},

а множина вихідних переходів до позиції р_i виразом

post(p_i) = {t: F(p_i, t) ≥1}.

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

При функціонуванні МП переходить від однієї розмітки до іншої. Перехід t може спрацювати при розмітці , якщо

p pre(t):(p)-F(p,t) ≥0,

де (p) кількість міток у позиції р.

У результаті спрацьовування переходу t нова розмітка ' виникає у відповідності з наступним правилом:

p (pre(t) post(t)): '(p)= (p)-F(p,t)+H(t,p).

У цьому випадку говорять, що розмітка ' досяжна з розмітки , а  передує '. Даний факт позначається наступним чином: →^t' .

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

Якщо розмітка ' досяжна з розмітки  в результаті спрацьовування послідовності переходів r=t₁, t₂ ,..., t_k, де: r - слово з множини Т* всіх слів в алфавіті Т, то це позначається як →^t1'''→^t2... →''→ ^tk ' або →^r'.

Розмітка  досяжна в мережі N, якщо ₀→. Множину всіх досяжних розміток в мережі N позначимо через R(N).

Перехід t досяжний від розмітки  (→t) в мережі N, якщо:

 ' ''({ ',  ''}R(N)& - '):  '→ ^T ''.

Перехід t досяжний в мережі N, якщо ₀→t. В галузі моделювання систем проблема досяжності розмітки інтерпретується як можливість досягнення певного стану системи.

Перехід t живий, якщо:

R(N): →t.

МП жива, якщо:

t (tT&R(N)):  (p) →t.

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

R(N):  (p)≤K.

МП обмежена, якщо:

p (рp&r(n)):  (p) ≤K.

Якщо К=1, то МП називається безпечною.

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

Дерево досяжних розміток представляє собою орієнтований граф, множина вершин якого утворена множиною R(N), причому з вершини  у вершину ' веде дуга, позначена символом переходу t, якщо і тільки якщо →^t'. У загальному випадку дерево досяжних розміток може мати нескінченне число вершин. Для перетворення дерева в корисний інструмент аналізу опишемо алгоритм побудови кінцевого дерева досяжності.

Кожна i-та вершина дерева зв'язується з розширеною розміткою (i). У розширеній розмітці число міток у позиції може бути або позитивним цілим, нескінченно великим. Нескінченне число міток позначимо символом . Кожна вершина класифікується або як гранична, термінальна, дублююча вершина, або як внутрішня. Граничними є вершини, які ще не оброблені алгоритмом. Після обробки граничні вершини стають або термінальними, або дублюючими, або внутрішніми.

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

Нехай x - гранична вершина, яку необхідно обробити, і з якою пов'язана розмітка (X).

1. Якщо в дереві є інша вершина y, що не є граничною, і з нею пов'язана розмітка (y)=(x), то вершина x дублюється.

2. Якщо для розмітки (x) ни один з переходів не є дозволений, тобто (x) тупикова розмітка, то x термінальна вершина.

3. Для будь-якого переходу t_j, з множини T дозволеного в розмітці (x), створити нову вершину z дерева досяжності. Розмітка (z), пов'язана з цією вершиною, визначається для кожної позиції р_i наступним чином:

а) якщо  (x)i=, то  (z) i =;

б) якщо на шляху від кореневої вершини до x існує вершина y така, що  (y) →^tj (x),  (y)<  (x) и  (y)i< (x)i, то  (z)i=;

в) у противному випадку  (z)i= (x)i.

Дуга, позначена t_j, спрямована від вершини х до вершини z. Вершина x перевизначається як внутрішня, вершина z стає граничною. Коли всі вершини дерева стають термінальними, дублюючими або внутрішніми, алгоритм зупиняється.

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

Введемо в розгляд матрицю С, котра отримується наступним чином:

C = H^T-F,

де H^T - транспонована матриця H.

Нехай розмірність С дорівнює n×m, де m і n - потужності множин Р і Т.

Розглянемо матричні рівняння:

×C=0, (4.1)

C× =0, (4.2)

де і - вектори, розмірність яких дорівнює n і m відповідно.

Вектор , який задовольняє рішенням рівняння (4.1), всі елементи якого позитивні, називається р-ланцюгом; р-ланцюг, всі елементи якого більше нуля, називається повним р-ланцюгом.

Аналогічно на основі рівняння (4.2) визначаються поняття t-ланцюга та повного t-ланцюга.

МП, для якої існує повний р-ланцюг, називається інваріантною. МП, для якої існує повний t-ланцюг, називається послідовною.

Порядок виконання роботи

1. Вибрати структуру МП у відповідності з номером варіанту.

2. Описати задану МП-модель з допомогою матриць F, H, ₀.

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

4. Провести дослідження МП-моделі шляхом побудови дерева досяжних розміток (ДДР) власноруч і з використанням програмного комплексу. Порівняти отримані результати.

5. На основі проведених досліджень оцінити коректність МП-моделі і запропонувати варіанти усунення недоліків у разі їх виявлення. Припустимо додавати нові елементи і обмежено видозмінювати топологію мережі. Отримана модель повинна відповідати вимогам жвавості і безпеки.

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

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

Контрольні питання

1. Що таке МП і з допомогою яких параметрів вона задається?

2. Що таке жвавість, безпека, обмеженість і досяжність МП?

3. Як інтерпретуються для модельованої НД жвавість, обмеженість і досяжність МП?

4. Як виглядає рівняння стану МП?

5. У чому полягають матричні методи дослідження МП-моделей?

6. Що таке повний р-ланцюг і повний t-ланцюг?

7. Що таке дерево досяжних розміток?

8. Які прийоми використані в алгоритмі побудови дерева досяжних розміток для обмеження дерева?

9. Які властивості МП досліджуються в процесі аналізу?