Абстрактные конечные автоматы 1-го и 2-го рода. Матрицы переходов и выходов. Представление графом.

Абстрактный автомат задается как совокупность шести объектов:

- множества входных сигналов Х (входной алфавит автомата);

- множества выходных сигналов Y (выходной алфавит автомата);

- множества состояний автомата А;

- элемента а₀ Î А, называемого начальным состоянием автомата;

- функций переходов j(а,x) и выходов y(а,x), задающих однозначные отображения множества (а,x), где а Î А и x Î X, в множества А и Y.

Закон функционирования автомата первого рода задается уравнениями вида:

а(t)= j[а(t-1), x(t)]; y(t)=y[а(t-1), x(t)]; t=1,2,...;

(7)

Закон функционирования автомата второго рода:

а(t)= j[а(t-1), x(t)]; y(t)=y[а(t), x(t)]; t=1,2,...

(8)

В практике используют:

- автомат Мили: произвольный конечный автомат первого рода;

- автомат Мура: частный случай конечных автоматов второго рода, у которого функция выходов y(а,x) не зависит от переменной х.

Автомат называется конечным если конечно число его состояний. Автоматы задают табличным способом или направленным графом. В первом случае строят матрицы переходов и выходов. Строки обеих этих таблиц обозначаются входными сигналами автомата, а столбцы – его состояниями. На пересечении строки и столбца таблицы переходов ставится соответствующее значение функции переходов j(а,x), а в таблице выходов – значение y(а,x). Для автомата Мура сдвинутая таблица выходов сводится к одной строке, поэтому часто в таблице переходов над каждым состоянием а_i автомата, обозначающим тот или иной столбец таблицы, ставят соответствующий этому состоянию выходной сигнал j (а_i,x) = y(а_i).

При задании автомата с использованием направленного графа вершины графа отождествляются с состояниями автомата, а стрелки – с выходными сигналами. Если входной сигнал x_i вызывает переход автомата из состояния а_j в состояние а_k, то на графе автомата этому сигналу соответствует помеченная буквой x_i стрелка, соединяющая вершину, соответствующую состоянию а_j, с вершиной, соответствующей состоянию а_k. Для задания функции выхода ребра графа также помечаются соответствующими выходными сигналами. Если обозначенная входным сигналом x_i стрелка соединяет вершину а_j с а_k, то в случае автоматов первого рода ей предписывается выходной сигнал y(а_j,x_i), а в случае автоматов второго рода – выходной сигнал y(а_k,x_i) (см. рис. 12).

 

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

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

Сети Петри функционируют в непрерывном времени. Динамика функционирования определяется правилами срабатывания переходов. Изменение состояния сети связано с механизмом изменения маркировок позиций. В случае простой временной сети Петри:

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

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

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

Элементарный цикл обслуживания моделируется простой временной сетью Петри, представленной на рис. 16.

С переходами на рис. 16 связаны времена выполнения следующих действий: t₁ –поступление заявки на обслуживание во входную очередь; t₂ – начало обслуживания; t₃ – конец обслуживания; t₄ –выход заявки из цикла обслуживания. Позиции этой сети Петри соответствуют условиям: Р₁ – наличие заявки, ожидающей обслуживания, во входной очереди; Р₂ – наличие заявки на обслуживании в процессоре; Р₃ – процессор свободен; Р₄ – наличие обслуженной заявки в выходной очереди. Маркировка сети Петри, показанной на рис. 16, соответствует начальному состоянию системы обслуживания: заявок, ожидающих обслуживание, во входной очереди нет, и процессор свободен (вершина P₃ содержит метку).

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

Маркировка, показанная на рис. 17, соответствует следующему состоянию: заявка ожидает обслуживания и процессор свободен: вершины Р₁ и P₃ содержат метки, и, следовательно, переход t₂ активизирован.

 

 

Ингибиторные сети Петри. Моделирование элементарного цикла обслуживания ингибиторной сетью Петри. Пример моделирования системы или процесса ингибиторной сетью Петри.

Особой разновидностью сетей Петри являются ингибиторные сети, которые в дополнение к обычным дугам (ветвям) графа сети содержат запрещающие, так называемые ингибиторные ветви. Такая ветвь запрещает активацию перехода при наличии достаточного количества меток во входных вершинах обычных дуг до тех пор, пока в ее входной вершине имеются метки. Во фрагменте сети Петри, приведенном на рис.22-а, ветвь а запрещает запуск перехода t₁ при наличии метки в позиции P₁. Пример реализации простейшего цикла обслуживания с использованием ингибиторной сети Петри представлен на рис.22-б. Здесь переход t₂ при наличии метки в позиции Р₂ будет «заперт» не смотря на наличии метки в вершине Р₁ до тех пор, пока метка не покинет Р₂ через переход t₃, что эквивалентно завершению очередного обслуживания.

Сеть Петри для моделирования магистрального канала передачи данных. Пусть к общему каналу связи подключены N абонентов и возможна связь любых абонентов друг с другом. Абонент-отправитель осуществляет попытку связи в случайный момент времени Т₁. Если канал занят передачей информации от другого абонента, это обнаруживается по наличию сигналов несущей частоты в канале связи. Абонент задерживает передачу на время t₁, являющееся реализацией равномерно распределенной в заданном диапазоне случайной величины t. Если в момент времени (Т₁+t₁) канал связи опять занят, то передача задерживается по тому же правилу. Если два абонента или более пытаются начать передачу одновременно, возможны конфликты. Одновременность описывается условием DТ<e, где DТ – промежуток времени между моментами начала передачи данных различными абонентами, e>0. При конфликте передача начинается, но передаются искаженные данные. Ликвидация конфликта заключается в том, что все абоненты, начавшие одновременно передачу данных, прекращают ее и пытаются начать работу через промежуток времени, индивидуальный для каждого абонента и являющийся функцией t.

В модельной реализации (см. рис. 23) источник (открытый переход t₂) имитирует поток заявок на передачу от всех абонентов. Если канал свободен и конфликта нет, заявка проходит через t₃, t₆, t₇, t₁₀, t₁₁ и выходит из системы обслуженной, причем в t₆ происходит задержка на время e, а в t₁₀ - на время (Т_п-e), где Т_п – время передачи пакета.

Если канал занят (заявка задержана в t₁₀), то попытка другого абонента начать передачу приводит к прохождению заявки по маршруту t₃, t₆, t₉, и далее в один из переходов t₁₂..t_n. Срабатывание перехода t₉, а не t₇, происходит потому, что предыдущая заявка, прошедшая через t₇ и еще не вышедшая из t₁₀, изъяла метку из позиции р₉. Тем самым переход t₇ оказался запрещенным, а t₉ разрешенным.

Переходы t₁₂...t_n моделируют задержку пакетов на время t_i. Через время t_i заявка переходит к р₃, т. е. предпринимается новая попытка передачи сообщения. Конфликты возникают, если новая заявка приходит в позицию р₃, когда предыдущая еще не покинула переход t₆. Поэтому метка не может пройти переход t₃, но может пройти через переход t₄ в позицию р₆. Теперь вышедшая из t₆ заявка сможет пройти через t₈ на переходы t₁₂...t_n, где обе заявки будут задержаны на случайные отрезки времени перед повторными попытками передачи. Чтобы метка из р₈ перешла в t₈, а не в t₉, ветви, ведущей в t₈, присваивается более высокий приоритет. Переход t₅ срабатывает в случае, если в конфликт вошло более двух заявок [3, 20-23].

 

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

Для моделирования средств вычислительной техники и процессов обработки информации используются разновидности сетей Петри, различающиеся способами разрешения конфликтов. В стохастических сетях Петри дополнительно вводятся случайные задержки или вероятности срабатывания активных переходов. В примере на рис. 21-а сработает либо переход t₁ (c вероятностью р₁), либо t₂ (c вероятностью 1 -р₁). В приоритетных сетях конфликтные ситуации разрешаются введением различных приоритетов для ветвей. Конфликт, показанный в примере на рис. 21-б, всегда будет разрешаться в пользу перехода t₁, так как он имеет приоритет, а переход t₂ сможет сработать только в том случае, если, при наличии меток в вершинах Р₂ и Р₃, метки в вершине Р₁ не окажется.

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

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

Сеть Петри, реализующая заданную СМО, имеет вид, представленный на рис. 103.

 

Вершина	Описание
P1	Наличие заявок во входной очереди (количество меток соответствует количеству заявок)
P2	Наличие пакета по 10 на обслуживании во втором процессоре
P3	Наличие пакетов по 2 на обслуживании в первом процессоре (количество меток соответствует количеству параллельно обслуживаемых пакетов)
P4	Наличие в выходной очереди (счетчике) обслуженных пакетов по 10 (количество меток соответствует количеству пакетов)
Р5	Наличие в выходной очереди (счетчике) обслуженных пакетов по 2 (количество меток соответствует количеству пакетов)