Книжка по сетям Петри (547616), страница 33

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

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

7.16.а показан пример ОС.сети. Из определения ОСсати видно что она представляет собой наложение на Обметь "синхронизирующей" сети специального вида, а которой множество мест совпадает с множеством Р„каждый выходной переход места.ресурса Р ирг является началом не- 12$ д (7) д> Эьь 7,16 к еоп у ° 3 Р Е Рг» Э ! ы Iт ~ Ия .

к Е. !, Л у Е (т Л ! I„ lт 1Р, ксоу ч" Мх![у~/язепу[Их у[, Таким образом, отношение Повязывает те и только те элементы ОС- сети, которыа соединены некоторым путем в подсети действий ГУк. Отно. шенка еоп свпзыаазт те и только те элементы, которые принадлежат двум разным критическим интервалам по некоторому ресурсу из Р,. Отношение ео связывает те элементы. которые не соединены никаким путем в подсети [ух [но нх может соединить путь в сети гу, проходящий через некоторый ресурс! н они не принадлежат разным критическим интервалам по вобо. му нз ресурсов из Р,.

которого интервала в О сети, с с, с, длл этого переходе имеется парный входной для Р паре. ход, который служит кон. цом этого интервала. На рис. 7ДЕ, б и е показано ! ° разложение ОСсети не со. стзаляющую ОС.сать и синхроннзнрующую сеть. [Олег, с, рация наложения была вве. дана в главе б длл конечных с, С д ! сетей, Мы уже отмечапн, Ф) что она естественным обра- зом может быть расширена д на случай басконечных се. тей,! !» Если а разных интерва. лах их начале являютсл вы* ходными пере хода ми дпя некоторого ресурса, а их концы - входными длл то. го же ресурса, что зти интервалы будем называть критическими интаразлами по данному ресур. су. Если [! ы..., l„! — множество интервалов, каждая пара которого является ~арой критических интервалов по ресурсу Р, то будем обозначать этот факт следующим образом: 3 lы ..,, !„1Р, Единстванным ресурсом в сети [у на рнс, 7 7, а служит мастер,з.

Интер валы г[г»„гт!. [[ты г,! и[[ты гт! -критичаскиеннтераалы гюр,ь. Свяжем отношения, с помощью которых в % 7,! ввалилось понятие лераплепьного ~роцесса с конкуренцией, с отношениями в ОСюетях. Как обычно, действия представлены переходами, а изменения условий - масте. ми, не явллющимися ресурсами. Таким образом, мастзресурсы играют вспомогательную роль и не интерпретируются как изменанил условий. Поэтому, если длл остальных мщт ОСсети остаетсл актуальным правило. требующее, чтобы место изменлло свою разметку лищь один раз, на расур. сы это э!завило не рэссззострзняется. Отношенил Ф,.со и соп следующим образом аыражаютсл через сетевые отношанил, Пусть [у [Ря О Р,, Т, Ри о Р,, дгь! — Фсеть. ° элементы х и у принадлежат множеству Хх Рс О Т: х й у» [хРсуЧуГди[Ч[х у[, В случее ОСсетай также возникает вопрос, аспкая лн ОС сеть лалпетсп корректным представлением параллельного процасса с конкуренцией.

Рассмотрим ОС сеть /У, показанную на рис, /.16 а, В этой сети имертся дае критических интервала /(г„г,(и /(г„г,! ло ресурсу рь н два критических интервале /(гы гз! и /(гы гт(по ресурсу рю. Эта сеть полностью соотаетст. вует определению ОСсети. В ней имеютсп последовательные переходы (например, г~ 6 гз, Гт 6 Гч(, параллельные переходы (например, г~ со гч, гз соте),и конкУРнРУющнепеРеходы (напРнмеР/П солгз,г( еопге,гз соя гч(, Однако при работа сети /У может возникнуть ситуация.

показаннап не рнс. 7.16,6, когда ни один нз переходов гы гз, гы гь не может сработать. Это означает, что пцзачисланные переходы соответствуют действиям, которые могут не реализоватьсп, что аротиаоречнт опредапанню параллельного про. щюса с конкуренцие», а котором любое дайстаиа происходит ровно один раз. Причина возникновенил такой ситуации состоит ° том, что интервал /(г, гз) н /(гы г~) пересекаютсп по пцзеходу гы а интервалы /(гч,гт) и /(гы гч( пересекаются по переходу гы Прн этом мрасечание устроено таким образам, что лерасекеющиася две пары интервалов являются критически.

ми по разным ресурсам, и начало интервала /(гы г~) входит ° интервал /(г,,/з) как анУтРанний (не начальный) паРахсд, а начало интеРвала /(гз, гч1 выходит в интервал /(гч, г,( как внутренний переход. Мы ограничнмсп введением ОСсетей как сетевых прадстаалени(( ларзл. лельных процессов с конкуренцией, на обсуждал нх сален с сетлмн Петри, моделирующими системы, которые порождает такие процассьь ГЛАВА 8 СЕТИ ПЕТРИ И ПРОГРАММИРОВАНИЕ Среди приложений теории сетей Петри к задачам моделирования дис. кратных аистам наибольшее развитие получили работьь свяэаннью с попытками использовать аппарат сетей Петри, их модификации и обобщения, для описания н изучения структурной динамики программ, в первую оче.

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

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

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

ется исполнаниам звкаочительного оператора. Псслвбоеэгепьнал структуре улрееленшт может быть представлена кек связнап автоматная сеть Петри (см. э 4.2) с определенным топологнческим ограничением, зламанты которой интерпратнруютсл специальным образом. 12$ )Вакая сеть ммвэя единственное головное место, все ве переходы деются вю "'безусловные" .е одним выходным местом и "условные" с двумя выходю(ыми меетвии. Кюхдь)й "безусловный" переход сети интерлретируател как безусловный оператор, каждый "условный" переход интерпретируется как усповмый оператор. Если в последовательной программе оператор е' следует за оператором а, то в сети соответствующие переходы связаны дугами с общим настом, которое является выходным для а м входпым для а.

Например, структуре управления следующей программы (вычисление фзкториагв) представляется с помощью интарпретированной сети Патри, изображенной на рис. 8,1: Ьеа)с )птебвг к, у: йрит(к); 1 ) 1: Ф х * О Фея дою» ) 2; у:~уХх; х: х — 1; бото! 1; ! 2; оигрит(у) этор аяд П ходы в интерпретированмой сети изображены прлмоуг внутри которых выписаны сопоставленные парююдеээ р щжнап сеть не рис.

8,! оямсыеает только структуру ~ ~алания, но не молапирует сам механизм управления' Д но, в терминах сети Патри нельзя описать сементмку условного оператора (см. главу б) . Поэтому, когда место рч получает фижму, то эта фищка сообщает лищь о том, что условный опаратор аыполнилея, но не несет информацию о вычисленном значении условия. В результате выбор опарэтора для яродолжения исполнения последовательной программы моделируетсп е сети медетарммнированной альтернативой (оператор оигриг (у) или оператор у: - уХк), указываощай оба возможных варианта продолления. Для того чтобы иметь средства модапировамия условного управлепе, достаточно вы.

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

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