Расчет процесса

В компьютерной науке , то процесс исчисления (или процесс алгебры ) представляют собой разнородное семейство родственных подходов к формально моделированию параллельных систем . Вычисления процессов предоставляют инструмент для высокоуровневого описания взаимодействий, коммуникаций и синхронизации между набором независимых агентов или процессов. Они также предоставляют алгебраические законы, которые позволяют манипулировать описаниями процессов и анализировать их, и позволяют формально рассуждать об эквивалентности между процессами (например, используя бимимуляцию ). Ведущие примеры расчетов процессов включают CSP , CCS , ACP и LOTOS .^[1] Более поздние дополнения к семейству включают π-исчисление , внешнее исчисление , PEPA , интегральное исчисление и объединенное исчисление .

Основные функции [ править ]

Хотя разнообразие существующих вычислений процессов очень велико (включая варианты, которые включают стохастическое поведение, информацию о времени и специализации для изучения молекулярных взаимодействий), есть несколько общих черт, которые имеют все вычисления процессов: ^[2]

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

Математика процессов [ править ]

Чтобы определить исчисление процесса , нужно начать с набора имен (или каналов ), цель которых - предоставить средства связи. Во многих реализациях каналы имеют богатую внутреннюю структуру для повышения эффективности, но в большинстве теоретических моделей это абстрагируется. Помимо имен, нужны средства для формирования новых процессов из старых. Основные операторы, всегда присутствующие в той или иной форме, позволяют: ^[3]

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

Параллельная композиция [ править ]

Параллельная композиция двух процессов и , как правило, записывается , является ключевым примитивом, отличающим вычисления процесса от последовательных моделей вычислений. Параллельный состав позволяет вычисление в и приступить одновременно и независимо друг от друга. Но он также обеспечивает взаимодействие, то есть синхронизация и поток информации от до (или наоборот) по совместно используемому каналу оба. Важно отметить, что агент или процесс могут быть подключены более чем к одному каналу одновременно. ${\ displaystyle {\ mathit {P}}}$ ${\ displaystyle {\ mathit {Q}}}$ ${\ displaystyle P \ vert Q}$ ${\ displaystyle {\ mathit {P}}}$ ${\ displaystyle {\ mathit {Q}}}$ ${\ displaystyle {\ mathit {P}}}$ ${\ displaystyle {\ mathit {Q}}}$

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

Связь [ править ]

Взаимодействие может быть (но не всегда) направленным потоком информации. То есть ввод и вывод можно разделить как примитивы двойного взаимодействия. Вычисления процессов, которые делают такие различия, обычно определяют оператор ввода ( например ) и оператор вывода ( например ), оба из которых называют точку взаимодействия (здесь ), которая используется для синхронизации с примитивом двойного взаимодействия. ${\ Displaystyle х (v)}$ ${\ displaystyle x \ langle y \ rangle}$ ${\ displaystyle {\ mathit {x}}}$

Если происходит обмен информацией, она будет переходить от процесса вывода к процессу ввода. Примитив вывода будет указывать данные для отправки. В , эти данные есть . Точно так же, если вход ожидает получения данных, одна или несколько связанных переменных будут действовать как заполнители, которые будут заменены данными, когда они поступят. В , играет эту роль. Выбор типа данных, которыми можно обмениваться во время взаимодействия, является одной из ключевых особенностей, отличающих различные вычисления процесса. ${\ displaystyle x \ langle y \ rangle}$ ${\ displaystyle y}$ ${\ Displaystyle х (v)}$ ${\ displaystyle v}$

Последовательная композиция [ править ]

Иногда взаимодействия необходимо временно упорядочить. Например, может быть желательно указать такие алгоритмы, как: сначала получить некоторые данные, а затем отправить эти данные ${\ displaystyle {\ mathit {x}}}$ ${\mathit {y}}$ . Для таких целей можно использовать последовательную композицию . Это хорошо известно из других моделей вычислений. В расчетах процессов оператор секвенирования обычно интегрируется с вводом или выводом, либо с обоими. Например, процесс будет ждать ввода . Только когда этот ввод произойдет, процесс будет активирован, и полученные данные будут заменены идентификатором . $x(v)\cdot P$ ${\mathit {x}}$ ${\mathit {P}}$ ${\mathit {x}}$ ${\mathit {v}}$

Семантика редукции [ править ]

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

x\langle y\rangle \cdot P\;\vert \;x(v)\cdot Q\longrightarrow P\;\vert \;Q[^{y}\!/\!_{v}]

Интерпретация этого правила сокращения:

Здесь процесс отправляет сообщение по каналу . Обычно процесс получает это сообщение по каналу . $x\langle y\rangle \cdot P$ ${\mathit {y}}$ ${\mathit {x}}$ $x(v)\cdot Q$ ${\mathit {x}}$
После того, как сообщение было отправлено, оно становится процессом , а становится процессом , в котором заполнитель заменяется полученными данными . $x\langle y\rangle \cdot P$ ${\mathit {P}}$ $x(v)\cdot Q$ $Q[^{y}\!/\!_{v}]$ ${\mathit {Q}}$ ${\mathit {v}}$ ${\mathit {y}}$ ${\mathit {x}}$

Класс процессов, которые могут быть расширены при продолжении операции вывода, существенно влияет на свойства исчисления. ${\mathit {P}}$

Скрытие [ править ]

Процессы не ограничивают количество соединений, которые могут быть установлены в данной точке взаимодействия. Но точки взаимодействия допускают вмешательство (т.е. взаимодействие). Для синтеза компактных, минимальных и композиционных систем решающее значение имеет способность ограничивать интерференцию. Операции сокрытия позволяют контролировать связи между точками взаимодействия при параллельном составлении агентов. Сокрытие можно обозначить по-разному. Например, в я-Исчисление скрытие имени в можно выразить как , в то время как в ПСУ может быть записана в виде . ${\mathit {x}}$ ${\mathit {P}}$ $(\nu \;x)P$ $P\setminus \{x\}$

Рекурсия и репликация [ править ]

Представленные до сих пор операции описывают только конечное взаимодействие и, следовательно, недостаточны для полной вычислимости, которая включает в себя поведение без завершения. Рекурсия и репликация - это операции, которые позволяют конечное описание бесконечного поведения. Рекурсия хорошо известна из мира последовательностей. Под репликацией можно понимать сокращение параллельной композиции счетно бесконечного числа процессов: $!P$ ${\mathit {P}}$

!P=P\mid !P

Нулевой процесс [ править ]

Процесс конкременты как правило , также включают в себя нулевой процесс ( по- разному обозначенный как , , , , или какой - либо другой соответствующий символ) , который не имеет точек взаимодействия. Он совершенно неактивен, и его единственная цель - действовать как индуктивный якорь, на котором могут генерироваться более интересные процессы. ${\mathit {nil}}$ $0$ ${\mathit {STOP}}$ $\delta$

Алгебра дискретных и непрерывных процессов [ править ]

Алгебра процессов изучалась для дискретного времени и непрерывного времени (реального времени или плотного времени). ^[4]

История [ править ]

В первой половине 20-го века были предложены различные формализмы, отражающие неформальную концепцию вычислимой функции , с μ-рекурсивными функциями , машинами Тьюринга и лямбда-исчислением, возможно, наиболее известными примерами сегодня. Удивительный факт, что они по существу эквивалентны в том смысле, что все они кодируются друг в друге, поддерживает тезис Черча-Тьюринга . Еще одна общая особенность комментируется реже: все они легче всего воспринимаются как модели последовательноговычисление. Последующая консолидация информатики потребовала более тонкой формулировки понятия вычислений, в частности явного представления параллелизма и коммуникации. Модели параллелизма, такие как исчисления процессов, сети Петри в 1962 году и модель акторов в 1973 году, возникли в результате этого исследования.

Исследование процесса исчислений начали всерьез с Робин Милнер «плодотворную работу с по исчислению сообщающихся систем (CCS) в период с 1973 по 1980. Хоар » s процессы Взаимодействующие последовательные (НСП) впервые появился в 1978 году и впоследствии был разработан в полноценный процесс исчисления в начале 1980-х годов. По мере развития между CCS и CSP происходил обмен идеями. В 1982 году Ян Бергстра и Ян Виллем Клоп начали работу над тем, что стало известно как алгебра коммуникационных процессов (ACP), и ввели термин « алгебра процессов» для описания своей работы. ^[1] CCS, CSP и ACP составляют три основные ветви семейства вычислений процессов: большинство других вычислений процессов могут прослеживать свои корни до одного из этих трех исчислений.

Текущее исследование [ править ]

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

Разработка новых расчетов процессов для лучшего моделирования вычислительных явлений.
Нахождение корректных субсчетов данного исчисления процесса. Это ценно, потому что (1) большинство исчислений довольно дикие в том смысле, что они довольно общие и мало что можно сказать о произвольных процессах; и (2) вычислительные приложения редко исчерпывают все исчисления. Скорее они используют только очень ограниченные по форме процессы. Ограничение формы процессов в основном изучается с помощью систем типов .
Логика для процессов, позволяющая рассуждать о (по сути) произвольных свойствах процессов, следуя идеям логики Хоара .
Теория поведения: что означает совпадение двух процессов? Как мы можем определить, являются ли два процесса разными или нет? Можем ли мы найти представителей классов эквивалентности процессов? Обычно процессы считаются одинаковыми, если никакой контекст, то есть другие процессы, выполняющиеся параллельно, не может обнаружить разницу. К сожалению, сделать эту интуицию точной сложно и в большинстве случаев дает громоздкие характеристики равенства (которые в большинстве случаев также должны быть неразрешимыми из-за проблемы остановки ). Бисимуляции - это технический инструмент, который помогает рассуждать об эквивалентности процессов.
Выразительность исчислений. Опыт программирования показывает, что на одних языках определенные проблемы решить легче, чем на других. Этот феномен требует более точной характеристики выразительности вычислений, моделирующих вычисления, чем та, которую дает тезис Черча-Тьюринга . Один из способов сделать это - рассмотреть кодировки между двумя формализмами и посмотреть, какие кодировки свойств потенциально могут сохранить. Чем больше свойств может быть сохранено, тем более выразительной будет цель кодирования. Для технологических вычислений знаменитые результаты заключаются в том, что синхронное π-исчисление более выразительно, чем его асинхронный вариант, имеет ту же выразительную силу, что и π-исчисление более высокого порядка , ^[5], но меньше, чемокружающее исчисление . ^{[ необходима цитата ]}
Использование процесса исчисления для моделирования биологических систем (стохастическое π-исчисление, BioAmbients, Beta Binders, BioPEPA, Brane Calculus). Некоторые считают, что композиционность, предлагаемая инструментами теории процессов, может помочь биологам организовать свои знания более формально.

Программные реализации [ править ]

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

CADP
Инструментальные средства параллелизма
набор инструментов mCRL2

Связь с другими моделями параллелизма [ править ]

История Моноид является свободным объектом , который в общем состоянии представлять историю отдельных процессов сообщающихся. Таким образом, исчисление процессов представляет собой формальный язык, наложенный на исторический моноид последовательным образом. ^[6] То есть, исторический моноид может записывать только последовательность событий с синхронизацией, но не определяет разрешенные переходы между состояниями. Таким образом, исчисление процессов для моноида истории то же самое, что формальный язык для свободного моноида (формальный язык - это подмножество множества всех возможных строк конечной длины в алфавите, порожденном звездой Клини ).

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

См. Также [ править ]

Стохастический зонд
Язык темпорального процесса

Ссылки [ править ]

^ а б Баэтен, JCM (2004). «Краткая история алгебры процессов» (PDF) . Сообщение CSR 04-02 . Vakgroep Informatica, Технический университет Эйндховена.
^ Пирс, Бенджамин (1996-12-21). «Основы исчисления для языков программирования». Справочник по информатике и инженерии . CRC Press. С. 2190–2207. ISBN 0-8493-2909-4.
^ Baeten, JCM; Браветти, М. (август 2005 г.). «Общая алгебра процессов» . Вычисления алгебраических процессов: первые двадцать пять лет и далее (Серия заметок БРИКС NS-05-3) . Бертиноро, Форли, Италия: БРИКС, Департамент компьютерных наук, Орхусский университет . Проверено 29 декабря 2007 .
^ Baeten, JCM; Мидделбург, Калифорния "Алгебра процессов с таймингом: реальное и дискретное время". CiteSeerX 10.1.1.42.729 . Cite journal requires |journal= (help)
^ Sangiorgi, Давиде (1993). Gaudel, M. -C .; Жуанно, Ж. -П. (ред.). «От π-исчисления к π-исчислению более высокого порядка - и обратно» . ТАПСОФТ'93: Теория и практика разработки программного обеспечения . Конспект лекций по информатике. Springer Berlin Heidelberg. 668 : 151–166. DOI : 10.1007 / 3-540-56610-4_62 . ISBN 9783540475989.
^ Мазуркевич, Антони (1995). «Введение в теорию трассировки» (PostScript) . В Diekert, V .; Розенберг, Г. (ред.). Книга следов . Сингапур: World Scientific. С. 3–41. ISBN 981-02-2058-8.

Дальнейшее чтение [ править ]

Мэтью Хеннесси : алгебраическая теория процессов , MIT Press , ISBN 0-262-08171-7 .
CAR Hoare : Последовательные процессы передачи информации , Prentice Hall , ISBN 0-13-153289-8 .
- Эта книга была обновлена Джимом Дэвисом из вычислительной лаборатории Оксфордского университета, и новое издание доступно для загрузки в виде файла PDF на веб-сайте Using CSP .
Робин Милнер : расчет коммуникационных систем , Springer Verlag, ISBN 0-387-10235-3 .
Робин Милнер : Коммуникационные и мобильные системы: вычисление Пи , Springer Verlag, ISBN 0-521-65869-1 .
Андрей Миронов : Теория процессов
Валк, Рюдигер ; Молдт, Дэниел; Кёлер-Бусмайер, Майкл, ред. (2011). "Глава 5: Prozessalgebra - Parallele und kommunizierende Prozesse" (PDF) . Formale Grundlagen der Informatik II: Modellierung und Analyze von Informatiksystemen . Theoretische Grundlagen der Informatik (на немецком языке). Часть 2. Гамбургский университет . FGI2. Архивировано (PDF) из оригинала на 2019-07-09 . Проверено 13 июля 2019 .

[baeten2004-1] а б Баэтен, JCM (2004). «Краткая история алгебры процессов» (PDF) . Сообщение CSR 04-02 . Vakgroep Informatica, Технический университет Эйндховена.

[2] Пирс, Бенджамин (1996-12-21). «Основы исчисления для языков программирования». Справочник по информатике и инженерии . CRC Press. С. 2190–2207. ISBN 0-8493-2909-4.

[3] Baeten, JCM; Браветти, М. (август 2005 г.). «Общая алгебра процессов» . Вычисления алгебраических процессов: первые двадцать пять лет и далее (Серия заметок БРИКС NS-05-3) . Бертиноро, Форли, Италия: БРИКС, Департамент компьютерных наук, Орхусский университет . Проверено 29 декабря 2007 .

[4] Baeten, JCM; Мидделбург, Калифорния "Алгебра процессов с таймингом: реальное и дискретное время". CiteSeerX 10.1.1.42.729 . Cite journal requires |journal= (help)

[5] Sangiorgi, Давиде (1993). Gaudel, M. -C .; Жуанно, Ж. -П. (ред.). «От π-исчисления к π-исчислению более высокого порядка - и обратно» . ТАПСОФТ'93: Теория и практика разработки программного обеспечения . Конспект лекций по информатике. Springer Berlin Heidelberg. 668 : 151–166. DOI : 10.1007 / 3-540-56610-4_62 . ISBN 9783540475989.

[6] Мазуркевич, Антони (1995). «Введение в теорию трассировки» (PostScript) . В Diekert, V .; Розенберг, Г. (ред.). Книга следов . Сингапур: World Scientific. С. 3–41. ISBN 981-02-2058-8.

[1]

vтеПараллельные вычисления
Общий	Параллелизм Контроль параллелизма
Расчет процесса	CSP CCS ACP LOTOS π-исчисление Окружающее исчисление API-исчисление PEPA Соединение-исчисление
Классические проблемы	Проблема ABA Проблема курильщиков сигарет Тупик Проблема обедающих философов Проблема производителя и потребителя Состояние гонки Проблема читателей – писателей Проблема сна парикмахера
Категория: Параллельные вычисления