Synchronization of Asynchronous Processes in-CSP
RAJIVE BAGRODIA University of California at Los Angeles
Many concurrent programming languages including CSP and Ada use synchronous message-passing to define communication between a pair of asynchronous processes. Suggested primitives like the generalized alternative command for CSP and the symmetric select statement for Ada allow a process to nondeterministically select one of several communication statements for execution. The communication statement may be either an input or an output statement. We propose a simple algorithm to implement the generalized alternative command and show that it uses fewer messages than existing algorithms. Categories and Subject Descriptors: D.3.3 [Programming Languages]: Language ConstructsD.4.1 [Operating Systems]: Process Management-synchroconcurrent programming structures; nization; D.4.4 [Operating Systems]: Communications Management-input/ou&ut, message sending; D.4.7 [Operating Systems]: Organization and Design-distributed systems General Terms: Algorithms, Design, Languages output guards,
Additional Key Words and Phrases: CSP, guarded commands, nondeterminism, parallel programming, process communication, symmetric select statements
1. INTRODUCTION Many concurrent programming languages [l, 131 use synchronous messagepassing for communication between a pair of concurrent, asynchronous processes. In synchronous message-passing, the sender and receiver must both be ready to communicate for a communication between them to occur; we refer to the above form of communication as a binary rendezuous. The generalized alternative command  allows a process to select one of several binary rendezvous for execution. A number of algorithms [6, 7, 16, 17, 201 have been designed to implement the above command for a group of concurrently executing processes. Buckley and Silberschatz  present four criteria to determine the “effectiveness” of algorithms that implement this...