2012-07-02: Preemptive Threads with Continuations

Last week, we covered cooperative threading with continuations. This week we’ll change the infrastructure to mimic preemption.

-

Before we start, make sure you’ve read last week’s post.

We’ll be working from almost the same example program:

The only difference is that I’ve removed the calls to yield after the calls to printf.

Recall that this program has the following output:

We’ll also be using the same basic threading system:

Now, this system is about modeling concurrency through threading, so there is no actual real concurrency in the system. In contrast, in a real operating system there is true concurrency because the computer interacts with concurrently-running pieces of hardware... such as disk devices, the network card, or an alarm device. When this concurrent devices message the kernel, through interrupts, it can take control from the user programs and potentially choose a different user program to re-use, without the permission of the user process.

This option is not available at the user level, particularly if you do not assume the pre-existence of a lower-level threading system. Since I’m a good academic, whenever you face a problem that seems unsolvable, the one sure path is to redefine success. Thus, we’ll focus on the "without permission" part of preemptive concurrency—removing the need of threaded programs from calling yield, but having it called for them, without their permission, periodically.

The simplest way to realize this is to choose a set of "primitive" functions provided by the OS and have them call yield on behalf of the process. For example, printf is a naturally choice.

When we take this approach, we need to ensure that the process has no other way of getting to these primitives. This is not a very hard thing to do if we’re implementing a language tower, like Racket, but is more difficult if we are simply writing a library atop Racket.

This approach has a fundamental trade-off with regards to fairness: the fewer primitive functions, the more likely it is that the other processes will starve, as the current thread may not ever call a primitive, such as printf. A typical solution to this is to call yield on every function return, including tail-calls (i.e. loops), because every program must do this very often.

However, if primitive functions always call yield and there are many such primitive functions, then we’re likely to have too many context switches. In that case, it’s wise to use some sort of "fuel" counter that indicates how many function calls are allowed before switching. We can realize this in the printf code:

In this example I used a fuel of two, which renders the following output:

A nice side-effect of a fuel system like this is that you can give different processes different amounts of fuel to represent priorities.

This is actually how the Racket threading system is implemented, although all the continuation capturing, context switching, primitive functions, and fuel manipulation is done in the C virtual machine. You can see the macros that manage fuel around line 1581 of include/scheme.h in the Racket VM source.

Next week, we’ll look at system calls in this infrastructure.

By the way, if you use this code at home, make sure you put the code in this order: