46364

Активность сетей Петри. Задача о чтении/записи

Реферат

Информатика, кибернетика и программирование

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

Русский

2013-11-21

1.96 MB

15 чел.

Активность сетей Петри. Задача о чтении/записи.

 

Причиной рассмотрения сохранения в сети Петри было распределение ресурсов в операционной системе ЭВМ. Другая задача, которая может возникнуть при распределении ресурсов вычислительной системы — тупики. Тупики служат предметом многих исследований в области вычислительной техники . Лучше всего иллюстрирует задачу простой пример. Рассмотрим систему, включающую два различных ресурса q и r и два процесса а и b. Если оба процесса нуждаются в обоих ресурсах, им необходимо будет совместно использовать ресурсы. Для выполнения этого потребуем, чтобы каждый процесс запрашивал ресурс, а затем освобождал его. Теперь предположим, что процесс, а сначала запрашивает ресурс q, затем ресурс r и, наконец, освобождает и q, и r. Процесс В работает аналогично, но сначала запрашивает r, а затем q. Сеть Петри на рис. 4.6 иллюстрирует два процесса и распределение ресурсов между ними.

Начальная маркировка помечает ресурсы q(p4) и r(р5) доступными и указывает на готовность процессов a и b. Одним выполнением этой сети является t1 t2 t3 t4 t5 t6   Другим — t4 t5 t6 t1 t2 t3 Ни одно из этих выполнений не приводит к тупику. Однако рассмотрим последовательность, которая начинается переходами t1 t4 . процесс а обладает ресурсом q и хочет получить r, процесс b обладает r и хочет получить q. Система заблокирована; никакой процесс продолжаться не может.

Тупик в сети Петри — это переход (или множество переходов), которые не могут быть запущены. В сети Петри на рис. 4.6. тупик возникает, если нельзя запустить переходы t2 и t5. Переход называется активным, если он не заблокирован (нетупиковый). Это не означает, что переход разрешен, скорее он может быть разрешенным. Переход tj  сети Петри С называется потенциально запустимым в маркировке μ, если существует маркировка μ'  R(C,μ), в которой tj  разрешен. Переход активен в маркировке μ, если потенциально запустим во всякой маркировке из R(C, μ). Следовательно, если переход активен, то всегда возможно перевести сеть Петри из ее текущей маркировки в маркировку, в которой запуск перехода станет разрешенным.

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

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

Уровень 1: Переход tj обладает активностью уровня 1, если он потенциально запустим, т. е. если существует такая μ,  R(C,μ ), что tj разрешен в μ'.

Уровень 2: Переход tj обладает активностью уровня 2, если для всякого целого n существует последовательность запусков, в которой tj присутствует по крайней мере n раз.

Уровень 3: Переход tj обладает активностью уровня 3, если существует бесконечная последовательность запусков, в которой tj присутствует неограниченно часто.

Уровень 4: Переход tj обладает активностью уровня 4, если для всякой μ'  R(C, μ) существует такая последовательность запусков σ, что tj разрешен в δ (μ, σ).

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

В качестве примера, иллюстрирующего уровни активности, рассмотрим сеть Петри на рис. 4.7. Переход t0 не может быть запущен никогда; он пассивен. Переход t1 можно запустить точно один раз; он обладает активностью уровня 1. Переход t2 может быть запущен произвольное число раз, но это число зависит от числа запусков перехода t3. Если мы хотим запустить t2 пять раз, мы запускаем пять раз t3, затем t1 и после этого пять раз t2. Однако, как только запустится t1 (t1 должен быть запущен до того, как будет запущен t2), число возможных запусков t2 станет фиксированным. Следовательно, t2 обладает активностью уровня 2, но не уровня 3. С другой стороны, переход t3 можно запускать бесконечное число раз, и поэтому он обладает активностью уровня 3, но не уровня 4, поскольку, как только запустится t1 , t3 больше запустить будет нельзя.

Задача активности одного перехода. Активен ли данный переход tj   T?

Очевидно, что задача активности сводится к задаче активности одного перехода. Для нахождения решения задачи активности мы просто решим задачу активности одного перехода для каждого tj  Т; если |Т| = т, то мы должны решить т задач активности одного перехода.

Задачу достижимости можно также свести к задаче активности. Поскольку варианты задачи достижимости эквивалентны, мы рассмотрим задачу достижимости нуля в одной позиции. Если перед нами стоят какие-либо другие задачи достижимости, их можно свести, как показано в разд. 5.2, к задаче достижимости нуля в одной позиции. Теперь, если мы хотим определить, может ли быть позиция pi нулевой в какой-либо достижимой маркировке для сети Петри С1 = (Р1, Т1, I1, O1) с начальной маркировкой μ1 то построим сеть Петри С2 = (Р2, Т2, I2, O2) с начальной маркировкой μ2, которая будет активна тогда и только тогда, когда нулевая маркировка не будет достижима из μ1.

Сеть Петри С2 строится из C1 введением двух позиций r1 и r2 и трех переходов s1 s2 и s3. Сначала модифицируем все переходы Т1, включая r1 в качестве входа и выхода. Начальная маркировка μ2 будет включать фишку в r1. Позиция r1 — это позиция «действия», пока фишка остается в r1, переходы Т1 могут запускаться. Следовательно, любая маркировка, достижимая в С1 достижима также и в позициях Р1 в С2. Определим переход S1 так, что его входом будет T1, а выход пуст. Это позволяет удалить фишку из r1, запрещая запуск всех переходов в 7\ и «замораживая» маркировку Р1. (Заметим, что все переходы Т1 находятся в конфликте и не только по определению, но и по построению могут запускаться каждый раз не более чем по одному.)

Позиция r1 и переход s1 позволяют сети С1 достичь любой достижимой маркировки, затем запуском S1 заморозить сеть в этой маркировке. Далее необходимо проверить, является ли позиция рi нулевой. Введем новые позицию r2 и переход s2, имеющий в качестве входа рi а в качестве выхода r2. Если pi может когда-либо стать нулевой, то этот переход не является активным. В действительности вся сеть будет пассивной, если в этой маркировке сработает переход S1. Следовательно, если pi может быть пустой, сеть не является активной. Если рi не может быть пустой, тогда s2 всегда может быть запущен, помещая фишку в r2. В этом случае мы должны будем вернуть фишку в r1 и гарантировать, что все переходы в С2 активны. Необходима уверенность в том, что С2 активна, даже если С1 не является активной. Это обеспечивается переходом s3, который «наполняет» сеть С2 фишками, гарантируя тем самым, что, если фишка помещена в r2, каждый переход активен. Переход s3 в качестве входа имеет r2 , а в качестве выхода все позиции С2 (все pi в С1, r1 и r1). Эта конструкция иллюстрируется рис. 5.6.

Далее, если маркировка μ с μ(рi) = 0 достижима в R(C1, μ1), тогда С2 также может достичь этой маркировки в позициях Р1 путем выполнения той же самой последовательности запусков переходов. Затем можно запустить s1, замораживая подмножество С1. Поскольку μ(pj) = 0, s2 запустить нельзя и С2 пассивна. Таким образом, если рi может стать нулевой — С2 неактивна.

Справедливо обратное, если С2 неактивна, тогда должна быть

достижима маркировка μ с μ(r2) = 0, из которой недостижимо состояние с фишкой в r2. (Если в r2 есть фишка, то s3 разрешен, а повторно запуская s3 достаточное число раз, можно разрешить любой (или все) переход, т. е. сеть активна.) Если r2 не имеет фишек и не может их получить, тогда маркировка pi также должна быть нулевой. Таким образом, если С2 неактивна, тогда достижима маркировка, в которой маркировка pi нулевая.

На основе этой конструкции мы доказали следующую теорему.

Теорема  Задача достижимости сводится к задаче активности.

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

Теорема 5.6. Задача активности одного перехода сводится к задаче достижимости.

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

 

где-либо в дереве запустить переход tj. Если нельзя, то μ массивна для tj. Проверка активности tj в таком случае требует проверки достижимости какой-либо пассивной для tj маркировки.

В общем случае, однако, может существовать бесконечное число пассивных для tj маркировок и бесконечное множество маркировок, в котором находятся пассивные для tj маркировки. Заметив два свойства, сведем множество маркировок, которые необходимо проверить для достижимости, к конечному числу. Во-первых, если маркировка μ пассивна для tj, то и любая маркировка μ' μ пассивна для tj. (Любая последовательность запусков, возможная из μ', возможна также из μ, поэтому если μ' может привести к запуску tj , то это может и μ.) Во-вторых, маркировки некоторых позиций не будут влиять на пассивность для tj данной маркировки, поэтому маркировки этих позиций являются «несущественными», они могут быть произвольными. Заимствуя прием из построения дерева достижимости, заменим «несущественные» компоненты на ω, показывая, что в этих позициях может быть произвольно большое число фишек, не влияющих на пассивность маркировки для tj. Теперь, поскольку любая μ'  μ пассивна для tj, если μ пассивна для tj, нам не нужно рассматривать позиции pi с μ(pi)=. Это означает, что мы применяем задачу достижимости подмаркировки с P= Pi |μ(Pi) ω}

Рассмотрим в качестве примера сеть Петри на рис. 5.7. Маркировки (2, 0), (1, 0), (0, 0), (0, 1), (0, 2), (0, 3),... являются пассивными для t2 , но их можно представить конечным образом множеством {(2, 0), (1, 0), (0, ω)}.

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

Более того, Dt можно эффективно вычислять. Поскольку Dt конечно, не- ω -компоненты имеют верхнюю границу b. Граница b определяется как такое наименьшее число, что если пассивна для tj любая маркировка μ, такая, что μ(pi)  b + 1 для всех pi то является пассивной для tj и подмаркировка μ', такая, что μ'(pi) = μ(pi), если μ(рi) < b, и μ'(pi) = ω, если μ(рi) = b + 1. При таком определении b можно построить Dt следующим образом.

Вычислить b. Начать с b = 0, увеличивать b до тех пор, пока не окажется, что b удовлетворяет описанному определению границы. Проверка каждого b требует проверки всех (b + 2)n маркировок с компонентами, меньшими или равными b+1.

Вычислить Dt проверкой всех маркировок и подмаркировок с компонентами, не превышающими b или равными ω. Dt — это множество пассивных для tj маркировок из множества (b + 2)n маркировок.

Построив Dt, можно рассматривать задачу достижимости подмаркировки для каждого элемента Dt. Если какой-либо элемент Dt достижим из начальной маркировки, сеть Петри неактивна, если же никакой элемент Dt недостижим - сеть Петри активна.

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

На рис. 3.33 иллюстрируется решение задачи в том случае, когда количество процессов чтения ограничено величиной n. Если в системе количество процессов чтения не ограничено, то только n процессов могут выполняться в одно и то же время.

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

ограниченному количеству процессов читать одновременно.

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

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

Достижимость и покрываемость  сетей Петри. Пример.

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

Определение 4.5. Задача достижимости. Для данной сети Петри С с маркировкой μ и маркировки μ’ определить: μ'  R(C, μ)?

Задача достижимости, быть может, основная задача анализа сетей Петри; многие другие задачи анализа можно сформулировать в терминах задачи достижимости. Например, для сети Петри с рис. 4.6 тупик может возникнуть, если достижимым является состояние (0, 1, 0, 0, 0, 0, 1, 0).

На рис. 4.8 показана сеть Петри, цель которой заключается в решении задачи о взаимном исключении, — предполагается, что позиции p4 и р9 будут взаимно исключающими. Мы хотим знать, является ли какое-либо состояние с μ(р4)  1 и μ(p9)  1 достижимым. Эта задача аналогична достижимости, но несколько отличается; она называется задачей покрываемости. Маркировка

μ "покрывает маркировку μ,, если μ" μ'.

Определение Задача покрываемости. Для данной сети Петри С с начальной маркировкой μ и маркировки μ.' определить, существует ли такая достижимая маркировка μ"  R(C, μ), что μ"  μ'.

В других возможных задачах типа достижимости могло бы игнорироваться содержимое некоторых позиций и приниматься во внимание сравнение или покрытие содержимого нескольких важных позиций. Например, в сети Петри на рис. 4.8 наш интерес ограничен позициями р4 и р9 — маркировка остальных позиций не важна. Таким образом, мы можем рассматривать достижимость и покрываемость «по модулю» множества позиций. Эти задачи называются задачами достижимости подмаркировки и покрываемости подмаркировки.

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

Последняя задача, которую можно решить с помощью дерева достижимости, — задача покрываемости. В задаче покрываемости мы хотим для данной маркировки μ' определить, достижима ли маркировка μ"  μ'. Данная задача решается проверкой дерева достижимости. Строим для начальной маркировки μ дерево достижимости. Затем ищем любую вершину х с μ[х] μ'. Если такой вершины не существует, маркировка р' не покрывается никакой достижимой маркировкой; если она найдена, μ[х] дает достижимую Маркировку, покрывающую μ'.

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

Заметим, что, если несколько компонент покрывающей маркировки равны w, между изменениями маркировки, получающимися в результате прохождения циклов, возможна взаимосвязь. Рассмотрим сеть Петри на рис. 4.18 и ее дерево достижимости, показанное на рис. 4.19. Согласно проведенному анализу, маркировка (0, 14, 1, 7) покрывается в множестве достижимости. Путь, порождающий покрывающую маркировку, состоит из некоторого числа переходов t1, за которыми следует переход t2, после которого уже следует некоторое число переходов t3. Задача заключается в определении того, сколько раз нужно запустить переходы t1 и t3. Так как мы хотим иметь в позиции р1 14 фишек, a t1 помещает в р2 одну фишку, попытаемся

выполнить 14 t1. Однако нам необходимо выполнить 7t3, а каждый запуск t3 удаляет из р2 фишку, поэтому в действительности необходимо выполнить не менее 21 t1 затем t2 и после этого не менее 7t3 (выполнить t3 такое число раз, чтобы в позиции р2 осталось не менее 14 фишек). Карп и Миллер  предложили алгоритм, определяющий минимальное число запусков переходов, необходимых для покрытия дайной маркировки.

Конечные автоматы

На низком уровне вычислительные системы могут быть описаны автоматами. Автомат — это пятерка (Q, ∑, ∆, δ, Г), где

Q — конечное множество состояний {q1, q2,…, qk};

∑ — конечный входной алфавит;

∆ — конечный выходной алфавит;δ : Q х ∑ → Q — функция следующего состояния, отображающая текущее состояние и текущий вход в следующее состояние; Г : Q х ∑→∆ — функция выхода, отображающая текущее состояние и текущий вход в выходной символ.

Автоматы часто представляют в виде графов переходов, как, например, на рис. 3.9. В графе переходов состояния представляются кружками, являющимися вершинами. Дуга из состояния qi в qj помеченная a|b, означает, что, находясь в состоянии qi автомат при входе а перейдет в состояние qj выдавая при этом символ b. Формально следовало бы записать

δ(qi ,a)=qj и Г (qi ,a)=b

Входной алфавит определяет входы автомата из внешнего мира, а выходной алфавит — выходы автомата во внешний мир.

В качестве примера рассмотрим автомат, изображенный на рис. 3.9. Этот автомат преобразует двоичное число, представленное последовательностью бит, начиная с младшего, в дополнение до двух. В данном случае входной и выходной алфавит состоит из трех символов: 0, 1 и R. Автомат начинает работать в состоянии qt. Символ сброса (R) означает конец (или начало) числа и возвращает автомат в исходное состояние. Выход автомата для символа сброса является просто его повторением.

Аналогичный автомат показан на рис. 3.10. При тех же самых входах этот автомат вычисляет четность входного числа. Он начинает работу в состоянии q1. Выход копирует вход до тех пор, пока входным символом не окажется символ сброса. Выходом для символа сброса будет 0 в случае нечетного числа и 1 — в случае четного числа.

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

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

ходными позициями переходов. Несмотря на возможную путаницу, эти термины наиболее естественны для обоих понятий.

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

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

Для конечного автомата (Q, ∑, ∆, δ, Г) мы определили сеть Петри (Р, Т, I, О) таким образом:

P = Q∑∆,

T = {tq,σ|q   и σ  ∑ },

I(tq,σ) ={q,σ},

O(tq,σ)  = {δ(q,σ), Г(q,σ)}

Эта сеть Петри является моделью конечного автомата.

На рис. 3.13 изображена сеть Петри, соответствующая автомату с рис. 3.9. На рис. 3.14 - cеть Петри, соответствующая автомату с рис. 3.10.

При сравнении сетей Петри на рис. 3.13, 3.14 с эквивалентными автоматами на рис. 3.9, 3.10 возникают некоторые вопросы. Прежде всего: почему модель сети Петри предпочтительнее описания конечным автоматом? Описание автоматом более понятно, чем описание сетью Петри, в которой 6 переходов, 24 дуги и 7 или 8 позиций. Это верно. Однако мы показали, что сети Петри могут представлять любую систему, представимую автоматом, и это свидетельствует о больших возможностях сетей Петри.

Кроме того, следует отметить, что модель сети Петри имеет определенное преимущество при  композиции автоматов.  Например,

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

щую четность. Такая композиция является автоматом с составными состояниями, компоненты которых — это состояния обоих подавтоматов. В сетях Петри такая композиция есть просто совмещение выходных позиций первой сети с входными позициями второй. На рис. 3.15 показана композиция автоматов, а на рис. 3.16 — составная сеть Петри.

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

Ограниченность сетей Петри. Задача об обедающих мудрецах.

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

Обратное утверждение также является верным, если сеть Петри неограниченна, то число достижимых маркировок бесконечно. Поскольку дерево достижимости конечно, бесконечное число достижимых маркировок отражает присутствие символа ω.

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

Найденное значение является границей числа фишек для заданной позиции. Если граница для всех позиций равна (1), сеть безопасна.

На рис. 4.17 демонстрируется использование дерева достижимости для определения ограниченности.

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

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

На рис. 3.32 показано решение этой задачи с помощью сети Петри. Позиции С1,…,C5 представляют палочки для еды, и так как каждая из них первоначально свободна, то в начальной маркировке в каждой из этих позиций имеется фишка. Каждый мудрец представлен двумя позициями Mi  и Ei для состояний размышления и принятия пищи соответственно. Для того чтобы мудрец перешел из состояния размышления в состояние принятия пищи, обе палочки (слева и справа) должны быть свободны. Это легко моделируется сетью Петри.

Сохранение сетей Петри. P- и  V- системы. Пример.

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

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

Определение 4.3. Сеть Петри С — (Р, Т, I, О) с начальной маркировкой μ называется строго сохраняющей, если для всех μ'  R(С, μ)

μ'(pi)= μ (pi)

Строгое сохранение — это очень сильное ограничение. Например, из него немедленно следует, <что число входов в каждый переход должно равняться числу выходов, |(tj)| = |O(tj)|. Если бы это было не так, запуск перехода изменил бы число фишек в сети.

Однако для более общего представления о свойстве сохранения рассмотрим рис. 4.3. Изображенная на нем сеть Петри не является строго сохраняющей, поскольку запуск перехода t1 или t2 уменьшит число фишек на 1, а запуск перехода t3 или t4 добавит фишку к маркировке. Мы можем тем не менее преобразовать эту сеть Петри в сеть на рис. 4.4, являющуюся строго сохраняющей.

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


Фишка определяется ее позицией в сети, все фишки в позиции неразличимы. Следовательно, веса связываются с каждой позицией сети. Вектор взвешивания ω =( ω 1, ω 2,…, ωn) определяет вес ωi для каждой позиции pi P.

Определение Сеть Петри С — (Р, Т, I, О) с начальной маркировкой μ. называется сохраняющей по отношению к вектору взвешивания ω, ω=( ω 1, ω 2,…, ω n), n=|P|, ω i  O , если для всех μ,  R(С, μ.)

 ω i . μ' (pi) = ωi . μ' (pi) .

Строго сохраняющая сеть Петри является сохраняющей по отношению к вектору взвешивания (1, 1, 1). Все сети Петри являются сохраняющими по отношению к вектору взвешивания (0, 0, 0). Этот факт вносит в теорию некоторую нестройность, поскольку нам бы хотелось определить сеть Петри как сохраняющую, если она является сохраняющей по отношению к некоторому вектору взвешивания. Однако, так как всякая сеть Петри является сохраняющей по отношению к нулевому вектору, такое определение не является удовлетворительным. Таким образом, сеть Петри называется сохраняющей, если она сохраняющая по отношению к некоторому положительному ненулевому вектору взвешивания ω  0 (с положительными ненулевыми весами, ωi  0).

Сеть Петри с рис. 4.3 является, поэтому сохраняющей, поскольку она сохраняющая по отношению к (1, 1, 2, 2, 1). Сеть Петри с рис. 4.5   не является сохраняющей.

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

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

При оценке сохранения необходимо быть внимательным с символом ω. Если маркировка имеет ω в качестве маркировки позиции pi, тогда для того, чтобы сеть была сохраняющей, вес этой позиции должен быть равным 0. Напомним, что символ ω представляет бесконечное множество значений. Так как все веса неотрицательны, вес должен равняться либо нулю (тем самым означая, что число фишек в данной позиции не важно), либо быть положительным. Если вес положителен, то сумма будет разной для двух маркировок, различающихся в своей со-компоненте. Следовательно, если какая-либо маркировка с ненулевым весом равна ω, сеть — несохраняющая.

Эти рассуждения относятся к сохранению по отношению к определенному взвешиванию. Сеть Петри является сохраняющей, если она сохраняющая по отношению к некоторому вектору ω, ωi  0. Дерево достижимости можно использовать для определения того, является сеть сохраняющей или нет, путем нахождения вектора весов ω (если он существует). Заметим, прежде всего, что для того, чтобы сеть Петри была сохраняющей по отношению к положительному вектору весов, она должна быть ограниченной. Как было указано выше, неограниченная позиция должна иметь нулевой вес, что недопустимо в сети с положительным вектором весов. (Если мы хотим допустить нулевые компоненты, нужно просто установить веса всех неограниченных позиций равными нулю и рассматривать после этого только оставшиеся компоненты.) Теперь, если сеть сохраняющая, существуют взвешенная сумма, обозначим ее s, и вектор весов ω = (ω1 , ω 2, .... , ωn). Для каждой маркировки μ[x] дерева достижимости имеем

ω1 . μ[x]1 + ω2 . μ[x]2+…+ ωn . μ[x]n=S

Это равенство определяет для k вершин дерева достижимости совокупность из k линейных уравнений с n + 1 неизвестными. Добавим к ним ограничения: ωi  0, i = 1, n, в результате чего определим ограничения для вектора весов.

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

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

Большинство задач синхронизации не могут быть решены непосредственно сетями Петри, но разрешимы скорее на основе известных механизмов синхронизации. В частности, одним из самых популярных механизмов синхронизации являются Р- и V-операции Над семафорами, впервые определенные Дейкстрой . Семафор — -Это элемент данных, который может принимать только неотрицательные целые значения. V-операция увеличивает значение на 1, а Р операция уменьшает его на 1. Р-операцию можно применять только в том случае, когда значение семафора останется в результате неотрицательным; если же значение семафора равно 0, то Р-операция должна ждать, пока какой-нибудь другой процесс не выполнит V-операцию. Р- и V-операции определены как примитивные, т. е. никакая другая операция не может изменять значение семафора одновременно с ними.

Такие операции легко моделируются сетью Петри, как показано на рис. 3.34. Каждый семафор моделируется позицией, количество фишек в позиции показывает значение семафора. Р-операция использует позицию семафора в качестве входа, V-операция — в качестве выхода.

Преимущество этого заключается в том, что многие системы проектируются и описываются с помощью Р - и V-операций.

Например, в операционной системе Venus  Р- и V-операции являются основным механизмом связи между процессами. Такие системы, следовательно, можно промоделировать сетями Петри.

Безопасность сетей Петри. Задача о взаимном исключении.

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

Определение 4.1. Позиция pi  P сети Петри С= (Р, Т, I, О)

с начальной маркировкой μ является безопасной, если μ(рi)  1 Для любой μ'  R(C, μ.). Сеть Петри безопасна, если безопасна каждая ее позиция.

Безопасность — очень важное свойство для устройств аппаратного обеспечения. Если позиция безопасна, то число фишек в ней равно 0 или 1. Следовательно, позицию можно реализовать одним Триггером.

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

Если позиция не является кратной входной или кратной выходной для перехода, ее можно сделать безопасной. К позиции *рi которую необходимо сделать безопасной, добавляется новая позиция p'i. Переходы, в которых pi используется в качестве входной или выходной, модифицируются следующим образом:

Если Pi  I(tj)   и  Pi   0(tj), тогда добавить p'i к 0(tj).

Если Pi  0(tj)   и  Pi   I (tj), тогда добавить р'i к I (tj).

Цель введения этой новой позиции pi — представить условие «рi пуста». Следовательно, pi и pi,    дополнительны; pi имеет фишку, только если рi- не имеет фишки и наоборот. Любой переход, удаля-

ющий фишку из рi должен помещать фишку в pi, а всякий переход, удаляющий фишку из pi, должен помещать фишку в pi. Начальная маркировка также должна быть модифицирована для обеспечения того, чтобы точно одна фишка была либо в либо в рi. (Мы допускаем, что начальная маркировка безопасна.) Заметим, что такая принудительная безопасность возможна только для позиций, которые в начальной маркировке являются безопасными и входная и выходная кратность которых равна О или 1 для всех переходов. Позиция, имеющая для некоторого перехода выходную кратность 2, будет получать при его запуске две фишки и, следовательно, не может быть безопасной. Простая сеть Петри на рис. 4.1 преобразована в безопасную, как показано на рис. 4.2.

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

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

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

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

Второй процесс вычисляет новое значение хn = g(x);

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

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

Результат вычисления первого процесса потерян, так как теперь значением разделяемого объекта является g(x), в то время как им Должно быть либо g(f(x)), либо f(g(x)). (Представьте себе, что g(x) — «снять со счета х 1000 долл.», f(x) — «поместить на счет х 1000 долл.», а процессы 1 и 2 — банковские операции.)

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

Эта задача может быть решена сетью Петри, как показано на рис. 3.28. Позиция T представляет собой разрешение для входа в критическую секцию. Для того чтобы какой-либо процесс вошел в критическую секцию, он должен иметь фишку в p1 или в р2 соответственно, свидетельствующую о желании попасть в критическую секцию, а также должна существовать фишка в t1, дающая разрешение на вход. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы t1 и t2 вступят в конфликт, и только один из них сможет запуститься. Запуск tt запретит переход t2, вынуждая процесс 2 ждать, пока первый процесс выйдет из своей критической секции и возвратит фишку обратно в позицию T.

Использование сетей Петри для моделирования процессов синхронизации. Задача Д.Питерсона. PERT-диаграммы и сети Петри. Примеры.

 

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

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

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

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

PERT-диаграмма и сеть Петри взаимосвязаны: PERT-диаграмма легко преобразуется в сеть Петри. Каждый этап PERT-диаграммы представляется позицией, причинно-следственные связи — переходами. Диаграмма на рис. 3.35 может быть преобразована в эквивалентную сеть Петри, изображенную на рис. 3.36.

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

Конвейерная обработка, описанная в разд. 3.3.2, является частным случаем производственной системы . Сборочная линия — другой пример производственной системы. Производственные системы и сборочные линии могут быть промоделированы сетями Петри.

Одно из первых применений сетей Петри — применение в качестве средства генерации оптимального кода для компилятора с [ Фортрана CDC 6600. Подход к решению этой задачи, предложенный , заключался в моделировании программы на Фортране | сетью Петри   способом,  подобным моделированию блок-схемы £(разд. 3.4.1). Затем отдельные операторы программы рассматривались с целью определения минимального набора причинно-следственных связей между операторами, позволяя исключать из сети • Петри некоторые из искусственно введенных ограничений на последовательность операторов программы. Эти искусственные ограничения введены из-за необходимости для программиста представлять программу на Фортране в виде последовательности, задающей полный порядок на множестве операторов, даже если требуется только частичное упорядочение. В качестве примера рассмотрим следующие три оператора:

10y=x+1 ,

20y=y+1,

30z=x+y.

Они написаны таким образом, что оператор 10 предшествует оператору 20, но такая последовательность вовсе необязательна. Порядок, в котором будут выполнены операторы 10 и 20 (или они будут выполнены одновременно), не имеет значения для программы. Однако оператор 30 должен следовать только после операторов 10 и 20. После изменения упорядочения операторов необходимо рассмотреть и поток управления. Этот анализ заключается в применении условий Бернстайна для обеспечения детерминированности.

Результатом такого анализа является сеть Петри, представляющая программу с минимальными ограничениями на последовательность операторов, т. е. допускающую максимальный параллелизм. Теперь задача состоит в компиляции такой программы. Это требует отображения переменных в регистры и упорядочения инструкций для получения полностью упорядоченной последовательности инструкций машинного языка.  CDC 6600 — это ЭВМ с несколькими регистрами и кратными функциональными блоками (разд. 3.3.3). Так как функциональные блоки могут выполнять различные инструкции параллельно, то очень важно порождать инструкции в порядке, максимально увеличивающем параллелизм при работе функциональных блоков. На это также влияет распределение переменных по регистрам. Сеть Петри, моделирующая программу и представляющая ограничения, налагаемые программой, объединяется с сетью Петри, моделирующей устройство управления CDC 6600 и представляющей ограничения, налагаемые аппаратным обеспечением. Такая объединенная сеть представляет все возможные последовательности инструкций, которые могут выполняться аппаратурой и реализовать алгоритм данной программы. Эта сеть затем выполняется для получения всех таких последовательностей инструкций. Две (или более) последовательности образуются вся кий раз, когда два (или более) перехода одновременно разрешены. Запуск одного перехода будет порождать одну последовательность; запуск другого перехода — другую. Например, сеть Петри на рис. 3.37 представляет последовательности abcdef, bacdef, abcedf, bacedf. После того как последовательности получены, вычисляются необходимые затраты времени на их выполнение, и наиболее быстрая последовательность генерируется компилятором для действительного выполнения.

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

Н2С204 →   2СОа + 2Н+ + 2е-

2е- + 2Н+ + Н202 → 2Н20.

Можно представить и реакции катализа. Соединение водорода и этилена образует этан (Н2 + С2Н4 → С2Н6) только в присутствии платины. Это отражено на рис. 3.39.

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

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

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

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

Ограниченность дерева достижимости

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

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

Рассмотрим, например, сети Петри на рис. 4.20 и 4.21, дерево достижимости которых изображено на рис. 4.22. Одно дерево достижимости представляет эти две схожие (но различные) сети Петри. Множества же достижимости их не совпадают. В сети Петри на рис. 4.20 число фишек в позиции р2 всегда четно (пока не будет запущен переход t1), тогда как в сети Петри на рис. 4.21 оно может быть произвольным целым. Символ t0 не позволяет обнаруживать информацию такого рода, препятствуя использованию дерева достижимости для решения задачи достижимости.

Аналогичная трудность существует и для задачи активности На рис. 4.23 и 4.24 приведены две сети Петри, дерево достижимости которых изображено на рис. 4.25. Однако сеть на рис. 4.23 может иметь тупик (например, в результате последовательности t1 t2 t3 )  а сеть Петри с рис. 4.24 — нет. Дерево достижимости же вновь не может передать различие этих двух случаев.

Заметим, что хотя дерево достижимости не обязательно содержит достаточную информацию для решения задач достижимости и активности, тем не менее в некоторых случаях это бывает возможно.

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

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

Ограниченность сетей Петри. Задача о производителе/потребителе.

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

Определение 4.2. Позиция рi P  сети Петри С= (Р, Т, I, О) с начальной маркировкой μ является k-безопасной, если μ'(рi)  к для всех μ'  R(C, μ).

1-безопасная позиция называется просто безопасной. Заметим, что граница k' по числу фишек, которые могут находиться в позиции, может быть функцией от позиции (например, позиция р1 может быть 3-безопасной, тогда как позиция р2 — 8-безопасной). Однако, если позиция pi k-безопасна, то она также и k'-безопасна Для всех k'  k. Поскольку число позиций конечно, можно выбрать ft, равное максимуму из границ каждой позиции, и определить сеть Петри k-безопасной, если каждая позиция сети k-безопасна.

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

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

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

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

В другом варианте задачи о производителе/потребителе используется буфер ограниченного размера. При такой постановке задачи буфер между производителем и потребителем ограничен, т. е. имеет только n ячеек для элементов данных. Следовательно, производитель не может постоянно работать с той скоростью, которая ему нужна, а вынужден ждать, если потребитель работает медленно и буфер заполнен. На рис. 3.31 показано решение этой проблемы. Ограниченному буферу сопоставляются две позиции: В представляет количество элементов данных, которые произведены, но еще не использованы (число заполненных ячеек), В' — количество пустых ячеек в буфере. Первоначально В' имеет n фишек, а В фишек не имеет. Если буфер заполнен, то В' фишек не имеет, а В имеет n фишек. Если теперь производитель попытается поместить еще один элемент данных в буфер, то он будет остановлен, так как в В' нет фишки, делающей этот переход разрешенным.

1


 

А также другие работы, которые могут Вас заинтересовать

21005. Расчет многовибраторных антенн 444.5 KB
  Рассчитать и построить диаграммы направленности системы из полуволнового вибратора и рефлектора. Ток рефлектора составляет 10%, 50%, 90% от тока вибратора и опережает ток вибратора по фазе на
21006. Антенны Радиорелейных Линий связи 188.5 KB
  Донецк 2011 Цель работы: расчет формы диаграммы направленности антенны по известному распределению амплитуд поля. Рассчитать диаграмму направленности параболической антенны с круглым раскрывом амплитуды поля в котором изменяются по закону Er=11r R02 со спадом поля на краях раскрыва относительно центра до =0. Определить коэффициент направленного действия зеркальной параболической антенны по условиям ЗАДАНИЯ 1 приняв значение коэффициента использования равным 05.
21007. Исследование рупорной антенны 95.5 KB
  Цель работы: исследование особенностей распространения радиоволн сантиметрового диапазона и экспериментальное снятие диаграммы направленности рупорной антенны.
21008. РАСЧЕТ ПАРАМЕТРОВ СИММЕТРИЧНОГО И НЕСИММЕТРИЧНОГО ВИБРАТОРОВ. Распределение тока Ix и заряда Qx 108 KB
  Каково распределение поля симметричного и несимметричного вибратора в зависимости от длины вибратора и длины волны. Основные характеристики симметричного и несимметричного вибратора. При каком отношении диаграмма направленности симметричного вибратора имеет боковые лепестки?
21009. РАСЧЕТ ХАРАКТЕРИСТИК И ПАРАМЕТРОВ ТЕЛЕВИЗИОННЫХ АНТЕНН 91.5 KB
  Затухание вносимое коаксиальным кабелем распределительной сети 5дБ фильтром сложения 95 дБ разветвительным устройством 105 дБ. Распределительное устройство имеет проходное затухание 05 дБ и переходное затухание 17 дБ. Полное затухание распределительной сети затухание вносимое коаксиальным кабелем распределительной сети плюс затухание вносимое фильтром сложения плюс затухание вносимое разветвительным устройством плюс полное затухание вносимое всеми распределительными устройствами плюс переходное затухание...
21010. Исследование особенностей распространения радиоволн сантиметрового диапазона и экспериментальное снятие диаграммы направленности рупорной антенны 307.48 KB
  Краткие сведения по теме Диаграмма направленности антенны представляет собой графическую зависимость напряженности электромагнитного поля созданного антенной от углов наблюдения в пространстве. Чтобы построить диаграмму направленности ДН характеристики поля измеряют на одинаковом достаточно большом расстоянии от антенны. Основные значения параметров антенны в режиме приема и передачи остаются неизменными следовательно диаграмма направленности антенны не зависит от того применяется антенна в качестве передающей или приемной т.
21011. МНОГОВИБРАТОРНЫЕ АНТЕННЫ 73.5 KB
  Пример: Рассчитать и построить диаграммы направленности системы из полуволнового вибратора и рефлектора. Ток рефлектора составляет 70 от тока вибратора и опережает ток вибратора по фазе на 90. Диаграмма направленности вибратора с рефлектором. Рассчитать и построить диаграммы направленности системы из полуволнового вибратора и рефлектора.
21012. АНТЕННЫ РАДИОРЕЛЕЙНЫХ ЛИНИЙ СВЯЗИ 79.5 KB
  1 Краткие сведения по теме Характеристики направленности поверхностных антенн определяются формой раскрыва и распределением поля в нем. Характеристики раскрыва в этом случае определяются следующими уравнениями: Уровень первого бокового лепестка 176 дБ =1. Амплитуды поля от центра к краям раскрыва рис. В приведенных формулах для круглого раскрыва ; J1u и J2u функции Бесселя первого рода соответственно первого и второго порядков.