2.3. Дедлоки

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

Приклад 2.6.

Розглянемо приклад на рис. 2.8,а. Мережа А визначає циклічне необмежене спрацювання переходів t₁, t₂, t₃. При спрацюванні переходи t₂ і t₃ споживають одиницю ресурсу з вузла р₃ кожен. Для визначеності можна собі уявити, що вузол р₃ містить дві ділянки пам'яті (буфери), які операційна система може динамічно виділяти програмі за її запитом. Поки процес, керований мережею А, виконується один, ситуації дедлока не виникає. Але якщо з'являється ідентичний процес, що виконується паралельно А і керується мережею В (рис.2.8,б), тоді виникає конкуренція за ресурс у вузлі р₃.

Рис.2.8. Мережа Петрі для прикладу 2.5.

Ситуація дедлока виникає при такій послідовності спрацювання переходів мережі: t₁, t₄, t₂, t₅. І в цьому стані маємо дедлок: жоден перехід не може спрацювати. Проте мережа нормально функціонуватиме, якщо у вузлі p_i залишити одну фішку, тобто дозволити виконуватися або процесу А, або процесу В, але не обидвом одночасно.

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

3. Лабораторне завдання

3.1. Дослідити властивості наступних мереж Петрі:

MPN =(P,T,I,O),

P={p₁, p₂, p₃, p₄}

T={t₁, t₂, t}

I(t₁)={ p₁}, O(t₁)={ p₂},

I(t₂)={ p₂, p₃}, O(t₂)={p₁ ,p₄},

I(t₃)={ p₄}, O(t₃)={p₃},

M₁ = (0, 1, 1, 0)

Властивості мереж Петрі

Обмеженість.

Наша мережа є обмеженою, тому що в нас тільки дві мітки.

Безпечність.

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

Зберігання.

Досліджувана мережа зберігається.

Досяжність маркування.

Досліджувана мережа є досяжною.

Активність.

Досліджувана мережа є живою.

Граф досяжності

Часткове дерево досяжності маркованої мережі Петрі

(0,1,1,0)

|T₂

(1,0,0,1)

Т₁/ \T₃

(0,1,0,1) (1,0,1,0)

Т₃| |Т₁

(0,1,1,0) (0,1,1,0)

Висновок

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