Книжка по сетям Петри (547616), страница 37
Текст из файла (страница 37)
Унарныа операции (итерация и разметка) "просачиваются" лри применении их к векторам и матрицам из операторов и сетей до скалярных элементов. Например, формула ((е, Ь), (с, д)! Н.э, .Ы, (юс, чн)) задает матрицу 2 Х 2 из сетей вида к, где х = а или Ь или силн д. Бинарные операции обобщаются на случай векторов сетей за счет ассоциативности этих операций. При таком обобщении удобней испольэовать префиксную Форму операций над сетями, поэтому изменим обозначения бинарных операций на более наглядные обозначения следующим образом: символ, наложения заменим на символ гз, символ; присоединения заманим на симвоп~, символ ((' исключения заменим на символ ТГ.
Тогда Иа, Ь, с, т() (а, Ь, с, а, ) (а, Ь,с, гг) (е;Ь;спз), Ч (д Ь, с, г) - (а (( Ь з с 1 у) . Иб Бинарные операции распространяются на случай матриц по слвдуквцвму правилу просачивания: матрице, к которой приманена бинарная операция, трвнспонируется, после чего операция применяется к канвой из векторных строк. Например, Ч([в.
Ь), [с, дИ [Ч(в, с), Ч [Ь, Ф . 8 данном случае результатом применения операции исключения к матри- це 2Х 2 из элементарных сетей является вектор из двух сетей, задаваемых формулами Ч(а,с) и Ч(Ь,И) (или (э1с) и (Ь 3Ф). Для распространения функций управления на случай, когда формаль- ный параметр можат заменяться составным значением, также использу- ются описанные выше ярввила просачивания. При этом возможность за- мены формального параметра составным значением дает воэможность задавать "динамические" типы управления: пштех (тесх) =1 ° Чх, где теск означает, что функция непосредственно применима к векто- ру операторов. Теперь можно исяользоввть тип пхпех в формуле управления титек ([э, ЬИ. которой вектор (д Ь! — фактический параметр [пера операторов) Эта формула эквивалентна формуле управления 1 "Ч(а, Ь), т.е.
формуле, стоящей в правой части описания типа пиках 2. Аналогично формула пщтех ( [а, Ь, с) ) эквивалентна формуле 1 ° Ч (э, Ь, с!. Если вместо формального парэметравекторв подставляется фактический параметр. матрица У=(2,,..., 2»), гдето; — вактор, то функция пнзтех применима к нему, но только после предварительного унврного просачивания функции по слвдующему правилу: гпигех(У) = пщтех[(2ы..., »»И" ( пщтехК,),..., литах(2„И. Пусть динамический тип управления описан следующим образом: рагех (тесх,часу)" ! Ь[ ох,чту. Ь» Ч(х, УИ. формула рагех ((в, ь,с), (гт, е, УИ задаетследующуюструктуру: рэгех Ив, Ь, с), (с[, в, У)) = =1Ь[ цэ,ь,с], ~[г)е, У),Ь" Чца,о с], Ие,гИ) = 1 Ь( и[а, Ь, с); и[о, в, г). д [Ч(э, гт), Ч (Ь, е), Ч [с.
г!)) = 1 ь К[в ь с), з (Ф е, У), ь [" Ч (а, с[), " Ч [ь в), » Ч (с, У] И = = 1 ((в;Ь;с), И;е,'1), [а [) Ф, * (Ь []е), (с, О!. Рис.' 8.8. Двумерная сеточная структура с переменным числом операторов по обоим измерениям может быть определена с помощью следующего типа управления: ! асйсе (матт х ) = 1 зз (Ь'Цх, Ь'3 тх ). Для случая матрицы 3 Х 3 структура управления показана на рис.
8.11: !а!Все ((а, З, а!2, а!э ), (ез ! ° а22, 3! 3), (аз!, аэз азз)) = 1 й (зз«2((а! З, а! 2, а! 3 ), !аз З, а2 2, а2 3 ), (аз ! аз 2 аз 3 )) ~~((а! !,аз !.аз!). (азз.езз.азз). (а!э,азз,азз)И = = 1 Д (Д («З(а... а,, аз ! ). «3 (а ! 2, аз 2 аз 2 ), «3!е ! з аз з, аз з ) ) («2(а! ! а! 2 а! 3) «з(аз! е22,а32 ),«3 (аз!,а32, езз))) = 1 ((а! З,Э2 !,аз! ), (азз,а22,ВЗ2). (а!э,а2э,'езз), (а! ! а!2,а!3) (а2 ! а22,а23), (аэ! а32 ~азз) ) ° Программируемые типы управления дают возможность конструировать разнообразные структуры управления. В частности, техникой типов уп. равнения удобно описываются многие известные управляющие конструкции последовательных и параллельных языков.
После того как программист описал набор "абстрактных" типов управления и проверил их пра- Ь 6 с) л, вл!. б) Рис. 8.10. Соответствующая сеть показана на рис. 8.9. Для функции управления зацех (виг х) = 1 цЧх, где гяатг указывает, что зта функция непосредственно применима к матрица операторов, структура управления, задаваемая формулой зецех ((а, Ь, с), Иге, О) = 12 Ч((а, Ь, с), (ЗУ, е, Ц) = = 1 ~ ( Т(а, ЗГ), Ч(Ь, е), Ч (С Ю = 1 (а 1 д); (Ь )( е); (с )) у! ), . показана на рис. 8.10, а. Структура управления, задаваемая другой формулой, которая использует тот жетип управления зецех, показана парис. 810, б: зецех ((а, Ы, (с, г)), (е, К)) = 1~Ч ((3, Ы, (с, 8), (е, У П = = 1 з(Ч(а, с, е), Ч (Ь, 3(, 1П = 1 (а 1 с () е); (Ь () ЗГ () О.
Рис. 8л2. вильность, он может с их помощью конструировать конкретные структуры управления в программах. Рассмотрим в качестве примера, илжострирующего возможности про. граммированиястипами управления, каким образом можно спепиФици. ровать структуру управления параллельной программы, решающей известную задачу о пяти философах [33) . Пять философов гуляют в саду и размышляют. Когда философ чувст.
вует, что проголодался, он заходит в столовую, где стоит круглый стол с пятью стульями и миской спагетти посреди стола. На столе — пять вилок, по одной слева и справа от каждого стула'. философ садится за стол, берет вилки (если они на месте) и ест спагетти (для етого обязательно нужно две вилки) . Утолив голод, философ кладет вилки на стол и выходит асад размышлять, пока вновь не почувствует, что проголодался.
Задача состоит в том, чтобы синхронизировать независимые действия философов и не допускать взаимной блокировки, когда все философы сидят за столом, каждый взял по одной вилке и никто из них не может начать есть спагетти. Решение задачи — не позволять всем пяти философам одновременно находиться в столовой. Пусть набор действий всех пяти философов представлен матрицей РН размерности 5 Х 7, в которой 1-я строка РН[1, ! соответствует действиям Дго философа.
Каждый из философов выполняет семь действий, обре. зующих следующий вектор операторов: РН[1;) = РН[1, 1] (философ 1 входит в столовую), РН~~, 2] (философ1 берет левую вилку), РН[1, 3] (философ1 бррет правую вилку), РН[1, 4] (философ 1 ест спагетти), РН[1, 5] (философ1 кладет левую вилку), РН1~, 6! (философ 1 кладет правую вилку), РН[1, 7] (философ 1 выходит из столовой) . Для программирования задачи о пяти философах сконструируем сле- дующие типы управления: аст (еес Х) 1 З (Х[1], гз (Х[2], Х[3]), Х[4], тЪ (Х[б], Х[6], Х[7! ), $43 При замене формального параметра-вектора Х строкой матрицы РН фор. мируется сеть, описывающая поведение одного философа.
При замене параметра Х матрицей РН функция аст просачивается, так что результатом выражения аст (РН1 является вектор из пяти сетей, описывающих поведение философов. Наконец, формула управления д аст (РН1 задает параллельную структуру управления (сеть), показанную на рис. 8.12. Эта структура описывает независимые параппальнью действия филгсофов. Лля вектора длины 7 следующая функция Ног(4 вьцюляет его "критичцский участок". Если вместо Х подставить вектор РН[ )], то этот участок Включает последовательность действий философа (, при которых он использует левую от него вилку: Ногй (тес Х) =ч) (Х(2], Х[4], Х[б]1.
Аналогично функция г(ог)г будет использована для выделения критического участка, связанного с использованием философом правой вилки: г(ог)г (зесХ) = ~(Х(3], Х(4), Х(6]). Вспомогательная функция зл)(т осуществляет циклический сдвиг вектоРа длины б: тп)(т(еесХ) = У, где У[г] =К[(/+ 1) пнн) б], г' 1, ..., б. Тип управления рагпштех (час Х, еес У) Ы1 *9 (Х, У)! задает покомпонентное взаимное исключение элементов векторов Х н У. Тогда формула управления Ь рагпштех(Иог(с(РН), з)нбт(г(ог)с(РН) ) ) задает структуру управления, показанную на рис. ВЛ 3. Эта структура указывает, что каждая вилка является общим ресурсом для сидящих рядом философов, и исключает возможность одновременного исполнения ими действий, для которых требуется вилка. Наконец,тип управления (ош(чесХ) = (4 «К) разрешает параллельное исполнение не более четырех операторов илн сетей нз вектора, подставляемого вместо Х.
Поэтому формула управления Ь Еоиг (ест(РН1 ) указывает, что не более четырех философов может одновременно находиться в столовой. Теперь остается методом поспедова. тельного наложения отдельных слоев записать результирующую формулу управления, задающую структуру уп- Рис Е.13. 144 равлення па1иллельной программы, которая (ххпает задачу о пяти философах: (Ласт (РН(. Ь раппцтех (((огц [РН((, тЫ(т (г(от(с (РН((,й(оцг (аст (РН)И. Соответствующая сеть показана на рис. В.14. 3 8.4 Петри-машина регулярные и иерархические сети, представленные формулами, можно "обрабатывать" с помощью ЭВМ.
Такая обработка может включать преобразования сетей, их оптимизацию по заданным критериям, моделирование их функционирования. Конечной целью программного представления сетей является применение их как компонентов систем программирования, ориентированных на описание и моделирование параллельных структур. Примером программного имитатора иерархических сетей с ожиданием может служить так называемая Петри. машина [Ц, которая строит по заданной формуле иерархическую сеть с ожиданием и имитирует ее функционирование.
Петри-машина является основой интерпретатора управления для асинхронных параллельных программ. Петри-малина состоит из четырех блоков: — блок операций реализует операции над сетями, 1ЕЗ вЂ” блок развертки строит внутреннее предсчавление сети в форме так пазы ваеьюй развернутой сети, — блок ввода осуществляет ввод формул и построение развернутой сети с помощью первых двух блоков. — блок имитации моделирует функционирование сети.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
