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

процессы не могут изменить значения переменных этого процесса.

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

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

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

измениться. Пусть 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

несколькими параллельными процессами, получил название – критический ресурс.

Часть программы, использующая критический ресурс, называется критическим участком (критическим интервалом, критической секцией, критической областью).

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

параллельных процессов в критических участках:
- взаимное исключение

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

PROC2; coend;
end.
1





2

3






4

C2:=false;
cobegin
PROC1; PROC2; coend;
end.
1





2


3





4

cobegin PROC1; PROC2; coend;
end.
1





2



3





4

PROC2; coend;
end.
1








2


3




4

Var Common:boolean;
Procedure TS (Лок, Общ);
begin Лок:=Общ;

Общ:=true; end;

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), а другое – число желающих пройти дверь.

S.C может использоваться переменная логического типа. Такой логический семафор получил

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

Двоичные семафоры используются для операции взаимоисключения нескольких процессов в случае, когда в критическом участке должен находиться только один процесс, числовые семафоры обладают также другими расширенными возможностями.

Обратите внимание, что здесь начальное значение счетчика семафора Event

(событие) равно 0, т.е. семафор закрыт. Операция P(Event) переводит главный процесс в состояние «Ожидание», если значение семафора не было изменено. Открыть семафор может подчиненный процесс, сменив значение счетчика на 1, если подчиненный процесс выполнит V(Event) раньше.

PRODUSER Until FALSE;
Repeat CONSUMER Until FALSE;
coend;
end.
Обратите внимание на начальные

значения счетчиков семафоров.

Full,Empty,S:Semaphore;
begin
S.C:=1; Full.C:= ; Empty.C:= ;
cobegin

Repeat PRODUSER Until FALSE;
Repeat CONSUMER Until FALSE;
coend;
end.

R.C:=1;
cobegin
Repeat READER Until FALSE;
. . .
Repeat READER

Until FALSE;
Repeat WRITER Until FALSE;
. . .
Repeat WRITER Until FALSE;
coend; end.

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.