Теория процессов
 Скачать 1.62 Mb.
|
|
Теория процессов А.М.Миронов Предисловие Основу настоящей книги составляют курсы лекций по математи- ческой теории программирования, читавшиеся автором в течение ряда лет для студентов механико-математического факультета и факультета вычислительной математики и кибернетики МГУ имени М.В.Ломоносова, а также для студентов университета г. Переславля-Залесского имени А.К.Айламазяна. В книге дано подробное изложение основных понятий и ре- зультатов исчисления взаимодействующих систем Р.Милнера (см. [89]) и приведён один из возможных вариантов его обобщения для решения задач формального описания и анализа процессов с передачей сообщений. Изложение теоретических понятий и ре- зультатов сопровождается иллюстрациями их применения к ре- шению различных задач верификации процессов. Большинство рассматриваемых примеров взято из книг [89] и [92]. Наряду с известными результатами, в книге изложены ре- зультаты автора по верификации процессов с передачей сообще- ний, и даны примеры применения этих результатов для верифи- кации некоторых процессов с передачей сообщений. Автор пользуется случаем выразить глубокую благодарность за внимание и полезные обсуждения руководителю ведущей рос- сийской научной школы в области теоретической информатики и программирования, заведующему кафедрой математической теории интеллектуальных систем мехмата МГУ академику Ва- лерию Борисовичу Кудрявцеву. Также автор благодарит за внимание и поддержку руковод- ство Университета г. Переславля-Залесского. Особая благодар- ность - проректору Университета Валерии Николаевне Юмагу- жиной. Кроме того, автор выражает благодарность за проявленный интерес и полезные обсуждения всем участникам семинара по анализу и преобразованию программ в Институте Прикладной Математики РАН им. М.В.Келдыша, на котором докладывались изложенные в книге результаты автора по верификации процес- сов с передачей сообщений. 1 Оглавление 1 Введение 8 1.1 Предмет теории процессов . . . . . . . . . . . . . . 8 1.2 Верификация процессов . . . . . . . . . . . . . . . . 11 1.3 Спецификация процессов . . . . . . . . . . . . . . . 12 2 Понятие процесса 14 2.1 Представление поведения динамических систем в виде процессов . . . . . . . . . . . . . . . . . . . . . 14 2.2 Неформальное понятие процесса и примеры про- цессов . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.1 Неформальное понятие процесса 15 2.2.2 Пример процесса . . . . . . . . . . . . . . . . 16 2.2.3 Другой пример процесса . . . . . . . . . . . 18 2.3 Действия . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4 Определение понятия процесса . . . . . . . . . . . . 21 2.5 Понятие трассы 23 2.6 Достижимые и недостижимые состояния . . . . . . 24 2.7 Замена состояний . . . . . . . . . . . . . . . . . . . 25 3 Операции на процессах 27 3.1 Префиксное действие . . . . . . . . . . . . . . . . . 27 3.2 Пустой процесс . . . . . . . . . . . . . . . . . . . . . 28 3.3 Альтернативная композиция . . . . . . . . . . . . . 29 3.4 Параллельная композиция . . . . . . . . . . . . . . 35 3.5 Ограничение . . . . . . . . . . . . . . . . . . . . . . 52 3.6 Переименование . . . . . . . . . . . . . . . . . . . . 55 3.7 Свойства операций на процессах . . . . . . . . . . . 55 2 4 Эквивалентность процессов 63 4.1 Понятие эквивалентности процессов и связанные с ним задачи . . . . . . . . . . . . . . . . . . . . . . . 63 4.2 Трассовая эквивалентность процессов . . . . . . . . 64 4.3 Сильная эквивалентность . . . . . . . . . . . . . . . 67 4.4 Критерии сильной эквивалентности . . . . . . . . . 71 4.4.1 Логический критерий сильной эквивалент- ности 71 4.4.2 Критерий сильной эквивалентности, осно- ванный на понятии бимоделирования . . . . 73 4.5 Алгебраические свойства сильной эквивалентности 74 4.6 Распознавание сильной эквивалентности . . . . . . 83 4.6.1 Отношение µ(P 1 , P 2 ) . . . . . . . . . . . . . . 83 4.6.2 Полиномиальный алгоритм распознавания сильной эквивалентности . . . . . . . . . . . 85 4.7 Минимизация процессов 88 4.7.1 Свойства отношений вида µ(P, P ) . . . . . . 88 4.7.2 Минимальные процессы относительно ∼ . . 91 4.7.3 Алгоритм минимизации процессов . . . . . . 94 4.8 Наблюдаемая эквивалентность . . . . . . . . . . . . 96 4.8.1 Определение наблюдаемой эквивалентности 96 4.8.2 Логический критерий наблюдаемой эквива- лентности . . . . . . . . . . . . . . . . . . . . 100 4.8.3 Критерий наблюдаемой эквивалентности, ос- нованный на понятии наблюдаемого БМ . . 102 4.8.4 Алгебраические свойства наблюдаемой эк- вивалентности . . . . . . . . . . . . . . . . . 104 4.8.5 Распознавание наблюдаемой эквивалентно- сти и минимизация процессов относительно ≈ . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.8.6 Другие критерии эквивалентности процессов 107 4.9 Наблюдаемая конгруэнция . . . . . . . . . . . . . . 108 4.9.1 Мотивировка понятия наблюдаемой конгру- энции . . . . . . . . . . . . . . . . . . . . . . 108 4.9.2 Определение понятия наблюдаемой конгру- энции . . . . . . . . . . . . . . . . . . . . . . 110 4.9.3 Логический критерий наблюдаемой конгру- энтности . . . . . . . . . . . . . . . . . . . . 112 3 4.9.4 Критерий наблюдаемой конгруэнтности, ос- нованный на понятии НБМ . . . . . . . . . . 113 4.9.5 Алгебраические свойства наблюдаемой кон- груэнции . . . . . . . . . . . . . . . . . . . . 114 4.9.6 Распознавание наблюдаемой конгруэнтности 125 4.9.7 Минимизация процессов относительно на- блюдаемой конгруэнции . . . . . . . . . . . . 125 5 Рекурсивные определения процессов 127 5.1 Процессные выражения . . . . . . . . . . . . . . . . 127 5.2 Понятие рекурсивного определения процессов . . . 128 5.3 Вложение процессов . . . . . . . . . . . . . . . . . . 129 5.4 Предел последовательности вложенных процессов 131 5.5 Процессы, определяемые процессными выражени- ями . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 5.6 Эквивалентность РО . . . . . . . . . . . . . . . . . 135 5.7 Переходы на P Expr . . . . . . . . . . . . . . . . . . 137 5.8 Доказательство эквивалентности процессов при по- мощи РО . . . . . . . . . . . . . . . . . . . . . . . . 139 5.9 Проблемы, связанные с понятием РО . . . . . . . . 140 6 Примеры доказательства свойств процессов 141 6.1 Потоковые графы . . . . . . . . . . . . . . . . . . . 141 6.2 Мастерская . . . . . . . . . . . . . . . . . . . . . . . 143 6.3 Неконфликтное использование ресурса . . . . . . . 147 6.4 Планировщик . . . . . . . . . . . . . . . . . . . . . . 151 6.5 Семафор . . . . . . . . . . . . . . . . . . . . . . . . 163 7 Процессы с передачей сообщений 166 7.1 Действия с передачей сообщений . . . . . . . . . . 166 7.2 Вспомогательные понятия . . . . . . . . . . . . . . 168 7.2.1 Типы, переменные, значения и константы . 168 7.2.2 Функциональные символы . . . . . . . . . . 169 7.2.3 Выражения . . . . . . . . . . . . . . . . . . . 170 7.3 Понятие процесса с передачей сообщений . . . . . 172 7.3.1 Множество переменных процесса . . . . . . 173 7.3.2 Начальное условие . . . . . . . . . . . . . . . 173 7.3.3 Операторы . . . . . . . . . . . . . . . . . . . 173 4 7.3.4 Определение процесса . . . . . . . . . . . . . 175 7.3.5 Функционирование процесса . . . . . . . . . 176 7.4 Изображение процессов в виде блок-схем . . . . . . 178 7.4.1 Понятие блок-схемы . . . . . . . . . . . . . . 178 7.4.2 Функционирование блок-схемы . . . . . . . 182 7.4.3 Построение процесса, определяемого блок-- схемой . . . . . . . . . . . . . . . . . . . . . . 185 7.5 Пример процесса с передачей сообщений . . . . . . 187 7.5.1 Понятие буфера . . . . . . . . . . . . . . . . 187 7.5.2 Представление поведения буфера в виде блок- схемы . . . . . . . . . . . . . . . . . . . . . . 189 7.5.3 Представление поведения буфера в виде про- цесса . . . . . . . . . . . . . . . . . . . . . . . 190 7.6 Операции на процессах с передачей сообщений . . 192 7.6.1 Префиксное действие . . . . . . . . . . . . . 192 7.6.2 Альтернативная композиция . . . . . . . . . 193 7.6.3 Параллельная композиция . . . . . . . . . . 193 7.6.4 Ограничение . . . . . . . . . . . . . . . . . . 194 7.6.5 Переименование . . . . . . . . . . . . . . . . 195 7.7 Эквивалентность процессов . . . . . . . . . . . . . . 195 7.7.1 Понятие конкретизации процесса . . . . . . 195 7.7.2 Понятие эквивалентности процессов . . . . 197 7.8 Процессы с составными операторами . . . . . . . . 198 7.8.1 Мотивировка понятия процесса с составны- ми операторами . . . . . . . . . . . . . . . . 198 7.8.2 Понятие составного оператора . . . . . . . . 199 7.8.3 Понятие процесса с СО . . . . . . . . . . . . 200 7.8.4 Функционирование процесса с СО . . . . . . 200 7.8.5 Операции на процессах с СО . . . . . . . . . 201 7.8.6 Преобразование процессов с передачей со- общений в процессы с СО . . . . . . . . . . . 202 7.8.7 Конкатенация СО . . . . . . . . . . . . . . . 203 7.8.8 Редукция процессов с СО . . . . . . . . . . . 205 7.8.9 Пример редукции . . . . . . . . . . . . . . . 207 7.8.10 Понятие конкретизации процесса с СО . . . 212 7.8.11 Отношения эквивалентности на процессах с СО . . . . . . . . . . . . . . . . . . . . . . . . 214 5 7.8.12 Метод доказательства наблюдаемой эквива- лентности процессов с СО . . . . . . . . . . 215 7.8.13 Пример доказательства наблюдаемой экви- валентности процессов с СО . . . . . . . . . 219 7.8.14 Дополнительные замечания . . . . . . . . . 222 7.8.15 Другой пример доказательства наблюдаемой эквивалентности процессов с СО . . . . . . 226 7.9 Рекурсивные определения процессов . . . . . . . . 232 8 Примеры процессов с передачей сообщений 235 8.1 Разделение множеств . . . . . . . . . . . . . . . . . 235 8.1.1 Задача разделения множеств . . . . . . . . . 235 8.1.2 Распределённый алгоритм решения задачи разделения множеств . . . . . . . . . . . . . 235 8.1.3 Процессы Small и Large . . . . . . . . . . . . 237 8.1.4 Анализ алгоритма разделения множеств . . 238 8.2 Вычисление квадрата . . . . . . . . . . . . . . . . . 243 8.3 Сети Петри . . . . . . . . . . . . . . . . . . . . . . . 248 8.4 Протоколы передачи данных в компьютерных сетях 249 8.4.1 Понятие протокола . . . . . . . . . . . . . . 249 8.4.2 Методы исправления искажений в кадрах . 250 8.4.3 Методы обнаружения искажений в кадрах . 254 8.4.4 Пример протокола . . . . . . . . . . . . . . . 259 8.4.5 Протокол с чередующимися битами . . . . . 267 8.4.6 Двунаправленная передача . . . . . . . . . . 273 8.4.7 Дуплексный протокол с чередующимися би- тами . . . . . . . . . . . . . . . . . . . . . . . 274 8.4.8 Двунаправленная конвейерная передача . . 277 8.4.9 Протокол скользящего окна с возвратом . . 278 8.4.10 Протокол скользящего окна с выборочным повтором . . . . . . . . . . . . . . . . . . . . 283 8.5 Криптографические протоколы . . . . . . . . . . . 289 8.5.1 Понятие криптографического протокола . . 289 8.5.2 Шифрование сообщений . . . . . . . . . . . 292 8.5.3 Формальное описание КП . . . . . . . . . . 294 8.5.4 Примеры КП . . . . . . . . . . . . . . . . . . 295 6 9 Представление структур данных в виде процессов303 9.1 Понятие структуры данных . . . . . . . . . . . . . 303 9.2 СД “память с 2 k ячейками” . . . . . . . . . . . . . . 304 9.3 СД “стек” . . . . . . . . . . . . . . . . . . . . . . . . 308 9.4 СД “очередь” . . . . . . . . . . . . . . . . . . . . . . 309 10 Семантика языка параллельного программирова- ния 311 10.1 Описание языка параллельного программирования 311 10.1.1 Конструкции языка L . . . . . . . . . . . . . 312 10.1.2 Программы на языке L . . . . . . . . . . . . 314 10.2 Семантика языка L . . . . . . . . . . . . . . . . . . 315 10.2.1 Семантика выражений . . . . . . . . . . . . 316 10.2.2 Семантика деклараций . . . . . . . . . . . . 317 10.2.3 Семантика операторов . . . . . . . . . . . . 318 11 Исторический обзор и современное состояние дел 320 11.1 Робин Милнер . . . . . . . . . . . . . . . . . . . . . 320 11.2 Исчисление взаимодействующих систем (CCS) . . 321 11.3 Теория взаимодействующих последовательных про- цессов (CSP) . . . . . . . . . . . . . . . . . . . . . . 322 11.4 Алгебра взаимодействующих процессов (ACP) . . 323 11.5 Процессные алгебры . . . . . . . . . . . . . . . . . . 323 11.6 Мобильные процессы . . . . . . . . . . . . . . . . . 326 11.7 Гибридные системы . . . . . . . . . . . . . . . . . . 327 11.8 Другие математические теории и программные сред- ства, связанные с моделированием процессов . . . 327 11.9 Бизнес-процессы . . . . . . . . . . . . . . . . . . . . 328 7 Глава 1 Введение 1.1 Предмет теории процессов Теория процессов является одним из разделов математической теории программирования, который изучает математические мо- дели поведения динамических систем, называемые процессами. Говоря неформально, процесс представляет собой модель та- кого поведения, которое заключается в исполнении действий. Такими действиями могут быть, например, • приём или передача каких-либо объектов, или • преобразование этих объектов. Основные достоинства теории процессов как математическо- го аппарата, предназначенного для моделирования и анализа ди- намических систем, заключаются в следующем. 1. Аппарат теории процессов хорошо подходит для формаль- ного описания и анализа поведения распредел¨ енных ди- намических систем, т.е. таких систем, которые состоят из нескольких взаимодействующих компонентов, причем • все эти компоненты работают параллельно, и • взаимодействие компонентов происходит путём пере- сылки сигналов или сообщений от одних компонентов другим компонентам. 8 Важнейшим примером распределенных динамических си- стем являются программно-аппаратные вычислительные ком- плексы, в которых • один класс компонентов определяется совокупностью компьютерных программ, которые функционируют в этом комплексе • другой класс компонентов связан с аппаратной плат- формой, на базе которой функционирует этот комплекс • третий класс компонентов представляет собой сово- купность информационных ресурсов (базы данных, ба- зы знаний, электронные библиотеки, и т.п.), которые используются для обеспечения функционирования это- го комплекса • также может приниматься во внимание класс компо- нентов, связанных с человеческим фактором. 2. Методы теории процессов позволяют анализировать с при- емлемой сложностью модели с очень большим и даже бес- конечным множеством состояний. Это возможно благода- ря разработанной в теории процессов технике символьных преобразований выражений, описывающих процессы. Важнейшим примером моделей с бесконечным множеством состояний являются модели компьютерных программ с пе- ременными, множества значений которых имеют очень боль- шой размер. В таких моделях программ в целях удобства проведения рассуждений большие множества значений неко- торых переменных заменяются на соответствующие беско- нечные множества. Например, множество значений пере- менных типа double, представляющее собой конечную (но очень большую) совокупность действительных чисел, мо- жет быть заменено на бесконечное множество всех действи- тельных чисел. В некоторых случаях представление анализируемой про- граммы в виде модели с бесконечным множеством состо- яний существенно упрощает проведение рассуждений об 9 этой программе. Анализ модели этой программы с конеч- ным, но очень большим множеством состояний классиче- скими методами теории автоматов, которые основаны на • явном представлении множества состояний этой моде- ли, и • анализе этой модели путём явного оперирования с её состояниями может иметь очень высокую вычислительную сложность, и в некоторых случаях замена • задачи анализа исходной конечной модели • на задачу анализа соответствующей бесконечной моде- ли такими методами, которые основаны на символь- ных преобразованиях выражений, описывающих эту модель, может дать существенный выигрыш с точки зрения вычис- лительной сложности. 3. Методы теории процессов хорошо подходят для изучения иерархических систем, т.е. таких систем, которые имеют многоуровневую структуру. Каждая компонента таких систем рассматривается как под- система, которая, в свою очередь, может состоять из несколь- ких подкомпонентов. Каждая из этих подкомпонентов мо- жет взаимодействовать • с другими подкомпонентами, и • с системами более высокого уровня. Основными источниками задач и объектами применения ре- зультатов теории процессов являются распределенные компью- терные системы. Вместе с тем, теория процессов может использоваться также для моделирования и анализа поведения систем самой различ- ной природы, важнейшими примерами которых являются орга- низационные системы. К их числу относятся 10 • системы управления деятельностью предприятий, • государственные структуры, • системы организации коммерческих процессов (например, системы организации торговых сделок, аукционов, и т.п.) Процессы, относящиеся к функционированию таких систем, принято называть бизнес-процессами. 1.2 Верификация процессов Наиболее важный класс задач, для решения которых предназна- чена теория процессов, связан с проблемой верификации процес- сов. Проблема верификации процесса заключается в построении формального доказательства того, что анализируемый процесс обладает заданными свойствами. Для многих процессов данная задача представляет исключи- тельную актуальность. Например, безопасная эксплуатация та- ких систем, как • системы управления атомными электростанциями, • медицинские устройства с компьютерным управлением, • бортовые системы управления самолетов и космических ап- паратов, • системы управления секретными базами данных, • системы электронной коммерции невозможна без удовлетворительного решения задачи верифика- ции свойств корректности и безопасности процессов, функциони- рующих в таких системах, так как нарушения данных свойств в системах подобного типа могут привести к существенному ущер- бу для экономики и самой жизни людей. Точная постановка задачи верификации состоит из следую- щих частей. 11 1. Построение процесса, представляющего собой математиче- скую модель поведения анализируемой системы. 2. Представление проверяемого свойства в виде математиче- ского объекта (называемого спецификацией). 3. Построение математического доказательства утверж- дения о том, что построенный процесс удовлетворяет спе- цификации. 1.3 Спецификация процессов Спецификация процесса представляет собой описание свойств этого процесса в виде некоторого математического объекта. Примером спецификации является требование надежности пе- редачи данных через ненадежную среду. При этом не указыва- ется, как именно должна обеспечиваться эта надежность. В качестве спецификации могут выступать, например, следу- ющие объекты. 1. Логическая формула, выражающая некоторое требование к процессу. Например, таким требованием может быть условие того, что если процесс получил некоторый запрос, то через неко- торое заданное время процесс выдаст ответ на этот запрос. 2. Представление анализируемого процесса на более высоком уровне абстракции. Данный вид спецификаций используется при многоуров- невом проектировании процессов: реализацию процесса на каждом уровне проектирования можно рассматривать как спецификацию для реализации этого процесса на следую- щем уровне проектирования. 3. Некоторый эталонный процесс, относительно которого пред- полагается, что он обладает заданным свойством. В этом случае задача верификации заключается в постро- ении доказательства эквивалентности эталонного и анали- зируемого процессов. 12 При построении спецификаций следует руководствоваться сле- дующими принципами. 1. Одно и то же свойство процесса может быть выражено на разных языках спецификаций (ЯС), и • на одном ЯС оно может иметь простую специфика- цию, • а на другом – сложную. Например, спецификация, описывающая связь между вход- ными и выходными значениями для программы, вычисляю- щей разложение целого числа на простые множители, име- ет • сложный вид на языке логики предикатов, но • простой вид, если выразить эту спецификацию в виде некоторой эталонной программы. Поэтому для представления свойства процесса в виде спе- цификации важно выбрать такой ЯС, на котором специфи- кация этого свойства имела бы наиболее ясный и простой вид. 2. Если свойство процесса изначально было выражено на есте- ственном языке, то при переводе его в спецификацию важ- но обеспечить соответствие между • естественно-языковым описанием этого свойства, и • его спецификацией, т.к. в случае несоблюдения этого условия результаты вери- фикации не будут иметь смысла. 13 Глава 2 Понятие процесса 2.1 Представление поведения динамиче- ских систем в виде процессов Один из возможных методов математического моделирования поведения динамических систем заключается в представлении поведения этих систем в виде процессов. Процесс, как правило, не учитывает всех деталей поведения анализируемой системы. Одно и то же поведение может быть представлено различными процессами, отражающими • разную степень абстракции при построении модели этого поведения, и • разные уровни детализации действий, исполняемых систе- мой. Если целью построения процесса для представления поведения некоторой системы является проверка свойств этого поведения, то выбор уровня детализации действий системы должен произво- диться с учётом тех свойств, которые необходимо проанализиро- вать. Построение процесса, представляющего поведение анали- зируемой системы, должно производиться с учётом следующих принципов. 1. Описание процесса не должно быть чрезмерно детальным, т.к. излишняя сложность этого описания может вызвать 14 существенные вычислительные проблемы при формальном анализе этого процесса. 2. Описание процесса не должно быть чрезмерно упрощён- ным, оно должно • отражать те аспекты поведения моделируемой систе- мы, которые имеют отношение к проверяемым свой- ствам, и • сохранять все свойства поведения этой системы, кото- рые представляют интерес для анализа т.к. в случае несоблюдения этого условия результаты ана- лиза такого процесса не будут иметь смысла. 2.2 Неформальное понятие процесса и примеры процессов Прежде чем сформулировать точное определение процесса, мы приведём неформальное понятие процесса, и рассмотрим про- стейшие примеры процессов. 2.2.1 Неформальное понятие процесса Как было сказано выше, мы понимаем под процессом модель по- ведения динамической системы на некотором уровне абстракции. Процесс можно представлять себе как граф P , компоненты которого имеют следующий смысл. • Вершины графа P называются состояниями, и изобража- ют ситуации (или классы ситуаций), в которых может нахо- диться моделируемая система в различные моменты своего функционирования. Одно из состояний является выделенным, оно называется начальным состоянием процесса P . • Рёбра графа P имеют метки, изображающие действия, ко- торые может исполнять моделируемая система. 15 • Функционирование процесса P описывается переходами по рёбрам графа P от одного состояния к другому. Функцио- нирование начинается из начального состояния. Метка каждого ребра изображает действие процесса, ис- полняемое при переходе от состояния в начале ребра к со- стоянию в его конце. 2.2.2 Пример процесса В качестве первого примера рассмотрим процесс, представляю- щий собой простейшую модель поведения некоторого торгового автомата. Мы будем представлять себе этот автомат как машину, кото- рая имеет • монетоприемник, • кнопку, и • лоток для выдачи товара. Когда покупатель хочет приобрести товар, он • опускает монету в монетоприемник, • нажимает на кнопку и после этого в лотке появляется товар. Предположим, что наш автомат торгует шоколадками по цене 1 монета за штуку. Опишем действия такого автомата. • По инициативе покупателя, в автомате могут происходить следующие действия: – попадание в щель монеты, и – нажатие кнопки. • В ответ автомат может осуществлять реакцию: выдавать в лоток шоколадку. 16 Обозначим действия короткими именами: • прием монеты мы обозначим символом пр_мон, • нажатие кнопки - символом наж_кн, и • выдачу шоколадки - символом выд_шок. Процесс нашего торгового автомата выглядит следующим об- разом: s 0 s 1 s 2 ? - @ @ @ @ @ @ @ @ @ I пр_мон наж_кн выд_шок Данная диаграмма объясняет, как именно функционирует тор- говый автомат: • вначале автомат находится в состоянии s 0 , в этом состоянии он ожидает появления в приемнике монеты (то, что состояние s 0 является начальным, изображается на диаграмме двойным кружочком вокруг идентификатора этого состояния) • когда монета появляется, автомат переходит в состояние s 1 и ждет нажатия на кнопку, • после нажатия кнопки автомат – переходит в состояние s 2 , – выдает шоколадку, и – возвращается в состояние s 0 17 2.2.3 Другой пример процесса Рассмотрим более сложный пример торгового автомата, который отличается от предыдущего тем, что продаёт два вида товаров: чай и кофе, причём стоимость чая - 1 рубль, а стоимость кофе - 2 рубля. Автомат имеет две кнопки: одну - для чая, другую - для кофе. Покупатель может платить монетами достоинством в 1 рубль и 2 рубля. Данные монеты будут обозначаться знакосочетаниями мон_1 и мон_2 соответственно. Если покупатель опустил в монетоприемник монету мон_1, он может купить только чай. Если же он опустил монету мон_2, он может купить кофе или два чая. Кофе можно купить также, опустив в монетоприёмник две монеты мон_1. Процесс такого торгового автомата выглядит следующим об- разом: s 0 s 1 s 2 s 3 s 4 s 5 ? ? пр_мон_1 пр_мон_2 пр_мон_1 наж_кн_чай выд_чай наж_кн_чай выд_чай наж_кн_кофе выд_кофе @ @ @ @ I @ @ @ @ I 6 - Для формального определения понятия процесса мы должны уточнить понятие действия. Это уточнение излагается в парагра- фе 2.3. 18 2.3 Действия Для задания процесса P , представляющего собой модель пове- дения некоторой динамической системы, должно быть указано некоторое множество Act(P ) действий, которые может выпол- нять процесс P . Мы будем предполагать, что действия всех процессов явля- ются элементами некоторого универсального множества Act всех возможных действий, которые может выполнить какой-либо про- цесс, т.е. для любого процесса P Act(P ) ⊆ Act Выбор множества Act(P ) действий процесса P зависит от це- лей моделирования. В разных ситуациях для представления мо- дели анализируемой системы в виде некоторого процесса могут выбираться разные множества действий. Мы будем предполагать, что множество действий Act делится на 3 следующих класса. 1. Входные действия, которые изображаются знакосочета- ниями вида α? Действие вида α? интерпретируется как ввод в процесс неко- торого объекта с именем α. 2. Выходные действия, которые изображаются знакосоче- таниями вида α! Действие вида α! интерпретируется как вывод из процесса некоторого объекта с именем α. 3. Внутреннее (или невидимое) действие, которое обозна- чается символом τ . Внутренним мы называем такое действие процесса P , ко- торое не связано с его взаимодействием с окружающей средой (т.е. с процессами, являющимися внешними по от- ношению к процессу P , и с которыми он может взаимодей- ствовать). 19 Например, внутреннее действие может быть связано с вза- имодействием компонентов процесса P . В действительности, внутренние действия могут быть са- мыми разнообразными, но для обозначения всех внутрен- них действий мы будем использовать один и тот же символ τ . Это отражает наше желание не различать все внутрен- ние действия, т.к. они не являются “наблюдаемыми” извне процесса P . Обозначим знакосочетанием Names совокупность имён объ- ектов, которые могут вводиться в какой-либо процесс нли выво- диться из него. Мы не накладываем никаких ограничений на виды объек- тов, с которыми могут оперировать процессы, поэтому множе- ство N ames предполагается бесконечным. Множество Act по определению представляет собой дизъюнк- ное объединение Act = {α? | α ∈ N ames} ∪ ∪ {α! | α ∈ N ames} ∪ ∪ {τ } (2.1) Отметим, что объекты, которые вводятся в процесс и выво- дятся из него, могут иметь самую различную природу (как мате- риальную, так и не материальную). Например, ими могут быть • материальные ресурсы, • люди, • деньги, • информация, • энергия, • и т.д. Кроме того, сами понятия ввода и вывода могут иметь вирту- альный характер, т.е. слова “ввод” и “вывод” могут использовать- ся лишь как метафоры, а в действительности никакого ввода или 20 вывода какого-либо реального объекта может и не происходить. Говоря неформально, мы будем рассматривать действие процес- са P как • входное, если его инициатором является процесс, внешний по отношению к P , и • выходное, если оно не является внутренним, и его иници- атором является сам процесс P . Для каждого имени α ∈ N ames действия α? и α! называются комплементарными. Мы будем использовать следующие обозначения. 1. Для каждого действия a ∈ Act \ {τ } знакосочетание ¯ a обо- значает действие, комплементарное к a, т.е. α? def = α!, α! def = α? 2. Для каждого действия a ∈ Act\{τ } знакосочетание name(a) обозначает имя, указанное в действии a, т.е. name(α?) def = name(α!) def = α 3. Для каждого подмножества L ⊆ Act \ {τ } • L def = {a | a ∈ L} • names(L) def = {name(a) | a ∈ L} 2.4 Определение понятия процесса Процессом называется тройка P вида P = (S, s 0 , R) (2.2) компоненты которой имеют следующий смысл. • S - множество, элементы которого называются состояни- ями процесса P . 21 • s 0 ∈ S – некоторое выделенное состояние, называемое на- чальным состоянием процесса P . • R – подмножество вида R ⊆ S × Act × S Элементы множества R называются переходами. Если переход из R имеет вид (s 1 , a, s 2 ), то – мы будем говорить, что этот переход является пере- ходом из состояния s 1 в состояние s 2 с выполнением действия a, – состояния s 1 и s 2 называются началом и концом это- го перехода соответственно, а действие a называется меткой этого перехода, и – иногда, в целях повышения наглядности, мы будем обозначать данный переход знакосочетанием s 1 - a s 2 (2.3) Функционирование процесса P = (S, s 0 , R) заключается в порождении последовательности переходов вида s 0 - a 0 s 1 - a 1 s 2 - a 2 и выполнении действий a 0 , a 1 , a 2 . . ., соответствующих этим пе- реходам. Более подробно: на каждом шаге функционирования i ≥ 0 • процесс находится в некотором состоянии s i (s 0 = s 0 ), • если есть хотя бы один переход из R с началом в s i , то процесс – недетерминированно выбирает переход с началом в s i , помеченный таким действием a i , которое можно вы- полнить в текущий момент времени, (если таких переходов нет, то процесс временно при- останавливает свою работу до того момента, когда по- явится хотя бы один такой переход) 22 – выполняет действие a i , и после этого – переходит в состоние s i+1 , которое является концом выбранного перехода • если в R нет переходов с началом в s i , то процесс заканчи- вает свою работу. Знакосочетание Act(P ) обозначает множество всех действий из Act \ {τ }, которые могут быть выполнены процессом P , т.е. Act(P ) def = {a ∈ Act \ {τ } | ∃ ( s 1 - a s 2 ) ∈ R} Процесс (2.2) называется конечным, если его компоненты S и R являются конечными множествами. Конечный процесс можно изображать геометрически, в виде диаграммы на плоскости, в которой • каждому состоянию соответствует некоторый кружочек на плоскости, в котором может быть написан идентификатор, представляющий собой имя этого состояния, • каждому переходу соответствует стрелка, соединяющая на- чало этого перехода и его конец, причём на стрелке напи- сана метка этого перехода, • начальное состояние выделяется некоторым образом (на- пример, вместо обычного кружочка рисуется двойной кру- жочек). Примеры таких диаграмм содержатся в параграфах 2.2.2 и 2.2.3. 2.5 Понятие трассы Пусть P = (S, s 0 , R) – некоторый процесс. Трассой процесса P называется конечная или бесконечная последовательность a 1 , a 2 , . . . элементов множества Act, такая что существует последователь- ность состояний процесса P s 0 , s 1 , s 2 , . . . 23 обладающая следующими свойствами: • s 0 совпадает с начальным состоянием s 0 процесса P • для каждого i ≥ 1 множество R содержит переход s i - a i s i+1 Множество всех трасс процесса P мы будем обозначать через T r(P ). 2.6 Достижимые и недостижимые состо- яния Пусть P – процесс вида (2.2). Состояние s процесса P называется достижимым, если s = s 0 или существует последовательность переходов в P , имеющая вид s 0 - a 1 s 1 , s 1 - a 2 s 2 , s n−1 - a n s n в которой n ≥ 1, s 0 = s 0 и s n = s. Состояние называется недостижимым, если оно не являет- ся достижимым. Нетрудно видеть, что после после того, как • из S будут удалены недостижимые состояния, и • из R будут удалены переходы, в которых присутствуют недостижимые состояния, получившийся процесс P 0 (который иногда называют достижи- мой частью процесса P ) будет представлять точно такое же поведение, которое представлял исходный процесс. По этой при- чине мы будем рассматривать такие процессы P и P 0 как одина- ковые. 24 2.7 Замена состояний Пусть • P – процесс вида (2.2), • s – некоторое состояние из S • s 0 – произвольный элемент, не принадлежащий множеству S. Обозначим символом P 0 процесс, который получается из P заме- ной s на s 0 в множествах S и R, т.е., в частности, каждый переход в P вида s - a s 1 или s 1 - a s заменяется на переход s 0 - a s 1 или s 1 - a s 0 соответственно. Как и в предыдущем параграфе, нетрудно видеть, что P 0 бу- дет представлять точно такое же поведение, которое представлял P , и по этой причине мы можем рассматривать такие процессы P и P 0 как одинаковые. Также отметим, что заменять можно не одно состояние, а произвольное подмножество состояний процесса P . Такую заме- ну можно представить как задание взаимно однозначного отоб- ражения f : S → S 0 (2.4) и результатом такой замены по определению является процесс P 0 вида P 0 = (S 0 , (s 0 ) 0 , R 0 ) (2.5) где • (s 0 ) 0 def = f (s 0 ), и • для каждой пары s 1 , s 2 ∈ S и каждого a ∈ Act ( s 1 - a s 2 ) ∈ R ⇔ ( f (s 1 ) - a f (s 2 ) ) ∈ R 0 25 Поскольку такие процессы P и P 0 представляют одинаковое по- ведение, мы можем рассматривать их как одинаковые. Отметим, что в литературе по теории процессов такие про- цессы P и P 0 иногда называют не одинаковыми, а изоморф- ными. Отображение (2.4) с указанными выше свойствами на- зывают изоморфизмом между P и P 0 . Процесс P 0 называют изоморфной копией процесса P . 26 Глава 3 Операции на процессах В этой главе мы определим некоторые операции на процессах, при помощи которых из одних процессов мы сможем строить другие, более сложные процессы. 3.1 Префиксное действие Первая такая операция - префиксное действие. Пусть заданы • процесс P = (S, s 0 , R), и • действие a ∈ Act. Действие операции префиксного действия a. на процесс P заключается в том, что • к множеству состояний P добавляется новое состояние s, которое будет начальным состоянием нового процесса, и • к множеству переходов добавляется переход s - a s 0 Получившийся процесс обозначается знакосочетанием a.P 27 Проиллюстрируем действие данной операции на примере тор- гового автомата из параграфа 2.2.2. Обозначим процесс, пред- ставляющий поведение этого автомата, символом P та Расширим множество действий данного автомата новым вход- ным действием вкл?, которое будет означать включение этого автомата в сеть. Процесс вкл?. P та представляет поведение нового торгового автомата, который в начальном состоянии не может • ни принимать монет, • ни воспринимать нажатия на кнопку, • ни выдавать шоколадок. Единственное, что он может - это стать включенным. После этого его поведение ничем не будет отличаться от поведения исходного автомата. Графовое представление процесса вкл?. P та выглядит следу- ющим образом: s s 0 s 1 s 2 ? - - @ @ @ @ @ @ @ @ @ I вкл? мон? кн? шок! 3.2 Пустой процесс Среди всех процессов существует один наиболее простой. Этот процесс имеет всего одно состояние, и не имеет переходов. Для обозначения такого процесса мы будем использовать константу (т.е. нульарную операцию) 0. 28 Возвращаясь к примерам с торговыми автоматами, можно сказать, что процесс 0 представляет поведение сломанного авто- мата, то есть такого автомата, который вообще не может ничего делать. Путем применения операций префиксного действия к процес- су 0 можно определять поведение более сложных автоматов. Рас- смотрим, например, такой процесс: P = мон?.кн?.шок!.0 Графовое представление этого процесса выглядит следую- щим образом: s 0 s 1 s 2 s 3 - - - мон? кн? шок! Этот процесс задает поведение автомата, который обслужи- вает ровно одного покупателя, и после этого ломается. 3.3 Альтернативная композиция Следующая операция на процессах - это бинарная операция аль- тернативной композиции. Данная операция используется в том случае, когда по паре процессов P 1 и P 2 , надо построить процесс P , который будет функционировать • либо как процесс P 1 , • либо как процесс P 2 , причём выбор процесса, в соответствии с которым P будет функ- ционировать, может определяться • как самим P , • так и окружающей средой, в которой функционирует P . 29 Например, если P 1 и P 2 имеют вид P 1 = α? . P 0 1 P 2 = β? . P 0 2 (3.1) и в начальный момент времени окружающая среда • может ввести в P объект α, но • не может ввести в P объект β то P должен выбрать то поведение, которое является единствен- но возможным в данной ситуации, т.е. работать так же, как про- цесс P 1 Отметим, что в данном случае выбирается такой процесс, пер- вое действие в котором может быть выполнено в текущий момент времени. Выбрав P 1 , и выполнив действие α?, процесс P обязан продолжать работу в соответствии со своим выбором, т.е. в соот- ветствии с процессом P 0 1 |