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:
- Evaluate a stack-group until it is time to switch to a new task.
- Put the present stack-group into suspended status.
- Choose a new stack-group (task).
- 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
- 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.
