Лекция 7 Глава Синхронизация параллельных процессов на высоком уровне - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Лекция 5 Глава Синхронизация параллельных процессов на низком уровне 1 86.89kb.
Лекция Синхронизация 1 279.14kb.
Семафоры и синхронизация процессов 1 44.41kb.
Столице Южного Урала 2012 год запомнился насыщенными спортивными... 1 29.74kb.
Об аварийном, экстремально высоком и высоком загрязнении окружающей... 3 587.16kb.
Понятие и структура ос. Эволюция вычислительных и ос. Основные функции ос 5 765.71kb.
Четвертая конференция стран ес и Центральной Азии на высоком уровне... 1 45.46kb.
Лекция для аспирантов БиБи №8 из части I раздела 2, посвященного... 1 272.53kb.
Книга Иисуса Навина 1 Глава 1 1 Глава 2 2 Глава 3 3 Глава 4 4 Глава... 10 525.38kb.
Книга Пророка Иеремии 1 Глава 1 2 Глава 2 3 Глава 3 4 Глава 4 6 Глава... 23 1126.9kb.
Книга Пророка Исаии 1 Глава 1 2 Глава 2 3 Глава 3 4 Глава 4 5 Глава... 21 987.21kb.
Программа Третьей международной научно-практической конференции «Актуальные... 1 111.66kb.
Направления изучения представлений о справедливости 1 202.17kb.

Лекция 7 Глава Синхронизация параллельных процессов на высоком уровне - страница №1/1

“Системное программное обеспечение”


Лекционный курс в 6-7 семестрах для специальности 510200


Лекция 7



Глава 6. Синхронизация параллельных процессов на высоком


уровне


  1. Мониторы. Команды Wait() и Signal(). Монитор, реализующий двоичный семафор.

  2. Решение задачи передачи данных одного процесса другому при помощи монитора (случай кольцевого буфера).

  3. Решение задачи передачи данных одного процесса другому при помощи монитора (случай информационной базы).

  4. Рандеву в языке Ада. - Самостоятельно.

  5. Решение задачи передачи данных одного процесса другому с помощью задач на языке Ада (случай кольцевого буфера). - Самостоятельно.

  6. Решение задачи “обедающие философы”. - Самостоятельно.



Литература


  • [Гордеев 01] Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. СПб.: Питер, 2001.

  • [Дейтел 87] Дейтел Г., Введение в операционные системы. М."Мир",1987.

  • [Кейлингерт 85] Кейлингерт П., Элементы операционных систем, М."Мир", 1985.

  • [Кейслер 86] Кейслер С., Проектирование операционных систем для малых ЭВМ, М."Мир", 1986.

  • [Колин 75] Колин А., Введение в операционные системы, М."Мир", 1975.

  • [Цикритзис 77] Цикритзис Д., Бернстайн Ф., Операционные системы, М."Мир", 1977.

Мониторы


Рассмотренные нами в предыдущей главе средства реализации примитивов взаимоисключения элементарны, а решение с их помощью достаточно сложных проблем параллельных вычислений затруднительно. Средства синхронизации параллельных процессов более высокого уровня были первоначально предложены в работах Дейкстра и Хоара4.

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



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

Внутренние данные монитора могут быть либо глобальными, относящимися ко всем процедурам монитора, либо локальными, относящимися только к одной процедуре монитора. Ко всем этим данным можно обращаться только изнутри монитора; процессы, находящиеся вне монитора просто не могут получить доступа к данным монитора. Принимая такое структурное решение, значительно упрощающее разработку программных систем повышенной надежности, говорят, что информация спрятана (information hiding).


Команды Wait () и Signal ().


Если процесс обращается к некоторой процедуре монитора, но соответствующий ресурс занят, эта процедура выдает команду ожидания Wait. Когда монитор блокирует процесс с помощью команды Wait, он должен указать условие, при котором процесс может возобновить свою работу. Когда это условие будет выполнено, монитор выработает команду оповещения Signal, объявляющую о том, что данный ресурс освободился. Если какие-либо процессы ожидают выполнения этого условия, то один из них пробуждается и получает разрешение продолжить работу. Учитывая выше сказанное, команды ожидания и оповещения могут быть записаны следующим образом:
Wait(переменная-условие)

Signal(переменная-условие)
Переменная-условие (condition variable) вводится для каждой причины, по которой процесс может быть переведен в состояние ожидания. Заметим, что эти переменные совершеннно не похожи на обычные переменные, с которыми мы привыкли иметь дело. Когда определяется переменная-условие, заводится очередь. Процесс, выдавший команду ожидания, включается в эту очередь, а процесс, выдавший команду сигнализации, тем самым позволяет ожидающему процессу выйти из очереди и войти в монитор (обслуживание очереди может, например, осуществляться с использованием дисциплины FIFO).

Монитор, реализующий двоичный семафор.

Рассмотрим монитор, с помощью которого реализуется алгоритм выполнения операций Р и V над семафором S. Этот алгоритм известен, как алгоритм Хоара5 .

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

Monitor Семафор;

S : integer;

S_POSITIVE: condition; {переменная-условие, которая указывает, когда

заблокированный процесс может продолжать работу}
procedure P;

begin

if S<1 then Wait(S_POSITIVE);{ожидание выполнения условия}

S:=S-1

end;
procedure V;

begin

S:=S+1;

if S=1 then Signal(S_POSITIVE);{сигнал о выполнении условия}

end;

begin

S:=1

end;

Рассмотрим, каким образом, при помощи приведенного монитора Хоара можно организовать взаимоисключение двух процессов. Здесь вызовы процедур P или V монитора будем указывать как Семафор.Р или Семафор.V.



begin

Parbegin
Процесс_Х:

begin

While (true) do

begin

Call (Cемафор.Р);

{Критический участок Процесса_Х};

Call(Семафор.V);

{Оставшиеся операторы Процесса_Х}

end

end;
Процесс_Y;

begin

While (true) do

begin

Call (Cемафор.Р);

{Критический участок Процесс_Y};

Call(Семафор.V);

{Оставшиеся операторы Процесса_Y}

end

end

Parend

end.
Семантика монитора гарантирует, что если хотя бы один процесс ожидает выполнения условия, то никакой другой обратившийся процесс не может вмешаться между сигналом о выполнении этого условия и продолжением ровно одного из ожидающих процессов. Хотя по сравнению с семафорами, мониторы не представляют собой более мощного инструмента синхронизации, у них есть некоторые преимущества. Во-первых, доступ к разделяемым переменным всегда ограничен телом монитора, что автоматически исключает критические участки. Во-вторых, мониторы очень гибки, в форме мониторов можно реализовать не только рассмотренный нами семафор, но и многие другие синхронизирующие операции, о чем и пойдет речь далее.

Решение задачи передачи данных одного процесса другому при помощи монитора (случай кольцевого буфера)

Рассмотрим в этом разделе так называемый кольцевой буфер (ring buffer) и покажем, каким образом он может использоваться в случаях, когда процесс-производитель должен передавать данные процессу-потребителю.

Напомним, что реализация взаимодействия в паре “производитель-

потребитель” при помощи семафоров рассматривалась нами ранее, теперь же покажем каким образом для решения этой проблемы можно воспользоваться монитором. В качестве кольцевого буфера, куда процесс-производитель помещает данные, используем массив BUFFER заданного размера N.

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

Аналогично может возникнуть ситуация, когда процесс-потребитель хотел бы прочитать данные, а массив оказывается пустым - в этом случае процесс-потребитель должен ждать, пока процесс-производитель не поместит данные в массив.

Рассмотрим монитор Кольцевой_буфер, базовая версия которого предложена в работе 6 .
monitor Кольцевой_буфер;

var BUFFER : array [0..N-1] of Тип_данных;

Tpos : 0..N; {текущая позиция в буфере}

Zpos, Opos : 0..N-1; {соответственно, очередная заполняемая и

очередная освобождаемая позиции в буфере}

BUFNp, BUFNz : condition; { переменные-условия,

BUFNz- буфер незаполнен, является признаком, которого ждет производитель, если обнаружит, что буфер целиком заполнен, он устанавливается по сигналу потребителя о том, что тот только что освободил позицию;

BUFNp- буфер непуст, является признаком, которого ждет потребитель, если обнаружит, что буфер пуст, этот признак устанавливается по сигналу производителя о том, что он только что поместил данные в некоторую позицию буфера }

Procedure Заполнить_позицию (Данные:Тип данных) ;



begin

if Tpos = N then Wait(BUFNz){ожидание сигнала- буфер незаполнен};

BUFFER[Zpos] := Данные;

Tpos:=Tpos+1;

Zpos:=(Zpos +1) mod N;

Signal(BUFNp){сигнал, оповещающий, о том, что буфер непуст}

end;
Procedure Ocвободить_позицию ( var Данные: Тип данных) ;

begin

if Tpos=0 then Wait(BUFNp);{ожидание сигнала- буфер непуст}

Данные := BUFFER[Opos];

Tpos:=Tpos-1;

Opos:= (Opos+1) mod N;

Signal(BUFNz){сигнал, оповещающий о том, что буфер незаполнен}

end;
begin
Tpos:=0;

Opos:=0;

Zpos:=0

end;

Механизам кольцевого буфера весьма удобен для реализации управления спулингом (вводом-выводом с буферизацией) в ОС. Однако следует учитывать, что кольцевой буфер должен иметь достаточно большой размер, чтобы синхронизировать скорости работы спулера (процесса-производителя данных) и деспулера (процесса-потребителя данных).




Решение задачи передачи данных одного процесса другому при помощи монитора (случай информационной базы)

В вычислительных системах обычно имеются процессы-читатели” и “процессы-писатели”(readers and writers) , если первые читают данные из информационной базы, то вторые, записывают данные в информационные базы. Заметим, что процессы-читатели не изменяют содержимого базы и могут обращаться к ней одновременно. А процесс-писатель может изменять данные, поэтому он должен иметь монопольный, исключительный доступ к базе данных.



Эта задача была впервые сформулирована и решена в работе Куртуа, Хейманса и Парнаса7. Решение этой задачи с использованием монитора впервые было предложено в работе Хоара8.
monitor Читатели_Писатели;
var

READERS : integer;{переменная указывает количество активных читателей, когда READERS = 0, ожидающий процесс-писатель получает возможность начать работу}

SmbWRITE : boolean;{somebody write - когда кто-то пишет эта

переменная имеет истинное значение}

PermREAD,

PermWRITE : condition; {permission read/write - пока не появится истинное значение условия читать разрешается,PermREAD - процесс-читатель не может продолжить свое выполнение; пока не появится истинное значение условия писать разрешается, Permwrite - процесс-писатель не может продолжить свое выполнение}


Procedure Начало_Чтения;

begin

if (SmbWRITE) or (Очередь(PermWRITE))

then Wait(PermREAD);{ожидание сигнала - читать разрешается}

READERS:=READEARS+1;

Signal(PermREAD);{сигнал, оповещающий о возможности чтения}

end;

Procedure Конец_Чтения;

begin

READERS:=READERS-1;

If READERS=0 then Signal(PermWRITE);{сигнал, оповещающий о

возможности записи}

end;
Procedure Начало_Записи;

begin

if (READERS>0) or (SmbWRITE)

then Wait(PermWRITE);{ожидание сигнала - писать разрешается}

SmbWRITE:=true

end;
Procedure Конец­_Записи;

begin

SmbWRITE:=false;

if Очередь(PermREAD)

then Signal(PermREAD) {сигнал, оповещающий о возможности чтения}

else Signal(PermWRITE);{сигнал, оповещающий и возможности записи}

end;
begin

READERS:=0;

SmbWRITE:=false

end;
Когда процессу-читателю нужно произвести чтение, он вызывает процедуру монитора под названием Начало_Чтения, а после завершения чтения - процедуру Конец_Чтения. После входа в процедуру Начало_Чтения новый процесс-читатель сможет продолжить свою работу, если нет процесса-писателя, производящего в данный момент запись или ожидающего очереди на запись. Второе из этих условий необходимо для того, чтобы предотвратить возможность бесконечного откладывания ожидающих процессов-писателей. Отметим, что процедура Начало_Чтения завершается выдачей сигнала разрешающего чтение, PermREAD, чтобы следующий, ожидающий в очереди читатель мог начать чтение. Причем во время выполнения такой цепочки действий все вновь приходящие процессы включаются в очередь ожидания.

Когда процесс завершает операцию чтения, он вызывает процедуру Конец_Чтения, которая уменьшает число читателей на 1 и, в конце концов количество процессов-читателей становится равным 0; в этот момент вырабатывается сигнал разрешающий запись, PermWRITE, и следующий процесс-писатель получает возможность продолжать работу.

Когда процессу-писателю нужно произвести запись, он вызывает процедуру Начало_Записи. Поскольку процесс-писатель должен иметь монопольный доступ к информации, то если в настоящий момент есть уже работающие процессы-читатели или какой-либо активизированный процесс-писатель, данному процессу-писателю придется ждать выдачи сигнала PermWRITE. Когда же писатель получает возможность продолжить работу, переменная SmbWRITE:=true.

Когда процесс-писатель заканчивает свою работу, он устанавливает SmbWRITE:=false, тем самым, открывая вход в монитор для других процессов.

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

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




Решение задачи “обедающие философы”

(для самостоятельной работы)

Одна из наиболее интересных задач, предложенных Дейкстрой9 - это задача об обедающих философах. Она иллюстрирует многие нюансы, присущие параллельному программированию.



Формулировка задачи заключается в следующем.

Пять философов сидят за круглым столом. Каждый из них ведет простую жизнь - некоторое время они предаются размышлениям, а некоторое время едят спагетти. Перед каждым философом находится блюдо, которое постоянно пополняет специальный слуга. На столе лежат ровно пять вилок, по одной между каждыми двумя соседями-философами. Чтобы есть спагетти, в соответствии с правилами хорошего тона, философ должен использовать обе вилки, которые лежат по обе стороны его тарелки.

Задача заключается в том, чтобы разработать параллельную программу с монитором, моделирующую поведение философов. В программе должна исключаться возможность тупиков и бесконечного откладывания, в противном случае один, или несколько философов вскоре погибнут голодной смертью. Программа должна обеспечивать взаимоисключение - два философа не могут одновременно пользоваться одной и той же вилкой. Рассмотрим процедуры, описывающие поведение философов.

Procedure Типичный_философ;

begin

while (true) do

begin

мыслить;

есть

end

end;
Прокомментируйте каждый из следующих фрагментов, реализующих поведение философов, какие последствия вызовет реализация этих алгоритмов?
Procedure Типичный_философ_А;

begin

while (true) do

begin

мыслить_некоторое время;

взять_обе_вилки;

есть_некоторое время;

положить_обе_вилки

end

end;

Procedure Типичный_философ_В;

begin

while (true) do

begin

мыслить_некоторое время;

repeat

взять_левую_вилку;

if правой_вилки_нет then положить_левую_вилку

else взять_правую_вилку

until в_руках_обе_вилки;

есть_некоторое время;

положить_левую_вилку;

положить_правую_вилку

end

end;

Вопросы


  1. Укажите сходства и различия в применении мониторов и операций над семафорами.

  2. В чем отличия обычных переменных от переменных-условий?

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

  4. Рассмотрим простую операционную систему, состоящую из главного процесса М, работающего с ЦП; читающего процесса R, который работает с читающим каналом и печатающего процесса Р, который работает с печатающим каналом. Запрограммируйте эти три процесса так, чтобы процесс R читал данные и передавал их процессу М, который обрабатывал бы эти данные и передавал процессу Р для выдачи на печать.

Запрограммируйте эти процессы для случаев:

  • имеются два буферных пула, содержащие по К буферов;

  • имеется один буферный пул, содержащий К буферов.



4 Dijkstra E.W. Hierarchical Ordering of Sequential Processes. Acta Informatica, Vol.1,1971, pp.115-138

Hoare C.A.R. Monitors: An Operating System Structuring Concept, CACM, Vol.17,No10,1974, pp.549-557



Чарльз Энтони Ричард Хоар начал карьеру в 1960 году в Англии,. С 1977 года профессор вычислительной математики Оксфордского университета, лауреат премии Тьюринга 1980 года.

5 Hoare C.A.R. Monitors: An Operating System Structuring Concept, CACM, Vol.17,No10,1974, pp.549-557

6 Hoare C.A.R. Monitors: An Operating System Structuring Concept, CACM, Vol.17,No10,1974, pp.549-557


7 Courtois P.H., Heymans F., Parnas D.L. ConcurrentControl with Readers and Writers. CACM, Vol 14, No 10, 1971, pp. 667-668

8 Hoare C.A.R. Monitors: An Operating System Structuring Concept, CACM, Vol.17,No10,1974, pp.549-557



9 Dijkstra E.W. Hierarchical Ordering of Sequential Processes. Acta Informatica, Vol.1,1971, pp.115-138






Либо человечество покончит с войной, либо война покончит с человечеством. Джон Кеннеди
ещё >>