Стр. 7-16 Лекция 7. P/V системы. Автор: Котов Е.А.

P/V системы

P/V системы системы синхронизации

Семафор – целочисленная неотрицательная переменная.

P на 1 s=s+1 (если возможно)

V на 1 s=s+1

Синхронизация осуществляется через семафоры.

P, V опции – примитивны, т.е. никакая другая опция не работает одновременно с ними над семафором.

Число фишек = S

Задача:

Табак, бумага, спички – курил

Агент на каждом шаге выкладывает 2 наименьших.

Таким образом было сообщено, что механизмов P/V систем недостаточно.

Моделирование автоматической P/V системой

В начале каждого процесса выполняется P(s_i)этот процесс не будет запущен, пока s1. После выполнения P(s_i) процесс выбирает любой u для которого, определена f(x_i, u) – функция перехода и выполняет V(s_i). Потом возвращает по петле к P(s_i) все s=0, Кроме начального состояния s=1.

Система замещения векторов

Состоит из начального вектора s≥0 и m пар векторов (u_i, v_i). Причем, u_i≤v_i. u_i – вектора проверки.

1. sК

2. xК и x + u_i ≥ 0  x + v_i  К

Если позиция в петле u_i = v_i

нет u_i < v_i

проверка разрешения перехода отделяется от действия по его запуску.

Анализ механической системы увеличивается.

Моделирование – сети Петри.

Имеется несколько типов расшир. сетей Петри:

1. Введение областей ограничений множества позиций, которые могут быть одновременно маркированы.

2. Введение перехода «исключающее ИЛИ». Можно запирать т.т.т, когда фишка только в 1 входной позиции.

3. Введение понятия переключатели. При срабатывании перехода маркер перемещается в 1 из выходных позиций в зависимости от разметки переключателя.

4. Переходам ставиться в соответствие приоритет

5. Ингибиторные дуги. Проверка на 0 разметку позиций. Выполнение действий при невыполнении условия. Позволяет увеличить мощность метода до мощности Тюринга.

6. Раскрашенные сети. Каждая метка сети получает свой цвет; условия разрешения и срабатывания перехода для каждого цвета задаются независимо.

СP=(P, T, C, I, O)

C – множество красок, цветов маркеров

С = {c₁, c_2,…, c_l} = C(p)VC(t)

C(p) – цвет позиции

C(p) – переходы

I = I(p, t) : C(p) · C(t) → N

O = O(p, t) : C(p) · C(t) → N

Предполагают, что с(p_i) = {a₁ⁱ, a₂ⁱ,…}, с(t_i) = {b₁^j, b₂^j,…}

Разметка задается формой существующих цветов, ассоциированных с каждой позицией.

t_j в раскрашенной сети Петри разрешен по отношению к цвету b_k т.т.т., когда

Когда М₀ такова, что t_j разрешен по отношению к b_k^j? То новая разметка

Пример:

2 станка, каждый 2 задания.

p₁ – допустимые задания

p₂ – допустимые ресурсы

t₁ – начало исполнения задания

p₃ – исполнение

t₂ – конец исполнения

Еще один подход (нужный):

Вводится множество цветов маркеров С = {c_k}. p и t соединены с помощью помеченных дуг, метки – либо подмножества множества цветов, либо свободные переменные χ.

Правило срабатывания переходов:

• Если дуга p_it помечена множеством С_i≤С, то t срабатывает только, если p_i содержит по крайней мере по 1 маркеру каждого цвета из С_i. В результате срабатывания t из p_i будет удалено по 1 такому маркеру.

• Если tp_i помечена С_j, то срабатывание t передает в p_i по 1 маркеру каждого цвета из С_j.

• Если одна или несколько дуг помечены χ, то это χ может принять значение любого С, т.е. дуга меняет цвет маркера.

Расширение раскрытия сетей Петри:

1. Сети Петри со связанными переходами.

α : T → T·{<, =, >} (функция связи)

Правила разрешения перехода t_i, связанного с t_j, наряду с обычными требованиями к разметке входных позиций t_i добавляет требование разрешения t_j.

(t_i → t_j, ρ)

α(t_i) = (t_j ,<) сначала запускается t_j, а затем, если возможно t_i

α(t_i) = (t_j ,=) одновременно как 1 сложный переход, при этом если t_i и t_j имеют общую входную позицию, то

((С_i  С_j) = 0) & (С_i  {χ}  С_j  {χ})

α(t_i) = (t_j ,>) сначала t_i, а потом t_j

Запуск связанного перехода – 1 шаг работы сети.

1. Сети Петри с блуждающими дугами

При введении блуждающих дуг вводится понятие переключателя дуг Д и переключателя S.

s  S

s = (s_d, s_p) : s_d : d → p

s_p : (p) → p

p  P

d  Д – псевдопозиция, которая может входить во входящую или выходящую дугу перехода.

s_d(d) = p₁

p = s_p((s_d(d)))

Языки сетей Петри

L(C) – свободный язык сетей Петри

Если L(C) – связанный язык, то множество

L(C, ) = {() : α(C)} образует префиксный язык помеченной сети (C, )

Пусть ₀ – начальная разметка сети Петри, _f – фиксированный термин и пусть  - последовательность срабатывания переходов, которые переводят ₀^ → _f, то множество

L(C, _f) = {T* : ₀^ → _f } образует свободный терминальный язык, а множество

L(C, , _f) = {() : α(C, _f)} образует терминальный язык помеченной сети Петри.

L(C) = {(t₃, t₁, t₄, t₂)ⁿ}

L(C, ) = {T* : ₀^ → _f }

Пример:

Представление автомата сети Петри

A = (x, u, z, f, h, x₀, F)

C = (P, T, I, O)

P = U  X  Z

T = {tx, u : x  X, u  U, f(x, u)  X}

I(tx, u) = {x, u}

O(tx, u) = {f(x, u), h(x, u)}={X, Z}

В каждой позиции сети Петри соответствующий эдемент входного алфавита U, состояние, выходного алфавита.

Для любой пары (x, u) вводится переход,

вход – состояние, входящий символ

выход – состояние, выходящий символ,

Поэтому t имеет 2 или 1 входную (выходную) дугу.

|T| = |f|

Если A – инициальный с x₀, то начальная разметка сети Петри состоит в наличии маркера в первой позиции, соответствующей данному состоянию.

Существует (tz) = Z функция помечения, все остальные - -помечения (т.е. не мемеченные).

L^N = L^A

Пример:

Od – открыт

Cd – закрыт

A = (I, O, U, X, Z, f, h, x₀, F)

f : x · V → X V  U · I

h : x · V → W W  Z · 0

C = (P, T, I, O)

P = X  V  W

T = {tx, u : x  X, v  V, f(x, v)  X}

I(tx, u) = {x, v}

O(tx, u) = {f(x, u), h(x, u)}={X, Z}

|P| = |X| + |V| + |W|

|X| + |U| + |Z| ≤ |P| ≤ |X| + |U||I| + |O||Z|

Пример:

I = {1, 2}

O = {5, 6}

X = {x₁, x₂, x₃,}

x₀ = x₁

F = x₂

U = {a} V = {(a, 1), (a, 2)} = {v₁, v₂}

Z = {b} W = {(b, 5), (b, 6)} = {w₁, w₂}

3+2+2=7 позиций

f : (x₁, V₁) → x₂

(x₁, V₂) → x₃

(x₁, ) → x₁

h : (x₁, V₁) → W₁

(x₁, V₂) → W₂

(x₁, ) → W₃

_a = {_ai , _ai-1,…, _a , _a _a , _a}

_b = {_bi , _bi-1,…, _b , _b _b , _b }

Цветная сеть

Модели подсистем

1. Должна отображать все выполняемые действия

2. Должна отображать каждое состояние подсистемы

3. По возмущению обладать имитационными свойствами

Схват