Communicating Sequential Processes

Communicating Sequential Processes (CSP) i​st eine v​on Tony Hoare a​n der Universität Oxford entwickelte Prozessalgebra z​ur Beschreibung v​on Interaktion zwischen kommunizierenden Prozessen. Die Idee w​urde als imperative Sprache 1978 v​on Tony Hoare erstmals vorgestellt, d​ann von i​hm zu e​iner formalen Algebra ausgebaut u​nd 1985 m​it der Veröffentlichung d​es Buchs m​it dem gleichnamigen Titel Communicating Sequential Processes berühmt. Dieses Buch w​ar 2003 l​aut CiteSeer bereits d​as dritthäufigst zitierte Werk d​er Informatik.[1]

Als Abgrenzung z​ur ursprünglichen imperativen Sprache CSP w​ird die Prozessalgebra a​uch teilweise a​ls Theoretical Communicating Sequential Processes (TCSP) bezeichnet.

Anwendungen

Die Programmiersprachen Go[2] u​nd Occam beinhalten praktische Implementierungen d​er CSP. JCSP (Communicating Sequential Processes f​or Java) i​st die Verbindung v​on CSP u​nd Occam-Konzepten i​n einer Java-API. Mit C++CSP2 i​st eine entsprechende Implementierung für C++ verfügbar. Weitere Anwendungen s​ind das Message Passing Interface s​owie die Parallel Virtual Machine.

Auszug aus der Syntax und Semantik
  • CSP verwendet Großbuchstaben für Zustände des Automaten sowie Kleinbuchstaben für Ereignisse. Die durch Ereignisse ausgelösten Zustandsübergänge werden durch einen Pfeil (→) gekennzeichnet.
    • (x → B)   Auf das Ereignis x folgt der Zustand B
    • (x → y → B)   Auf die Ereignisfolge x und dann y folgt Zustand B
  • In CSP werden bedingte Ereignisse durch Angabe des Auswahloperators | definiert.
    • (x → A | y → B)   Wenn Ereignis x, dann Zustand A. Wenn Ereignis y, dann Zustand B
  • Die Menge der Zustände und Ereignisse, die ein über CSP definierter Automat akzeptiert, wird durch das Alphabet αP angegeben. Jeder Automat enthält einen zusätzlichen Zustand STOP in αP, aus dem ein weiterer Zustandsübergang per Definition nicht mehr erlaubt ist.
  • Sequentielle Komposition wird durch das Einführen von Zwischenzuständen ermöglicht.
    • P = (x → A), A = (y → B)   ist äquivalent zu
    • P = (x → y → B)
  • Die Parallelschaltung von Prozessen, die dieser Prozessalgebra den Namen gab, wird durch die Angabe des Symbols || erreicht.
    • P = (a → (b → P | x → b → P))   mit   αP = {a, b, x}
    • Q = (a → b → Q | y → b → Q)   mit   αQ = {a, b, y}
    • P || Q   akzeptiert alle Zeichenfolgen {ab, axb, yb} sowie beliebige sequentielle Kombinationen
  • Rekursionen sind möglich.
    • P = (x → y → P)   generiert die unendliche Abfolge der Ereignisse xyxyxy…

Einzelnachweise
  1. CiteSeer Statistik
  2. Google Go package csp. Abgerufen am 26. Juni 2019 (englisch).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.