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

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ МЕТОДОВ И СРЕДСТВ МОДЕЛИРОВАНИЯ СИСТЕМ РАСПРЕДЕЛЕННОЙ ОБРАБОТКИ ИНФОРМАЦИИ (РОИ).

1.1. Анализ характеристик систем РОИ.

1.2. Анализ процесса проектирования систем РОИ.

1.3. Анализ формальных моделей, используемых для исследования систем РОИ.

1.3.1. Анализ возможностей сетевых моделей.

1.3.2. Классификация и характеристики низкоуровневых сетей Петри

1.3.3. Классификация и характеристики высокоуровневых сетей Петри.

1.4. Сравнительный анализ средств имитационного моделирования систем РОИ.

ВЫВОДЫ.

ГЛАВА 2. РАЗРАБОТКА ФОРМАЛЬНОГО АППАРАТА ДЛЯ

ПРЕДСТАВЛЕНИЯ МОДЕЛЕЙ СИСТЕМ РОИ.

2.1. Требования к формальному аппарату для представления моделей систем РОИ.

2.2. Общее описание Е-сетей и модифицированных Е-сетей.

2.3. Алгебра модифицированных Е-сетей.

2.4. Алгоритм функционирования модифицированных Е-сетей

2.5. Язык описания сетевой модели.S

2.6. Язык управления процессом моделирования.

ВЫВОДЫ.

ГЛАВА 3. РАЗРАБОТКА КОМПЛЕКСА ИМИТАЦИОННОГО

МОДЕЛИРОВАНИЯ.

3.1. Требования к комплексу имитационного моделирования

Winsim.

3.2. Выбор архитектуры комплекса имитационного моделирования Winsim.

3.2.1. Креативная система.

3.2.2. Реализация компилятора языка MDL.

3.2.3. Исполнительная система.

3.3. Анализ возможностей распараллеливания процессов имитационного моделирования на группе компьютеров в ЛВС

ВЫВОДЫ.

ГЛАВА 4. ПРИМЕНЕНИЕ КОМПЛЕКСА WINSIM ДЛЯ

ИССЛЕДОВАНИЯ СИСТЕМ РОИ.

4.1. Методика представления систем РОИ на языке MDL.

4.2. Исследование модели локальной вычислительной сети с кольцевой топологией.

4.3. Исследование модели локальной вычислительной сети типа Ethernet.

4.4. Исследование распределенных алгоритмов взаимного исключения.

4.4.1. Алгоритм Рикарта-Агравала.

4.4.2. Алгоритм Трехе ля.

4.4.3. Алгоритм Судзуки-Касами.

ВЫВОДЫ.

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

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

Несмотря на успехи, достигнутые в области исследования и реализации систем РОИ, здесь существует много нерешенных проблем как теоретического, так и практического характера. Так как любая система РОИ представляет собой очень сложный объект, то, не имея ее работоспособной модели, такую систему очень трудно отладить и реализовать даже при наличии в ней 10-20 узлов. Постоянное развитие новых методов и средств реализации систем РОИ также требуют разработки новых формальных методов и средств исследования распределенных систем, которые могли бы служить практическим инструментом на стадии проектирования систем

РОИ, а также для устранения «узких» мест в уже существующих распределенных системах. Этой тематике и посвящена данная работа.

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

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

1) развитие перспективного формального аппарата для представления моделей систем РОИ на основе Е-сетей;

2) разработка принципов построения и алгоритмов функционирования комплекса имитационного моделирования на основе аппарата Е-сетей для описания и исследования систем РОИ;

3) программная реализации комплекса имитационного моделирования на основе аппарата Е-сетей для описания и исследования систем РОИ;

4) разработка методики построения и исследования Е-сетевых моделей систем РОИ;

5) разработка и исследование моделей систем РОИ.

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

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

1. Введены новые операции над модифицированными Е-сетями и изучены их свойства.

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

3. Реализована интегрированная среда разработки в составе комплекса имитационного моделирования Winsim и подсистема сборки модели.

4. Разработана методика представления систем РОИ в виде модифицированных Е-сетей.

5. Разработаны и исследованы сетевые модели локальных вычислительных сетей Token Ring и Ethernet и распределенных алгоритмов взаимного исключения Рикарта-Агравала, Трехеля и Судзуки-Касами.

Практическая ценность работы. Созданные программные инструментальные средства в виде комплекса имитационного моделирования Winsim, могут использоваться для автоматизации построения и исследования имитационных моделей систем РОИ, в частности, при проектировании и исследовании перспективных архитектур систем обработки данных, в том числе -высокопроизводительных распределенных систем. Этот комплекс может быть использован при изучении вузовских дисциплин, в которых рассматриваются организация вычислительных процессов, построение вычислительных сетей, организация параллельной и распределенной обработки информации. Предложенные в диссертационной работе способы распределенной реализации имитационного комплекса обеспечивают возможность эффективного моделирования систем практически неограниченных размеров и сложности. Разработанные и исследованные в работе Е-сетевые модели алгоритмов взаимного исключения могут быть использованы при анализе и модификации протоколов в распределенных системах. Обоснование применения математического аппарата систем массового обслуживания замкнутого типа для аналитического исследования этих алгоритмов позволяют проводить верификацию результатов имитационного моделирования и исследование эффективности подобных алгоритмов. В целом результаты диссертации, включая разработанные программно-инструментальные средства, позволяют практически применять перспективный формальный аппарат модифицированных Е-сетей для исследования систем РОИ и принимать на этой основе обоснованные решения при выборе параметров, выявлении и устранении "узких" мест в системах РОИ.

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

Апробация работы. Основные результаты диссертационной работы были апробированы на международных, всероссийских и межвузовских научно-технических конференциях и семинарах, что отражено в списке литературы. Разработанные с участием автора диссертации микрокомпьютерная система имитационного моделирования Микросим и комплекс имитационного моделирования Winsim, реализующие формальный аппарат модифицированных Е-сетей, прошли государственную регистрацию в РОСПАТЕНТ (регистрационные №№ 2002610187 и 2002610717). Комплекс Winsim зарегистрирован на международном Web-сайте [94] в списке программных продуктов, основанных на сетях Петри и их расширениях.

Публикации. Содержание диссертации отражено в 20 опубликованных работах, в том числе в двух свидетельствах РОСПАТЕНТа РФ.

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

ВЫВОДЫ

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

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

3. Показано, что Е-сети позволяют адекватно моделировать типичные логические компоненты, входящие в состав систем РОИ.

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

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

ЗАКЛЮЧЕНИЕ

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

Важным результатом диссертационной работы явилось создание программного комплекса Winsim для автоматизации построения и исследования Е-сетевых моделей. Предназначенный для эксплуатации на ПК класса IBM PC под управлением ОС Windows, этот комплекс существенно пополняет ряд известных у нас и за рубежом программных систем моделирования, основанных на сетях Петри и их расширениях. Он включен в международный каталог программных продуктов, основанных на сетях Петри и их расширениях. Микрокомпьютерная система имитационного моделирования Микросим и комплекс имитационного моделирования Winsim прошли государственную регистрацию в РОСПАТЕНТ РФ.

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

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

2. Разработаны структура и алгоритмы программного комплекса Winsim, предназначенного для построения и исследования Е-сетевых имитационных моделей.

3. Разработан и реализован программный комплекс Winsim.

4. Разработана методика представления компонентов систем РОИ в форме Е-сетевых моделей и на языке описания сетевых моделей MDL. Данная методика обоснована и проиллюстрирована на примерах построения Е-сетевых моделей ряда функциональных компонентов, входящих в состав систем РОИ.

5. Проанализирована возможность построения распределенной системы имитационного моделирования, основанной на аппарате модифицированных Е-сетей.

6. Разработаны и исследованы Е-сетевые модели ЛВС Token Ring и Ethernet. Полученные характеристики функционирования ЛВС согласуются с результатами аналитического расчета, что подтверждает адекватность разработанных моделей.

7. Разработаны и исследованы модели распределенных алгоритмов взаимного исключения Рикарта-Агравала, Трехеля и Судзуш-Касами. Предложено для анализа эффективности алгоритмов использовать эквивалентную аналитическую модель СМО замкнутого типа.

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

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

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

1. Айвазян С.А. и др. Прикладная статистика: Исследование зависимостей: Справ, изд. / Под ред. С.А, Айвазяна. - М.: Финансы и статистика, 1985. -487 с.

2. Альянах И.Н. Моделирование вычислительных систем. М.: Машиностроение, 1988.-223 с.

3. Андрианов А.Н., Бычков С.П., Хорошилов А.И. Программирование на языке симула-67. М.: Наука, 1985. - 288 с.

4. Армстронг Дж. Р. Моделирование цифровых схем на языке VHDL / Пер. с англ. М.: Мир, 1992. - 175 с.

5. Архангельский А.Я. Программирование в Delphi 5 2-е изд., перераб. и дополн. - М.: ЗАО "Издательство БИНОМ", 2000 г. - 1072 с.

6. Афанасьев Н.В. и др. Локальные вычислительные сети: Учебник для вузов связи. М.: Радио и связь, 1996. - 337 с.

7. Ахо Л., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1. Синтаксический анализ / Пер. с англ. под ред. В.М.Курочкина. М.: Мир, 1978.-612 с.

8. Ачасова С.М., Бандман О.Л. Корректность параллельных вычислительных процессов. Новосибирск: Наука. Сиб. Отделение, 1990.-253 с.

9. Баев В.В., Паненко С.В. Пакет программ моделирования дискретных процессов расширенными сетями Петри // УСиМ, 1991, №8, с. 83 87.

10. Берже Ж.-М., Фонкуа А., Мажиро С., Руйар Ж. VHDL'92. Новые свойства языка описания аппаратуры VHDL / Пер. с англ. М.: Радио и связь, 1995. -256 с.

11. Бусленко Н.П. Моделирование сложных систем М.: Наука, 1978 - 400 с.

12. Васяева Н.С., Михеев П.В. Организация контроля трафика в сети с кольцевой топологией. Йошкар-Ола: Марийск. гос. техн. университет, 2001, 8 с. Деп. в ВИНИТИ 06.02.2001. № 305 - В2001.

13. Вентцель Е.С., Овчаров JI.A. Прикладные задачи теории вероятностей. -М.: Радио и связь, 1983. 416 с.

14. Гагарина Л.Г., Илюшечкина Л.В. Комплекс имитационного моделирования для анализа систем распределенной обработки информации // Оборонный комплекс научно-техническому прогрессу России. - М.: ВИМИ, 2002, №2, с. 33-35.

15. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. 2-е изд., перераб. и доп. - М.: Наука. Главная редакция физико-математической литературы, 1987. - 336 с.

16. Гультяев А. Визуальное моделирование в среде MATLAB: учебный курс. СПб: Питер, 2000. - 432 с.

17. Гультяев А.К. MATLAB 5.3. Имитационное моделирование в среде Windows. Спб.: КОРОНАпринт, 2001. - 400 с.

18. Гурбанова Ш.М., Мустафаев В.А. Разработка модели управления гибкой производственной системы на основе аппарата сетей Петри. Http://ww w.galnam.in-baku.com

19. Иванищев В.В. Автоматизация моделирования потоковых систем / Под ред. В.М.Пономарева. Л.: Наука, 1986. - 142 с.

20. Илюшечкин В.М., Илюшечкина Л.В. Опыт диалогового имитационного моделирования вычислительных систем // Алгоритмы и программы системного математического обеспечения ЕС ЭВМ и кросс средств: Сб. научных трудов. М.: МИЭТ, 1982, с. 72 - 79.

21. Илюшечкина Л.В. Интегрированная среда разработки имитационных моделей распределенных систем обработки информации // Информационные технологии в науке, проектировании и производстве: Материалы пятой

22. Всероссийской научно-технической конференции. Н.Новгород: МВВО АТН РФ, 2002 г., с. 28.

23. Илюшечкина Л.В., Костин А.Е. Использование комплекса имитационного моделирования WINSIM для исследования локальных вычислительных сетей // Научная сессия МИФИ-2002. Т. 12. Информатика. Компьютерные системы и технологии. М.: МИФИ, 2002, с. 166 - 167.

24. Илюшечкина Л.В., Костин А.Е. Язык микрокомпьютерной системы имитационного моделирования // Микропроцессорные вычислительные устройства управляющих систем / Под ред. В.А. Бархоткина. М.: МИЭТ, 1988, с. 66-71.

25. Казаков Ю.П., Смелянский Р.Л. Об организации распределенного имитационного моделирования. // Программирование, №2 , 1994, с. 45-63.

26. Киндлер Е. Языки моделирования. М.: Энергия, 1985. - 288 с.

27. Кириллов В.Ю., Нижняк В.В. Пакет программ работы с сетями Петри для ПЭВМ // УсиМ, 1989, №4. с. 48-51.

28. Комаров А.В. Алгоритм диспетчеризации передачи данных по локальной магистрали многопроцессорной системы кольцевого типа // Известия вузов. Электроника, 2001, №1, с. 80 86.

29. Корнеев В.В. Параллельные вычислительные системы, М., Нолидж, 1999.

30. Костин А.Е., Гагарина Л.Г., Илюшечкина Л.В. Исследование локальной вычислительной сети Ethernet с использованием модифицированных Е-сетей. // Известия вузов. Электроника, 2002, №2, с. 72-78.

31. Костин А.Е., Илюшечкина Л.В. Специальная файловая система для диалоговых моделирующих комплексов в ОС ЕС // Методы разработки и peaлизации программного обеспечения ЭВМ: Сб. научных трудов. / Под ред. А.В.Савченко М.: МИЭТ, 1985, с. 10 - 16.

32. Костин А.Е., Илюшечкина JI.B. Исследование работы локальной вычислительной сети Ethernet на имитационной модели // Информационно-управляющие и телекоммуникационные системы: Межвуз. сб. научных трудов. / Под ред. В.А.Бархоткина М.: МИЭТ, 2002, с.

33. Костин А.Е., Илюшечкина JI.B., Илюшечкин В.М. Система Е-сетевого моделирования МИКРОСИМ // Программные средства МИЭТ / Под. ред. Савченко А.В. М.: МИЭТ, 1990, с. 32 - 33.

34. Костин А.Е., Илюшечкин В.М., Корнилов А.Р., Зимнович В.А., Илюшечкина Л.В., Федоров А.Р., Шаньгин В.Ф. Диалоговая система имитационного моделирования // Алгоритмы и программы: Инф. Бюллетень, 1987, №9, с.9.

35. Костин А.Е., Илюшечкина Л.В. Модифицированные Е-сети для исследования систем распределенной обработки информации // Автоматика и вычислительная техника, 1988, № 6, с. 27 35.

36. Котов В.Е. Сети Петри. М.: Наука, 1984. - 158 с.

37. Краснощекое П.С., Петров А.А. Принципы построения моделей. Изд. 2-е, перераб. и доп. М.: ФАЗИС, 1999. - 412 с.

38. Литвинов В.В., Марьянович Т.П. Методы построения имитационных систем. Киев: Наукова думка, 1991 .-117с.

39. Лукьянов Г.В. Особенности технологий локальных сетей Token Ring и Ethernet // НТИ, Сер. 1, ВИНИТИ, 2000, № 12, с. 1 18.

40. Мельников Д.А. Информационные процессы в компьютерных сетях. Протоколы, стандарты, интерфейсы, модели М.: КУДИЦ-ОБРАЗ, 2000. -256 с.

41. Новиков Ю.В., Кондратенко С.В. Локальные сети: архитектура, алгоритмы, проектирование. М.: ЭКОМ, 2000. - 312 с.

42. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы СПб.: Издательство "Питер", 2001. - 672 с.

43. Олифер В.Г., Олифер Н.А. Сетевые операционные системы СПб.: Издательство "Питер", 2001. - 544 с.

44. Павловский Ю.Н. Имитационные модели и системы. М.: ФАЗИС: ВЦ РАН, 2000. - 134 с.

45. Пентус А.Е., Пентус М.Р. Объектно-ориентированное представление иерархических сетей Петри // Фундаментальная и прикладная математика, 2000, Том 6, Вып. 3, с. 831 840.

46. Петрович М.Л., Давидович М.И. Статистическое оценивание и проверка гипотез на ЭВМ. М.: Финансы и статистика, 1989. - 191 с.

47. Питерсон Дж. Теория сетей Петри и моделирование систем / Пер. с англ. под ред. В.А.Горбатова. М.: Мир, 1984. - 264 с.

48. Райтер Р., Вальран Ж. Распределенное имитационное моделирование дискретно-событийных систем // М. Мир, ТИИЭР, т. 77, № 1, 1989, с. 245-262.

49. Румянцев П.В. Азбука программирования в Win32 API. М.: Радио и связь, 1998.-272 с.

50. Свидетельство об официальной регистрации программы для ЭВМ № 2002610187, Россия. Микрокомпьютерная система имитационного моделирования МИКРОСИМ / Костин А.Е., Илюшечкин В.М., Илюшечкина

51. Л.В., Голова С.Ю., Немцова Т.И., Корнилов А.Р. Зарегистрировано в РОСПАТЕНТ 15 февраля 2002 г., заявка № 2001611748.

52. Свидетельство об официальной регистрации программы для ЭВМ № 2002610717, Россия. Комплекс имитационного моделирования Winsim. / Костин А.Е., Илюшечкина Л.В., Илюшечкин В.М. Зарегистрировано в РОСПАТЕНТ 17 мая 2002 г., заявка № 2002610428.

53. Свистунов С.В. Справочник. Стандартные функции и процедуры Delphi 4, Delphi 5. М.: ЛХА "Альманах", 2001.-318 с.

54. Сидоров Е.А., Пивоваров В.В., Бобков С.Г. Метод доступа к коммуникационной среде с кольцевой топологией // Научная сессия МИФИ-2002. Т. 12. Информатика. Компьютерные системы и технологии. М.: МИФИ, 2002, с. 178-179.

55. Советов Б.Я., Яковлев С.А. Моделирование систем: Учеб для вузов 3-е изд., перераб. и доп. - М.: Высш. шк., 2001. - 343 с.

56. Феррари Д. Оценка производительности вычислительных систем / Пер. с англ. под. Ред. В.В.Мартынюка. М.: Мир, 1981. - 576 с.

57. Харт Дж.М. Системное программирование в среде Win32, 2-е изд. Пер. с англ. : М.: Издательский дом "Вильяме", 2001. - 464 с.

58. Хоар Ч. Взаимодействующие последовательные процессы. М.: Мир, 1989.-264 с.

59. Чайя Л. Элементарные причинно-следственные структуры // Системная информатика: Сб. науч. тр. Вып. 7: Проблемы теории и методологии создания параллельных и распределенных систем. Новосибирск: Наука, 2000, с. 6 81.

60. Шалыто А.А. Логическое управление. Методы аппаратной и программной реализации алгоритмов. СПб.: Наука, 2000. - 780 с.

61. Шрайбер Т.Дж. Моделирование на GPSS / Пер. с англ. под ред. М.АФайнберга. М.: Машиностроение, 1980. - 592 с.

62. Юров В. Assembler. Спб.: Питер, 2001. - 624 с.

63. Bagrodia R., Deelman E., Phan T. Parallel Simulation of Large Scale Parallel Applications // International Journal of High-Performance Computing Applications, 2001, vol.15, No. 1, pp. 3 12.

64. Baldassari M., Bruno G. An environment for Object-Oriented Conceptual Proggramming Based on PROT Nets // Lectures on Petri Nets II: Applications, Lecture Notes on Computer Science / Ed. W.Reisig, G.Rozenberg. Springer-Verlag, 1998, vol. 340, pp. 1-19.

65. Billington J., Wheeler G.R., Wilbur-Ham M.C. PROTEAN: A High-Level Petri Net Tool for the Specification and Verification of Communication Protocols // IEEE Trans. Software Eng., 1988, vol. 14, pp. 301 316.

66. Boujarwah A., Al-Seif N., Saleh K. Modelling the semantics of multitasking facilities in Concurrent С using Petri nets // Information and Software Technology, 1996, vol. 38, No. 1, pp. 3 9.

67. Bux W. Local Area Subnetworks. A Performance Comparison // IEEE Trans. On Commun. 1981. - vol. COM-29, N 1, pp. 1465 - 1473.

68. Carothers C., Fujimoto R.M., Lin Y.-B., England P. Distributed Simulation of PCS Networks Using Time Warp // Proc. of International Workshop on Modeling, Analysis and Simulalation of Computer and Telecommunication Systems, 1994, pp. 2-7.

69. Chandy K.M., Misra J. Distributed Simulation: A Case Study in Design and Verification of Distributed Programs // IEEE Trans, on Software Engineering, 1979, vol. SE-5, No. 5, pp. 440 452.

70. Cheung T.-Y. Petri nets for protocol engineering // Computer Communications, 1996, Vol. 19, No. 14, pp. 1250 1257.

71. Ciardo G. Petri Nets with Mark-Dependent Arc cardinality: Properties and Analysis // Proc. Of the 15th Int. Conf. On Application and Theory of Petri Nets. Lecture Notes on Computer Science / Ed. R.Valette. Springer-Verlag, 1994, vol.815, pp. 179-198.

72. Coulouris G., Dollimore J., Kindberg T. Distributed Systems: Concepts and Design, 3rd ed. Addison-Wesley, 1995. - 644 p.

73. Dietz C., Schreiber G. A Term Representation of P/T Systems // Proc. Of the 15th Int. Conf. On Application and Theory of Petri Nets. Lecture Notes on Computer Science / Ed. R.Valette. Springer-Verlag, 1994, vol. 815, pp. 239 -257.

74. Dijkstra E.W. Solution of a Problem in Concurrent Programming Control // Communications of the ACM, 1965, vol. 8, No. 9, p. 569.

75. Enslow P.H. What is a Distributed Data Processing Systems // Computer, 1978, vol. 11, No. l,pp. 13-21.

76. Fincel A., Rosier L. A Survey on the Decidability Questions for Classe of FIFO Nets // Advances in Petri Nets, Lecture Notes on Computer Science / Ed. W.Reisig. Springer-Verlag, 1998, vol. 40, pp. 106 - 132.

77. Flynn M.J. Some Computer Organizations and their Effectivness // IEEE Trans, on Computers, 1972, vol. 21, No. 9, p. 948 960.

78. Fujimoto R.M. Parallel Discrete Event Simulation // Communications of the ACM, 1990, vol. 33, No. 10, pp. 31 53.

79. German R. Performance Analysis of Communication Systems: Modeling with Non-Markovian Stochastic Petri Nets. John Wiley & Sons. - 2000. -456 p.

80. Gerogiannis V.C., Kameas A.D., Pintelas P.E. Comparative Study and Categorization of High-Level Petri Nets // The Journal of Systems and Software, 1998, vol. 43, pp. 133-160.

81. Harel D., Politi M. Modeling Reactive Systems with Statecharts: state machine approach. McGraw-Hill, 1998. - 258 p.

82. He X. PZ nets a formal method integrating Petri nets with Z // Information and Software Technology, 2001, Vol. 43, No. 1, pp. 1-18.

83. Helary J.-M., Mostefaoui A., Raynal M. A General Scheme for Token- and Tree-Based Distributed Mutual Exclusion Algorithms // IEEE Trans, on Parallel and Distributed Systems, 1994, vol. 5, No. 11, pp. 1185 1994.

84. Http://www.daimi.aau.dk/PetriNets/tools/quick.html.

85. Jefferson D. Virtual Time // ACM Trans, on Programming Languages and Systems, 1985, vol. 7, No. 3, pp. 404-425.

86. Jensen K. An Introduction to the Practical Use of Coloured Petri Nets // Lectures on Petri Nets II: Applications, Lecture Notes on Computer Science / Ed. W.Reisig, G.Rozenberg. Springer-Verlag, 1998, vol. 340, pp. 237 - 292.

87. Knuth D.E. Additional Comments on a Problem in Concurrent Programming Control // Communications of the ACM, 1966, vol. 9, No. 5, pp. 321 322.

88. Koh I., DiCesare F. Modular Transformation Methods for Generalized Petri Nets and Their Application to Automated Manufacturing Systems // IEEE Trans, on Systems, Man and Cybernetics, 1991, vol. 21, pp. 1512 1522.

89. Kostin A.E. MICROSIM E-net Tool for Modelling Networks and Distributed Data Processing Systems // Proc. of the First Symposium on Computer Networks, May 30 - 31, 1996 - Bebek, Istanbul, 1996, pp. 34-46.

90. Lamport L. A New Solution of Dijkstra's Concurrent Programming Problem /./ Communications of the ACM, 1974, vol. 17, No. 8, pp. 453 455.

91. Lamport L. Time, clocks and ordering of events in a distributed system // Communications of the ACM, 1978, vol.21, pp. 568 564.

92. Lin Y.-B. Memory Management Algorithms for Parallel Simulation 11 Information Processing Letters, 1994, vol. 50, pp. 12-25.

93. Lin Y.-B., Fishwick P.A. Asynchronous Parallel Discrete Event Simulation // IEEE Trans, on Systems, Man and Cybernetics, 1996, vol. 26, No. 4, pp. 1 -33.

94. Lindemann C. Performance Modelling with Deterministic and Stochastic Petri Nets, Wiley, 1998. 405 p.

95. Maekawa M. A VN Algorithm for Mutual Exclusion in Decentralized Systems // ACM Trans, on Computer Systems, 1985, vol. 3, No. 2, pp. 145 159.

96. Mattern F. Efficient Distributed Snapshots and Global Virtual Time Algorithms for Non-FIFO Systems // Journal for Parallel and Distributed Computing, 1993, vol. 18, No. 4, pp. 423-424.

97. Milner R. Communication and Concurrency. Prentice-Hall, Englewood Cliffs, NJ, 1989.

98. Mitschele-Thiel A. Systems Engineering with SDL. John Wiley & Sons, 2001 -360 p.

99. Naimi M., Trehel M., Arnold A. A Log(N) Distributed Mutual Exclusion Algorithm Based On the Path Reversal // Journal of Parallel and Distributed Computing, 1996, vol. 34, pp.1 13

100. Nicol D.M., Fujimoto R.M. Parallel Simulation today // Annals of Operations Research, 1994, vol.53, pp. 249-286.

101. Nishio S., Li K.F., Manning E.G. A Resilient Mutual Exclusion Algorithm for Computer Networks // IEEE Trans, on Parallel and Distributed Systems, 1990, vol. 1, No. 3, pp. 344 355.

102. Nutt G.J. Evaluation Nets for Computer System Performance Analysis 11 AFIPS FJCC, 1972, vol. 41, Pt. 1, p. 279-286.

103. Peterson G.L. Myths about the Mutual Exclusion Problem // Information Processing Letters, 1981, vol. 12, No. 3, pp. 115 116.

104. Reinke C. Haskell-Coloured Petri Nets // Implementation of Functional Languages, 11th International Workshop, IFL'99, Lochem, The Netherlands, September 7-10, 1999. Springer Verlag: Selected Papers, LNCS, vol. 1868, pp. 165-180.

105. Ricart G, Agrawala A.K. An Optimal Algorithm for Mutual Exclusion in Computer Networks // Communications of the ACM, 1981, vol. 24, pp. 9-17.

106. Saiedian H. An Invitation to Formal Methods // IEEE Computer, 1996, vol. 29, No. 4, pp. 16-30.

107. Sang J., Mascarenhas E., Rego V. Mobile-Process Based Parallel Simulation // Journal of Parallel and Distributed Computing, 1996, vol. 33, No. 1, pp. 12 -23.

108. Sibertin-Blanc C. Concurrency in Cooperative Objects // Second International Workshop on High-Level Parallel Programming Models and Supportive Environments, HIPS'97, IEEE Society Press, April 1997, Geneva (S), pp. 33 -41.

109. Stotts P.D., Godfrey P. Place/Transition Nets with Debit Arcs // Information Processing Letters, 1992, vol. 41, pp. 25 33.

110. Suzuki I., Kasami T. A Distributed Mutual Exclusion Algorithm //ACM Trans, on Computer Systems, 1985, vol.3, No. 4, pp. 344 349.

111. Tanenbaum A.S., M. van Steen. Distributed Systems: Principles and Paradigms. Prentice-Hall, 2002. - 840 p.

112. The ACM Computing Classification System. Http://www.acm.org

113. Thomas R.H. A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases // ACM Trans, on Database Systems, 1979, vol. 4, No. 2, pp. 180-209.

114. Valavanis K.P. On the Hierarchical Modeling Analysis and Simulation of Flexible Manufacturing Systems with Extended Petri Nets // IEEE Trans, on Systems, Man and Cybernetics, 1990, vol. 20, pp. 94 110.

115. Van Benthem J. Temporal Logic // Handbook of Logic in Artificial Intelligence and Logic Programming / Ed. D.M. Gabbay, C.J. Hogger, J.A. Robinson. Oxford: Clarendon Press, 1995, Vol. 4, pp. 241 - 350.

116. Ventouris K.P., Pintelas P.E. A Practical Assesment of Formal Specification Approaches to Data Abstractions // Journal of Systems and Software, 1992, vol. 17, pp. 169-188.

117. Weili Y, Xudong H. Mapping Petri nets to concurrent programs in CC++ // Information and Software Technology, 1997, Vol. 39, No. 7, pp. 485 495.

118. Yakovlev A.V., Koelmans A.M., Semenov A., Kinniment D.J. Modelling, analysis and synthesis of asynchronous control circuits using Petri nets // Integration, the VLSI Journal, 1996, Vol. 21, No. 3, pp. 143 170.

119. Model Descroption Language, MDL)

120. Если максимальное число повторений цепочки, заключеннной в фигурные скобки, ограничено некоторой константой, то эта константа записывается справа от закрывающей фигурной скобки.

121. Так, запись {А}3 означает # | А | АА j AAA

122. В этом описании отражены лишь те элементы, которые являются расширениями языка Object Pascal. Синтаксис языка Object Pascal (в частности, определения нетерминалов <идентификатор>, <число>, <число без знака>, <целое без знака> и <оператор>) описан в ?.,

123. ОПИСАНИЕ СЕГМЕНТА Ml. <СЕГМЕНТ> ::= SEGMENT <ИМЯ СЕГМЕНТ А>,Т1СК=<ЕДИНИЦ А ВРЕМЕНИ>;

124. ТЕЛО> SEGEND. М2. <ИМЯ СЕГМЕНТА> ::= <ИДЕНТИФИКАТОР> МЗ. <ЕДИНИЦА ВРЕМЕНИ> ::= PSEC | NSEC | MCSEC | MSEC | SEC |

125. MIN | HOUR | DAY М4. <ТЕЛО> ::= <РАЗДЕЛ АТРИБУТОВ>

126. РАЗДЕЛ СЕТЕВЫХ ПЕРЕМЕННЫХ>1. РАЗДЕЛ ПАСКАЛЬ-МЕТОК>1. РАЗДЕЛ ПАСКАЛЬ-КОНСТАНТ>1. РАЗДЕЛ ПАСКАЛЬ-ТИПОВ>

127. РАЗДЕЛ ПАСКАЛЬ-ПЕРЕМЕННЫХ>

128. РАЗДЕЛ ПАСКАЛЬ-ПРОЦЕДУР И ПАСКАЛЬ-ФУНКЦИЙ>

129. РАЗДЕЛ ЭЛЕМЕНТАРНЫХ СЕТЕЙ>

130. РАЗДЕЛ ДОБАВЛЯЕМЫХ СЕГМЕНТОВ>

131. РАЗДЕЛ СВЯЗЫВАНИЯ СЕГМЕНТОВ>

132. ОПИСАНИЕ АТРИБУТОВ И СЕТЕВЫХ

133. ПЕРЕМЕННЫХ В1. <РАЗДЕЛ АТРИБУТОВ> ::= ATTRIBUTES <СПИСОК ОДНОТИПНЫХ АТРИБУТОВ>{<СПИСОК ОДНОТИПНЫХ АТРИБУТОВ>} В2. <СПИСОК ОДНОТИПНЫХ АТРИБУТОВ> ::=

134. ИМЯ АТРИБУТА> {,<ИМЯ АТРИБУТА>}: <АРИФМ.ТИП>; ВЗ. <АРИФМ.ТИП> ::= INTEGER | REAL В4. <РАЗДЕЛ СЕТЕВЫХ ПЕРЕМЕННЫХ> ::=

135. DATA <СПИСОК ОДНОТИПНЫХ СЕТЕВЫХ ПЕРЕМЕННЫХ> {<СПИСОК ОДНОТИПНЫХ СЕТЕВЫХ ПЕРЕМЕННЫХ>} В5. <СПИСОК ОДНОТИПНЫХ СЕТЕВЫХ ПЕРЕМЕННЫХ>

136. СПИСОК ПРОСТЫХ ПЕРЕМЕННЫХ> | сСПИСОК МАССИВОВ>

137. В6. <СПИСОК ПРОСТЫХ ПЕРЕМЕННЫХ> ::= <ПРОСТАЯ ПЕРЕМЕННАЯ>

138. ПРОСТАЯ ПЕРЕМЕННАЯ^: <АРИФМ.ТИП>; В7. сПРОСТАЯ ПЕРЕМЕННАЯ> ::= <ИМЯ ПЕРЕМЕННОЙ> |

139. ИДЕНТИФИКАТОР> /<ЗНАЧЕНИЯ ЭЛЕМЕНТОВ>/ В12. <ЗНАЧЕНИЯ ЭЛЕМЕНТОВ> <НАЧ.ЗНАЧЕНИЕ> {,<НАЧ.ЗНАЧЕНИЕ>}

140. В13. сГРАНИЧНЫЙ ИНДЕКС> <ЦЕЛОЕ БЕЗ ЗНАКА> В14. <ИМЯ АТРИБУТА> ::= <ИДЕНТИФИКАТОР> В15. <ИМЯ ПЕРЕМЕННОЙ> <ИДЕНТИФИКАТОР>

141. РАЗДЕЛ ЭЛЕМЕНТАРНЫХ СЕТЕЙ Е1. <РАЗДЕЛ ЭЛЕМЕНТАРНЫХ СЕТЕЙ> ::=

142. СПЕЦИФИКАТОР ЭЛЕМЕНТАРНОЙ СЕТИ> Е2. СПЕЦИФИКАТОР ЭЛЕМЕНТАРНОЙ СЕТИ> ::= СТРУКТУРА СЕТИ>; | <ПРОЦЕДУРАУПРАВЛЕНИЯ>; | <ПРОЦЕДУРА ВРЕМЕННОЙ ЗАДЕРЖКИ>; |сПРОЦЕДУРА ПРЕОБРАЗОВАНИЯ^ ЕЗ, <СТРУКТУРА СЕТИ> ::=

143. NET ИДЕНТИФИКАТОР ПЕРЕХОДА> : <СХЕМА> Е4. ИДЕНТИФИКАТОР ПЕРЕХОДА> ::= <ТИП СЕТИхНОМЕР ПЕРЕХОДА>

144. ИДЕНТИФИКАТОР ПОЗИЦИИ> «ДИСЦИПЛИНА ОБСЛУЖИВАНИЯ^

145. Е12. ИДЕНТИФИКАТОР ПОЗИЦИИ> ::= <ТИП ПОЗИЦИИхНОМЕР ПОЗИЦИИ

146. Е13. <ТИП ПОЗИЦИИ> ::= S | Q Е14. НОМЕР ПОЗИЦИИ> ::= <ЦЕЛОЕ БЕЗ ЗНАКА> Е15. сДИСЦИПЛИНА ОБСЛУЖИВАНИЯ> ::= FIFO | LIFO | RAND | LOW (ИМЯ АТРИБУТА>) | HIGH (ИМЯ АТРИБУТА>) Е16. ПРОЦЕДУРА УПРАВЛЕНИЯ> ::= CONTROL

147. ИДЕНТИФИКАТОР ПЕРЕХОДА>: <ОПЕРАТОР>{;<ОПЕРАТОР>} Е17. ПРОЦЕДУРА ВРЕМЕННОЙ ЗАДЕРЖКИ> ::= TIME

148. ИДЕНТИФИКАТОР ПЕРЕХОДАМ <ОПЕРАТОР>{;<ОПЕРАТОР>} Е18. ПРОЦЕДУРА ПРЕОБРАЗОВАНИЯ> ::= TRANSFORM

149. ИДЕНТИФИКАТОР ПЕРЕХОДА>: <ОПЕРАТОР>{;<ОПЕРАТОР>}

150. Примечания: В составе конструкции <ОПЕРАТОР> могут быть ссылки на встроенные функции MDL (см. Приложение 3). Дисциплины обслуживания LOW/HIGH обеспечивают расположение фишек в порядке возрастания/ убывания значений атрибутов.

151. РАЗДЕЛ ДОБАВЛЯЕМЫХ СЕГМЕНТОВ А1. <РАЗДЕЛ ДОБАВЛЯЕМЫХ СЕГМЕНТОВ> : :=

152. ATTACH <СПИСОК СЕГМЕНТОВ> А2. <СПИСОК СЕГМЕНТОВ> ::=

153. СЕГМЕНТ-ОРИГИНАЛ> / <СЕГМЕНТ-КОПИЯ> {,<СЕГМЕНТ-КОПИЯ>}/

154. СЕГМЕНТ-ОРИГИНАЛ> / <СЕГМЕНТ-КОПИЯ> , {,<СЕГМЕНТ-КОПИЯ>}/} A3. <СЕГМЕНТ-ОРИГИНАЛ> : := <ИМЯ СЕГМЕНТА> А4. <СЕГМЕНТ-КОПИЯ> ::= <ИМЯ СЕГМЕНТА>

155. РАЗДЕЛ СВЯЗЫВАНИЯ СЕГМЕНТОВ Л1. <РАЗДЕЛ СВЯЗЫВАНИЯ СЕГМЕНТОВ> ::=

156. NK <ПАРА СЕГМЕНТОВ> : <ПАРА ПОЗИЦИЙ> {/<ПАРА ПОЗИЦИЙ>} Л2. <ПАРА СЕГМЕНТОВ> ::= <СОСТАВНОЕ ИМЯ>, -СОСТАВНОЕ ИМЯ>

157. ЛЗ. <СОСТАВНОЕ ИМЯ> ::= <ИМЯ СЕГМЕНТА> {.<ИМЯ СЕГМЕНТА>} Л4. <ПАРА ПОЗИЦИЙ> ::= ИДЕНТИФИКАТОР ПОЗИЦИИ>,1. ИДЕНТИФИКАТОР ПОЗИЦИИ>6. ССЫЛКИ НА СЕТЕВЫЕ ОБЪЕКТЫ

158. Д1. <ПЕРЕМЕННАЯ> <ПОЛНАЯ ПАСКАЛЬ-ПЕРЕМЕННАЯ> | сКОМПОНЕНТНАЯ ПАСКАЛЬ-ПЕРЕМЕННАЯ> |

159. УКАЗАННАЯ ПАСКАЛЬ-ПЕРЕМЕННАЯ> | <ССЫЛКА НА СЕТЕВОЙ ОБЪЕКТ> Д2. <ССЫЛКА НА СЕТЕВОЙ ОБЪЕКТ> ::=

160. ССЫЛКА НА ПРОСТУЮ ПЕРЕМЕННУЮ» | <ССЫЛКА НА ЭЛЕМЕНТ МАССИВА> | ССЫЛКА НА АТРИБУТ ФИШКИ> | <ССЫЛКА НА ПОЗИЦИЮ> | <ССЫЛКА НА ПЕРЕХОД> ДЗ. ССЫЛКА НА ПРОСТУЮ ПЕРЕМЕННУЮ» ::= %<ИДЕНТИФИКА-ТОР>

161. Д4. <ССЫЛКА НА ЭЛЕМЕНТ МАССИВА> ::= %<ИДЕНТИФИКАТОР>

162. ВЫРАЖЕНИЕ> {,<ВЫРАЖЕНИЕ>} 1 . Д5. <ССЫЛКА НА АТРИБУТ ФИШКИ> ::= %<ИДЕНТИФИКАТОР ПОЗИЦИИ>. <ИМЯ АТРИБУТА>

163. SNA1 | SNA2 | SNA3 j SNA4 | SNA5