동시성 모델 및 프로세스 계산법

동시성 모델과 프로세스 계산법은 독립적인 프로세스가 어떻게 실행되고, 통신하며, 동기화되는지에 대한 형식적인 설명을 제공합니다.

Definition

프로세스 계산법(process calculus)은 병렬 구성, 통신, 선택을 위한 연산자와 두 프로세스가 동일하게 동작하는 시점을 결정하는 등가성을 사용하여 동시 시스템을 통신 프로세스로 기술하기 위한 형식 대수입니다.

Scope

이 주제는 동시 계산의 대수적 모델을 다룹니다: Hoare의 CSP와 Milner의 CCS, 통신 토폴로지가 변하는 모바일 프로세스를 위한 파이-계산법(pi-calculus), 그리고 비동기 메시지 전달의 액터 모델(actor model)을 포함합니다. 또한 통신 및 동기화 기본 요소, 비시뮬레이션(bisimulation)과 같은 행위적 등가성, 그리고 공유 메모리(shared-memory)와 메시지 전달(message-passing) 동시성 간의 대조를 다룹니다.

Core questions

• 동시 통신 프로세스를 대수적으로 어떻게 기술할 수 있는가?
• 두 동시 프로세스가 행위적으로 언제 등가한가?
• 메시지 전달은 공유 메모리 동시성과 어떻게 비교되는가?
• 파이-계산법에서처럼 동적 통신 구조는 어떻게 모델링되는가?

Key theories

통신 순차 프로세스 (CSP)

Hoare의 CSP는 공유 통신 이벤트에서 동기화하는 프로세스를 통해 동시성을 모델링하며, 메시지 전달 언어의 기초와 프로세스 정제 이론을 제공합니다.

CCS 및 비시뮬레이션

Milner의 통신 시스템 계산법(Calculus of Communicating Systems)은 프로세스가 언제 상호 교환 가능한지에 대한 추론을 위한 정밀한 행위적 등가성 개념인 비시뮬레이션을 가진 프로세스 대수를 제공합니다.

파이-계산법

Milner, Parrow, Walker는 프로세스 계산법을 이동성으로 확장하여 통신 채널 자체가 메시지로 전달될 수 있도록 함으로써 연결 구조가 동적으로 진화할 수 있게 했습니다.

Clinical relevance

프로세스 계산법과 액터 모델은 메시지 전달을 기반으로 하는 동시 및 분산 언어와 프레임워크 설계의 기초를 형성하며, 프로토콜을 명세하고 검증하기 위한 형식적인 도구를 제공합니다. 비시뮬레이션과 정제(refinement)는 올바른 동시 동작에 대한 정확한 기준을 제시합니다.

History

동시성 이론은 1970년대 후반 Hoare의 CSP와 Milner의 CCS로 성숙했으며, Hewitt의 액터 모델(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

비시뮬레이션이란 무엇인가?

비시뮬레이션은 각 프로세스가 상대방의 관찰 가능한 단계를 무한정 일치시킬 수 있을 때 성립하는 프로세스 간의 등가성으로, 두 동시 프로세스가 동일한 동작을 나타낸다는 아이디어를 형식화합니다.

파이-계산법은 이전 계산법에 비해 무엇을 추가하는가?

파이-계산법은 통신 채널을 메시지로 보낼 수 있도록 하여 이동성을 모델링하므로, 누가 누구와 통신할 수 있는지의 토폴로지가 실행 중에 변경될 수 있어 동적이고 재구성 가능한 시스템을 포착합니다.