Демьянович Ю.К., Иванцова О.Н. Технология программирования для распределенных параллельных систем

Подождите немного. Документ загружается.

Здесь более уместна асинхронная передача сообщений: зависа-

ний не будет, программа отработает без задержки. При асинхрон-

ной передаче легко модифицировать программу при увеличении

числа процессов.

Замечание. Недостаток асинхронных передач (и в отдельных

случаях — весьма существенный) состоит в том, что резко ослабе-

вает контроль за вычислительным процессом: в частности, может

быть изменен порядок арифметиче ски х действий, что, как извест-

но, может привести к большим вычислительным погрешностям.

§ 2. Операторы взаимодействия

Предположим, что процесс А собирается передать значение про-

цессу В, а процесс В — получить это значение.

Это запишем, используя нотацию языка CSP (Communicating

Sequential Process).

process A {. . . B!e; . . .} # оператор вывода: выдать

process B {. . . A?x; . . .} # оператор ввода: запросить

Язык CSP характеризуется использованием так называемого за-

щищенного взаимодействия, о котором речь пойдет ниже.

В приведенном фрагменте использованы операторы:

B!e — оператор вывода; лучше всего его читать так: “выдать e

процессу B”.

A?x — оператор ввода, который читается так: “запросить x у

процесса A”.

Если типы переменных e и x совпадают, то операторы ввода и

вывода называются согласованными.

Эти операторы приостанавливают каждый из процессов до тех

пор пока другой пр оцес с не подойдет к выполнению соответству-

ющего согласованного оператора, после чего оба оператора выпол -

няются одновременно. Выполнение согласованных операторов мож-

но рассматривать как распределенное присваивание : здесь значение

переменной из одного процесса присваивается переменной другого

процесса. На момент такого присваивания процессы синхронизиру-

ются, а далее выполняются независимо.

Общий вид операторов ввода и вывода таков:

Destination!port(e_1, . . ., e_n);

# - выдать e_1, . . ., e_n процессу Destination

# через порт с именем port

Source?port(x_1, . . ., x_n);

# - запросить x_1, . . ., x_n у процесса Source

# через порт с именем port

Здесь Destination и Source — процессы (соответственно

процесс-приемник и процесс-источник), port — общее для обоих

процессов имя порта (это имя можно не использовать, если имеет-

ся лишь один вид сообщений, при этом с кобки можно не писать),

e_1, . . ., e_n и x_1, . . ., x_n — имена переменных соответ-

ствующих типов.

При использовании массива источников возможно обраще ни е к

определенному элементу этого массива в виде

Source[i]?port(x_1, . . ., x_n);

а также возможен запрос ко всем источникам массива в виде

Source[*]?port(x_1, . . ., x_n);

Простым примером является следующий процесс-фильтр:

process Copy {

char c;

do true -->

West?c; # запросить символ у процесса West

East!c; # выдать символ процессу East

}

Оператор ввода ждет, пока процесс West будет готов принять

символ, а оператор вывода ждет, пока процесс East будет готов

выдать символ; оба выполняются одновременно.

Язык CSP использует понятие защищенных команд.

Рассмотрим процесс отыскания наибольшего делителя двух по-

ложительных целых чисел x и y (алгоритм Евклида).

process Euc {

int id, x, y;

# ввести запрос от любого

# клиента клиентского массива:

do true -->

Client[*]?args(id, x, y);

do x>y --> x=x-y;

[ ] x<y --> y=y-x; # или

# выдать результат

# клиенту с идентификатором id :

Client[id]!result(x);

}

Клиент Client[i] взаимодействует с Euc соответствующим об-

разом:

. . . Euc!args(i, v1, v2); Euc?result(r); . . .

§ 3. Защищенное взаимодействие

Защищенные операторы взаимодействия в языке CSP имеют

вид:

B; C --> S;

Здесь B — логическое выражение, C — оператор взаимодействия,

S — список операторов.

B и C образуют защиту. Говорят, что защита (B,C) пропускает,

если B истинн о и не пропускает если B ложно.

Если B истинно (защита пропускает), а оператор C пока не вы-

полнен, то говорят, что защита пропускает, но блокирует; в про-

тивном случае говорят, что защита пропускает и не блокирует.

Защищенные операторы взаимодействия используются в опера-

торах if и do.

Рассмотрим оператор if:

if B_1; C_1 --> S_1;

[ ] B_2; C_2 --> S_2;

fi;

В этом операторе обе ветви являются защищенными операторами

взаимодействия.

Здесь сначала вычисляются логические выражения в защитах:

1) если обе защи ты не пропускают, то выполнение оператора if

заканчивается;

2) если одна из защит п ропускает, а вторая — не т, то выбира-

ется та, которая пропускает и происходит ожидание возможности

выполнения соответствующего оператора C_i;

3) если обе защиты пропускают, но блокируют, то происходит

ожидание, пока одна из них разблокируется;

4) если обе защиты пропускают и не блок ируют, то выбирается

одна из них (недетерминирование).

Аналогично работает оператор do; отличие в том, что ци кл по-

вторяется до тех пор, пока все защиты перестанут пропускать.

Рассмотрим примеры

1. В первом примере в защите нет логического выражения и по-

тому цикл выполняется бесконечно (при готовности процессов West

и East):

process Copy {

char c;

do West?c --> East!c

# запросить у процесса West и выдать процессу East

}

2. Во втором примере может буферизоваться один ил и два сим-

вола

process Copy {

char c1, c2;

West?c1 # запросить из West

do West?c2 --> East!c1

# - защита блокирована (может быть West не готов

# выполнить запрос)

# запросить еще символ из West и

# выдать предыдущий символ в East

c1=c2; # - переприсвоить символы

[ ] East!c1 --> West?c1; # - выдать символ в East и

# запросить символ из West

}

Процесс может заблокироваться и на East (если не готов принять)

и на West (если не г отов выдать запрос).

Здесь обе защиты всегда пропускают и потому ци кл никогда

не завершается; однако, время от времени он может блокировать-

ся. Если обе защиты не блокируют, то выполняется любая ветвь

(недетерминирование).

3. Третий пример. Реализацию кольцевого буфера можно полу-

чить, реализуя программу Copy в виде

process Copy {

char buffer[10];

int front=0, rear=0, count=0;

do count<10 West?buffer[rear] -->

count=count+1; rear=(rear+1) mod 10;

[ ] count>0; East!buffer[front] -->

count=count-1; front=(front+1) mod 10;

}

Здесь используется оператор do с двумя ветвями, но теперь в защи-

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

Защита в первой ветви пропускает, когда в буфере есть сво-

бодное место, и э та защита не блокирует, если процесс West готов

вывести запрашиваемый символ (в конец заполняемого буфера), а

защита во второй ветви пропускает, если в буфере есть символы и

процесс East готов получить символ (из начала массива заполнен-

ного буфера).

Цикл здесь тоже никогда не завершается, ибо хотя бы одно из

логических значений истинно.

4. В четвертом примере ис польз уется три порта: acquire, reply,

release.

Здесь рассмотри м распреде лите ль ресурсов, использующий

асинхронную передачу сообщений.

process Allocator {

int avail=MAXUNITS;

set units=[начальные значения];

int index, unitid;

do avail>0; Client[*]?acquire(index) -->

avail--; remove(units, unitid);

# удаление units из доступных

Client[index]!reply(unitid);

# ответ клиенту с указателем id

[ ] Client[*]?release(index, unitid) -->

avail++; insert(units, unitid);

# вставить units на место

}

Замечание. В этой программе не нужно сохранять запросы, по-

скольку получение сообщения acquire откладывается до тех пор,

пока не появится доступные элементы (т. е. до тех пор, пока н е

станет avail>0).

5. Пятый пример. Симме трич ное решение в задаче об обмене

значениями двух локальных переменных.

process P1 {

int value1=1, value2;

if P2!value1 --> P2?value2;

# процессу P2 выдать значение value1,

# а затем запросить у него value2

[ ] P2?value2 --> P2!value1;

# или наоборот

}

process P2 {

int value1, value2=2;

if P1!value2 --> P1?value1;

# выдать процессу P1 значение value2

# (если он готов принять),

# у процесса P1 запросить значение value1

[ ] P1?value1 --> P1!value2;

# у процесса P1 запросить значение value1

# выдать процессу P1 значение value2

}

Замечание. Напомним, что в подобных ситуациях альтернатива

выбирается недетерминированно.

§ 4. Программа генерации простых чисел

Здесь опять воспользуемся языком CSP. Пусть нам нужно найти

простые числа между 2 и n. Сначала задается список всех таких

чисел

2 3 4 5 6 . . . n

Вычеркнем числа, кратные двум, кроме первого, считая n нечет-

ным числом, пол учим

2 3 5 7 9 . . . n

Затем выче рк нем все числа, кратные трем, кроме первого. Если

продолжить этот процесс далее , то останутся лишь простые числа

от 2 до n.

Приведенный алгоритм называется решето Эратосфена.

Будем распараллеливать этот алгоритм, используя конвейер

процессов-фильтров.

Каждый фильтр получает поток чисел от своего предшествен-

ника, отделяет первое число и посылает своему преемнику все чис-

ла, некратные первому числу потока. Отделяемые числа являются

простыми.

process Sieve[1] {

int p=2;

for [i=3 to n by 2]

Sieve[2]!i; # - передать нечетные числа Sieve[2]

}

process Sieve[i=2 to L] {

int p, next;

Sieve[i-1]?p; # - запросить первое число у i-1-го,

# p является простым

do Sieve[i-1]?next -->

# - запросить следующее число у i-1-го

if (next mod p)!=0 -->

# если оно не делится на p,

# то передать его дальше:

Sieve[i+1]!next;

}

Замечание 1. Для нормального завершения всех процессов в

конце списка можно поместить маркер, после получения которого

каждый из рассмотрен ных процессов нормально завершается.

Замечание 2. Когда программа заканчивается, то искомый на-

бор простых чисел находится в переменных p рассматриваемых

процессов.

Глава 5. О НЕКОТОРЫХ ЯЗЫКАХ

ПРОГРАММИРОВАНИЯ

§ 1. О языке Occam (“Бритва Оккама”)

Язык разрабатывался для работы с транспьютерами.

Базовыми элементами языка являются декларации и три “про-

цесса”:

– присваивание;

– ввод;

– вывод.

Ввод/вывод аналогичны таковым в языке CSP, но каналы гло-

бальны по отношению к процессам и имеют имена.

Каждый канал должен иметь одного отправителя и одного по-

лучателя.

Базовые процессы объединяются в обычные процессы с помо-

щью так называемых конструкторов; существуют

– последовательные конструкторы;

– параллельный конструктор;

– защищенный оператор взаимодействия.

Конструкторы PAR — параллельный, SEQ — последовательный.

В синтаксисе Occam каждый базовый процесс, конструктор и

декларация занимают отдельную строчку; а декларация заканчи-

вается двоеточием, в записи используются отступы.

Рекурсия не поддерживается.

Пример 1.

INT x,y:

SEQ

x:=x+1 # последовательное

y:=y+1 # увеличение значений x и y

Замечание. Для п аралл ельн ого исполнения вместо SEQ можно

поставить PAR.

В языке Occam существуют также конструкторы

IF, CASE, WHILE, ALT (для защищенного взаимодействия).

Кроме того, имеется механизм, называемый репликатором (по-

хож на квантификатор).

Параллельные процессы создаются с помощью конструктора

PAR; они взаимодействуют через каналы с помощью базовых про-

цессов ввода ? и вывода !.

Пример 2. Программа эхо с клавиатуры на эк ран:

WHILE TRUE

BYTE ch:

SEQ

keyboard?ch

screen!ch

Можно написать программу, где имеется один канал с накопле-

нием и два процесса.

Пример 3.

CHAN OF BYTE comm:

PAR

WHILE TRUE # процесс вывода с клавиатуры

BYTE ch:

SEQ

keyboard?ch

comm!ch

WHILE TRUE # процесс вывода на экран

BYTE ch:

SEQ

comm?ch

display!ch

Замечание. Использование отступов делает ненужным закры-

вающие ключевые слова.

Конструктор ALT обеспечивает защищенное взаимодействие. За-

щита состоит из

1) процесса ввода или;

2) логического выражения и процесса ввода или;

3) логического выражения и конструктора SKIP.

Пример 4. Процедурный вариант копирования

PROC Copy(CHAN OF BYTE West, Ask, East)