Модели параллелизма и процессные исчисления

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

Definition

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

Scope

Эта тема охватывает алгебраические модели параллельных вычислений: CSP Хоара и CCS Милнера, пи-исчисление для мобильных процессов, чья топология связи изменяется, и акторную модель асинхронной передачи сообщений. Она затрагивает примитивы связи и синхронизации, поведенческие эквивалентности, такие как бисимуляция, и контраст между параллелизмом с общей памятью и передачей сообщений.

Core questions

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

Key theories

Взаимодействующие последовательные процессы (CSP)

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

CCS и бисимуляция

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

Пи-исчисление

Милнер, Пэрроу и Уокер расширили процессные исчисления до мобильности, позволяя передавать сами каналы связи в качестве сообщений, так что структура соединений динамически развивается.

Clinical relevance

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

History

Теория параллелизма сформировалась в конце 1970-х годов с появлением CSP Хоара и CCS Милнера, в то время как акторная модель Хьюитта (1973) предложила альтернативу асинхронной передачи сообщений. Пи-исчисление в 1992 году позволило моделировать мобильность процессов. Эти исчисления повлияли на языки передачи сообщений и библиотеки параллелизма и остаются основой для верификации протоколов.

Debates

Общая память против передачи сообщений

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

Key figures

• C. A. R. Hoare
• Robin Milner
• Carl Hewitt
• Joachim Parrow
• David Walker

Seminal works

• hoare1978
• milner1989
• milner1992
• hewitt1973

Frequently asked questions

Что такое бисимуляция?

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

Что пи-исчисление добавляет по сравнению с более ранними исчислениями?

Пи-исчисление моделирует мобильность, позволяя отправлять каналы связи в качестве сообщений, так что топология того, кто с кем может общаться, может меняться во время выполнения, что позволяет описывать динамические и реконфигурируемые системы.