Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Parallel

Multitasking for Common LISP


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.

Programming in Common LISP. John Wiley & Sons, 1985.

Horowitz, E. Fundamentals of Programming Languages. Computer Science Press, 1984.

Courtesy AI Expert


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.