Презентация "Взаимодействующие параллельные процессы" (11 класс) по информатике – проект, доклад

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

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

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

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

Использование общего ресурса

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

Попытка взаимоисключение с использованием флагов

var C1, C2: boolean;

Begin C1:=false; C2:=false; cobegin PROC1; PROC2; coend; end.

Алгоритм Деккера 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.

Взаимоисключение операцией проверка и установка (Test and Set)

begin Common:=false; cobegin PROC1; PROC2; coend; end.

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

Общ:=true; (критич. Участок занят) Лок2:=True; While Лок2 do TS(Лок2,Общ); true true true

Команда BTS источник, индекс Переносит бит по адресу источник[индекс] -> CF (Лок), Затем бит источник[индекс]

Семафоры

Семафоры, как средство синхронизации параллельных процессов, предложил голландский математик Э. Дейкстра (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.

«Читатели – Писатели» с приоритетом писателей

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.