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

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

Глава 6. УДАЛЕННЫЙ ВЫЗОВ ПРОЦЕДУР И

ВЗАИМОДЕЙСТВИЕ ПРОЦЕССОВ

§ 1. Удаленный вызов процедур

Удален ный вызов процедур будем обозначать RPC (Remote

Procedure Call).

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

деляемые переменные, а также процессы, которые си нхрони зи ру-

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

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

тором имеются и процессы и процедуры, при этом модули могут

находиться не в одном, а в разных адресных пространствах (см.

рис. 7).

Рис. 7. Использование модулей при удаленном вызове процедуры

Процессы в одном адресном пространстве называют облегченны-

ми потоками. При переключении контекста

такому потоку прихо-

дится сохранять относительно мало информации. Заметим, однако,

что это не относится к процессам в UNIX, ибо последние жест-

ко отделены друг от друга: каждый процесс имеет свое адресное

пространство и при переключении контекста требует сохранения

таблиц управления памятью и состояния регистров.

Процессы внутри модуля могут разделять перемен ные и вызы-

вать процедуры, объявленные в этом модуле, но процессы из дру-

гого модуля могут вызывать лишь те процед уры модуля, которые

Контекстом данного процесса в тот или иной момент времени можно на-

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

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

заменяется другим процессом с другим контекстом, так что при этом происхо-

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

приостановленного процесса прежний контекст восстанавливается.

экспортируются этим модулем. Процессы внутри модуля (локаль-

ные процессы) наз ываются фоновыми.

Модуль характеризуется следующей схемой:

module mname

[заголовки операций];

body

[объявления переменных];

[код инициализации];

[процедуры для экспортируемых операций];

[локальные процедуры и процессы];

end mname

Заголовок операции opname задается де клар ацие й op, а им ен но

op opname([параметры]){returns[результат]}

Здесь указываются типы, и могут указываться имена парамет-

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

данный раздел необязателен.

Процедуры для экспортируемых операций задаются в виде

proc opname(параметры) returns идентификатор результатов

[объявления локальных переменных];

[операторы];

end

Здесь не обязательно указывать типы параметров и результата (они

указаны в объявлении заголовка операции op).

Аналогично использованию м ониторов процесс (или процедура)

модуля вызывает процедуру другого модуля при обращении вида

call mname.opname(аргументы)

Ключевое слово call не обязательно.

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

имя модуля можно не использовать:

opname(аргументы)

Межмодульный вызов порождает обслуживающий его новый

процесс (процесс-сервер), а аргументы пе ред аются в виде сообще-

ний от вызывающего модуля. После вызова вызывающий модуль

ждет, пока процесс-сервер выполнит тело процедуры, реализующей

операцию opname. Возвращаясь из opname процесс-сервер отсыла-

ет результаты вызвавшему процессу и завершается, а вызвавший

процесс продолжает свою работу (см. рис. 8). Передача и получение

результатов происходит неявно, их специально программировать не

следует.

Рис. 8. Приостановка вызывающего процесса, работа процесса-сервера

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

одном адресном пространстве, то новый процесс не создается: вы-

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

§ 2. Вопросы взаимно исключающего доступа

и синхронизации (внутри модуля)

В модулях может быть много процессов:

– процессы-серверы (осуществляющие удаленные вызовы);

– фоновые процессы;

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

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

ция процессов.

Имеется два способа реализации взаимного исключения и син-

хронизации: все пр оцесс ы одного м одуля выполняются

1) со взаимным исключением и в каждый момент активен лишь

один процесс;

2) паралле льно (и явным образом программируется взаимное

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

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

ваться семафоры или мониторы, а также передача сообщений).

При первом способе

– модули проще программировать;

– можно достичь б´ольшей эффективности при реализации на

однопроцессорной системе.

Второй способ позволяет исключать является зацикливающиеся

процессы и является

– более общим, чем первый;

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

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

В дальнейшем будет использоваться второй способ, а именно

будем считать, что

1) процессы внутри модуля выполняются параллельно;

2) программируется взаимное исключение и условная синхрони-

зация.

§ 3. Модуль сервера времени

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

get_time

delay

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

цию get_time, и может заблокироваться (“уснуть”), вызывая опе-

рацию delay.

Сервер времени имеет внутренни й процесс, который постоян-

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

увеличивает счетчик времени.

module TimeServer

op get_time() returns int;

# - получить время

op delay (int interval, myid);

# - "заснуть" на interval "тиков"

body

int tod=0; # tod - время (суток)

sem m=1; # m - семафор исключения

sem d[n]=([n]0);

# d[n] - скрытые семафоры задержек

queue of (int waketime, int process_id) napQ

# napQ - очередь приостановленных

# процессов (при m=1 tod<waketime)

proc get_time() returns time {

time=tod;

# никаких блокировок не требуется

# процесс лишь читает tod

}

proc delay(interval, myid) { # здесь interval>0

int waketime=tod+interval;

P(m); # закрыть семафор, если он открыт

# приостановить процесс, если семафор закрыт

[вставить (waketime, myid)

в подходящее место очереди napQ]

# очередь упорядочена по времени waketime

V(m); # открыть семафор

P(d[myid]);

# ждать пропуска = закрыть семафор для myid =

# = включен спящий режим для процесса myid

}

process Clock {

[запустить аппаратный таймер];

while(true) {

[ждать прерывания, затем

перезапустить аппаратный таймер];

tod=tod+1;

P(m); # закрыть семафор, если он не закрыт

# приостановить процесс, если он закрыт

while (tod>=[наименьшее waketime из napQ]) {

[удалить (waketime,id) из napQ];

V(d[id]);

# - разбудить спящий процесс id

# (т.е. открыть семафор для id)

}

V(m); # - открыть семафор (теперь возможно

# обслуживание других процессов)

}

end TimeServer

Здесь класс queue поддерживает очередь с односторонним до-

ступом (с помощью соответствующих операций).

Замечание. Здесь предполагается, что myid принимает значения

от 0 до n-1.

§ 4. Распределенная файловая систем а

Пусть прикладной процесс вызывает файл процедурой read или

write в локальном модуле FileCache.

Локальный модуль FileCache, вообще говоря, получает данные

от модуля FileServer, который управляет блоками данных, распо-

ложенных на диске. Для того, чтобы прочитать или записать файл

на д иск модуль FileCache должен вызвать процедуры readblk или

writeblk.

Естественно, если FileCache имеет у себя требуемые данные, то

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

обратиться к модулю FileServer.

Иногда FileCache может производить упреждающие чтение или

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

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

ФАЙЛОВЫЙ КЭШ

В РАСПРЕДЕЛЕННОЙ ФАЙЛОВОЙ СИСТЕМЕ

module FileCache # рабочая станция без диска

op read (int count; result char buffer[*]);

op write (int count; char buffer[ ]);

body

[кэш файловых блоков];

[переменные для хранения информации дескриптора файла];

[семафоры для синхронизации доступа к кэш-памяти];

proc read(count, buffer) {

if ([нужные данные не находятся в кэш-памяти]) {

[выбрать блок кэш-памяти для использования];

# предполагается освободить место ...

if ([необходимо записать блок кэш-памяти])

FileServer.writeblk(...);

FileServer.readblk(...);

}

buffer=[количество count байт блока кэш-памяти];

}

proc write(count, buffer) {

if ([ блок не находится в кэш-памяти]) {

[выбрать блок в кэш-памяти для использования];

# предполагается освободить место ...

if ([необходимо записать выбранный блок])

FileServer.writeblk(...);

}

[блок кэш памяти = count байт из buffer];

}

end FileCache

ФАЙЛОВЫЙ СЕРВЕР

В РАСПРЕДЕЛЕННОЙ ФАЙЛОВОЙ СИСТЕМЕ

module FileServer # находится на файловом сервере

op readblk (int fileid, offset; result char blk[1024]);

op writeblk (int fileid, offset; char blk[1024]);

body

[кэш-память дисковых блоков];

[очередь запросов на доступ к диску];

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

к кэш-памяти и к очереди];

proc readblk(fileid, offset, blk) {

if ([нужный блок не находятся в кэш-памяти]) {

[сохранить запрос на чтение в очереди диска];

[ждать выполнения операции чтения];

}

blk=[подходящий дисковый блок];

}

proc writeblk(fileid, offset, blk) {

[выбрать блок из кэш-памяти];

if ([необходимо записать выбранный блок]) {

[сохранить запрос на запись в очереди диска];

[ждать записи блока на диск];

}

[блок кэш-памяти]=blk;

}

process DiskDriver {

while(true) {

[ждать запроса на доступ к диску];

[начать дисковую операцию; ждать прерывания;

запустить процесс, ожидающий

завершения данного запроса];

}

end FileServer

Замечание 1. Ес ли у каждого прикладного процесса есть от-

дельный модуль FileCache, то внутренняя синхронизация не нуж-

на (ибо в каждый момент времени выполняется один запрос чте-

ния или записи). В случае использования несколькими процессами

одного модуля FileCache, или если в нем реализуется упреждаю-

щее чтение, то потребуется использовать семафоры для обеспече-

ния взаимных исключе ни й.

Замечание 2. В файловом сервере взаимные исключения

необходимы, поскольку он используется несколькими модулями

FileCache и, кроме того, содержит внутренний процесс DiskDriver.

§ 5. Фильтр слияния в Remote Procedure Call (RPC)

Фильтр слияния получ ает два входных отсортированных по-

тока, а на выходе образуется один отсортированный поток. Пред-

полагается, что конец входного потока отмечен маркером EOS.

Ранее фильтр слияния рассматривался в случае наличия прими-

тивов передачи сообщений send и receive; здесь нет таких прими-

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

имодействие.

Кроме того, труднее связать экземпляры фильтров, ибо нет

единых входного и выходного каналов. Поэтому используется

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

(capability) ко входному потоку, который можно рассматривать как

указатель на операцию.

ФИЛЬТРЫ СОРТИРОВКИ СЛИЯНИЕМ

optype stream=(int); # тип операций с потоком данных

module Merge[i=1 to n]

op in1 stream, in2 stream; # входные потоки

# (экспортируемые операции)

op initialize (cap stream); # ссылка на входной поток

body

int v1,v2; # входные значения из потоков 1 и 2

cap stream out; # мандат доступа ко входному потоку

sem empty1=1, full1=0, empty2=1, full2=0;

proc initialize(output) { # обеспечить выходной поток

out=output;

}

proc in1(value1) { # создать новое значение для потока 1

P(empty1); v1=value1; V(full1);

}

proc in2(value2) { # создать новое значение для потока 2

P(empty2); v2=value2; V(full2);

}

process M {

P(full1), P(full2); # ожидать два входных значения

while(v1!=EOS and v2!=EOS)

if(v1<=v2)

{call out(v1); V(empty1); P(full1);}

else # v2<v1

{call out(v2); V(empty2); P(full2);}

# считывание остатка непустого входного канала

if(v1==EOS)

while(v2!=EOS)

{call out(v2); V(empty2); P(full2);}

else # v2==EOS

while(v1!=EOS)

{call out(v1); V(empty1); P(full1);}

call out(EOS); # присоединить маркер конца

end Merge

Описанная программа в два раза длиннее аналогичной програм-

мы параграфа 3 из главы 1, которая была основана на примитивах

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

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

раграфа. Однако, этот процесс использует оператор call для по-

мещения значения в выходной канал, а не send; для получения

следующего числа из потока используются семафоры.

Внутри модуля серверные процессы, обрабатывающие вызовы

in1 и in2 являются производителями, а M — потребителем.

Каждый модуль экспортирует операции in1 и in2. Они обеспе-

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

для получения входных значений.

Главный модуль вызывает из модулей третью операцию

initialize для того, чтобы передать фильтру мандат на доступ к

используемому выходному потоку; например, главный модуль мо-

жет дать фильтру Merge[i] мандат доступа к операции in2 филь-

тра Merge[j] с помощью строки

call Merge[i].initialize(Merge[j].in2)

Сравнение програм мы из параграфа 3 главы 1 с этой програм-

мой показывает основной недостаток: дли на программы велика

(требуются дополнительные фрагменты).

§ 6. Обмен значениями в RPC

При взаимодействии равных процессов программирование с ис-

пользованием удаленного вызова процедур (RPC) также ведет к

удлинению программы по сравнению с использованием посылки

сообщений. Предположим, что модули находятся на разных ком-

пьютерах.

ОДИН ИЗ ВАРИАНТОВ ОБМЕНА ЗНАЧЕНИЯМИ

module Exchange[i=1 to 2]

op deposit(int);

body

int othervalue;

sem ready=0; # семафор используется для сигнализации

proc deposit(other) {

# - процедура вызывается из другого модуля

othervalue=other;