Рабочие листы
к вашим урокам
Скачать
1 слайд
Взаимодействующие
параллельные
процессы
2 слайд
Параллельные процессы
P1 P2
Q1 Q2
Последовательные процессы
Логические параллельные процессы
P1 P2
Q1Q2
Физические параллельные процессы
P1 P2
Q1 Q2
3 слайд
Взаимодействующие процессы
Физически параллельные
P1 P2 P3 wait (ожидание)
P4
Q1 Q2 Q3
fork (разветвление) join (соединение)
Логически параллельные
P1 P2P3 P4
Q1Q2 Q3
4 слайд
Взаимодействующие процессы
Независимые процессы имеют свое множество переменных и ресурсов. Другие процессы не могут изменить значения переменных этого процесса.
Взаимодействующие процессы – совместно используют общие ресурсы, и выполнение одного процесса влияет на результат другого. Ресурсами могут быть области памяти, файлы данных, ВУ и т.д.
Взаимодействовать могут конкурирующие процессы, каждый из которых использует совместный ресурс только для своих целей, либо процессы, совместно выполняющие общую работу – асинхронные процессы.
5 слайд
Использование общего ресурса
В результате прерывания последовательность действий обеих программ
может измениться. Пусть Count = 10 и эта последовательность станет
1-4-5-6-2-3.
1 CX = 10
4 CX = 10
5 CX = 9
6 Count = 9
CX = 11
Count = 11
Правильное значение CX = 10 Эта ситуация называется коллизией.
Работа с Count не является единой неделимой операцией.
1 inc Count 2 dec Count
6 слайд
Проблема критического участка
Общий ресурс, совместно используемый несколькими параллельными процессами, получил название – критический ресурс.
Часть программы, использующая критический ресурс, называется критическим участком (критическим интервалом, критической секцией, критической областью).
Требования к критическому участку программы:
- только один процесс может находиться внутри критического участка (взаимное исключение);
- ни один процесс не должен ждать бесконечно долго входа в критический участок;
- ни один процесс не может оставаться внутри критического интервала бесконечно долго;
-операции взаимного исключения должны выполняться корректно при нарушении работы одного или нескольких процессов вне критического участка (устойчивость к нарушениям);
- вход и выход взаимоисключения должны быть идентичными для всех процессов и не зависеть от их числа (симметрия).
7 слайд
Методы взаимоисключения
Используется множество методов взаимоисключения взаимодействующих параллельных процессов в критических участках:
- взаимное исключение с активным ожиданием:
- запрещение прерываний,
- строгое чередование,
- алгоритмы Деккера и Петерсона,
- операция проверки и установки;
- семафоры и мьютексы;
- мониторный механизм взаимоисключения;
- обмен сообщениями между процессами;
8 слайд
Параллельные процессы без взаимоисключения
Cobegin
(нач. установка)
PROC1; PROC2;
coend
1
2
3
4
(переменные управления взаимоисключением)
9 слайд
Взаимоисключение строгим чередованием процессов
var NP: 1,2;
Begin
NP:=1;
cobegin
PROC1; PROC2; coend;
end.
1
2
3
4
10 слайд
Попытка взаимоисключение с использованием флагов
var C1, C2: boolean;
Begin
C1:=false; C2:=false;
cobegin
PROC1; PROC2; coend;
end.
1
2
3
4
11 слайд
Алгоритм Деккера
VAR C1,C2:Boolean; NP:1,2;
begin
NP:=1;
C1:=FALSE; C2:=FALSE;
Cobegin PROC1; PROC2; coend;
end.
12 слайд
Алгоритм Петерсона
var C1, C2: boolean; var NP:1,2;
begin
C1:=false; C2:=false; cobegin PROC1; PROC2; coend;
end.
1
2
3
4
13 слайд
Взаимоисключение операцией проверка и установка (Test and Set)
begin Common:=false;
cobegin PROC1; PROC2; coend;
end.
1
2
3
4
Var Common:boolean;
Procedure TS (Лок, Общ);
begin Лок:=Общ;
Общ:=true; end;
14 слайд
Операция Test and Set
Procedure TS (Лок, Общ);
begin
Лок:=Общ;
Общ:=TRUE;
end;
Общ:=false;
(критич. участок свободен)
Лок1:=True;
While Лок1 do TS(Лок1,Общ);
true false
false <- false
false true
Общ:=true;
(критич. Участок занят)
Лок2:=True;
While Лок2 do TS(Лок2,Общ);
true true
true <- true
true true
Команда BTS источник, индекс
Переносит бит по адресу источник[индекс] -> CF (Лок),
Затем бит источник[индекс]<- 1 (Общ).
L:BTSM, 1; вход
JCL; взаимоисключения
;критическая секция
ANDM, 0B; выход взаимоисключения
15 слайд
Семафоры
Семафоры, как средство синхронизации параллельных процессов, предложил голландский математик Э. Дейкстра (E. W. Dijkstra) в 1965 г.
Семафор S это агрегат данных, который состоит из счетчика с целыми значениями S.C и очереди процессов S.Q, ждущих входа в критический участок. При создании семафора счетчик принимает начальное значение
C >= 0, а очередь – пустая.
Две операции над числовыми семафорами.
16 слайд
Свойства числового семафора
Работу числового семафора можно сравнить с работой автоматизиро-ванной двери, которая открывается, если бросить жетон. Жетон пропускает только одного человека. Жетон бросает не тот, кто проходит, а другой.
Свойства числовых семафоров.
Пусть C0 – начальное значение S.C, nP и nV – общее число выполнения операций P(S) и V(S).
Тогда:
- текущее значение счетчика семафора: S.C = C0 – nP + nV;
- число процессов в состоянии ожидания: nB = max(0,–S.C);
- число форсирований: nF = min(nP,C0–nV).
Последний параметр показывает насколько nP больше nV. По аналогии с автоматической дверью nF дает знать, что количество прошедших равно наименьшему из двух чисел, одно из которых есть общее количество опущенных жетонов C0+nV(S), а другое – число желающих пройти дверь.
17 слайд
Логический семафор - mutex
Вместо числовой переменной S.C может использоваться переменная логического типа. Такой логический семафор получил название мьютекс (mutex – MUtual EXclusion semaphor, семафор взаимного исключения).
S.C принимает значения TRUE и FALSE, а операции P(S) и V(S) выражаются действиями:
Двоичные семафоры используются для операции взаимоисключения нескольких процессов в случае, когда в критическом участке должен находиться только один процесс, числовые семафоры обладают также другими расширенными возможностями.
18 слайд
Взаимоисключение числовым семафором
VAR S:Semaphore;
begin
S.C:=1;
cobegin
PROC1;
PROC2;
coend;
end.
19 слайд
Синхронизация процессов «Главный – Подчиненный»
VAR Event:Semaphore;
begin
Event.C:=0;
cobegin MASTER; SLAVE; coend;
end.
Обратите внимание, что здесь начальное значение счетчика семафора Event (событие) равно 0, т.е. семафор закрыт. Операция P(Event) переводит главный процесс в состояние «Ожидание», если значение семафора не было изменено. Открыть семафор может подчиненный процесс, сменив значение счетчика на 1, если подчиненный процесс выполнит V(Event) раньше.
20 слайд
Синхронизация процессов «Производитель – Потребитель»
VAR Buf:Record;
Start,Finish:Semaphore;
begin
Start.C:=0; Finish.C:=1;
cobegin
Repeat PRODUSER Until FALSE;
Repeat CONSUMER Until FALSE;
coend;
end.
Обратите внимание на начальные значения счетчиков семафоров.
![«Производитель – Потребитель» множественный буферVAR Buf:array [1..N] of Reco...](https://documents.infourok.ru/7db39852-2143-4bc2-9880-89be4b656790/slide_21.jpg "«Производитель – Потребитель» множественный буферVAR Buf:array [1..N] of Reco...")
21 слайд
«Производитель – Потребитель» множественный буфер
VAR Buf:array [1..N] of Record;
Full,Empty,S:Semaphore;
begin
S.C:=1; Full.C:= ; Empty.C:= ;
cobegin
Repeat PRODUSER Until FALSE;
Repeat CONSUMER Until FALSE;
coend;
end.
22 слайд
«Читатели – Писатели»
с приоритетом читателей
VAR Nrdr:integer; W,R:Semaphore;
Begin Nrdr:=0; W.C:=1; R.C:=1;
cobegin
Repeat READER Until FALSE;
. . .
Repeat READER Until FALSE;
Repeat WRITER Until FALSE;
. . .
Repeat WRITER Until FALSE;
coend; end.
23 слайд
«Читатели – Писатели»
с приоритетом писателей
VAR Nrdr:integer; W,R,S:Semaphore;
Begin Nrdr:=0; W.C:=1; R.C:=1; S.C:=1;
cobegin
Repeat READER Until FALSE;
. . .
Repeat READER Until FALSE;
Repeat WRITER Until FALSE;
. . .
Repeat WRITER Until FALSE;
coend; end.
Рабочие листы
к вашим урокам
Скачать
6 653 557 материалов в базе
Настоящий материал опубликован пользователем Нижельская Галина Анатольевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс профессиональной переподготовки
500/1000 ч.
Курс профессиональной переподготовки
600 ч.
Курс профессиональной переподготовки
300/600 ч.
Курс профессиональной переподготовки
300/600 ч.
Мини-курс
6 ч.
Мини-курс
10 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.