В.Ш. Кауфман - Языки программирования - концепции и принципы (1990) (1160787), страница 65

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 65)

драйвер(верх[корень], низ[корень])

par i = первый.узел for число.улов

узел(верх[i], низ[i], верх[2*i+1], низ[2*i+1],

верх[2*i+2], низ[2*i+2])

par i = первый.лист for число.листьев

лист(верх[i], низ[i])

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

замысел, сосредоточившись на каждом виде процессов. При этом каналы

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

Объявления процессов. Основной процесс-сортировщик (узел) легко

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

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

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

сверху.

proc распред(chan of пары низ, лево, право) =

-- по каналам-параметрам "низ", "лево", "право" передаются

-- пары (bool; real), в соответствии с протоколом "пары"

val bool влево is true,

bool вправо is false :

bool направление, еще :

seq

направление := влево

низ ? еще

while еще -- цикл до конца потока

real число :

seq

низ ? число

if направление = влево

лево ! true; число -- выдать пару

направление = вправо

право ! true; число

низ ? еще

направление := not направление -- смена направления

par

лево ! false -- признак конца потока

право ! false :

Комментарии, по-видимому, излишни.

proc слияние(chan of пары низ, лево, право) =

bool лево.еще, право.еще :

real левый.мин, правый.мин : -- минимумы

seq

par

лево ? лево.еще; левый.мин -- ввод парами

право ? право.еще; правый.мин

while лево.еще or право.еще

if лево.еще and -- так можно прерывать строчку

((not право.еще or (левый.мин < правый.мин))

seq

низ ! true; левый.мин

лево ? лево.еще; левый.мин -- ведь предыдущий не

-- последний

право.еще and -- вторая альтернатива if

((not лево.еще or (правый.мин < левый.мин))

seq

низ ! true; правый.мин

право ? право.еще; правый.мин

низ ! false; any -- "заполнитель" для нормального

-- конца (см. ввод по каналу "низ")

proc узел(chan of пары снизу, вниз, влево, слева,

вправо, справа) =

par

распред(снизу, влево, вправо) -- взаимодействие

слияние(вниз, слева, справа) : -- через потомков

proc драйвер(chan of пары верх, низ) =

real число :

seg

seq i = 0 for колич.чисел

seq

число := создание.чисел -- какая-то процедура

верх ! true; число

верх ! false; any -- посылка "звонка" о конце работы

-- согласовано с приемом в процессе "узел"

seg

seq i = 0 for колич.чисел

seq

низ ? any; число -- чтобы "съедать" булевы

обработать.(число) -- обработка чисел

низ ? any; any -- "съедание" признака

-- конца (получение звонка об окончании работы)

proc лист(chan of пары верх, низ) =

real число :

seq

верх ? any; число -- прием пары

низ ! true; число; false; any -- поворот потока

-- и посылка звонка

верх ? any -- прием звонка и сразу конец

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

для того, чтобы не мешать работе связанного с ним узла (см. ниже).

17.7. Завершение работы коллектива процессов

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

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

любому нарушению нормального режима работы. В частности, неосторожное

завершение работы некоторого члена коллектива (например, в момент, когда

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

к "зависанию" членов коллектива, ожидающих несостоявшихся рандеву.

Например, представим себе, что драйвер (подходящим образом

модифицированный) обнаружил в потоке недопустимый объект. Ему нельзя просто

выдать диагностику и завершить работу. Ведь взаимодействующие с ним

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

возникнет тупиковая ситуация (которая может коснуться неограниченного

количества процессов). При этом на выходе драйвера (по каналу "низ" в общем

случае не будет получена даже та часть потока, которую удалось нормально

отсортировать (так как она "застряла" в процессах-узлах).

Основной тезис таков: следует считать, что на каждого члена коллектива

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

информировании партнеров о предстоящем завершении работы. Это естественная

плата за параллелизм (и простоту каналов как средств взаимодействия).

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

корректном завершении работы с каждого партнера.

Подсказка. Конечно, такой механизм должен использовать специальный

сигнал завершения работы, "понимаемый" всеми партнерами.

Опишем вариант правильной стратегии поведения процессов. Процесс,

решивший закончить свою работу, должен:

1. Передать потенциальным партнерам (т.е. партнерам, с которыми еще

возможно содержательное взаимодействие) сообщение со смыслом "заканчиваю".

2. Получить от всех потенциальных партнеров сообщение со смыслом

"услышан" (это может быть, например, также сообщение "заканчиваю", но

полученное от процесса, который перестает быть потенциальным партнером после

передачи такого сообщения).

3. Не заказывать рандеву с процессами, приславшими сигнал "услышан".

4. Закончить работу.

Таким образом, сообщение "заканчиваю" дает возможность партнерам

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

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

больше не будет.

Конечно, в некоторых случаях эту стратегию можно упростить. Например,

если в процессе нет приема, то ему можно завершать работу сразу после своего

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

"заканчиваю" от всех потенциальных партнеров.

В нашей сортировке сообщение "заканчиваю" представлено передачей

"false". Драйвер, выступая инициатором завершения, посылает вверх "false" и

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

пока не получит "false" сверху. Процесс-узел, со своей стороны, сначала

посылает сообщения "заканчиваю" своим потомкам, а завершает работу лишь

после получения "false" от потомков и его передачи предку.

Несколько дополнительных вопросов.

1. Почему в драйвере внешний комбинатор "seq"? Что изменится, если

поставить "par"?

Логически ничего не изменится, так как второй seq сможет что-либо

получить по каналу "низ" только после посылки "false" по каналу "верх".

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

Дело в том, что переменная "число" формально станет разделяемой между

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

процесс получит доступ к ней строго после первого). Это противоречит

принципам Оккама и вызовет соответствующую диагностику компилятора.

2. Можно ли первый вложенный "seq" в драйвере заменить на "par"?

Нельзя из-за разделяемой переменной "число".

А если ее объявление поставить перед самым внутренним комбинатором

"seq" (т.е. сделать ее локальной внутри следующей конструкции)?

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

параллельными процессами. Однако остается нарушенным еще один принцип

Оккама: один канал "верх" не может обслуживать более двух асинхронных

партнеров! Остается и содержательное возражение - потребуется синхронизация

запусков процедуры создание.чисел (зачем?).

Итак, каналы Оккама отличаются от симметричного рандеву только тем, что

каждый канал статически закрепляется за вполне определенной парой партнеров.

Модификация семантики небольшая, однако становится существенно проще

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

17.9. Сопоставление концепций параллелизма в Оккаме и в Аде

Основное отличие концепции параллелизма, принятой в Аде, от концепции

Оккама состоит в том, что если в Оккаме асинхронный процесс - обычная

(рядовая) компонента программы, то в Аде каждый асинхронный процесс -

объект, требующий специального объявления.

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

как компоненты иерархии действий, а в Аде - как компоненты иерархии объектов

определенных (а именно задачных) типов. Специфика задачных типов и

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

В конечном итоге и в Оккаме (как было видно) можно объявлять

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

завершением процессов. Однако исходная концепция существенно влияет на

выбранные для этого авторами выразительные средства.

Постараемся показать это на примере описания на Аде коллектива

процессов, преобразующих координаты векторов. Главная наша цель -

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

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

Аде, а затем перейдем к программированию.

17.9.1. Концепция параллелизма в Аде

Итак, прежде чем иметь дело с асинхронным процессом в Аде, его нужно

определить посредством объявления задачи. Примером может служить объявление

задачи "буф", приведенное в качестве описания монитора Хансена-Хоара. Оно

состоит из спецификации и тела задачи. Спецификация содержит только

объявления входов, т.е. названия видов рандеву (процедур-рандеву),

предоставляемых в качестве услуг клиентам процесса "буф". Тем самым

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

(обслуживающим процессом), что не мешает ему выступать клиентом в других

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

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

называемого предвыполнения (обработки) этого объявления и выполняется

асинхронно с запустившим его процессом (среди объявлений которого находится

рассматриваемое объявление задачи). Запустивший процесс называется предком,

а запущенный - его потомком. Точнее говоря, одновременно запускаются все

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

[В Аде предусмтрены исключения, возникающие при попытках заказать

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

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

рандеву между собой, не опасаясь попадания в аварийные ситуации.]

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

когда выполнится оператор terminate (внутри процесса) или abort (вне

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

Объявления коллективов процессов. Объявление задачи "буф" представляет

лишь один вид объявления. В этом случае формально считается объявленным

анонимный задачный тип, единственным объектом которого и считается

объявленный процесс (в нашем случае - "буф").

Однако в общем случае можно объявить именованный задачный тип и затем

объявлять отдельных его представителей обычными объявлениями объектов (этого

типа). Например:

task type буф is -- добавлено слово type

entry поставить (X : in сообщение);

entry получить (X : out сообщение);

end буф;

task body буф is

. . . -- тело совершенно то же

end буф;

. . .

A, B : буф; -- обычное объявление двух объектов

При обработке такого объявления создаются и одновременно запускаются

два процесса А и В типа "буф". Клиенты могут воспользоваться услугами

"мастеров", заказывая соответствующме рандеву посредством вызовов входов

А.поставить(Z1); В.поставить(Z2);

В.получить(Y1); А.получить(Y2); и т.п.

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

записях. Вызов входа - аналог выборки поля записи. Это характерная операция

для задачных типов. Но в определяющем пакете для конкретного задачного типа

можно объявить и иные операции (использующие в качестве элементарных вызовы

входов). Например, операцию "передать слово", использующую вызов входа,

аботающий с одним байтом. Все это дает основания считать задачные типы

полноценными (ограниченными приватными!) типами данных, причем данных

активных (а не привычных пассивных).

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

Аде), становится естественным строить из них структуры, в частности, массивы

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

Например, можно объявить тип - массив буферов

type масс_буф is array 1...10 of буф;

и конкретный массив этого типа

М : масс_буф;

Характеристики

Список файлов книги