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:

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:

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:

If the receiver calls _?_ first:

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!!!).