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

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

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

пределяющий проце сс, но в этом нет особой необходимости: можно

выделить глобальный канал open, в который клиент и направляет

запрос на получени е доступа к свободному серверу.

Каждый свободный файловый сервер опрашивает канал open

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

принять запрос (указав в ответе свой идентификатор) и ожидает

запросы от этого клиента на открытие файлов.

Клиент отправляет запрос на открытие файла в специальный

канал access[i], где i — идентификатор файлового сервера, ожи-

дающего этот запрос (т.е. сервера, ответившего клиенту о своей

готовности). При закрытие файла сервер освобождается и снова

ждет запросов.

Взаимодействие между клие нтом и сервером в приводимой ни-

же программе является отражением стиля программирования, на-

зываемого программированием “непрерывного диалога”: клиент на-

чинает диалог с файловым сервером с помощью запроса open. Да-

лее клиент п родолжает общаться с тем же сервером.

ПРОГРАММА “ФАЙЛОВЫЕ СЕРВЕРЫ И КЛИЕНТЫ”

(“непрерывный диалог”)

type kind=enum(READ, WRITE, CLOSE);

chan open(string fname; int clientID);

# запросы на открытие

chan access[n](kind k; [типы других аргументов]);

# канал доступа клиента к серверу

chan open_reply[m](int serverID);

# ответ сервера на запрос об открытии:

# id сервера или ошибка

chan access_reply[m]([типы результатов]);

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

# данные, ошибки

process File_Server[i=0 to n-1] {

string fname; int clientID;

kind k; [переменные для других аргументов];

bool more=false;

[переменные для локального буфера, кэш-памяти и т. д.];

while (true){

receive open(fname, clientID);

# получить из канала open запрос

# на открытие файла

[открыть файл fname]; [если успешно, то:]

send open_reply[clientID](i); more=true;

# если успех, то послать ответ клиенту по его

# собственному каналу

# и указать идентификатор сервера

while (more){

receive access[i](k, [другие аргументы]);

# получить из канала access[i]

# (собственность i-го сервера) запрос k

if (k==READ)

[обработать запрос на чтение];

else if (k==WRITE)

[обработать запрос на запись];

else # k==CLOSE

{[закрыть файл]; more=false;}

send access_reply[clientID](results);

# после получения от клиента команды CLOSE

# закрыть файл, послать результаты клиенту и

# закончить непрерывный диалог

}

process Client[j=0 to m-1]{

int serverID; [объявление других переменных];

send open("foo", j);

# открыть файл "foo"

# j - идентификатор клиента

receive open_reply[j](serverID);

# получить ID сервера

# использовать файл, затем закрыть его;

send access [serverID]([аргументы доступа]);

receive access_reply[j]([результаты]);

}

Замечание. Здесь фигурирует один канал open с запросами на

открытие; он совместно используется всеми клиентами и серверами.

Другие решения р ассм атриваем ой задачи состоят в следующем.

1. Можно представить определенную диспетчеризацию рас-

пределения запросов: в этом случае должен иметься процесс-

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

ловые серверы должны сообщать диспетчеру информацию о том,

что они свободны.

2. В рассмотренном решении количества клиентов и файловых

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

ние файловых серверов и клиентов, но программа будет сложнее;

однако, это, возможно, приведет к экономии при реализации.

3. Можно иметь по одному файловому серверу на каждый диск,

но тогда либо серверы, либо клиенты должны отслеживать всю ин-

формацию по открытию и закрытию файлов и передавать эту ин-

формацию при каждом запросе; это усложняет программирование

и увеличивает потоки информации.

4. Наконец, существует подход, использующий доступ к файлам

с помощью удаленных процедур (этот подход используется в фай-

ловой системе Sun Network File System /NFS/): при этом “откры-

тие” файла состоит в получении файлового дескриптора и набора

атрибутов файла, которые затем передаются при каждом вызове

процедуры доступа к файлу. В результате возрастают затраты на

передачу ар гумен тов, но существенно упрощается обработка сбо-

ев как серверов, так и клиентов (если происходит сбой файлового

сервера, то клиент просто повторяет запросы).

§ 5. Обмен значениями

Пусть имеется n процессов P[0:n-1], в каждом из которых име-

ется локальная переменная v, принявшая некоторое значение. За-

дача состоит в том, чтобы определить наибольшее и наименьшее

значения переменных v в упомянутых процессах и дать эту инфор-

мацию всем проце ссам .

Первый способ (асимметр ичн ое решение). Один из процессов

(например, P[0]) с обирает все n чисел, находит минимальное и мак-

симальное среди них и рассылает результаты остальным процессам

(см. рис. 4).

chan values(int), results[n](int smallest, int largest);

process P[0] { # управляющий процесс

int v; # переменная v считается инициализированной

int new, smallest=v, largest=v; # начальное состояние

# собрать числа, сравнить,

# запомнить минимальное и максимальное:

for [i=1 to n-1] {

receive values(new);

if (new<smallest) smallest=new;

if (new>largest) largest=new;

}

# разослать результаты остальным процессам:

for [i=1 to n-1]

send results[i](smallest, largest);

}

process P[i=1 to n-1] {

int v; # считается, что переменная v инициализирована

int smallest, largest;

send values(v);

receive results[i](smallest, largest);

}

Рис. 4. Структура взаимодействия при асимметричном решении

Второй способ (симметр ичн ое решение). Все процессы выпол-

няют один и тот же алгоритм (в стиле SIMD – Single Instruction

Multiple Data). Здесь каждый процесс отправляет свое значение

всем остальным, затем все процессы вычисляют минимум и макси-

мум из n значений (см. рис. 5).

Рис. 5. Структура взаимодействия при симметричном решении

chan values[n](int);

process P[i=0 to n-1] {

int v; # считается, что v инициализирована

int new, smallest=v, largest=v; # начальное условие

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

for [j=0 to n-1 st j!=i] # для каждого j от нуля до n-1,

# исключая j=i

send values[j](v);

# собрать значения, найти и

# заполнить минимум и максимум:

for [j=1 to n-1] {

receive values[j](v);

if (new<smallest)

smallest=new;

if (new>largest)

largest=new;

}

Третий способ (кольцевое решение). Здесь процессы организо-

ваны в логическое кольцо; каждый процесс получает сообщение от

своего предшественника и отправляет сообщение преемнику (см.

рис. 6).

Рис. 6. Структура взаимодействия при кольцевом решении

Каждый процесс пр оходит две стадии:

1) получает два числа и, подключая свое число, находит мини-

мальное и максимальное и отсылает преемнику;

2) получает значения глобально максимального и глобально ми-

нимального и отсылает преемнику.

Это решение почти симметрично: немного отличается P[0] —

это процесс ини ци ализ атор.

chan values[n](int smallest, int largest);

process P[0] { # процесс-инициализатор

int v; # считается, что v инициализирована

int smallest=v, largest=v; # начальное состояние

# послать v следующему процессу P[1]:

send values[1](smallest, largest);

# получить глобальные максимальное и

# минимальное от P[n-1] и отправить

# их процессу P[1]:

receive values[0](smallest, largest);

send values[1](smallest, largest);

}

process P[i=1 to n-1] {

int v; # считается, что v инициализирована

int smallest, largest;

# получить текущие минимум и максимум

# и обновить их, сравнивая с v:

receive values[i](smallest, largest);

if (v<smallest)

smallest=v;

if (v>largest)

largest=v;

# отправить результат следующему процессу и

# ожидать получение глобальных результатов:

send values[(i+1) mod n](smallest, largest);

}

Замечание. Симметричное решение — самое короткое , его легко

программировать, но оно требует взаимодействия каждого с каж-

дым. Хотя теоретически все сообщения могут быть посланы одно-

временно и пересылка может происходить параллельно с наимень-

шими вре мен ным и затратами, но на практике пересылка большого

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

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

Заметим, что при симметричном решении устанавливаем n(n-1)/2

связей точка-точка, где n — число ВМ; это число весьма значитель-

но, если число ВМ велико.

Кольцевое решение напоминает конвейер: операнды u

min

и u

max

получают дополнительную обработку на каждом шаге конвейера.

Однако, конвейер плохо загружен (особенно, если n велико); та-

ким образом, в рассматриваемой простой задаче кольцевое решение

вряд ли эффективно. Оно может оказаться эффективным

1) при обработке потоков данных с числом элементов данных

больше или равным n (например, при подсчете тех же минимумов

и максимумов в i-й компоненте вектора v[0:n-1], i=0,1, . . . , n-1,

если каждый ВМ имеет свой локальный вектор v);

2) при значительных вычислениях с упомянутыми (даже и ска-

лярными) данными.

Наиболее приемлемо централизованное решение в приведенном

выше первом способе: здесь данные отправляются центральному

ВМ без задерже к и без задержек обрабатываются центральным

ВМ.

Глава 4. ОПЕРАТОРЫ ВЗАИМОДЕЙСТВИЯ

И ЗАЩИТА

§ 1. Синхронная передача сообщений

Команда send не приводи т к блокировке программы, отправив-

шей сообщение. В этом случае отправленное сообщение ли бо до-

стигает адресата, либо (если адресат не может его принять) оно

остается в канале в очереди у адресата; рано и ли поздно адресат

примет сообщение. При этом отправитель продолжает свою рабо-

ту. Такой способ обработки команды называется неблокирующим и

асинхронным (он не требует синхронизации отправителя и адреса-

та).

В противоположность команде send команда synch_send явля-

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

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

Если адресат не готов принять послание, то начинается простой

отправителя. При этом процесс-отправитель не может послать но-

вое сообщение адресату. Физически сообщение находится в адрес-

ном пространстве отправителя до готовности адресата получить

его; при такой реализации возникает очер едь в канале отправителя

из адресов сообщени й нуждающихся в отправке.

Синхронной передаче свойственны следующие не достатки.

1. Первый недостаток. При взаимодействии двух процессов по

крайней мере один из них блокируется, в зависимости от того, кто

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

Рассмотрим следующую программу “производитель – потреби-

тель”:

channel values(int);

process Producer {

int data[n];

for [i=0 to n-1] {

[выполнить некоторые вычисления];

synch_send values(data[i]);

}

process Consumer {

int results[n];

for [i=0 to n-1] {

receive values(results[i]);

[выполнить некоторые вычисления];

}

Если вычисления, производимые этим процессам таковы, что

иной раз Producer выполняет их быстрее, а иной раз их быстрее

выполняет Consumer, то простаивает то Producer, то Consumer, так

что обще е время простоя процессов складывается из этих слагае-

мых. При асинхронной работе весьма вероятно, что в канале будет

скапливаться достаточное число сообщений и простоев не будет во-

все.

2. Второй недостаток блок ировок состоит в том, ч то использу-

ющие синхронизацию процессы более предрасположены к взаим-

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

чтобы соблюдалось соответствие между операторами передачи и

приема.

При программ ировани и синхронизации нужно проявлять из-

вестную осторожность; наприм ер , рассмотрим программу обмена

значениями:

channel in1(int), in2(int);

process P1 {

int value1=1, value2;

synch_send in2(value1);

receive in1(value2);

}

process P2 {

int value1, value2=2;

synch_send in1(value2);

receive in2(value1);

}

Эта программа зависнет, поскольку оба процесса заблокируются

в операторах synch_send. В одном из них (но не в обоих) нужно

выполнить операцию receive сначала, а synch_send потом.