Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой

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

Full description

Saved in:

Bibliographic Details
Date:	2007
Main Authors:	Нестеренко, Б.Б., Новотарский, М.А.
Format:	Article
Language:	Russian
Published:	Інститут проблем реєстрації інформації НАН України 2007
Series:	Реєстрація, зберігання і обробка даних
Subjects:	Математичні методи обробки даних
Online Access:	http://dspace.nbuv.gov.ua/handle/123456789/50907
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой / Б.Б. Нестеренко, М.А. Новотарский // Реєстрація, зберігання і оброб. даних. — 2007. — Т. 9, № 4. — С. 49-59. — Бібліогр.: 12 назв. — pос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50907
record_format	dspace
spelling	irk-123456789-509072013-11-06T18:07:58Z Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой Нестеренко, Б.Б. Новотарский, М.А. Математичні методи обробки даних Приведен краткий обзор современных средств для описания моделей сложных систем. Показано, что для повышения адекватности моделей актуальна задача развития новых низкоуровневых формальных средств описания объектов — алгебр процессов. Коротко описаны основы известных алгебр процессов и предложена алгебра процессов, ориентированная на имитационное моделирование сложных систем с реальной рабочей нагрузкой. Рассмотрены вопросы определения эквивалентности системы и модели. Приведен пример описания однородной вычислительной среды в терминах алгебры процессов. Наведено короткий огляд сучасних засобів для опису моделей складних систем. Показано, що для підвищення адекватності моделей актуальним є розвиток нових низькорівневих формальних засобів опису об’єктів — алгебр процесів. Коротко описано основи відомих алгебр процесів і запропоновано алгебру процесів, яка орієнтована на імітаційне моделювання складних систем з реальним робочим навантаженням. Розглянуто питання визначення еквівалентності системи й моделі. Наведено приклад опису однорідного обчислювального середовища в термінах алгебри процесів. A brief review of modern means for the description of complex systems models is given. It is shown that for increase of adequacy of models the problem of development of new low-level formal means for the objects’ description (process algebras) is actual. Basic concepts of known process algebras are shortly described and the process algebra that is focused on simulation of complex systems with real working loading is offered. Questions of definition of equivalence of a system and a model are considered. An example of the description of the homogeneous computing environment in terms of process algebra is given. 2007 Article Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой / Б.Б. Нестеренко, М.А. Новотарский // Реєстрація, зберігання і оброб. даних. — 2007. — Т. 9, № 4. — С. 49-59. — Бібліогр.: 12 назв. — pос. 1560-9189 http://dspace.nbuv.gov.ua/handle/123456789/50907 519.876.5 ru Реєстрація, зберігання і обробка даних Інститут проблем реєстрації інформації НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Математичні методи обробки даних Математичні методи обробки даних
spellingShingle	Математичні методи обробки даних Математичні методи обробки даних Нестеренко, Б.Б. Новотарский, М.А. Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой Реєстрація, зберігання і обробка даних
description	Приведен краткий обзор современных средств для описания моделей сложных систем. Показано, что для повышения адекватности моделей актуальна задача развития новых низкоуровневых формальных средств описания объектов — алгебр процессов. Коротко описаны основы известных алгебр процессов и предложена алгебра процессов, ориентированная на имитационное моделирование сложных систем с реальной рабочей нагрузкой. Рассмотрены вопросы определения эквивалентности системы и модели. Приведен пример описания однородной вычислительной среды в терминах алгебры процессов.
format	Article
author	Нестеренко, Б.Б. Новотарский, М.А.
author_facet	Нестеренко, Б.Б. Новотарский, М.А.
author_sort	Нестеренко, Б.Б.
title	Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой
title_short	Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой
title_full	Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой
title_fullStr	Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой
title_full_unstemmed	Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой
title_sort	алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой
publisher	Інститут проблем реєстрації інформації НАН України
publishDate	2007
topic_facet	Математичні методи обробки даних
url	http://dspace.nbuv.gov.ua/handle/123456789/50907
citation_txt	Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой / Б.Б. Нестеренко, М.А. Новотарский // Реєстрація, зберігання і оброб. даних. — 2007. — Т. 9, № 4. — С. 49-59. — Бібліогр.: 12 назв. — pос.
series	Реєстрація, зберігання і обробка даних
work_keys_str_mv	AT nesterenkobb algebraprocessovdlâmodelirovaniâsložnyhsistemsrealʹnojrabočejnagruzkoj AT novotarskijma algebraprocessovdlâmodelirovaniâsložnyhsistemsrealʹnojrabočejnagruzkoj
first_indexed	2025-07-04T12:46:57Z
last_indexed	2025-07-04T12:46:57Z
_version_	1836720553738633216
fulltext	ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 4 49 УДК 519.876.5 Б. Б. Нестеренко, М. А. Новотарский Институт математики НАН Украины ул. Терещенковская, 3, 01601 Киев-4, ГСП, Украина тел. (044) 234-04-07, e-mail: model@imath.kiev.ua, novot@ukr.net Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой Приведен краткий обзор современных средств для описания моделей сложных систем. Показано, что для повышения адекватности моде- лей актуальна задача развития новых низкоуровневых формальных средств описания объектов — алгебр процессов. Коротко описаны ос- новы известных алгебр процессов и предложена алгебра процессов, ориентированная на имитационное моделирование сложных систем с реальной рабочей нагрузкой. Рассмотрены вопросы определения экви- валентности системы и модели. Приведен пример описания однород- ной вычислительной среды в терминах алгебры процессов. Ключевые слова: алгебра процессов, процесс, активность, поведенче- ская эквивалентность, строгое взаимное подобие. Введение Одним из самых мощных и эффективных средств исследования сложных дискретных систем является компьютерное моделирование. Особую актуальность оно приобретает в том случае, когда необходимо проводить исследование дис- кретных систем, натурные эксперименты с которыми нецелесообразны из сооб- ражений безопасности или дороговизны. К настоящему времени накоплен огром- ный опыт создания компьютерных моделей, различающихся природой формаль- ного описания объекта исследования. Среди прочих широкое распространение получил объектно-ориентированный подход к построению моделей. Известным представителем средств объектно-ориентированного моделирования является язык Modelica [1], созданный для описания сложных систем, содержащих меха- нические, гидравлические, электрические, электронные и другие компоненты. Язык обеспечивает поддержку классов и экземпляров блоков, а также наследова- ние и полиморфизм блоков. Класс определяет некоторый шаблон или прототип блока. Оперируя классом, нельзя говорить о конкретных значениях переменных, так как в определении класса присутствует только информация об их типах и именах. Экземпляр блока — это конкретный представитель класса блоков, вклю- © Б. Б. Нестеренко, М. А. Новотарский mailto:novotar@yandex.ru Б. Б. Нестеренко, М. А. Новотарский 50 чающий свои собственные значения переменных. В функциональную схему могут входить несколько статических или динамических экземпляров одного и того же класса. Статические экземпляры создаются при создании модели и уничтожаются при ее уничтожении, а динамические могут создаваться и уничтожаться в ходе моделирования. Механизм наследования позволяет создавать новые классы путем использования уже имеющихся в качестве предков, а полиморфизм означает воз- можность использования вместо экземпляра блока некоторого базового класса экземпляра любого его производного класса. Следует отметить, что упомянутый принцип объектно-ориентированного мо- делирования больше отражает внутреннюю организацию модели. В то же время чрезвычайно важно обеспечить комфортные условия взаимодействия с ней поль- зователей. В связи с этим большой стимул к развитию получил визуальный под- ход, разрабатываемый с целью упрощения технологии создания моделей. Визуа- лизация чаще всего происходит за счет применения технологии «блочного моде- лирования», использующей графический язык иерархических блок-схем. Функ- ции элементарных блоков могут быть предопределенными или описываться с по- мощью языка более низкого уровня. Подход «блочного моделирования» исполь- зован, например, в пакетах SIMULINK (MATLAB) [2], VisSim [3] и др. Современные средства моделирования стремятся сочетать в себе объектно- ориентированный и визуальный подходы. Примером удачной реализации являет- ся унифицированный язык моделирования (UML) [4]. Первоначально разработан- ный для определения, визуализации, проектирования и документирования про- граммных систем, сейчас UML используется также при моделировании бизнес- процессов, в системном проектировании и отображении организационных струк- тур. Использование упомянутых подходов чаще всего оправдано в том случае, ко- гда речь идет об анализе качественных параметров объектов исследования. В слу- чае необходимости получения точных характеристик сложной системы возникает проблема обоснования адекватности модели. Избыточный характер визуального описания и неточная семантика зачастую становятся непреодолимыми препятст- виями для решения этой задачи. Решение проблемы лежит в сфере использования низкоуровневых средств формального описания. Долгое время фаворитом низко- уровневых средств являлись сети Петри [5] и их модификации [6]. Однако гро- моздкость сетевого формального представления стала существенным препятстви- ем при описании сложных систем. Современные низкоуровневые средства, наря- ду с компактностью представления модели, должны обеспечивать хорошо форма- лизованный механизм установления ее адекватности. Именно таким требованиям соответствуют алгебры процессов. Основы описания алгебры процессов Алгебра процессов ― это инструмент формального описания, который моде- лирует параллельные системы посредством их алгебры и обеспечивает аппарат анализа структуры и поведения модели. Основополагающими разработками в данной области принято считать такие алгебры процессов: Calculus of Communi- cating Systems (CCS) [7], Communicating Sequential Processes (CSP) [8], Algebra of http://ru.wikipedia.org/wiki/%D0%9C%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%B1%D0%B8%D0%B7%D0%BD%D0%B5%D1%81-%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D1%81%D1%81%D0%BE%D0%B2 http://ru.wikipedia.org/wiki/%D0%9C%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%B1%D0%B8%D0%B7%D0%BD%D0%B5%D1%81-%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D1%81%D1%81%D0%BE%D0%B2 http://ru.wikipedia.org/w/index.php?title=%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5&action=edit http://ru.wikipedia.org/w/index.php?title=%D0%9E%D1%80%D0%B3%D0%B0%D0%BD%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0&action=edit http://ru.wikipedia.org/w/index.php?title=%D0%9E%D1%80%D0%B3%D0%B0%D0%BD%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0&action=edit Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 4 51 Communicating Processes (ACP) [9] и Performance Evaluation Process Algebra [10]. Все упомянутые алгебры включают описание активных компонент и механизмы взаимодействия между ними. В большинстве случаев активные компоненты пред- ставлены процессами или агентами, состоящими из активностей, каждая из ко- торых задает определенные дискретные действия системы. Любая активность может быть внутренней по отношению к процессу, или задавать взаимодействие между процессами. Такое взаимодействие носит бинарный характер. Поэтому ка- ждая активность DÎa всегда имеет сопряженную активность DÎa , и это имен- но та сопряженная активность, с которой готова синхронизироваться активность a . В алгебре процессов можно скрыть поведение фрагмента процесса, предста- вив его как черный ящик. При этом возникает возможность построить сложную имитационную модель, исключив более простые части, поведение которых не представляет интереса при исследовании. Невидимое поведение моделируют с помощью специальной активности s , представляющей внутренние действия про- цесса. Таким образом, полный алфавит активностей { }sÈL=Act включает ак- тивности взаимодействия DÈD=L и множество { }s внутренних активностей. Простейший константный процесс не может выполнять ни одной активности и приводит к освобождению всех ресурсов посредством выполнения активности nil . Если процесс включает более одной активности, последовательность их свершения регулируется префиксной записью P.a , смысл которой состоит в том, что она представляет процесс, сначала выполняющий активность a , а затем функционирующий, как Р. Примером элементарного процесса 1Р может служить выражение: nilendbeginP ..:1 = . Символ =: означает присвоение выражения в правой части процессу 1Р . Действия процесса согласно данному выражению состоят из прямой после- довательности трех активностей. Активность begin выполняет действия, связан- ные с началом функционирования процесса 1Р , end завершает процесс 1Р , nil освобождает ресурсы и удаляет процесс 1Р из модели. Для моделирования систем с параллельным функционированием компонен- тов синтаксис алгебры дополняют операциями выбора. Операция P + Q представ- ляет процесс, который ждет готовности процессов P или Q принять участие в не- которой активности. После этого происходит недетерминированный выбор между ними. Применив префиксную запись, приведем пример процесса 4P , использую- щего данную операцию: 22114 ..: PbeginPbeginP += . Процесс 4P предполагает выбор между двумя альтернативами. Этот выбор кон- тролируется начальными активностями составляющих его процессов и не зависит от внешнего воздействия. Б. Б. Нестеренко, М. А. Новотарский 52 Для того чтобы конструировать сложные процессы, необходимо также уметь параллельно запускать несколько подпроцессов, обеспечивая механизмы взаимо- действия и синхронизации. С этой целью используют параллельную конструкцию QP , которая представляет два процесса, развивающихся параллельно. Процес- сам P и Q позволено любое индивидуальное поведение, однако при наличии в них сопряженных активностей выполняется синхронизация путем одновременного свершения активностей. К общепринятым операциям, используемым в различных алгебрах процессов, относят переименование [ ]KP и сжатие AP \ . Процесс [ ]KP ведет себя как Р, но во всех своих активностях переименовывается функцией K. Процесс AP \ ведет себя как Р, но не позволяет выполнять никаких активностей из А. Рассмотренное неформальное описание основных синтаксических операций, характерных для различных алгебр процессов, дает общее представление об этом инструменте формализации. Высокая эффективность данного подхода стимули- рует разработчиков применять алгебры процессов к самым различным моделям. На сегодняшний день хорошо разработаны подходы к использованию алгебры процессов для построения стохастических моделей параллельных структур [10] и для имитационных моделей с синтетическими рабочими нагрузками, базирующи- мися на вероятностном распределении параметров входных заданий [11]. Однако такие подходы требуют предварительных знаний о системе и ее рабочей нагрузке для получения адекватных результатов моделирования. При использовании моде- лей на этапе разработки сложной системы такие знания, как правило, отсутству- ют. Поэтому представляет значительный интерес создание алгебры процессов для имитационного моделирования систем с реальной рабочей нагрузкой. Алгебра процессов для описания моделей сложных систем с реальной нагрузкой Кроме рассмотренных особенностей рассматриваемая в данной работе версия алгебры процессов отличается применением в ней технологии «блочного модели- рования». Новизна этого подхода состоит в том, что алгебраическая модель имеет двухуровневый характер. На верхнем уровне с помощью выражений алгебры процессов формируется структура модели и определяется характер взаимодейст- вия между компонентами. Нижний уровень содержит алгоритмы, описывающие процесс обработки реальной рабочей нагрузки отдельными компонентами. Такой подход позволяет достичь высокой адекватности модели при реализации кон- кретных вычислительных алгоритмов. Для его успешной реализации полный ал- фавит активностей FÈL=Act включает активности взаимодействия { } LÍ = n jj 1 l и множество внутренних активностей { } FÍ = m ii 1 j . Активности взаимодействия моделируют обмен информацией между компонентами сложной системы, а внут- ренние активности определяют алгоритмы функционирования этих компонент на заданном уровне абстрагирования. Синтаксис алгебры процессов для имитационного моделирования сложных систем с реальной рабочей нагрузкой основан на использовании двух типов пере- менных: Pvar и Var. Переменные типа Pvar предназначены для описания значе- Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 4 53 ний параметров процессов системы, а переменные типа Var задают значения па- раметров рабочей нагрузки. Pvar — множество переменных для временного хра- нения и обработки экземпляров процессов, включающее такие переменные про- цессов: [ ] nilXXX keyi ,,, . Формальное описание алгебры процессов допускает наличие конечного мно- жества переменных, значения которых определяются при помощи операции PX: = . Данная операция присваивает тривиальной переменной Х поведение про- цесса Р. Переменные сложного типа могут отображать индексные и списковые структуры. Индексная переменная процесса имеет вид [ ]iX , где IiÎ — значение индекса. Списковая переменная keyX всегда содержит ссылку key , указывающую на следующий элемент. Последний элемент списка имеет ссылку nil . Выражения для процессов объединены во множество Pexp , а выражения для рабочей нагрузки составляют множество выражений Ехр. Рехр — множество, ко- торое включает такие выражения: ( )( ) ;.,.,.,. PtysPtsPtP ¬¬a Ii PPP ++++ LL1 , IIii PvPvPv !!! 11 ++++ LL , IIii PwPwPw ### 11 ++++ LL ; CQP L , CQP L> , CQP L« , CQP L<> ; ;\; APKP { } ( )CPCPk Pj,,´ ; ( ) [ ]( ),, PXxcyclePX ==Â где ActExpyVarxwstPexpQPPvarX ÎÎÎÎÎ a,,,,,,,, ; І — конечное множе- ство индексов; K — функция переименования ,: ActActK ® LÌA — подмно- жество активностей взаимодействия. Переменные типа Var соответствуют простым и структурированным типам переменных, описываемым в алгоритмических языках программирования. Поэто- му правила для выражений Exp напоминают правила составления выражений в упомянутых языках. Операции префиксации ( )( ) PtysPtsPtP .,.,.,. ¬¬a образуют базо- вый механизм конструирования поведения процесса. Тривиальная префиксация P.a представляет процесс, поведение которого соответствует описанному ранее. Префиксная задержка Pt . — это операция, которая задает процесс с начальной задержкой на t единиц модельного времени, а параметрическая префиксная за- Б. Б. Нестеренко, М. А. Новотарский 54 держка Pts .¬ описывает действия процесса, для которого предварительно ус- танавливается значение временного параметра s путем присвоения ему значения t . Функциональная префиксация ( )( )Ptys .¬ определяет действия процесса, за- держанного на величину s , принадлежащую области значений функции у. Осуществление префиксаций P.a и Pt . не зависит от состояния внешней среды и определяется исключительно внутренними параметрами процесса. По- этому их используют для описания независимых процессов. Префиксации Pts .¬ и ( )( )Ptys .¬ отображают характер взаимодействия процессов с внеш- ней средой. Такое взаимодействие может быть выражено в виде параметрической синхронизации. Синхронизацию по времени задают путем параметрической за- мены величины задержки начала развития процесса Р в одном из параллельных процессов. При функциональной задержке развитие процесса Р начинается только при условии срабатывания ключевой функции y . Операции выбора Ii PPP ++++ LL1 , IIii PvPvPv !!! 11 ++++ LL , IIii PwPwPw ### 11 ++++ LL предназначены для определения одного процесса из множества процессов с целью его дальнейшего развития. Недетерминирован- ный выбор обеспечивает определение одного из процессов Ii PPP ++++ ......1 в момент времени, который называется моментом выбора. Управляемый выбор IIii PvPvPv !!! 11 ++++ LL осуществляет выбор того процесса iP , для которого соответствующая логическая переменная iv принимает истинное значение. Вероятностный выбор IIii PwPwPw ### 11 ++++ LL производит выбор процесса iP с вероятностью iw при условии 1......1 =++++ Ii www . Множество активностей процесса выбора формируется путем объединения множеств составных процессов: ( ) ( ) ( )Ii Ii i PActPActPActPAct ÈÈÈÈ=÷ ø ö ç è æå Î ......: 1 . Условие выполнения активности ÷÷ ø ö çç è æ åÎ ÎIi iPActa требует принадлежности данной активности к множеству активностей одного из процессов ( ) IkPAct k ÎÎ ,a . Суть операции выбора состоит в отображении конкуренции элементов системы за владение скрытым ресурсом. Поэтому в случае наличия одинаковых активностей во множествах разных процессов срабатывает только та активность, которая первой получила доступ к скрытому ресурсу. Операции параллельной композиции и взаимодействия CQP L , CQP L> , CQP L« , CQP L<> определяют взаимное поведение парал- лельно развивающихся процессов. Операция параллельной композиции Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 4 55 CQP L показывает, что упомянутые процессы в ходе своего развития либо не взаимодействуют вообще, либо характер их взаимодействия не влияет на резуль- таты моделирования. Операция управляемой передачи CQP L> определяет процедуру передачи информации от процесса Р к параллельной композиции CQ L в момент свершения активности вывода в процессе Р. Операции синхрон- ного взаимодействия CQP L« и асинхронного взаимодействия CQP L<> формируют процедуры обмена информацией, отличающиеся тем, что для син- хронного обмена необходимо одновременное выполнение комплементарных ак- тивностей передачи и приема, а для асинхронного обмена не требуется ожидать момента возникновения комплементарных активностей. Операции переименования и сжатия APKP \, относят к операциям группового редактирования, поскольку они обеспечивают модификацию группы активностей процесса одновременно. Операцией переименования KP называют систему, представленную процессом P, все активности которого переименовыва- ются с помощью функции K. Операция сжатия AP \ представлена системой, со- стоящей из процесса P и множества активностей A, в которой заблокированы все активности, принадлежащие множеству сжатия A. Главным назначением данных операций является модификация поведения группы объектов модели в ходе моде- лирования. Например, с помощью операции сжатия можно управлять синхрони- зацией обмена между процессом P и параллельной композицией CQ L путем блокирования комплементарных активностей взаимодействия. Операции клонирования, включения и сокрытия введены для придания описаниям моделей иерархических свойств. Операция клонирования Pk ´ поро- ждает k идентичных процессов P. Операция включения { }PC задает конструк- цию из процессов C и P, включающую процесс P в качестве субпроцесса процес- са С. Операция сокрытия ( )CPj позволяет скрывать выполнение субпроцесса P, входящего в главный процесс C , путем замены его некоторой вычислительной активностью j . Операции рекурсии и цикла ( ) ( )PXxcyclePX ==Â , предназначены для многократного повторения некоторой последовательности активностей, входящих в процесс P. Операцией рекурсии ( )PX =Â называют систему, состоящую из ре- курсивно повторяемой последовательности активностей процесса P, присвоенных переменной типа Pvar. Операцией цикла ( )PXxcycle = называют систему, ко- торая состоит из циклически повторяемой x раз последовательности активностей процесса P, присвоенного переменной типа Pvar. Операция рекурсии может зада- вать бесконечную или конечную последовательность процессов. Конечная после- довательность возникает в том случае, когда в ходе выполнения очередного эк- земпляра процесса исполняется условие завершения рекурсии, которое всегда оп- ределяется внутренним состоянием процесса. Операция цикла отличается от опе- рации рекурсии наличием переменной x , значение которой ограничивает количе- ство повторений выполнения процесса P. Б. Б. Нестеренко, М. А. Новотарский 56 Описание системы с помощью рассмотренных операций алгебры процессов задает только верхний уровень модели. Для исчерпывающего ее описания необ- ходимо функционально определить элементы множества активностей Act , представив модель в виде маркированной системы с переходами: { }( )ActSAct Î¾®¾P aa,,, , где ï þ ï ý ü ï î ï í ì =P 4,41,4 , 4,11,1 PP P PP ji L LL L — множество процессов; ¾®¾a — множество переходов, формируемых внутренними активностями и ак- тивностями взаимодействия при { } P´´PÍ¾®¾ Acta ; S — множество состоя- ний системы. Такое представление дает возможность воспользоваться подходами общей теории систем для строгого обоснования эквивалентности модели ее специфика- ции в случае моделирования с целью разработки. Вопросы эквивалентности Основой определения адекватности является поведенческая эквивалентность, которая с помощью анализа состояний системы позволяет сформулировать усло- вия эквивалентного поведения процессов [12]. Под состоянием системы в данном случае понимают совокупность значений параметров, установленных в результате свершения активности. Для практического определения эквивалентности используют взаимное подо- бие, основывающееся на отношении эквивалентности. Пусть P — процесс, а бинарное отношение R на P представляет собой мно- жество PP´ с состояниями ( ) Rqp Î, или pRq. Тогда эквивалентным отношени- ем R на P будем называть бинарное отношение, отвечающее таким условиям: — R должно быть рефлексивным, т.е. qRqpRp, при Pqp Î, ; — R должно быть симметричным, т.е. из pRq следует qRp при Pqp Î, ; — R должно быть транзитивным, т.е. из pRq и qRz следует pRz при Pzqp Î,, . Рефлексивность бинарного отношения обеспечивает внутреннюю непротиво- речивость процессов, эквивалентно отображающих внутренне непротиворечивые процессы. Транзитивность позволяет сохранять эквивалентность во время поша- говой реализации модели в соответствии с ее описанием. Для того, чтобы объект моделирования и его описание были взаимно подобными, очевидна также необ- ходимость выполнения принципа симметричности. Для выполнения строгого взаимного подобия необходимо, чтобы активности системы соответствовали активностям модели, и состояния, достигаемые после выполнения каждой из активностей, были одинаковыми. Пусть существует отношение P´PÍR и процессы PÍQP, с допустимы- ми состояниями Ppp Î¢, , Qqq Î¢, при ( ) Rqp Î, . Тогда, если: — для каждого перехода pp ¢¾®¾a существует состояние q′ такое, что Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 4 57 qq ¢¾®¾a при ( ) Rqp Î¢¢, , — для каждого перехода qq ¢¾®¾a существует состояние p′ такое, что pp ¢¾®¾a при ( ) Rqp Î¢¢, , то отношение R будем называть строгим взаимным подобием, а состояния p и q будем называть строго взаимно подобными qp ~ . В случае, когда все состояния системы и модели строго взаимно подобны, то такая модель эквивалентна исследуемой системе. Пример описания однородной вычислительной среды Рассмотрим, например, описание структуры однородной вычислительной сре- ды (см. рис.), состоящей из узлов, описываемых процессами алгебры процессов. Произвольный узловой процесс jiP , включает подпроцессы 41 ,, QQ L , моде- лирующие работу основных элементов узла в соответствии с выражением алгеб- ры процессов: ( ){ }66554433221, !!!!! QvQvQvQvQvQP ji ++++« . (1) Выражение (1) показывает, что в произвольный момент времени процесс 1Q может синхронно взаимодействовать с тем процессом, который будет выбран в результате выполнения операции управляемого выбора ( )6655443322 !!!!! QvQvQvQvQv ++++ . Работа узла сводится к многократному повторению процесса jiP , , задаваемо- му оператором рекурсии: ( )jiPX ,=Â . (2) Структура однородной вычислительной среды Б. Б. Нестеренко, М. А. Новотарский 58 Определив взаимодействие между узлами как асинхронное, получим выра- жение алгебры процессов для внешнего взаимодействия узла jiP , : ( )1,1,,1,1, +-+- jijijijiji PPPPP <> . (3) Для получения описания однородной вычислительной среды объединим вы- ражения (1), (2) и (3): ( ){ }( ) ( )1,1,,1,166554433221, !!!!! +-+-++++«Â jijijijiji PPPPQvQvQvQvQvQP <> , (4) где 4,,1;4,,1 LL == ji . Выражение (4) определяет все возможные варианты развития процессов как на уровне взаимодействия между узлами, так и на уровне подпроцессов узла. Од- нако для решения вопросов эквивалентности модели необходимо активностям, формирующим данные процессы, поставить в соответствие алгоритмы обработки реальной рабочей нагрузки. Выводы Современные средства моделирования широко используют объектно-ориен- тированный подход, который в сочетании с визуальным представлением инфор- мации позволяет существенно сократить время построения модели сложной сис- темы. Однако избыточный характер визуального описания и неточная семантика зачастую становятся непреодолимыми препятствиями для построения таких мо- делей, эквивалентность которых объекту моделирования должна быть строго обоснованной. Решение проблемы лежит в сфере использования низкоуровневых средств формального описания, позволяющих применять принципы определения эквивалентности, используемые в общей теории систем. Одним из современных и бурно развивающихся низкоуровневых средств такого типа являются алгебры процессов, основанные на событиях или активностях, объединяемых в процессы, которые описывают работу компонентов сложных систем. Интерпретация актив- ностей и характер взаимодействия в рамках отдельной алгебры процессов полно- стью определяются ее алфавитом и совокупностью допустимых операций. Пред- ложенная в рамках этой работы версия алгебры процессов ориентирована на ими- тационное моделирование сложных систем с реальной рабочей нагрузкой. Поэто- му она содержит алфавит, состоящий из двух множеств активностей, объединяю- щих активности взаимодействия и внутренние активности. Расширенный набор операций позволяет строить иерархические модели с различными видами взаимо- действия между компонентами. Определение активностей за счет применения технологии «блочного моделирования» дает возможность обработки моделью ре- альной рабочей нагрузки. Решение вопросов эквивалентности сводится к установлению эквивалентного отношения между состояниями системы и модели. Строгое взаимное подобие на- Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 4 59 ступает при условии, что активности системы соответствуют активностям модели, и состояния, достигаемые после выполнения каждой из активностей, одинаковы. 1. Fritzson P. Principles of Object-Oriented Modeling and Simulation with Modelica 2.1. — San Francisco: Wiley-IEEE Press, 2004. — 944 p. 2. Karris T.S. Introduction to Simulink with Engineering Applications. — Fremont: Orchard Publi- cations, 2006. — 584 p. 3. Дьяконов В. VisSim+MathCad+MATLAB. Визуальное математическое моделирование. — М.: Солон-Пресс, 2004. — 384 с. 4. Буч Г., Якобсон А. UML. Классика CS. — С.Петербург: Из-во «Питер», 2006. — 736 с. 5. Питерсон Дж. Теория сетей Петри и моделирование систем. — М.: Мир, 1984. — 264 с. 6. Нестеренко Б.Б., Новотарский М.А. Мультипроцессорные системы. — К.: Институт ма- тематики АН Украины, 1995. — 408 с. 7. Milner R. Communication and Concurrency. — London: Prentice-Hall, 1989. — 260 p. 8. Хоар Ч. Взаимодействующие последовательные процессы. — М.: Мир, 1989. — 264 с. 9. Bergstra J.A., Klop J.W. Algebra for Communicating Processes with Abstraction // J. of Theoret- ical Computer Science. — 1985. — Vol. 37. — P. 77–121. 10. Hilston J. A Compositional Approach to Performance Modelling. — Cambridge University Press. —1996. — 168 p. 11. Glynn P.W. A GSMP Formalism for Discrete Event Simulation // Proc. of the IEEE. — 1989. — Vol. 77, N 1. — P. 14–23. 12. Main M. Trace, Failure and Testing Equivalences for Communicating Processes // International Journal of Parallel Programming. — 1987. — Vol.16, N 5. — P. 383–400. Поступила в редакцию 17.10.2007

Алгебра процессов для моделирования сложных систем с реальной рабочей нагрузкой

Institution

Similar Items