Книжка по сетям Петри, страница 35

Условие готовност~ в этом случае носит стандертный характер и не выписывзется явно в программе, а неявно подразумевается. В обратном потоковом управ~юноа действие может выполняться, если его реэультет необходим в качестве аргумента лля некоторого другого действия. В этом случае второе действие кзк бы вызывает первое в кача:тве процв- АУРЫ. В динамическом уп)ззелвнии условие готовности является логическим выражением, зависящим от переменных той же пзмяти, мед которой определены операторы программы.

Ниже мы рассмотрим более подробно особенности событийного и пото. каната асинхронного управления. Их семантика удобно и наглядно описывается в терминах асинхронных сетей — сетей Петри и их модификаций. При агом специфика определенного типе управления будет в основном отражена в интерпретации переходов, мест и фишек сетей. В реальных программах события могут иметь различный характер. Мы ограничимся единственным типом событий — завершениями действий, а под действиями будем понимать исполнение операторов программен В этом случае семантика событийного управления может быть представлена с помощью сети Петри, элементы которой интерпретируются следующим образом.

Переходам сопоставлены операторы, места хранят информацию о событиях. Событие может не произойти, произойти, повториться. Соответствующее место на имеет фишки, имеет одну фишку или несколько фицюк. Условие срабатывания перехода трактуется как усвюие готоаности соответствующего оператора. Срабатывание перехода изменяет разметку его входных мест, и тем самым формируется информация о происцюдшем событии — исполнении соответствующего оператора.

Механизм событийного управления, базирующийся на формализме сетей Петри, позволяет описывать более сложные управляющие ситуации, чем механизм последовательно-параллельного программирования с семафорами, и, следователыю, порождать более богатые множестве эквивалентных вычислительных процессов. Так, на рис. 8.4 представлена с помощью сети Петри схруктура управления, которую не удается запрограммировать с помощью обычных семафоров без использования искусственно введенных условных операторов [681.

В этом примере каждый из трех операторов 113, где У 1, 2, 3, может выполниться только после того, как выполнятся операторы. гт2 и М2, гдето=1,1 =2 для ('= 1,г'=1,1г 3 для 1 2 и/ 2, Д 3 для! 3. Причина, по которой с помощью семафоров нельзя запрограммировать такую структуру управления, состоит в том, что неделимая операция Р применяется только к одному сеьюфору. Для того чтобы аппарат сетей Петри применять не только для описания семантики событийного управления, но и непосредственно использовать в языке параллельного программирования, разработаны аналитические методы представления сетей, которые позволяют задевать струк.

туру асинхронного управления программы в виде управляющих выражений. Эти выражения трактуются как формулы алгебры регулярных и иерархических сетей, рассмотренной в главе 6. Управляющие выражения воспринимаются управлением системы, исполняющей программу, и управление оргагл низует вычислительный процесс, задаваемый этим выражением. При интерпретации иерархических сетей простым переходам сопоставляются простые, неделимые операторы, состав.

ным переходам — составные операторы. Места интерпретируются как переменные события 1управляющие переменные!, а ус. ловия срабатывания переходов — как условия готовности операторов. Исполнение иерархически организованной асинхрон~зч ной программы с событийным управлени. ем можно представить как работу рекурсивной процедуры исполнения составного оператора. При включении оператора генерируется локальная кОпия этой процедуры. работа которой сводится к проверке л с, а.е. условии готовности пассивных внутрен- 134 них операторов. Каждая такая проверка инициируется некоторым событием, например, заверцюнием оператора.

Завершение оператора про. исходит по там же правилам, что и завершение составного перехода в иерэр. хичэской сети с ожидэниам. 9 8.2. Потоковые сетя Если в событийном асинхронном управлении условия готовности привязаны к управляющим событиям, то в потоковом управлении они изменяются исключителыю под влилниам потоков данных, которыми обмениваются операторы (или операции) . Исполнение оператора может начаться, если для этого оператора готовы входнью даннью (аргументы).

Для того чтобы обнаружить наличие или отсутствие данных лля операто. ра, необходима память "болев активная", чем обычная адресуемая память прямого доступа, в которой любая ячейка (переменная) общедоступна (не резервирована для определенных операторов) и всегда содержит неко. торую "обезличенную" информацию беэ указания истории ее получения и каким операторам она предназначена.

Поэтому в потоковых асинхронных прогрмимах используется понятие распределенной памяти, состоящей из элементов специального типа — очередей (каналов). Каждая очередь приписана некоторой группе операторов, и указывается, какие операторы могут записывать в очередь и какие считывать из нее. Обычно ограничиваются одной парой операторов — эаписываощим и считывающим.

Функционально очередь представляет собой элемент памяти ограниченной или неограниченной еикости, хранящий в каждый момент времени строго упорядоченную последовательность данных (возможно, пустую). В последовательностивыделяется первый элемент (голова очереди) н последний элеиент (хессг очереди). Любая запись данного в очередь увеличивает ее длину нэ 1, и вновь записанный элемент становится последним (зались в хвост сче(юди). Любое считывание данного уменьшает длину очереди на 1, первый Злемент удаляется из очереди, а второй становится головой очереди. Считывание возможно, если очередь непуста. Запись возможна, если очередь имеет неограниченную емкость или число данных в очереди меньше ее емкости. Предполагается, что информацияосостоянии очереди (пуста, непуста, переполнена) всегда доступна управлению.

Введение распределенной памяти, состоящей иэ очередей, позволяет конкретизировать условия готовности операторов в потоковом управлении: оператор можно исполнять, если каждая его входная очередь (ипи определенная часть входных очередей) непуста. Иногда требуется, чтобы входные очереди содержали не менее некоторого, указанного для данного оператора, числа данных. Иногда добавляется дополнительное условие, чтобы выходные очереди были пусты или не переполнены. В литературе рассматривались различные варианты программного представления потоковых асинхронных вычислений и архитектуры потоковых вычислительных машин (31) .

Выше было показано, что механизм событийного асинхронного управления описывается в терминах сетей Петри, э для того, чтобы ээпрогрэм. мировать его, можно использовать управляющие выражения, основанные на алгебре регулярных и иерархических сетей. Семантику потокового управления также можно описывать в терминах сетей Петри, более того, можно использовать модификацию алгебры регулярных сетей и с еа помощью программировать асинхронные потоковые программы.

Назовем логоковыаш сетлмь интерпретированные регулярнью сети, в которых 135 переходы интерпретируются как операции (функции), места — как очереди, а фишки — как данные. Дополнительно принимаются еле. дующие соглашения: переход с л входными местами (места угюря. дочены) может интерпретироваться только л-местной операцией; имеется неявный, скрытый механизм организации очереди данных фишек в каждом месте. На рис. З.б показаны три потоковые сети, задаваемые следующими формулами и интерпретирующими функциями, которые сопоставляют каждому переходу некоторую операцию: а1 1((тз, гз ).

гэ. (гг, г4). гз ). гз. lз(гз ) = а, У, (г,1 Ы, (тэ) =+, Iз(тч) = С,!з(тз) = Х,(з(тз) = 6) 1((гз,гз):гз. (г,,г,);г,);г,. !з(гз)'-а,)г(тг) ь.!з(гэ1 — +.(з(г4) с. (, (тз ) = зг, !з (г, ) = +, !з (г, ) = +. в ) 1 (((го гз 1 гэ, гз ); гз, гз ); гт .

(э (гз ! = а. !э(гз ) = Ь. (э(гэ ) = + !э (гз ) с, (э (тэ ! = +. Гэ (ге 1 = тт. lэ (гт 1 = + Здесь символы +, Х, +обозначают бинарные операции сложения, умно- жения и деления нацело. Символы а. Ь, с, зз обозначаот одноместные кон- стантные операции, которые для любого аначения аргумента вырабатыва. ют одно и то же значение, равное соответственно а, Ь, с или з( (т.е. зтх, а(л! =ли т.д.). В потоковых сетях операция, соответствующая переходу, может ис- полниться, если данныефишки присутствуют во всех входных местах перехозю.

После исполнения операции результат вырабатывается в таком числе экземпляров, каково число выходных мает.очередей у соответствую- щего перехода, !за Если подставить вместо символов переходов в формуле потоковой сети символы интерлретнрующих их операций или функций, то получится потоковое управляющее выражение, составленное из интерпретирующих операций н операций управления. Одна н та же ннтеряретируюцюя опарация может подставляться вместо разных переходов. Условимся отмечать дополнительными индексами вхождения одной и той же операции, сопоставленной резным переходам. Это позволит избекать слияния равных переходов в адин при построении сати по потоковой формуле. Потоко.