Cooperative Processes

Another way to create concurrency, instead of using task switching, is to use cooperative processes.  Instead of centralised control, processes cooperate each other by "yielding" their own time to other processes, using the mechanism called "co-routine".

We start the discussion by showing how co-routines work.  A normal function A calls function B look like this:

A()         B()
 ...         ...
 B() *1
 *2         return
 ...

A calls B at the point 1, then goes to the beginning of B.  When B reaches the end, it returns to A at the point 2. The machine instruction sequence is:

:A              :B
...             ...
jal rads B
*2              ret rads
...

jal knows where to jump to because the address of B is known (and it is "static").  Now contrast the above with co-routine call.  A calls B (*1), and the control is transfer to B.  At some point B calls A (*2). Then A calls B (*3).  Now, rather than starting at the beginning of B.  It starts at the last place when B calls A (*3) and so on.

:A               :B
...              ...
co-call B *1     co-call A *2
*2               *3              
...              ....
co-call B *3     co-call A *4
*4
...


This creates the virtual "concurrency" of A and B.  When a process co-calls other process, it yields to that process. To make co-routine works, the positions such as *2, *3 must be remembered.  They are called "continuation" point.  Now the call address is "dynamic", it is not known in advanced and it changes through time. To get the continuation point, the call instruction "jal rads X"  saves the return address in rads.  We get the continuation point from the register rads.  The way to return to the continuation point, the instruction "ret rads" is used. The call B is achieved by:

jal rads saveConA
mov rads #B
ret rads            ; jump to B
(continuation point)

:saveConA
  add r0 rads #2       ; to get the continuation point
  st r0 continuationA  ; save it
  ret rads

continuationA       ; storing ret ads, global

saveRadsA is used to get the continuation point then call B is achieved by jump via "rads".

Now, when B co-calls A, it stores its own continuation point and indirect jump to A by using A's continuation point and indirect jump to it.

; co-call A

jal rads saveConB
ld rads continuationA
ret rads
(B's continuation point)

:saveConB
  add r0 rads #2
  st r0 continuationB
  ret rads

continuationB          ; store B's cont.  global


The co-call A can be modelled in the similar fashion.  Now I will show the code in full.

continuationA
continuationB

:main
  mov r1 #A
  st r1 continuationA    ; initially at beginning of A
  mov r1 #B
  st r1 continuationB    ; initially at beginning of B
  ....
  jmp A                  ; start co-routine

:A
  ...
  ; co-call B
  jal rads saveConA
  ld rads continuationB
  ret rads
  ...
  ; co-call B
  jal rads saveConA
  ld rads continuationB
  ret rads
  ...


:B
  ...
  ; co-call A
  jal rads saveConB
  ld rads continuationA
  ret rads
  ...
  ; co-call A
  jal rads saveConB
  ld rads continuationA
  ret rads
  ...

:saveConA
  add r0 rads #2
  st r0 continuationA
  ret rads

:saveConB
  add r0 rads #2
  st r0 continuationB
  ret rads


Let us see how to craft this into a high level language Rz. The normal function call is "B()".  We annotate the co-call by "@" prefix, so co-call B is "@B()".  With this notation, we will show an example of concurrency by co-routines. Assume the compiler generates proper code sequence to saveConA, saveConB and initialise continuationA, continuationB.

A()
  print(1)
  @B()
  print(2)
  @B()
  print(3)

B()
  print("a")
  @A()
  print("b")
  @A()
  print("c")


once we start A() the following output appears:

1 a 2 b 3 c

Hence, A and B are virtually concurrent and the act of "yielding" to other process is voluntary. See the complete S21 code here (coop.txt).

The weakness of co-operative process is that if one process in the co-operation is buggy then all the processes will crash. The advantage of co-operative process is that it is very simple and very efficient, hence it is used often in a resource constrained system (such as small embedded systems).

last update  17 Feb 2017