CSP(ID:795/csp001)Communicating Sequential Processesfor Communicating Sequential Processes. Hoare, Oxford, 1978. A notation for concurrency based on synchronous message passing and selective communications. cobegin/coend. People: Structures: Related languages
References: in [ACM] CACM 21(08) (August 1978). view details in [ACM] JACM 25(03)March 1978 view details in [ACM] JACM 25(03)March 1978 view details in TOPLAS 2(3) July 1980 view details in TOPLAS 2(3) July 1980 view details in TOPLAS 2(3) July 1980 view details in TOPLAS 2(3) July 1980 view details External link: Online copy in TOPLAS 2(3) July 1980 view details External link: Online copy in TOPLAS 2(3) July 1980 view details These models differ in the underlying structure of their observations which influences both the number of representable language operators and the notion of correctness expressed by P sat S. Safety properties are treated by all models; the more sophisticated models also permit proofs of liveness properties. An important feature of the models in a special hiding operator which abstracts from internal process activity. This allows large processes to be composed hierarchically from networks of smaller ones in such a way that proofs of the whole are constructed from proofs of its components. We also show consistency of the denotational models w.r.t. a simple operational semantics based on transitions which make internal process activity explicit. External link: Online copy in TOPLAS 2(3) July 1980 view details Guarded Communicating Processes is a complete language for distributed applications based on Hoare's CSP. CSP are an "ambitious attempt to find a single simple solution" to the communication and synchronization problems of concurrent processes, that is to represent in a single frame semaphores, critical regions, monitors, queues and so on. They are characterized by some choices: . synchronous communication, via the two basic communication primitives: the input command, whose syntax is . no shared data among processes . non determinism, through the embedding of the communication primitives in the Dijkstra's guarded commands. The CSP is becoming more relevant not because of optimization purposes (optimization is for Peter Wegner an issue of smart compilers and it is related to the ratio between logical concurrency and physical concurrency), but because their dealing concurrent systems through the notion of communicating state machine components is a simple and conceptually powerful kind of process abstraction. The technology development itself, for instance the IAN technology supporting an increasing number of distributed applications in the office automation and process control areas applications and, consequently, requiring highly distributed languages, made the CSP a considerable point of reference in the development of languages for implementing such applications. CSP have therefore been widely discussed in the computer science community from the semantics point of view and have inspired other programming language as ADA (for what concerns the extended rendezvous mechanism), and, more recently, OCCAM. A number of experimental implementations and communication algorithms, have been presented in the literature since 1978, but very rarely they can be actually used for distributed applications.In fact, the proposed languages concentrate mainly on the communicating mechanism, ignoring all the other necessary features that make a language actually usable. Furthermore, very often the implementations were simulations on a single processor of a distributed application: that means that little consideration was given to the performance issues within network. The GCP language (Guarded Communicating Processes language: the name is still provisional) has been defined, deriving its control mechanisms from the Hoare's CSP and embedding them in a fully defined concurrent programming language. in TOPLAS 2(3) July 1980 view details in TOPLAS 2(3) July 1980 view details This paper surveys the languages which have resulted from his proposal and discusses three of these languages. in The Computer Journal 29(6) 1986 view details Communicating Sequential Processes By 1978, there were many proposed methods in use for communication and synchronization in the context of programming multiprocessors. Shared memory was the most common communication mechanism, and semaphores, critical regions, and monitors were among the synchronization mechanisms. C. A. R. Hoare addressed both issues with a single language primitive: synchronous communication. In Hoare's CSP language, processes communicate by sending or receiving values from named unbuffered channels. Since the channels are unbuffered, the send operation blocks until the value has been transferred to a receiver, thus providing a mechanism for synchronization. One of Hoare's examples is that of reformatting 80-column cards for printing on a 125-column printer. In his solution, one process reads a card at a time, sending the disassembled contents character by character to a second process. This second process assembles groups of 125 characters, sending the groups to the line printer. This sounds trivial, but in the absence of buffered I/O libraries, the necessary bookkeeping involved in a single-process solution is onerous. In fact, buffered I/O libraries are really just encapsulations of these two sorts of processes that export the single-character communication interface. As another example, which Hoare credits to Doug McIlroy, consider the generation of all primes less than a thousand. The sieve of Eratosthenes can be simulated by a pipeline of processes executing the following pseudocode: p = get a number from left neighbor print p loop: n = get a number from left neighbor if (p does not divide n) send n to right neighbor A generating process can feed the numbers 2, 3, 4, ..., 1000 into the left end of the pipeline: the first process in the line eliminates the multiples of 2, the second eliminates the multiples of 3, the third eliminates the multiples of 5, and so on: The linear pipeline nature of the examples thus far is misrepresentative of the general nature of CSP, but even restricted to linear pipelines, the model is quite powerful. The power has been forcefully demonstrated by the success of the filter-and-pipeline approach for which the Unix operating system is well known [2] Indeed, pipelines predate Hoare's paper. In an internal Bell Labs memo dated October 11, 1964, Doug McIlroy was toying with ideas that would become Unix pipelines: "We should have some ways of coupling programs like garden hose--screw in another segment when it becomes necessary to massage data in another way. This is the way of IO also.'' [3] Hoare's communicating processes are more general than Unix shell pipelines, since they can be connected in arbitrary patterns. In fact, Hoare gives as an example a 3x3 matrix of processes somewhat like the prime sieve that can be used to multiply a vector by a 3x3 square matrix. in The Computer Journal 29(6) 1986 view details |