The LARD Scheduler

This section describes the low-level operation of the LARD scheduler. Most programs interact with the scheduler using higher-level functions such as wait_until, wait_for etc. The low-level mechanism described here is only of interest to those who are writing replacements for or extensions to these high-level functions.

Thread Basics

A concurrent LARD program is made up from a number of threads, each of which is identified by an integer thread id (tid). The scheduler is non-preemptive, that is the currently executing thread will continue to run without interruption until it yields control. At this point the scheduler will activate another thread.

Each thread has a priority, which takes one of the following values:

	PRI_RUN
	PRI_WAIT
	PRI_TIMEADV
	PRI_DEMWAIT
	PRI_SUSP

These priority values are defined as enumeration values of type priority in ctrl.l. PRI_RUN is the highest priority, PRI_SUSP is the lowest priority. When the scheduler is called to select a new thread to run it will choose a thread from the highest priority level that contains any threads. If all threads have priority PRI_SUSP then none is available to be activated and the program terminates with an appropriate message.

Scheduler Control Functions

Access to the scheduler is controlled by a number of functions declared in ctrl.l in the standard library:

mytid returns the tid of the current thread.
setmypriority sets the priority of the current thread (but does not cause it to be descheduled).
setpriority sets the priority of a thread identified by its tid (but does not cause the current thread to be descheduled).
yield causes the current thread to be descheduled and another to be selected in its place. Note that if no thread has a higher priority than the current thread then it is possible that the current thread will be rescheduled.
spawn creates a new thread to evaluate a given expression. The new thread will initially have priority PRI_RUN. spawn returns the tid of the new thread.
running checks to see if a thread identified by its tid still exists. tids are never re-used (up to 2^32 at least).

This basic arangement is sufficient to implement the higher-level concurrency and scheduling mechanisms, including _|_, wait_for etc.

Implementation of `_|_`

_|_ is implemented using priorities PRI_RUN and PRI_SUSP only. Here is an extract from its definition in ctrl.l:

	(S1:expr(void)) | (S2:expr(void)) : expr(void) = (
	  ltid:var(int).
	  rtid:var(int).
	  ptid:var(int).
	
	  ptid:=mytid;
	  ltid:=spawn( (S1;setpriority(ptid,PRI_RUN)) ,forparnum);
	  rtid:=spawn( (S2;setpriority(ptid,PRI_RUN)) ,forparnum);
	
	  repeat (
	    setmypriority(PRI_SUSP);
	    yield
	  ) until ((!running(ltid)) && (!running(rtid)))
	).

This code operates as follows:

Two new threads are spawned to execute the left and right subexpressions.
The parent sets its priority to PRI_SUSP and yields.
The two new threads are considered for execution along with any other threads with priority PRI_RUN. Eventually one will complete evaluation of the subexpression and set the priority of the parent thread to PRI_RUN.
The parent thread will eventually resume execution and will check the status of the new threads. If one thread is still running it will resuspend itself.
In due course both threads will have completed and the parent's repeat_until_ loop will complete, allowing _|_ to return.

The implementation of forpar_do_ is similar.

Implementation of Channel Communication

The channel communication mechanism could operate as follows (and did in previous versions) using wait_until:

	(c:var(chan(Tc:type))) ? (e:expr(Te:type)) : expr(Te) = (
	  r:var(Te).

	  wait_until(c->s);  /* wait until data is present */
	  r:=e;              /* evaluate body */
	  c->s:=false;       /* indicate that data is no longer present */
	  r
	).

	(c:var(chan(Tp:type))) ! (v:val(Tp)) : expr(void) = (
	  c->v:=v;           /* send data */
	  c->s:=true;        /* indicate that data is present */
	  wait_until(!c->s); /* wait until data is no longer present */
	).

However the implementation of wait_until is relatively inefficient since each wait_until condition is re-evaluated each time that anything that does useful work occurs. Since the channel code is extensively used a more optimal implementation is desirable.

The improved implementation using the low-level scheduler functions is as follows:

	(c:var(chan(Tc:type))) ? (e:expr(Te:type)) : expr(Te) = (
	  r:var(Te).

	  if (!c->s) then (
	    c->rtid:=mytid;
	    setmypriority(PRI_SUSP);
	    yield
	  );
	  r:=e;
	  c->s:=false;
	  setpriority(c->stid,PRI_RUN);
	  c->rtid:=0;
	  r
	).

	(c:var(chan(Tp:type))) ! (v:val(Tp)) : expr(void) = (
	  c->v:=v;
	  c->s:=true;
	  if (c->rtid!=0) then setpriority(c->rtid,PRI_RUN);
	  c->stid:=mytid;
	  setmypriority(PRI_SUSP);
	  yield;
	).

The code can operate in two ways. If the sender calls _!_ first:

stid is set to the tid of the sender.
The sender is suspended.
The receiver calls _?_.
The receiver body expression is evaluated.
The sender's priority is set to PRI_RUN.
The sender eventually resumes.

If the receiver calls _?_ first:

rtid is set to the tid of the receiver.
The receiver is suspended.
The sender eventually calls _!_. It sets the receiver's priority to PRI_RUN, stores its tid in stid and suspends itself.
The receiver is eventaully rescheduledand evaluates its body expression. It sets the sender's priority to PRI_RUN allowing the sender to continue.

Implementation of `wait_for`

wait_for is implemented using priority levels PRI_RUN, PRI_TIMEADV and PRI_SUSP. A single process, advance_time, permantently has priority PRI_TIMEADV. Here are extracts from the implementations of wait_for and advance_time:

	wait_for(delay:val(int)) : expr(void) = (
	    target_time : var(int).
	    target_time:=now+delay;
	    regtime(mytid,target_time);
	    setmypriority(PRI_SUSP);
	    yield
	).

	advance_time : expr(void) = (
	  setmypriority(PRI_TIMEADV);
	  forever(
	    yield;
	    now:=nexttime
	  )
	).

regtime and nexttime are calls to C code that maintains a list of threads that are currently waiting for time to advance and their target times. This code is written in C partly for efficiency and partly because LARD doesn't have the necessary data structures to code it easily.

wait_for computes the target time and registers this with regtime. It then sets its priority to PRI_SUSPand yields.

When no thread has priority PRI_RUN, i.e. all threads are waiting, it is safe to advance time. The scheduling algorithm ensures that advance_time will be called at this point. It calls nexttime, which finds the tids of all threads that are waiting for the next timestep and sets their priorities to PRI_RUN. It returns the time at this timestep which is assigned to now.

Implementation of `wait_until`

Because wait_until is more general than the other scheduling mechanisms its implementation is less optimal. Its implementation makes use of the two other priority levels, PRI_WAIT and PRI_DEMWAIT.

Here is an extract from the implementation of wait_until in ctrl.l:

	wait_until(e:expr(bool)) : expr(void) = (
	  while !e do (
	    setmypriority(PRI_DEMWAIT);
	    yield
	  );
	  promote_waits;
	  setmypriority(PRI_RUN)
	).

If evaluating the expression returns false the thread sets its priority to PRI_DEMWAIT and yields. Threads with priority PRI_DEMWAIT will essentially never get scheduled.

Whenever any "useful work" gets done, something may have changed causing a wait condition to evaluate to true. To allow the waits conditions to be reevaluated function promote_waits is called. This changes the priority of all threads with priority PRI_DEMWAIT to PRI_WAIT. Calls to promote_waits are found in the implementation of advance_time and wait_until (and maybe there should also be some in channels.l, but there aren't, and this needs investigating!!!).