Nebenläufigkeitsmodelle und Prozesskalküle

Nebenläufigkeitsmodelle und Prozesskalküle bieten formale Beschreibungen, wie unabhängige Prozesse ausgeführt werden, kommunizieren und synchronisieren.

Definition

Ein Prozesskalkül ist eine formale Algebra zur Beschreibung nebenläufiger Systeme als kommunizierende Prozesse, mit Operatoren für parallele Komposition, Kommunikation und Auswahl sowie Äquivalenzen, die bestimmen, wann zwei Prozesse sich gleich verhalten.

Scope

Dieses Thema behandelt algebraische Modelle der nebenläufigen Berechnung: Hoares CSP und Milners CCS, den Pi-Kalkül für mobile Prozesse, deren Kommunikations-Topologie sich ändert, und das Aktorenmodell der asynchronen Nachrichtenübermittlung. Es befasst sich mit Kommunikations- und Synchronisationsprimitiven, Verhaltensäquivalenzen wie der Bisimulation und dem Kontrast zwischen Shared-Memory- und Message-Passing-Nebenläufigkeit.

Core questions

• Wie können nebenläufige kommunizierende Prozesse algebraisch beschrieben werden?
• Wann sind zwei nebenläufige Prozesse verhaltensmäßig äquivalent?
• Wie verhält sich die Nachrichtenübermittlung im Vergleich zur Shared-Memory-Nebenläufigkeit?
• Wie werden dynamische Kommunikationsstrukturen modelliert, wie im Pi-Kalkül?

Key theories

Communicating Sequential Processes (CSP)

Hoares CSP modelliert Nebenläufigkeit durch Prozesse, die sich bei gemeinsamen Kommunikationsereignissen synchronisieren, und bietet eine Grundlage für Message-Passing-Sprachen sowie eine Theorie der Prozessverfeinerung.

CCS und Bisimulation

Milners Calculus of Communicating Systems bietet eine Algebra von Prozessen mit einem präzisen Begriff der Verhaltensäquivalenz, der Bisimulation, um zu begründen, wann Prozesse austauschbar sind.

Der Pi-Kalkül

Milner, Parrow und Walker erweiterten Prozesskalküle auf Mobilität, indem sie es ermöglichten, Kommunikationskanäle selbst als Nachrichten zu übergeben, sodass sich die Verbindungsstruktur dynamisch entwickelt.

Clinical relevance

Prozesskalküle und das Aktorenmodell untermauern das Design von nebenläufigen und verteilten Sprachen und Frameworks, die auf Nachrichtenübermittlung basieren, und sie bieten formale Werkzeuge zur Spezifikation und Verifikation von Protokollen. Bisimulation und Verfeinerung liefern präzise Kriterien für korrektes nebenläufiges Verhalten.

History

Die Theorie der Nebenläufigkeit reifte Ende der 1970er Jahre mit Hoares CSP und Milners CCS, während Hewitts Aktorenmodell (1973) eine asynchrone Alternative zur Nachrichtenübermittlung bot. Der Pi-Kalkül erfasste 1992 die Prozessmobilität. Diese Kalküle beeinflussten Message-Passing-Sprachen und Nebenläufigkeitsbibliotheken und bleiben Grundlagen für die Protokollverifikation.

Debates

Shared Memory versus Message Passing

Eine grundlegende Designfrage ist, ob Nebenläufigkeit um einen gemeinsam genutzten, veränderlichen Zustand mit Synchronisation oder um isolierte Prozesse, die Nachrichten austauschen, organisiert werden sollte, wobei Prozesskalküle und das Aktorenmodell Letzteres befürworten.

Key figures

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

Seminal works

• hoare1978
• milner1989
• milner1992
• hewitt1973

Frequently asked questions

Was ist Bisimulation?

Bisimulation ist eine Äquivalenz von Prozessen, die dann gilt, wenn jeder die beobachtbaren Schritte des anderen unbegrenzt nachvollziehen kann, wodurch die Vorstellung formalisiert wird, dass zwei nebenläufige Prozesse dasselbe Verhalten zeigen.

Was fügt der Pi-Kalkül gegenüber früheren Kalkülen hinzu?

Der Pi-Kalkül modelliert Mobilität, indem er das Senden von Kommunikationskanälen als Nachrichten erlaubt, sodass sich die Topologie, wer mit wem sprechen kann, während der Ausführung ändern kann, wodurch dynamische und rekonfigurierbare Systeme erfasst werden.