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

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

Каждый из параллельных процессов вычислений ветвей протекает независимо от других и, достигая конца ватан. останавливаетея, ожидая, пока все остальные процессы в сегменте ме достигнут конца сегмента. В конце сагмепэ все процессы "слиеаютея" а пдин. Параллбпьные ветви сегментов могут, в свою очередь, содержать сегменты. 129 Рис. 8л, В последовательно-параллельных языках программирования для выделения параллельных ветвей используются специальные программные прн мнтивы, такие кек скобки параллельности раг)юб)п...

рампб, со)юб)п ... соапб или специальные операторы, отмечающие начало и конец параллельного сегмента. Примером могут служить операторы ттн1с (а, Ь, с,...) и )о)п(е, Ь. с, ...) . Первый оператор открывает сегментс параллельными ветвями, помеченными метками а, Ь, с,..., второй — замыкает сегмент с ветвями, помеченными меткамн а, Ь, с,... На рис.82.а показал пример последовательно-параллельной структуры„изображенной с помощью сети Петри.

Переход г~ интерпретируется как оператор(ог)т (а, Ь), инициирующий две параллельные ветви, помеченные метками а и Ь, переход тт — как оператор (огх (с, т(), переход П соответствует оператору )о)п [с, Ф, переход тю — оператору)щп (а, Ь) . Характерным свойством "чистой" последовательно-параллельной структуры управления является отсутствие каких-либо взаимодействий между параллельными ветвями, переходовскачков из одной ветви в другую. Такие структуры управления обладают существенным недостатком — малой гибкостью управления. В реальных условиях существует необходи.

мость организации взаимодействий параллельно протекающих проны:сов исполнения ветвей. Эти взаимодействия нужны для организации обменов между ветвями результатами промежуточных вычислений и для обеспечения раздельного доступа к общим ресурсам ветвей, таким как общие области рабочей памяти, общие внещние устройства и т.п. Для организации взаимодействий нужны дополнительные программные средства, обеспечивающие саму организацию взаимодействий и правиль. ность их реализации в процессе исполнения параллельных ветвей. В больщинстве случаев нужны средства, которые позволяли бы приостанавливать процесс исполнения некоторой ветви, пока не прибудут данные от 130 другой ветви нли пока лругиа ветви на освободят общий ресурс. Тот отразок ватам, на котором требуется "захват" общего ресурса, называет критическим интервалом ветви.

Дейкстра (32) прадпожил для этих целей механизм семафоров. включающмй спвциальмыв пареманмыа нового типа (саамфоры) и два операции Р и У, аргумантами которых могут быть только переменные типа семафоров. Область значений самафора — целые наетрицатальныа числа. Если область значаний сужама до двух — 0,1, семафор называют бинарным. Опарзция У изменяет значанна з семафора на з + 1. Действие операции Р определяется следующим образом: — если з Ф О, то Р уменьшает значение з на 1, — зепи з = О, то Р на изменяат значение з и на заваршаатсл до тах пор.

пока некоторая другая ветвь на изманит значение з с помощью операции У. Сущаетванным являатся тот факт, что операции Р и У считаются "неделимыми". По отмошамию к У это означаат еладуннцаа. Операция У состоит из трех фраз: — считываниа значения самафора нз памяти, — уваличаниа значания семафора, — помещение нового значения в память.

Неделимость У(з) заключается в том, что с самого начала выполнения этой опарации до аа заваршания доступ к переменной еамафору з запрещен длл асах других опарацмй. Аналогично депо обстоит с операцией Р. Обыч. но Р лрадшаствуат критическому интарвалу ватви, а У заваршаат аго. В каждый момент времени, когда значаниа семафора з изменяется с О на 1, только одна из операций можат заваршиться и разрешить вход в критический интервал только одному процессу исполнания ватви. Ниже следует пример параллальной программы (32) на алголоподобном языке, дополнаммом скобками рвтЬав!и... рагапб, выдаляющими сегмент с двумя параллельными ветвями ргосааа 1 и ргосам 2, раздаланнымн запятой, и самафором титах.

Каждая из параллальных ветвей прадставляат собой посладоватальмый цикл, содаржэщий критический интервал (сплел( аасгюл) и остальную часть цикла (гататг(аг ог сус!а): Ьа(рп мгпа1ога титах; титах: 1; рагЬв()(п ргосам 1: Ьаб(п (.1: Р(титах) ," сг(г(са! засгюл 1; У(титах); 'эгпалкйгг оусус(а 1; Восо 11 апб, ргосаз$2: Ьавт 1.2: РЬпимх); сп'гка! евсг(ол 2; У(титах); тта1лгуаг оу с ус!а 2; бото !. 2 мм1 131 8 этом примере решается зедючэ взаимного исключения исполнения К)ЗИТИЧЮСКИХ ИНТЮРВЭЗЗОВ ДВУХ ЦИКЛИЧЮСКИХ ЛРОЦЮССОВ ПЭ)ЮЛЛЮЛЬНЬ$Х ВЮТВЮй.

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

Наряду с обычным зацикливанием выражений наиболее частыми ошибкеми являются взэимныа блокировки и отталкивания процессов исполнения пэрэллюлзюзых Ветвей. Взаимная блокировка Феюозосх) возникает, например, в следующей ситуации. Пусть дВЕ Ветви А и В требуют при своей работе доступе к двум общим ресурсам. Типичная ошибочная ситуация, в которсх может возник. нуте блокировка, показана с помощью сети петри ню рис. 8.3.

пусть процесс ИСПОЛНЕНИЯ ЕЮТИ А (ПЩЗЮХОДЫ Гы Гз, Гз) ПОСЯЮ ВЫПОЛНЕНИЯ ДЕЙСТВИЯ Гз ЗЭ. хвэтилоДиниз РесУРсов, иэобРюжэемый фишкой в месте Рт, после чего МЕСТО Рт ИМЮет РаЗМЕтКУ О. ПРОЦЕСС ИСПОЛНЕНИЯ ВвтВИ В (ПЕ)ЗЮХОДЫ Г„, Гз, гз) после Выполн6ния дэйстВиЯ гч эюхвэтил дРУгой РЮОУ)ю(место Рз им66т РЮЭМЮТКУ О) . Обэ п)зоцэссэ Оетзноэнпись, А аюрвп Гз.

В пцзэд гз, тэк «э« для выполнения следующих действий каждому из них нужен второй ресурс, захваченный партнером. При этом ни один из процюссоя ню мо. жег вернуть захваченный ресурс. Ооэниклэ блокировка, показания нэ рис. 83. Характерной зюдэчюй, неправильное рмпение которой может привести кэк к блокировке, тек и к оттэлкивэнию, является зэлзчэ о пяти обедающих философах )33), Рассматриваемая ниже в % 8.3.

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

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

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

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

Событием может быть инициирование или завершение какого-либо оператора программы (программные события), прерывание в системе мли сигнал. об освобождении некоторого ее ресурсе (системные события) . Прн потоковом управлении ллйствие (оператор или операция) программы может выполниться, если готовы все необходимые для него аргументы (операндь ) .