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

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

Пусть n является степенью двойки (n = 2

). Для построения

сортирующей сети упомянутый процесс GLUE скопируем в 2

k−1

вы-

числительных модулей, подав на них по паре соседних элементов: в

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

Далее в 2

k−2

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

почек, в результате получим 2

k−2

упорядоченных цепочек по четы-

ре числа.

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

ющей сети, корень которого выдаст полностью отсортированный

поток (см. рис. 1). Высота дерева log

n, а ширина n/2.

В сети имеются каналы; входные и выходные каналы должны

быть разделяемыми.

Рис. 1. Распараллеливание процесса слияния

Пример 3. Фильтр для слияния двух входных потоков.

chan in1(int), in2(int), out(int);

process GLUE{

int v1, v2;

receive in1(v1);

receive in2(v2); # получены первые два входных числа

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

# в выходной канал и повторить

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

if (v1<=v2)

{send out(v1); receive in1(v1);}

else # (v2<v1)

{send out(v2); receive in2(v2); }

}

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

if(v1 == EOS)

while(v2!=EOS)

{send out(v2); receive in2(v2);}

else # (v2==EOS)

while(v1!=EOS)

{send out(v1); receive in1(v1);}

# добавить маркер в выходной канал

send out(EOS);

}

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

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

ниям входа.

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

Типичной схемой в параллельных программах является связь

типа клиент-сервер.

Процесс-клиент

1) запрашивает сервис;

2) ждет обработки запроса.

Процесс-сервер

1) многократно ожидает запрос;

2) обрабатывает его;

3) посылает ответ.

От клиента к серверу и обратно существует двунаправленный

поток информации.

Между клиентом и сервером возникают такие же отношения как

между программой, вызывающей подпрограмм у, и самой подпро-

граммой в последовательном прогр амми ровани и. Аналогично тому,

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

так и сервер может быть вызван многими к ли ентами.

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

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

ограничивается возможностями системы.

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

онных си стем ах, объектно-ориентированных системах, сетях, базах

данных и т.п.

Наиболее типичная ситуация — чтение и запись файла. Модуль

файлового сервера производит операции чтения (read) и записи

(write). Если проце сс- кли ен т хочет получить доступ к файлу на

сервере, то он вызывает эти операции.

На системе с разделяемыми файлами подобные операции реа-

лизуются соответствующими процедурами. При этом важно, чтобы

лишь одному процессу-клиен ту из обратившихся к данному фай-

лу в один и тот же момент времени разрешалось писать в файл;

остальные могут лишь читать из него.

В распреде лен ной системе клиенты и серверы обычно распола-

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

возникает, например, при запросе через сеть World Wide Web; это

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

URL-адрес. URL-адрес косвенно указывает на другой вычисл ител ь-

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

ступна для процесса-сервера, где располагается страница. Процесс-

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

результате запрошенная стран ица возвращается на вычислител ь-

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

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

вычислительных модулях).

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

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

мов взаимного искл ючени я и условной синхронизации.

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

виде одного или нескольких процессов, выполняющихся не на кли-

ентских машинах. Сервер представляет собой многопоточную про-

грамму с одним потоком для каждого клиента.

Глава 2. МОНИТОРЫ И УСЛОВНЫЕ ПЕРЕМЕННЫЕ

§ 1. Мониторы

Мониторы представляют собой программные модули. Как и се-

мафоры они являются мощным средством синхронизации; при этом

они реализуются столь же эффективно.

Семафоры представляют собой низкоуровенный механизм син-

хронизации: они глобальны по отношению ко всем процессам и это

доставляет значительные неудобства.

В противоположность семафорам мониторы обеспечивают боль-

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

стракции данных.

Монитор содержит пер еме нн ые, хранящие состояния объекта,

и имеет набор операций (процедур) для работы с объектом.

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

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

Параллельная программа и спол ьзует

– активные процессы;

– пассивные мониторы .

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

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

одного монитора.

В результате получается удобная модульность:

– процесс, вызывающий процедуру монитора, может не знать о

конкретной реализации процедуры;

– программист монитора может не знать о конкретных способах

использования монитора и изменять его “начинку”, сохраняя лишь

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

§ 2. Структура монитора

Монитор состоит из интерфейса и тела:

– интерфейс опред еляет предоставляемые операции (методы);

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

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

ющие интерфейс.

Хотя в различных языках мониторы объявляются и создаются

по-разному, будем считать монитор статичным объектом вида:

monitor Monname{

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

[операторы инициализации]

[процедуры]

}

Процедуры реализуют видимы е операции.

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

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

мя существования монитора).

Монитор обладает тремя свойствами:

1) вне монитора видны только имена процедур, которые следует

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

или иными п остоянными переменными, напри мер ,

call Monname.opname(arguments),

где opname — имя одной из операций (процедур) с аргументами

arguments;

2) операторы внутри монитора не могут обращаться к перемен-

ным вне монитора;

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

цедур.

Монитор отличается от механизма абстракции данных в языках

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

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

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

сов).

§ 3. Взаимное исключение в мониторе

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

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

ра.

Монитор при неявном исключении организуется так, что если

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

1) она становится активной;

2) в любой момент времени активной может быть только один

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

не могут работать одновременно с одной процедурой монитора);

3) программист, использующий монитор, не вмешивается и не

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

§ 4. Условные переменные

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

ные.

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

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

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

состояние. Условную переменную используют и для запуска при-

остановленного процесса.

Объявление условной переменной имеет вид:

cond cv;

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

ременной является очередь приостановленных процессов (очередь

задержки). В начале эта очередь пуста.

Может быть объявлен массив условных переменных:

cond cv[n];

Условные переменные можно объявлять и использовать только

в пределах мониторов.

Процесс не может обращаться непосредственно к условной пе-

ременной; он имеет лишь косвен ный доступ к ней. Имеются следу-

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

1) процесс запрашивает состояние очереди:

empty(cv);

(возвращается “истина”, если очередь пуста);

2) процесс блокируется на условной переменной

wait(cv);

(в результате процесс ставится в очередь, соответствующую этой

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

тельный доступ к монитору);

3) процесс, заблокированный на условной переменной cv, запус-

кается оператором

signal(cv);

(если очередь пуста никакие действия не производятся, иначе —

запускается процесс, находящийся в начале очереди).

Итак, процессы wait и signal обеспечивают порядок сигнали-

зации FIFO:

– процессы при останавливаются в порядке вызовов wait;

– процессы запускаются в порядке вызовов signal.

§ 5. Способы выполнения операции сигнализации

Выполнение операции signal возможно процессом, работаю-

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

signal, вообще говоря, запускает другой процесс, то может полу-

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

цесса, что невозможно по определению монитора.

Разрешение этого противоречия возможно с помощью исполь-

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

рации signal:

1) SC — “сигнализировать и продолжить” (signal and

continue): сигнализирующий процесс продолжает работу, а про-

цесс, получивший сигнал (и находящийся в оче ред и FIFO), выпол -

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

2) SW — “сигнализировать и ожидать” (signal and wait): сиг-

нализирующий процесс приостанавливается, а процесс, получив-

ший сигнал вып олняется сразу.

Стратегия “сигнализировать и продолжить” не прерывает об-

служивания. Процесс, выполнивший операцию signal, сохраняет

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

ния, а процесс, получивший сигнал, будет иметь исключи тельный

доступ к этой процед уре монитора сразу после завершения вызвав-

шего процесса.

Стратегия “сигнализировать и ожидать” означает прерывание

сигнализирующего процесс а и немедленное начало выполнения вы-

званного процесса с возобновлением прерванного процесса после

завершения вызванного.

В этой стратегии имеются различные варианты выполнения: по-

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

это значит, что он помещается в очередь; может быть вариант, ко-

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

“сигнализировать и срочно ожидать”). Кроме того, возможны раз-

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

свою очередь вызовет другой процесс.

Иллюстрация работы монитора представлена на рис. 2.

Как было сказано, мониторы являются механизмами более вы-

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

для решения одних и тех же задач.

Рис. 2. Работа монитора

В качестве примера приведем реализацию семафора с помощью

монитора.

monitor Semaphore {

int s=0; # s больше или равно нуля

cond pos; # получает сигнал при s больше нуля

procedure Psem(); {

while (s==0) wait(pos);

s=s-1;

}

procedure Vsem(); {

s=s+1;

signal(pos); # запуск самого "старого" процесса

}

Здесь s — целочисленная переменная, представляющая значение

семафора.

Если s=0, то вызов процедуры Psem приводит к приостановке

вызвавшего процесса на условной переменной pos (т. е. процесс

попал в очередь), а если s>0, то вызов этой процедуры ведет к

уменьшению s на единицу.

Вызов процедуры Vsem приведет к увеличению s на единицу

и посылке сигнала на условную переменную pos, который воспри -

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

канале pos процесса).

В случае стратегии “си гнал изи ровать и продолжить” (SC) про-

должается выполнение сигнализирующего процесс а, а очередной (в

канале pos) процесс готовится к захвату позиций (это произойдет

после окончания сигнализирующего процесса).

В случае стратегии “си гнали зи ровать и ждать” (SW) происходит

переход вызвавшего процесса в состояние ожидания, а очередной

процесс (первый в очереди pos) захватывает ресурс и выполняется

сразу, уменьшая значения семафора s.

Замечание. При стратегии SC запускаемый процесс должен пе-

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

ложительно: это необходимо дел ать, поскольку в период времени с

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

жет другой процесс из очереди входа вызвать процедуру Psem и

уменьшить s.

Приведем другой вариант представления семафора с помощью

монитора.

monitor FIFOsemaphore {

int s=0;

cond pos;

procedure Psem() {

if (s==0)

wait(pos);

else

s=s-1;

}

procedure Vsem() {

if (empty(pos))

s=s+1;

else

signal(pos);

}

Примененный метод называется “методом передачи условия” : здесь

в случае операций signal и wait значение семафора не меняется;

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

торый семафор запускает.

Сравним операции wait и P, а также signal и V. Сходство опе-

раций в том, что операция wait аналогично P приостанавливает

процесс, а signal аналогично V его запускает, а отличия состоят

в следующем:

1) операция wait всегда приостанавливает процесс, в то время

как операция P это делает лишь, если значение семафора равно

нулю;

2) операция signal не производит никаких действий, если нет

процессов приостановленных на условной переменной (т. е. факт

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

операция V либо запускает процесс, либо увеличивает значение

семафора.

Замечание. В дальнейшем будем предп олагать, что использует-

ся стратегия SC, т. е. стратегия “сигнализировать и продолжить”

(signal and continue).

§ 6. Операции с условными переменными

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

ными, используемый в дальнейшем.

Все приводимые ниже операции естес твенны и достаточно легко

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

Т а б л и ц а № 1.

К о м а н д а С о д е р ж а н и е к о м а н д ы

wait(cv) Ждать в конце очереди

wait(cv,rank) Ждать в порядке возрастания значения ранга (rank)

signal(cv) Запустить процесс из начала очереди и продолжить

signal_all(cv) Запустить все процессы очереди и продолжить

empty(cv) Истина, если очередь пуста, иначе — ложь

minrank(cv) Значение ранга процесса в начале очереди ожидания