Josh Haberman

Several people have misinterpreted what I was saying in my previous blog entry, even to the point of thinking I have no idea what I’m talking about. Since these are smart people who I respect, this seems a clear indication that my writing wasn’t clear enough. I think I got a little too excited about shooting from the hip, and sacrificed the integrity of the message. I’ll have to adjust my approach a little.

Let me try a slightly different way of explaining my point. My point, again, was:

software always gets to decide what to do next

Here’s what I mean by that. Let’s say things are going a little crazy on your computer. You’re streaming a sound file from the internet, your shell is in the middle of doing a “cp -r ~ /mnt/external-hd”, and you’re moving your mouse around maniacally and clicking with wild abandon.

Your computer has a bunch of stimuli right now. We have interrupts firing from the sound card, the network card, the mouse, and the disk controller. We’re doing a bunch of I/O, bringing pages into and evicting pages out of the buffer cache. We’re taxing the CPU with MP3 decoding. All at the same time. Sounds like a recipe for thrashing, slowdown, and instability, right? Well, if you’re using a mainstream OS.

OK, now take this crazy situation and freeze. Whew, that feels better. Things aren’t so crazy any more. I have a second to think. By the way, this is what things are always like for your CPU. Even though it might seem crazy and hectic for you, a slow-thinking human, that interrupts are coming in hundreds of times a second, your CPU can execute a million or more cycles between each one. Plenty of time to do a little contemplating.

What sort of contemplating might you do? All kinds of contemplating! Here’s an example. “I’m copying a whole tree of files. Yes, it’s true that I usually put all the most recently read pages in the buffer cache, and evict old pages to make space. But these pages are not likely to be the next pages to be accessed, so I will not evict anything to make room for them.” (to be fair, Linux does support this particular capability with madvise(MADV_DONTNEED).

Here’s another example: “a mouse interrupt just came in. yes, it’s true that my mp3 decoder (a real-time task, since it’s feeding data to the sound card) is currently synthesizing a frame, but that will only take 20ms of CPU time, and I have a good 100ms of real time left before the next sound card deadline. I know that these mouse interrupts only take about 1ms to fully service, so I will schedule that code now, for the purpose of high GUI responsiveness.”

Or: “this real-time mp3 decoder just took 100ms of CPU time to synthesize this frame, which is longer than the amount of CPU time available between sound card interrupts. this real-time process is unsustainable — we should stop it and warn the user as much.”

It is totally possible to write software that performs this kind of reasoning. The software always decides what to do next, and this kind of reasoning just represents a particularly sophisticated decision function. This is in contrast to the much more primitive decision functions of mainstream OS’s, which operate with almost no real information about tasks except for a static priority and measurements of how much CPU or I/O the process has used in the past. Linux uses this information in very complicated formulas that try to figure out whether a process is “interactive” or not (or at least it used to — it may have been changed since this article was written):

The [Linux] scheduler goes to great lengths to try to identify interactive tasks and to boost their priority accordingly. This process involves numerous strange computations involving a number of magic constants; it is difficult to understand, much less improve. –Linux Weekly News

Current OS’s decide what to do next in ways that are sub-optimal. One reason is what I have already outlined, which is that they don’t have very much information about the tasks on the system except a static priority. Another is that any device driver that handles interrupts has the power to halt progress of the system if they run for too long or disable interrupts. I do not believe that current OS’s impose any limitations on device drivers and interrupt handlers, which (if true) would imply that any driver has the opportunity to halt progress of the system indefinitely.

The sweet spot is surely somewhere between current OS’s and the omniscient OS I was describing before. The solution is to give the OS enough information that it can make intelligent decisions about how to schedule access to scarce resources (CPU time, memory space, and I/O bandwidth), without needing to give it so much information that the interfaces are complicated and the coupling too tight.

Here’s an easy example: if I am an audio editor trying to playback 10 tracks in real-time, I should be able to tell the OS “starting now, I need X MB of disk bandwidth per second, and if you cannot sustain that I want to know now.” Also, I expect the OS to prioritize the X MB/s of bandwidth I reserved above everything else, but only up to X MB/s. Apparently XFS has filesystem-level support for this kind of bandwidth reservation, but no OS I know of supports this.

It looks like I’m not the first person to have these sorts of ideas. I haven’t read the paper in detail, but it looks like some guys from CMU had these ideas ten years ago, and published them in a paper called A Resource-Centric Approach To Multimedia Operating Systems (warning, PostScript). Because ultimately, OS’s are all about divvying up access to scarce resources.

A final thought: it’s often repeated that most of the worthwhile ideas in computer science were discovered decades ago, and that all the “new” things these days are just reworkings of the same old ideas. It would follow that what’s really valuable is compelling implementations of these ideas. This bodes well for me, I think, because I excel at implementations. I like to survey the landscape of ideas, separate the wheat from the chaff, and build systems based on the best ideas. That is what I hope lies ahead for me.