Содержание к диссертации
/і
Введение 5
Глава I. Сети Петри и параллельные граф-схемы алгоритмов *5
I.I. Сети Петри 13
Определение основных понятий ХЗ
Классы сетей Петри 19
Расширения сетей Петри 22
1.2. Параллельные граф-схашалгоритмов 24
1.2.Ь Определение основных понятий 25
1,2.2« Корректность параллельных граф-схем алгоритмов , , зі
Структурированные ПГСА 35
Методы проверки ПГСА на корректность 41
1,3. Переход, от ПГСА к сети Петри 42
Правила перехода 44
Анализ правил перехода 47
1,4. Постановка задачи проверки ПГСА на корректность . . 5U
Выводы к главе I 52
Глава П. Редукция сетей Петри ЪЪ
2Д. Постановка задачи редукции 53
2.1-І- Определение условий 54
2.1.2. Отличия от ранее введенных преобразований редукции 63
2.2. Определение преобразований редукции 64
2.2.1.Какие вершины можно удалять? 65
2.2.2.Удаление избыточного перехода 68
Удаление избыточной позиции 71
Преобразование подстановки позиции 74
Замена фрагмента . 77
2.3. Анализ преобразований редукции ..... 85
.2.3.1; ЦЗ- эквивалентность преобразований 85
Конечность преобразований 92
Оценки сложности 93
Независимость 94
Локальность 95
Однозначность 96
Нерешенные вопросы редуцирования IOO
2.4. Классы рсдуцируемости сетей Петри ЮІ
Диаграмма алонения классов редуиируемости 101
Доказательство вложении 102
2.5. ' Алгоритм и программа редукции 105
выводы к главе П IU5
Глава Ш. Анализ сетей Петри 107
у 3.1. Декомпозиция FC- сетей 107
Определение понятий . 1и7
№- и L~ условия 115
Объединенный алгоритм проверки условии . 120
Сложность алгоритма и пути ее уменьшения ...... 123
3.2. Построение дерева достинимых .маркировании и исполь
зование его для анализа сети , . 12Ь
3.3. Требования, к алгоритмам анализа сетей Летри на
правильность 133
Выводы к главе Ш '136
Глава ІУ. Применение методики и особенности програм
мной реализации 137
4.1. Применение разработанных методов к анализу некото
рых СИСТеЫ ВЗаИМОДОЙСТВуЮЦИХ ПрОцеССОВ -j-^rj
4.I.I. Проверка асинхронных интерпретации параллельных
микропрограмм на детерминированность . . 139
4-.1.2. Проверка некоторых-овоііств протоколов ...... 143
4.1.3. Иштация процесса формирования и функционирования-
экономических систем . 147
у 4.2. Представление данных и характерные особенности
программы анализа ПГСА на корректность 150
Выводы к главе ІУ 154
Заключение 155
Литература 157
Указатель обозначении 164
Приложение, документы об использовании результатов 169
Введение к работе
Развитие устройств автоматики и вычислительной техники идет по пути усложнения в направлении от последовательной обработки к параллельной* Это обусловлено: во-первых?потребностью во все более производительных и гибких ЭВМ, а во-вторых, возросшими возможностями технологии^приводящими к удешевлению и миниатюризации аппаратуры. Такое развитие характеризуется следующими этапами: от распараллеливания по данным (например^одновременная обработка разрядов в последовательных ЭВМ классической архитектуры) через распараллеливание действий к параллельному управлению. В связи с этим возникает потребность в методах описания анализа и синтеза управления дискретными параллельными системами. Теория таких систем для последовательного случая хорошо известна и давно стала классической рЗ, 17, 18, 23, 38, 45, 48j, однако учет фактора параллельности требует дальнейшего развития этой теории. Попыткой такого развития (в одном из аспектов) и является настоящая работа.
Под дискретной параллельной системой мы будем понимать устройство (или совокупность устройств), реализующее систему последовательных процессов, которые могут выполняться параллельно. В работе JI83 структурная схема вычислительного устройства(абстрактная модель ЭВМ)представляется в виде операционного и управляющего автомата. Дальнейшим развитием (обобщением) этой схемы является представление управляющего автомата как устройства управления со многими связями между управляющим и операционным блоком. Операционный блок (или совокупность таких блоков) может рассматриваться не только как операционный блок вычислительной машины классическо-го (неймановского) типа, но и как многопроцессорная вычислительная система, участок автоматизированного производства, комплекс производственных предприятий и т.п.
Общим для всех этих примеров является то, что в управляемом
блоке реализуется система процессов, каждый из которых состоит из множества действий. Конкретный смысл действий нас не интересует* Единственное требование налагаемое на них состоит в следующем: время выполнения каждого действия является конечным. Действия могут трактоваться по-разному в зависимости от характера рассматриваемой системы, уровня подробности, целей описания, методов анализа и т.п. Так, например, при описании участка автоматизированного производства действие** можно считать операцию или последовательность операций обработки отдельной детали, а при рассмотрении вычислительной машины действие это - в зависимости от уровня рассмотрения - элементарная пересылка, микрокоманда, команда или совокупность команд. Важно подчеркнуть, что действие считается на определенном уровне неделимым, хотя оно может представлять некоторую совокупность действий, рассматриваемых на более детальных уровнях.
Для действий, между которыми не существует причинно-следственной связи, порядок выполнения не определен,- такие действия называются параллельными. Действие реализуется при выполнении оператора. Множество операторов вместе с совокупностью причинно- следственных связей отображается в управляемую систему. Управляющее устройство обеспечивает асинхронный принцип управления, при котором моменты инициации каждого оператора определяются из анализа сигналов готовности к выполнению как данного, так и связанных с ним операторов.
Важным свойством, которому должно удовлетворять описание управляющей системы, является корректность. Корректное описание соответствует такой системе, в которой при реализации взаимодействующих процессов никогда не наступает ситуаций, приводящих к зависанию процессов, взаимной блокировке двух и более процессов и т.п. Свойство корректности обеспечивает, например, обязательное завер-
шение начавшегося вычисления и инвариантность его результата от соотношения продолжительностей времен срабатывания операторов. Как обеспечить корректность описания параллельной системы управления? Методы теории конечных автоматов, которые служая основой для проектирования устройств управления дискретными системами ограничены рассмотрением последовательных процессов. Их возможности оказываются недостаточными для создания способов обеспечения корректной работы системы взаимодействующих процессов. Вопросы теории параллельных процессов исследованы достаточно полно 26, 30, 35, 36, 37, 46, 60 3?однако созданию практических алгоритмов анализа на корректность должного внимания до настоящего времени не уделялось. Использование сетей Петри для такого анализа отражено в работах [50-52, 55, 56 j , связанных с декомпозицией и редукцией сетей Петри.
Целью диссертации является разработка методов анализа на корректность описаний дискретных систем с асинхронными взаимодействиями. Основным требованием при этом является возможность машинного анализа в приемлемое время систем, возникающих в практике.
Достижению цели подчинено создание (или выбор) как способов описания управляемой системы (параллельные граф-схемы алгоритмов) так и средств описания управления, которые отображают все возможные ситуации в управляемой системе и являются основой для проектирования управляющего устройства.
Выбор таких средств должен основываться на сравнительном анализе различных моделей параллельных вычислений. Подробный анализ таких моделей дается в 60 J . В нашем случае в качестве модели были выбраны сети Петри 62] , при этом были учтены следующие соображения:
I) поведение управляемой системы удобно описывать в терминах событий и условий, что соответствует "событиям" - срабатываниям пе-
реходов и "условиям" - значениям функции маркирования в сети Петри;
существует формальное отображение параллельной граф-схемы алгоритма управления в сеть Петри, моделирующую поведение системы [Н-5] ;
сеть Петри можно рассматривать как расширение понятия абстрактного автомата и представить эквивалентным автоматом [IIJ или композицией автоматов [12 J ; следовательно^ методы синтеза устройств управления могут л какой-то мере использовать опыт синтеза конечных автоматов;
сети Петри имеют наглядное графическое представление,что позволяет при разработке и программировании алгоритмов анализа сетей использовать опыт, накопленный при создании матобеспечения для решения задач теории графов; это касается как вопросов представления сетей в памяти ЭВМ [4-4J, так и использования классических алгоритмов таких,как определение сильной связности графа и т.п. [8"] I
математическая теория сетей Петри достаточно хорошо развита, имеются много работ как уршс в стране, так и за рубежом, в которых исследуются различные вопросы, связанные с анализом сетей и их применением для моделирования; не ставя своей целью дать обзор таких работ (имееются по крайней мере две монографин по сетям Петри [53, 62 ]; см.также обзор [42])отметим те,которые
в большей степени повлияли на наши исследования [50-52, 55,56j;
6) кроме того в терминах сетей Петри можно представлять дру
гие модели параллельных вычислений.
Под сетями Петри понимаются в общем случае, так называемые^ обобщенные сети Петри, это такие сети, у которых значение маркирования в каждой позиции-ноль или натуральное число и дуги связывающие позиции и переходы могут иметь кратность большую единицы. Такая
*) оформление диссертации уже было закончено, когда вышла книга: Яотов В.Е. Сети Петри.- М.: Наука, 1984.
общность для наших делай является черезмерной в силу следующего: исходным заданием для синтеза асинхронного устройства управления должно быть удобное и наглядное описание системы взаимодействий^: между операторами. Как показал опыт проектирования микропрограммных автоматов^ таким представлением является граф-схема алгоритма (ГСА) [13,25^). Поэтому представляется целесообразным ввести аналогичный способ описания системы асинхронно взаимодействующих операторов - параллельные граф-схемы алгоритмов (ЛГСА), которые являются расширением обычных граф-схем, широко используемых при описании дискретного управления. Параллельная граф-схама хотя и обладает всей необходимой информацией, но в явной форме не отражает поведения управления системой, а потому не дает наглядного представления о внутренней управляющей логике. Сети Петри и будут тем средств ом,которое призвано моделировать управление в ПГСА, а для такого моделирования вполне достаточно ординарных сетей Петри, которые' являются подклассом обобщенных сетей. К достоинствам ординарных сетей следует отнести то, что алгоритмы анализа таких оетей более просты (по сравнению с алгоритмами анализа обобщенных сетей), имеют меньшие оценки сложности; кроме того применение ординарных сетей позволяет ( в силу компактного представления в памяти ЭВМ) анализировать (в том числе и на корректность) системы с большим числом элементов.
Проблема корректности возникла и наиболее полно исследована в программировании. Однако при синтезе управления (в частности микропрограммного) особенно важно отсутствие некорректностей: в программе некорректность может быть устранена в процессе отладки, а правильность функционирования аппаратуры должна быть обеспечена в процессе синтеза и проектирования. Кроме того, в параллельной микропрограмме по сравнению с параллельной программой интенсивность взаимодействия между операторами намного выше: время взаимодейст-
вия и общее время работы у параллельных микропрограмм сопадают по порядку величины, т.е. на каждое действие приходится ант обмена данными. Это усложнение приводит к тому, что корректности параллельных микропрограмм должно быть уделено повышенное внимание.
Для решения задачи проверки исходного описания управляемой системы, заданного в виде ЇЇГСА, на корректность можно использовать один из следующих подходов.
Пределить правила написания ПГСА так, чтобы при соблюдении этих правил граф-схема получалась заведомо корректной. Проблема корректности, таким образом, сводится к проверке соблюдения определенных правил написания. Этот подход состоит в распространении идей структурного программирования на случай параллельных граф-схем 66, 69Л .
Найти в ПГСА все конфигурации, приводящие к некорректности.
Перейти от ПГСА к ординарной сети Петри, сводя проверку ПГСА на корректность к анализу соответствующей сети Петри на свойство живости и безопасности.
В диссертации для проверки ПГСА на корректность применяется третий из перечисленных подходов. Хотя'переход сети не уменьшает экспоненциальную вычислительную сложность проверки на корректность, он (этот переход) имеет кроме ранее перечисленных достоинств использования сетей Петри для моделирования еще одно. А именно, сложность анализа сети Петри можно существенно уменьшить» сократив сеть применением эквивалентных преобразований (правил редукции). Эквивалентность понимается как сохранение свойств живости и безопасности в отличие от работ [31-32 J , где эквивалентные преобразования приводят к сетям, порождающим один и ют же язык, или от работ С27, 43 J5b которых сети считаются эквивалентными, если они
II (
приводят к тому же конечному автомату. Поскольку целью диссертации является разработка приемлемых по времени методов анализа на корг ректность, то для достижения этой цели были разработаны эквивалентные преобразования редукции (сокращения) исходного описания. На основании этих преобразований созданы практические (с полиномиальной сложностью при степени полинома 2*3) алгоритмы редукции ординарных сетей Петри. Имеющиеся в литературе 50 - 52 J преобразования для аналогичных целей обобщенных сетей Петри нас не удовлетворяют по следующим причинам; во-первых?из-за высокой сложности, а во-вторых, в силу того, что применение преобразований.определенных в 50-52 ];не сохраняет [6 2 свойство безопасности ординарных сетей Петри.
Разработка полиномиальных по сложности преобразований редукции ординарных сетей Петри и исследование вопросов^ связанных с редуцируемостыО;является другой важной задачей, решаемой в диссертации.
Диссертация состоит из введения, четырех глав и заключения. В первой главе определяются понятия относящиеся к сетям Петри и параллельным граф-схемам алгоритмов; исследуется корректность структурированных ПГСА; обосновывается переход от граф-схемы к ее модели г сети Петри, определяются правила такого перехода; доказывается теорема правильности сведения задачи проверки ПГСА на корректность к анализу соответствующей сети Петри на живость и безопасность.
Во второй главе введены преобразования редукции ординарных сетей Петри,сохраняющие живость и безопасность сети. Определены условия применения указанных преобразований такие^как нонечность, полиномиальная сложность, независимость, локальность, однозначность, массовость и полнота. Преобразования проанализированы на выполнение некоторых (наиболее важных для практики) условий.
Введены классы редуцируемости ординарных сетей Петри, соотношения между этими классами систематизированы в виде диаграммы вложения. Дано краткое описание алгоритма редукции.
Тре т ь я глава посвящена методам анализа различных классов сетей Петри. В алгоритме анализа выделено три этапа: редукции; декомпозиция; построение дерева достижимых маркирований. Сформулирован и исследован алгоритм анализа одного из классов (так называемых, сетей свободного выбора) сетей Петри. Рассмотрены вопросы анализа ординарных сетей с использованием дерева достижимости. Сформулированы требования к алгоритму анализа ординарных сетей Петри.
Б четвертой главе на примерах нескольких работ показано применение разработанной методики к анализу параллельных микропрограмм и проверке некоторых свойств протоколов. В задаче моделирования процесса функционирования экономической системы рассмотрена возможность использования ординарных сетей Петри для описания подсистем, поддерживающих исходный экономический потенциал. Кратко описаны представления данных и характерные особенности программы анализа ПГСА на корректность.
В заключении перечислены результаты работы.
