MPMD-языки высокого уровня. Средства синхронизации и обмена данными

Синхронизация параллельных процессов в MPMD-ЯВУ необходима в двух случаях:

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

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

Основными моделями обмена данными между параллельными процессами в MPMD-ЯВУ являются:

обмен через общие (нелокальные) переменные;
обмен посредство передачи сообщений.

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

Модель обмена данными через общие переменные.

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

Семафоры. Напомним, что бинарный семафор, это целочисленный тип данных, для которых установлены три операции (

– переменная типа "семафор"):

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

Если семафор закрыт, то процесс, вызвавший операцию

, ждет, пока семафор откроется (с помощью операции

процессом, который вызвал его закрытие).

Семафоры в ЯВУ для мультипроцессоров и мультикомпьютеров реализуются на основе семафоров ОС.

Пример 1

В языке 3L Parallel C семафоры вводятся с помощью ключевого слова SEMA, например, описание

SEMA buf_free:

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

1) Функция, выполняющая инициализацию семафора.

sema_init(s, c)

Здесь s – семафор (переменная типа SEMA); c – целое число (обычно 0 или 1). Если c=1, то после выполнения операции открытия семафора s c получает значение 1, после выполнения операции закрытия семафора – 0.

2) Функция закрытия семафора.

sema_wait(s)

3) Функция открытия семафора.

sema_signal(s)

Схема организации взаимного исключения процессов с помощью семафоров рассмотрена выше.

Оператор WAIT. Оператор WAIT в ЯВУ для мультипроцессоров и мультикомпьютеров также реализуется на основе семафоров ОС и имеет следующий синтаксис: WAIT <событие>. Покажем использование оператора WAIT на примере.

Пример 2

Рассмотрим следующую последовательную программу:

Ввод (x, y)

u:= x + y

v:= x * y

w:= u * y

z:= u / y

Вывод (u, v, w, z)

С помощью оператора WAIT можно организовать параллельное вычисление значений переменных u, v, w, z следующим образом:

    Ввод(x,y)
    FORK(М1,М2,М3,М4)
M1: u:= x + y
M2: v:= x * y
M3: WAIT (M1)
    w:= u * y
M4: WAIT (M1)
    z:= u / y
    JOIN(М1,М2,М3,М4)
    Вывод(u,v,w,z)

Событие в данной программе – завершение оператора, помеченного указанной меткой. Заметим, что допустима также, например, конструкция вида WAIT (M1 AND (x

y))

Модель обмена данными посредством передачи сообщений.

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

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

— момент времени, в который в точку обмена "приходит" процесс

— момент времени, в который точки обмена достигает процесс

, (

) — период простоя процесса

Рис. 1. К определению модели простого рандеву.

Модель обмена данными "простое рандеву" используется, например, в ЯВУ Occam, 3L parallel C, Ада.

Пример 3

В языке 3L parallel C ветви программы могут обмениваться данными как через общую память (с использованием семафоров), так и через "порты". Обмен через порты осуществляется с помощью библиотечных функций, основными из которых являются следующие:

1) Функция приема слова из порта.

chan_in_word(x, input port)
или
chan_in_word(&x, input port)

Здесь x – передаваемое слово, &x – указатель на передаваемое слово, input port – идентификатор порта ввода;

2) Функция передачи слова в порт (аналогична функции chan_in_word).

chan_оut_word(x, out port)
или
chan_out_word(&x, out port)

3) Функция приема сообщения из порта.

chan_in_message(xlen, &x, input port)

Здесь xlen – длина сообщения, &x – указатель на первый элемент передаваемого сообщения, input port – идентификатор порта входа;

4) Функция передачи сообщения в порт (аналогична функции chan_in_message).

chan_out_message(xlen, &x, input port)

Расширенное рандеву (вызов удаленной процедуры) происходит по следующей схеме:

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

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

Асинхронная передача данных может быть буферизованной или не буферизованной.

Основные виды операций обмена.

Парный обмен данными – это обмен сообщениями между двумя процессами (обмен типа "точка-точка") – см. рис. 2.

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

трансляционный обмен данными — передача сообщения от одного процесса всем остальным процессам некоторой совокупности процессов (one-to-all broadcast) – см. рис. 3;

коллекторный обмен данными — сбор данных от всех процессов некоторой совокупности процессов в один из процессов этой совокупности (single-node accumulation) – см. рис. 4;

множественный трансляционный обмен данными — передача данных от всех процессов некоторой совокупности процессов всем процессам этой совокупности (all-to-all broadcast);

множественный коллекторный обмен данными — прием сообщений каждым из процессов некоторой совокупности процессов от всех процессам этой совокупности (multi-node accumulation).

Рис. 2. Парный обмен. Жирным выделен процесс-передатчик.

Рис. 3. Трансляционный обмен. Жирным выделен процесс-передатчик.

Рис. 4. Коллекторный обмен. Жирным выделен процесс-передатчик.