Сеть автоматов для моделирования асинхронного взаимодействия процессов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Новик, Константин Валерьевич

• Новик, Константин Валерьевич
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Новик, Константин Валерьевич

ВВЕДЕНИЕ.

ГЛАВА 1 ВВЕДЕНИЕ В СИСТЕМЫ ВЗАИМОДЕЙСТВУЮЩИХ ПРОЦЕССОВ.

1.1 Сеть Петри для моделирования асинхронного взаимодействия процессов при использовании общих ресурсов.

1.2 Сети с накоплениями событий.

1.3 Сети с распознающими предикатами.

1.4 Вычислительные сети (CN).

1.5 Самосинхроиизирующиеся сети (SN).

1.6 Асинхронные преобразующие сети.

1.7 Высказывательная (пропозиционная) сеть для экспертных систем.

1.8 Выводы по главе 1.

ГЛАВА 2 ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ JOINER-СЕТЕЙ.

2.1 Концептуальная интерпретация Joiner-сетей и взаимосвязей их элементов.

2.2 Формальная система, порождающая правильно построенные формулы JN.

2.3 Матричная форма представления JN.

2.4 Проблемы анализа сетей и формы их представления, удобные для анализа.

2.5 Joiner-алгебра (склеивающая алгебра).Ъ

2.6 Техника работы с Joiner-алгеброй.

2.7 Теорема о ярусно-параллельной форме Joiner-сети.

2.8 Многопроцессорное разложение сетей. Теорема о процессорной декомпозиции. Теорема о композиции локальных сетей.

2.9 Формальная интерпретация JN сетью автоматов.

2.10 Внутренняя структура элементарного автомата и правила его работы в сети.

2.11 Теорема о «работающей» цепочке.

2.12 Выводы по главе 2.

ГЛАВА 3 ИЗВЕСТНЫЕ МОДЕЛИ АСИНХРОННЫХ СИСТЕМ УПРАВЛЕНИЯ ПРОЦЕССАМИ И ИХ ПРЕДСТАВЛЕНИЕ JOINER-СЕТЬЮ.

3.1 Сети Петри (PN).

3.2 Асинхронные цифровые схемы (сети) Маллера (MN).

3.3 Дискретные нейронные сети Мак Каллока-Питтса (VN).

3.4 Семантическая сеть Ван-Хао (WN).

3.5 Алгебраические сети (AN). Исчисление Эрбрана-Геделя. Вычислительные модели Э. Тыугу.

3.6 Ринговые и роторные сети (RN, RoN).

3.7 Выводы по главе 3.

ГЛАВА 4 МОДЕЛИ РЕАЛЬНЫХ АСИНХРОННЫХ СИСТЕМ, ИСПОЛЬЗУЮЩИХ JOINER-CETH.

4.1 Модель, описывающая процессы разрушения древнерусских фресок

4.1.1 Описание модели.

4.1.2 Элементы модели.

4.1.3 Сеть, описывающая состояние фрески.7)

4.1.4 Пример работы сети.

4.2 Модель удаленной Интернет-атаки.

4.2.1 Описание модели.

4.2.2 Элементы модели.

4.2.3 Сеть для моделирования атаки.

4.2.4 Пример работы сети.

4.3 Модель системы связи канального процессора с двумя абонентами.

4.3.1 Описание модели.

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

4.3.3 Пример работы сети.

4.4 Модель информационной системы поля боя.

4.4.1 Описание модели.

4.4.2 Элементы модели.

4.4.3 Сеть для четырех подразделений.

4.4.4 Пример работы сети.

4.5 Модель группового поведения стаи рыб.

4.5.1 Описание модели.

4.5.2 Элементы модели.

4.5.3 Сеть для стаи из пяти рыб.

4.5.4 Пример работы сети.

4.6 Модель биржевой игры.

4.6.1 Описание модели.

4.6.2 Элементы модели.

4.6.3 Сеть для двух игроков.

4.6.4 Пример работы сети.

Введение диссертации (часть автореферата) на тему «Сеть автоматов для моделирования асинхронного взаимодействия процессов»

Работа посвящена моделям поведения сложных систем, в которых выделены элементы и их взаимосвязи. Элементы называются процессами, а взаимосвязи определяются поставками и потреблением отдельными процессами информации, энергии, вещества. Каждый элемент системы (процесс) «живет» по собственным законам и требует для своей «жизни» определенные ресурсы, например, каналы для передачи информации, хранилища для вещества, процессоры для выполнения действий и т.д. Говорят, что поведение такой системы асинхронно, в связи с тем, что взаимодействия (поставки и потребление ресурсов) не зависят от физического времени, а определяются событиями, которые генерируются отдельными элементами системы. События фиксируют результаты изменений в состоянии элементарных процессов, передаются (собираются) другими процессами, управляя изменением их состояния. В этом плане события являются синхронизаторами, инициаторами изменения состояний процесса. Сетевые модели в настоящее время весьма распространены, начиная с 80-х годов XX века, и насчитывают около тысячи публикаций.

1. Объект исследования.

Объектом исследования являются асинхронные системы (АС), которые задаются сетью Net = (S,E,R,I), где S = {S{,.,Sn} - конечное множество процессов, Е = {ех,.,ет} - конечное множество событий, R - правила, которые приписывают каждому процессу S, подмножества так называемых входных Ex(Si) и выходных Ey(Si) событий, правила имеют вид: : Ех (Si )Еу,

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

Содержательная Математическая модель Программа задача асинхронной системы

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

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

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

3. Какие проблемы решены в диссертации.

Собственно, решению двух вышеперечисленных проблем и посвящена данная работа.

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

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

4. Научная новизна работы.

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

1) Вводится понятие «картиночных» формул и строится формальная система порождения всех правильно построенных формул.

2) Вводится специальная Joiner-алгебра с двумя операциями: «•» -склеивание и «V» - композиция. Joiner-алгебра позволяет проводить эквивалентные преобразования формул. В частности, с ее помощью строятся стандартные разложения сетей.

3) Для каждого процесса вводится управляющий элементарный автомат с двумя видами функций: у/-пусковой (для запуска процесса) и (р

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

Сети, построенные на этих трех принципах называются Joiner-сетями.

Эти три результата получены самостоятельно (являются оригинальными), представляют научную новизну работы и выносятся на защиту.

5. История исследований.

Исследования по сетевой тематике начались с 1999 года, были отражены в бакалаврской диссертации «Струйная томография, теория и практическое применение» (2001) и в магистерской диссертации «Ситуационная комната для анализа и парирования Internet-атак» (2003). В основном исследования проводились в рамках грантов РФФИ № 01-0790277, «Разработка систем распределенного мозгового штурма через Internet для сложных научных проектов РАН», 2001-2002 гг.; № 03-07-90356, «Исследование моделей ситуационной комнаты, управляемой событиями, которые передаются через Internet», 2003-2005 гг.; № 04-07-90070, «Информационная система для искусствометрики памятников древнерусского искусства», 2004-2006 гг.; а также личных грантов РФФИ № 02-07-06064 и № 03-07-06149, «Программа поддержки молодых ученых», 2002 и 2003 гг., выделенных на проведение перспективных фундаментальных исследований. Большая часть результатов исследований вошла в диссертационную работу.

6. Логика построения работы и ее краткое содержание.

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

2) Во второй главе вводится понятие Joiner-сетей и строится их теория, состоящая из следующих разделов:

1. Формальная система, порождающая правильно построенные формулы Joiner-сетей (JN).

2. Joiner-алгебра.

3. Стандартные разложения JN.

4. Анализ циклических ярусно-параллельных разложений.

5. Интерпретация формул сети автоматами, автоматными пусковыми и флаговыми функциями.

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

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

Доказывается теорема о «работающей» цепочке и показывается применение этой теоремы для анализа корректности (логической неразрывности) сети.

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Новик, Константин Валерьевич

3.7 Выводы по главе 3

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

2. Существуют сети с операционной семантикой, отличной от сетей Петри.

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

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

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

JN

Заключение

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

1. Сформулирована общая концепция модели асинхронной системы, состоящей из множества процессов. Каждый процесс запускается или меняет свое состояние в зависимости от событий, которые происходят в других процессах.

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

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

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

5. Приведены примеры задач, для решения которых используются математические модели в виде Joiner-сетей и соответствующие комплексы программ. В частности, JN-модель поведения стаи рыб, JN-модель поведения биржевых игроков, JN-модель «жизни» настенных росписей (выполнялась для Ферапонтова монастыря, который входит в список объектов ЮНЕСКО), JN-модель Интернет-атаки и т.д.

Список литературы диссертационного исследования кандидат физико-математических наук Новик, Константин Валерьевич, 2006 год

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

2. Ахо А.,Хопкрофт Дж., Ульман Дэ/с Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 535 с.

3. Варшавский В. И., Поспелов ДА. Оркестр играет без дирижера. М.: Наука, 1984.-208 с.

4. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. - 608 с.

5. Зайцев Д.А. Инвариантность модели Петри протокола TCP // Научные труды Одесской национальной академии связи им. А.С. Попова. 2004. -№2.-С. 19-27.

6. Клини С.К. Введение в математику. М.: ИЛ, 1957. - 526 с.

7. Коновалова Л.И., Новик КВ. Мониторинговые возможности сетей Joiner-net // Информационные и математические технологии: Сб. научных трудов/ИСЭМ СО РАН Иркутск, 2004. - С. 14-17.

8. Коновалова Л.И., Новик КВ. Применение сетей Joiner-net для мониторинга состояния фресок Дионисия Ферапонтова монастыря // Моделирование процессов управления: Сб. научных трудов/Моск. физ.-тех. ин-т. М., 2004. - С. 88-94.

9. Котов В.Е. Алгебра регулярных сетей Петри // Кибернетика. 1980. - №5 -С. 10-18.

10. Котов В.Е. Сети Петри. М.: Наука, 1984. - 160 с.1 \.Котов В.Е., Наринъяни А.С. Асинхронные вычислительные процессы над памятью // Кибернетика: Сб. ст. / АН СССР. 1966. - №3 - С. 64-71.

11. Мак-Каллок У.С., Питтс У. Логическое исчисление идей, относящихся к нервной активности // Автоматы, под ред. Шеннона К.Э. и Маккарти Дж. -М.:ИЛ, 1956.-С. 362-384.

12. Мальцев А.И. Алгебраические системы. М.: Наука, 1970. - 392 с.

13. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1986. -392 с.

14. Медведский ИД., Семьянов П.В., Леонов Д.Г. Атака на Internet. М.: ДМК, 1999.-336 с.

15. Мендельсон Э. Введение в математическую логику. -М.: Наука, 1971. -320 с.

16. Минский М. Структура для представления знания // Психология машинного зрения. М.: Мир, 1978. - С. 249-338.

17. Новик КВ. Joiner-cera для моделирования взаимодействующих процессов // Информационные и математические технологии в науке и образовании: Сб. научных трудов/ИСЭМ СО РАН Иркутск, 2005. - Часть 1 - С. 243249.

18. Новик КВ. Исследование Joiner-net для управления синхронизацией данных // Процессы и методы обработки информации: Сб. научных трудов/Моск. физ.-тех. ин-т. М., 2005. - С. 31-39.

19. Новик К.В., Ситуационная комната для анализа и парирования Интернет-атак // Математические и информационные технологии в энергетике, экономике, экологии: Сб. научных трудов/ИСЭМ СО РАН Иркутск,2003. Часть 2 - С. 267-277.

20. Новик К.В. Струйный анализ временных рядов // Моделирование процессов управления и обработки информации: Сб. научных трудов/Моск. физ.-тех. ин-т. -М., 1999. С. 198-212.

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

22. Столяров JI.H. Структурный анализ численных алгоритмов для параллельных и конвейерных вычислений: Дисс. докт. физ.-мат. наук. -М.: МФТИ, 1987.

23. Столяров Л.Н., Новик К.В. Joiner-сеть для моделирования взаимодействующих параллельных процессов // Моделирование процессов управления: Сб. научных трудов/Моск. физ.-тех. ин-т. -М.,2004.-С. 81-97.

24. Столяров Л.Н., Новик КВ. Реализация параллельных процессов с помощью сетей Joiner-net // Информационные и математические технологии: Сб. научных трудов/ИСЭМ СО РАН Иркутск, 2004. - С. 1114.

25. Тыугу Э.Х. Концептуальное программирование. М.: Наука, 1984. - 256 с.

26. Холдин Ю.И. Сквозь пелену пяти веков. Сокровенная встреча с фресками Дионисия Мудрого. М.: Слово, 2002. - 420 с.31 .Bernstain P. Description problems in the modeling of asynchronous computer systems // Tech. Report / Univ. of Toronto. 1973. -N 48.

27. Dijkstra E. W. Cooperating sequential processes // Programming Languages / NATO Advanced Study Institute. Academic Press, 1968. - P. 43-112.

28. Petri C.A. Kommunication mit Automaten. Schriften fur des Rheinich-Westfalischen Inst. Fur Instrumentalle Mathematik. Univ. Bonn. - Bonn, 1962.

29. Xudong He, John A. N. Lee A methodology for Contructing Predicate Transition Net Specifications // Software Practice and Experience. - 1991. -V. 21, N 8. - P. 845-875.