Демьянович Ю.К., Иванцова О.Н. Технология программирования для распределенных параллельных систем
Подождите немного. Документ загружается.
# - сохраняем полученное значение
V(ready);
# - разрешаем процессу Worker забрать это значение
}
proc Worker {
int myvalue;
call Exchange[3-i].deposit(myvalue);
# - отсылаем значение myvalue другому
P(ready); # - ждем получение значения
# из другого процесса
}
end Exchange
§ 7. Операторы ввода
Если модуль экспортирует операцию
op opname([типы параметров]);
то процес с-се рвер осуществляет рандеву с процессом, вызвавшем
операцию opname и выполняет оператор ввода, простейший вариант
которого имеет вид
in opname([параметры]) --> S; ni
Область между ключевыми словами in и ni называется защи-
щенной операцией. Защита распространяется на идентификаторы
для параметров операци и opname (если они есть).
Здесь S означает последовательность операторов, реализую-
щих данную операцию.
Область видимости параметр ов — вся защищенная операция,
так что операторы из S могут считывать или записывать значения
параметров.
Оператор ввода приостанавливает работу процесса-сервера до
появления вызова операции opname. Затем проц есс -се рвер
1) выбирает самый старый из ожидающих вызовов;
2) копирует его аргументы в параметры;
3) выполняет список параметров S;
4) возвращает результирующие параметры вызвавшему процес-
су.
С этого момента процесс-сервер, выполняющий операцию, и
82
клиентский процесс, ее вызвавший, могут продолжать работу. (см.
рис. 9).
Рис. 9. Работа процесса-сервера и процесса-клиента
Ранее приведенный оператор ввода выполн яет одну операцию.
Однако, защищенное взаимодействие позволяет иметь несколько
условий
in op_1(параметры) and B_1 by e_1 --> S_1;
[ ] . . .
[ ] op_n(параметры) and B_n by e_n --> S_n;
ni
Каждая ветвь является защищенной операцией. Часть кода
перед символом --> называется защитой. Символы S_i служат
для обозначения последовательностей операторов. Выражение
and B_i называется условием синхронизации, а выражение e_i на-
зывается условием планирования.
Говорят, что защита в операторе ввода пропускает, если бы-
ла вызвана операция и соответствующее условие синхронизации
истинно (или его нет). Условие синхронизации может зависеть от
значений параметров (т. к. их область видимости включает всю за-
щищенную операцию), так что один вызов может привести к тому,
что защита пропустит, а в другом случае — не пропустит.
Выполнение in приостанавливает работу процесса, пока какая-
нибудь защита, наконец, пропустит.
Если несколько защит пропускает, то (при отсутствии условий
планирования) оператор обслуживает первый по времени вызов,
пропуская через одну из ветвей, причем выбор срабатывающей вет-
ви стандартом не определяется (фактически, ее выбор определя-
ется конфигурированием системы; допуская очевидную вольность
формулировок, говорят, что ветвь выбирается недетерминировано).
Выражение планирования используется для изменен ия порядка
83
обработки вызовов: п ер вым обслуживается самый старый вызов,
который имеет мини мальн ое значение выраже ния планирования.
Заметим, что как и условие синхронизации выражение плани -
рования может ссылаться на параметры операции, так что его зна-
чение, вообще говоря, зависит от аргументов вызова операции.
§ 8. Взаимодействие типа “клиент-сервер”
Пусть имеется процесс с локальным кольцевым буфером из n
элементов, который обслуживает две операции deposit и fetch:
deposit — производитель помещает элемент в буфер;
fetch — потребитель извлекает элемент из буфера.
Рассмотрим кольцевой буфер, построенный в помощью рандеву.
КОЛЬЦЕВОЙ БУФЕР НА ОСНОВЕ РАНДЕВУ
module BoundedBuffer
op deposit(type T), fetch(result type T);
body
process Buffer {
type T buf[n];
int front=0; rear=0; count=0;
# count - число обращений производителя к
# буферу минус число изъятий
while(true)
# вызывая deposite() производитель
# помещает товар в буфер:
in deposite(item) and count<n -->
buf[rear]=item;
# - помещение товара в буфер
rear=(rear+1) mod n;
# - номер следующего пустого ящика
count=count+1;
[ ]
# вызывая fetch(), потребитель
# забирает товар из буфера:
fetch(item) and count>0 -->
item=buf[front];
front=(front+1) mod n;
84
# - продвижение фронта заполненных ящиков
count=count-1;
ni
}
end BoundedBuffer
Далее п риве дем модуль, п ред ставляющий собой централизован-
ное решение задачи “об обедающих философах”.
РЕАЛИЗАЦИЯ ЗАДАЧИ “ОБ ОБЕДАЮЩИХ ФИЛОСОФАХ”
module Table
op getforks(int), relforks(int);
body
process Waiter {
bool eating[5]=([5] false); # булевский массив
while(true)
# защита может не пропустить, если вилки заняты
in getforks(i) and not(eating[left(i)]) and
not(eating[right(i)]) --> eating[i]=true;
[ ]
relforks(i) --> eating[i]=false;
ni
}
end Table
process Philosopher[i=0 to 4] {
while(true) {
call getforks(i); # запрос вилки
[поесть];
call relforks(i); # освобождение вилки
[поразмышлять];
}
}
Приведем пример модуля сервера времени, аналогичый рас-
смотренному ранее.
85
РЕАЛИЗАЦИЯ МОДУЛЯ СЕРВЕРА ВРЕМЕНИ
module TimeServer
op get_time() returns int; # вызов дать времени
op delay(int); # вызов задержки
op tick(); # вызывается обработчиком прерывания часов
body
process Timer {
int tod=0; # время суток
while(true)
# если для delay(waketime) имеем waketime<=tod,
# то пробуждение, иначе задержка
in get_time() returns time --> time=tod;
[ ] delay(waketime) and waketime<=tod -->
[ ] tick() --> { tod=tod+1; [запуск таймера]}
ni
}
end TimeServer
Здесь операц ии get_time и delay экспортируются для клиентов,
а tick — для обработчика прерывания часов. При вызове delay
используется условие синхронизации.
В следующем примере наряду с условием синхронизации ис-
пользуется выражение планирования. Это пример распределения
ресурсов по принципу “кратчайшее задание”; в енм фигурирует
условие планирования by time, что при выполнении условия син-
хронизации (в данном случае and free) ведет к первоочередному
выполнению наиболее раннего вызова с минимальным параметром
time.
РАСПРЕДЕЛЕНИЯ РЕСУРСОВ ПО ПРИНЦИПУ
“КРАТЧАЙШЕЕ ЗАДАНИЕ”
module SJN_Allocator
op request(int time), release();
body
process SJN {
bool free=true;
# free - занятость ресурса,
86
# free=true - ресурс свободен
while(true)
in request(time) and free by time --> free=false;
# and free - условие синхронизации
# by time - выражение планирования
# оно ведет к первоначальному исполнению
# запроса с наименьшим time
[ ] release() --> free=true;
ni
}
end SJN_Allocator
§ 9. Обмен значениями
Здесь возвращаемся к задаче, рассмотренной в параграфе 6; ре-
шение дадим с использованием рандеву. При этом процессы могут
связываться друг с другом непосредственно. Однако, следует предо-
стеречь от ошибки: процессы, сделавшие вызов одновременно, за-
блокируют друг друга. Поэтому один процесс должен выполнять
операторы call и in в одном порядке, а другой — в противополож-
ном.
module Exchange[i=1 to 2]
op deposit(int);
body
proc Worker {
int myvalue, othervalue;
if (i==1) { # один процесс вызывает
call Exchange[2].deposit(myvalue);
in deposit(othervalue) --> skip; ni
}
else { # другой процесс получает
in deposit(othervalue) --> skip; ni
call Exchange[1].deposit(myvalue);
}
}
end Exchange
87
§ 10. Объединенная нотация
Здесь р ассм атривается программная нотация, объеди няющая
RPC (Remote Procedure Call), рандеву и асинхронную передачу со-
общений в единое целое.
В этой нотации операция может быть вызвана
– либо синхронным оператором call;
– либо асинхронным оператором send
в виде строк
call Modname.opname([аргументы]);
send Modname.opname([аргументы]);
Оператор call завершается, как только операция обслужена и
возвращены результирующие аргументы, а оператор send — как
только вычислены аргументы.
Если операция возвращает результат (как функция), то она мо-
жет быть использована в выражении; в остальных случаях функ-
циональный результат игнорируется.
Операция может быть обслужена либо в процедуре proc, либо
с помощью рандеву (оператором in).
Если обслуживание происходит с помощью proc, то это произ-
водится немедленно без использования очередей.
При обслуживании оператором in создается очередь процессов,
вызывающих операцию (отметим, что доступ к очереди недели-
мый); в этом случае использование вызова call ведет к приоста-
новке вызывающего процесса, а при использовании вызова send
отправитель продолжает работу.
Таким образом, имеется четыре комбинации: два способа вызова
операции (call и send) и два способа обслуживания (proc и in).
Приведем соответствующую таблицу.
88
Т а б л и ц а № 3.
Вызов Обслуживание Результат Приостановка Образование
вызвавшего очереди
call proc Вызов да нет
процедуры
call in Рандеву да да
Динамическое
send proc создание нет нет
процесса
Асинхронная
send in передача нет да
сообщения
Замечание. Операцию нельзя одновременно обслуживать с по-
мощью proc и in, ибо возникает неопределенность, помещать ли в
очередь. Однако, она может обслуживаться в нескольких операто-
рах in, находящихся в нескольких процессах модуля; в этом случае
образуется единая очередь с неделимым доступом.
Для мониторов и асинхронной передачи сообщений ранее был
определен примитив empty, определяющий есть л и объекты в ка-
нале сообщений и ли в очереди условной переменной.
Здесь определим функцию ?opname, возвращающую число ожи-
дающих вызовов операции opname.
Пример:
in op1 ( . . . ) --> S1;
[ ] op2 ( . . . ) and ?op1==0 --> S2;
Здесь операции op1 и op2 находятся в неравном положении: вы-
зов op2 возможен только в том случае, если не было вызовов op1,
а вызов op1 возможен всегда.
§ 11. Очередь и кольцевой буфер
Здесь продемонстрируем различные способы вызова и обслужи-
вания операций.
ПОСЛЕДОВАТЕЛЬНАЯ ОЧЕРЕДЬ
module Queue
op deposit(type T), fetch(result type T);
body
89
type T buf[n];
int front=1, rear=1, count=0;
# front - передняя граница, rear - задняя граница,
# count - количество элементов в buf
proc deposit(item) {
if (count<n) {
buf[rear]=item;
# при вызове deposit в buf
# помещается новый элемент
rear=(rear+1) mod n; count=count+1;
}
else
[действия, соответствующие переполнению];
}
proc fetch(item) {
if (count>0) {
item=buf[front];
# при вызове fetch из buf извлекается элемент
front=(front+1) mod n; count=count-1;
}
else
[действия, соответствующие опустошению];
}
end Queue
Замечание 1. Если deposit вызван оператором call, то вызы-
вающий проце сс ждет, а если deposit вызвана оператором send, то
вызывающий процесс п родолжает работу.
Замечание 2. Модуль Queue пригоден для использования одним
процессом в другом модуле, но его не могут использовать одновре-
менно несколько процессов, ибо в нем нет критических секций для
защиты переменных модуля; при параллельном вызове операций
может возникнуть взаимное влияние.
Введем теперь оператор receive, а именно, следующий опера-
тор ввода
in op(f_1, . . ., f_n) --> v_1=f_1; . . .; v_n=f_n; ni
обозначим
90
receive op(v_1, . . ., v_n)
Введем еще операцию empty(), которая не имеет аргумен-
тов, и вызывается оператором send, а обслуживается оператором
receive.
Такая операция эквивалентна семафору, где send выступает в
качестве V, а receive — в качестве P. Начальное значение семафора
равно нулю. Его текущее значение, это число “пустых” сообщений,
переданных операции, минус число полученных сообщений.
В следующей программе буфера для реализации исключения
использованы семафоры.
КОЛЬЦЕВОЙ БУФЕР С СЕМАФОРАМИ
module BoundedBuffer
op deposit(type T), fetch(result type T);
body
type T buf[n];
int front=1, rear=1;
# локальные операции для имитации семафоров:
op empty(), full(), D(), F();
send D(); send F();
for [i=1 to n] # инициализация пустого "семафора"
send empty();
proc deposit(item){
receive empty(); receive D();
buf[rear]=item; rear=(rear+1) mod n;
send D(); send full();
}
proc fetch(item) {
receive full(); receive F();
item=buf[front]; front=(front+1) mod n;
send F(); send empty();
}
end BoundedBuffer
91