Раздел 12. Теория вычислительных процессов

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

Алфавит - конечное множество имен событий, выбранных для описания объекта. Алфавит считается заранее определенным свойством объекта и постоянным.

При выборе алфавита абстрагируются от:

1) Не рассматривается множество несуществующих событий;

2) Событие происходи мгновенно (элементарное действие);

3) Отсутствует точная привязка событий ко времени.

Процесс – поведение объекта, описанное в терминах определенного набора событий, выбранного в качестве его алфавита. Малые прописные – имена событий; Заглавные – имена процессов; алфавит некоторого процесса – а.

Способы описания:

1) Префиксы (предваренные описания объектов):

х—>P (P за x) – описывает объект, который в начале участвует в событии x, a затем ведет себя в точности как P.

а (х—>Р)= аР, при условии х э аР – описание процесса с использованием префикса. Используется для описания процесса который рано или поздно останавливается.

2) Рекурсия: Часы=(тик—>Часы) – метод рекурсивного описания процесса. Будет правильно работать, если в правой части уравнения рекурсивному вхождению процесса предшествует хотя бы одно событие;

3) Выбор: x—>P|y—>Q – описывает объект, который в начале участвует в одном из событий x или y. Дальнейшее поведение объекта описывается процессом P, если первым произошло событие x, и Q – если первым произошло событие y.

Св-ва процессов:

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

аP=аQ – если алфавит Р совпадает с алфавитом Q, то P||Q – процесс ведущий себя как система составленная из процессов Р и Q, взаимодействие между которыми пошагово синхронизировано.

Законы:

1) Симметричность P||Q = Q||P;

2) Ассоциативность P||(Q||R) = (P||Q)||R;

3) Деблок (тупик всей системы процессов) P||СТОП а p = СТОП а p;

4) Пара процессов либо одновременно выполняют одно и тоже действие, либо попадает в состояние дедлока, если начальные состояния процессов не совпадают:

(c—>P||c—>Q)—>(c—>(P||Q))

(c—>P||d—>Q)—>СТОП (c!=d)

2) Синхронность. аP!=аQ – когда такие процессы объединены для совместного исполнения, то события, содержащиеся в обоих алфавитах требуют одновременного участия P и Q. Множество всех логически возможных для данной системы событий есть объединение алфавитов, составляющих её процессы:

A(P||Q)=аP u aQ

3) Недетерминизм. Когда процесс обладает некоторым спектром поведения, а его окружение не имеет возможности влиять на выбор, то выбор осуществляется произвольным (недетерминированным) образом. Одна из главных причин введения недетерминизма – абсрагироваться от некоторых деталей реализации.

P П Q – недетерминированные процессы P и Q

Законы:

1) Идемпотентность Р П Р = Р

2) Симметричность P П Q = Q П Р;

3) Ассоциативность P П (Q П R) = (P П Q) П R;

4) Дистрибутивность x—> P П Q = (x—>P) П (x—>Q)

Алгебра над процессами

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

<x,y> – в протокол для событий x,y

Свойства протоколов и операции над ними:

1) Конкатенация – строит новый протокол из пары операндов, соединяя их в указанном порядке. <n1>^<n2>=<n1,n2>

2) Сужение –протокол t суженный на множество символов A. Он строится из t отбрасыванием всех символов, не принадлежащих A (операция строго дистрибутивна).

3) S0 – голова; S| – хвост; <x,y,x>0 = x; < x,y,x >| = <y,x>

4) Итерация А* – набор всех конечных протоколов, включая <>, составленных из элементов множества А.

5) Длина протокола #S (примеры: #<>=0, #<x,y,x>=3)

6) Число вхождений символа x в протокол S S[стрелка вниз]x

Автомат – математическая модель процесса.

V={v1,v2..vk}– конечное множество входных символов (входной алфавит);

W= {W1,w2..wm} – выходной алфавит;

Q={q1,q2..qn} состояния автомата.

При рассмотрении автомата рассматривается отображение множества входных сигналов на множество выходных

Если Q конечно, то автомат называется конечным (с конечной памятью). Автомат с 1м состоянием – тривиальный.

Лямбда(q,v)– функция перехода; Мю(q,v)– функция выхода.

Автоматы:

1) синхронные и асинхронные

2) конечные и бесконечные

3) детерминированные и недетерминированные

Автомат Мили:

Омега(t)=мю[q(t),v(t)] – определение входного сигнала с привязкой по времени.

Поведение автомата в любой момент времени зависит от q и v. Можно устранить время и выразить выходную формулу так:омега(t)=мю(q,v)

Общая запись авт. Мили: А=<V,W,Q,лямбда, мю, q0>, где V, W ,Q – алфавит входных и выходных символов состояний; лямбдаб мю – функции переходов и выходов; q0 – начальное состояние.

Можно вычислить реакцию автомата в виде последовательности выходных символов.

Автомат Мура:

омега(t)=мю(q)Частный случай автомата Миле.

омега=мю(q,v)=мю~(q~)– Функция выхода (тильда у симолов сверху)

q~(t+1)=лямбда(q~,v~)– Функция переходов

61. Основы специальной теории сетей: синтаксис и семантика сетей Петри, модельная и предметная интерпретация, определение, способы задания сетей Петри, понятие выполнения сети, основные соглашения выполнения сети, пространство состояний, множество и граф достижимости, динамические свойства сетей, анализ сетей; сетевая объектная модель процессов, ее особенности и отличие от автоматной модели.

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

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

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

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

Под сетью будем понимать тройку (P, T, F), где

P – непустое множество элементов сети, называемых местами;

T – непустое множество элементов сети, называемых переходами;

F – функция инцидентности, задающая связи между элементами множеств P и T, и для (P, T, F) выполнены следующие условия:

PхТ=пустое множество(множества мест и переходов не пересекаются);

любой элемент сети инцидентен хотя бы одному элементу другого типа.

Сеть Петри - это набор PN = (P, T, F, M0), где (P, T, F) - конечная сеть (множества P и T конечны), а I0 - функция начальной разметка сети, которая сопоставляет любому месту pi I P некоторое число M0(p)=n.

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

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

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

Свойства и анализ, динамические свойства сетей:

1) Безопасность – число фишек в сети не превышает 1;

2) К-безопасность – число фишек в сети не превышает к;

3) Сохраняемость – используется при моделировании распределении ресурсов в системе, фишки не исчезают и не создаются;

4) Активность – используется при моделировании распределении ресурсов, когда возможна тупиковая ситуация

Количество фишек в позициях сети Петри в момент времени t – есть пространство состояний в сети.