The Tar Pit

The last time I visited the field of operating system design, I concluded that journey with questions. That line of questioning didn't solve much, but merely provided a sort of hierarchy that aims to reconcile current well-established designs, i.e. Unix, with proposed designs from current research, e.g. microkernels, unikernels. I now propose the idea that my previous proposal was utter, unmitigated bullshit. I further propose that current definitions of the term operating system are ill-conceived, and that the problem of how to properly design a general-purpose operating system is in principle unresolvable, first and foremost because there is no such thing as a "general-purpose operating system".

In defining the operating system, let us first defer to our priors. We begin with Tanenbaum¹:

The machine language typically has between 50 and 300 instructions, mostly for moving data around the machine, doing arithmetic, and comparing values. [...] For example, a disk can be commanded to read by loading the values of the disk address, main memory address, byte count and direction [...] into its registers.

To hide this complexity, an operating system is provided. It consists of a layer of software that (partially) hides the hardware and gives the programmer a more convenient set of instructions to work with. [...]

On top of the operating system is the rest of the system software. Here we find the command interpreter (shell), window systems, compilers, editors and similar application-dependent programs. It is important to realize that these programs are definitely not part of the operating system, even though they are typically supplied by the computer manufacturer. [...] The operating system is (usually) that portion of the software that runs in kernel mode or supervisor mode. [...] Compilers and editors run in user mode. If a user does not like a particular compiler, he is free to write his own if he so chooses: he is not free to write his own clock interrupt handler, which is part of the operating system and is normally protected by hardware against attempts by users to modify it.

The Modern Operating Systems (MOS) definition goes bottom up from the hardware to the user, and delimits the operating system as the software component running in supervisor mode. I propose that this is at best a confusion in terms (and at worst bullshit): the operating system kernel is indeed the software component residing in supervisor mode, or ring 0, name it what you will. But on what grounds do we state that the kernel is equivalent to the operating system in its entirety? "Andrew Tanenbaum is a god in the field of distributed systems" is not an argument, or at least not one worth taking into account.

Then Tanenbaum sets to make politics instead of science. Despite being a proponent of the microkernel design, he decides that the user may modify their compiler, but not their kernel. To which we humbly ask, on what fucking basis? I can readily invalidate this argument on any GNU/Linux box that I own, and thus there it is, GNU/Linux -- not just Linux! -- is an operating system.

Then later (not quoted here) Tanenbaum mentions embedded OSes, but he does not mention, say, Sinclair BASIC, which is technically speaking an operating system, despite the fact that it does not reside in a special supervisor mode. How do we delimit the operating system from the application base in that case? Are ZX Spectrums (or say, Lisp machines) embedded systems and I didn't know?

Since MOS does not even get close to satisfying our intellectual curiosity, we move on to Silberschatz et al.'s² Operating System Concepts, aka OSC:

We have looked at the operating system's role from the views of the user and of the system. How, though, can we define what an operating system is? In general, we have no completely adequate definition of an operating system. Operating systems exist because they offer a reasonable way to solve the computer problem of creating a usable computing system. [...]

In addition, we have no universally accepted definition of what is part of the operating system. A simple viewpoint is that it includes everything a vendor ships when you order "the operating system". The features included, however, vary greatly across systems. [...] A more common definition is that the operating system is the one program running at all times on the computer (usually called the kernel), with all else being systems programs and application programs. This last definition is the one that we generally follow.

Here the authors try to give a more rigorous definition, but they admit in failing to do so. Indeed, there is no clear delineation of where the operating system ends and the service or the application starts; but this is not a matter of acceptance, but one of properly defining our notions so as to not muddy our understanding of this universe. And yet, Silberschatz et al. end up confusing the kernel with the OS again, and then they go on writing an entire book on the subject³.

Given the lack of a proper definition, we, as educated people, are left with the unpleasant task of figuring one out ourselves. Fortunately though, the previous definitions are not entirely wrong, they are merely crooked. The operating system is, as Tanenbaum points out, a set of abstractions, given that e.g. most of the time the user doesn't have the time to deal with processor interrupts and task scheduling. These abstractions, as Silberschatz et al. point out, may be implemented as programs meant to assist a human operator, i.e. user⁴, in the operation of a computer system.

Fundamentally, the set of abstractions that make up an operating system comprises two classes of items: first, a language to be employed by the user; then, a set of operation tools, which tools may be either general-purpose, or on the contrary, very specific, depending on the system and on the task that the user wants to achieve. Does this description sound familiar? Well, it should, because we've just described the key elements of any general-purpose programming language out there. And that's fine, because formal languages and automata are isomorphic!

So, is the C programming language an operating system? That sounds like a stupid proposition. I don't know about C, but isn't Unix an operating system? All *nixes are specified by the UNIX standard, also known as IEEE Std 1003.1™, also known as POSIX.1. In fact, the UNIX standard specifies an operating system at two levels, both of which rely on a common set of definitions. The first level is the system interface, usually employed by C programmers to write e.g. system applications such as web servers; the language here is thus usually C, while the tools are the system API. The second level is the shell interface, which includes the shell command language, some built-in utilities such as echo and set, and a set of general-purpose utilities such as ls, awk, grep etc. This, all of this, represents the UNIX operating system -- notice how I haven't mentioned "kernel" or "supervisor mode" anywhere, because these are implementation details which may vary from one system to another.

What other operating systems do we have at our disposal, then? Let's enumerate a few more.

Is Java an operating system? Again, I don't know about the language itself, but Java, the JVM run-time and the libraries do form an operating system. The same goes for most Common Lisp implementations, which may in some cases require some extensions for e.g. threading, but are otherwise operating systems in their own right. What about Emacs then? Yes, Emacs is an operating system built on top of a text editor, and I'm not even joking: I am writing this text, using IRC, sending e-mails, organizing notes and setting up music playlists, all from Emacs, so that makes it very much a general-purpose OS.

Notice how all these systems make use of general-purpose tools, which is what makes them systems, as opposed to appliances, which use only specific tools. However, each operating system differs from another in some specificity or another. For example, TeX and its tools form an operating system, and while theoretically they can be used for any task, in practice they are used for typesetting. Similarly, web browsers are operating systems, generally exposing JavaScript as their language, but we don't use them for... in fact, people are using them for all sorts of applications nowadays, so who am I to judge. Similarly, Excel is an operating system for data-flow applications, etc.

This then kills the myth of the general-purpose operating system. If there were such a thing, then it is conceivable that we would now use GPOS instead of GNU/Linux, Chrome OS, MacOS or SLIME -- and when I say "if there were", I mean that there exists no such thing in the observable universe, and until someone proves the opposite, I reserve the right to remain very skeptical. And since there is no such thing, we are left with operating systems which are only somewhat general-purpose, but which in fact differ very much in the way they work and/or the tasks they are suited for. Their particular organization is of course interesting -- they are nested, or co-located on the same hardware, and they often communicate in various ways from which stem such and such complexities -- but all these are details that must be taken precisely as the details they represent.

Thus, this essay untangles some concepts, laying a (not in any way novel, mind you!) foundation for designing operating systems that do not suck. Please to properly cite these ideas in your paper, or else.

Filed under: computing.
RSS 2.0 feed. Comment. Send trackback.