Связь последовательных процессов - Communicating sequential processes

В Информатика, связь последовательных процессов (CSP) это формальный язык для описания узоры из взаимодействие в параллельные системы.[1] Это член семейства математических теорий параллелизма, известных как алгебры процессов, или технологические расчеты, на основе передача сообщений через каналы. CSP оказал большое влияние на дизайн Оккам язык программирования[1][2] а также повлиял на дизайн языков программирования, таких как Лимбо,[3] RaftLib, Идти,[4] Кристалл, и Clojure core.async.[5]

CSP был впервые описан в статье 1978 г. Тони Хоар,[6] но с тех пор претерпел существенные изменения.[7] CSP практически применяется в промышленности как инструмент для уточнение и проверка одновременные аспекты множества различных систем, таких как T9000 Транспьютер,[8] а также безопасную систему электронной торговли.[9] Сама теория CSP также по-прежнему является предметом активных исследований, включая работу по расширению диапазона ее практического применения (например, увеличение масштаба систем, которые можно легко анализировать).[10]

История

Версия CSP, представленная в оригинальной статье Хоара 1978 года, была, по сути, языком параллельного программирования, а не языком программирования. процесс исчисления. У него был существенно другой синтаксис чем более поздние версии CSP, не обладали математически определенной семантикой,[11] и не смог представить неограниченный недетерминизм.[12] Программы в исходном CSP были написаны как параллельная композиция из фиксированного числа последовательных процессов, взаимодействующих друг с другом строго посредством синхронной передачи сообщений. В отличие от более поздних версий CSP, каждому процессу было назначено явное имя, а источник или место назначения сообщения определялись путем указания имени предполагаемого процесса отправки или получения. Например, процесс

КОПИЯ = * [c: символ; запад? c → восток! c]

многократно получает символ из процесса с именем Запад и отправляет этот символ в процесс с именем Восток. Параллельная композиция

[запад :: РАЗБОР || X :: КОПИЯ || восток :: ASSEMBLE]

присваивает имена Запад к РАЗБОРКА процесс, Икс к КОПИРОВАТЬ процесс, и Восток к СБОРКА процесс и выполняет эти три процесса одновременно.[6]

После публикации оригинальной версии CSP Хоар, Стивен Брукс и А. В. Роско разработал и усовершенствовал теория CSP в его современной алгебраической форме процесса. Подход, использованный при превращении CSP в алгебру процессов, находился под влиянием Робин Милнер работает над Расчет коммуникационных систем (CCS) и наоборот. Теоретическая версия CSP была первоначально представлена ​​в статье Брукса, Хора и Роско в 1984 г.[13] а позже в книге Хора Связь последовательных процессов,[11] который был опубликован в 1985 году. В сентябре 2006 года эта книга все еще оставалась третий по популярности Информатика ссылка за все время согласно Citeseer[нужна цитата ] (хотя и ненадежный источник из-за характера отбора проб). Теория CSP претерпела несколько незначительных изменений с момента публикации книги Хора. Большинство этих изменений было вызвано появлением автоматизированных инструментов для анализа и проверки процессов CSP. Роско Теория и практика параллелизма[1] описывает эту новую версию CSP.

Приложения

Ранним и важным применением CSP было его использование для спецификации и проверки элементов INMOS T9000. Транспьютер, сложный суперскалярный конвейерный процессор, предназначенный для поддержки крупномасштабной многопроцессорной обработки. CSP использовался для проверки правильности как конвейера процессора, так и процессора виртуального канала, который управлял внешними коммуникациями для процессора.[8]

Промышленное применение CSP для разработки программного обеспечения обычно сосредоточено на надежных и критически важных для безопасности системах. Например, Бременский институт безопасных систем и Daimler-Benz Aerospace смоделировали систему управления сбоями и интерфейс авионики (состоящий примерно из 23 000 строк кода), предназначенные для использования на Международной космической станции в CSP, и проанализировали модель, чтобы подтвердить, что их конструкция свободна от взаимоблокировок и блокировок.[14][15] Процесс моделирования и анализа позволил выявить ряд ошибок, которые было бы трудно обнаружить, используя только тестирование. По аналогии, Системы высокой надежности Praxis применял моделирование и анализ CSP во время разработки программного обеспечения (примерно 100 000 строк кода) для безопасного центра сертификации смарт-карт, чтобы убедиться, что их проект безопасен и свободен от тупиков. Praxis утверждает, что в этой системе уровень дефектов намного ниже, чем в сопоставимых системах.[9]

Поскольку CSP хорошо подходит для моделирования и анализа систем, которые включают в себя сложные обмены сообщениями, его также применяли для проверки протоколов связи и безопасности. Ярким примером такого рода приложений является использование Лоу CSP и Проверка уточнения FDR обнаружить ранее неизвестную атаку на Протокол аутентификации с открытым ключом Нидхема – Шредера, а затем разработать скорректированный протокол, способный отразить атаку.[16]

Неформальное описание

Как следует из названия, CSP позволяет описывать системы в терминах компонентных процессов, которые работают независимо и взаимодействуют друг с другом исключительно через передача сообщений коммуникация. Тем не менее "Последовательный" часть имени CSP теперь является чем-то вроде неправильного употребления, поскольку современные CSP позволяют определять процессы компонентов и как последовательные процессы, и как параллельную композицию более примитивных процессов. Отношения между различными процессами и способ взаимодействия каждого процесса с окружающей средой описываются с использованием различных алгебраический процесс операторы. Используя этот алгебраический подход, довольно сложные описания процессов можно легко построить из нескольких примитивных элементов.

Примитивы

CSP предоставляет два класса примитивов в своей алгебре процессов:

События
События представляют собой общение или взаимодействие. Предполагается, что они неделимы и мгновенны. Они могут быть атомарными именами (например, на, выключенный), составные имена (например, клапан. открыть, valve.close) или события ввода / вывода (например, мышь? ху, экран! растровое изображение).
Примитивные процессы
Примитивные процессы представляют собой фундаментальные модели поведения: примеры включают ОСТАНОВКА (процесс, который ничего не сообщает, также называемый тупик ), и ПРОПУСКАТЬ (что представляет собой успешное завершение).

Алгебраические операторы

CSP имеет широкий набор алгебраических операторов. Основные из них:

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

Примеры

Один из архетипических примеров CSP - это абстрактное представление торгового автомата по продаже шоколада и его взаимодействия с человеком, желающим купить шоколад. Этот торговый автомат может выполнять два разных события, «монета» и «шоколад», которые представляют собой внесение платежа и доставку шоколада соответственно. Автомат, требующий оплаты (только наличными) перед предложением шоколада, можно записать как:

Можно смоделировать человека, который может использовать для платежей монету или карту:

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

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

Если мы абстрагируем этот последний составной процесс, скрывая события «монеты» и «карты», т.е.

мы получаем недетерминированный процесс

Это процесс, который либо предлагает событие «choc», а затем останавливается, либо просто останавливается. Другими словами, если мы рассматриваем абстракцию как внешний вид системы (например, того, кто не видит решения, принятого этим человеком), недетерминизм был введен.

Формальное определение

Синтаксис

Синтаксис CSP определяет «законные» способы объединения процессов и событий. Позволять е быть событием, и Икс быть набором событий. Тогда основные синтаксис CSP можно определить как:

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

Формальная семантика

CSP был наполнен несколькими различными формальная семантика, которые определяют смысл синтаксически правильных выражений CSP. Теория CSP включает взаимно согласованные денотационная семантика, алгебраическая семантика, и операционная семантика.

Денотационная семантика

Три основные денотационные модели CSP - это следы модель, стабильные отказы модель и сбои / расхождения модель. Семантические отображения из выражений процесса в каждую из этих трех моделей обеспечивают денотационную семантику для CSP.[1]

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

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

Более формально смысл процесса п в модели следов определяется как такой, что:

  1. (т.е. содержит пустую последовательность)
  2. (т.е. закрыто по префиксу)

куда - множество всех возможных конечных последовательностей событий.

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

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

Инструменты

За прошедшие годы был создан ряд инструментов для анализа и понимания систем, описанных с помощью CSP. Ранние реализации инструмента использовали различные машиночитаемые синтаксисы для CSP, что делало входные файлы, написанные для разных инструментов, несовместимыми. Однако большинство инструментов CSP теперь стандартизированы на машиночитаемом диалекте CSP, разработанном Брайаном Скаттергудом, иногда называемом CSP.M.[17] CSPM диалект CSP обладает формально определенным операционная семантика, который включает встроенный функциональный язык программирования.

Самый известный инструмент CSP, вероятно, Уточнение отказов / расхождений 2 (FDR2 ), который является коммерческим продуктом, разработанным Formal Systems (Europe) Ltd. FDR2 часто описывается как модель проверки, но технически уточнение checker, поскольку он преобразует два выражения процесса CSP в Помеченные переходные системы (LTS), а затем определяет, является ли один из процессов уточнением другого в рамках определенной семантической модели (трассировки, сбои или сбои / расхождения).[18] FDR2 применяет различные алгоритмы сжатия пространства состояний к LTS процесса, чтобы уменьшить размер пространства состояний, которое необходимо исследовать во время проверки уточнения. На смену FDR2 пришла FDR3, полностью переписанная версия, включающая, помимо прочего, параллельное выполнение и встроенную проверку типов. Он выпущен Оксфордским университетом, который также выпустил FDR2 в период с 2008 по 2012 год.[19]

В Проверка уточнения Аделаиды (ARC)[20] это средство проверки уточнения CSP, разработанное Группой формального моделирования и проверки в Университет Аделаиды. ARC отличается от FDR2 тем, что внутренне представляет процессы CSP как Диаграммы упорядоченных двоичных решений (OBDD), который устраняет проблему взрыва состояния явных представлений LTS, не требуя использования алгоритмов сжатия в пространстве состояний, таких как те, что используются в FDR2.

В ProB проект,[21] который размещается в Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, изначально был создан для поддержки анализа спецификаций, созданных в B метод. Однако он также включает поддержку анализа процессов CSP как посредством проверки уточнения, так и LTL модельная проверка. ProB также можно использовать для проверки свойств комбинированных спецификаций CSP и B. Аниматор ProBE CSP интегрирован в FDR3.

В Набор инструментов для анализа процессов (PAT)[22][23] это инструмент анализа CSP, разработанный в Школе вычислительной техники Национальный университет Сингапура. PAT может выполнять проверку уточнения, проверку модели LTL и моделирование процессов CSP и Timed CSP. Язык процессов PAT расширяет CSP за счет поддержки изменяемых общих переменных, асинхронной передачи сообщений и различных структур процессов, связанных со справедливостью и количественным временем, таких как срок и Подожди до. Базовый принцип проектирования языка процессов PAT заключается в объединении языка спецификаций высокого уровня с процедурными программами (например, событие в PAT может быть последовательной программой или даже вызовом внешней библиотеки C #) для большей выразительности. Изменяемые общие переменные и асинхронные каналы обеспечивают удобный синтаксический сахар для хорошо известных шаблонов моделирования процессов, используемых в стандартном CSP. Синтаксис PAT похож на CSP, но не идентичен ему.M.[24] Принципиальные различия между синтаксисом PAT и стандартным CSPM - это использование точки с запятой для завершения выражений процесса, включение синтаксического сахара для переменных и присваиваний, а также использование немного другого синтаксиса для внутреннего выбора и параллельной композиции.

VisualNets[25] производит анимированные визуализации систем CSP на основе спецификаций и поддерживает синхронизированные CSP.

CSPsim[26] это ленивый симулятор. Он не моделирует проверку CSP, но полезен для исследования очень больших (потенциально бесконечных) систем.

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

Связанные формализмы

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

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

Поскольку это связано с параллельными процессами, которые обмениваются сообщениями, Актерская модель в целом похож на CSP. Однако эти две модели делают несколько принципиально разных выборов в отношении предоставляемых ими примитивов:

  • Процессы CSP анонимны, в то время как субъекты имеют личность.
  • CSP использует явные каналы для передачи сообщений, тогда как системы субъектов передают сообщения названным субъектам назначения. Эти подходы можно рассматривать как двойственные друг другу в том смысле, что процессы, принимающие по одному каналу, фактически имеют идентичность, соответствующую этому каналу, в то время как связь на основе имени между акторами может быть нарушена путем создания акторов, которые ведут себя как каналы.
  • Передача сообщений CSP в основном включает в себя рандеву между процессами, участвующими в отправке и получении сообщения, то есть отправитель не может передать сообщение, пока получатель не будет готов его принять. В отличие от этого, передача сообщений в системах-акторах является в основном асинхронной, то есть передача и прием сообщений не обязательно должны происходить одновременно, и отправители могут передавать сообщения до того, как получатели будут готовы их принять. Эти подходы также можно рассматривать как двойственные друг другу в том смысле, что системы на основе рандеву могут использоваться для построения буферизованных коммуникаций, которые ведут себя как системы асинхронного обмена сообщениями, в то время как асинхронные системы могут использоваться для построения коммуникаций в стиле рандеву с использованием сообщения / протокол подтверждения для синхронизации отправителей и получателей.

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

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

  1. ^ а б c d Роско, А.В. (1997). Теория и практика параллелизма. Prentice Hall. ISBN  978-0-13-674409-2.
  2. ^ Inmos (1995-05-12). Occam 2.1 Справочное руководство (PDF). SGS-THOMSON Microelectronics Ltd., Документ INMOS 72 ок 45 03.
  3. ^ «Ресурсы о многопоточном программировании в стиле Bell Labs CSP». Получено 2010-04-15.
  4. ^ «Вопросы и ответы по языковому дизайну: зачем создавать параллелизм на идеях CSP?».
  5. ^ "Каналы Clojure core.async".
  6. ^ а б Хоар, К.А.Р. (1978). «Связь последовательных процессов». Коммуникации ACM. 21 (8): 666–677. Дои:10.1145/359576.359585. S2CID  849342.
  7. ^ Abdallah, Ali E .; Джонс, Клифф Б.; Сандерс, Джефф В. (2005). Коммуникация последовательных процессов: первые 25 лет. LNCS. 3525. Springer. ISBN  9783540258131.
  8. ^ а б Барретт, Г. (1995). «Проверка модели на практике: процессор виртуального канала T9000». IEEE Transactions по разработке программного обеспечения. 21 (2): 69–78. Дои:10.1109/32.345823.
  9. ^ а б Холл, А; Чепмен, Р. (2002). «Правильность по конструкции: разработка коммерческой системы безопасности» (PDF). Программное обеспечение IEEE. 19 (1): 18–25. CiteSeerX  10.1.1.16.1811. Дои:10.1109/52.976937.
  10. ^ Криз, С. (2001). Индукция, независимая от данных: проверка модели CSP для сетей произвольного размера (= Д. Фил.). Оксфордский университет. CiteSeerX  10.1.1.13.7185.
  11. ^ а б Хоар, К.А.Р. (1985). Связь последовательных процессов. Прентис Холл. ISBN  978-0-13-153289-2.
  12. ^ Клингер, Уильям (Июнь 1981 г.). Основы актерской семантики (Докторская диссертация по математике). Массачусетский технологический институт. HDL:1721.1/6935.
  13. ^ Брукс, Стивен; Хоар, К.А.Р.; Роско, А.В. (1984). «Теория сообщающихся последовательных процессов». Журнал ACM. 31 (3): 560–599. Дои:10.1145/828.833. S2CID  488666.
  14. ^ Buth, B .; М. Куварас; Я. Пелеска; Х. Ши (декабрь 1997 г.). «Анализ тупиков для отказоустойчивой системы». Материалы 6-й Международной конференции по методологии алгебры и программным технологиям (AMAST’97). С. 60–75.
  15. ^ Buth, B .; Я. Пелеска; Х. Ши (январь 1999 г.). «Комбинирование методов анализа отказоустойчивой системы в режиме livelock». Материалы 7-й Международной конференции по методологии алгебры и программным технологиям (AMAST’98). С. 124–139.
  16. ^ Лоу, Г. (1996). «Взлом и исправление протокола открытого ключа Нидхэма – Шредера с использованием FDR». Инструменты и алгоритмы построения и анализа систем (TACAS). Springer-Verlag. С. 147–166.
  17. ^ Скэттергуд, Дж. Б. (1998). «Семантика и реализация машиночитаемых CSP». D.Phil. Вычислительная лаборатория Оксфордского университета. Цитировать журнал требует | журнал = (помощь)
  18. ^ A.W. Роско (1994). «Модель-проверка CSP». В Классический разум: эссе в честь К.А.Р. Hoare. Прентис Холл. Цитировать журнал требует | журнал = (помощь)
  19. ^ «Введение - документация FDR 4.2.4». www.cs.ox.ac.uk.
  20. ^ Парашкевов, Атанас Н .; Янчев, Джей (1996). «ARC - инструмент для эффективного уточнения и проверки эквивалентности для CSP». IEEE Int. Конф. по алгоритмам и архитектурам параллельной обработки ICA3PP '96. С. 68–75. CiteSeerX  10.1.1.45.3212.
  21. ^ Леушель, Майкл; Фонтейн, Марк (2008). «Исследование глубины CSP-M: новый инструмент проверки, совместимый с FDR» (PDF). ICFEM 2008. Springer-Verlag. Архивировано из оригинал (PDF) на 2011-07-19. Получено 2008-11-26.
  22. ^ Вс, июн; Лю, Ян; Донг, Джин Сон (2009). «PAT: на пути к гибкой проверке на справедливости» (PDF). Труды 20-й Международной конференции по компьютерной проверке (CAV 2009). Конспект лекций по информатике. 5643. Springer. Архивировано из оригинал (PDF) на 2011-06-11. Получено 2009-06-16.
  23. ^ Вс, июн; Лю, Ян; Донг, Джин Сон (2008). «Возвращение к проверке модели CSP: введение в инструментарий анализа процессов» (PDF). Труды Третьего Международного симпозиума по использованию формальных методов, верификации и валидации (ISoLA 2008). Коммуникации в компьютерных и информационных науках. 17. Springer. С. 307–322. Архивировано из оригинал (PDF) на 2009-01-08. Получено 2009-01-15.
  24. ^ Вс, июн; Лю, Ян; Донг, Джин Сон; Чен, Чуньцин (2009). «Интеграция спецификаций и программ для спецификации и проверки системы» (PDF). IEEE Int. Конф. по теоретическим аспектам программной инженерии TASE '09. Архивировано из оригинал (PDF) на 2011-06-11. Получено 2009-04-13.
  25. ^ Грин, Марк; Абдалла, Али (2002). «Анализ производительности и настройка поведения для оптимизации коммуникационных систем». Коммуникационные архитектуры процессов 2002.
  26. ^ Брук, Филипп; Пейдж, Ричард (2007). «Ленивое исследование и проверка моделей CSP с помощью CSPsim». Взаимодействие с архитектурами процессов 2007.
  27. ^ ISO 8807, Язык спецификации временного упорядочивания

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

внешняя ссылка

  • PDF-версия книги Hoare's CSP - Действуют ограничения авторских прав, см. Текст страницы перед загрузкой.
  • WoTUG, группа пользователей для систем CSP и occam style, содержит некоторую информацию о CSP и полезные ссылки.
  • Цитаты CSP от CiteSeer