CS 563 Concurrent Programming
Lecture 6: Communicating Sequential Processes (CSP)
Communication Sequential Processes
Copyright By PowCoder代写 加微信 powcoder
CSP is a formal language for describing concurrent systems It was introduced by C.A.R. Hoare in 1978
An implementation of CSP (OCCAM) was used in the T9000 Transputer
Destination!port(e1, … , en)
Source?port(x1, …, xn)
Destination
Example: Copy
West e c Copy c
process Copy { char c;
x= eval(c)
c= eval(e)
do true ->
West?c; # input char from West East!c; # output char to East
CSP: The Main Idea
Something similar to input and output can be used to allow processes to communicate
Multiple communicating processes can be present in both a single machine and across multiple machines
Equivalent to
CSP Process Interaction
Processes interact via synchronous message passing
When a process gets to a send, it has to wait until the receiving process is ready to receive
When a process gets to a receive, it has to wait until the sending process sends
Processes have to rendezvous at a point, or else process is blocked Processes have to be named explicitly
Example: GCD
process GCD { int id, x, y;
Any Source
do true ->
Client[*] ? args(id, x, y); # input a “call” # repeat the following until x == y
do x > y -> x = x – y;
[ ]x
Client[id] ! result(x); # return the result
Nondeterministic Choice
Destination
Guarded Communication
CSP is partially based on a programming construct proposed by Dijkstra to indicate the concurrent execution of processes and non- determinism
Syntax: B; C->S; Example:
process Copy { char c;
do West?c -> East!c; od }
Guarded Communication Example
Define a process that repeatedly accepts input from the user, squares it and sends it to process C
Without guards:
*[x:integer; user?x; C!x*x]
With guards:
*[x:integer; user?x ->C ! x*x]
User ? X is the guard
C ! x*x is the guarded command
Repeatedly square input
Guarded Outcomes
The guard succeeds when the Boolean expression is true, and (if the guard includes I/O), the I/O does not block
The guard fails if the Boolean is false
The guard is neither true or false if the Boolean is true and the I/O of the guard does block
Specifying Alternative Commands
*[
[]
[]
[]
1. If all guards fail, the result is
an error.!
2. If one guard succeeds, it
executes its command (or
command list).!
3. If more than 1 guard
succeeds, one of the commands (whose guard was true) is non-deterministically chosen and executed!
4. If none succeed, but not all fail, wait.!
Buffering I
process Copy {
char c1, c2;
West ? c1;
do West ? c2 -> East ! c1; c1 = c2; [ ]East ! c1->West?c1;
Buffering II
process Copy {
char buffer[10];
int front = 0, rear = 0, count = 0;
do count < 10; West ? buffer[rear] ->
count = count+1; rear = (rear + 1) mod 10; [ ]count>0;East!buffer[front]->
count = count – 1; front = (front + 1) mod 10; od
Resource Allocation
process Allocator {
int avail = MAXUNITS;
set units = initial values;
int index, unitid;
do avail > 0; Client[*] ? acquire (index) ->
avail–; remove (units, unitid);
Client [index] ! reply (unitid);
[ ] Client[*] ? release (index, unitid) ->
avail++; insert (units, unitid); od
Sieve of Erastosthenes
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com