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

Введение.

1. Формальные средства описания и анализа сложных систем управления.

1.1. Общие проблемы спецификации, синтеза и анализа сложных систем.

1.2. Проблемы организации параллельных вычислений в распределенных системах.

1.3. Формальные модели в исследованиях распределенных систем.

1.4. Описание и моделирование параллельных процессов и потоков данных.

Выводы.

2. Теория ПМС как аппарата формализованного описания и моделирования сложных систем.

2.1. Формальное определение ПМС.

2.1.1. Структура ПМС.

2.1.2. Иерархичность и модульность ПМС.

2.2. Множества классов ПМС.

2.3. Принципы управляемости и динамической реконфигурации в правилах

2.4. Динамика ПМС.

2.4.1. Алгоритм интерпретации ПМС.

2.5. Методы формального анализа свойств ПМС.

2.5.1. Ограниченность и безопасность.

2.5.2. Сохранение.

2.5.3. Активность.

2.5.4. Достижимость маркировки в ПМС.

2.6. Применение к ПМС других методов анализа, разработанных для сетей • Петри, Е-сетей и других расширений сетей Петри.

Выводы.

3. Принципы формальной интерпретации в терминах ПМС алгоритмов распределенной обработки данных и управления процессами.

3.1. Разработка функционально полных наборов компонентов ПМС.

3.1.1. Трансформация Е-сетевых структур в ПМС.

3.1.2. Адекватность ПМС формальным моделям сетей Петри.

3.1.3. Доказательство алгоритмической полноты ПМС.

3.2. Представление элементов распределенных систем в терминах ПМС.

3.2.1. Реализация операций управления процессами.

3.2.2. Интерпретация взаимоисключения и операций управления ресурсами.

3.3. Формализованная методика построения ПМС по диаграмме состояний процесса.

Выводы.

4. Программные средства моделирования сложных систем управления на основе ПМС.

4.1. Функции программных средств ПМС.

4.2. Организация средств моделирования.

4.2.1. Принципы построения средств быстрой разработки программных систем.

4.2.2. Структура среды имитационного моделирования.

4.2.3. Подходы к проектированию моделей с помощью ПМС.

4.3. Средства проведения модельного эксперимента.

4.4. Реализация диалоговых систем и тренажеров с помощью средств ПМС.

4.4.1. Реализация открытого программного интерфейса.

4.5. Реализация среды имитационного моделирования.

Выводы.

Актуальность проблемы

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

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

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

Цель работы

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

Методы исследования

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

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

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

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

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

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

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

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

Практическая ценность работы

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

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

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

Реализация результатов работы

Разработанное алгоритмическое и программное обеспечение используется в Научно-производственном объединении Прикладной механики г. Железногорск для исследования отказоустойчивости функционирования бортовых комплексов управления (БКУ) космических спутников связи в процессе их проектирования. Основные положения диссертации внедрены в процесс проектирования БКУ космических аппаратов в НПО ПМ г. Железногорск.

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

Результаты диссертационной работы докладывались и обсуждались: на Первом Российско-Корейском международном симпозиуме по науке и технологии К01Ш8'97, г. Ульсан, Южная Корея, 1997 г.; на Третьем Российско-Корейском международном симпозиуме по науке и технологии К01Ш8'97, г.Новосибирск, Россия, 1999г.; на региональной научно-технической конференции студентов и молодых специалистов «Радиотехнические и информационные системы и устройства» в секции «Автоматизированные системы обработки информации, управления и проектирования», г. Томск, Россия, 1999 г.; на V областной научно-практической конференции студентов, аспирантов и молодых ученых «Современные техника и технологии», г. Томск, Россия, 1999 г.; на VII Международной научно-методической конференции «Новые информационные технологии в университетском образовании», г. Томск, Россия, 2000 г.; на Четвертом Российско-Корейском международном симпозиуме по науке и технологии КОЬШ8'2000, г. Ульсан, Южная Корея, 2000 г.

Публикации

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

Структура и объем работы

Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 132 страницах машинописного текста, включает 18 рисунков, 3 таблицы, а также содержит список литературы из 81 наименования и приложения. Общий объем работы - 147 страниц.

Выводы

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

1. Анализ современных концепций построения БКУ на базе БЦВМ: научно-технический отчет. Красноярск: НПО ПМ, 1990.

2. Бобровский С. Семинар по С++ Builder 5.0. // PCWeek 2000, №13 - с. 30.

3. Бортовые цифровые вычислительные машины и системы. / В.И. Матов, Ю.А. Белоусов и др.; Под ред. В.И. Матова. М.: Высшая школа, 1988.

4. Бусленко В.Н. Автоматизация имитационного моделирования сложных систем / Под ред. Н.П. Бусленко. М.: Наука, 1977.

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

6. Буч Г. Объектно-ориентированное проектирование. М.: Мир, 1993.

7. Васильев Г.П., Горский В.Е., Шяудкулис В.И., Саух Н.М. Программное обеспечение неоднородных распределенных систем: Анализ и реализация. М.: Финансы и статистика, 1986.

8. Вендров A.M. CASE-технологии. Современные методы и средства проектирования информационных систем. http://www.citforum.ru/case

9. Верников Г. Стандарт онтологического исследования IDEF5. -http://www.citforum.ru/case

10. Головкин Б. А. Параллельные вычислительные системы. М.: Наука, 1980.

11. Дейтел Г. Введение в операционные системы: в 2-х томах. М.: Мир, 1987.

12. Диалоговые системы в АСУ / В.М. Брябрин, Ю.А. Любарский и др.; Под ред. Д.А. Поспелова. М.: Энергоатомиздат, 1983.

13. Диалоговые системы в АСУ / В.М. Брябрин, Ю.А. Любарский и др.; Под ред. Д.А. Поспелова. М.: Энергоатомиздат, 1983.

14. Дмитриев А.К., Мальцев П.А. Основы теории построения и контроля сложных систем.-Л.: Энергоатомиздат, 1988.

15. Дмитриев А.К., Мальцев П.А. Основы теории построения и контроля сложных систем. Л.: Энергоатомиздат, 1988.

16. Дмитриева Е.А. Исследование динамических процессов в многопроцессорных вычислительных системах методом Е-сетевого моделирования. Томск: ТПУ, 1991. - Деп. в ВИНИТИ 01.03.91, N 928-В91.

17. Дмитриева Е.А. Объектно-ориентированная среда Е-сетевого моделирования бортовых комплексов управления. / Дис. на соиск. уч. ст. к.т.н. Томск: ТПУ, 1992.

18. Дмитриева Е.А. Фреймовое представление знаний в интеллектуальных системах моделирования многопроцессорных систем управления. Томск: ТПУ, 1991. - Деп. в ВИНИТИ 01.03.91, N 929-В91.

19. Дмитриева Е.А., Цапко Г.П. Метод формального описания протоколов обмена информацией в специализированных многопроцессорных устройствах // Методы повышения эффективности функционирования вычислительных систем / ОмПИ. Омск, 1988. с. 92-95.

20. Елманова Н.З. Borland С++ Builder 3.0. Архитектура «клиент/сервер», многозвенные системы и Internet-приложения. -М.: Диалог-МИФИ, 1999.

21. Елманова Н.З. Распределенные вычисления и технологии Inprise. // Компьютерпресс 1999, №1, CD.

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

23. Информационная технология в промышленности / Ю.Г. Данилевский, И.А. Петухов, B.C. Шибанов. Л.: Машиностроение, 1988.

24. Информационные технологии в испытаниях сложных объектов: методы и средства / Скурихин В.И., Квачев В.Г. и др.; Отв. ред. Египко В.М. АН УССР. Ин-т кибернетики им. В.М. Глушкова. Киев: Наук, думка, 1990.

25. Искусственный интеллект: В 3 кн. Кн. 1. Системы общения и экспертные системы: Справочник / Под ред. Э.В. Попова. М.: Радио и связь, 1990.

26. Искусственный интеллект: В 3 кн. Кн. 2. Модели и методы: Справочник / Под ред. Д.А. Поспелова. М.: Радио и связь, 1990.

27. Искусственный интеллект: В 3 кн. Кн. 3. Программные и аппаратные средства: Справочник / Под ред. В.Н. Захарова, В.Ф. Хорошевского. М.: Радио и связь, 1990.

28. Иыуду К.А. Надежность, контроль и диагностирование вычислительных систем и машин. М.: Высшая школа, 1989.

29. Калянов Г.Н. CASE. Структурный системный анализ (автоматизация и применение). М.: Лори, 1996.

30. Кесс Ю.Ю. Анализ и синтез фреймовых моделей АСУ. М.: Энергоатомиздат, 1986.

31. Клейнрок JI. Вычислительные системы с очередями / Пер. с англ. М.: Мир, 1979.

32. Клейнрок JI. Теория массового обслуживания / Пер. с англ. М.: Машиностроение, 1979.

33. Костин А.Е. Модели и алгоритмы организации распределенной обработки данных в информационно-управляющих системах. / Дисс. на соиск. уч. ст. д.т.н. М.: Московский институт электронной техники, 1989.

34. Костин А.Е. Принципы моделирования сложных дискретных систем. М.: МИЭТ, 1983.

35. Костин А.Е. Программный комплекс для сетевого имитационного моделирования дискретных систем с параллельными процессами // Управляющие системы и машины. 1987, №4. - с. 98-102.

36. Костин А.Е., Ильюшечкин В.М., Корнилов А.Р. Представление параллельных процессов в распределенных микропроцессорных системах Е-сетями // Известия ВУЗов СССР.: Приборостроение. 1986, №3. - с. 28-33.

37. Костин А.Е., Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах. М.: Высшая школа, 1987.

38. Котов В.Е. Сети Петри. М.: Наука, 1989.

39. Котов В.Е., Черкасова J1.A. Сетевой подход к описанию семантики параллельных систем и процессов // Кибернетика и вычислительная техника, 1986, вып. 2, с. 75-94.

40. Лаптев B.C., Жаврид Е.В. и др. Проблемно-ориентированные инструментальные средства разработки программного обеспечения управляющих и информационно-управляющих систем. // УСиМ. 1988, №4. - с. 74-76.

41. Лейн Алекс. Объектно-ориентированное программирование в реальном мире // Мир ПК. 1991, №5. - с. 29-36.

42. Мамедли Э.М., Соболев H.A. Механизмы операционных систем, обеспечивающие отказоустойчивость в управляющих многомашинных вычислительных системах // АиТ 1995, №8. - с. 3-63.

43. Мануэль Т. Объектно-ориентированное программирование: рождение новой звезды // Электроника 1989, №9. - с. 49-55.

44. Марка Д.А., МакГоуэн К. Методология структурного анализа и проектирования. -М.: МетаТехнология, 1993.

45. Месарович М., Мако Д., Такахара И. Теория иерархических многоуровневых систем. М.: Мир. 1973.

46. Месарович М., Такахара И. Общая теория систем: математические основы. М.: Мир, 1978.

47. Микропроцессоры. Книга 1: Архитектура и проектирование микро-ЭВМ. Организация вычислительных процессов / Нестеров П.В., Шаньгин В.Ф., Костин А.Е. и др. / Под ред. Л.Н. Преснухина. М.: Высшая школа, 1986.

48. Минский М. Фреймы для представления знаний. М.: Мир, 1979.

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

50. Никонов В.В., Подгурский Ю.Е. Применение сетей Петри // Зарубежная радиоэлектроника. 1986, №11. - с. 17-37.

51. Никонов В.В., Подгурский Ю.Е. Сети Петри, теория, применение // Зарубежная радиоэлектроника. 1984, №4.

52. Основы моделирования сложных систем / Л.И. Дыхненко, И.В. Кузьмин и др. -Киев: Вища. шк., 1981.

53. Основы теории вычислительных систем / С.А. Майоров, Г.И. Новиков, Т.И. Алиев и др.; Под ред. С. А. Майорова. М.: Высшая школа, 1978.

54. Осуга С. Обработка знаний: Пер. с япон. М.: Мир, 1989.

55. Петренко А.Ф. Представление взаимодействующих процессов дискретными сетями // Автоматика и вычислительная техника 1983, №6 - с. 34-40.

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

57. Поляков Г.А., Умрихин Ю.Д. Автоматизация проектирования сложных цифровых систем коммутации и управления. М.: Радио и связь, 1988.

58. Пранявичюс Г.И. Модели и методы исследования вычислительных систем. -Вильнюс: Мокслас, 1982.

59. Пранявичюс Г.И., Шваните Д.Ю. Применение Е-сетей при создании имитационных моделей // Математика и математическое моделирование. Вильнюс, 1980, вып. 4, с. 68-72.

60. Применение микропроцессорных средств в системах передачи информации / Б.Я. Советов, О.И. Кутузов, Ю.А. Головин, Ю.В. Аверков. М.: Высшая школа, 1987.

61. Разработка САПР: В 10 кн. Кн. 1. Проблемы и принципы создания САПР: Практ. пособие / A.B. Петров, В.М. Черненький; Под ред. A.B. Петрова. М.: Высшая школа, 1990.

62. Розенблюм Л.Я. Сети Петри // Известия АН СССР, Технич. кибернет., 1983, №5 -с. 12-40.

63. Советов Б.Я., Яковлев С.А. Моделирование систем: учеб. для вузов по спец. «Автоматизированные системы обработки информации и управления». М.: Высшая школа, 1998.

64. Теллес М. Borland С++ Builder: библиотека программиста. СПб: Питер Ком, 1998.

65. Туротт П. и др. Супербиблия Delphi 3. Пер. с англ. К.: ДиаСофт, 1997.

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

67. Хювенен Э., Сеппянен Й. Мир Лиспа. В 2-х т. Т. 2: Методы и системы программирования. Пер. с финск. М.: Мир, 1990.

68. Цапко Г.П. Е-сетевой метод информационно-логического проектирования бортовых комплексов управления. Томск: Изд. ТПУ, 1995.

69. Черноусов Е. Язык С++ и объектно-ориентированное программирование // Компьютер Пресс. 1991, №5. - с. 27-31.

70. Шапиро Э., Такеути А. Объектно-ориентированное программирование в Параллельном Прологе // Язык Пролог в пятом поколении ЭВМ: Сб. статей 19831984 гг.: Пер. с англ. / Сост. Н.И. Ильинский. -М.: Мир, 1988.

71. Шеннон Р. Имитационное моделирование систем искусство и наука: Пер. с англ. М.: Мир, 1978.

72. Языки искусственного интеллекта и объектно-ориентированное программирование // Компьютер Пресс. 1991, №9 - с. 33-60.

73. Jensen K. Coloured Petri Nets: A High Level Language for System Design and Analysis // Advanced in Petri nets 1990. Lecture Notes in Computer Science, vol.483. Springer, Berlin Heidelberg New York 1990.

74. Noe J.D., Nutt G.J. Macro E-Nets for Representation of Parallel Systems // IEEE Trans, on Computers, 1973, vol. C-22, №8, p. 718-727.

75. Nutt G.J. Evaluation Nets for Computer System Performance Analysis // AFIPS FJCC, 1972, vol. 41, Pt. l,p. 279-286.