Communicating Sequential Processes (CSP)

BAP Online Manuals : Bap Language Tutorial : BAP Communication Layers : Communicating Sequential Processes (CSP)
Previous: BAP Communication Layers
Next: Low Level Router and the 'C' Layer

2.4.1. Communicating Sequential Processes (CSP)

The CSP modell is based on the idea of several 'regular' sequential processes that are running in parallel to each other. In this context its not important if these processes are really running on distinct processors or if they are scheduled on one processor my a multitasking environment. The important difference to a single sequential process is that the programmer never know, how much time a process will need to finish a (sub-) program.

Thus there are two major new problems: How to communicate (transport data between the processes) and how to synchronize certain actions.

Communication

There are two major ideas about interprocess communication. The one uses a portion of shared memory (that two or more processes can use), the other uses messages . Please note that the message is definitely the more general mechanism because shared memory can easyly be used to implement messages, while the opposite attempt produces a lot of overhead.

Synchronization

Many different schemes of synchronization have been developed in the past. Here only semaphores and messages are considered.

The purpose of a semaphore is to protect a critical region. A critical region is for example a pice of code that acceses a harware port. Only one process ever may access this port at a time. To guarantee that there is no other process entering such a pice of code, a 'SemP()' command is set before the critical region and a 'SemP()' behind. However, semaphres are not a part of BAP so I will stop explaining here.

Messages can be used to synchronize, too. The basic mechanism involved is a 'suspending' wait action. To suspend means in this context, that a process becomes desactivated until the message arrives, for which it is waiting.

For example, a computation that requires the results of three parallel sub-computations has to wait until the results of the sub-computations arrive. The main process will execute three 'receive message' commands and will only continue if all three results are present.

Please note, that it is difficult to express a critical region behaviour using messages and to express a 'join' using semaphores (although there are methods to do so).

Brain Aid Prolog

We chose the CSP modell for the implementation of BAP, but omitted the semaphores and added some different functionality on the Client-Server Layer .

Many attempts have been made to use the 'inherent parallelism' of logic programming languages like PROLOG. New parallel constructs were introduced to modify the way PROLOG programs were executed.

Instead we chose the Communicating Sequential Processes (CSP) model of for our implementation. In this model every PROLOG process strictly uses the control flow as defined in Clocksin and Mellish. Contrary to AND/OR parallelism, multiple control flow or similar concepts a message passing library enables processes to communicate and synchronize.