2012-07-12: Domain-Specific Operating Systems: Threads, System Calls, and Continuations

In the past few posts I’ve been writing about threading system that are based on continuations in user-land. This post I’ll extend that system to provide system calls that control access to sensitive resources, such as files and the thread pool.

-

We’ll be working from the same example program as last week, except that we’ll be changing printf from a "primitive" function to a system call. Here’s the program:

Recall that this program has the following output:

In the original threading system, global mutable variables were used to handle the state of the threading system:

Notice that the "logical" system calls—thread, exit, yield and printf—all mutate the thread system’s state (ts). This makes the system difficult to test and analyze.

Our goal is to tease out all this code into a single "kernel" that actually is the threading system and exists independently from the state of the various threads. Here’s a sketch of the kernel:

The state of the kernel will simply be the list of threads and all the kernel really does is continuously call step-one-thread to advance the state of the kernel until all the threads exit. All the work will, of course, take place in step-one-thread:

Its job is simply to select the first thread, run it until it reaches a system call and then deal with the system call.

Let’s represent each system call as structure:

The thing that all system calls have in common is that the context of the user program is preserved, but other than that, each is distinct in the data that it carries.

Once this is in place, we can pretty easily write the code to handle the system calls and update the kernel’s state:

A new thread just needs to push both contexts (the parent and the child) onto the thread queue. (We add them to the top of the queue to preserve compatibility with the previous versions of this code.) When a thread exits, the user context is thrown away. When a printf occurs, the string is displayed and the user context is placed back on the queue, at the end.

We only need to do two more things: implement run-thread-until-syscall and implement the code that the user programs call to return system call structures to the kernel. These are tightly intertwined.

The second is actually simpler, so we’ll do that first. The basic idea is to capture the continuation going back to the kernel and throw it back to the kernel as something like an exception (really, an abort, which you can think of as an exception that can only be caught by privileged code.)

The other code will be very similar to this, so we’ll write a macro to simplify it:

Now that we know how the "thrower" works, we can easily implement the "catcher":

This code says that you just invoke the thread context like a function, but you wrap it in a new prompt. When the code inside aborts with a value, then it is returned to the caller of run-thread-until-syscall (that’s what the values means). We always put in call to exit, in case the code just ends.

I love this code because it so elegantly separates all the different features of an operating system: capturing system calls and program contexts, evaluating the impact on the kernel state for the call, and running the OS itself. From this foundation you could add other system calls and scheduling behavior. I call this a "domain-specific operating system."

One of my pet projects is to build video games in Racket. In that project, I’m using this idea to implement each agent in the game world (the enemies, the player, etc) as processes with custom system calls to interact with each other and the audio/video resources. The kernel there maintains two separate lists of threads: ones that need to do more work on this frame and ones that are done until the next frame needs to be rendered, with a system call to indicate to the OS that all work for a frame is done. It’s really quite beautiful. Maybe I’ll write more about it in the future.

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