Handling Cooperating Tasks
Many problems to be solved concurrently require that the several tasks communicate with each other so that certain operations may be synchronized. One famous example of need for such communication is the prodducer/consumer problem that arises when producer and consumer tasks both need access to the same memory location.
The producer's task is to place information into the memory location for use. The producer is supplying this information one record at a time and the consumer using it one record at a time. The difficulty arises because the memory location holds only a record. If the producer attempts to supply records faster than they are accepted by the consumer, or if the consumer attempts to access them faster than supplied by the producer, chaos reigns. This is a simplified version of a very common problem: Consider a text editor -- data is not able to be until read into a buffer from the disk.
The solution is to synchronize the two through an interprocess mechanism. Many such mechanisms have been developed. Here we will choose to use semaphores (see Fundamentals of Programming Languages) due to their simplicity. A semaphore is a global two-valued variable together with two operations: wait and signal. These operations are described in pseudocode in Figure 2. A wait operation essentially places a task in sleeping status until a signal operations occurs (in another task) to wake it up. Note that during the signal and wait operations, we must be careful task switching does not occur, or the semaphore variables mahy be modified incorrectly.
Figure 2: The Semaphore Functions
<b>WAIT</b><br> - Input: a semaphore name<br> Output: none<br> - if semaphore's value = 1,<br> then<br> - set value to 0<br> - return<br> else<br> - remove this task from ready list<br> - place this task in the queue waiting upon this semaphore<br> - switch to another task<br> <b>SIGNAL</b><br> - Input: a semaphore name<br> Output: none<br> - if there are processes waiting upon this semaphore,<br> then<br> - remove one from the queue and add it to the ready list<br> - returnu else<br> - set the semaphore's value = 1<br>
In the producer/consumer problem, one semaphore is used to specify that the buffer is full and the consumer needs to retrieve it. Figure 3 gives the pseudocode for implementing this producer/consumer solution.
Figure 3: CLI LISP Synchronized Producer and Consumer Tasks
<b>PRODUCER - CONSUMER</b> - empty the buffer - create a list of information for the example (could be read in) - initialize the semaphores ($ok-to-produce $ok-to-consume) - start the concurrent producer and consumer tasks <b>PRODUCER</b> - repeat until the information is exhausted - wait until the buffer is empty (using semaphore $ok-to-produce) (this suspends PRODUCER) - fill the buffer - signal that the buffer is full (using semaphore $ok-to-consume) (this wakes up CONSUMER) <b>CONSUMER</b> - repeat until the information is exhausted - wait until the buffer is full (using semaphore $ok-to-consume) (this suspends CONSUMER) - access the buffer - signal that the buffer is empty (using semaphore $ok-to-produce) (this wakes up PRODUCER)
Figure 4 illustrates the importance of such synchronization. In Figure 4A, we have concurrent producer and consumer task synchronization; Figure 4B shows teh relevance of such synchronization by removing the semaphores.
Figure 4: The importance of synchronization.
<b>(A)</b> * (pc) READ-BY-PRODUCER<--- THIS ----PRINT-BY-CONSUMER---> THIS READ-BY-PRODUCER<--- IS ----PRINT-BY-CONSUMER---> IS READ-BY-PRODUCER<--- A ----PRINT-BY-CONSUMER---> A READ-BY-PRODUCER<--- TEST ----PRINT-BY-CONSUMER---> TEST READ-BY-PRODUCER<--- OF ----PRINT-BY-CONSUMER---> OF READ-BY-PRODUCER<--- SEMAPHORES END-PRODUCER ----PRINT-BY-CONSUMER---> SEMAPHORES END-CONSUMER (END-PRODUCER END-CONSUMER) * <b>(B)</b> * (un-pc) READ-BY-PRODUCER<---A READ-BY-PRODUCER<--- TEST READ-BY-PRODUCER<--- OF READ-BY-PRODUCER<--- ----PRINT-BY-CONSUMER---> SEMAPHORES SEMAPHORES ----PRINT-BY-CONSUMER---> NIL END-PRODUCER ---PRINT-BY-CONSUMER--->NIL ----PRINT-BY-CONSUMER---> NIL ----PRINT-BY-CONSUMER---> NIL ----PRINT-BY-CONSUMER---> NIL END-CONSUMER (END-PRODUCER END-CONSUMER)
Suggestions for Future Work
The concurrent LISP interpreter presented here provides a vehicle for exploration of the burgeoning area of multiprocessor parallel programming.
The major deficiency in the present implementation is the lack of memory space available to handle the stack-groups. Common LISP is a large program leaving little room for concurrent tasks. Moving to a larger memory space would allow the fully recursive implementation of concurrency. This may readily be accomplished by using bindings to give local rather than global values to stack-group variables. A longer-term goal would be to allow the LISP interpreter itself to decide which forms might profitably be executed in parallel instead of having to use cobegin explicitly. This is quite feasible in a purely functionallcinguage such as pure LISP but becomes difficult when we allow global variables.
References
Allen,J. Anatomy of LISP. McGraw-Hill, 1978.
Ben-Ari, M. Principles of Concurrent Programming. Prentice-Hall,1982.
Horowitz, E. Fundamentals of Programming Languages. Computer Science Press, 1984.
Courtesy AI Expert