Continuation Systems
|
This article's tone or style may not reflect the encyclopedic tone used throughout the wiki. See Wikipedia's article on tone for suggestions. |
Time-sharing works by interrupting the running program and saving its run-time state (such as program counter and registers) into a data structure (often the kernel-level stack). Theoretically speaking, that saved state constitutes a one-shot continuation of the interrupted program. Indeed, switching threads in a thread-based system involves saving the continuation of the old thread into that thread's data structure, and then loading and throwing to a new continuation from the new thread. Adding a copy operation for continuations allows user-programs to decide when to use expensive multi-shot continuations. Finally, adding an operation to suspend the current continuation and pass it as a value to a specified new continuation enables continuations to communicate -- throwing to a continuation sends it a value that may include its invoker.
Because no saved continuation can represent the currently-running program, the idea of virtual processors is required. These represent the current continuation by storing the kernel's status information for the current computation and abstracting over machine processors. The kernel can use virtual processors to support multiprocessor or multi-core machines by creating a virtual processor abstraction for each logical processor.
One can easily see an analogy: virtual processors look and behave like running threads, while saved continuations look and behave like suspended threads.
Scheme and ML programmers have known for years how to use continuations of coroutines to create cooperative threading systems, but a preemptive system (like most operating-system creators desire) requires some mechanism to preempt a running program. Adding an event abstraction accomplishes this. These events can contain any number of saved continuations for "handlers", and support an operation to "fire" or "trigger" the event. When something fires an event, it dequeues all of its handlers and hands them to a scheduler that only needs to decide what kind of event-handler continuations can preempt what kind of running virtual processors. When the scheduler decide to preempt, it simply passes the preempted continuation to the preempting continuation as a value, possibly checking the return value it receives when the preempting continuation finishes for error codes. Giving the handler the preempted continuation allows it to perform higher-level scheduling operations, possibly moving a function that even L4 kept in the kernel out of it.
Note that events can serve as a convenient abstraction over machine interrupts. Using them as such provides a convenient way to translate hardware support for preemption into operating-system support for preemption.
However, adding a continuation as an event handler with the current set of operations will run far too slowly for real use. Instead, events gain a new operation that adds the current continuation to the given event's set of handlers and then invokes a given continuation with a given value. This primitive can run much more efficiently.
Finally, adding a single additional primitive operation will serve to bring this concurrency system into the truly parallel world of multi-core and multi-processor machines. Since a continuation cannot terminate itself without throwing to another continuation, a virtual processor can even run itself forever once started. One only needs a primitive to start an inactive virtual processor with a given continuation and value.
In conclusion, continuations; virtual processors; and events can be used to build complex concurrency and parallelism models on top of normal processes by giving user-space or higher levels of the kernel control over the multiplexing of processors.
An interesting side question: Can events be used to implement standard synchronization objects, assuming that the kernel makes events work in a parallel-safe manner? It can easily be shown that events will sufficiently serve to implement barrier variables, but what about semaphores?