Oberon || Compiler & Tools || Library || Module Index || Search Engine

Ulm's Coroutine Scheme

Introduction

A simple and powerful coroutine scheme has been offered in Modula-2 by N. Wirth. The two basic operations (exported by the SYSTEM module) of Modula-2 are:

PROCEDURE NEWPROCESS(proc: PROC;
                     addr: ADDRESS; size: CARDINAL;
                     VAR new: ADDRESS);
PROCEDURE TRANSFER(VAR source, destination: ADDRESS);

The first disadvantage of NEWPROCESS is that coroutines must be parameterized by use of global variables. This leads to following typical layout:

VAR (* global variables *)
   crparams: CoroutineParameters;
   source: ADDRESS; (* current coroutine is called by this one *)
   newcr: ADDRESS; (* coroutine just created by NEWPROCESS *)

PROCEDURE Coroutine;
   VAR
      myparams: CoroutineParameters;
BEGIN
   (* copy parameters and return to calling coroutine *)
   myparams := crparams;
   TRANSFER(newcr, source);
   (* rest of coroutine *)
END Coroutine;

PROCEDURE SetupCoroutine(params: CoroutineParameters; proc: PROC);
   (* create coroutine and pass parameters *)
BEGIN
   NEWPROCESS(proc, addr, size, newcr);
   crparams := params;
   TRANSFER(source, newcr);
END SetupCoroutine;

NEWPROCESS and TRANSFER are found in nearly every Modula-2 implementation and seem to be thus very portable at first sight. Nevertheless, the stack size required by the coroutine (parameter size of NEWPROCESS) is very implementation dependent.

TRANSFER has two variable parameters: source and destination. This allows two ways of allocating coroutine structures:

• the address pointing to the coroutine structure remains constant (e.g. coroutine structure is at beginning of the stack).
• the coroutine structure is allocated at time of coroutine suspension (call of TRANSFER); e.g. at top of stack.

A special case is introduced by the main coroutine. The main coroutine is implicitly created during runtime start-off. The pointer to the coroutine structure of the main coroutine is set by the first TRANSFER operation. Thus, the source parameter is not an input parameter at least for the first TRANSFER-operation. This requires either the second case or the use of a prior invisible pointer to the coroutine structure of the main coroutine. Consequently, the source parameter can be omitted if at least the pointer to the main coroutine becomes visible.

The second case invalidates copies of earlier coroutine pointers as illustrated by following example:

VAR
   main, newcr: ADDRESS;

PROCEDURE Coroutine;
   VAR
      cr: ADDRESS;
BEGIN
   TRANSFER(cr, main);
   (* ... *)
END Coroutine;

PROCEDURE Setup;
BEGIN
   NEWPROCESS(Coroutine, addr, size, newcr);
   TRANSFER(main, newcr);
   (* newcr is no longer valid *)
END Setup;

Ulm's Coroutine Primitives

NEWPROCESS and TRANSFER have been replaced by

PROCEDURE CRSPAWN(VAR newcr: COROUTINE);

PROCEDURE CRSWITCH(dest: COROUTINE);

The main change is that coroutines declare themselves to be coroutines as illustrated by following example:

PROCEDURE Coroutine(myparams: CoroutineParameters;
                    VAR newcr: SYSTEM.COROUTINE);
BEGIN
   (* start as normal procedure *)
   SYSTEM.CRSPAWN(newcr); (* return to Setup *)
   (* execution continues here after CRSWITCH(newcr) *)
END Coroutine;

PROCEDURE Setup;
   VAR
      cr: SYSTEM.COROUTINE;
BEGIN
   Coroutine(crparams, cr);
   (* ... *)
END Setup;

• Creation of a new stack.
  The initial stack size is determined by the size of the activation record of the calling procedure and a default value taken from Coroutines.defaultsize. An optional second parameter of CRSPAWN allows to specify the initial stack size. Note that the current storage management system allows coroutine stacks to grow dynamically.
• The coroutine structure is allocated at the beginning of the new stack and initialized.
  The coroutine structure contains information about the stack management registers (pointers to the activation record) and the program counter of the coroutine. The program counter of the coroutine is set to the instruction after the call of CRSPAWN.
• The activation record (parameters and local variables) of the procedure calling CRSPAWN is copied to the new stack.
• Immediate return to the calling procedure. Thus, the coroutine procedure must not be a function.

CRSPAWN returns like CRSWITCH if the newly created coroutine resumes execution.

Only a destination parameter is needed for CRSWITCH because the pointer to the coroutine (of type COROUTINE) does not change.

The pointer to the main coroutine is initialized during runtime start-off in the system interface module Coroutines:

DEFINITION Coroutines;

   (* run time interface to coroutines *)

   IMPORT SYS := SYSTEM;

   TYPE
      Coroutine = SYS.COROUTINE;

      CoroutineTag = POINTER TO CoroutineTagRec;
      CoroutineTagRec = RECORD END;

   VAR
      defaultsize: LONGINT;
         (* default initial stack size of a coroutine,
            the size of the activation record of the procedure
            calling CRSPAWN is added to the default;
            the default is taken if the second parameter of CRSPAWN
            is omitted
         *)
      tag: CoroutineTag; (* used for all coroutines *)

      main: Coroutine;
         (* is allocated during initialisation of this module
            and points to the main coroutine
         *)

      source: Coroutine;
         (* the last CRSWITCH operation was executed by this coroutine *)

      current: Coroutine;
         (* coroutine currently active *)

END Coroutines.

An Example: Simple Producer/Consumer Problem

PROCEDURE Produce(VAR newtoken: Token;
                  VAR producer, consumer: Coroutines.Coroutine);
   VAR
      token: Token;
BEGIN
   SYSTEM.CRSPAWN(producer);
   LOOP
      (* produce token *)
      newtoken := token;
      SYSTEM.CRSWITCH(consumer);
   END;
END Produce;

PROCEDURE Consume(VAR newtoken: Token;
                  VAR producer, consumer: Coroutines.Coroutine);
  VAR
     token: Token;
BEGIN
   SYSTEM.CRSPAWN(consumer);
   LOOP
      token := newtoken;
      (* consume token *)
      SYSTEM.CRSWITCH(producer);
   END;
END Consume;

PROCEDURE Setup;
   VAR
      token: Token;
      producer, consumer: Coroutines.Coroutine;
BEGIN
   Produce(token, producer, consumer);
   Consume(token, producer, consumer);
   SYSTEM.CRSWITCH(producer);
END Setup;

Further Hints

Ulm's Oberon library offers a couple of abstractions which base on coroutines. Tasks introduces the notion of tasks, task groups and schedulers. Each task group is controlled by a scheduler which is member of another task group. Task groups and schedulers form a tree with the main task as root.

Tasks need not to know about other coroutines and how to call CRSWITCH. Instead, they may tell what they are waiting for by the use of conditions, an abstraction offered by Conditions. Specific condition types are exported by StreamConditions, TimeConditions, EventConditions, Semaphores and other modules.

Usually, schedulers follow the standard scheduler interface of Schedulers which allows to add tasks dynamically. A simple round robin scheduler without priorities is exported by RoundRobin. A first task group which is managed by a round robin scheduler is created by the default implementation of SysModules.

Oberon || Compiler & Tools || Library || Module Index || Search Engine