Operating Systems from First Principles, Part 1: Rethinking Threads

Arguably the most basic functionality of any modern OS is multitasking, and a decent threading model is fast becoming a required feature of any modern language runtime; therefore, it makes sense that I start what will in time become a lengthy elaboration with this topic.

An often-missed subtlety is that there are two different goal sets that can arise regarding multiple processors and threads, and though the realization of one can support the other, this may not be the best way to go about doing things.

The first goal is the most common: having the appearance of an infinite number of processors regardless of the underlying hardware. The primary concern here is interactivity. Raw number-crunching can be postponed provided that threads which acknowledge events are able to do so. This is what we all learn in undergrad, and is the goal of a pthread-style API. This is the production of concurrent execution, sometimes from a single processor, sometimes from several.

The second goal is increased performance, or the consumption of concurrent execution. Because the pthread model is so common, we might be tempted roll this line of thinking into it, but there are a few key differences. Parallel evaluation of terms differs from pthread-style concurrency in that it is purely an optimization; it does not affect the outcome of the terms in anyway, and . Furthermore, the interactivity and timing issues are irrelevant. The goal here is to commit more processors to a task, hopefully achieving better performance. Cilk is probably the best example of this particular way of doing things.

Building a scheduler system that caters to both is, to my knowledge, a largely unexplored problem. Such a system needs to support threads, which represent the expectation of interactivity. However, multiple CPUs might be committed to a single thread. The scheduling problem then becomes one of balancing the desire for interactivity with the desire to commit large numbers of CPUs to a given thread, so that it completes faster. A useful heuristic here might be that highly interactive threads desire relatively few CPU's, as they would function primarily as dispatchers to more compute-bound threads.

Crossing the user/kernel boundary gets even more complicated, which I'll discuss in later entries. Suffice to say, the activation model is vastly superior to anything else, and the problem gets further complicated by the desire to commit exactly the number of desired CPUs to a given task.