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

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

Рассмотрим две разные программы 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.2.2. Взаимное исключение

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

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

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

repeat

<пролог> {вход в критическую секцию}

<критическая секция>

<эпилог> {выход из критической секции}

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

until false

Рис. 4.11

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

К критическому интервалу предъявляются следующие требования:

а) взаимного исключения (в каждый момен­т времени не более одного процесса выполняется в крити­ческом интервале) ;

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

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

г) отсутствия «зависаний»: процесс, запрашивающий вход в критический интервал, не должен находиться в состоянии ожидания неопределенное время (считается, что все процессы имеют одинаковый приоритет);

д) симметрии (пролог и эпилог должны быть идентичными для всех процессов и не зависеть от их числа).

Реализация критических интервалов основывается на взаимном исключении, обеспечиваемом техническими средствами. Все ЭВМ имеют основную форму взаимного исключения, назыв­аемую блокированием памяти. Это средство запрещает однов­ременное исполнение двух команд, которые обращаются к одной и той же ячейке памяти. Если в этой ячейке памяти хранится значение разделяемой (общей) переменной, то во время исполнения данной команды получить доступ к ней может только один процесс. Блокирование памяти предотвращает одноврем­енный доступ, но не предотвращает чередование доступов. Таким образом, если критические интервалы исчерпываются одной командой обращения к оперативной памяти, данного средства может быть достаточно для непосредственной реализации критических интервалов. Если критические интервалы требуют более одного обращения к памяти, их все же можно реализовать, используя блокировку памяти. Переменные, чья целостность гарантируется блокировкой памяти, указывают, какой процесс может войти в свой критический интервал. Однако, пользуясь только блокировкой памяти, написать правильную реализацию критических интервалов очень трудно.