Scheduling Examples Using Serpent Threads

Roger B. Dannenberg
Jan 2018

Introduction

This is a companion document to Introduction to Scheduling. The examples on that page are recreated here using Serpent threads.

Threads in Serpent are non-preemptive, which means you normally do not have to worry about synchronization or race conditions where two threads are concurrently reading and writing to shared memory with unpredictable results. In contrast, threads in Serpent run until you explicitly call yield() or yieldto() or perhaps call a scheduling function that indirectly yields control to another thread.

The scheduler library (sched) has been extended to support threads, allowing threads to pause within a logical time system. Thus, threads support the same kind of precise timing you can obtain by scheduling function and method calls directly with the scheduler.

Scheduling Threads

Simple Example

(Code available here.) Let's make a simple program to print a message every second.

require "debug"
require "sched"

def activity():
    if fork(): return // main thread returns
    sched_wait(1)     // initial delay is 1 s
    var i = 101
    while true: // loop forever
        display "activity", i, sched_rtime, time_get()
        i = i + 1
        sched_wait(1)
    // this thread never ends

sched_init()
activity()
sched_run()

Notes:

The main thread is reserved for the scheduler, so we need to fork a new thread to get scheduled behavior.
The fork() function duplicates the current stack frame, so the effect is as if there are now two copies of the function running.
fork() returns the “child” thread to the main thread, but it returns nil (false) to the child thread, so the test if fork(): ... allows the two threads to proceed on different paths.
The main thread returns immediately: if fork(): return.
The child thread waits 1 s, then enters a loop where it prints, increments i and waits 1 s.
The sched_wait(1) call uses the scheduler to suspend the thread and wake up later. When the thread wakes up, the logical time will be advanced by exactly 1. (This differs greatly from time_sleep() which causes the entire Serpent process (all threads, GUI, etc.) to sleep for some time, but does not advance the logical time.)
The rest of the code is very much like the Simple Example using temporal recursion.

Here's what some output looks like:

activity: i = 101, sched_rtime = 1, time_get() = 1
activity: i = 102, sched_rtime = 2, time_get() = 2.002
activity: i = 103, sched_rtime = 3, time_get() = 3.001
activity: i = 104, sched_rtime = 4, time_get() = 4.001
activity: i = 105, sched_rtime = 5, time_get() = 5
activity: i = 106, sched_rtime = 6, time_get() = 6
activity: i = 107, sched_rtime = 7, time_get() = 7.001
activity: i = 108, sched_rtime = 8, time_get() = 8
activity: i = 109, sched_rtime = 9, time_get() = 9.001
activity: i = 110, sched_rtime = 10, time_get() = 10.001
^C

Notice that the ideal event times, accessed as sched_rtime are precisely 1 second apart, as if the computer is infinitely fast and time is not quantized. The actual time, accessed as time_get() is close to the ideal time, but sometimes a millisecond or two late.

Two Activities

(Code available here.) Scheduling is most useful when there are many threads whose events are interleaved in time. This example is an alternate implementation of the temporal recursion example Two Activities. The code here is very much like the previous example (above) since it mainly just adds another thread.

As with Two Activities, the code runs two activities. activity_1 runs every second; activity_2 runs every 3 seconds.

require "debug"
require "sched"


def activity_1():
    if fork(): return
    var i = 101
    while true:
        display "act1    ", i, sched_rtime, time_get()
        i = i + 1
        sched_wait(1)


def activity_2():
    if fork(): return
    var i = 201
    while true:
        display "    act2", i, sched_rtime, time_get()
        i = i + 1
        sched_wait(3)

sched_init()
activity_1()
activity_2()
sched_run()

Again, here is some output generated by the program. Notice that when 2 events are scheduled for the same time, they run sequentially, but it is not obvious which will run first. (In this case, ordering is deterministic, but order depends on the implementation of the priority queue in the scheduler.)

Notice also that activity 1 (“act1”) runs every second, while activity 2 (“act2”) runs every 3 seconds.

    act2: i = 201, the_sched.time = 1, time_get() = 1.001
act1    : i = 101, sched_rtime = 1, time_get() = 1.001
act1    : i = 102, sched_rtime = 2, time_get() = 2
act1    : i = 103, sched_rtime = 3, time_get() = 3.001
act1    : i = 104, sched_rtime = 4, time_get() = 4.001
    act2: i = 202, sched_rtime = 4, time_get() = 4.002
act1    : i = 105, sched_rtime = 5, time_get() = 5
act1    : i = 106, sched_rtime = 6, time_get() = 6
act1    : i = 107, sched_rtime = 7, time_get() = 7
    act2: i = 203, sched_rtime = 7, time_get() = 7
act1    : i = 108, sched_rtime = 8, time_get() = 8.001
act1    : i = 109, sched_rtime = 9, time_get() = 9
act1    : i = 110, sched_rtime = 10, time_get() = 10
    act2: i = 204, sched_rtime = 10, time_get() = 10
act1    : i = 111, sched_rtime = 11, time_get() = 11.001
act1    : i = 112, sched_rtime = 12, time_get() = 12.002
^C

Multiple "Threads" Using One Function

(Code available here.) Let's go back to the first example and initialize the schedule with two calls to activity. We will pass in the initial delay and initial values of i so they can be different, thus duplicating the behavior of the Multiple Threads Using One Function example.

require "debug"
require "sched"


def activity(i):
    if fork(): return // main thread returns
    sched_wait(1)     // initial delay is 1 s
    while true: // loop forever
        display "activity", i, sched_rtime, time_get()
        i = i + 1
        sched_wait(1)
    // this thread never ends

sched_init()
activity(101)
activity(201)
sched_run()

Here is some output generated by the program. Notice that there are two independent threads, even though there in only one function. The events are separated by 1 second, with one set of events starting at 1 and the other starting at 1.1.

activity: i = 101, sched_rtime = 1, time_get() = 1.002
activity: i = 201, sched_rtime = 1.1, time_get() = 1.101
activity: i = 102, sched_rtime = 2, time_get() = 2.001
activity: i = 202, sched_rtime = 2.1, time_get() = 2.102
activity: i = 103, sched_rtime = 3, time_get() = 3
activity: i = 203, sched_rtime = 3.1, time_get() = 3.1
activity: i = 104, sched_rtime = 4, time_get() = 4
activity: i = 204, sched_rtime = 4.1, time_get() = 4.1
activity: i = 105, sched_rtime = 5, time_get() = 5.001
activity: i = 205, sched_rtime = 5.1, time_get() = 5.101
^C

The Stopping a “Thread” Pattern

(Code available here.) How can we stop a thread that runs a loop as in previous examples? The simplest way is to set a flag that causes the loop to exit immediately. As described in The Stopping a “Thread” Pattern, not a good solution.

A solution with threads that parallels the temporal recursion example follows.

require "debug"
require "sched"


activity_id = 0 // used to kill "threads"


def activity_start(delay, i):
    if fork(): return
    sched_wait(delay)
    activity_id = activity_id + 1 // kill any old running activity
    var id = activity_id
    while id == activity_id:
        display "activity", id, i, sched_rtime, time_get()
        i = i + 1
        sched_wait(1)
    display "activity terminates", id, sched_rtime, time_get()


sched_init()
activity_start(1, 101)
activity_start(4.5, 201)
sched_run()

Notice how this differs from the temporal recursion solution.

In the temporal recursion solution, we have a delayed start followed by periodic executions of activity. This required two functions, but since threads can wait in the middle of sequential execution, we can perform the initial delay, then increment activity_id, and then enter a loop, all within one function, activity_start.

Here is some output generated by the program. Notice that the first thread is effectivly killed at time 4.5 when activity_id is incremented, but the thread does not "know" this until it wakes up at time 5, “sees” activity_id has changed, and terminates (returns).

activity: id = 1, i = 101, sched_rtime = 1, time_get() = 1.001
activity: id = 1, i = 102, sched_rtime = 2, time_get() = 2.002
activity: id = 1, i = 103, sched_rtime = 3, time_get() = 3.001
activity: id = 1, i = 104, sched_rtime = 4, time_get() = 4.001
activity: id = 2, i = 201, sched_rtime = 4.5, time_get() = 4.5
activity terminates: id = 1, sched_rtime = 5, time_get() = 5.001
activity: id = 2, i = 202, sched_rtime = 5.5, time_get() = 5.501
activity: id = 2, i = 203, sched_rtime = 6.5, time_get() = 6.501
activity: id = 2, i = 204, sched_rtime = 7.5, time_get() = 7.501
^C

Spawning New Activity

(Code available here.) A thread can be forked at any time. Here's a thread that runs every second. Each second, it forks another thread that runs every 0.1 seconds, but only 3 times. This has the same behavior as the Spawning New Activity example.

In this implementation, the “sub-thread” is syntactically nested within the main thread, so each iteration of the outer loop forks a copy of the inner loop. These are independent threads, so there is no constraint in this case that the inner thread completes before the next iteration of the outer loop.

It is important to understand when the inner threads complete. Find the line return // IMPORTANT!. This returns from the inner thread or “sub-thread”. Without this, the inner thread would continue executing the outer loop. Even though the fork() is inside the loop, it still duplicates the entire state of execution of the function.

require "debug"
require "sched"

def activity(i):
    if fork(): return
    sched_wait(1) // initial delay
    while true:
        display "activity", i, sched_rtime, time_get()
        i = i + 1
        if fork() == nil:
            for j = 0 to 3
                sched_wait(0.1)
                display "     sub", j, sched_rtime, time_get()
            return // IMPORTANT!
        sched_wait(1)

sched_init()
activity(101)
sched_run()

Here is some output generated by the program.

activity: i = 101, sched_rtime = 1, time_get() = 1.001
     sub: j = 0, sched_rtime = 1.1, time_get() = 1.102
     sub: j = 1, sched_rtime = 1.2, time_get() = 1.202
     sub: j = 2, sched_rtime = 1.3, time_get() = 1.3
activity: i = 102, sched_rtime = 2, time_get() = 2.002
     sub: j = 0, sched_rtime = 2.1, time_get() = 2.101
     sub: j = 1, sched_rtime = 2.2, time_get() = 2.2
     sub: j = 2, sched_rtime = 2.3, time_get() = 2.3
activity: i = 103, sched_rtime = 3, time_get() = 3.001
     sub: j = 0, sched_rtime = 3.1, time_get() = 3.101
     sub: j = 1, sched_rtime = 3.2, time_get() = 3.201
     sub: j = 2, sched_rtime = 3.3, time_get() = 3.302
^C

Virtual Time, Fixed Tempo

(Code available here.) This example uses threads to implement the temporal recursion example Virtual Time, Fixed Tempo. The thread-based solution is very similar, and the chief thing to note is that sched_wait() in activity() uses vtsched because it is selected when sched_wait() is called. If another scheduler is selected while sched_wait() is waiting, it does not matter, because the scheduler will be saved and restored by sched_wait(). However, sched_select just sets a global variable, so you should be careful. For example, if you call a function that calls sched_select in order to use it for a new thread, keep in mind that the current scheduler may change when you call that function.

require "debug"
require "sched"


def activity(i):
    if fork(): return
    sched_wait(1)
    while true
        display "activity", i, sched_rtime, time_get(), sched_vtime
        i = i + 1
        sched_wait(1)


sched_init()
sched_select(vtsched)
sched_set_bps(2) // 2 beats per second
activity(101)
sched_run()

Here's the output. Notice the_sched (which is vtsched) time is not even close to real time because this is virtual time (or beats, if you prefer).

activity: i = 101, sched_rtime = 0.5, time_get() = 0.5, sched_vtime = 1
activity: i = 102, sched_rtime = 1, time_get() = 1.002, sched_vtime = 2
activity: i = 103, sched_rtime = 1.5, time_get() = 1.502, sched_vtime = 3
activity: i = 104, sched_rtime = 2, time_get() = 2.001, sched_vtime = 4
activity: i = 105, sched_rtime = 2.5, time_get() = 2.502, sched_vtime = 5
^C

Virtual Time, Variable Tempo

(Code available here.) The speed or tempo can be changed. Here, we reimplement the Virtual Time, Variable Tempo example using threads. This example changes tempo to 0.5 beats per second at beat 4.

Notice how we wait until beat 4 to change tempo. Top-level commands in Serpent are compiled as the body of a parameter-less function, which is then called, so the semantics here are to fork the implicit parameter-less function; hence, sched_wait works. You might find it more direct

require "debug"
require "sched"

def activity(i):
    if fork(): return
    sched_wait(1)
    while true:
        display "activity", i, sched_rtime, time_get(), sched_vtime
        i = i + 1
        sched_wait(1)

sched_init()
sched_select(vtsched)
sched_set_bps(2) // 2 beats per second
// equivalent to: sched_set_period(0.5)
activity(101)
if fork() == nil:
    sched_wait(4)
    sched_set_bps(0.5)
sched_run()

Here's the output. Notice the real times (time_get()) are every 0.5s until beat 4, then every 2s.

activity: i = 101, sched_rtime = 1, time_get() = 0.5
activity: i = 101, sched_rtime = 0.5, time_get() = 0.5, sched_vtime = 1
activity: i = 102, sched_rtime = 1, time_get() = 1.002, sched_vtime = 2
activity: i = 103, sched_rtime = 1.5, time_get() = 1.501, sched_vtime = 3
activity: i = 104, sched_rtime = 2, time_get() = 2, sched_vtime = 4
activity: i = 105, sched_rtime = 4, time_get() = 4.002, sched_vtime = 5
activity: i = 106, sched_rtime = 6, time_get() = 6.002, sched_vtime = 6
^C

Conclusions

This should be enough to get you started with threads. The remaining examples in Scheduling in Practice can of course be implemented using threads.

Threads are most useful when combined with scheduling primitives such as sched_wait() which gives precisely timed thread behavior and enables many threads to run concurrently.

Keep in mind that threads do not run in parallel and if a thread goes into an long computation, it may starve other threads or cause timing problems. sched_wait() is especially useful here because it allows you to tell threads when to run and when to stop.