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

Государственная агадемия аэрокосмнческого приборостроения

ОД на правах рукописи

г 1 т ^

Молчанов Алексей Юрьевич

Методы и средства моделирования и анализа на основе Б-сетей.

Специальность 05.13.11 "Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей"

Автореферат диссертации на соискание ученой степени • кандидата технических наук.

С.-Петербург 1997

Рабата выполнена ва Государственной академии аэрокосмического приборостроения.

Научный руководитель:

канд. техн. наук, доц. Гордеев Александр Владимирович

Официальные оппоненты:

докт. техн. наук, проф. Колесников Дмитрий Николаевич канд. техн. наук, до'Ц. Яшин Александр Иванович

Ведущая организация:

Холдинговая компания "Ленинец".

Защита диссертации состоится _ 1997 г. в часов

на заседании диссертационного совета К063.21.03.

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

Автореферат разослан

"21" 1997 г.

Ученый секретарь совета:

/докт. техн. наук, проф., Фнльчаков В.В./

Общая характеристика работы

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

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

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

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

Ме10;¡ы__н сел ело даи. При выполнении исследований по вопросам диссертации были использованы: теория параллельных процессов, теория алгоритмов, теория графов, теория сетей Петри, математическая лотка.

Цаушая_новизна, В процессе выполнения исследований в рамках

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

• метод построения дерена достижимости F-cereu посредством использования цепочек переходов из графа достижимости покрывающих маркировок;

• методика создания новых типов переходов F-сетей на основе технологии объектно-ориентированного программирования. . •

Практическая значимость. В процессе решения основных задач данной диссертационной работы были разработаны следующие средства: « структура данных для машинного представления F-сетепых моделей;

• алгоритм имитационного моделирования с помощью F-сетей, реализующий управление на основе событий;

• алгоритм построения графа достижимости покрывающих маркировок.

Основные результаты работы реализованы в программном комплексе моделирования и анализа "Сети Петри для Windows". Профаммный комплекс предназначен для построения моделей параллельных систем, имитационного моделирования и анализа построенных моделей, а также для обучения методам имитационного моделирования. (Профаммный комплекс функционирует на персональной ЭВМ типа IBM PC/AT в фафической среде MS Windows.)

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

• метод и алгоритм анализа сетей Петри с помощью построения фафа достижимости покрывающих маркировок;

• метод н -алгоритм анализа F-cerefi путем построения дерева достижимости сети с использованием фафа достижимости покрывающих маркировок;

• методика создания новых типов переходов F-еетей на основе технологии объектно-ориентированного профаммирооання и структура данных для ее реализации;

• алгоритм имитационного моделирования на основе F-cereft.

Внеяренне, Результаты диссертационной работы использованы в следующих организациях: Санкт-Петербургский государственный технический университет (г. С.-Петербург); Государственная академия аэрокосмического приборостроения (г. С.-Петербург); "Академия универсального образования и предпринимательства" (г. С.-Петербург), НПП "Турботест" (г. С.-Петербург). Внедрение результатов диссертационной работы подтверждено соответствующими актами, копии которых даны в приложениях к диссертационной работе.

Апробация работы. Основные положения работы докладывались на следующих научно-технических конференциях и семинарах: "Автоматизация процессов управления соединениями и частями ПВО, информационные технолога»", С.-Петербург, 1996 г.; "Диагностика, информатика и метрология", С.-Петербург, 1994 и 1995 г.г.; "Новые информационные

техполопт", Гурзуф, . 1994 г.; "Техническое диапюанрооание - 93", С.Петербург, 1993 I'.

ПубдлКлШШЬ По результатам диссертационной работы опубликовано 11 статен и докладам, разработано 3 электронных учебника. Основные положения диссертационной работы отражены и 6 отчетах по НИР, выполненных к ГААП и СПбШГГ в 1991-94 г.

Офухлурд__ц_яйка_Шссе|Шншн» Диссертация состоит из введения,

четырех глав, заключения, списка литературы (78 наименовании) и приложении. Объем основной части • 138 страниц машинописного текста.

Краткое содержание работы по главам

и

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

систем

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

1! рабою производится иыиор моделирующего формализма на основе Р-сетен (функциональных сетей) - расширения сетей Петри, построенного на основе друтго расширенна - Г-сетен. Р'-сеш построены путем сопоставления с каждым переходом его типа, заданного процедурой функционирования. Формализм [-'-сетей предложен А.В. Гордеевым.

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

Для ана'нш большинства расширений сетей Петри матричные методы' анализа неприменимы. Единственно возможным является метод, основанный

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

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

2. Анализ модифицированных сетей Петри

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

Во второй части главы для сетей Петри предложен метод анализа на основе построения графа достижимости покрывающих маркировок, содержащего цепочки срабатывания переходов, приводящие от начальной маркировки Мо к маркировкам, покрывающим заданную Ми. Данный метод реализован с помощью алгоритма построения графа в. Его выполнение основано на порождении предыдущих маркировок переходов. При этом обозначение * в маркировке соответствует произвольному числу маркеров в позиции. При сравнении маркировок сети * = 0. Правила математических операций над символом *: * + п = п, пеЫ; * - п = -п. иеЫ; где N - множество целых неотрицательных чисел.

ч.

Определение 2.1 Порожденная предыдущая маркировка MJ для перехода сети t, еТ (где Т - множество мерехоцоп сети) на основе произвольной маркировки сети Мт строится следующим образом:

Если Эркg0(t,> (где 0((,) - множество выходных' позиций перехода что Мт(рк)>0, го находится маркировка MJ но следующим правилам:

• строится маркировка М,": MT"(pJ)=M1(pJ)-W(t„pJ), VpjeOOj), где VV -функция разметки кратности дуг сети (\V>0),

• если MT"(pj)<0, то MT"(pj)=*, VpjGl1 (Мт" - промежуточная маркировка);

® M,'(Pj)=MT"(Pj)+W(pj,ti). Vpjelft,), где I(tj) - множество входных позиций перехода t,.

/bin порожденной предыдущей маркнропкн перехода сети п работе докатим следующие три своистиа:

Утверждение 2.1. Суп. действий согласно определению (2.1) для перехода сети t,eT и маркировки сети Мт заключается в нахождении маркировки сети М', такой, что для перехода I, выполняется правило: I,: ¡М|-»М,, и Мр>М,. (Первое свойство порождаемой предыдущей маркировки).

Утверждение 2.2. Из правил срабатывания перехода и определения (2.1) следует, что если t,: М„->МХ и М | - порожденная предыдущая маркировка для 1, на основе маркировки Мт, то Мн=М„. В этом случае промежуточная маркировка М," обладает свойством: Vp(eV: Mr"(pj)=M,(pj)-W(t„pj). (Второе свонстпо порожденной предыдущей маркировки).

Утверждение 2.5. Наш t,: М„—>Мр, Мр>Мг и Mj - порожденная предыдущая маркировка для перехода I, на основе маркировки Мт, то М,'<МН. (Третье свойство порожденной предыдущей маркировки).

II) определения (2.1) дается определение порожденной предыдущей маркировки win последовательности срабатывания перехолоп.

Определение 2.2. q"=(ik|.....tkj,...,ik[J) - последовательность срабатывания

переходив, разрешенная для М0. п - длина иоследошиелыюстп, a к| - номер перехода, срабатывающею на i-том шаге. Тогда (Мо,...,М„) последовательность маркировок для q", причем ikj: М„->М|, tk|: M|->MJ( lk|J: M„.i->Mn. При этом q" порождает Mn из Mo (qn: MU-»M„).

Определение 2.3. Порождаемой предыдущей маркировкой для

последовательности qn=(tkJ,...,tkJ.....!fc|[) на основе произвольной М„ называется

маркировка, получаемая п результате порядка действий, при котором для tk£ на основе М„ порождается предыдущая маркировка М„.|, затем для t^'f,., па основе М,,.; порождается М„.г и т.д. до tk|. На последнем шаге порождения предыдущей маркировки для q" будет порождена MJ для tkj.

Последовательность маркировок (Mö,...,Mn.J,Mn) является при этом последовательностью порождаемых предыдущих маркировок для q". Дня

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

Утверждение 2.4. Порождаемая предыдущая маркировки М,'> последовательности q" обладает свойством, что ц": \1о->М,; и М,!>Мц. (Первое свойство). Маркировка М„ называется порождаемой конечной маркировкой.

Утверждение 2.5. Если (Мо,...,Мп) - последовательность маркировок для

qnI а (Мо.....М„.|',М„) - последовательность порождаемых предыдущих

маркировок дня той же то V 0<кп: М,'=М,. (Второе свойство).

• Утверждение 2.6. Если 1)": Ми—>М„, Мц^М,, н Ми - порождаема» предыдущая маркировка для я" на основе М„, то Мо>Мо. (Третье свойство).

Определение 2.4. Последовательность <)"=(11].....называется

поглощающей, если для'Соответствующей ей последовательности маркировок (Мо,...,Мп) выполняется условие Мо^М,,.

Утверждение 2.7. Для поглощающей последовательности Мо>М„.

Доказательство: По определению (2.4) для имеем М^М,',, по из утверждения (2.4) для ц", получаем М^М,,, следовательно, М^>\1„.*

Утверждение 2.8. Если - некоторая произвольная последовательность . срабатывания переходов, а я" - поглощающая последовательность: ц^сц1,'. т<11, то которая имеет вид' "'.ц'Ц).

Определение 2.5. содержит в себе (включает в себя) ц"1 ш<п (1)'"сс||' и чУэя1?). если У^ея":1 З^еяГ: п VI,.¡2 3)„)2: ,Н>: к„=1л, кцЦ2.

Определение 2.6. Последовательности ц" и ц" равнозначны (с|?=ц"), если Ч?**)" и при этом выполняется чТсц" и ч'дсц1'.

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

На первом цуге алгоритма в список Ь заносится искомая маркировка М„. В фафе в строятся вершины, соответствующие М„ и Мо.

На втором шагд проверяется, пуст ли список и если он пуст, то построение графа в закончено. Если список не пуст, из нею выбирается первая маркировка, которая берется в качестве текущей маркировки М,. Маркировка Мт удаляется из списка Ь.

На третьем шаге, если М0>МГ, то для всех М[, таких, что существует ребро (МГ,М|) в фафе в, ребро (МТ,МГ) удаляезся из трафа С и строится ребро (М3,М;), которому в соответствие ставится тот же переход, что и ребр_\

С

внесение коночной маркировки Ми в список &

Выбор текущей маркировки М| из списка ^

Выбор очередного перехода 1, из множества Т

Выбор вершины

Мд из ребра (Мд.Мт) в графе О

-16-

Порождение предыдущей Мт' на осиоое Мт для перехода 1,

17 I Внесение маркировки М,' в список I

_ 12

выбор вершины

Мд из ребра (Мд'.Мд) в фафе

а

Построение ребра (Мт,Мт') в графе О для перехода 1,

,_13_

Текущая вершина в графе О:

МДМд'

Рис. 1. Блок-схема алгоритма построения фафа достижимости покрыгмюжич маркировок.

(М,,М,'). Вершина Мг удаляется из фафа С, после чею следует перейти ко второму ша1у алгоритма, иначе надо перейти к следующему ша1у алгоритма.

На четвертом шаге рассматривается маршрут (МГ,М„) в |рафе С. Если некоторая маркировка, входящая в данный маршрут, покрывает М„ то для Мт выполняется алгоритм отката и затем необходимо вернуться ко., второму шагу алгоритма. Иначе переходим к следующему шагу алгоритма.

На пятом шаге порождаются новые вершины фафа в. Для каждого перехода сети ^ выполняются следующие действия: если Зр^еОО,), такая что Мт(рк)>0. то для перехода и М, порождается предыдущая маркировка М;, которая добавляется в список а в графе С строится иершина и ребро (М;,МТ). Ребру ставится в соответствие переход После нахождения всех маркировок М; необходимо вернуться ко второму ша1у алгоритма.

Блок-схема данного алгоритма приведена на рис. 1.

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

Каждый возможный маршрут (М0,М„) в фафе С соответствует последовательности срабатывания переходов сети, переводящей Мо .в маркировку покрывающую М„: М,|>М„. Если не существует покрывающей маркировки, >о фаф С будет содержать только Мо. Среди множества • маркировок М„ могут оказаться маркировки точно совпадающие с М„. Отсутствие маркировок, совпадающих с М„, среди всех маркировок М,'„ не означает полного их отсутствия среди всех достижимых маркировок. В этом случае такие маркировки или не могут быть достигнуты, или могут быть достигнуты только посредством более длинных цепочек срабатывания переходов.

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

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

Пуст ь (^СХМо.М,,) - множество всех последовательностей срабатывания переходов с]"е0, любых длин п>0. таких что: ц": Мо-»М1 и М£М„.

Определение 2.7. Множество последовательностей срабатывания переходов с минимальными циклами О'=О'(М0,Мн): (З'СМо.М^с^Мо.М,,), Ус|п€<3' не существует яП1еО, чтсяп, т<п.

В работе доказаны свойства множества <3'.

Утверждение 2.9. Множество О' не может• содержать с]? таких, что где ц"! (т>0) - поглощающая последовательность. .

Утверждение 2.10. Цели Мо- начальная маркировка, М„ - произвольная маркировка. Для М;,: М£МИ, н ЗО^О'СМо.МУ. тогда Э(Ц=<3'(М0,МИ) и Зя^зО; т<п такая, что ч'Усч!!.

Утверждение 2.11. Пусть Мо - начальная маркировка, М„ - произвольная маркировка, ВО'=0'(Мо,Ми). Тогда если qл • произвольная последовательность

а (М<1.....Мл') - порождаемые предыдущие маркировки для ч" (М„=МП'),

то не существует М,' и М,' ¡>], таких, что М/>М,'.

На основании свойств множества 0* для алгоритма построения графа достижимости покрывающих маркировок сформулнр'опана теорема.

Теорема. Алгоритм построения графа достижимости покрывающих маркировок С для маркировки М„ на основе начальной маркировки Мо порождает все последовательности из множества 0'=С2'(Ма,Мн).

Доказательство теоремы выполнено по методу математической индукции: Пусть (¡"еС?': Мо->М» и М,;>МИ. Последовательность маркировок

для ч"=(1к|.....(Мо.....М„) М„=М,|. Порожденные предыдущие маркировки

для qn: (Мо.....М„ЛМп). Необходимо доказать,' что qл войдет в множество

последовательностей срабатывания переходов, порождаемое алгоритмом.

На первом шаге индукции, так как то по утверждению (2.9) она

не содержит поглощающих последовательностей, следовательно 1к" имеет как минимум одну выходную позицию и \/р^Оик"): М„(р^>0. Покажем, что Эр;бО(11Ц): М„(р,)>0. Допустим, что Ур^ОЛ1^): Ми(р;)=0, тогда так как МП>М„ и М„.,->МГ1, то М„.,(р,)>М„ОД, получаем: М„.,>МИ. Но

тогда 3ч""''=0к|.....1кп'п.,): М0->МП.| и М„.|>МН и, согласно определению (2.7),

не может входить в 0'. Следовательно, Зр,еО(1к]|): М„(р^>0 и по условию ачгорптма порождаемая предыдущая маркировка для будет включена в список Ь, а соответствующая вершина - в граф в на пятом шаге при первой итерации алгоритма. Также переходу 1к" будет поставлена в соответствие одна из ветвей графа в. Очевидно, что построенная вершина не будет исключена из фафа на четвертом шаге алгоритма при последующей итерации.

На ¡-ом шаге индукции положим, что переход ^""'„.¡ея" входит в одну из ветвей графа в. Докажем, что переход ^" '/¡,.¡.,€4" также будет включен в одну из ветвей графа. Исходя из тог^, что ¿^'¡^ входит в одну из ветвей фафа в, порожденная предыдущая Маркировка Мп.>.1 уже включена в список Ь. Так как переход то по утверждению (2.9) он не может быть переходом-

поглотителем и должен иметь хотя бы одну выходную позицию. Покажем, что Э^еСК^"-'^.,): М„.|/,(рз)>0. Предположим обратное - что Ур^О^0'"^.,)

выполняется М„.;.'|(р^=0. Из предыдущего шаги индукции имеем, что вены»

графа С, соответствующая последовательности .....уже построена

алгоритмом. Рассмотрим данную ветвь и последовательность (1кп'[,......Д1^).

Если в ней пег перехода 1к™ такого, чтобы Зр^О((к""'и р^1(1к™,) и при этом во входные позиции ^ маркеры помещаются переходом 1к"'1'|'.|.,, то повторяя рассуждения, выполненные для перехода на первом шаге

индукции, получаем противоречие Иначе, если 3^-', из (1к"''п^.....

удовлетворяющий указанным условиям, то, рассмотрев шаг алгоритма но порождению предыдущей маркировки М„,.1 для 1к";,, получаем, что М,„.'|(р^>0. Из этого утверждения и принятых для ,и условий следует: ветвь

графа в, соответствующая О1"1*),.......1к£), может быть только при М„ ,-'(р^)>0,

что противоречит сделанному предположению Vpj€0(ík"■|"¡1.1.,): Мп.Др^О. Следовательно, предположение неверно н 1к,1''|'.1.|: Зр^О(1к"' ,): М,,.,.',(р^>0. Тогда по условиям алгоритма 1к|41'4| будет включен в одну из построенных ветвей графа в, а порожденная предыдущая маркировка для нею - в список Ь. Он не может быть исключен из дерева на четвергом ша;е здюриша при последующей итерации, так как а по утверждению (2.11) не

существует порожденных предыдущих маркировок М/ и М,' ¡^ для таких, что М/>М|'.

Из основного положения математической индукции следует, что всем переходам из ч"е<3' будут поставлены в соответствие ветви графа в, построенного алгоритмом, а всем порожденным предыдущим маркировкам -вершины графа. По утверждению (2.6) для ц": М^<Мо. О1едователыю, на третьей шаге при очередной итерации алгоритма в графе О будет построена ветвь (Мо,М!) для ц". Таким образом последовательность ц" и соответствующие ей порожденные предыдущие маркировки (Мо,...,Мп.|,М„) строятся алгоритмом построения графа достижимости покрывающих.

"Рассуждения строились для произвольной справедливы для всех

последовательностей из (}'. Следовательно, алгоритм построения 1рафа достижимости покрывающих маркировок для Мв на основе начальной маркировки Мо порождает все последовательности из

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

этою строится дерево достижимости для F-сетей на основе |рафа достижимости покрывающих маркировок G, который предварительно должен быть построек на основе упрощенной сетевой модели.

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

3. Моделирование параллельных дискретных систем на основе F-

сетей

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

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

Матричный метод основан на использовании матриц смежности С+ и С", Но структура F-сетевой модели не описывается полностью матрицами смежности сети. Поэтому необходимы дополнительные структуры данных, соответствующие переходам и позициям сети. Для матричного метода дополнительные структуры данных представлены векторами переходов и позиции. Объем, занимаемый данными, при этом составляет:

V" = п'Чкр + m*vnoj + 2*n*m*vayr . (3.1),

где v„ep - объем данных, занимаемый одним элементов вектора переходов; v„0j - объем данных, занимаемый одним элементом вектора позиций; vsyr -объем данных, необходимый для хранения элемента матриц С* и С; л ■ количество переходов; m - количество позиций.

Время доступа к элементу матрицы определяется формулой:

ТМ = tajp + tBb,6 (3.2),

где (¡цр - время вычисления адреса строки; 1шг, - время выполнения выборки значения по адресу строки и номеру столбца.

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

УГ = пЧкр 4 П1*у„т + 2*п*кср*(2*Vи,-щ+). (3.3),

где кср - среднее число входных и выходных дуг перехода сети; у„„ц - обьем данных для хранения одного индекса матрицы.

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

Трм = (2-р„,)*кЧг.1» + ^ныб* Рт + 1,>, (3.4).

Для оценки вероятности ненулевого значения элемента матрицы смежности можно использовать формулу:

рВ5 = КУ(п*т) = кср/т (3.5).

Тогда выражение (3.4) можно преобразовать к следующему виду: Трм = (2-кср/ш)*ч+к1рЧра. + 1Вио*(к<гр/т) + I» (3.6),

где К - общее количество входных или выходных дуг переходов сети; рв1 -вероятность ненулевого значения для элемента матрицы смежности; 13„ - время возврата значения из процедуры.

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

V? = п*у„ср + ш*упот + 2*п*кср*(уук+уД)Т) (3.7),

где Уук - объем памяти, необходимый для хранения указателя.

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

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

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

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

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

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

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

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

13 протрам.чпом комплексе реализован событийный алгоритм имитационного моделирования F-сетей, который не требует аи.ениа модели после наступления очередного события, (функционирование алгоритма построено на основе использования динамических списков, полому он назван списковым событийным алгоритмом. Дчя opiainnaiiiiii спискового событийного алгоритма использованы дна списка: список активных переходов, упорядоченный по временам завершения их фазы активной» (список завершения) н неупорядоченный список блокированных переходов.

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

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

4. Моделирование и анализ с помощью Р-сстей на примере системы нпбрацноцной диагностики

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

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

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

В ИИС [ЗД представляет интерес вероятность откладывания передачи пакетов данных, собранных за некоторое количество циклов работы системы. Чтобы решить эту задачу, для 'модели ИИС ВД выполнен анализ по предложенному-в работе методу построения дерева достижимости сети на основе 1рафа достижимости покрывающих маркировок. В результате выполнения анализа модели получены значения вероятности откладывания передачи пакетов данных и времени, за которое может произойти это событие,

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

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

Основные результаты работы

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

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

2. Предложен метод построения дерева достижимости F-сетей на основе графа достижимости покрывающих маркировок, который позволяет повысить его информативность не сравнению со стандартным методом построання.. ;

3. Разработана структура данных для машинного представлении моделей на основе F-сетей и списковый событийный алгоритм имитационного моделирования, которые позволяют сократить объем оперативной памяти ЭВМ, занимаемой описанием модели, и повысить скорость имитационного моделирования для моделей большого объема (свыше 100 переходов).

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

Предложенные методы моделирования и анализа параллельных асинхронных систем реализованы в программном комплексе моделирования и анализа на основе F-сетей "Сети Петри для Windows".

^ Публикации

1. Молчанов А.Ю. Алторнтм-'ацалпза достижимости состояний сложных военно-технических систем, представленных модифицированными сс!ями Петри //Автоматизация процессов управления соединениями и частями ПВО, информационные технологии. Состояние и перспективы создания единой автоматизированной радиолокационной системы /Тез. докл. Научной военно-технической конференции 15-16 мая 1996 года - СПб.: 1996 - с.23-26.

. 2. Молчанов А.Ю. Алгоритм анализа достижимости состояния объектов, представленных сетями Петри /Сборник научн. трудов молодых специалистов ГААП - СПб.: ГААП, 1993 - с.42-46.

3. Молчанов А.Ю. Ме*год диагностирования вычислительных систем на основе расширении сетей Петри //Тез. докл. НТК "Диагностика, информатика и метрология - 95'.* - СПб.: 1995 - с.103-105.

4. Гордеев A.B., Молчанов А.Ю.. Платонов Н.Э. Средства эмуляции мультипроцессорных вычислительных систем //Новые информационные

технологии /Тез. докл. Второй Международной школы-семинара - Гурзуф: 1994 - с.97-98.

5. Гордеев A.B., Домаискнй ВТ., Молчанов А.Ю. Применение сетевых имитационных моделей для оценки надежности функционирования системы диспетчерского контроля н управления /Сб. научн. трудов СПбИИТ - СПб.: 1994 - с.71-76.

6. Гордеев A.B., Доманскнй В.Т., Молчанов А.Ю. Использование сетевых моделей для имитационного моделирования системы диспетчерского контроля н управления устройствами электроснабжения железных дорог //Вестник ВНИИЖТ, 1994,. №1 - с.38-48.

7. Молчанов А.Ю. и др. Опыт создания электронного учебника гю моделированию и анализу сетей Петри /Лез. докл. НТК "Диагностика, информатика и метролошя - 94" - СПб.: 1994 - ч.Н, с,255-257.

8. Гордеев A.B., Молчанов А.Ю. Применение сетей Петри для анализа вычислительных процессов и проектирования вычислительных систем: Учебное пособие - СПб.: ГААП, 1993.

9. Гордеев A.B., Молчанов А.Ю., Платонов И.Э. Диагностирование мультипроцессорных вычислительных систем реального времени //Техническое диагностирование^ /Труды конференции- СПб.:1993 - с. 13-15.

Ю.Гордеев А:В., Молчанов А.Ю. Проектирование вычислительных комплексов с использованием средств имитационного моделирования на основе F-сетей //Информационно-управляющие н вычислительные комплексы на основе новых технологий. /Тез. докл. Всероссийской НТК • СПб.: 1992-с.61-65.

II. Гордеев A.B., Кириллов Н.П., Молчанов А.Ю. Система имитационного моделирования процессов функционирования сложных систем как компонент систем поддержки принятия решений /Материалы ДСП секции прикладных проблем при АН СССР - М.: 1992 - с.34-40.

Электронные учебники

1. Молчанов А.Ю. и др. Сети Петри для Windows, Интегрированная система со встроенными средствами обучения /Электронный учебник - М.:

. РосНИИИС, 1995 - 2,33 Мбайт.

2. Молчанов А.Ю. и др. Интегрированная система моделирования и формального анализа на базе сетей Петрн /Электронный учебник - СПб.: РФНТР, 1994 - 1,36 Мбайт

3. Молчанов А.Ю. и др. Сети Петри, Моделирование и анализ /Электронный учебник - М.: РосНИИИС, 1992 - 1,92 Мбайт.

Лицензия ЯР Ю20341 от 27.I2.9Ir. Подписано к печати 16.04.97г. Печать сфсггна*. Тираж 100 экз. Зака» ЯЧ08 190000, С-Пвтврбург, ул. Б. Морская,67 ь