Стр. 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(si)этот процесс не будет запущен, пока s1. После выполнения P(si) процесс выбирает любой u для которого, определена f(xi, u) – функция перехода и выполняет V(si). Потом возвращает по петле к P(si) все s=0, Кроме начального состояния s=1.

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

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

  1. sК

  2. xК и x + ui 0 x + vi К

Если позиция в петле ui = vi

нет ui < vi

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

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

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

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

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

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

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

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

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

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

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

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

С = {c1, c2,…, cl} = 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

Предполагают, что с(pi) = {a1i, a2i,…}, с(ti) = {b1j, b2j,…}

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

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

Когда М0 такова, что tj разрешен по отношению к bkj? То новая разметка

Пример:

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

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

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

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

p3 – исполнение

t2конец исполнения

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

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

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

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

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

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

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

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

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

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

(titj, ρ)

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

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

((Сi Сj) = 0) & (Сi {χ} Сj {χ})

α(ti) = (tj ,>) сначала ti, а потом tj

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

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

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

s S

s = (sd, sp) : sd : d → p

sp : (p) → p

p P

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

sd(d) = p1

p = sp((sd(d)))

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

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

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

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

Пусть 0 – начальная разметка сети Петри, f – фиксированный термин и пусть - последовательность срабатывания переходов, которые переводят 0f, то множество

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

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

L(C) = {(t3, t1, t4, t2)n}

L(C, ) = {T* : 0f }

Пример:

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

A = (x, u, z, f, h, x0, 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 – инициальный с x0, то начальная разметка сети Петри состоит в наличии маркера в первой позиции, соответствующей данному состоянию.

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

LN = LA

Пример:




Od – открыт

Cd – закрыт




A = (I, O, U, X, Z, f, h, x0, 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 = {x1, x2, x3,}

x0 = x1

F = x2

U = {a} V = {(a, 1), (a, 2)} = {v1, v2}

Z = {b} W = {(b, 5), (b, 6)} = {w1, w2}

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

f : (x1, V1) → x2

(x1, V2) → x3

(x1, ) → x1

h : (x1, V1) → W1

(x1, V2) → W2

(x1, ) → W3

a = {ai , ai-1,…, a , a a , a}

b = {bi , bi-1,…, b , b b , b }


Цветная сеть

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

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

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

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









Схват



Случайные файлы

Файл
128591.doc
24641-1.rtf
20484-1.rtf
17020.rtf
104279.rtf