Вычисление процессов

редактировать

Семейство подходов к моделированию параллельных систем

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

Содержание

1 Основные возможности
2 Математика процессов
- 2.1 Параллельная композиция
- 2.2 Связь
- 2.3 Последовательная композиция
- 2.4 Семантика сокращения
- 2.5 Скрытие
- 2.6 Рекурсия и репликация
- 2.7 Нулевой процесс
3 Алгебра дискретных и непрерывных процессов
4 История
5 Текущие исследования
6 Программные реализации
7 Связь с другими моделями параллелизма
8 См. Также
9 Ссылки
10 Дополнительная литература

Существенные особенности

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

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

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

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

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

Параллельная композиция

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

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

Общение

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

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

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

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

Семантика редукции

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

x ⟨y⟩ ⋅ P | x (v) ⋅ Q ⟶ P | Q [y / v] {\ displaystyle x \ langle y \ rangle \ cdot P \; \ vert \; x (v) \ cdot Q \ longrightarrow P \; \ vert \; Q [^ {y} \! / \ ! _ {v}]}

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

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

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

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

Скрытие

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

Recursion and replication

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

! P = P ∣! P {\ displaystyle! P = P \ mid! P}

! P = P \ mid! P

Нулевой процесс

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

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

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

История

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

Исследования процессов исчисления начались всерьез с плодотворной работы Робина Милнера по Исчислению коммуникационных систем (CCS) в период с 1973 по 1980 год. АВТОМОБИЛЬ Книга Хоара Communicating Sequential Processes (CSP) впервые появилась в 1978 году, а в начале 1980-х годов была преобразована в полноценное вычисление процессов. По мере развития между CCS и CSP происходил обмен идеями. В 1982 году Ян Бергстра и Ян Виллем Клоп начали работу над тем, что стало известно как Алгебра коммуникационных процессов (ACP), и ввели термин «алгебра процессов». описать свою работу. CCS, CSP и ACP составляют три основные ветви семейства исчислений процессов: большинство других исчислений процессов могут прослеживать свои корни до одного из этих трех исчислений.

Текущее исследование

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

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

Программные реализации

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

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

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

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

См. Также

Ссылки

Дополнительная литература

Мэтью Хеннесси : Алгебраическая теория процессов, MIT Нажмите, ISBN 0-262-08171-7.
C. AR Hoare : Communicating Sequential Processes, Prentice Hall, ISBN 0-13-153289-8.
- Эта книга была обновлена Джимом Дэвисом из Оксфордского университета Computing Laboratory и новое издание доступны для загрузки в виде файла PDF на веб-сайте Using CSP.
Робин Милнер : Расчет коммуникационных систем, Springer Verlag, ISBN 0-387-10235-3.
Робин Милнер : Коммуникационные и мобильные системы: Pi-Calculus, Springer Verlag, ISBN 0-521-65869-1.
: Теория процессов
Валк, Рюдигер ; Молдт, Дэниел; Köhler-Bußmeier, Michael, ред. (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 г.