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