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

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

chair =

(

1, если посетитель уже сел в кресло,

а парикмахер еще не занят,

0, если посетитель обс луживается парикмахером.

open =



1, если выходная дверь открыта,

0, если выходная дверь закрыта.

Имеется четыре условия синхронизации:

1) посетители дожидаются освобождения парикмахера;

2) посетители ждут, пока парикмахер откроет дверь;

3) парикмахер ждет прихода посетителя;

4) парикмахер ждет ухода посетителя.

Для этого потребуется четыре условных переменных:

barber_available получает сигнал при barber>0 (очередь,

ожидающих парикмахера);

chair_occupied получает сигнал при chair>0 (очередь на за-

нятие кресла);

door_open получает сигнал при open>0 (очередь, ожидающих

окончание стрижки);

customer_left получает сигнал при open=0 (очередь, окончив-

ших стрижку).

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

wait, заключенных в циклы. В момент истинности условий выпол-

няется операция signal.

monitor Barber_Shop{

int barber=0, chair=0, open=0;

cond barber_available; # barber>0, то signal

cond chair_occupied; # chair>0, то signal

cond door_open; # open>0, то signal

cond customer_left; # open=0, то signal

procedure get_haircut(){

while(barber==0) wait(barber_available);

barber=barber-1;

chair=chair+1;

signal(chair_occupied);

while(open==0) wait(door_open);

open=open-1;

signal(customer_left);

}

procedure get_next_customer(){

barber=barber+1;

signal(barber_available);

while(chair==0) wait(chair_occupied);

chair=chair-1;

}

procedure finished_cut(){

open=open+1;

signal(door_open);

while(open>0) wait(customer_left);

}

Особенности монитора таковы.

I. В процедуре get_haircut имеется два обращения к процедуре

wait:

1) посетителю нужно ждать освобождения парикмахера (ка-

нал barber_available);

2) посетителю приходиться ждать в процессе стрижки (канал

door_open);

II. Посетителю еще нужно ждать

3) в кресле перед началом стрижки (канал chair_occupied);

4) после стрижки до открытия выходной двери (канал

customer_left).

§ 2. Активные мониторы

Как видно из предыдущих параграфов, монитор управляет ре-

сурсом, предоставляя набор процедур для доступа к нему.

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

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

В некотором смысле рассмотренные ранее мониторы являются

пассивными наборами процедур, а не активными процессами.

В условиях распределен ной памяти и взаимодействия процес-

сов на основе передачи сообщений желательно пр ограм ми ровать

мониторы в виде активных процессов.

Предположим, что в мониторе имеется лишь одна процедура op.

Тогда структура монитора такова

monitor Mon{

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

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

procedure op ([формальные параметры]){

[тело процедуры];

}

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

цесс Server.

Постоянные переменные монитора становятся локальными пе-

ременными этого процесса.

Сервер сначала инициализирует переменные, затем выполняет

один и тот же цикл, обслуживая “вызовы” процедуры op.

Имитация вызова состоит в следующем:

– сначала клиентский процесс отправляет сообщение в канал

запроса;

– ответ он получает из канала ответа.

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

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

(или специальные примитивы, позволяющие определить отправи-

теля).

chan request(int clientID, [типы входных данных]);

# - канал запроса

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

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

process Server {

int clientID;

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

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

while (true){

receive request(clientID, [входные значения]);

[код из тела операции op];

send reply[clientID]([результаты]);

}

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

send request(i, [аргументы-значения]);

# - вызов op

receive reply[i]([аргументы для результатов]);

# - ожидания ответа

}

Заметим, что каналы глобальны по отношению к процессам,

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

ское именование).

Динамическое именование также может быть применено: каж-

дый клиент создает собственный канал ответа, передавая его в пер -

вом поле запроса. В этом случае у других процессов не будет до-

ступа к ответу.

Заметим, что есл и монитор имеет несколько процедур, то в со-

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

дуру) вызывает клиент. У различных операци й могут быть разные

наборы арг умен тов: это требует программирования записей с вари-

антами и объединениями .

type op_kind=enum(op_1, ..., op_n);

# объявление перечисляемого типа

type arg_type=union(arg_1, ..., arg_n);

# объявление типа объединения

#(резервирование одного пространства)

type res_type=union(res_1, ..., res_n);

# объявление типа объединения

#(резервирование одного пространства)

chan request(int clientID, op_kind, arg_type);

# канал запросов

chan reply[n](res_type);

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

process Server {

int clientID; op_kind kind; arg_type args;

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

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

while (true){ ## инвариант цикла

receive request(clientID, kind, args);

if (kind==op_1) {[тело op_1]};

. . . . . . . . . .

else if (kind==op_n) {[тело op_n]};

send reply[clientID](results);

}

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

arg_type myargs; res_type myresults;

[поместить аргументы-значения в myargs];

send request(i, op_j, myargs); # вызов op_j

receive reply[i](myresults); # ждать ответа

}

Заметим, что при обслуживании клиента рассмотр енн ому мони-

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

операции содержит лишь последовательные операции.

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

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

тывается, что запрос может быть обработан с задержкой. Главное

отличие реализующего его серверного процесса состоит в том, что

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

запросу. Поэтому он запоминает запрос и откладывает посылку от-

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

После отправки запроса клиент ждет получения ресурса (хо-

тя могут быть и другие варианты). После освобождения ресурса

клиент посылает сообщение о его освобождении, но не ждет е го

обработки.

Сначала приведем монитор, а потом — реализующий его сервер.

МОНИТОР

monitor Resource_Allocator{

int avail=MAXUNITS;

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

cond free;

# - получает сигнал, когда процессу нужен ресурс

procedure acquire(int &id){

if(avail==0) # нет доступа,

wait(free); # уход в очередь

else # есть доступ

avail=avail-1;

remove(units, id);

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

}

procedure release(int id){

insert(units, id);

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

# возврат его на место

if(empty(free)) # нет очереди

avail=avail+1;

else

signal(free); # сигнал "очереднику"

}

СЕРВЕР РАСПРЕДЕЛЕНИЯ РЕСУРСОВ И КЛИЕНТЫ

type op_kind=enum(ACQUIRE, RELEASE);

chan request(int clientID, op_kind kind, int unitID);

chan reply[n](int unitID);

process Allocator {

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

# units - многоэлементный ресурс,

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

queue pending; # в начальном состоянии очередь пуста

int clientID, unitID; op_kind kind;

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

while (true){

receive request(clientID, kind, unitID);

if (kind==ACQUIRE) {

if (avail>0){ # удовлетворить запрос:

avail--; remove(units, unitID);

send reply[clientID](unitID);

} else # запомнить запрос:

insert(pending, clientID);

} else { # kind==RELEASE, то освобождение ресурса

if empty(pending){ # очередь пуста

# возвратить unitID в множество элементов:

avail++; insert(units, unitID);

} else {

# удовлетворить unitID для ожидающего клиента:

remove(pending, clientID);

send reply[clientID](unitID);

}

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

int unitID;

send request(i, ACQUIRE, 0); # "вызов" запросов

receive reply[i](unitID);

# использовать ресурс unitID, затем освободить его

send request(i, RELEASE, unitID);

. . .

}

Замечание. Клиенты остаются без изменений.

Здесь рассмотрен частный случай имитации монитора с помо-

щью процесса-сервера; в этом мониторе программирование прово-

дится с помощью метода передачи условия.

Для моделирования мониторов, содержащих операторы wait

или/и операторы signal, приходится сохранять ожидающий запрос

и проверять очередь ожидающих запросов.

Между программами с мониторами и с передаче й сообщений

имеется некоторое соответствие.

Т а б л и ц а № 2.

Мониторы Программы с передачей

сообщений

Постоянные переменные Локальные переменные сервера

Идентификаторы процедур Канал запроса и виды операций

Вызов процедуры send request();

receive reply();

Вход в монитор receive request();

Возврат в процедуру send reply();

Оператор wait Сохранение ожидающего запроса

Оператор signal Получение и обработка

ожидающего запроса

Тела процедур Ветви оператора выбора

по видам операций

Относительная производительность двух стиле й программиро-

вания определяется аппаратурой.

Программирование с помощью мониторов обычно эффективнее

для систем с разделяем ой памятью, и потому на таких ВС обычно

реализуются мониторы.

Для распределенных систем эффективность мониторов часто

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

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

ется оба механизма.

§ 3. Планирующий сервер

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

ку.

Для того, чтобы осуще ствлять планирование процесс должен

просматривать все ожидающие запросы. Процесс получает сооб-

щения, выполняя цикл, который завершается, когда канал request

пуст и есть хотя бы один сохраненный запрос. Затем драйвер вы-

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

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

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

рим одну из них.

Процесс записывает ожидающие запросы в одну из двух упоря-

доченных очередей left или right в зависимости от направления,

в котором для обработки запроса необходимо перемещать головки

диска из их текущего положения.

Запросы очереди left упорядочены по уменьшению номера ци-

линдра, а в очереди right — по возрастанию.

Переменная headpos запоминает текущую позицию головок, а

nsaved — число сохраненных запросов.

Пусть cy1 — затребованный адрес (т.е. позиция, куда требует-

ся переместить головку). Инвариант для внешнего цикла процесса

можно записать в следующем виде.

SST: {left — это упорядоченная очередь от наибольшего

к наименьшему}

{все значения в left не больше headpos}

{right — это упорядоченная очередь от наименьшего к

наибольшему}

{все значения в right не меньше headpos}

{если (nsaved==0), то и left и right пусты}

Примитив empty в условии внутреннего цикла while позволяет

определить, есть ли еще сообщение в очереди канала request.

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

мого опросом.

Процесс постоянно опрашивает канал request, чтобы опреде-

лить, имеются ли ожидающие запросы. Если такие запросы есть,

то процесс получает еще один запрос для того, чтобы расширить

возможность выбора подходящего. Если ожидающих запросов нет,

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

сохраненных.

ПЛАНИРУЮЩИЙ ПРОЦЕСС

chan request(int clientID, int cy1,

[типы других аргументов]);

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

process Disk_Driver {

queue left, right;

# упорядоченные очереди сохраненных запросов

int clientID, cy1, headpos=1, nsaved=0;

[переменные для запоминания

других аргументов запроса];

while (true){ ## инвариант цикла SST

while (!empty(request) or nsaved==0){

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

# переменных равно нулю, то ждать первого

# запроса или получать еще один запрос

receive request(clientID, cy1, . . .);

if (cy1<=headpos)

insert(left, clientID, cy1, . . .);

else

insert(right, clientID, cy1, . . .);

nsaved++;

# число сохраненных запросов увеличивается

}

# выбрать наилучший запрос из очередей left и right

if (size(left)==0)

remove(right, clientID, cy1, args);

else if (size(right)==0)

remove(left, clientID, cy1, args);

else

[удалить запрос, который в left или в right

ближе всего к headpos];

headpos=cy1; nsaved--;

# число сохраненных запросов уменьшается на единицу

[получить доступ к диску];

send reply[clientID](results);

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

}

§ 4. Файловые серверы и клиенты

Рассмотрим процессы, обеспечивающие доступ к файлам на дис-

ке.

Для работы с файлом клиент должен его открыть. После ра-

боты клиент закрывает файл.

Будем предполагать, что одновременно могут быть открыты не

более n файлов, а доступ к каждому открытому файлу обеспечива-

ется отдельным процессом — отдельным файловым сервером. Итак,

будем считать, что имеется n файловых серверов, причем все фай-

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

бой свободный файловый сервер.