Слайд 1Романенко Владимир Васильевич,
к.т.н., доцент каф. АСУ ТУСУР
Параллельные вычислительные процессы
Слайд 2Описание вычислительных процессов
Параллельные вычислительные процессы
Слайд 3Базовые определения
Имена процессов будем обозначать словами, составленными из прописных букв,
а буквами P, Q, R, … будем обозначать произвольные процессы.
Буквы
x, y, z, … используются для переменных, обозначающих события.
Буквы A, B, C, … используются для обозначения множества событий.
Буквы X, Y, Z, … используются для переменных, обозначающих процессы.
Алфавит процесса P обозначается αP.
Процесс с алфавитом αP, такой, что в нем не происходит ни одно событие из αP, назовем СТОПαP.
Слайд 4Базовые определения
Пример: автомат, торгующий шоколадками.
В качестве имени процесса выберем ТАП
(торговый аппарат простой).
Имена событий – мон (опускание монеты в щель
автомата) и шок (появление шоколадки из выдающего устройства).
Алфавит αТАП = {мон, шок}.
Слайд 5Префиксная запись
Префиксная форма описания процессов:
(x → P),
где
x – событие;
P –
процесс.
При этом
α(x → P) = αP, xαP.
Пример:
(мон → (шок →
(мон → (шок → СТОПαТАП)))).
Слайд 6Рекурсивная запись
Рекурсивный метод определения процесса:
P = (x → P),
P =
(x → (y → P)),
и т.д. Здесь x, yαP.
Пример 1:
ТАП
= (мон → (шок → ТАП)).
Слайд 7Рекурсивная запись
Рекурсивный метод определения процесса:
P = (x → P),
P =
(x → (y → P)),
и т.д. Здесь x, yαP.
Пример 2:
процесс ЧАСЫ описывает часы, единственная функция которых – тикать:
αЧАСЫ = {тик},
ЧАСЫ = (тик → ЧАСЫ).
Слайд 8Определение выбора
Описание объектов с несколькими линиями поведения:
(x → P |
y → Q),
где
α(x → P | y → Q) =
αP, x, yαP, αP = αQ.
Пример 2: копирование битов из входного канала в выходной:
αКОПИБИТ = {вв.0, вв.1, выв.0, выв.1},
КОПИБИТ = ((вв.0 → выв.0 | вв.1 → выв.1) → КОПИБИТ).
Слайд 9Параллельные процессы
Оператор параллельной композиции:
P || Q.
Законы:
P || Q = Q
|| P – логическая симметрия между процессом и его окружением;
(c
→ P) || (c → Q) = c → (P || Q),
(c → P) || (d → Q) = СТОП – пара процессов с одинаковыми алфавитами либо одновременно выполняет одно и то же действие, либо попадает в состояние тупика, если начальные события процессов не совпадают;
Слайд 10Параллельные процессы
Оператор параллельной композиции:
P || Q.
Законы:
P || (Q || R)
= (P || Q) || R – ассоциативность (при совместной
работе процессов неважно, в каком порядке они объединены оператором параллельной композиции);
P || СТОПαP = СТОПαP – процесс, находящийся в тупиковой ситуации, приводит к тупику всей системы.
Слайд 11Задача об обедающих философах
Алфавит философа:
αФИЛi = {i.садится, i.встает, i.берет_вил.i, i.берет_вил.(i+51),
i.кладет_вил.i,
i.кладет_вил.(i+51)}
Алфавит вилки:
αВИЛi = {i.берет_вил.i, (i–51).берет_вил.i,
i.кладет_вил.i, (i–51).кладет_вил.i}
Слайд 12Задача об обедающих философах
Поведение философа:
ФИЛi = (i.садится → i.берет_вил.i →
i.берет_вил.(i+51) →
i.кладет_вил.i → i.кладет_вил.(i+51) → i.встает → ФИЛi)
Поведение вилки:
ВИЛi =
(i.берет_вил.i → i.кладет_вил.i → ВИЛi |
(i–51).берет_вил.i → (i–51).кладет_вил.i → ВИЛi)
Слайд 13Задача об обедающих философах
Поведение всего пансиона:
ФИЛОСОФЫ =
(ФИЛ0 || ФИЛ1 ||
ФИЛ2 || ФИЛ3 || ФИЛ4),
ВИЛКИ =
(ВИЛ0 || ВИЛ1 || ВИЛ2
|| ВИЛ3 || ВИЛ4),
ПАНСИОН = (ФИЛОСОФЫ || ВИЛКИ)
Слайд 14Протоколы поведения процессов
Протоколом поведения процесса называется конечная последовательность символов, фиксирующая
события, в которых процесс участвовал до некоторого момента времени.
Примеры:
–
пустой протокол;
x – протокол из одного события;
x, y – протокол из двух событий и т.д.
мон, шок, мон, мон, шок, мон, шок.
Слайд 15Операции с протоколами
Конкатенация:
s^t,
tn+1 = t^tn,
(s^t)n+1 = s^(s^t)n^t.
Например:
мон, шок^мон = мон,
шок, мон.
Свойства:
s^(t^u) = (s^t)^u – ассоциативность;
s^ = ^s = s
– пустой протокол служит единицей.
Слайд 16Операции с протоколами
Сужение:
t ↑ A.
Например:
мон, шок, мон ↑ мон =
мон, мон.
Свойства:
x ↑ A = x, если xA, y ↑
A = , если yA;
(s^t) ↑ A = (s ↑ A)^(t ↑ A) – дистрибутивность;
↑ A = , s ↑ = , (s ↑ A) ↑ B = s ↑ (AB).
Слайд 17Операции с протоколами
Голова и хвост:
s0 – первый элемент;
s′ – результат,
полученный после его удаления,
т.е. x, y0 = x, x, y′
= y.
Например:
мон, шок, мон0 = мон,
мон, шок, мон′ = шок, мон.
Слайд 18Сети Петри
Параллельные вычислительные процессы
Слайд 19Основные определения
Сеть Петри N является четверкой N = (P, T,
I, O), где:
P = {p1, p2, …, pn} – конечное
множество позиций,
n ≥ 0;
T = {t1, t2, …, tm} – конечное множество переходов,
m ≥ 0;
I: T → P* – входная функция, сопоставляющая переходу мультимножество его входных позиций;
O: T → P* – выходная функция, сопоставляющая переходу мультимножество его выходных позиций.
Слайд 20Основные определения
Граф сети Петри обладает двумя типами узлов: кружок, представляющий
позицию сети Петри; и планка, представляющая переход сети Петри.
Маркировка μ
– функция отображения
μ: P → Nat,
μ = μ(p1), μ(p2), …, μ(pn),
где n – число позиций в сети Петри и μ(pi)Nat,
1 ≤ i ≤ n – количество фишек в позиции pi.
Слайд 21Основные определения
Пример: Сеть Петри N = (P, T, I, O),
P
= {p1, p2, p3},
T = {t1, t2},
I(t1) = {p1, p1,
p2},
O(t1) = {p3},
I(t2) = {p1, p2, p2},
O(t2) = {p3}.
Слайд 22Основные определения
Маркированная сеть Петри N = (P, T, I, O,
μ) определяется совокупностью структуры сети Петри N = (P, T,
I, O) и маркировки μ.
Например, μ = 1, 0, 2:
Слайд 23Основные определения
Матричный вид сети Петри N = (P, T, I,
O) задается парой (D–, D+), где:
D–[k, i] = ^#(pi, tk)
– кратность дуги, ведущей из позиции pi в переход tk;
D+[k, i] = #^(tk, pi) – кратность дуги, ведущей из перехода tk в позицию pi,
для произвольных 1 ≤ k ≤ m, 1 ≤ i ≤ n. При этом
μ′ = μ – e[k]D– + e[k]D+ = μ + e[k]D.
Слайд 24Запуск сетей Петри
Сеть Петри выполняется посредством запусков переходов. При этом
образуется новая маркировка μ′:
μ′(p) = μ(p) – ^#(p, t) +
#^(t, p),
где:
^#: PT → Nat;
#^: TP → Nat;
μ(p) ≥ ^#(p, t);
pP.
Слайд 25Запуск сетей Петри
Пример: μ = 3, 5, 1
Слайд 26Запуск сетей Петри
Пример: μ = 3, 5, 1
После перехода t1:
μ′
= 2, 4, 2
Слайд 27Запуск сетей Петри
Пример: μ = 3, 5, 1
После перехода t1:
μ′
= 2, 4, 2
После перехода t2:
μ′′ = 1, 2, 3
Слайд 28Моделирование систем
Механизм взаимного исключения для двух процессов:
Слайд 29Моделирование систем
Простой семафор S:
n – текущее значение счётчика;
Nmax – максимальное
значение счётчика;
Р – операция блокирования семафора (WaitOne, WaitForSingleObject, acquire, …);
V
– операция деблокирования семафора (Release, ReleaseSemaphore, release, …).
Слайд 30Моделирование систем
Простой семафор S:
Слайд 31Моделирование систем
Задача об
обедающих
философах:
Слайд 32Моделирование систем
Задача об
обедающих
философах:
Слайд 33Моделирование систем
Задача об
обедающих
философах:
Слайд 34Моделирование систем
Задача об
обедающих
философах:
Слайд 35Моделирование систем
Задача об
обедающих
философах:
Слайд 36Моделирование систем
Задача об
обедающих
философах:
Слайд 37Моделирование систем
Задача об
обедающих
философах:
Слайд 38Моделирование систем
Задача об
обедающих
философах:
![Основные определенияМатричный вид сети Петри N = (P, T, I, O) задается парой (D–, D+), где:D–[k, i]](/img/tmb/4/300659/a31c6401eb09748be370371a8b744c28-800x.jpg "Параллельные вычислительные процессы Основные определенияМатричный вид сети Петри N = (P, T, I, O)")
