Co_Routines Support for Oberon

[Dmitry Dagaev]

This topic deals with Co_ subsystem: Co_Routines cross-platform support for Oberon.

It was developed in 2014 and has public domain licence.
The CPC version for BlackBox is http://www.zinnamturm.eu/downloadsAC.htm#Co_.
The cross-platform collection is http://sourceforge.net/projects/ta1/files/co2.0/. (co-v2.0-all.zip)

Basically, Co_ subsystem is implement in Oberon style and supports following platforms:

BlackBox for Windows, which is based on Windows Fibers coroutines implementation

BlackBox for Linux, based on unix contexts (makecontext, swapcontext)

XDS for Windows, based on Modula2 COROUTINES

XDS for Linux, based on Modula2 COROUTINES

Ofront for Windows/Linux (not published)

It has no Kernel support yet, so pointers in coroutines are not examined by garbage collector.

Co_ subsystem supports 2 types of coroutines (classification taken from http://wiki.c2.com/?CoRoutine):

1.Anonymous coroutines - used by Scheduler for Cooperative Multitasking

2.Directed Coroutines - called as subroutines by stack discipline

Co_ package consists of following modules with comprehensive examples:

Co_Tasks - Task for Cooperative Multitasking and base module for Co_Routines

Co_Routines - Implementation itself

Co_ScheadTasks - scheduler for Cooperative Multitasking

ObxSameFringe - Same Fringe problem example (directed coroutine)

ObxMJackson - Michael Jackson's methology for inverted programming - grep example (directed coroutine)

ObxShakespeare - Othello play scheduler

ObxAction - background task Co_Routines-based implementation

ObxTActions - background task Tasks-based implementation

ObxPhilosophers - Dining Philosophers multitasking problem with semaphores

ObxProducerConsumer - Producers and Consumers multitasking

ObxReadersWriters

In this branch I'll concern several issues about coroutines I met during the latter period.

[Dmitry Dagaev]

types.png

Basic types for tools

(9.41 KiB) Not downloaded yet

Types of Tools.
Co_Tasks module introduce the basic types for tools, providing pseudo-parallel execution. In is derived from C.Szyperski "Insight-EthOS" where the relations between entities below were defined (Fig: types.png).

Task is the most lightweight form, Coroutine contains stack information. Preemptive forms are not considered here. In order to implement multitasking, Scheduler (Co_SchedTasks) is purposed.

[Dmitry Dagaev]

Types of Co_Routines (More about types http://www.softpanorama.org/Lang/Asmorama/coroutines_in_assembler.shtml).
Either of technologies used perform context switching.
Cocall instruction directs control to other Co_Routine. We use Transfer command to cocall. In the Fig: co3.png we see cocalls between processes.
Process1(transfer)->Process2(transfer)->Process3(transfer)->Process1
1.In case of Anonymous Co_Routines there is no problem, there is just control transfer to other. In case of Cooperative Multitasking - to unknown other, caused by Scheduler. Transfer in this model takes no arguments--there is no meaningful way to send data to the next context to run, because it is not known which context it will be!
2.Directed coroutines transfer to definite other and inputs/outputs data from on return.
But here is a problem, when you (Process1) pass data for Process2, but control returns from Process3!

Directed coroutines must have semantics similar to subroutines. Example on nested subroutines:

Code: Select all

PROCEDURE c(x: INTEGER; VAR y: INTEGER);
BEGIN
    y := x+3
END c;

PROCEDURE b(x: INTEGER; VAR y: INTEGER);
    VAR z: INTEGER;
BEGIN
    c(x, z);
    y := z+2
END b;

PROCEDURE a;
    VAR y: INTEGER;
BEGIN
    b(0, y);
    Log.Int(y)
END a;


We assume a(call)->b(call)->c(return)->b(return)->a.
And we ensure the result is 5.

We can try coroutines techniques for this example (very simplified example)

Code: Select all

PROCEDURE c(x: INTEGER; VAR y: INTEGER);
BEGIN
    c.y := c.x+3;
    Co.Transfer(a);
END c;

PROCEDURE b(x: INTEGER; VAR y: INTEGER);
    VAR z: INTEGER;
BEGIN
    c.x := x;
    Co.Transfer(c);
    z := c.y;
    b.y := z+2
END b;

PROCEDURE a;
    VAR y: INTEGER;
BEGIN
    b.x := 0;
    Co.Transfer(b);
    y := b.y;
    Log.Int(y)
END a;


I deliberately made an error, corresponding to co3.png: it must be Co.Transfer(b) from PROCEDURE c.
But can anybody predict the result of such loss of flow control?

The Co_Routines system has assurance for flow control in programs with Yield routine and reentrance protection.

Code: Select all

PROCEDURE c(x: INTEGER; VAR y: INTEGER);
BEGIN
    c.y := c.x+3;
    Co.Yield;
END c;

PROCEDURE b(x: INTEGER; VAR y: INTEGER);
    VAR z: INTEGER;
BEGIN
    c.x := x;
    Co.Transfer(c);
    z := c.y;
    b.y := z+2;
    Co.Yield
END b;

PROCEDURE a;
    VAR y: INTEGER;
BEGIN
    b.x := 0;
    Co.Transfer(b);
    y := b.y;
    Log.Int(y)
END a;


[Dmitry Dagaev]

Directed Coroutines syntax.
Directed coroutines are used in various languages as generators. Coroutines compiler support (in Python, Lua, etc) affords subroutine-like style. Coroutine Transfer is like subroutine call, coroutine Yield is like RETURN.
The C-like syntax with compiler support is below.

Code: Select all

int coroutine Generate123() {
   yield 1;  /* Execution begins here upon first call to Generate123 */
   yield 2;  /* execution continues here upon "resume Generate123" */
   yield 3;  /* execution continues here upon second "resume Generate123" */
  }
printf("%d\n", Generate123()); /* prints "1" */
printf("%d\n", resume Generate123()); /* prints "2" */
printf("%d\n", resume Generate123()); /* prints "3" */


The Co_Routines subsystem has no compiler support, but uses Transfer-Yield strict FILO discipline

Code: Select all

TYPE
Gen = POINTER TO RECORD (Co.Coroutine)
    rc: INTEGER
END;

PROCEDURE Do (t: Ct.Task);
    VAR g: Gen;
BEGIN
    g := t(Gen);
    g.rc := 1; Co.Yield;
    g.rc := 2; Co.Yield;
    g.rc := 3; Co.Yield
END Do;

PROCEDURE Run;
    VAR g: Gen;
BEGIN
    NEW(g);
    Co.InitCoroutine(g, Do);
    g.Start(g);
    g.Transfer(g);
    Log.Int(g.rc); Log.Ln;
    g.Transfer(g);
    Log.Int(g.rc); Log.Ln;
    g.Transfer(g);
    Log.Int(g.rc); Log.Ln;
END Run;


The new Coroutines system by Josef Templ https://forum.blackboxframework.org/viewtopic.php?f=41&t=610 syntax will be as following

Code: Select all

TYPE
Gen = POINTER TO RECORD (Co.Coroutine)
    rc: INTEGER
END;

PROCEDURE Do (this: Gen);
BEGIN
    g.rc := 1; Co.Transfer(this.from);
    g.rc := 2; Co.Transfer(this.from);
    g.rc := 3; Co.Transfer(this.from);
END Do;

PROCEDURE Run;
    VAR g: Gen;
BEGIN
    NEW(g);
    Co.Init(g);
    Co.Transfer(g);
    Log.Int(g.rc); Log.Ln;
    Co.Transfer(g);
    Log.Int(g.rc); Log.Ln;
    Co.Transfer(g);
    Log.Int(g.rc); Log.Ln;
END Run;   


The problem is, that Co.Transfer(this.from) is used instead of Co.Yield statement. So FILO calling sequence not guaranteed.

Co_Routines subsystem guarantees strict FILO calling sequence. Moreover a REENTRANT_ERROR (Trap 59) is generated on such attempt.

[Ivan Denisov]

The problem is, that Co.Transfer(this.from) is used instead of Co.Yield statement. So FILO calling sequence not guaranteed.

Why?

[Dmitry Dagaev]

You can type Co.Transfer(another). Nothing prevents you. And you return data not to calling point, but to other side. Just if you ask Mary an apple but get project plan from Boss.
The same situation, if you use subroutines, is guaranteed by compiler. Subroutine calls are placed in stack by FILO discipline.
CALL Subroutine();
RETURN after-the-call;

[Josef Templ]

Dmitry, before I go into the design issue I have a technical question.
You are using the ConvertThreadToFiberEx function but not the
CreateFiberEx function.

Is there a special reason for that?

Do you know what the default behavior with respect to the fpu registers is
when not using the *Ex functions? I mean, is it faster to use the *Ex functions
with the floating point flag set to 0 or is this the default in the non-*Ex functions
anyway?

- Josef

[Dmitry Dagaev]

Josef,

I am using primary:=ConvertThreadToFiber(0) to create primary fiber for current thread and CreateFiber for each coroutine. ConvertThreadToFiber is necessary, because only fibers can execute fibers according to MSDN. On CLOSE ConvertFiberToThread is mandatory.
I have no information about Fibers implementation details.

The fastest approach is to deal with register operations. I witnessed some source code of Cooperative Tasks switching by Ilya Ermakov https://community.blackboxframework.org/viewtopic.php?f=49&t=165&p=952#p952, but this source was not published. It used GETREG/PUTREG for registers switching.

[Josef Templ]

I am using primary:=ConvertThreadToFiber(0) to create primary fiber for current thread and CreateFiber for each coroutine.

I see.
ConvertThreadToFiberEx (in the CPC 2014 package) is only in the Co_Api module
but not used.

- Josef

[Dmitry Dagaev]

The only reason to use ConvertThreadToFiberEx is to use FIBER_FLAG_FLOAT_SWITCH. In Co_Api module I was performing some experiments on this flag, and it is set to 0 in my current version. Setting this flag results in creating fibers failure on several old (and, maybe, new) platforms. They say, that in win2k-sp6 fiber is not created when the flag is set. So I met the portability problem and decided to use default behaviour.