Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 128
Текст из файла (страница 128)
1б.49 Вполне очевидно, что в конце концов все метки переместятся в рз, и процесс завершится. Процесс в сети Петри, изображенной на рис. 16.51, никогда не завершится, поскольку переход гг всегда разрешен. 'О Рис. 1б.бО Рис. 1б.б1 Сеть Петри на рис. 16.52 выполняет вычисления (а+6) х 1с+Н). Каждый из переходов гг или 1з может сработать первым; однако переход гз не будет разрешен, пока оба перехода гг и гз не сработают. 720 ГЛЯВЯ тб. Сети .+ь 'о--о- 'О (а+а) (с+4 Рис, 1б.б2 Рг Π—,О, " I ~Р5 ' О-' -'О-'-О л ,-0 1 Р1 / ~Р5 "О-' -'О-'-„О ,-О 1 Рис. 1б.бЗ Рис.
16.Б4 Состояние сети Петри, изображенное на рис. 16.55, достижимо из состояния сети Петри, изображенного на рис. 16.56, поскольку оно производится срабатыванием перехода 1,, а затем срабатыванием перехода 14. Рг Рг Рг Рис. 1б.бб Рис. !б.бб Состояние 15 называется непосредственно достижимым из состояния 15„ если срабатывание какого-либо перехода 1 в то время, пока сеть находится в состоянии Рг, приводит к состоянию 15 . Более формально, состояние 15, непосредственно достижимо из состояния (г„если существует переход 1 такой, что и а(15„1), Состояние 15, достижимо из состояния (г„если, начиная из состояния 15„ срабатывание последовательности переходов производит состояние Р ..
Состояние Гн достижимо из состояния Рг„если существуют состояния 151„151„,Р,„,, и переходы 11,1з,...,1, такие, что 151„, = б1(г,„,ть) для 14 = 1,2,...,т — 1. В частности, состояние, изображенное на рис. 16,53, непосредственно достижимо из состояния, изображенного на рис. 16.54, поскольку оно производится срабатыванием перехода 15. РЯЗДЕЛ 16.3. Сети Петри 721 Сеть Петри называется живой, если для любого состояния и и любого перехода 8 существует состояние и', достижимое из состояния и, так что переход 1 в состоянии и' является разрешенным. Таким образом, каким бы ни было текущее состояние, существует такая последовательность срабатывания переходов с началом в текущем состоянии, что любой заданный переход может сработать. Очевидно, что сеть на рис.
16.57 является живой. Одно из определений тупиковой сети Петри — сеть не живая. Следовательно, существует такое состояние, что если сеть Петри находится в этом состоянии, то один или более переходов могут никогда не сработать. Назовем это состояние частичным туваком. Будем говорить, что сеть Петри находится в тунике, если имеется состояние, в котором ни один из переходов не может сработать.
Таким образом, существует такое состояние Р, когда 5(Р,1) не определена для всех переходов ~. Рассмотрим стандартный пример, когда два процессора используют совместно два ресурса, например, принтер и память, каждый из которых не может быть использован ими одновременно. Если один процессор имеет доступ к принтеру, а другой — к памяти, то оба не могут завершить задания. Они также ие могут освободить используемый ресурс, поэтому система находится в тупике. Эта ситуация показана на рис. 16.58.
ресурс! — ~0 допуск допуск — — задание Ь ресурс й Рис. 15.55 Еще один пример, проблему обедающих философов, мы рассмотрим в упражнениях. Другая, с которой приходится сталкиваться при использовании сети Петри для совместного использования файлов, — это проблема взаимного исключения.
Предположим, что одновременный доступ двух людей к одним и тем же данным 722 ГЛАВА тб. Сети нежелателен. Так, недопустимо, чтобы один человек читал данные, а другой в это же время их изменял. Эта проблема решается путем взаимного исключения. Пока один человек работает с данными, для другого доступ закрыт.
Такая ситуация проиллюстрирована на рис. 16.59. Единственная метка в позиции с препятствует допуску другого субъекта до тех пор, пока метка не будет перемещена. субъектА субъект В с О Рис. !б.б9 Рис. /б.бО Сеть Петри называется безопасной, если каждая позиция содержит не более одной метки. Когда сеть Петри безопасна, в каждой позиции имеется либо одина метка, либо они отсутствуют вообще, поэтому помещение метки в позицию является бинарной операцией.
Для большинства моделей контроля необходима безопасная сеть Петри, поскольку наличие метки может означать протекание процесса, а ее отсутствие — сигнал о его остановке. Сеть Петри называется ограниченной, если количество меток в каждой позиции не превышает некоторое целое чиср, (» ) ло 1т. Ограниченная сеть Петри предоставляет возможность контроля проблемы переполнения. Очевидно, что безопасная цепь Петри — ограниченная. Сеть Петри, изображенная на рис. 16.60, ограниченной не является. В некоторых сетях Петри на вместимость позиций на- 'О кладываются ограничения, и по условию количество меток не может превышать эту вместимость. Сеть Петри называется коисереативмой, если общее число меток во всех позициях всегда постоянно.
В этом случае количество меток на входе каждого перехода равно количеству меток иа выходе перехода. Если метки описывают ресурсы, то консервативная сеть Петри гарантирует, что никакой ресурс не будет ни создан, ни утерян. Консервативная сеть Петри является очевидным образом ограниченной. Сеть Петри, изображенная на рис. 16.61, консервативна. РАЗДЕЛ 16.3. Сети Петри 723 ° УПРАЖНЕНИЯ 1. Какие из приведенных ниже сетей Петри а) являются безопасными? б) являются консервативными? в) являются ограниченными? г) имеют достижимым каждое состояние? д) являются живыми? е) имеют все текущие переходы разрешенными? ж) имеют переходы, которые могут быть разрешены в некотором состоянии, достижимом из текущего состояния? (й) (1) 724 ГЛАВА 16.
Сети 2. В сетях Петри (упражнение 1) найдите: а) все возможные состояния сети Петри; б) состояние после срабатывания перехода г1, в) состояние после последовательного срабатывания переходов г, и 1з, г) любое тупиковое состояние; д) любое частично тупиковое состояние. 3. Постройте пример сети Петри, в которой два перехода разрешены, но срабатывание каждого из них блокирует другой. 4. Постройте пример сети Петри, которая является безопасной, но не является живой. 5.
Постройте пример сети Петри с ограничением 4 6. Постройте пример сети Петри, которая является безопасной, но не является ограниченной. 7. Постройте пример сети Петри, которая является консервативной, но не является безопасной. 8. Постройте сеть Петри, которая эквивалентна сети, изображенной на рис. 16.58, но не является тупиковой. 9. Может ли консервативная сеть Петри быть тупиковой? 10. Приведите пример сети Петри, которая имеет состояние, недостижимое из исходного состояния. 11. Постройте сеть Петри, которая частино тупиковая, но не тупиковая. 12.
Проблема обедающих философов формулируется следующим образом: пять философов сидят за столом, чтобы есть и размышлять. В любой заданный промежуток времени они могут делать что-то одно. Философы едят китайское блюдо, используя палочки, поэтому для еды каждому необходимо иметь две палочки. Когда философы размышляют, палочки не нужны. На столе между двумя сидящими лежит одна палочка, т.е. всего пять палочек. Очевидно, что если философы одновременно возьмут правую палочку, то каждый будет лишен пищи. Постройте сеть Петри, моделирующую эту задачу, которая не была бы тупиковой, т.е. когда философ будет приниматься за еду, у него для этого будут две палочки по обе стороны от него.
726 О! АНА 17. теория вычислений Если алфавит А=(1,0), то следующие множества являются языками. 1 = (О, 1, ОО, И, ООО, Ш,...); Т,з = (ю; ю Е А" и содержит точно одну цифру Ц; Тз = (ю: ю е А' и содержит точно две цифры Ц; 7,4 = (ю: ю Е А" и содержит не мене двух цифр Ц. Если алфавит А = (а, Ь, с), то следующие множества являются языками. Ег = (асЬ, аасЬЬ, ааасЬЬЬ,...); 7 з = (ю: ю = а"Ь" для п > Ц; Тз = (ю: ю Е а"Ь для гп, и > Ц; 14 = (ю: ю Е А' и не содержит последовательных одинаковых букв) .
ОПРЕДЕЛЕНИЕ 17.4. Пусть 5 — подмножество множества А . Тогда Я множество всех строк или слов, образованных конкатенацией слов из множества Я, т.е. Я' = (югюз... ю„: ю; Е Я). Символ ' называется звездой Клини в честь математика и логика Стивена Коула Клини. Заметим, что данное определение согласовано с определением множества А".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
