Взаимодействующие параллельные процессы

Параллельные процессы

Взаимодействующие процессы

Взаимодействующие процессы
Независимые процессы имеют свое множество переменных и ресурсов. Другие процессы не могут изменить значения переменных этого процесса.
Взаимодействующие процессы – совместно используют общие ресурсы, и выполнение одного процесса влияет на результат другого. Ресурсами могут быть области памяти, файлы данных, ВУ и т.д.
Взаимодействовать могут конкурирующие процессы, каждый из которых использует совместный ресурс только для своих целей, либо процессы, совместно выполняющие общую работу – асинхронные процессы.

Использование общего ресурса
В результате прерывания последовательность действий обеих программ
может измениться. Пусть 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

Проблема критического участка
Общий ресурс, совместно используемый несколькими параллельными процессами, получил название – критический ресурс.
Часть программы, использующая критический ресурс, называется критическим участком (критическим интервалом, критической секцией, критической областью).
Требования к критическому участку программы:
- только один процесс может находиться внутри критического участка (взаимное исключение);
- ни один процесс не должен ждать бесконечно долго входа в критический участок;
- ни один процесс не может оставаться внутри критического интервала бесконечно долго;
-операции взаимного исключения должны выполняться корректно при нарушении работы одного или нескольких процессов вне критического участка (устойчивость к нарушениям);
- вход и выход взаимоисключения должны быть идентичными для всех процессов и не зависеть от их числа (симметрия).

Методы взаимоисключения
Используется множество методов взаимоисключения взаимодействующих параллельных процессов в критических участках: - взаимное исключение с активным ожиданием:
- запрещение прерываний,
- строгое чередование,
- алгоритмы Деккера и Петерсона,
- операция проверки и установки;
- семафоры и мьютексы;
- мониторный механизм взаимоисключения;
- обмен сообщениями между процессами;

Параллельные процессы без взаимоисключения
Cobegin
(нач. установка)
PROC1; PROC2;
coend
1
2
3
4
(переменные управления взаимоисключением)

Взаимоисключение строгим чередованием процессов
var NP: 1,2;
Begin
NP:=1;
cobegin
PROC1; PROC2; coend;
end.
1
2
3
4

Попытка взаимоисключение с использованием флагов
var C1, C2: boolean;
Begin
C1:=false; C2:=false;
cobegin PROC1; PROC2; coend;
end.
1
2
3
4

Алгоритм Деккера
VAR C1,C2:Boolean; NP:1,2;
begin
NP:=1;
C1:=FALSE; C2:=FALSE;
Cobegin PROC1; PROC2; coend;
end.

Алгоритм Петерсона
var C1, C2: boolean; var NP:1,2;
begin
C1:=false; C2:=false; cobegin PROC1; PROC2; coend;
end.
1
2
3
4

Взаимоисключение операцией проверка и установка (Test and Set)
begin Common:=false;
cobegin PROC1; PROC2; coend;
end.
1
2
3
4
Var Common:boolean;
Procedure TS (Лок, Общ);
begin Лок:=Общ;
Общ:=true; end;

Операция 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: BTS M, 1 ; вход
JC L ; взаимоисключения
; критическая секция
AND M, 0B ; выход взаимоисключения

Семафоры
Семафоры, как средство синхронизации параллельных процессов, предложил голландский математик Э. Дейкстра (E. W. Dijkstra) в 1965 г.
Семафор S это агрегат данных, который состоит из счетчика с целыми значениями S.C и очереди процессов S.Q, ждущих входа в критический участок. При создании семафора счетчик принимает начальное значение
C >= 0, а очередь – пустая.
Две операции над числовыми семафорами.

Свойства числового семафора
Работу числового семафора можно сравнить с работой автоматизиро-ванной двери, которая открывается, если бросить жетон. Жетон пропускает только одного человека. Жетон бросает не тот, кто проходит, а другой.
Свойства числовых семафоров.
Пусть 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), а другое – число желающих пройти дверь.

Логический семафор - mutex
Вместо числовой переменной S.C может использоваться переменная логического типа. Такой логический семафор получил название мьютекс (mutex – MUtual EXclusion semaphor, семафор взаимного исключения).
S.C принимает значения TRUE и FALSE, а операции P(S) и V(S) выражаются действиями:
Двоичные семафоры используются для операции взаимоисключения нескольких процессов в случае, когда в критическом участке должен находиться только один процесс, числовые семафоры обладают также другими расширенными возможностями.

Взаимоисключение числовым семафором
VAR S:Semaphore;
begin
S.C:=1;
cobegin
PROC1;
PROC2;
coend;
end.

Синхронизация процессов «Главный – Подчиненный»
VAR Event:Semaphore;
begin
Event.C:=0;
cobegin MASTER; SLAVE; coend;
end.
Обратите внимание, что здесь начальное значение счетчика семафора Event (событие) равно 0, т.е. семафор закрыт. Операция P(Event) переводит главный процесс в состояние «Ожидание», если значение семафора не было изменено. Открыть семафор может подчиненный процесс, сменив значение счетчика на 1, если подчиненный процесс выполнит V(Event) раньше.

Синхронизация процессов «Производитель – Потребитель»
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 Record;
Full,Empty,S:Semaphore;
begin
S.C:=1; Full.C:= ; Empty.C:= ;
cobegin
Repeat PRODUSER Until FALSE;
Repeat CONSUMER Until FALSE;
coend;
end.

«Читатели – Писатели»
с приоритетом читателей
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.