Теория вычислительных процессов

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

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

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

Пример 3.29. Общая внешняя память.

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

ДОППАМ = i: КОПИР

Предполагается, что эта память используется как подчиненный процесс

(доп: ДОППАМ //...).

Внутри основного процесса доступ к этой памяти осуществляется взаимодействиями

Доп.i.лев!блок >... доп.i.прав?у >,..

Дополнительная память может также совместно использоваться параллельными процессами. В этом случае действие

(доп.i.лев!блок >...)

одновременно займет произвольный свободный сектор с номером i и запишет в него значение блок. Аналогично, доп.1.прав?х за одно действие считает содержимое сектора i в х и освободит этот сектор для дальнейшего использования, вполне вероятно, уже другим процессом. Именно это упрощение и послужило истинной причиной использования КОПИР для моделирования каждого сектора.

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

3.4.4 Планирование ресурсов

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

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

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

пожалуйста, осуществляющее запрос ресурса,

спасибо, сопровождающее реальное получение ресурса.

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

(рес.i. пожалуйста; реc.i.спасибо;...; реc.i.свободен > ПРОПУСК.)

Простым и эффективным способом планирования ресурса является назначение его процессу, ожидавшему дольше всех. Такая политика называется «первым пришел -- первым, обслужен» (FСFS) или «первым пришел -- первым ушел» (FIFO) и представляет собой принцип очереди, соблюдаемый, к примеру, пассажирами на автобусной остановке.

В заведении же типа поликлиники, где посетители не могут; или не хотят выстраиваться в очередь, для достижения того же результата действует другой механизм. Регистратура выдает талоны со строго возрастающими последовательными номерами. При входе в поликлинику посетитель берет талон. Когда врач освободился, он вызывает посетителя, имеющего талон с наименьшим номером, но еще не принятого. Этот алгоритм, называемый алгоритмом поликлиники, более строго описан ниже. Мы будем предполагать, что одновременно могут обслуживаться до R посетителей,

Пример 3.30. Алгоритм поликлиники.

Нам потребуются три счетчика:

р -- посетители, сказавшие пожалуйста,

t -- посетители, сказавшие спасибо,

r -- посетители, освободившие свои ресурсы.

Очевидно, что в любой момент времени r ? t ? р. Кроме того, р всегда будет номером, который получает очередной посетитель, приходящий в поликлинику, а t -- номером очередного обслуживаемого посетителя; далее, р -- t будет числом ожидающих посетителей, а R + r -- t -- числом ожидающих врачей. Вначале значения всех счетчиков равны нулю и могут быть вновь положены равными нулю в любой момент, когда их значения совпадают -- например, вечером, после ухода последнего посетителя.

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

ПОЛИКЛИНИКА = B0,0,0

Вp,t,r = if 0 < r = t = р then ПОЛИКЛИНИКА

else if R+r - t > 0 AND р -- t > 0

then t.спасибо > Вр,t+1,r

еlse (р.пожалуйста > Вр+1,t, r | i.свободен > Вр,t,r+1)).

3.5 Программирование параллельных вычислений

3.5.1 Основные понятия

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

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

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

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

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

Рассмотренные механизмы связи необязательно используются только непосредственно на соответствующих архитектурах. Так легко промоделировать обмен сообщениями, используя общую память, с другой стороны можно смоделировать общую память, используя обмен сообщениями. Последний подход известен как виртуальная общая память.

Наиболее желательными (даже скорее обязательными) признаками параллельных алгоритмов и программ являются:

· параллелизм,

· маштабируемость,

· локальность,

· модульность.

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

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

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

Модульность отражает степень разложения сложных объектов на более простые компоненты. В параллельных вычислениях это такой же важный аспект разработки программ, как и в последовательных вычислениях.

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

3.5.2 Многопоточная обработка

Если L -- метка некоторого места в программе, то команда

fork L

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

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

Разновидность команды ветвления до сих пор используется в операционной системе UNIХ™. При этом ветвление не подразумевает переход по метке. Его эффект заключается во взятии совершенно новой копии всей памяти программы и передачи этой копии новому процессу. Как исходный, так и новый процессы продолжают исполнение с команды, следующей за командой ветвления. У каждого процесса есть средство определить, является ли он порождающим (отец) или порождаемым (сын). Выделение процессам непересекающихся участков памяти снимает основные трудности и опасности многопоточной обработки, но может быть неэффективным как по времени, так и по объему памяти. Это означает, что параллелизм допустим только на самом внешнем (самом глобальном) уровне задания, а использование его в мелком масштабе затруднительно.

3.5.3 Условные критические участки

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

Для решения этой проблемы предложено удобное средство, называемое условным критическим участком. Он имеет вид

with общперем when условие dо критический участок

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

3.5.4 Мониторы

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

Приведем пример очень простого монитора, ведущего себя как счетчиковая переменная.

1 monitor счет;

2 vаr n: integer

3 рrocedure* вверх; begin n := n + 1 еnd;

4 рrocedure* вниз; when > 0 dо begin n := n - 1 еnd;

5 function* приземл. Вооlеаn; begin приземл := (n = 0) еnd;

6 begin n := 0;

7 ...;

8 if n ? 1 then рrint(n)

9 еnd

Строка 1 описывает монитор с именем счет.

2 описывает локальную для монитора общую переменную n. Она доступна только внутри самого монитора.

З - 5 описывают три процедуры и их тела. Звездочки обеспечивают вызов этих процедур из программы, использующей монитор.

6 Здесь начинается исполнение монитора.

7 Три жирные точки обозначают внутреннее предложение, соответствующее блоку, который будет использовать монитор.

8 При выходе из использующего блока печатается конечное значение n (если оно ненулевое).

Новый экземпляр этого монитора может быть описан локальным для блока Р:

instanсе ракетa: счет; Р

Внутри блока Р можно вызывать помеченные звездочками процедуры, используя команды

ракета.вверх;... ракета.вниз;. ..;, if ракета.приземл then...

Непомеченная же процедура или такая переменная, как n, недостижимы из Р. Свойственное мониторам взаимное исключение позволяет вызывать процедуру монитора любому числу процессов внутри Р без взаимного влияния при изменении n. Заметим, что попытка вызвать ракета.вниз при n. = 0 будет отложена до тех пор, пока некоторый другой процесс внутри Р не вызовет ракета.вверх. Это гарантирует, что значение n никогда не станет отрицательным.

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

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

3.6 Модели параллельных вычислений

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

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

3.6.1 Процесс/канал

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

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

2. Процесс - это последовательная программа с локальными данными. Процесс имеет входные и выходные порты, которые служит интерфейсом к среде процесса.

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

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

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

6. Процессы можно распределять по физическим процессорам произвольным способами, причем используемое отображение (распределение) не воздействует на семантику программы. В частности, множество процессов можно отобразить на одиночный процессор.

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

3.6.2 Обмен сообщениями

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

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

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

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

3.6.3 Параллелизм данных

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

Модель также является часто используемой моделью параллельного программирования. Название модели происходит оттого, что она эксплуатирует параллелизм, который заключается в применении одной и той же операции к множеству элементов структур данных. Например, «умножить все элементы массива M на значение x», или «снизить цену автомобилей со сроком эксплуатации более 5-ти лет». Программа с параллелизмом данных состоит из последовательностей подобных операций. Поскольку операции над каждым элементом данных можно рассматривать как независимые процессы, то степень детализации таких вычислений очень велика, а понятие «локальности» (распределения по процессам) данных отсутствует. Следовательно, компиляторы языков с параллелизмом данных часто требуют, чтобы программист предоставил информацию относительно того, как данные должны быть распределены между процессорами, другими словами, как программа должны быть разбита на процессы.

3.6.4 Общей памяти

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

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

4. Сети Петри

4.1 Введение в сети Петри

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

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

В одном из подходов к проектированию и анализу систем сети Петри используются, как вспомогательный инструмент анализа. Здесь для построения системы используются общепринятые методы проектирования. Затем построенная система моделируется сетью Петри, и модель анализируется. Если в ходе анализа в проекте найдены изъяны, то с целью их устранения проект модифицируется. Модифицированный проект затем снова моделируется и анализируется. Этот цикл повторяется до тех пор, пока проводимый анализ не приведет к успеху.

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

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

4.2 Основные определения

4.2.1 Теоретико-множественное определение сетей Петри

Пусть мультимножество это множество, допускающее вхождение нескольких экземпляров одного и того же элемента.

Сеть Петри N является четверкой

N=(P,Т,I,O),

где

P = {p1, p2,..., pn} -- конечное множество позиций, n і 0;

T = {t1, t2,..., tm} -- конечное множество переходов, m і 0;

I: T і P* -- входная функция, сопоставляющая переходу мультимножество его входных позиций;

О: T і P* - выходная функция, сопоставляющая переходу мультимножество его выходных позиций.

Позиция pОP называется входом для перехода tОT, если pОI(t). Позиция pОP называется выходом для перехода tОT, если pОO(t). Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями.

Пример 4.1.

Сеть Петри N =(P,T,I,O),

P={p1, p2, p3},

T={t1, t2},

I(t1)={ p1, p1, p2}, O(t1)={p3},

I(t2)={ p1, p2, p2}, O(t2)={p3}.

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

4.2.2 Графы сетей Петри

Рисунок 4.1.

Наиболее наглядным представлением сети Петри является её графическое представление, которое представляет собой двудольный, ориентированный мультиграф.

Граф сети Петри обладает двумя типами узлов: кружок ?, представляющий позицию сети Петри; и планка ?, представляющая переход сети Петри. Ориентированные дуги этого графа (стрелки) соединяют переход с его входными и выходными позициями. При этом дуги направлены от входных позиций к переходу и от перехода к выходным позициям. Кратным входным и выходным позициям перехода соответствуют кратные входные и выходные дуги. Граф сети Петри примера 4.1.

В графе сети Петри не возможны дуги между двумя позициями и между двумя переходами.

4.2.3 Маркировка сетей Петри

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

Маркировка m сети Петри N=(P,T,I,О) есть функция, отображающая множество позиций P во множество Nat неотрицательных целых чисел. Маркировка m, может быть также определена как n-вектор

m=<m(?p₁)?, m(?p₂), ??…, m(p_n)>,

где n - число позиций в сети Петри и для каждого 1 Ј i Ј n ?m(p_i) О Nat - количество фишек в позиции pi.

Рисунок 4.2.

Маркированная сеть Петри N=( P,Т,I,О,m) определяется совокупностью структуры сети Петри (P,T,I,О) и маркировки m. На рисунке 4.2 представлена маркированная сеть Петри m = <1,0,1>.

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

4.2.4 Правила выполнения сетей Петри

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

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

Пусть функция ^{^}#: PґT ® Nat для произвольных позиции pОP и перехода tОТ задает значение ^{^}#(p,t), которое совпадает с кратностью дуги, ведущей из p в t, если такая дуга существует, и с нулем, в противном случае.

Пусть функция #^{^}: TґP ®Nat для произвольных и перехода tОT позиции pОP задает значение #^{^}(t,p), которое совпадает с кратностью дуги, ведущей из t в p, если такая дуга существует, и с нулем, в противном случае.

Переход tОT в маркированной сети Петри N=(P,T,1,О,m) разрешен, если для всех p О I(t) справедливо m(?p) ??і ?^{^}#(p,t).

Запуск разрешённого перехода tОT из своей входной позиции pОI(t) удаляет ^{^}#(p,t) фишек, а в свою выходную позицию p'О O(t) добавляет #^{^}(t,p') фишек.

Рисунок 4.3.

Сеть Петри до запуска перехода t1 (рис. 4.3, а). Сеть Петри после запуска перехода t1 (рис. 4.3, б).

Переход t в маркированной сети Петри с маркировкой m может быть запущен всякий раз, когда он разрешен и в результате этого запуска образуется новая маркировка m', определяемая для всех pОP следующим соотношением:

m'(p)= m(p) - ^{^}#(p,t) + #^{^}(t,p).

Запуски могут осуществляться до тех пор, пока существует хотя бы один разрешенный переход. Когда не останется ни одного разрешенного перехода, выполнение прекращается.

Если запуск произвольного перехода t преобразует маркировку m сети Петри в новую маркировку m', то будем говорить, что m' достижима из m посредством запуска перехода t и обозначать этот факт, как m ®^t m'. Это понятие очевидным образом обобщается для случая последовательности запусков разрешённых переходов. Через R(N,--m) обозначим множество всех достижимых маркировок из начальной маркировки m в сети Петри N.

Преобразование маркировки сети Петри изображено на рисунке 4.3. Переход t1 преобразует маркировку? m =<5,1> в маркировку m'=<2,3>.

4.3 Моделирование систем на основе сетей Петри

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

4.3.1 События и условия

Представление системы сетью Петри основано на двух основополагающих понятиях: событиях и условиях. Возникновением событий управляет состояние системы, которое может быть описано множеством условий. Условие может принимать либо значение «истина», либо значение «ложь».

Возникновение события в системе возможно, если выполняются определённые условия - предусловия события. Возникновение события может привести к выполнению других условий - постусловий события. В качестве примера рассмотрим следующую ниже задачу моделирования.

Пример 4.2. Моделирование последовательной обработки запросов сервером базы данных. Сервер находится в состоянии ожидания до тех пор, пока от пользователя не поступит запрос клиента, который он обрабатывает и отправляет результат такой обработки пользователю.

Условиями для рассматриваемой системы являются:

а) сервер ждет;

б) запрос поступил и ждет;

в) сервер обрабатывает запрос;

г) запрос обработан.

Событиями для этой системы являются:

1.Запрос поступил.

2. Сервер начинает обработку запроса.

3. Сервер заканчивает обработку запроса.

4. Результат обработки отправляется клиенту.

Для перечисленных событий можно составить следующую таблицу их пред- и постусловий

Событие	Предусловия	Постусловия
1 2 3 4	нет а, б в г	б в г, а нет

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

Рисунок 4.4.

На рисунке 4.4. предусловие выполняется для события 2.

4.3.2 Одновременность и конфликт

Особенность сетей Петри - их асинхронная природа. В сетях Петри отсутствует измерение времени. В них учитывается лишь важнейшее свойство времени - частичное упорядочение событий.

Выполнение сети Петри (или поведение моделируемой системы) рассматривается здесь как последовательность дискретных событий, которая является одной из возможных. Если в какой-то момент времени разрешено более одного перехода, то любой из них может стать «следующим» запускаемым. Переходы в сети Петри, моделирующей некоторую систему, представляют ее примитивные события (длительность которых считается равной 0), и в один момент времени может быть запущен только один разрешённый переход.

Моделирование одновременного (параллельного) возникновения независимых событий системы в сети Петри демонстрируется на рисунке слева.

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

Другая ситуация в приведенной справа сети Петри. Эти два разрешённые перехода находятся в конфликте, т. е. запуск одного из них удаляет фишку из общей входной позиции и тем самым запрещает запуск другого. Таким образом, моделируются взаимоисключающие события системы.

4.3.3 Моделирование параллельных систем взаимодействующих процессов

4.3.3.1 Моделирование последовательных процессов

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

Пример 4.3. Последовательная программа на абстрактном языке программирования, вычисляющая Y! и произведение всех чётных чисел из отрезка [1,Y] для Y О Nat.



Рисунок 4.5.

begin

read(Y);

X1:=1;

X2:=1;

while Y>0 do

begin

if mod(Y,2)=0

then begin

X1:=X1*Y;

end;

X2:=X2*Y;

Y:=Y-1;

end;

write(X1);

write(X2);

end

Программа представляет два различных аспекта процесса: вычисление и управление. Сети Петри удачно представляют структуру и управление программ. Они предназначены для моделирования упорядочения действий и потока информации, а не для действительного вычисления самих значений.

Рисунок 4.6.

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

a: read(Y); X1:=1; X2:=1;

b: Y>0

c: mod(Y,2)=0

d: X1:=X1*Y;

e: X2:=X2*Y; Y:=Y-1;

f: write(X1); write(X2);

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

4.3.3.2 Моделирование взаимодействия процессов

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

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

Существуют различные виды взаимодействия (синхронизации) процессов, в том числе: взаимодействие посредством общей памяти; - посредством передачи сообщения различных видов.

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

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

4.3.3.3 Задача о взаимном исключении

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

Процесс P1 считывает значение х из разделяемого объекта;

Процесс P2 считывает значение х из разделяемого объекта;

Процесс P1 вычисляет новое значение х'=f(x);

Процесс P2 вычисляет новое значение х"=g(x);

Процесс P1 записывает х' в разделяемый объект;

Процесс P2 записывает х" в разделяемый объект, уничтожая значение х

Результат вычисления процесса P1 потерян.

Рисунок 4.7.

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

Следующая сеть Петри (рисунок 4.7) моделирует механизм взаимного исключения для двух процессов P1 и P2. Она легко обобщается на произвольное число процессов.

Позиция m представляет условие «критическая секция свободна», разрешающее вход в критическую секцию. Попытка процесса P1 (P2) войти в критическую секцию осуществляется после помещения фишки в его позицию s1 (s2). Такая попытка может увенчаться успехом, если в позиции m содержится фишка. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы t1 и t2 вступят в конфликт, и только один из них сможет запуститься. Запуск t1 запретит запуск перехода t2, вынуждая процесс P2 ждать, пока процесс P1 выйдет из своей критической секции, и возвратит фишку обратно в позицию m.

4.3.3.4 Задача о производителе/потребителе

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

Позиция B представляет буфер, каждая фишка соответствует сообщению, которое произведено, но еще не использовано.



Рисунок 4.8.

4.3.3.5 Задача об обедающих философах

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

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

В этой сети Петри позиция пi, i О {1,2,3,4,5}, представляет условие «i-тая вилка свободна». В начальной маркировке каждая из этих позиций имеет фишку. Каждому философу i О {1,2,3,4,5} соответствует две позиции: позиция дi - представляющая условие «i-тый философ думает»; и позиция еi - представляющая условие «i-тый философ ест». В начальной маркировке все позиции дi содержат фишку, а все позиции еi пусты.

Каждому философу i О {1,2,3,4,5} также соответствует два перехода: переход начi - представляющий событие «начало приема пищи i-тым философом»; и переход завi - представляющий событие «завершение приема пищи i-тым философом».

Рисунок 4.9.

4.4 Анализ сетей Петри

Моделирование систем сетями Петри, прежде всего, обусловлено необходимостью проведения глубокого исследования их поведения. Для проведения такого исследования необходимы методы анализа свойств самих сетей Петри. Этот подход предполагает сведения исследования свойств реальной системы к анализу определенных свойств моделирующей сети Петри.

4.4.1 Свойства сетей Петри

Позиция pОP сети Петри N=(P,Т,I,O) c начальной маркировкой О является k-ограниченной, если m'(p)Јk для любой достижимой маркировки m'ОR(N,m). Позиция называется ограниченной, если она является k-ограниченной для некоторого целого значения k. Сеть Петри ограниченна, если все ее позиции ограниченны.

Позиция pОP сети Петри N=(P,Т,I,O) c начальной маркировкой m является безопасной, если она является 1-ограниченной.Сеть Петри безопасна, если безопасны все позиции сети.

Сеть Петри N=(P,Т,I,O) с начальной маркировкой m является сохраняющей, если для любой достижимой маркировки m'ОR(N,m) справедливо следующее равенство.

'(p).

Тупик в сети Петри - один или множество переходов, которые не могут быть запущены. Определим для сети Петри N с начальной маркировкой m следующие уровни активности переходов:

Уровень 0: Переход t обладает активностью уровня 0 и называется мёртвым, если он никогда не может быть запущен.

Уровень 1: Переход t обладает активностью уровня 1 и называется потенциально живым, если существует такая m'ОR(N,m), что t разрешён в m'.

Уровень 2: Переход t, обладает активностью уровня 2 и называется живым, если для всякой m'ОR(N,m) переход t является потенциально живым для сети Петри N с начальной маркировкой m'.

Сеть Петри называется живой, если все её переходы являются живыми.

Задача достижимости: Для данной сети Петри с маркировкой m и маркировки m' определить: m'ОR(N,m)?

Задача покрываемости: Для данной сети Петри N с начальной маркировкой m и маркировки m' определить, существует ли такая достижимая маркировка m'ОR(N,m), что m">іm'

(Отношение m"іm' истинно, если каждый элемент маркировки m" не меньше соответствующего элемента маркировки m'.)

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

Сеть Петри N=(P,Т,I,O) с начальной маркировкой m и сеть Петри N'=(P',Т',I',O') с начальной маркировкой m' эквивалентны, если справедливо R(N,--m)=R(N',--m').

Понятие эквивалентности сетей Петри может быть определено также через равенство множеств возможных последовательностей запусков переходов.

Более слабым, по сравнению с эквивалентностью, является свойство включения, определение которого совпадает с определением эквивалентности, с точностью до замены = на m.

4.4.2 Методы анализа

Особый интерес вызывают методы анализа свойств сетей Петри, которые обеспечивают автоматический анализ моделируемых систем. Сначала рассмотрим метод анализа сетей Петри, который основан на использовании дерева достижимости.

4.4.2.1 Дерево достижимости

Дерево достижимости представляет все достижимые маркировки сети Петри, а также - все возможные последовательности запусков ее переходов.



Рисунок 4.10 а б

Пример 4.4. Частичное дерево достижимости маркированной сети Петри изображено на рисунке 4.10, а, а частичное дерево достижимости для трёх шагов построения имеет вид (рисунок 4.10, б).

Для сети Петри с бесконечным множеством достижимых маркировок дерево достижимости является бесконечным. Сеть Петри с конечным множеством достижимых маркировок также может иметь бесконечное дерево достижимости (см. пример 4.4). Для превращения бесконечного дерева в полезный инструмент анализа строится его конечное представление. При построении конечного дерева достижимости для обозначения бесконечного множества значений маркировки позиции используется символ w. Также используются следующие ниже операции над w, определяемые для любого постоянного a.

w -- а = w; w + а = w; а < w; w Ј w.

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

1. Если в дереве имеется другая вершина y, не являющаяся граничной, и с ней связана та же маркировка, m[x]=m[y], то вершина х становится дублирующей.

2. Если для маркировки m [х] ни один из переходов не разрешен, то x становится терминальной.

3. В противном случае, для всякого перехода tОT, разрешенного в m [х], создаётся новая вершина z дерева достижимости. Маркировка m [z], связанная с этой вершиной, определяется для каждой позиции pОP следующим образом: