О временном представлении теории взаимодействующих процессов Хоара
В статье вводится параметр времени в теорию взаимодействующих процессов Хоара. Представлены основные операции теории, такие как префиксация, рекурсия, операторы выбора и др. и аксиоматические законы теории с учетом введенного параметра....
Збережено в:
| Дата: | 2011 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2011
|
| Назва видання: | Математичні машини і системи |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/83600 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О временном представлении теории взаимодействующих процессов Хоара / Е.Н. Гайтан // Мат. машини і системи. — 2011. — № 3. — С. 130-134. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-83600 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-836002015-06-21T03:02:47Z О временном представлении теории взаимодействующих процессов Хоара Гайтан, Е.Н. Моделювання і управління великими системами В статье вводится параметр времени в теорию взаимодействующих процессов Хоара. Представлены основные операции теории, такие как префиксация, рекурсия, операторы выбора и др. и аксиоматические законы теории с учетом введенного параметра. У статті вводиться параметр часу до теорії взаємодіючих процесів Хоара. Представлені основні операції теорії, такі як префіксація, рекурсія, оператори вибору та ін. та аксіоматичні закони теорії з урахуванням введеного параметра. The article studies addition of the time parameter to the theory of communicating processes of Hoare. The basic operations of theory, such as prefix, recursion, selection operator and other, and axiomatic laws of theory are rewritten taking into account the entered parameter. 2011 Article О временном представлении теории взаимодействующих процессов Хоара / Е.Н. Гайтан // Мат. машини і системи. — 2011. — № 3. — С. 130-134. — Бібліогр.: 6 назв. — рос. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/83600 004.82 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 |
2011 |
| topic_facet |
Моделювання і управління великими системами |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/83600 |
| citation_txt |
О временном представлении теории взаимодействующих процессов Хоара / Е.Н. Гайтан // Мат. машини і системи. — 2011. — № 3. — С. 130-134. — Бібліогр.: 6 назв. — рос. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT gajtanen ovremennompredstavleniiteoriivzaimodejstvuûŝihprocessovhoara |
| first_indexed |
2025-07-06T10:25:03Z |
| last_indexed |
2025-07-06T10:25:03Z |
| _version_ |
1836892819165282304 |
| fulltext |
130 © Гайтан Е.Н., 2011
ISSN 1028-9763. Математичні машини і системи, 2011, № 3
УДК 004.82
Е.Н. ГАЙТАН
О ВРЕМЕННОМ ПРЕДСТАВЛЕНИИ ТЕОРИИ ВЗАИМОДЕЙСТВУЮЩИХ
ПРОЦЕССОВ ХОАРА
Анотація. У статті вводиться параметр часу до теорії взаємодіючих процесів Хоара. Представ-
лені основні операції теорії, такі як префіксація, рекурсія, оператори вибору та ін. та аксіома-
тичні закони теорії з урахуванням введеного параметра.
Ключові слова: теорія взаємодіючих процесів, подія, процес, протокол, префіксація, рекурсія, опе-
ратор вибору, функція перейменування.
Аннотация. В статье вводится параметр времени в теорию взаимодействующих процессов Хоа-
ра. Представлены основные операции теории, такие как префиксация, рекурсия, операторы выбо-
ра и др. и аксиоматические законы теории с учетом введенного параметра.
Ключевые слова: теория взаимодействующих процессов, событие, процесс, протокол, префикса-
ция, рекурсия, оператор выбора, функция переименования.
Abstract. The article studies addition of the time parameter to the theory of communicating processes of
Hoare. The basic operations of theory, such as prefix, recursion, selection operator and other, and axi-
omatic laws of theory are rewritten taking into account the entered parameter.
Keywords: theory of communicating processes, event, process, protocol, prefix, recursion, selection oper-
ator, renaming function.
1. Введение
Последние десятилетия прошлого века охарактеризовались бурным развитием информа-
ционных технологий. Начиная с 70-х годов ХХ века, существенно расширился спектр за-
дач, эффективно решаемых с использованием информационных технологий, что способст-
вовало их широкому внедрению в различные виды деятельности и проявлению повышен-
ного интереса к проектированию программных средств со стороны исследователей [1].
В информатике для описания взаимодействия в программных системах значитель-
ное развитие получило семейство формальных языков, или математических теорий парал-
лелизма, известных как алгебра процессов или алгебра исчислений.
В настоящее время существует достаточное количество форм методов параллелиз-
ма, наиболее известные из которых:
1. CSP (Communicating sequential processes) [2] – теория взаимодействующих после-
довательных процессов, предложенная известным теоретиком информатики Ч. Хоаром
(Великобритания). Согласно Хоару, взаимодействие между процессами происходит при
помощи сообщений.
2. CCS (Calculus of communicating systems) [3, 4] – теория взаимодействующих про-
цессов, разработанная Р. Милнером. В основу взаимодействия процессов положен меха-
низм рандеву, при котором взаимодействие между процессами происходит мгновенно.
3. ACS (Algebra of communicating systems) [5] – алгебра взаимодействующих про-
цессов, предложенная Бегстра и Клопом.
В данной работе будет использоваться CSР. Алгебра Хоара представляет собой хо-
рошую нотацию с математической теорией. Хоар формализовал понятие процесса и ввел
его описание при помощи протоколов, а также предложил ряд аксиом, описывающих
взаимодействие процессов.
Однако недостатком данной теории является абстрагирование от понятия времени.
Хоар считает, что:
– события происходят мгновенно, т.е. являются элементарным действием, не
ISSN 1028-9763. Математичні машини і системи, 2011, № 3 131
имеющим протяженности во времени. Протяженное, т.е. требующее времени, действие
рассматривается как пара событий, первое из которых отмечает начало действия, а второе
– его завершение;
– события и процессы не привязываются точно ко времени. Преимуществом такого
подхода, по мнению Хоара, является упрощение построений и рассуждений, их примени-
мость к физическим и вычислительным системам любой скорости и производительности.
Однако следствием исключения времени является отказ от понятия одновременно-
сти, причинно-временных зависимостей. Когда совместность событий существенна (на-
пример, при синхронизации процессов), единственный способ учесть данное обстоятель-
ство – свести эти события в одно или позволить совместным событиям происходить в лю-
бом относительно друг друга порядке. Кроме того, абстрагирование от времени приводит к
невозможности численной оценки длительности процесса.
Цель данной работы – введение времени в теорию взаимодействующих последова-
тельных процессов Ч. Хоара для устранения описанных недостатков.
2. Основы CSP (Communicating sequential processes)
CSP описывает поведение системы как алгебраическую модель процессов, в которых
сложные формы поведения составлены из более простых с помощью небольшого набора
операторов. Эти операторы включают:
– префиксную запись, которая описывает последовательное выполнение операций:
пусть x – событие, а P – процесс. Тогда ( )Px → описывает объект, который вначале
участвует в событии x , а затем ведет себя как P . Заметим, что операция префиксации ас-
социативна справа, а это означает, что ( )x y P x y P→ → = → → ;
– механизм рекурсии для описания многократно или бесконечно повторяемого про-
цесса: процесс ( )P x P= → , записанный с помощью рекурсии, выполняет один раз собы-
тие x , а затем ведет себя как процесс P .
Префиксная запись и рекурсия задают линейную модель поведения. Она аналогична
программе, содержащей линейную последовательность операторов и не имеющей опера-
торов цикла или ветвления;
– альтернатива в поведении объекта представляется с помощью нескольких опера-
торов выбора. CSP обеспечивает две основные формы выбора: внутренний выбор, выпол-
няемый самим объектом или управляющим им процессом, и внешний выбор, когда реше-
ние принимается средой (информация поступает извне от объектов, не являющихся эле-
ментами данной системы).
В случае детерминированного выбора окружение процесса либо само осуществляет
выбор, либо может наблюдать его. Если x и y – различные события, то оператор выбора
( )x P y Q→ → описывает объект, который сначала участвует в одном из событий x , y , а
затем описывается процессом P , если первым произошло событие x , или Q , если пер-
вым произошло событие y . Таким образом, наступление события x или y определяется
внешним фактором, но далее выбор между процессами P и Q строго детерминируется.
При недетерминированном процессе ни процесс, ни его окружение не могут ни вы-
бирать, ни наблюдать его действие. В таком случае выбор между процессами P и Q осу-
ществляется произвольно. Использование недетерминированного выбора ( )P QΠ позволя-
ет учитывать стохастическое влияние внешних по отношению к объекту факторов возму-
щающих воздействий со стороны других объектов, взаимодействующих с моделируемой
системой.
Генеральный выбор ( )x P y Q→ → вводится, чтобы позволить окружению процес-
132 ISSN 1028-9763. Математичні машини і системи, 2011, № 3
са управлять выбором при условии выбора на первом шаге. Если первое действие невоз-
можно для P , то выбирается Q ; иначе выбирается P . Если первое действие возможно и
для P , и для Q , выбор между ними остается недетерминированным;
– взаимодействие процессов (объединение, синхронизация двух и более процессов).
Процессы могут происходить последовательно и параллельно, взаимодействовать между
собой, обмениваясь сообщениями по входным и выходным каналам. Использование кана-
лов для передачи сообщений между процессами соответствует архитектурному стилю «ка-
налы и фильтры».
Одним из наиболее важных моментов является различие в операторах управления
выбором. Это различие дает возможность моделировать реальные системы, в которых
многие параметры определяются внешними факторами, и является ключевым для описа-
ния некоторых критических свойств архитектурных взаимодействий.
Описание архитектурных взаимодействий устроено таким образом, что имеется
возможность их протоколировать, определять, какое конкретно взаимодействие ответст-
венно за какую функцию и где в модели произошла ошибка, если поведение системы не
соответствует ее спецификации.
3. Введение временного параметра в CSP
Введем следующие подходы к модельному времени в моделировании [6]:
1. Пересчет значения выходного сигнала в моменты особого состояния, когда зара-
нее известны моменты изменения входных сигналов и особых состояний системы (собы-
тийно-ориентированный подход).
2. Пересчет значения выходного сигнала с фиксированным шагом t∆ . При таком
моделировании значение модельного времени на каждом такте увеличивается на фиксиро-
ванную величину. В этот момент можно вычислять логические условия и выполнять собы-
тия. Недостатком данного подхода является возможность "перескочить" момент модельно-
го времени, при котором агрегат находится в особом состоянии. Данная реализация мо-
дельного времени более проста, но уступает предыдущей в эффективности.
3. Пересчет значения выходного сигнала в реальном времени.
На данном этапе для модельного времени реализуются событийно-
ориентированный подход и пересчет значения выходного сигнала с фиксированным ша-
гом.
Рассмотрим введение времени в теорию взаимодействующих процессов Ч. Хоара.
Обозначим временную переменную как t .
Тогда описание процесса P принимает вид
1 1 2 2(( , ) ( , ) ... ( , ) )n nP x t x t x t P= → → → → , (1)
где
nt – время, например количество тактов, за которое выполняется событие
nx .
При этом законы, введенные для процессов, сохраняют свое действие, однако пере-
писываются с учетом времени, например:
1 2 1 2(( , ) ) (( , ) )x t P x t P t t→ = → ⇔ = (2)
или
1 2 3 4 1 4 2 4(( , ) ) | ( , ) ) (( , ) ) ( , ) ) ( ) ( )x t P y t Q y t Q x t P t t t t→ → = → → ⇔ = ∧ = . (3)
Протоколы поведения процессов принимают следующий вид:
1 1 2 2( , ), ( , ),..., ( , )n nx t x t x t< > , (4)
ISSN 1028-9763. Математичні машини і системи, 2011, № 3 133
где
nt – время, за которое выполняется событие
nx .
Операции для работы с протоколами остаются неизменными. Однако введение вре-
мени позволяет расширить функцию переименования f , где f – инъективная функция,
отображающая последовательность символов из множества A в последовательность сим-
волов из множества B . Она может работать не только с множеством событий в протоко-
лах процессов, но и с временем выполнения данных событий, позволяя вводить временные
коэффициенты для управления модельным временем.
Рассмотрим в качестве примера функции переименования оператор twice (“удво-
ить”), который удваивает каждый элемент на входе данного оператора.
Оператор twice без учета времени позволяет получить следующий протокол собы-
тий:
twice*( 1,5,3,6 ) 2,10,6,12< > =< > . (5)
При введении времени получаем расширение возможностей данного оператора:
twice_x *( (1,10), (5,20), (3,30), (6,40) ) (2,10), (10,20), (6,30),(12,40)< > =< > ,
twice_t *( (1,10), (5,20), (3,30), (6,40) ) (1,20), (5,40), (3,60), (6,80)< > =< > , (6)
twice_xt *( (1,10), (5,20), (3,30), (6,40) ) (2,20), (10,40), (6,60), (12,80)< > =< > .
Таким образом, при применении функции f к процессу P с алфавитом Pα , где
каждое событие связано со временем, функция f показывает не только изменение алфа-
вита, но и времени выполнения этих событий, и введя временной коэффициент масштаби-
рования, можно управлять модельным временем.
Протоколы процесса после переименования получаются простой заменой отдель-
ных символов и времени выполнения во всех протоколах исходного процесса.
Помеченное событие со временем принимает вид
.( , )l x t . (7)
Взаимодействие процессов осуществляется по описанным в [2] законам, однако
введение времени позволяет расширить теорию взаимодействующих последовательных
процессов введением дополнительных операторов. Так, введем дополнительный символ ?
для процесса, который
1t единиц времени ведет себя как P , а затем
2t единиц времени ве-
дет себя как Q . Тогда
1 2( ? ) ( ? )R P t Q t= → . (8)
Такое расширение теории взаимодействующих последовательных процессов позво-
лит математически строго описывать причинно-временные зависимости между элемента-
ми системы.
4. Численная оценка времени выполнения процесса
Введение времени в описание процессов позволяет численно оценивать время их выпол-
нения.
Обозначим через ( )PT время выполнения процесса P .
Тогда для префиксно-рекурсивного определения событий получим
1 1 2 2
1
(( , ) ( , ) ... ( , ) ),
( ) .
n n
n
i
i
P x t x t x t P
T P t
=
= → → → →
=∑
(9)
134 ISSN 1028-9763. Математичні машини і системи, 2011, № 3
Для процессов, содержащих операторы выбора, оценивается интервал времени их
выполнения min max( ) [ , ]T P t t∈ , а также при необходимости среднее оценочное значение
( )
2
tt
PT maxmin
^ += (10)
или
1
1
( ) ,
n
i
i
T P t
n =
= ∑ (11)
где
it – длительность выполнения процесса при выборе i -того варианта;
n – количество альтернатив в операторе выбора.
Например, пусть
1 1 2 2 3 3(( , ) ) | ( , ) ( , ) )P x t P x t x t P= → → → . (12)
Тогда
1 2 3( ) |T P t t t= + . (13)
Пусть
1 2 3t t t< + . (14)
Тогда мы можем оценить интервал времени выполнения процесса P :
min max
1 2 3
( ) ,
( ) .
t T P t
t T P t t
≤ ≤
≤ ≤ +
(15)
5. Выводы
В данной работе:
– введен временной параметр в теорию взаимодействующих процессов Хоара;
– переписаны основные операции теории, такие как префиксация, рекурсия, опера-
торы выбора и др. и аксиоматические законы теории с учетом введенного параметра;
– введено численное определение длительности выполнения процесса.
Использование данной теории позволит эффективно моделировать архитектуру со-
временных программных систем.
СПИСОК ЛИТЕРАТУРЫ
1. Бусленко Н.П. Моделирование сложных систем / Бусленко Н.П. – М.: Наука, 1978. – 399 с.
2. Хоар Ч. Взаимодействующие последовательные процессы / Хоар Ч. – М.: Мир, 1989. – 264 с.
3. Milner R. A Calculus of Communicating Systems / R. Milner // Lecture Notes in Computer Sciences. –
1980. – Vol. 92. – 260 p.
4. Milner R. Calculi for Synchrony and Asynchrony / R. Milner // Theoretical Computer Science. – 1983.
– N 25. – Р. 267 – 310.
5. Bergstra J.A. Process Algebra with Asynchronous Communication Mechanisms / J.A. Bergstra,
J.W. Klop // Lecture Notes in Computer Science. In Seminar on Concurrency. – 1985. – N 197. – P. 76 –
95.
6. Satoh I. Time and Asynchrony in Distributed Computing / I. Satoh. – Japan: Keio Univesity, 1996. –
97 р.
Стаття надійшла до редакції 25.05.2011
|