Параллельные вычислительные процессы

Сентябрь 9, 2022

Главная
Математика
Параллельные вычислительные процессы

Содержание

2. ОПИСАНИЕ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ Параллельные вычислительные процессы
3. Базовые определения Имена процессов будем обозначать словами, составленными из прописных букв, а буквами P, Q, R,
4. Базовые определения Пример: автомат, торгующий шоколадками. В качестве имени процесса выберем ТАП (торговый аппарат простой). Имена
5. Префиксная запись Префиксная форма описания процессов: (x → P), где x – событие; P – процесс.
6. Рекурсивная запись Рекурсивный метод определения процесса: P = (x → P), P = (x → (y
7. Рекурсивная запись Рекурсивный метод определения процесса: P = (x → P), P = (x → (y
8. Определение выбора Описание объектов с несколькими линиями поведения: (x → P | y → Q), где
9. Параллельные процессы Оператор параллельной композиции: P || Q. Законы: P || Q = Q || P
10. Параллельные процессы Оператор параллельной композиции: P || Q. Законы: P || (Q || R) = (P
11. Задача об обедающих философах Алфавит философа: αФИЛi = {i.садится, i.встает, i.берет_вил.i, i.берет_вил.(i+51), i.кладет_вил.i, i.кладет_вил.(i+51)} Алфавит вилки:
12. Задача об обедающих философах Поведение философа: ФИЛi = (i.садится → i.берет_вил.i → i.берет_вил.(i+51) → i.кладет_вил.i →
13. Задача об обедающих философах Поведение всего пансиона: ФИЛОСОФЫ = (ФИЛ0 || ФИЛ1 || ФИЛ2 || ФИЛ3
14. Протоколы поведения процессов Протоколом поведения процесса называется конечная последовательность символов, фиксирующая события, в которых процесс участвовал
15. Операции с протоколами Конкатенация: s^t, tn+1 = t^tn, (s^t)n+1 = s^(s^t)n^t. Например: 〈мон, шок〉^〈мон〉 = 〈мон,
16. Операции с протоколами Сужение: t ↑ A. Например: 〈мон, шок, мон〉 ↑ 〈мон〉 = 〈мон, мон〉.
17. Операции с протоколами Голова и хвост: s0 – первый элемент; s′ – результат, полученный после его
18. СЕТИ ПЕТРИ Параллельные вычислительные процессы
19. Основные определения Сеть Петри N является четверкой N = (P, T, I, O), где: P =
20. Основные определения Граф сети Петри обладает двумя типами узлов: кружок, представляющий позицию сети Петри; и планка,
21. Основные определения Пример: Сеть Петри N = (P, T, I, O), P = {p1, p2, p3},
22. Основные определения Маркированная сеть Петри N = (P, T, I, O, μ) определяется совокупностью структуры сети
23. Основные определения Матричный вид сети Петри N = (P, T, I, O) задается парой (D–, D+),
24. Запуск сетей Петри Сеть Петри выполняется посредством запусков переходов. При этом образуется новая маркировка μ′: μ′(p)
25. Запуск сетей Петри Пример: μ = 〈3, 5, 1〉
26. Запуск сетей Петри Пример: μ = 〈3, 5, 1〉 После перехода t1: μ′ = 〈2, 4,
27. Запуск сетей Петри Пример: μ = 〈3, 5, 1〉 После перехода t1: μ′ = 〈2, 4,
28. Моделирование систем Механизм взаимного исключения для двух процессов:
29. Моделирование систем Простой семафор S: n – текущее значение счётчика; Nmax – максимальное значение счётчика; Р
30. Моделирование систем Простой семафор S:
31. Моделирование систем Задача об обедающих философах:
32. Моделирование систем Задача об обедающих философах:
33. Моделирование систем Задача об обедающих философах:
34. Моделирование систем Задача об обедающих философах:
35. Моделирование систем Задача об обедающих философах:
36. Моделирование систем Задача об обедающих философах:
37. Моделирование систем Задача об обедающих философах:
39. Скачать презентацию

Слайд 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.садится, 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〉, если x∈A, 〈y〉 ↑ A = 〈〉, если y∉A;
(s^t) ↑ A = (s ↑ A)^(t ↑ A) – дистрибутивность;
〈〉 ↑ A = 〈〉, s ↑ ∅ = 〈〉, (s ↑ A) ↑ B = s ↑ (A∩B).

Слайд 17

Операции с протоколами
Голова и хвост:
s0 – первый элемент;
s′ – результат, полученный

после его удаления,
т.е. 〈x, y〉0 = 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),
где:
^#: P×T → Nat;
#^: T×P → Nat;
μ(p) ≥ ^#(p, t);
p∈P.

Слайд 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

Параллельные вычислительные процессы

Содержание

ОПИСАНИЕ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВПараллельные вычислительные процессы

Базовые определенияИмена процессов будем обозначать словами, составленными из прописных букв, а

Базовые определенияПример: автомат, торгующий шоколадками.В качестве имени процесса выберем ТАП (торговый

Префиксная записьПрефиксная форма описания процессов:(x → P),гдеx – событие;P – процесс.При

Рекурсивная записьРекурсивный метод определения процесса:P = (x → P),P = (x

Рекурсивная записьРекурсивный метод определения процесса:P = (x → P),P = (x

Определение выбораОписание объектов с несколькими линиями поведения:(x → P | y

Параллельные процессыОператор параллельной композиции:P || Q.Законы:P || Q = Q ||

Параллельные процессыОператор параллельной композиции:P || Q.Законы:P || (Q || R) =

Задача об обедающих философахАлфавит философа:αФИЛi = {i.садится, i.встает, i.берет_вил.i, i.берет_вил.(i+51), i.кладет_вил.i, i.кладет_вил.(i+51)}Алфавит

Задача об обедающих философахПоведение философа:ФИЛi = (i.садится → i.берет_вил.i → i.берет_вил.(i+51)

Задача об обедающих философахПоведение всего пансиона:ФИЛОСОФЫ = (ФИЛ0 || ФИЛ1 || ФИЛ2

Протоколы поведения процессовПротоколом поведения процесса называется конечная последовательность символов, фиксирующая события,

Операции с протоколамиКонкатенация:s^t,tn+1 = t^tn,(s^t)n+1 = s^(s^t)n^t.Например:〈мон, шок〉^〈мон〉 = 〈мон, шок,

Операции с протоколамиСужение:t ↑ A.Например:〈мон, шок, мон〉 ↑ 〈мон〉 = 〈мон,

Операции с протоколамиГолова и хвост:s0 – первый элемент;s′ – результат, полученный

СЕТИ ПЕТРИПараллельные вычислительные процессы

Основные определенияСеть Петри N является четверкой N = (P, T, I,

Основные определенияГраф сети Петри обладает двумя типами узлов: кружок, представляющий позицию

Основные определенияПример: Сеть Петри N = (P, T, I, O),P =

Основные определенияМаркированная сеть Петри N = (P, T, I, O, μ)

Основные определенияМатричный вид сети Петри N = (P, T, I, O)

Запуск сетей ПетриСеть Петри выполняется посредством запусков переходов. При этом образуется

Запуск сетей ПетриПример: μ = 〈3, 5, 1〉

Запуск сетей ПетриПример: μ = 〈3, 5, 1〉После перехода t1:μ′ =

Запуск сетей ПетриПример: μ = 〈3, 5, 1〉После перехода t1:μ′ =

Моделирование системМеханизм взаимного исключения для двух процессов:

Моделирование системПростой семафор S:n – текущее значение счётчика;Nmax – максимальное значение

Моделирование системПростой семафор S:

Моделирование системЗадача об обедающих философах:

Моделирование системЗадача об обедающих философах:

Моделирование системЗадача об обедающих философах:

Моделирование системЗадача об обедающих философах:

Моделирование системЗадача об обедающих философах:

Моделирование системЗадача об обедающих философах:

Моделирование системЗадача об обедающих философах:

Похожие презентации

ОПИСАНИЕ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ
Параллельные вычислительные процессы

Базовые определения
Имена процессов будем обозначать словами, составленными из прописных букв, а

Базовые определения
Пример: автомат, торгующий шоколадками.
В качестве имени процесса выберем ТАП (торговый

Префиксная запись
Префиксная форма описания процессов:
(x → P),
где
x – событие;
P – процесс.
При

Рекурсивная запись
Рекурсивный метод определения процесса:
P = (x → P),
P = (x

Рекурсивная запись
Рекурсивный метод определения процесса:
P = (x → P),
P = (x

Определение выбора
Описание объектов с несколькими линиями поведения:
(x → P | y

Параллельные процессы
Оператор параллельной композиции:
P || Q.
Законы:
P || Q = Q ||

Параллельные процессы
Оператор параллельной композиции:
P || Q.
Законы:
P || (Q || R) =

Задача об обедающих философах
Алфавит философа:
αФИЛi = {i.садится, i.встает, i.берет_вил.i, i.берет_вил.(i+51), i.кладет_вил.i, i.кладет_вил.(i+51)}
Алфавит

Задача об обедающих философах
Поведение философа:
ФИЛi = (i.садится → i.берет_вил.i → i.берет_вил.(i+51)

Задача об обедающих философах
Поведение всего пансиона:
ФИЛОСОФЫ = (ФИЛ0 || ФИЛ1 || ФИЛ2

Протоколы поведения процессов
Протоколом поведения процесса называется конечная последовательность символов, фиксирующая события,

Операции с протоколами
Конкатенация:
s^t,
tn+1 = t^tn,
(s^t)n+1 = s^(s^t)n^t.
Например:
〈мон, шок〉^〈мон〉 = 〈мон, шок,

Операции с протоколами
Сужение:
t ↑ A.
Например:
〈мон, шок, мон〉 ↑ 〈мон〉 = 〈мон,

Операции с протоколами
Голова и хвост:
s0 – первый элемент;
s′ – результат, полученный

СЕТИ ПЕТРИ
Параллельные вычислительные процессы

Основные определения
Сеть Петри N является четверкой N = (P, T, I,

Основные определения
Граф сети Петри обладает двумя типами узлов: кружок, представляющий позицию

Основные определения
Пример: Сеть Петри N = (P, T, I, O),
P =

Основные определения
Маркированная сеть Петри N = (P, T, I, O, μ)

Основные определения
Матричный вид сети Петри N = (P, T, I, O)

Запуск сетей Петри
Сеть Петри выполняется посредством запусков переходов. При этом образуется

Запуск сетей Петри
Пример: μ = 〈3, 5, 1〉

Запуск сетей Петри
Пример: μ = 〈3, 5, 1〉
После перехода t1:
μ′ =

Запуск сетей Петри
Пример: μ = 〈3, 5, 1〉
После перехода t1:
μ′ =

Моделирование систем
Механизм взаимного исключения для двух процессов:

Моделирование систем
Простой семафор S:
n – текущее значение счётчика;
Nmax – максимальное значение

Моделирование систем
Простой семафор S:

Моделирование систем
Задача об обедающих философах:

Моделирование систем
Задача об обедающих философах:

Моделирование систем
Задача об обедающих философах:

Моделирование систем
Задача об обедающих философах:

Моделирование систем
Задача об обедающих философах:

Моделирование систем
Задача об обедающих философах:

Моделирование систем
Задача об обедающих философах: