Исчисление процессов

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

В информатике исчисления процессов ( или алгебры процессов ) представляют собой разнообразное семейство родственных подходов к формальному моделированию параллельных систем . Исчисления процессов предоставляют инструмент для высокоуровневого описания взаимодействий, коммуникаций и синхронизации между набором независимых агентов или процессов. Они также предоставляют алгебраические законы, которые позволяют манипулировать и анализировать описания процессов, а также позволяют формально рассуждать об эквивалентности между процессами (например, с использованием бисимуляции ). Ведущие примеры исчислений процессов включают 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 x(v)}$ ${\displaystyle x\langle y\rangle }$ ${\displaystyle {\mathit {x}}}$

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

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

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

Семантика сокращения

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

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

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

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

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

Прячется

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

Рекурсия и репликация

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

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

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

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

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

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

История

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

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

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

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

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

Реализации программного обеспечения

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

• КАДР
• Инструментальные средства параллелизма
• набор инструментов mCRL2

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

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

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

Смотрите также

• Коммуникация последовательных процессов
• ПроВериф
• Стохастический зонд
• Тамарин Прувер
• Язык временных процессов
• π-исчисление

Рекомендации

1. Баетен, JCM (2004). «Краткая история алгебры процессов» (PDF) . Раппорт КСО 04-02 . Вакгруппа информатики, Технический университет Эйндховена.
2. Пирс, Бенджамин (21 декабря 1996 г.). «Основные вычисления для языков программирования». Справочник по информатике и инженерии . ЦРК Пресс. стр. 2190–2207. ISBN 0-8493-2909-4.
3. Баетен, JCM; Браветти, М. (август 2005 г.). «Общая алгебра процессов». Исчисление алгебраических процессов: первые двадцать пять лет и позже (серия заметок БРИКС NS-05-3) . Бертиноро, Форли, Италия: БРИКС, факультет компьютерных наук, Орхусский университет . Проверено 29 декабря 2007 г.
4. Баетен, JCM; Мидделбург, Калифорния (2000). «Алгебра процессов с синхронизацией: реальное время и дискретное время»: 627–684. CiteSeerX 10.1.1.42.729 .  {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
5. Санджорджи, Давиде (1993). «От π-исчисления к π-исчислению высшего порядка — и обратно». В Гауделе, М.-К.; Жуанно, Ж.-П. (ред.). TAPSOFT'93: Теория и практика разработки программного обеспечения . Конспекты лекций по информатике. Том. 668. Шпрингер Берлин Гейдельберг. стр. 151–166. дои : 10.1007/3-540-56610-4_62 . ISBN 9783540475989.
6. Мазуркевич, Антони (1995). «Введение в теорию следов». В Дикерте, В.; Розенберг, Г. (ред.). Книга Следов . Сингапур: World Scientific. стр. 3–41. ISBN 981-02-2058-8. Архивировано из оригинала (PostScript) 13 июня 2011 г. Проверено 29 апреля 2009 г.

дальнейшее чтение

• Мэтью Хеннесси : Алгебраическая теория процессов , MIT Press , ISBN 0-262-08171-7 . 
• АВТОМОБИЛЬ Хоар : Связь последовательных процессов , Прентис Холл , 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 Analyse von Informatiksystemen (на немецком языке). Том. Часть 2. Гамбургский университет . ФГИ2. Архивировано (PDF) из оригинала 9 июля 2019 г. Проверено 13 июля 2019 г. {{cite book}}: |work=игнорируется ( помощь )