Разделы презентаций


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

Содержание

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

Слайды и текст этой презентации

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

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

Слайд 2Параллельные процессы

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

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

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

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

Использование общего ресурсаВ результате прерывания последовательность действий обеих программ может измениться. Пусть Count = 10 и эта

Слайд 6Проблема критического участка
Общий ресурс, совместно используемый

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

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

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

Проблема критического участка    Общий ресурс, совместно используемый несколькими параллельными процессами, получил название – критический

Слайд 7Методы взаимоисключения
Используется множество методов взаимоисключения взаимодействующих

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

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

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





2

3






4
(переменные управления взаимоисключением)

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

Слайд 9Взаимоисключение строгим чередованием процессов
var NP: 1,2;
Begin
NP:=1;
cobegin
PROC1;

PROC2; coend;
end.
1





2

3






4

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

Слайд 10Попытка взаимоисключение с использованием флагов
var C1, C2: boolean;
Begin
C1:=false;

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





2


3





4

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

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

Алгоритм ДеккераVAR C1,C2:Boolean; NP:1,2;beginNP:=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

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

Слайд 13Взаимоисключение операцией проверка и установка (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)begin Common:=false;cobegin PROC1; PROC2; coend;end.1234Var Common:boolean;Procedure TS (Лок, Общ);

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

Операция Test and SetProcedure TS (Лок, Общ);begin	Лок:=Общ;	Общ:=TRUE;end;Общ:=false;(критич. участок свободен)Лок1:=True;While Лок1 do TS(Лок1,Общ);	    true

Слайд 15Семафоры
Семафоры, как средство синхронизации параллельных процессов,

предложил голландский математик Э. Дейкстра (E. W. Dijkstra) в 1965

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

Слайд 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) выражаются действиями:

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

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

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

Взаимоисключение числовым семафоромVAR S:Semaphore;beginS.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) раньше.
Синхронизация процессов «Главный – Подчиненный»VAR Event:Semaphore;beginEvent.C:=0;cobegin MASTER; SLAVE; coend;end.   Обратите внимание, что здесь начальное значение

Слайд 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:Record;  Start,Finish:Semaphore;beginStart.C:=0; Finish.C:=1;cobegin Repeat PRODUSER Until FALSE; Repeat CONSUMER Until FALSE;coend;end.Обратите

Слайд 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.
«Производитель – Потребитель» множественный буферVAR Buf:array [1..N] of Record;  Full,Empty,S:Semaphore;beginS.C:=1;    Full.C:=  ;

Слайд 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.
«Читатели – Писатели» с приоритетом читателейVAR Nrdr:integer; W,R:Semaphore;Begin  Nrdr:=0; W.C:=1; R.C:=1;cobegin Repeat READER Until FALSE; .

Слайд 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.
«Читатели – Писатели» с приоритетом писателейVAR Nrdr:integer; W,R,S:Semaphore;Begin  Nrdr:=0; W.C:=1; R.C:=1; S.C:=1;cobegin Repeat READER Until FALSE;

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика