О моделирующих возможностях сетей Петри

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

Однако важен и вопрос о том, насколько широкий класс объектов могут моделировать сети Петри. В п. 2.1.3. говорилось о свободном языке сети Петри, который представляет собой некоторое подмножество всех слов в алфавите T. Множество свободных языков всех сетей Петри образует класс свободных языков сетей Петри.

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

Помеченную сеть Петри можно рассматривать как генератор слов и изучать ее возможности с точки зрения математической лингвистики.

Рассмотренные в п. 2.1.5. расширения сетей Петри порождают другие классы языков.

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

В монографии В.Е. Котова [4] доказываются следующие утверждения:

1. Класс помеченных сетей Петри строго мощнее класса конечных автоматов и строго менее мощен, чем класс машин Тьюринга.

2. Классы ингибиторных сетей и сетей с приоритетами строго мощнее класса сетей Петри и равномощны классу машин Тьюринга.

3. Класс раскрашенных сетей при конечном количестве цветов равномощен классу сетей Петри.

4. Класс самомодифицируемых сетей эквивалентен классу ингибиторных сетей и сетей с приоритетами.

Лабораторная работа № 6 Моделирование систем с помощью
раскрашенных сетей Петри

 

Цель работы:

- освоить основные формализмы раскрашенных сетей Петри (CPN).

- научиться составлять формальное описание CPN.

- разработать программу и провести исследование заданной сети путем построения дерева маркировок.

Содержание работы

1) Изучить теорию CPN по учебнику (п.2.2) или по лекциям.

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

3) Разработать программу моделирования динамики CPN.

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

5) Построить эквивалентную обыкновенную PN и с помощью разработанной в Лабораторной работе №1 программы получить для нее фрагмент дерева маркировок.

Оформление работы

Оформленный отчет по лабораторной работе должен содержать:

· титульный лист с указанием фамилий исполнителей, группы и номера варианта;

· задание по работе;

· схему CPN;

· формальное описание CPN;

· дерево маркировок CPN;

· схему эквивалентной обыкновенной PN;

· дерево маркировок обыкновенной PN, полученное с помощью программы;

· листинг программы моделирования CPN.

Задача 1

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

Дополнительные условия:

1. Детали поступают на сборку по одной в определенном порядке: сперва типа , затем типа , затем типа .

2. Детали поступают на сборку комплектами:  деталей типа ,  - типа ,  - типа .

Варианты заданий

№ варианта	K	M	N	S	Дополнительное условие
1	1	2	3	2	1
6	2	3	3	3	2
11	2	4	6	3	1
16	4	6	6	2	2
21	3	5	6	3	1

 

Задача 2

Система массового обслуживания содержит два типа устройств:  и  и выполняет заявки  видов. Устройств  -  экземпляров, устройств  -  экземпляров. Заявки поступают извне буфер заявок и обслуживаются в указанном ниже порядке, обслуженные заявки выводятся из системы.

Устройство типа  обслуживает все заявки, устройство типа  - только заявки первого и k -го видов.

Дополнительные условия:

1. Заявки поступают произвольном порядке, а выводятся из системы в том же порядке, что и поступили.

2. Заявки имеют приоритеты: сперва обслуживаются все находящиеся в буфере заявки первого вида, затем все заявки второго вида и т.д.

Варианты заданий

№ варианта	nA	nB	k	Дополнительное условие
2	1	2	4	2
7	2	1	3	1
12	3	2	2	2
17	2	2	3	2
22	3	2	3	1

 

Задача 3

Система распределенной обработки информации состоит из главного процесса M (Master) и N подчиненных процессов (Slave) S ₁,…, S_N. Перед началом работы M посылает всем подчиненным процессам запрос на тестирование и продолжает работу только с теми из них, кто прислал положительные ответы на тесты.

Работа заключается в обмене сообщениями: M посылает процессу S_i n_i сообщений в синхронном или асинхронном режиме (т.е. с приемом «квитанций» о получении сообщения или без нее).

Порядок обмена сообщениями может быть:

1. произвольный;

2. в порядке возрастания номеров S_i;

3. все сообщения, относящиеся к S_i, передаются подряд;

4. режим обмена синхронный;

5. режим обмена асинхронный.

Варианты заданий

№ варианта	N	Количество сообщений				Порядок обмена
		n1	n2	n3	n4
3	3	5	2	3	-	1, 4
8	2	5	4	-	-	1, 3, 5
13	4	3	3	3	2	2, 4
18	3	4	4	2	-	2, 3, 5
23	2	4	3	-	-	2, 5

 

Задача 4

По компьютерной сети передается сообщение от отправителя S (Sender) к получателю R (Receiver). Сообщение разбито на M пакетов p_i (i =1,…, M), в сети существует N маршрутов передачи m_j (j =1,…, N). Каждый пакет p_i может быть передан по любому из маршрутов m_j, причем скорость передачи может быть различной.

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

Дополнительные условия:

1. Емкость буфера получателя R, составляет K пакетов. При наполнении буфера получатель R прекращает прием пакетов.

2. То же, что и в п. 1, но при наполнении буфера отправитель S прекращает посылку пакетов.

3. Пакеты передаются по одному, и передача очередного пакета p_{i +1} возможна только после получения «квитанции» о приеме предыдущего пакета p_i.

Варианты заданий

№ варианта	M	N	k	Дополнительные условия
4	8	3	5	1
9	6	2	3	1, 3
14	10	4	5	2
19	8	3	4	2, 3
24	10	2	5	3

Задача 5

Арифметическо-логическое устройство процессора содержит конвейер команд, состоящих из N видов функциональных устройств и обеспечивающий выполнение M различных команд (см. п. 2.3.1). Некоторые функциональные устройства могут дублироваться, в этом случае они работают параллельно. При поступлении из ОЗУ команды определенного типа конвейер настраивается на ее выполнение и пропускает операнды последовательно через все функциональные устройства. Если следующие команды имеют тот же тип, то конвейер не перестраивается, а выполняет их в прежнем режиме, загружая последовательно все функциональные устройства. При поступлении команды другого типа ее выполнение блокируется до тех пор, пока не будет завершено выполнение предыдущих команд, и конвейер не освободится. После этого происходит перестройка конвейера на новый тип команд и работа по описанному выше алгоритму.

Принятые допущения:

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

2. При прохождении команд через дублированные функциональные устройства не должна нарушаться их очередность – правило FIFO.

3. Необходимо составить начальную маркировку, соответствующую тестовой последовательности команд.

Варианты заданий

№ варианта	Число типов ФУ N	Число типов команд M	типы и количество функциональных устройств
			1	2	3	4
5	4	2	1	1	2	1
10	3	2	1	2	1	-
15	3	3	1	2	1	-
20	4	3	1	1	2	1
25	4	2	1	2	1	1

Контрольные вопросы

1 Назовите основные принципы работы цветных сетей?

2 Как определяется тип цвета в CPN?

3 Какие функции вы использовали в своей лабораторной работе?

4 Как задается начальная маркировка в цветной сети?

5 Как меняется правило срабатывания для цветных сетей?

6 Использование переменных в цветных сетях.

Лабораторная работа № 7. Исследование  раскрашенных сетей Петри
с временным механизмом

Цели работы

- освоить описание и особенности функционирования раскрашенных сетей Петри с временным механизмом (timed CPN - TCPN).

- создать программу моделирования TCPN.

- освоить методику имитационного моделирования системы, описанной с помощью TCPN.

Содержание работы

1) Изучить описание и особенности функционирования TCPN по учебнику (2.2.4 п. 2) или по лекциям.

2) Расширить возможности CPN, созданной в Лабораторной работе №6 за счет введения временного механизма. Для этой цели ввести случайные времена задержки срабатывания переходов.

3) Модифицировать программу созданную в Лабораторной работе №6, путем учета времени задержки срабатывания переходов.

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

Оформление работы

Оформленный отчет по лабораторной работе должен содержать:

· титульный лист с указанием фамилий исполнителей, группы и номера варианта;

· задание по работе;

· схему CPN с временными отметками;

· результаты имитационного моделирования;

· листинг программы моделирования TCPN.

Задача 1

В системе, рассмотренной в Лабораторной работе №6, учесть следующие временные задержки (в часах).

Варианты заданий

№ варианта	Задержка поступления деталей			Время сборки узла	Время передачи на склад	Время реали зации
	A	B	C
1	1.0±0.5	0.5±0.2	0.7±0.3	2.0±1.0	1.0±0.5	5±1.0
6	1.5±0.5	1.0±0.3	0.5±0.2	2.0±0.5	1.0±0.5	4±1.0
11	2.0±0.5	1.5±0.5	0.6±0.2	1.5±0.2	1.5±0.7	6±1.5
16	1.5±0.5	1.0±0.5	0.7±0.3	1.5±0.5	1.0±0.3	5±1.5
21	2.0±0.5	0.7±0.2	1.0±0.4	2.5±0.5	2.0±0.5	4±1.0

 

1. Провести имитационное моделирование процесса выпуска и реализации 200 изделий, суммируя временные задержки на каждом этапе процесса.

2. Оценить среднее время изготовления и реализации одного изделия и его дисперсию.

3. Оценить наиболее «узкое место» в процессе производства и реализации.

 

Задача 2

В системе, рассмотренной в Лабораторной работе №6, учесть следующие временные задержки (в секундах).

Варианты заданий

№ варианта	Время обслуживания заявок				Время вывода заявки из системы
	m1	m2	m3	m4
2	1.0±0.5	1.0±0.3	0.5±0.2	1.5±0.3	1.2±0.5
7	1.5±0.3	1.0±0.2	0.7±0.3	1.0±0.3	0.3±0.5
12	1.0±0.3	2.0±0.5	1.5±0.3	-	1.2±0.5
17	0.5±0.1	0.7±0.2	-	-	1.0±0.3
22	1.0±0.3	1.5±0.3	0.8±0.2	-	1.5±0.4

 

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

2. Оценить среднее время обслуживания одной заявки и его дисперсию.

 

Задача 3

В системе, рассмотренной в Лабораторной работе №6, учесть следующие временные задержки (в секундах).

 

Варианты заданий

№ варианта	Время передачи M-Si	Время передачи Si-M	Время тестирования
3	1.0±0.5	-	0.5±0.1
8	1.5±0.5	0.5±0.1	0.6±0.1
13	1.0±0.3	-	0.5±0.2
18	0.8±0.2	0.5±0.2	1.2±0.3
23	0.9±0.3	0.6±0.2	1.0±0.4

 

 

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

2. Для каждого из процессов S_i оценить среднее время одного обмена и его дисперсию.

 

Задача 4

В системе, рассмотренной в Лабораторной работе №6, учесть следующие временные задержки (в миллисекундах).

Варианты заданий

№ ва-ри-ан-та	Время передачи пакета по маршруту mi				Время передачи «квитанции» mi				Время вывода одного пакета из буфера
	1	2	3	4	1	2	3	4
4	100±50	150±50	200±30	-	100±10	100±25	100±15	-	10±2
9	150±30	300±50	-	-	75±10	150±25	-	-	15±5
14	500±90	300±50	200±50	150±30	200±50	100±25	100±25	50±15	10±2
19	400±50	150±40	300±30	-	200±25	75±20	150±20	-	5±1
24	200±30	100±30	-	-	150±10	50±10	-	-	7±2

 

1. Провести имитационное моделирование процесса передачи 100 сообщений, каждое из которых состоит из 8 пакетов.

2. оценить среднее значение и дисперсию времени передачи одного пакета.

 

Задача 5

В системе, рассмотренной в Лабораторной работе №6, учесть следующие временные задержки (в микросекундах).

Варианты заданий

№ варианта	Время работы функционального устройства				Время передачи между ФУ	Время перена-стройки конвейера
	1	2	3	4
4	10±2	15±3	30±5	10±3	5±2	10±3
9	12±2	25±3	15±3	-	6±2	12±3
14	14±2	30±5	12±3	-	4±1	14±3
19	12±3	15±5	35±5	12±2	5±2	12±2
24	10±3	30±3	10±2	10±2	5±3	12±3

 

1. Сформировать поток из 200 команд различных типов и «пропустить» их через конвейер.

2. Оценить среднее время выполнения одной команды и сравнить его с номинальным временем выполнения (сумма времен работы всех ФУ плюс сумма времен на передачу данных между ФУ).

 

 

Контрольные вопросы

1 Как моделируются в CPN-Tools сети с вероятностными переходами и сети с приоритетами?

2 Как определяется комбинированные типы цветов в CPN?

3 Какие функции вы определили сами в своей лабораторной работе?

4 Как моделируются ингибиторные сети в CPN?

5 Можно ли в CPN-Tools моделировать иерархические сети?

6 В чем суть сетей с временным механизмом?