Channels ▼
RSS

Parallel

Multitasking for Common LISP


Design Criteria

In order to simulate true concurrency on a single processor system, our interpreter must allow for switching between tasks. In other words, we execute a single task for a (short) perdio of time, then switch between tasks randomly. In this way, our concurret tasks can assume an order of execution, just as tasks run on separate processors run independently. The two features the interpreter must have in order to handle this task switching are knowledge of the state of computation of each task and a task switching mechanism.

The state of computation of each task is defined by knowledge of all variable bindings and the current evalution state. A symbol (atom) in LISP has four associated properties:

  • A (possibly empty) stack of bindings.
  • A value.
  • A function definition.
  • A property list.

The last three properties are known globally so they have the same values across concurrent tasks. The stack of bindings represents locally assigned values. Such values disappear when the defining environment is left. Bindings are unique to the defining function so they are not carried across tasks. Our concurrent interpreter must remember the correct bindings for each task independently.

The current evaluation state consists of information as execution address, register contents, etc., and is essentially the information required whenever a subprogram is made in any language. This information is unique for each task, must be retained as we switch between tasks so that a task may be resumed precisely where it suspended.

The second fetaure required is the ability to randomly switch between the tasks. In other words, at the end of a given quantum of processor time, we wish to suspend the task currently executing and to begin execution of a randomly selected task. This process continues until all tasks have finished execution. Note that if we did not require this randomly interleaved capability, concurrent programming would reduce to sequential evaluation of a list of forms, which may be trivially implemented in LISP.

Three schemes present themselves for providing task switching. The first would be, to depend upon an external interrupt, presumably from a hardware clock, to cause the interpreter to switch. The difficulty is that we do not wish to interrupt LISP primitive operations or we would quickly corrupt the system. In addition, writing an interrupt routine that would work gracefully with an existent LISP interpreter is a large undertaking.

A second scheme is to implement a complete LISP interpreter extended to include the concurrent capability. This type of interpreter might even be written in LISP (see Programming in Common LISP for such an interpreter but without concurrency). This interpreter could monitor the number of calls to itself and gracefully switch tasks as desired. But the interpreter requires a large amount of system memory, which is already tight.

The third scheme, adopted here, is to define a new eval procedure on top of the sYstern's eval. In this way, all function evaluation must pass through our eval routine, which can count the number of calls to itself and switch tasks at appropriate intervals. However, some evaluations are not switchable (those that handle the actual task switching, for example), so we must allow for the ability to turn off switching as desired.

Concurrent Interpreter in LISP

We need to represent each concurrent task by an object that allows us to retain complete knowledge of the evaluation state of the task toge3ther with a list of applicable bindings. We also must be able to pick up this object, evaluate it for a period of time, suspend its evaluation so that we may evaluate another task, and later resume the original task.

Common LISP has exactly the object required: a stack-group. Stack-groups are functional objects with the attributes of a task. (Stack-groups are not a feature of Common LISP -- they are copied from Zeta LISP.) Stack-groups contain exactly the, information needed to implement a concurrent interpreter. A single stack-group is the LISP equivalent of a single task.

It is possible to initiate a stack-group (remember they have the attributes of a task), suspend a stack-group, and then resume it. Thus our switching algorithm consists of:

  1. Evaluate a stack-group until it is time to switch to a new task.
  2. Put the present stack-group into suspended status.
  3. Choose a new stack-group (task).
  4. Execute this new stack-group.

Implementation of the interpreter requires three major new routines:

  • An initialization function that creates the stack-groups and begins concurrent execution.
  • An evaluation function to ride on top of the system's eval, which will handle both form evaluation and groups initiation of task switching if appropriate;
  • A function to choose and begin execution of the next task.

In CLI, these three functions exactly are cobegin, cli_eval, and switch-around, respectively. They are described in Figure 1.


Figure 1: Routines cobegin, cli_eval, and switch-around are the heart of the interpreter.


<b>COBEGIN</b>
     - Input:   the forms to be evaluated concurrently (the tasks)
       Output:  a list of the values to these forms
     - initialize pseudo clock used to switch between tasks
     - create a stack group for each concurrent task
     - initiate concurrent execution
     - create a list of the values of the tasks

<b>CLI_EVAL</b>
     - Input:   a form to be evaluated
       Output:  the value of the form
     - increment pseudo clock
     - if switching is enabled
          and we have reached the end of a time slice
          and we are in concurrent mode,
       then
         - suspend current task and enable switching
       else
         - evaluate the form
         - return the value

<b>SWITCH-AROUND</b>
     - Input:   none
       Output:  none
     - if all tasks are complete,
       then
         - return
       else
         - randomly choose a task to execute
         - if this task has completed,
           then
             - eliminate it from the list of tasks
             - try again
           else
             - initiate task execution


Let's discuss each routine briefly. Keep in mind these key facts:

  • A stack-group is initiated and/or resumed by needed to calling it as a function.
  • A stack-group is suspended by executing the stack-group-return function.
  • A is suspended, control i returned to the pomint at which the stack-group was resumed (always function switch-around).
  • Evaluation of every form, whether directly named or subsidiary, always passes through cli_eval.

Cobegin is the only function of the three directly called by the user. The main purpose of this function is to create a stack-group for each input form (the tasks to be executed concurrently) and to begin concurrent execution by calling switch-around. Each stack-group is initialized to call upon cli_eval to evaluate its form.

In order to implement cli_eval, we use the Common LISP function evalhook. Evalhook takes as arguments the to evalutate this form (cli_eval). Attempting to evaluate the input form will typically cause evaluation of a number of subsidiary forms, and for each of these cli_eval will be used. However, the standard eval is used for the final evaluation of itself. It is this bypassing of cli_eval that enables us to use the standard eval for all function evaluations because each subsidary form will eventually be evaluated directly by a call to cli_eval. The primary purposes of cli_eval are to initiate switching between, if necessary, evaluate the form, and return a value.

Switch-around handles choosing the next task to execute and then resuming the execution of this task by calling the task's stack-group as a function (using funcall). Note that this means that when a stack-group issuspended, control returns to the form following this fun-call -- which is a recursive call to switch-around to choose a new task. Switch-around also handles deleting completed tasks (their stack-groups will be exhausted).

These three functions, consisting of about 70 lines of LISP code including subsidieary routines, implement concurrency in Common LISP. This ability is a real testimonial to both the power and elegance of LISP and the importance of including such powerful primitives as stack-groups.


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.
 

Video