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


Ulm's Coroutine Scheme


Andreas Borchert, University of Ulm, SAI, Helmholtzstr. 18, D-89069 Ulm

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);
NEWPROCESS creates a new coroutine with a stack starting at addr with size size. The coroutine starts execution by calling the parameterless global procedure proc. A handle to the new coroutine is returned in new.

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;
Each new coroutine is started just after creation to allow parameter copying. After getting parameters the coroutines transfer immediately back because the rest of the coroutine typically requires the existence of the other coroutines.

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:

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);
and an interface module Coroutines (see below).

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;
CRSPAWN performs following steps:

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.


Author: borchert, last change: 1994/02/15, revision: 1.2, converted to HTML: 1997/05/05

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