гуд работа. Курс лекций теория вычислительных процессов
 Скачать 1.54 Mb.
|
|
Определение. Сеть Петри есть двудольный ориентированный граф. Напомним, что двудольный граф - это такой граф, множество вершин которого разбивается на два подмножества и не существует дуги, соединяющей две вершины из одного подмножества. Итак, сеть Петри - это набор N = (T,P,A), T ∩ Р = Ø, где Т = {t 1 , t 2 , ..., t n } - подмножество вершин, называющихся переходами; Р = {p 1 , р 2 , ..., p m } - подмножество вершин, называющихся местами; А ⊆ (T×P) ∩ (P×T) - множество ориентированных дуг. По определению, дуга соединяет либо место с переходом, либо переход с местом. Пример 1 На рис. 10.3,а приведен пример сети Петри в графическом представлении. Переходы обозначены чер- точками, а места - окружностями. Каждый переход t имеет набор входных in{t} и набор выходных out{t} дуг. Сети Петри могут представляться также в форме продукционных правил (рис. 10.3,б). Наиболее интересны сети Петри тем, что они позволяют представлять и изучать в динамике поведение системы параллельных процессов в программе или в любом другом дискретном устройстве. a б Рис 10.3 10.2.2. Разметка сети Сеть Петри можно понимать (интерпретировать) по-разному. Можно представить себе, что места пред- ставляют условия (буфер пуст, файл закрыт и т.п.), а переходы - события (посылка или получение со- общения в буфер, запись в файл). Состояние сети Петри в каждый текущий момент определяется системой условий. Для того чтобы стало возможным и удобным задавать условие типа "в буфере находится 3 записи", в модель сети Петри до- бавляются фишки. Фишки изображаются точками внутри места. В применении к программированию можно представлять себе переходы как процедуры, а места - как переменные или буфер. Фишка свидетельствует о том, что переменная/буфер имеет значение, а если место имеет, к примеру, 3 фишки, то это может интерпретироваться как наличие трех разных значений в буфере. Если место со- держит фишку, то место маркировано и сеть называется маркированной. Начальное распределение фи- шек задает начальную маркировку М 0 сети. Маркировка сети определяет ее текущее состояние. Сеть на рис. 10.4 в начальном состоянии содержит одну фишку в месте р 3 . Маркировка формально зада- ется функцией М: Р → I, I = {0,1,2,..}, а функция М представляется вектором, в котором i-й компонент задает маркировку места p i . Например, начальная маркировка сети на рис. 10.4 представляется вектором М 0 = {1,0,0}. 79 Рис 10.4 На рис. 10.4 показана последовательность состояний сети Петри в ходе срабатывания переходов. На- чальная разметка М 0 = (1,0,0) показана на рис. 10.4,а. В этом состоянии может сработать только переход t 1 . Разметка сети M 1 = (1,1,1) после срабатывания t 1 показана на рис. 10.4,б. Последняя позволяет одно- временно сработать переходам t 1 и t 2 , разметка М 2 = (1,2,3) после их срабатывания показана на рис. 10.4,в. Сеть переходит из одного состояния в другое (от одной маркировки к другой), когда происходит собы- тие - срабатывание перехода. Переход может сработать, если есть хотя бы одна фишка во всех его вход- ных местах (рис. 10.5) Рис 10.5 Срабатывание перехода состоит из того, что из всех входных мест забирается по одной фишке и во все выходные места добавляется по одной фишке. Если представить себе переход как процедуру, то она корректно выполняется при наличии значений всех своих аргументов и вырабатывает значения всех выходных переменных. В другой интерпретации переход может представлять некоторое устройство. Устройство может (но не должно) сработать, если выполнились все входные условия. Если несколько переходов готовы срабо- тать, то срабатывает один из них (любой), или некоторые из них, или все (рис. 10.6). 80 Рис 10.6 Пример 2 Рассмотрим пример конвейера. Пусть есть три обрабатывающих устройства t 0 , t 1 , t 2 организованные в виде конвейера. Это могут быть, например, станки на заводе или функциональные устройства конвей- ерного процессора и вообще любой конвейер, в котором каждое обрабатывающее устройство выполня- ет лишь часть общей работы, а результат будет выработан лишь последним из них. Особенностью нашего конвейера является ограниченность емкости мест p 1 и р 2 ; место p 1 может вме- стить лишь два результата (место p 1 сети является 2-ограниченым) предшествующего этапа работы кон- вейера (вырабатывается переходом t 0 ), а место p 2 - 3-ограниченным. Символ n в месте р 0 означает на- личие n фишек в нем, n - целое положительной число. Сеть Петри, обеспечивающая необходимое прямое управление, приведена на рис. 10.7. Понятно, что в месте p 1 не может накопиться более 2 фишек при любых порядках срабатывания переходов сети. Места p 1 и р 2 часто еще называют асинхронными каналами, с их помощью реализуется программирование средствами асинхронного message passing interface (см. подраздел 10.3). Рис 10.7 Сеть Петри, в которой все места 1-ограничены, называется безопасной. Такой сетью можно задавать прямое управления в программах. Безопасная сеть никогда, не допустит, чтобы в переменную было по- ложено новое значение, если старое еще не было использовано по назначению. Нарушения этого прави- ла часто являются причиной ошибок в параллельных программах. 81 При использовании сетей Петри в языках программирования стандартные вычисления (например, сеть управления конвейерным исполнением процедур) может быть описана как управляющая процедура, например: control procedure pipiline (t 0 , p 4 , t 1 , p 5 , t 2 ); <описание сети примера 1>; Теперь, при необходимости задать в программе конвейерное вычисление некоторых процедур, их имена подставляются в обращение к управляющей процедуре pipiline вместо формальных параметров t 0 , t 1 , t 2 call pipiline (t 0 = procl, p 4 = 2, t 1 = proc2, p 5 = 3, t 2 = proc3.) Наличие библиотеки стандартных управляющих процедур способно облегчить отладку параллельной программы. Сеть примера 2 может быть использована также для управления асинхронным каналом при описания и реализации message passing interface в языках с асинхронными взаимодействиями. 10.2.3. Граф достижимости Для использования сетей Петри необходимо знать их свойства, такие, как безопасность, а для этого сле- дует изучить множество всех разметок сети с заданной начальной разметкой. Разметка М называется достижимой, если при некоторой последовательности срабатываний сети, начи- ная с начальной разметки М 0 , она переходит к разметке М. Множество разметок, достижимых в порядке срабатывания сети, представляется разверткой сети. Множество достижимых разметок удобно представлять графом достижимости, который показывает все достижимые разметки и последовательности срабатываний переходов, приводящих к ним. Пример 3 Следующая сеть (рис. 10.8,а.) определяет управление двумя параллельно протекающими процессами с синхронизацией. Граф достижимости показан на рис. 10.8,б. Граф развертки сети бесконечен (рис 10.8,б), однако после состояния М 3 в каждой ветви повторяется один и тот же фрагмент и потому воз- можно конечное представление графа достижимости (рис. 4 8,в). Рис 10.8 82 Для неограниченной сети и граф развертки и граф достижимости бесконечны. Такой неограниченный граф показан на рис. 10.9,а. Вообще всякое конечное дискретное устройство, вырабатывающее бесконечный результат (бесконеч- ный язык), обнаруживает некоторого рода регулярность в поведении, что и обеспечивает конечную его представимость (в теории формальных языков этот факт выражается в pumping теоремах). Это демонст- рируют и примеры графов достижимости. 10.2.4. Дедлоки Сети Петри оказались удобным средством для анализа такого свойства параллельной системы, как на- личие или отсутствие дедлоков. Состояние дедлока возникает, когда запрос ресурсов в системе не мо- жет быть удовлетворен и система останавливается (ни один переход не может сработать). Это может быть нормальный останов сети, а может быть и следствие конкуренции за ресурсы. Пример 4 Рассмотрим пример на рис. 10.9,а. Сеть А определяет циклическое неограниченное срабатывание пере- ходов t 1 , t 2 , t 3 . При срабатывании переходы t 2 и t 3 потребляют единицу ресурса из места р 3 каждый. Можно представить себе для определенности, что место р 3 содержит два участка памяти (буферы), ко- торые операционная система может динамически выделять программе по ее запросу. Пока процесс, управляемый сетью А, выполняется один, ситуации дедлока не возникает. Но если появляется идентич- ный процесс, выполняющийся параллельно А и управляемый сетью В (рис. 10.9,б), тогда возникает кон- куренция за ресурс в месте р 3 Рис 10.9 Ситуация дедлока возникает при такой последовательности срабатываний переходов сети: t 1 , t 4 , t 2 , t 5 . И в этом состоянии имеем дедлок: ни один переход не может сработать. Однако сеть будет нормально функционировать, если в месте p i оставить одну фишку, т.е. разрешить выполняться либо процессу А, либо процессу В, но не обоим одновременно. Опасность при таком динамическом (в ходе вычислений) захвате ресурсов вызывает дозахват ресурса (запрос дополнительной порции без освобождения уже захваченных ресурсов). Поэтому чаще всего не- обходимый ресурс захватывается сразу в нужном количестве, хотя при этом часть захваченного ресурса не может быть сразу использована и простаивает. 83 Пример 5 Рассмотрим классическую задачу о пяти обедающих философах. Суть задачи такова. Пять философов, прогуливаясь и размышляя, время от времени испытывают приступы голода. Тогда они заходят в сто- ловую, где стоит круглый стол, на нем всегда приготовлены пять блюд. Между соседними блюдами ле- жит одна вилка (всего лежат ровно пять вилок). Голодный философ: a. входит в столовую, садится за стол и берет вилку слева; b. берет вилку справа; c. ест (обязательно двумя вилками); d. кладет обе вилки на стол, выходит из столовой и продолжает думать. При конструировании управления в этой задаче следует учитывать самые разнообразные варианты по- ведения философов. Рассмотрим некоторые из них. a. Необходимо организовать действия философов так, чтобы они все были накормлены и не случи- лось бы так, что пять философов одновременно войдут в столовую, возьмут левую вилку и за- стынут в ожидании освобождения правой вилки. Голодная смерть всех философов неминуема, если никто из них не захочет расстаться па время со своей левой вилкой. Будет не лучше, если они одновременно положат левые вилки, а затем вновь одновременно попытаются завладеть не- обходимыми двумя вилками. Результат, понятно, тот же. Типичный дедлок в результате попытки дозахватить ресурс (вилку)! Грубым (неэффективным) приемом, чтобы избежать этой ситуации, является введение ограниче- ния на число философов, допущенных одновременно в столовую. Например, можно пускать в столовую не более четырех философов одновременно. Тогда один из них, по крайней мере, смо- жет захватить две вилки, поесть и освободить ресурсы (вилки). b. Необходимо также предусмотреть, чтобы два философа одновременно не хватали одну и ту же вилку (зная вспыльчивый характер философов, нетрудно предсказать результат). c. Стеснительный философ не должен умирать голодной смертью из-за того, что его вилки посто- янно раньше него хватают напористые соседи. d. Легко представить себе ситуацию, когда банда сговорившихся философов завладеет всеми вил- ками и, передавая их только в своей среде, уморит голодом всех прочих. Сеть Петри, задающая управление распределением вилок обедающим философам, строится пошагово. Вначале была сконструирована сеть, управляющая поведением одного (любого) философа (рис. 10.10). Далее она используется для конструирования сети, управляющей поведением нескольких философов. Пример такой сети для случая трех философов показан на (рис. 10.11). Разделяемые ресурсы - левые и правые вилки - разных фрагментов сети совмещаются. Это управление не решает задач а) - г). Рис 10.10 84 Рис 10.11 Пример 6 Другой пример взаимодействующих процессов показан на рис. 10.12,а. Здесь производитель П произво- дит детали и оставляет их на складе t 5 , а потребитель Т забирает их со склада, когда они там есть. Регу- лирует это взаимодействие место t 5 . Если необходимо принять во внимание ограниченную вместимость склада, тогда в сеть добавляется место t 6 (рис 10.12,б). Оно определяет наличие места для хранения 10 деталей. Взятие фишки из места t 6 , может интерпретироваться как взятие разрешения поместить оче- редную деталь на склад (есть свободное место для хранения). 85 Рис 10.12 Сети Петри очень удобны для задания прямого управления в теоретических работах при исследовании параллелизма. К сожалению, их трудно оказалось использовать в языках программирования как в силу большой времяемкости моделирования их поведения, так и в силу сложности конструирования и отлад- ки заданного ими прямого управления. 10.3. Message passing interface Message passing interface (MPI) - это метод программирования межпроцессных коммуникаций. В разных формах MPI изучался в асинхронных вычислениях с конца 60-х годов как у нас в стране, так и за рубе- жом. MPI использовался в нескольких коммерческих вычислительных системах. В настоящее время можно назвать рабочую станцию SP2 фирмы IBM с мультикомпьютерным ускорителем на базе микро- процессора PowerPC (до 128 процессорных элементов), в которой MPI является основным средством параллельного программирования. Именно на базе этого мультикомпьютера создана, в частности, шах- матная программа IBM Deep Blue. 10.3.1. Определение MPI Предполагается, что программа определяется как система независимых, параллельно протекающих взаимодействующих процессов. Как обычно, здесь процесс - это исполняющаяся программа со всеми обрабатываемыми данными. Исполнение этой же программы с другими данными определяет другой процесс. Взаимодействие определяется как посылка сообщения из одного процесса в другой и прием сообщения. Сообщение - любая последовательность битов, которая чаще структурируется и определяется как зна- чение набора (кортежа, структуры) переменных. Сообщение посылается в канал в одном процессе и выбирается из канала в другом процессе. 86 87 Канал может рассматриваться как очередь. Оператор send, записывает сообщение в канал, в канале мо- жет накопиться очередь сообщений. Оператор receive выбирает сообщение из канала, если оно есть в канале. Если очередь канала не ограничена, мы говорим об асинхронном MPI. В программе для использования MPI следует прежде всего описать каналы, например: ch queue (<описание_переменной>). Описание определяет канал queue, который в состоянии хранить значения переменной канала <описа- ние_переменной>. Переменная канала может быть простой или структурированной. Возможны описа- ния вида: ch symbol (char); ch data (day, month, year : integer); ch personal_date (name : string, age : integer ); Запись сообщения в канал производится оператором send; send < имя канала > (< выражение >); Выражение должно вырабатывать значение переменной, описанной в определении канала. Например: send data (d, m, у); Переменные d, m и у задаются в процессе-отправителе и должны содержать целые значения, как это и определено в описании канала data. Данные выбираются из канала оператором receive. receive personal_date (n, a); Переменные n и а определяются в процессе-получателе и должны быть описаны так же, как переменная канала. После выполнения оператора receive переменная n может содержать значение "Иванов И.И.", а переменная a - значение "30". Если канал предполагается неограниченным (асинхронный MPI), то оператор send может быть выпол- нен неограниченно много раз (неблокируемый оператор). Оператор receive получает значение из канала, если он не пуст. Если в канале нет значения, выполнение оператора receive задерживается (блокируемый оператор) до появления значения в канале. Канал асин- хронного MPI реализуется как асинхронный канал. Каналы описываются как глобальные объекты, поскольку они разделяются процессами программы. Можно определить массив каналов, например: ch data [l:k] (day, month, year : integer); Допускается, чтобы несколько процессов посылали сообщения в один и тот же канал. Аналогично, не- сколько процессов могут получать данные из одного канала. Описанный канал в начальный момент пуст. Пример 1 Одно из типичных межпроцессных взаимодействий определяет взаимодействия клиента и производите- ля. Производитель создает продукт и продает его многим клиентам. Программа их взаимодействий мо- жет иметь вид ch request (integer, <описание_запроса_клиента>); ch reply (integer, <описание_результата>); <описание_запроса_клиента> - это описание типов переменных, значения которых специфицируют за- прос клиента к производителю. Значение переменной, описанной как integer, определяет уникальный номер клиента. 88 < описание_результата > - описание переменных, специфицирующих ответ производителя на запрос клиента % Producer :: var index, ...; do true → receive request (index, ...); % ожидание запроса клиента % ..... % обработка запроса клиента и формирование ответа % send reply [index] (...); % ответ клиенту % od; Client [i : 1...n] :: send request (i,...); % обращение к Producer % receive reply [i](...);% ожидание ответа |