Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Стр. 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. По возмущению обладать имитационными свойствами

Схват

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций