Concurrency Proposal

[Levi Pearson]

Here's the design I've been working on for an implementation of low-
level concurrency support in the vm.  Please let me know if you see
any design flaws or find the description unclear in any aspect.  I
hope to contribute to the implementation, but my time for hacking is
limited so it'd be nice if others wanted to work on implementing it
as well.

This provides only the lowest-level of support for preemptive thread
switching; lots of userspace code design is left to be done.



VM-Level Support for Concurrency in Slate
=========================================

In order to support preemptive multithreading, the Slate virtual
machine requires a few modifications.  This document proposes an
interrupt-based system to integrate threading and i/o systems
together.  This will allow for an efficient low-level mechanism in the
virtual machine and flexible abstractions in userland.


Basic Theory of Operation
-------------------------

At the vm level, a series of interrupts will be introduced.  One will
signal a timer alarm, one will signal i/o completions, and another
will signal i/o errors.  While the current thread's Interpreter is
executing its interpret method, it will check the state of the active
(unmasked) interrupts.  When one is set, it will cause the thread to
yield to the thread that has asked to handle that interrupt.  When the
interrupt is handled, execution will resume with the interrupted
thread.

The timer interrupts will be used to yield control to the scheduler
thread, which will be responsible for choosing which thread to yield
control back to.  Policy for this will be entirely in userspace code,
as will handling sleeping and i/o-blocked threads.  The i/o-blocked
thread handling will require communication between the scheduler
thread and the i/o-completion and i/o-error handling threads.  When
the scheduler thread determines that no threads are ready to run, it
may ask the vm to put it to sleep until an i/o event occurs or a
thread is due to wake.

I/o interrupts will yield control to the threads that have asked to
handle them.  They will be given information about which operations
have completed and which have errored when the vm wakes them, and they
are then responsible to communicate this information to the scheduler
and wait for another interrupt.  As they register again to receive the
interrupt, they yield to the interrupted thread.

Implementation
--------------

Some OS-specific functions will need to be created to handle the
low-level details of timer scheduling and i/o multiplexing.  The
interface will occur through three functions, schedule_alarm,
get_next_event, and wait_for_event; and a global variable, pending_events.

schedule_alarm(time): Trigger an alarm interrupt in time milliseconds.

get_next_event(): If an alarm has been set via schedule_alarm() and it
is past its time, return a value representing an alarm event.  If
there is an i/o operation pending, return a value representing the
proper i/o event. If there are no events pending, clear pending_events.

wait_for_event(time): Stops the OS-specific alarm signals and calls an
OS-specific function to wait for an i/o event, with a timeout of time
milliseconds.  When it returns, if there are any i/o ports ready, set
pending_events. Start the OS-specific alarm signals again.

A new object will be added to the vm called Executor.  Its execute
method will be the new entry point in boot.c to replace the current
call to Interpreter interpret.  It will contain slots to keep track of
interruptHandlers, enabledInterrupts, pendingInterrupts,
currentThreads, and interruptFlag.   It will have the methods processEvents,
areInterruptsPending, and handleInterrupt associated with it as well.

slot interruptHandlers: An array of Interpreter objects that are
currently registered to handle the associated interrupts

slot enabledInterrupts: A bitmask representing currently enabled
interrupts

slot pendingInterrupts: A bitfield representing current interrupts
awaiting handling

slot currentThreads: A list of Interpreter objects associated with
their ids

method processEvents: This method loops calling get_next_event(),
adding the interrupt flag associated with each each event to
pendingInterrupts.

method areInterruptsPending: This method checks pending_events, and if
it is set, clears it and calls processEvents.  If pendingInterrupts
bitwise-and enabledInterrutps = 0, clear interruptFlag and return
false, otherwise return true

method handleInterrupt: This method is called from the current
Interpreter if it finds interrupts are pending.  It gets the highest
priority enabled interrupt, finds the handler thread for that
interrupt, pushes interrupt info onto its stack, and yields to it.
The interrupt info includes the id of the current thread (so it can be
yielded to when finished) and interrupt-specific information

method execute: This method is called by the bootstrap startup
function.  It loops indefinitely, calling interpret on the current
active Interpreter.  An Interpreter may yield to another thread by
returning a thread id.  The Executor then changes the current
Interpreter to the one whose id corresponds to the one returned and
loops.

The Interpreter object will need some changes as well, including some
new opcodes.

op waitForInterrupt: interrupt yieldingTo: thread id
  register this thread as the handler for the given interrupt (not
  timer interrupt) and return from Interpreter with the given thread
  id so that the Executor switches to that thread.

op yieldTo: thread id
  Return from Interpreter with the given thread id so the Executor
  switches to that thread.

op waitForTimerYieldingTo: thread id withTime: time
  Registers this thread to recieve a timer interrupt in time
  milliseconds and returns from Interpreter with the given thread id
  so that the Executor switches to that thread.

op wait: time
  If there are no pending interrupts, call wait_for_events(time)

Unix-specific Details
---------------------

To implement timers without excessive system-call overhead, a handler
can be registered for SIGALRM and setitimer() can be used to schedule
periodic triggering of the handler.  An initialization function should
register the sigalrm_handler as the SIGALRM handler and clear the
sigalrm_count global variable.  Functions should be provided,
start_sigalrm_signals and stop_sigalrm_signals, in order to disable
the signaling during calls to select().

global var sigalrm_count

func sigalrm_handler(): Increment sigalrm_count.  If an alarm is set
and the sigalrm_count is >= the alarm time (in sigalrm intervals) set
pending_events.  If sigalrm_count is >= time for an i/o check, do one
and set pending_events if there is an i/o event ready.

func start_sigalrm_signals(): Call setitimer() to send SIGALRM at 20 per
second

func stop_sigalrm_signals(): Call setitimer() to stop SIGALRMs

In addition, there needs to be some infrastructure around select() to
keep track of pending i/o events, moving ready ones to a ready list
and errored ones to an errored list.  This should be used by
wait_for_event() and sigalrm_handler() when i/o checking intervals are
reached.

Other OS Details
----------------

The Unix-specific things should have reasonable alternatives in other
OSes.  See the Scheme48 vm for ideas regarding Windows support.