-
Notifications
You must be signed in to change notification settings - Fork 1
More on Multitasking in zeptoscript
zeptoscript has support for cooperative multitasking, also known as symmetric coroutines. These are found in the zscript-task module defined in src/common/task.fs. This is dependent upon queues in the zscript-queue module defined in src/common/queue.fs.
Cooperative multitasking involves one or more tasks in a queue of ready tasks, along with zero or more blocked tasks in other queues. A single operation is used to switch between tasks, and switching between tasks always switches to the task at the head of the queue of ready tasks.
zeptoscript also has support for asymmetric coroutines. These are found in the zscript-coroutine module defined in src/common/coroutine.fs.
Asymmetric coroutines involves resuming suspended coroutines, passing them values, and suspending running coroutines, passing values to that which had resumed them. In many ways they are similar to generators in languages such as Python, but they are more general than them.
One important note about symmetric coroutines in zeptoscript is that there is no concept of a "task object". Tasks are simply saved states, which are similar but not identical to continuations à la Scheme, which are created each time they are yielded.
To start executing scheduled tasks one simply calls start ( -- ). This will only return when the last task terminates.
To yield the current task, to execute the next task in the task queue, one executes yield ( -- ). Note that this returns immediately if there are no queued tasks. An example of this in action is:
zscript-task import
: run-test ( -- )
fork not if 16 0 ?do ." FOO " yield loop terminate then
fork not if 16 0 ?do ." BAR " yield loop terminate then
start
;
Executing run-test outputs:
FOO BAR FOO BAR FOO BAR FOO BAR FOO BAR FOO BAR FOO BAR FOO BAR FOO BAR FOO BAR FOO BAR FOO BAR FOO BAR FOO BAR FOO BAR FOO BAR ok
Here is the same code but without yield:
zscript-task import
: run-test ( -- )
fork not if 16 0 ?do ." FOO " loop terminate then
fork not if 16 0 ?do ." BAR " loop terminate then
start
;
Executing run-test outputs:
FOO FOO FOO FOO FOO FOO FOO FOO FOO FOO FOO FOO FOO FOO FOO FOO BAR BAR BAR BAR BAR BAR BAR BAR BAR BAR BAR BAR BAR BAR BAR BAR ok
There are two ways to create a task. The first is to pass a thunk to spawn ( xt -- ), which places the new task at the rear of the task queue.
An example of this is:
zscript-task import
: run-test ( -- )
[: 16 0 ?do i . 250 ms loop terminate ;] spawn
start
;
Executing run-test outputs:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ok
The second is to call fork ( -- parent? ), which creates a new task which will continue executing at the point that fork would return false, and which immediately returns true in the parent task. This can be seen here:
zscript-task import
: run-test ( -- )
fork not if
fork not if
cr ." In child's child! " terminate
else
cr ." In child! " terminate
then
else
cr ." In parent! "
start
then
;
Executing run-test outputs:
In parent!
In child!
In child's child! ok
To terminate the current task one calls terminate ( -- ), as seen above. An example of the control flow provided by fork, start, and terminate is as follows:
zscript-task import
: run-test ( -- )
fork not if ." BAR! " terminate then
." FOO! "
start
." BAZ! "
;
Executing run-test outputs:
FOO! BAR! BAZ! ok
Each task has task-local storage, which it inherits from its parent task. It can be gotten with task-local@ ( -- task-local ) and set with task-local! ( task-local -- ). An example of this in action is:
zscript-task import
zscript-map import
symbol foo
: make-task-local ( -- )
16 ['] symbol>integral ['] = make-map task-local!
;
: run-test ( -- )
make-task-local
0 foo task-local@ insert-map
fork not if
10 0 ?do foo task-local@ map@ . yield loop
terminate
then
make-task-local
16 foo task-local@ insert-map
fork not if
10 0 ?do foo task-local@ map@ . yield loop
terminate
then
make-task-local
256 foo task-local@ insert-map
fork not if
10 0 ?do foo task-local@ map@ . yield loop
terminate
then
start
;
Executing run-test outputs:
0 16 256 0 16 256 0 16 256 0 16 256 0 16 256 0 16 256 0 16 256 0 16 256 0 16 256 0 16 256 ok
Bounded message channels (which we will call simply message channels from here out), defined in zscript-chan, are simple first-in-first-out (FIFO) queues permitting both blocking and non-blocking accesses, and also permitting "peeking" where the message at the head of the queue can be fetched without dequeuing it. Message channels have a fixed number of elements set when they are created, and receiving or peeking on an empty message queue and sending on a full message queue will block unless one is using non-blocking operations.
Bounded message channels are created with make-chan ( size -- channel ), where size is the maximum number of permitted elements. Newly-created message channels are empty.
Message channels are sent to with send ( message channel -- ) in a blocking fashion, or with send-non-block ( message channel -- success? ) in a non-blocking fashion. Note that send-non-block returns true for success? when a message was successfully sent, and false for success? when no message was sent.
Message channels are received from with recv ( channel -- message ) in a blocking fashion, or with recv-non-block ( channel -- message success? ) in a non-blocking fashion. Note that recv-non-block returns true for success? when a message can be received, and false for success? along with 0 for message when no message is available.
Message channels are peeked, i.e. fetching the message at the head of the queue without dequeuing it, with peek ( channel -- message ) in a blocking fashion, or with peek-non-block ( channel -- message success? ) in a non-blocking fashion. Note that peek-non-block returns true for success? when a message can be peeked, and false for success? along with 0 for message when no message is available.
Unbounded message channels, defined in zscript-uchan, are a special type of message channel that has no limit on the number of elements. Consequently, sends on unbounded message channels always return immediately, and never transfer control by themselves. This is important for things such as proper implementation of actors, but at the same time means that when sending messages it is important to at points call zscript-task::yield or another word that will call it such as zscript-task::ms, as the sent messages will otherwise never be handled, and memory usage will increase until the space in the heap is exhausted. On the other hand, receiving on unbounded message channels is blocking by default just like for bounded message channels.
Unbounded message channels are created with make-uchan ( -- uchannel ). Newly created unbounded message channels are empty.
Unbounded message channels are sent to with send ( message uchannel -- ). Unlike zscript-chan::send this does not block, as it immediately enqueues a message in an unbounded message channel's queue and returns control to its caller. There is no separate blocking and non-blocking words for this as a result.
Unbounded message channels are received from with recv ( uchannel -- message ) in a blocking fashion, or with recv-non-block ( uchannel -- message success? ) in a non-blocking fashion. Note that recv-non-block returns true for success? when a message can be received, and false for success? along with 0 for message when no message is available.
Unbounded message channels are peeked, i.e. fetching the message at the head of the queue without dequeuing it, with peek ( uchannel -- message ) in a blocking fashion, or with peek-non-block ( uchannel -- message success? ) in a non-blocking fashion. Note that peek-non-block returns true for success? when a message can be peeked, and false for success? along with 0 for message when no message is available.
A common use of message channels is for connecting producers with consumers. Any number of producers may send messages to message channels, and any number of consumers may receive messages from message channels. An example of this is as follows:
zscript-task import
zscript-chan import
symbol done
: run-test ( -- )
1 make-chan { my-chan }
fork not if 32 0 ?do i my-chan send 1 +loop done my-chan send terminate then
fork not if -32 -1 ?do i my-chan send -1 +loop done my-chan send terminate then
fork not if
0 { done-count }
begin done-count 2 < while
my-chan recv dup done <> if . else drop 1 +to done-count then
repeat
terminate
then
start
;
Executing run-test outputs:
0 1 -1 2 -2 3 -3 4 -4 5 -5 6 -6 7 -7 8 -8 9 -9 10 -10 11 -11 12 -12 13 -13 14 -14 15 -15 16 -16 17 -17 18 -18 19 -19 20 -20 21 -21 22 -22 23 -23 24 -24 25 -25 26 -26 27 -27 28 -28 29 -29 30 -30 31 -31 -32 ok
A simple sort of blocking wait is the time delay. This is implemented through wait-delay ( start-time delay -- ), where start-time is the starting time in ticks, as given by systick-counter ( -- ticks ), and delay is the delay from that time in ticks. Note that one tick is equivalent to 100 microseconds. Note that time delays involve the current task being repeatedly yielded until the time represented by start-time plus delay is reached.
However, other kinds of blocking waits are possible. Unlike time delays, they do not involve repeatedly testing for a condition, but rather placing the current task in a queue with block ( queue -- ) and then removing a task from the queue and scheduling it with wake ( queue -- ).
A good example of this sort of blocking wait is those provided by message channels. When one sends a message to a message channel and the message channel is full, the current task is blocked and placed at the rear of the queue referred to by chan-send-wait@. Likewise, when one attempts to receive a message from a message channel and the message channel is empty, the current task is blocked and placed at the rear of the queue referred to by chan-recv-wait@. This is shown by the following in src/common/channel.fs:
\ Wait on sending a message on a channel
: wait-send { msg chan -- }
begin
chan chan-send-wait@ block
chan chan-messages@ queue-size chan chan-max-size@ < if
msg chan actual-send true
else
false
then
until
;
\ Wait on receiving a message from a channel
: wait-recv { chan -- msg }
begin
chan chan-recv-wait@ block
chan chan-messages@ queue-empty? not if
chan actual-recv true
else
false
then
until
;
Conversely, when a message channel with a blocked receiving task is sent to, or when a message channel with a blocked sending task is received from, the blocked receiving task or the blocked sending task is dequeued and then scheduled with wake, as illustrated by the following:
\ Wake a sending task for a channel
: wake-send { chan -- }
chan chan-send-wait@ queue-empty? not
chan chan-send-pending@ not and if
true chan chan-send-pending!
chan chan-send-wait@ wake
then
;
\ Wake a receiving task for a channel
: wake-recv { chan -- }
chan chan-recv-wait@ queue-empty? not
chan chan-recv-pending@ not and if
true chan chan-recv-pending!
chan chan-recv-wait@ wake
then
;
\ Actually send a message on a channel
: actual-send { msg chan -- }
false chan chan-send-pending!
msg chan chan-messages@ enqueue
chan chan-send-count@ 1- chan chan-send-count!
chan wake-recv
;
\ ...
\ Actually receive a message on a channel
: actual-recv { chan -- msg }
chan chan-messages@ dequeue if
false chan chan-recv-pending!
chan chan-recv-count@ 1- chan chan-recv-count!
chan wake-send
else
[: ." should not happen!" cr ;] ?raise
then
;
So you are probably wondering how on Earth you "join" a task when there is no such thing as a "task object". This is accomplished by creating a message channel shared by both the task to be waited for and the waiting task, where the waiting task will receive on the message channel for each task to be waited for. Note that the "size" of each message channel must be at least as large as the number of tasks being waited for, so they will not block when they are about to terminate.
This is demonstrated by the following:
zscript-task import
zscript-chan import
3 constant join-count
: task-a { join-chan -- }
fork not if
16 0 ?do ." A: " i . 125 ms loop
0 join-chan send
terminate
then
;
: task-b { join-chan -- }
fork not if
16 0 ?do ." B: " i . 250 ms loop
0 join-chan send
terminate
then
;
: task-c { join-chan -- }
fork not if
16 0 ?do ." C: " i . 500 ms loop
0 join-chan send
terminate
then
;
: done-task { join-chan -- }
fork not if
join-count 0 ?do join-chan recv drop loop
." DONE! "
terminate
then
;
: run-test ( -- )
join-count make-chan { join-chan }
join-chan task-a
join-chan task-b
join-chan task-c
join-chan done-task
start
;
When executed this outputs the following:
A: 0 B: 0 C: 0 A: 1 B: 1 A: 2 A: 3 B: 2 C: 1 A: 4 A: 5 B: 3 A: 6 A: 7 B: 4 C: 2 A: 8 A: 9 B: 5 A: 10 A: 11 B: 6 C: 3 A: 12 A: 13 B: 7 A: 14 A: 15 B: 8 C: 4 B: 9 B: 10 C: 5 B: 11 B: 12 C: 6 B: 13 B: 14 C: 7 B: 15 C: 8 C: 9 C: 10 C: 11 C: 12 C: 13 C: 14 C: 15 DONE! ok
Here the tasks created by task-a, task-b, and task-c send messages on join-chan just before they call terminate, and the task created by join-task receives three messages, one for each of the tasks being joined, prior to printing DONE!.
The message channels we have seen are ones for single tasks to receive messages at a time. However, it might be desired to send messages to multiple tasks at a time. This can be achieved through creating one task which receives commands, and uses them to send messages to multiple other tasks. An example of this is below:
zscript-task import
zscript-chan import
zscript-queue import
symbol done
symbol do-send
symbol do-subscribe
symbol do-terminate
global wait-count
: relay-task ( -- cmd-chan )
1 make-chan { cmd-chan }
fork not if
make-queue ref { send-queue }
begin
cmd-chan recv pair> over do-send = if
nip { msg }
make-queue { new-queue }
begin send-queue ref@ dequeue while
dup new-queue enqueue
msg swap send
repeat
drop
new-queue send-queue ref!
else
over do-subscribe = if
send-queue ref@ enqueue drop
else
swap do-terminate = if
drop terminate
else
drop
then
then
then
again
then
cmd-chan
;
: subscribe { subscribe-chan cmd-chan -- }
do-subscribe subscribe-chan >pair cmd-chan send
;
: broadcast { msg cmd-chan -- }
do-send msg >pair cmd-chan send
;
: send-task { end-index start-index incr cmd-chan -- }
fork not if
end-index start-index ?do i cmd-chan broadcast incr +loop
wait-count@ 1- wait-count!
done cmd-chan broadcast
terminate
then
;
: recv-task { label cmd-chan -- }
fork not if
1 make-chan { recv-chan }
recv-chan cmd-chan subscribe
begin wait-count@ 0> while
recv-chan recv dup done <> if label type . else drop then
repeat
terminate
then
;
: terminate-task { cmd-chan -- }
fork not if
1 make-chan { recv-chan }
recv-chan cmd-chan subscribe
begin wait-count@ 0> while
recv-chan recv drop
repeat
do-terminate 0 >pair cmd-chan send
terminate
then
;
: run-test ( -- )
relay-task { cmd-chan }
s" A: " cmd-chan recv-task
s" B: " cmd-chan recv-task
s" C: " cmd-chan recv-task
cmd-chan terminate-task
10 0 1 cmd-chan send-task
-10 -1 -1 cmd-chan send-task
3 wait-count!
start
;
Executing run-test outputs:
A: 0 B: 0 C: 0 A: -1 B: -1 C: -1 A: 1 B: 1 C: 1 A: -2 B: -2 C: -2 A: 2 B: 2 C: 2 A: -3 B: -3 C: -3 A: 3 B: 3 C: 3 A: -4 B: -4 C: -4 A: 4 B: 4 C: 4 A: -5 B: -5 C: -5 A: 5 B: 5 C: 5 A: -6 B: -6 C: -6 A: 6 B: 6 C: 6 A: -7 B: -7 C: -7 A: 7 B: 7 C: 7 A: -8 B: -8 C: -8 A: 8 B: 8 C: 8 A: -9 B: -9 C: -9 A: 9 B: 9 C: 9 A: -10 B: -10 C: -10 ok
Here we have a task acting as an intermediary, receiving messages on one message channel, and then sending them to each of the destination message channels per its internal queue of message channels. This intermediary task acts on commands sent to its command message channel, which take the form of a pair of a command type and an associated value, including messages to subscribe a message channel to it, to send a message to the subscribed message channels, and to terminate the intermediary task. Note that a done message is used to wake up tasks waiting on messages from the intermediary task without requiring them to spin-wait in a non-blocking fashion.
Asymmetric coroutines are started with make-coroutine ( xt -- coroutine ), which takes an execution token and returns a coroutine in a suspended state that will execute that execution token, passing it the value passed to resume, when it is first resumed. Note that when the execution token is done executing, the last value on the stack is passed to the last caller of resume and after that point the coroutine is dead.
Asymmetric coroutines are resumed with resume ( x coroutine -- x' ), passing control to the coroutine. The value x is passed to the coroutine when it executes, either being returned by the coroutine's call to suspend, or if the coroutine had not been executed before being passed as an argument to the execution token which was passed into make-coroutine.
Asymmetric coroutines are suspended with suspend ( x -- x' ), passing control to that which had last resumed the coroutine. The value x is returned by the last call to resume which had resumed the coroutine. The next time resume is called for the coroutine, the argument passed to resume is returned by suspend.
The state of an a coroutine can be gotten with coroutine-state@ ( coroutine -- state ), where state may be one of suspended, running, or dead.
The current coroutine can be gotten with current-coroutine ( -- coroutine ).
Coroutines have coroutine-local state, that can be gotten with coroutine-local@ ( -- x ) and set with coroutine-local! ( x -- ). Coroutines inherit the coroutine-local state from when they were created. Note that there is a coroutine-local state that exists outside any coroutine which is used for initializing coroutines' coroutine-local states.
There are the following exceptions related to asymmetric coroutines:
x-not-in-coroutine is raised if one attempts to call suspend outside of a coroutine.
x-dead-coroutine is raised if one attempts to resume a dead coroutine.
x-running-coroutine is raised if one attempts to resume a running coroutine.
A simple example of asymmetric coroutines in action is generating a Fibonacci sequence and printing it out, as shown below:
zscript-coroutine import
: fibonacci-coroutine ( -- coroutine )
[:
drop
0 1 { x y }
x suspend drop
y suspend drop
begin
x y +
y to x
to y
y suspend drop
again
;] make-coroutine
;
: run-test ( -- )
fibonacci-coroutine { co }
25 0 ?do 0 co resume . loop
;
Executing run-test outputs:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 ok
Another example of asymmetric coroutines, this time involving a coroutine being resumed by another coroutine, is as follows:
zscript-coroutine import
: run-test
[:
.
[:
.
-1 suspend .
-2 suspend .
-3 suspend .
-4
;] make-coroutine { co }
256 co resume .
-256 suspend .
257 co resume .
-257 suspend .
258 co resume .
-258 suspend .
-259
;] make-coroutine { co }
0 co resume .
1 co resume .
2 co resume .
3 co resume .
4 co resume .
;
Executing run-test outputs:
0 256 -1 -256 1 257 -2 -257 2 258 -3 -258 3 -259 coroutine is dead