автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Исследование последовательно-параллельных сценариев в сетях Петри и разработка методов их поиска

Введение.

2. Графическая интерпретация свойства независимости процессов в графе переходов сети Петри.

2.1. Определение сети Петри и ее графа переходов.

2.2. Сеть Петри для интерфейса шины и ее граф переходов.

2.3. Другое представление внутреннего подграфа.

2.4. Операция «перемешивания». Независимость.

Решетки.

В связи с развитием вычислительной техники и микроэлектроники системы управления находят все более и более широкое применение.

Несмотря на разнообразие таких систем, в них можно выделить ряд общих черт:

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

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

2. Так как в дискретной модели множество состояний является дискретным, то можно определить множество элементарных (единичных) действий, переводящих модель из одного состояния в другое.

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

В [1] одной из важных характеристик поведения системы управления называется согласованность - «свойство, отражающее причинно-следственные взаимодействия». С точки зрения дискретной модели с выделенным множеством элементарных действий это свойство организует упорядоченные цепочки таких действий, где действия-следствия стоят строго после действий-причин. В итоге каждая компонента модели может иметь одну или несколько цепочек действий, описывающих варианты ее функционирования (в зависимости от поведения или состояния других компонент). В данной работе такие упорядоченные последовательности единичных действий называются процессами. Таким образом, можно сказать, что процесс - это некоторое характерное сложное (составное) событие, которое может произойти, но не обязательно происходит.

Другой естественной чертой технических систем в [1] названа параллельность или асинхрониость, определяемая как инвариантность поведения системы к изменениям длительностей элементарных действий.

В качестве простейших примеров асинхронных моделей можно привести следующие модели:

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

- поднять трубку;

- набрать номер;

- дождаться ответа;

- поговорить;

- положить трубку.

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

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

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

В итоге, поведение асинхронной согласованной дискретной модели можно описать через элементарные действия с использованием операций следования, выбора и циклического повтора, а также операции независимости, или, очевидно, при помощи регулярных выражений [2] и операции независимости.

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

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

Очевидно, что модель может иметь несколько вариантов поведения. Такие варианты будем называть сценариями поведения или просто сценариями.

Допустим, в вышеописанном примере 2) система содержит два равноценных канала передачи А и В, а передаваемый пакет распознается как адрес или данные благодаря специальному «ярлыку», содержащемуся в пакете. Тогда возможны следующие сценарии процедуры передачи (напомним, что передача адреса и передача данных не зависят друг от друга, и, следовательно, не предписывается никакой порядок их передачи): сценарий 1 - адрес передается по каналу А, данные передаются по каналу В (очевидно, что это оптимальный режим передачи, так как он занимает меньше времени за счет возможности одновременной передачи адреса и данных); сценарий 2 - по каналу А передается сначала адрес, затем данные, канал В не используется (такой сценарий можно трактовать как режим аварийной работы в случае каких-либо неисправностей в канале В). Эта система допускает еще четыре сценария передачи информации.

Вернемся к возможности описания систем управления при помощи регулярных выражений и операции независимости.

Делались попытки использовать такую возможность в виде моделирования систем управления некоторым набором независимо функционирующих объектов, каждый из которых реализует регулярные выражения (например, конечные автоматы, как классический способ реализации регулярных выражений [3]). Однако, этот подход имеет ряд серьезных недостатков.

Для построения каждой конкретной модели необходимо зафиксировать число параллельных процессов в сценарии поведения (или максимальное число таких процессов). Но описание системы, используемое при построении модели, не всегда содержит такую информацию, и даже, напротив, определение числа параллельных процессов может быть целью исследования системы (например, при проектировании вычислительной аппаратуры для решения определенной задачи необходимо установить минимальное число процессоров, полностью реализующих «параллельные возможности» системы).

В связи с совместным использованием регулярных выражений и отношения независимости часто упоминаются работы Лодайа (например, [4]) по теории последовательно-параллельных частично-упорядоченных множеств. Однако, использование такого языка моделирования требует описания всей информации о возможных последовательных процессах и их независимости на стадии описания модели. Это сродни использованию регулярных выражений как языка моделирования, языка описания системы.

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

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

В данной работе для описания моделей выбран классический язык описания асинхронных моделей - это язык сетей Петри [5]. Такому выбору послужили две причины. С одной стороны, этот язык допускает удобное и наглядное графическое представление. С другой стороны, язык сетей Петри особенно удобен для формализации причинно-следственных зависимостей.

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

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

1. В динамических моделях с общими ресурсами (например, компьютерах и операционных системах) позиция трактуется как событие, а переход - как процесс. Функционирование сети следует понимать так: входные события включают процессы, а окончание процесса генерирует выходные события. Такая интерпретация используется в [5]. Например, в «задаче об обедающих мудрецах» модель содержит позицию-событие «мудрец закончил есть» и переход-процесс «мудрец ест».

2. Во многих работах последнего времени (см. [6] и приведенную там библиографию по цветным сетям Петри) широкое распространение получает трактование сетей Петри через состояния и действия. А именно, позиции представляют состояния моделируемой системы или ее компонент, а переходы - действия, совершаемые компонентами системы. Для совершения какого-либо действия необходимо, чтобы система или определенный набор ее компонент находились в определенных состояниях. В свою очередь, свершение переходов может перевести компоненты в новые состояния. Например, для начала передачи данных по какому-либо каналу необходимо, чтобы этот канал был свободен. «Свободен» -это состояние канала, являющееся необходимым условием начала передачи.

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

Впервые сети Петри были предложены Карлом Адамом Петри в 1962 году для описания связи асинхронных компонент вычислительной системы и сразу привлекли интерес широкого круга исследователей. Большинство работ в этой области можно разделить на следующие группы:

1) изучение потенциальных возможностей сетей Петри - это вопросы реализуемости тех или иных моделей в виде сети Петри, эквивалентность сетей Петри между собой и сетей Петри другим видам моделей, языки сетей Петри, алгебра сетей Петри и т.д. (см., например, [7-10]);

2) анализ сетей Петри с точки зрения наличия состояний определенного типа - ловушек, тупиков и др. (см., например, [6, 11]);

3) локальные свойства, т.е. свойства отдельно взятых элементов сетей Петри - активность переходов, ограниченность позиций, позиционные инварианты и т.д. (см., например, [5, глава 4; 6,11]);

4) отчеты о построении сетей Петри для конкретных систем; количество таких работ выросло в связи с появлением специальных компьютерных программ для построения и редактирования сетей Петри, что позволяет работать с очень большими моделями (см., например, [12-15]).

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

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

Данная работа имеет следующую структуру:

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

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

Этот метод поиска, или последовательно-параллельный анализ сетей Петри, сформулирован и доказан в третьей главе. Для определения всех возможных последовательно-параллельных сценариев предлагается найти все «решетчатые» структуры в графе переходов сети Петри. «Ячейками» таких структур являются ромбовидные графы, состоящие из 4 вершин и 4 ребер и представляющие пары независимых переходов (см. рис. 2.10).

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

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

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

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

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

Некоторые вспомогательные построения и выкладки вынесены в приложения.

Приложение 1 содержит построение сети Петри для интерфейса шины типового микропроцессора, рассматриваемой во второй и пятой главах.

В приложении 2 строится граф переходов этой сети Петри.

Вывод регулярных выражений для множества путей по этому графу переходов приводится в приложении 3.

Апробация работы

Результаты диссертационной работы доложены и обсуждены на следующих конференциях:

• XLIV и XLV научных конференциях МФТИ (Долгопрудный, 2001,2002);

• Международной научно-практической конференции «Теория активных систем-2001» (Москва, ИПУ РАН, ноябрь 2001 года);

• the 2002 International Joint Conference on Neural Networks IJCNN'02 (Honolulu, Hawaii, 2002);

• the 9th International Conference on Neural Information Processing ICONIP'02 (Singapore, 2002).

По материалам диссертации было опубликовано 10 работ.

Диссертационная работа выполнена при поддержке Российского Фонда Фундаментальных Исследований (грант 01-07-90277).

Заключение

В данной работе получены следующие результаты:

1. Установлено, что если в поведении сети Петри можно выделить независимые циклические последовательные процессы, то граф переходов такой сети Петри может быть представлен в виде некоторой решетки.

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

3. Для построения такого решетчатого представления графа переходов предложено использовать четырех-шаговые диаграммы, составленные из пар независимых переходов сети Петри.

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

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

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

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

1. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах/Под ред. В.И.Варшавского. М.: Наука, 1986.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ. М.: Мир, 1978.

3. Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966.1.daya, К., Weil, P. A Kleene Iteration for Parallelism // FST & TCS'98, Lecture Notes in Computer Science, vol. 1530. -Springer-Verlag, 1998.-Pp. 355-366.

4. Питерсон, Дж. Теория сетей Петри и моделирование систем. — М.: Мир, 1984.

5. Jensen, К. An Introduction to the Theoretical Aspects of Coloured Petri Nets // Lecture Notes in Computer Science, vol. 803. Springer-Verlag, 1994.-Pp. 230-272.

6. Jancar, P., Esparza, J., Moller, F. Petri Nets and Regular Processes // Journal of Computer and System Sciences, 1999.

7. Garg, V.K., Raghunath, M.T. Concurrent Regular Expressions and Their Relationship to Petri Nets // Theoret. Сотр. Sci. 1992, vol. 96, pp. 285-304.

8. Esparza, J., Nielsen, M. Decidability Issues Petri Nets A Survey// J. Inform. Process. Cybernet. - 1994, vol. EIK 30, no. 3, pp. 143-160.

9. Nielsen, M., Winskel, G. Handbook of Logic in Computer Science. -Oxford University Press, 1995. Vol.4, Chapter «Models for Concurrency».

10. Jensen, K. An Introduction to the Practical Use of Coloured Petri Nets // Lecture Notes in Computer Science. Springer-Verlag, 1996.

11. Kishinevsky, М., Cortadella, J., Kondratyev, A. Asynchronous Interface Specification, Analysis and Synthesis // Proc. Design Automation Conf. June, 1998. - Pp. 2-7.

12. Mazzeo, A., Mazzoca, N., Russo, S., Vittorini, V. A Systematic Approach to the Petri Net Based Specifications of Concurrent Systems // Real Time Systems. 1997, vol. 13, pp. 219-236.

13. Mazzoca, N., Russo, S., Vittorini, V. Integrating Trace Logic and Petri Net Specifications// Proc. HICSS-30, Hawaii Int. Conf. on System Sciences. IEEE CS Press, 1997. - Vol. 1, pp. 443-451.

14. Naedele, M. Petri Net Models for Single Processor Real-Time Scheduling. TIK-Report, Zurich, 1998. - No. 61.

15. Murata, T. Petri Nets: Properties, Analysis and Applications// Proceedings of the IEEE. 1989, vol. 77, no. 4, pp. 541-580.

16. PowerPC 603e. RISC Microprocessor User' Manuals. — Motorola Inc., 1995.

17. Stallings, W. Computer Organization and Architecture. — Prentice-Hall, 1996.1. Список публикаций автора

18. Шакирова Н.Ф. Пример моделирования событийно-асинхронной работы фрагмента современного микропроцессора структурированными сетями Петри // Управление и обработка информации: модели процессов. Сб.ст., МФТИ, 2001 - С. 183-204.

19. Шакирова Н.Ф. Использование структурированных сетей Петри для моделирования интерфейса шины // Тезисы докладов XLIV научной конференции МФТИ (23-30 ноября 2001 года). Часть VII. Современные проблемы фундаментальных и прикладных наук. -МФТИ, 2001.-С. 15.

20. N.F.Shakirova, L.N.Stolyarov, E.M.Stolyarova. Petri Nets for Modeling the Behavior of Speculators II Proceedings of the 2002 International Joint Conference on Neural Networks IJCNN'02. -IEEE Press, 2002. Pp. 1865-1870.

21. Шакирова Н.Ф. Последовательно-параллельные сценарии для конвейерного технологического процесса // Информационные технологии в науке и образовании. Сб.ст., Иркутск, 2002. -С. 68-76.

22. Shakirova N. Construction of Petri Nets via States of Action Objects and Subjects // Proceedings of the 9th International Conference on Neural Information Processing (ICONIP'02). Singapore, 2002. -Pp. 226-230.

23. Shakirova N. A New Approach to the Analysis of Petri Nets: Parallel Processes and Predictability of Scenarios // Proceedings of the 9th International Conference on Neural Information Processing (ICONIP'02). Singapore, 2002. - Pp. 248-252.

24. Шакирова Н.Ф. Моделирование сетями Петри поведения игроков на финансовом рынке // Электронный журнал «Исследовано в России». 185, с. 2064-2073, 2002.

25. Шакирова Н.Ф. Формальный аппарат регулярных сетей Петри // Обработка информации и моделирование. — Сб.ст., МФТИ, 2002. -С. 263-289.

26. Шакирова Н.Ф. Как достроить сеть Петри, чтобы ограничить емкость определенной позиции? // Обработка информации и моделирование. Сб.ст., МФТИ, 2002. - С. 290-295.