Синхронизация параллельных процессов

Параллельная обработка

Рассмотрим две разные программы P и Q со своими сегментами процедур и данных. Обозначим соответствующие им процессы p и q . Выполнение совокупности процессов (p, q ) может происходить разными путями (возможные трассы совокупности этих процессов представлены на рис.4.10).

Рис. 4.10. Совместное выполнение нескольких процессов

По схеме на рис.4.10,а сначала полностью выполняется один процесс (процесс p), а затем - второй (процесс q ). По схеме на рис.4.10,б поочередно выполняются : последовательность инструкций p , потом последовательность инструкций q , затем вновь последовательность следующих инструкций p и т.д., пока не окончатся оба процесса.

Схема на рис.4.10,а является схемой последовательного выполнения процессов p и q. Как отмечалось ранее, она описывается неравенствами

КОН(q) < НАЧ(p) или КОН(p) < НАЧ(q) .

Схема на рис.4.10,б является схемой параллельного выполнения. Она, в свою очередь, описывается неравенствами

КОН(p) > НАЧ(q) и КОН(q) > НАЧ(p).

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

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

Взаимное исключение

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

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

Секция программы, предшествующая критической секции, носит название входная секция или пролог. Часть программы, непосредственно следующая за критической секцией, называется выходной секцией или эпилогом. В соответствии с этим общая структура программы какого-либо процесса имеет вид (рис.4.11):

repeat

Алгоритм Деккера

Примером программной реализации взаимного исключения является алгоритм Деккера (названный так по имени предложившего его голландского математика Деккера), позднее усовершенствованный Дейкстрой. Программа использует три общие для обоих процессов переменные (рис.4.12) : flag[1] и flag[2], устанавливающие возможность входа в критический интервал соответственно первого и второго процесса, и turn, определяющуюномер выбранного процесса.

Процесс P1 уведомляет о желании войти в свой критический участок, устанавливая свой флаг. Затем он переходит к циклу, в котором проверяет, не хочет ли также войти в свой критический участок и P2. Если флаг Р2 не установлен, то Р1 пропускает тело цикла ожидания и входит в свой критический участок. Предположим, однако, что Р1 при выполнении цикла проверки обнаруживает, что флаг Р2 установлен. Это заставляет Р1 войти в тело своего цикла ожидания. Здесь он анализирует значение переменной turn, которая используется для разрешения конфликтов, возникающих в случае, когда оба процесса одновременно хотят войти в свой критический участок. Если избранным процессом является Р1, он пропускает тело своего цикла if и повторно выполняет цикл проверки в ожидании момента, когда Р2 сбросит свой флаг. (Процесс Р2 со временем должен это сделать.). Если процесс Р1 определяет, что преимущественное право принадлежит процессу Р2, он входит в тело своего цикла if, где сбрасывает свой собственный флаг, а затем блокируется в цикле ожидания, пока избранным процессом остается Р2. Сбрасывая свой флаг, Р1 дает возможность Р2 войти в свой критический интервал. Со временем Р2 выйдет из своего критического участка и обеспечит возврат преимущественного права процессу Р1 и сброс флага Р2. Теперь у Р1 появляется возможность выйти из внутреннего цикла ожидания while и установить собственный флаг. Затем Р1 выполняет внешний цикл проверки. Если флаг Р2 (недавно сброшенный) по-прежнему сброшен, то Р1 входит в свой критический участок. Если, однако, Р2 сразу же пытается вновь войти в свой критический участок, то его флаг будет установлен, и Р1 снова придется войти в тело внешнего цикла while. Однако на этот раз «бразды правления» находятся уже у процесса Р1, поскольку сейчас именно он является избранным процессом (процесс Р2, выходя из своего критического ин тервала, установил для переменной turn - номера избранного процесса - значение 1). Поэтом­у Р1 пропускает тело условной конструкции if и многократно выполняет внешний цикл проверки, пока Р2 не сбросит собственный флаг, позволяя процессу Р1 войти в свой критический интервал.

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

флаг и вновь войдет в свой критический интервал. Когда Р1 снова захватит

Program Dekker’s algorithm;

Var flag: array[1..2] of boolean;

turn: 1..2;

ProcedureProcess P1;

begin

Repeat

flag[1] := true ;

whileflag[2] do

if turn = 2 then

flag[1] := false;

while turn = 2 do;

flag[1] := true

end;

< критический интервал >;

turn := 2 ;

flag[1] := false ;

< остальная часть программы >

untilfalse

end;

Procedure Process P2;

begin

Repeat

flag[2] := true ;

whileflag[1] do

if turn = 1 then

flag[2] := false;

while turn = 1 do;

flag[2] := true

end;

< критический интервал >;

turn := 1 ;

flag[2] := false ;

< остальная часть программы >

untilfalse

end;

Begin

flag[1] := false ;

flag [2] := false ;

turn := 1 ;

Process P1 ;

Process P2

End .

Рис. 4.12. Реализация взаимного исключения согласно алгоритму Деккера

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: