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

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

блокировка памяти;

специальные команды типа «проверка и установка»;

механизмы управления системой прерываний.

Перечисленные методы позволяют организовать такие средства, как

семафорные операции;

мониторы;

почтовые ящики;

конвейеры очереди сообщений.

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

Использование блокировки памяти при синхронизации параллельных процессов

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

Возможные проблемы при организации взаимного исключения при условии использования только блокировки памяти

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

Рис. 3

Задача вроде бы легко решается, если потребовать, чтобы процессы ПР1 и ПР2 входили в свои критические секции попеременно. Для этого одна общая переменная может хранить указатель на тот процесс, чья очередь войти в критическую секцию. В том случае, когда размерность процессов (программ) полностью совпадает, особых трудностей с организацией взаимно исключения не возникает. Однако если программа PR1 намного длиннее, чем PR2, или если процесс ПР1 заблокирован в секции PR1, или если процессор для ПР2 обладает более высоким быстродействием, то процесс ПР2 вскоре вынужден будет ждать входа в свою критическую секцию CS2, хотя процесс ПР1 и будет вне CS1. Такое ожидание может оказаться слишком долгим, то есть для этого решения один процесс вне своей критической секции может помешать другому войти в свою критическую секцию.

Устранить это блокирование с помощью двух общих переменных, которые возможно используя флаги, как указатели, находится или нет соответствующий процесс в своей критической секции. То есть с каждым из процессов ПР1 и ПР2 будет связана переменная, которая принимает значение true, когда процесс находится в своей критической секции, и false — в противном случае. Прежде чем войти в свою критическую секцию, процесс проверит значение флага другого процесса. Если это значение равно true, процессу не разрешается входить в свою критическую секцию. В противном случае процесс установит собственный флаг и войдет в критическую секцию.

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

Следующий (третий) вариант решения этой задачи усиливает взаимное исключение, так как в процессе ПР1 проверка значения переменной ПР2 выполняется только после установки переменной ПР1 в значение true (аналогично для ПР2).

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