The idea of communicating sequential processes was first clearly stated by Hoare in his 1978 paper "Communicating Sequential Processes" in Communications of the ACM volume 21, number 8. The basic idea of CSP is that multiple concurrent (parallel) processes can synchronize with each other most easily by synchronizing their I/O. The purposed way to do this is to allow I/O to occur only when: Process A states that it is ready to output to process B specifically, and process B states that it is ready to input from process A specifically. If one of these happens without the other being true, the process is put on a wait queue until the other process is ready.
First we need to know what a guarded command is. A guarded command is a normal command (program statement) preceded by a guard, which is a Boolean expression. The statement is only executed if the boolean guard evaluates to true, else the statement is a no-op. Multiple guarded commands can be combined in an Alternative Guarded command. In this case all of the guards are evaluated and on of the ones that evaluate to true is arbitrarily chosen to execute while the others are ignored. Such commands can be repeated, in which case all the guards are evaluated (and their matching statements run) until all of the guards evaluate to false. Finally, a guard can contain an input command. Since input commands are required to state a source process, the input guard is only evaluated if the process named as the source of the data is ready to output.
The Producer-Consumer problem (bounded buffer, see overheads for code). There are three process here; the consumer, the producer, and the buffer X. When the producer wants to produce it sends the output command p to the buffer X. If the buffer is busy at this point, or full, the producer will have to wait. When the consumer wants to consume, it first sends the dummy output command more to the buffer X to signal it is ready to consume (since we allow input commands in guards but not necessarily output commands), and then the input command c. The buffer then, has a repeated, multiple statement guard command, which if the buffer is not empty and the consumer is ready (signals more) sends a buffer element to the consumer, or if the buffer is not full and the producer is ready to send it adds an element to the buffer from the producer. I see two problems with Hoare's solution here. He says the buffer "X is designed to terminate when out=in and the producer is terminated" but there is no code for that, and it would appear difficult to implement that behavior. Also the buffer counters (in and out) are never decremented or assigned to a mod of themselves, only incremented, so they would eventually overflow!
The Dining philosophers problem. Notice the philosophers do only output statements to the room and the forks, while the room and forks do only input statements. Synchronization is achieved because any of the philosophers output statements may cause them to block if their forks are not available. It is interesting to note there is some extra security built in here, a fork will only listen to messages from (and hence can only be "picked up by") a philosopher adjacent to it. Again this code seems to have no real termination condition built in. To prevent deadlock caused by all 5 philosophers entering at once and picking up their left forks and waiting forever for their right fork, the room enter guard should be modified so that occupancy < 5 is part of the guard.
The advantages of CSP are that it is quite simple conceptually, yet provides a good solution to many of the common synchronization problems. CSP does have a couple of MAJOR drawbacks though. The biggest is that it requires explicit naming of both processes involved in any one I/O command pair. The other is that it does not perform any message buffering, but ALWAYS blocks instead. This could be fairly easily implemented by the programmer though.
X::
buffer:(0..9) portion;
in,out:integer; in := 0; out := 0;
comment 0 <= out <= in <= out+10;
*[in < out + 10; producer?buffer(in mod 10) ->
in := in + 1;
[] out < in; consumer?more( ) ->
consumer!buffer(out mod 10); out := out + 1;
PHIL = *[ ...During n'th lifetime
THINK;
room!enter( );
fork(i)!pickup( );
fork((i + 1) mod 5)!pickup;
EAT;
fork(i)!putdown( );
fork((i + 1) mod 5)!putdown( );
room!exit( );
]
FORK = *[
phil(i)?pickup( ) -> phil(i)?putdown( );
[]
phil((i - 1) mod 5)?pickup( ) ->
phil((i - 1) mod 5)?putdown( );
ROOM = occupancy:integer; occupancy = 0;
*[(i:0..4)phil(i)?enter( ) ->
occupancy := occupancy + 1;
[]
(i:0..4)phil(i)?exit( ) ->
occupancy := occupancy - 1;
MAIN = [room::ROOM || fork(i:0..4)::FORK ||
phil(i:0..4)::PHIL].
Go Back to the Operating Systems page.Last updated: 1 Feb 1995 / schmidt@cs.vt.edu