Communicating Sequential Processes

Communicating Sequential Processes

Communicating Sequential Processes (CSP) ist eine von Tony Hoare an der Universität Oxford entwickelte Prozessalgebra zur Beschreibung von Interaktion zwischen kommunizierenden Prozessen. Die Idee wurde als imperative Sprache 1978 von Tony Hoare erstmals vorgestellt, dann von ihm zu einer formalen Algebra ausgebaut und 1985 mit der Veröffentlichung des Buchs mit dem gleichnamigen Titel Communicating Sequential Processes berühmt. Dieses Buch war 2003 nach CiteSeer bereits das dritthäufigst zitierte Werk der Informatik.[1]

Als Abgrenzung zur ursprünglichen imperativen Sprache CSP wird die Prozessalgebra auch teilweise als Theoretical Communicating Sequential Processes (TCSP) bezeichnet.

Inhaltsverzeichnis

Anwendungen

Die Programmiersprache Occam ist eine praktische Implementierung der CSP. JCSP (Communicating Sequential Processes for Java) ist die Verbindung von CSP und Occam-Konzepten in einer Java-API. Mit C++CSP2 ist eine entsprechende Implementierung für C++ verfügbar. Weitere Anwendungen sind das Message Passing Interface sowie 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 → P) | (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…

Weblinks

Einzelnachweise

  1. CiteSeer Statistik

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Communicating Sequential Processes — En programmation concurrente[1], Communicating sequential processes (CSP) est une algèbre de processus permettant de modéliser l interaction de systèmes. CSP intègre un mécanisme de synchronisation basé sur le principe du rendez vous (détaillé… …   Wikipédia en Français

  • Communicating sequential processes — In computer science, Communicating Sequential Processes (CSP) is a formal language for describing patterns of interaction in concurrent systems.[1] It is a member of the family of mathematical theories of concurrency known as process algebras, or …   Wikipedia

  • Communicating sequential processes — En programmation concurrente[1], Communicating sequential processes (CSP) est une algèbre de processus permettant de modéliser l interaction de systèmes. CSP intègre un mécanisme de synchronisation basé sur le principe du rendez vous (détaillé… …   Wikipédia en Français

  • Calculus of communicating systems — The Calculus of Communicating Systems (CCS) is a process calculus introduced by Robin Milner in around 1980. Its actions model indivisible communications between exactly two participants. The formal language includes primitives for describing… …   Wikipedia

  • Algebra of Communicating Processes — The Algebra of Communicating Processes (ACP) is an algebraic approach to reasoning about concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras or process calculi. ACP was initially… …   Wikipedia

  • CSP — Communicating Sequential Processes (Computing » Networking) **** Chip scale package (Academic & Science » Electronics) *** Community Safety Partnership (Governmental » Police) *** Cryptographic Service Provider (Governmental » Military) ***… …   Abbreviations dictionary

  • Actor model and process calculi history — The Actor model and process calculi share an interesting history and co evolution.Early workThe Actor model, first published in 1973, [Carl Hewitt, Peter Bishop and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence… …   Wikipedia

  • Actor model — In computer science, the Actor model is a mathematical model of concurrent computation that treats actors as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions …   Wikipedia

  • Process calculus — In computer science, the process calculi (or process algebras) are a diverse family of related approaches to formally modelling concurrent systems. Process calculi provide a tool for the high level description of interactions, communications, and …   Wikipedia

  • Communications protocol — For other senses of this word, see Protocol. A communications protocol is a system of digital message formats and rules for exchanging those messages in or between computing systems and in telecommunications. A protocol may have a formal… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”