Задачи и упражнения по главе 2

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

2. Составьте СП для моделирования очереди (правило работы, FIFO) из трех ячеек.

Решение показано на рисунке 4.1. Здесь обозначено:

р₀ - буфер входных заявок;

р₇ - буфер обслуженных заявок;

p₈ - разрешение разгрузки выходного буфера:

Р₂, Р₄, Р₆ - ячейки очереди свободны;

Р₁, р₃, р₅- ячейки очереди заняты;

t₀ - загрузка входного буфера;

t_i - начало обслуживания заявки i-й ячейкой (i=l, 2, 3);

t₄ - загрузка выходного буфера:

t₅ - разгрузка выходного буфера.

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

3. На основе решения задачи 2 составьте СП для моделирования стека из 3 ячеек (правило работы LIFO).

4. На основе решения задач 2 и 3 составьте СП для моделирования дека из 3 ячеек (примечание: дек - это очередь с двусторонним движением, загрузка и выгрузка происходит с о6оих концов).

5. Решите задачу 2 с использованием ингибиторных связей.

6. Составьте СП для моделирования одноколейной кольцевой железной дороги из 5 участков и 5 станций, по которой в одном направлении движутся два поезда.

7*. Составьте обыкновенную СП и дерево всех маркировок в задаче о мудрецах для N = 3 (п. 2.3). Выпишите все слова свободного языка СП, определите инварианты позиций и инварианты переходов (п.2.6).

8*. Модификация задачи о мудрецах (п. З.1.). Составьте СП для этой ситуации при условии, что палочки складываются в одну коробочку и извлекаются из нее следующим образом:

а) по одной;

б) по две;

в) сперва мудрец берет правую палочку, затем левую, а освобождает палочки одновременно.

Составьте дерево маркировок для каждого из указанных случаев (N = 3), определите инварианты позиций и инварианты переходов (п.2.6).

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

10. В предыдущей задаче учесть конечную емкость бутылки - 5 порций.

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

12. Решите с использованием раскрашенных СП:

а) задачу 10;

б) задачу 11.

13. На сборочной площадке собирается изделие, состоящее из одной детали типа А, трех деталей типа В и двух деталей типа С. Детали поступают извне и хранятся накопителях, емкость которых для А составляет 3, для В - л для С - 5 узлов. Составьте модель движения деталей и изделия

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

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

14. Цех выпускает изделие, которое помещается на склад емкостью 5 изделий, а со склада поступает потребителям. При наполнении склада прием заявок на изготовление изделий прекращается. Составьте модель системы цех - склад - потребитель:

а) с помощью обычной СП. Составьте граф маркировок при начальном состоянии: склад и цех свободны;

б) с помощью СП с ингибиторными связями.

15. Приведите примеры раскрашенных сетей Петри и их описания в нотации К. Йенсена, которые реализуют следующие расширения обыкновенных СП:

а) с ингибиторными связями;

б) с приоритетами;

в) со случайным срабатыванием переходов;

г) самомодифицируемые (кратность дуг зависит от номера шага).

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

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

а) сумма а+b;

б) произведение а х b;

в) min (a, b):

г) max (a, b);

1 при x ≥ 1

д) sg(x) =;

0 при х = 0

е) «сокращенное» вычитание:

|y-x|, если y ≥ x

у — х =;

0, если y < х

ж) целочисленное деление а на b: у = div(a.b);

з) остаток от деления a на п: res(a, n).

18. Составьте СП, моделирующую работу RS - триггера.

19. Составьте СП, моделирующую работу триггера со счетным входом.

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

21. Решите задачу 20 для троичной системы.

22. Составьте СП, моделирующую работу 3-разрядного двоичного счетчика.

23. На основе рисунка 2.21 составьте СП, моделирующую семафор, имеющий три значения: 0, 1, 2 и управляющий работой трех процессов.

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

а) Y: = А*Х, где X, Y -2- вектора, А - 2 х 2 матрица;

б) А: = В* С, гдеА, В, С-2x2 матрицы;

в) С: = det(А), где А - симметричная 3x3 матрица;

г) С: = А + В, где А, В, С -2x2 матрицы;

д) вычислить сумму элементов массива, состоящего из 5 элементов;

е) вычислить суммуквадратов элементов массива состоящего из 3 элементов.