Exterminate All Operating System Abstractions (1996) [pdf](cs.berkeley.edu)
cs.berkeley.edu
Exterminate All Operating System Abstractions (1996) [pdf]
http://www.cs.berkeley.edu/~brewer/cs262b/hotos-exokernel.pdf
11 comments
One of the few times they learn from the past (VM/370) with good results. Moving along that spectrum, they'll security-related projects that did this while enforcing a security policy on the processes or guests. KeyKOS nanokernel architecture is one. VAX Security Kernel is another more like what people do today. Start with most robust design, then optimize from there.
Seems similar to the direction DirectX has taken lately?
DirectX and Vulkan are perfect examples of the exokernel philosophy. Another good example is the evolution of X11, culminating with Wayland, where applications draw the UI themselves using libraries instead of sending primitive draw commands to a server.
Abstractions are important as they reduce complexity, and simplify operations.
The foundation of computing is based off abstraction - using layers and interfaces to hide complexity, so developers can focus on higher-order problems.
This article argues against abstractions citing security, performance and cost. But time and again it has been shown that most costly component in software is human time - and simplifying the underlying architecture is worth the trade-offs
The foundation of computing is based off abstraction - using layers and interfaces to hide complexity, so developers can focus on higher-order problems.
This article argues against abstractions citing security, performance and cost. But time and again it has been shown that most costly component in software is human time - and simplifying the underlying architecture is worth the trade-offs
Abstractions are important as they reduce complexity, and simplify operations.
...but only when used correctly. Abstraction is a means to an end, not the end itself. Unfortunately, years of CS education seem to have taught most people that it's the other way around, causing massive increases in design complexity that are only justified by dogmatic adherence to "more abstraction is better". Some programming language communities are more disposed to this effect than others (e.g. Java.)
Correct application of abstraction is not common in mainstream software, and rather difficult to describe, but the simplicity and clarity is unmistakable when one encounters it. The occasional articles on HN about seemingly impossibly tiny programs are good examples.
This article is a bit "X considered harmful" reactionary but I see their point - often, software today is on the side of far too much abstraction.
...but only when used correctly. Abstraction is a means to an end, not the end itself. Unfortunately, years of CS education seem to have taught most people that it's the other way around, causing massive increases in design complexity that are only justified by dogmatic adherence to "more abstraction is better". Some programming language communities are more disposed to this effect than others (e.g. Java.)
Correct application of abstraction is not common in mainstream software, and rather difficult to describe, but the simplicity and clarity is unmistakable when one encounters it. The occasional articles on HN about seemingly impossibly tiny programs are good examples.
This article is a bit "X considered harmful" reactionary but I see their point - often, software today is on the side of far too much abstraction.
" Unfortunately, years of CS education seem to have taught most people that it's the other way around, causing massive increases in design complexity that are only justified by dogmatic adherence to "more abstraction is better"."
Abstractions only create design complexity when they are applied incorrectly. Abstractions should scale horizontally across a layer of the software stack (VMs, Storage - NFS, APIs, etc). If you're create a single-use abstraction, it's not really an abstraction but a complexity
Abstractions only create design complexity when they are applied incorrectly. Abstractions should scale horizontally across a layer of the software stack (VMs, Storage - NFS, APIs, etc). If you're create a single-use abstraction, it's not really an abstraction but a complexity
NFS is pretty much a canonical example of a poor abstraction.
The real problem with abstractions it promotes the lowest common denominator. If you have lots of different storage options, an abstraction will try to abstract them and create a standardized interface.
But this is a trade-off. The real benefit comes in simplifying the programming model and not forcing developers to read through manuals figuring out how to flip a bit on a hard drive. Instead, they can leverage open-source and libraries that rely on that standardization to deliver most of the value (with a small perf hit)
But this is a trade-off. The real benefit comes in simplifying the programming model and not forcing developers to read through manuals figuring out how to flip a bit on a hard drive. Instead, they can leverage open-source and libraries that rely on that standardization to deliver most of the value (with a small perf hit)
"It is important
to note that we favor abstractions, but they should
be implemented outside the operating system so that
applications can select among a myriad of implementations or, if necessary, roll their own ."
What is an operating system if not an abstraction of the hardware?
The idea is to multiplex, not abstract. To illustrate the difference, say you have an OS that runs only applications written in JVM bytecode. This is an abstraction: the OS is providing a different interface (bytecode) than the actual hardware interface (machine code).
Most OSes don't do anything like this. They allow applications to be written in raw machine code. The applications run as if they had full control over the CPU hardware. The OS then multiplexes the CPU by saving and restoring the program counter (and, typically, the rest of the registers and CPU state as well, though the exokernel design in this paper doesn't even do that). The idea is to (as much as possible) provide the same interface as the underlying hardware provides, then do a little extra work to make sure different applications aren't stepping on each other's toes.
Most OSes don't do anything like this. They allow applications to be written in raw machine code. The applications run as if they had full control over the CPU hardware. The OS then multiplexes the CPU by saving and restoring the program counter (and, typically, the rest of the registers and CPU state as well, though the exokernel design in this paper doesn't even do that). The idea is to (as much as possible) provide the same interface as the underlying hardware provides, then do a little extra work to make sure different applications aren't stepping on each other's toes.
It's more like the CPU has a multiplexing interface and the OS is managing that. Applications are not run in the same environment as the OS is.
I think they're arguing that the OS should be the minimum software representation of the hardware necessary for "secure multiplexing", and any abstractions/layers after that should be per-application as needed (and only as needed).
Certainly you can call that minimal representation an abstraction as well, but I'm not sure it's helpful in this context, since it seems clear enough what they're arguing against.
Certainly you can call that minimal representation an abstraction as well, but I'm not sure it's helpful in this context, since it seems clear enough what they're arguing against.
I came to this thread to argue exactly this - pleased you did it for me! My issue is 1) They do not acknowledge the need for this "initial minimal abstraction" and 2) I'm not so sure that it would be so minimal.
The issue comes when you try to define "safe multiplexing". Take for instance a spinning disk drive. If we took this at face value, every application would know about things like sectors and seek times. Presumably this would permit some sort of domain-specific optimisation (that, say, a database engine might use). Perhaps we posit that programs that don't need such specialisation use a library for disk access. So far so good.
Now what is it the OS is trying to multiplex? No longer abstract, high-level concepts like "write this data to this file", which it can safely mess about with because it knows what they mean; no, it has to multiplex read head seeks. It cannot have any awareness of the meaning of these seeks (that was the point of the exercise!) so it can't really be more intelligent than a "dumb multiplexer". So your finely tuned database application has its clever read head optimizations all shot to hell whenever literally anything else touches the disk.
In order for an OS to multiplex hardware resources efficiently, it needs to have some idea of what the applications are trying to accomplish, so it stands the best chance of giving it to them.
For what it's worth, I also find the paper rather hot headed and light on concrete examples.
The issue comes when you try to define "safe multiplexing". Take for instance a spinning disk drive. If we took this at face value, every application would know about things like sectors and seek times. Presumably this would permit some sort of domain-specific optimisation (that, say, a database engine might use). Perhaps we posit that programs that don't need such specialisation use a library for disk access. So far so good.
Now what is it the OS is trying to multiplex? No longer abstract, high-level concepts like "write this data to this file", which it can safely mess about with because it knows what they mean; no, it has to multiplex read head seeks. It cannot have any awareness of the meaning of these seeks (that was the point of the exercise!) so it can't really be more intelligent than a "dumb multiplexer". So your finely tuned database application has its clever read head optimizations all shot to hell whenever literally anything else touches the disk.
In order for an OS to multiplex hardware resources efficiently, it needs to have some idea of what the applications are trying to accomplish, so it stands the best chance of giving it to them.
For what it's worth, I also find the paper rather hot headed and light on concrete examples.
Secure multiplexing, VM's, and kernels were repeatedly done back in 80's and 90's under the Computer Security Initiative. See p5 on this one for an example where trusted functions efficiently did I/O multiplexing requests (syscalls) from untrusted drivers in guest OS's:
http://www.cse.psu.edu/~trj1/cse543-f06/papers/vax_vmm.pdf
You can ignore the security kernel and MLS stuff while imagining something simpler there. However, the design and assurance strategies for that one have yet to be topped by modern virtualization products.
Here's a modern approach to secure I/O with a nice list of others in Related Work:
http://repository.cmu.edu/cgi/viewcontent.cgi?article=1328&c...
Have fun with those.
http://www.cse.psu.edu/~trj1/cse543-f06/papers/vax_vmm.pdf
You can ignore the security kernel and MLS stuff while imagining something simpler there. However, the design and assurance strategies for that one have yet to be topped by modern virtualization products.
Here's a modern approach to secure I/O with a nice list of others in Related Work:
http://repository.cmu.edu/cgi/viewcontent.cgi?article=1328&c...
Have fun with those.
I think most applications would use a shared file system, just as they do today, including all the same optimisations. But your high performance database would likely be given its own disk to work with. (Just as you would today, but the benefits of giving a whole disk to a process in exokernel land are theoretically greater.)
The authors went on to implement a couple systems that handle that problem rather nicely. Applications (really, the libraries they use) do know about disk sectors, but the kernel's disk driver sorts their requests to optimizes seeks and exposes which sectors are loaded, to allow a kind of cooperative disk cache.
Even more interesting, they let applications share file systems by taking a bytecode-based representation of FS metadata from userspace, and using that to enforce correct usage of the actual disk blocks. This lets applications control where on the disk to allocate, when to read which blocks, etc. without losing any of the security and cooperation of a typical file system.
Even more interesting, they let applications share file systems by taking a bytecode-based representation of FS metadata from userspace, and using that to enforce correct usage of the actual disk blocks. This lets applications control where on the disk to allocate, when to read which blocks, etc. without losing any of the security and cooperation of a typical file system.
They are making 2 separate arguments then. What they are arguing against is standardization, which is just as important
Addressed in Section 4, Question 3.
The question remains if companies and developers value or care about the flexibility of creating "page table rules".
For highly scalable systems, the perf trade-off is just a matter of spinning up more VMs.
The higher-order benefit is you can expect your operating system and VM to behave the same, no matter what
For highly scalable systems, the perf trade-off is just a matter of spinning up more VMs.
The higher-order benefit is you can expect your operating system and VM to behave the same, no matter what
Spinning up more VMs costs more. That was a bigger issue in 1996 than now, but still an issue for large deployments.
[deleted]
Now, correct me if I'm wrong, but haven't we essentially got the exact opposite direction and strengthened the abstractions separating hardware and apps? I would assume elimination of abstractions would reduce portability unless suddenly the market moved to a unified hardware architecture, while we've gone the other way; we have numerous platforms of hardware AND software, and code is generally more portable than ever before due to the use of standardized languages and APIs.
The paper says to move the abstractions, not eliminate them.
> It is important to note that we favor abstractions but they should be implemented outside the operating system so that applications can select among a myriad of implementations or if necessary roll their own
For example, if my software doesn't like the OS's abstractions for networking, let me go find one that I do like and use it instead.
> It is important to note that we favor abstractions but they should be implemented outside the operating system so that applications can select among a myriad of implementations or if necessary roll their own
For example, if my software doesn't like the OS's abstractions for networking, let me go find one that I do like and use it instead.
Addressed in Section 4, Question 2.
… in which the authors describe application level device drivers to map between the physical hardware and a presumably common abstract interface. That doesn't seem to change the world much over a kernel device driver mapping to a common abstract interface, except that you can implement a different common abstract interface if you wish. You'll just have to write new drivers for all the cards. This is fine for experimentation, but not nice for production.
I think the ground shift between 1996 and now is the democratization of kernel code. These mysterious "kernel architects" referenced in the paper who handed down a system from on high are now any decent C programmer with an itch to scratch. If you don't like the Linux/*BSD/whatever abstractions given to you, then make your own. If people like it and it doesn't offend an influential developer it can even be widely deployed.
I think the ground shift between 1996 and now is the democratization of kernel code. These mysterious "kernel architects" referenced in the paper who handed down a system from on high are now any decent C programmer with an itch to scratch. If you don't like the Linux/*BSD/whatever abstractions given to you, then make your own. If people like it and it doesn't offend an influential developer it can even be widely deployed.
I disagree. It's much harder now to scratch your itch than ever before. You can see it in how people like Linus Torvalds have an almost demigod status in that kernel hacking is considered to be a highly arcane activity. This is in stark contrast to the past, where writing operating systems was a much more mundane and common activity, not unlike writing your own web framework today.
Certainly some shortcuts like DDE, rump kernels and emerging flavors of libOS are now coming around, but it's still an uphill battle.
Certainly some shortcuts like DDE, rump kernels and emerging flavors of libOS are now coming around, but it's still an uphill battle.
writing operating systems was a much more mundane and common activity
[citation needed] - outside of academic environments. I suppose the embedded environment might count as building your own micro-operating system (only one task? don't bother with a scheduler etc).
[citation needed] - outside of academic environments. I suppose the embedded environment might count as building your own micro-operating system (only one task? don't bother with a scheduler etc).
Just look at the Wikipedia Timeline of Operating Systems with special attention to number of distinct OS's in any given time period. You'll find it drops off sharply as it nears the present if you count stuff that was actually deployed or in working condition. Well, that was the situation when I looked at it a year ago. Hopefully you come back with good, contrary news. :)
Another example is sheer amount of dead, search results I get for OS projects on sites that track them. Almost all are before 2010 with most closer to the late 90's. I'm not sure why this is but there's just hardly anyone doing it anymore. Maybe it's because they google it and see how hard it is with all the dead projects. ;)
Another example is sheer amount of dead, search results I get for OS projects on sites that track them. Almost all are before 2010 with most closer to the late 90's. I'm not sure why this is but there's just hardly anyone doing it anymore. Maybe it's because they google it and see how hard it is with all the dead projects. ;)
Kernel hacking was always arcane, the original greybeard wizard stereotype. With the modern Internet community it became more accessible. At the same time, a million JS webdevs ALSO appeared to work on the big was.
This is one of the first papers introducing exokernels. The paper argues for breaking the shackles of OS abstraction and giving direct, (but mediated), control to the programs.
I like the idea, and am experimenting with it in my own OS. In the mainstream world, we see this paper's goals partially appearing with the people who give a network card directly to a server process in Linux.
If they said which architecture there were thinking about, I missed it. On x86 without IOMMU I can't think of any card I would trust. IOMMU implementation is so spotty I'm not sure I'd trust it either. There is a great deal to be said for keeping the device access locked away in the kernel where you know which features of the card you will use, and if it has a mode that lets it scribble elsewhere in memory, so aren't using it.
I like the idea, and am experimenting with it in my own OS. In the mainstream world, we see this paper's goals partially appearing with the people who give a network card directly to a server process in Linux.
If they said which architecture there were thinking about, I missed it. On x86 without IOMMU I can't think of any card I would trust. IOMMU implementation is so spotty I'm not sure I'd trust it either. There is a great deal to be said for keeping the device access locked away in the kernel where you know which features of the card you will use, and if it has a mode that lets it scribble elsewhere in memory, so aren't using it.
Yes, but do software companies really care about "giving direct, (but mediated), control to the programs".
What is the trade-off between that, and the added complexity in understanding all the different ways you can program something?
IMO, developers want a simple and standardized model to build applications on operating systems so they don't have to care about the internals.
This article represents a marginalized view by the larger industry as a whole.
What is the trade-off between that, and the added complexity in understanding all the different ways you can program something?
IMO, developers want a simple and standardized model to build applications on operating systems so they don't have to care about the internals.
This article represents a marginalized view by the larger industry as a whole.
Nobody is saying we should write all our programs directly against hardware. The point of the paper is that the operating system should let applications define their own abstractions. This is already standard practice for the CPU: the OS lets applications run machine code directly, and you can use whatever language you'd like to generate that machine code.
You can still have a standardized model for writing software. The argument is against baking this standardized model into the kernel, where it will stick around for decades, unable to be changed.
You can still have a standardized model for writing software. The argument is against baking this standardized model into the kernel, where it will stick around for decades, unable to be changed.
Yes, I 100% understand that point. But I repeat what I'm saying, this isn't a concern for most developers and most software companies. They don't care how a page table is written. They don't care about optimizing that.
Every standard or abstraction can be unbundled into multiple standards or abstractions. But at the end of the day, what wins is something that's simplest to the operator
Every standard or abstraction can be unbundled into multiple standards or abstractions. But at the end of the day, what wins is something that's simplest to the operator
You're not really contradicting anything, you're just making an argument from personal incredulity. People do care, you may not. Else the Linux kernel would have had a fraction of its manpower and no one would want to introduce userspace page fault handling (just recently userfaultfd(2) went in from a KVM optimization effort) or use userland TCP/IP.
When the authors talk about applications having their own OS, I think they have in mind infrastructure programs like databases and web servers: complex, low-level programs that have domain-specific needs from the hardware and can gain greatly by using it only in the way that they need to.
They obviously don't mean that every CRUD app should build its own OS, since that would be absurd.
They obviously don't mean that every CRUD app should build its own OS, since that would be absurd.
A database is a good example. For example, a database engine might benefit from being able to read large raw blocks from a disk and directly optimizing its own disk seeks, rather than using the common abstraction of a file as being just a stream of bytes.
You're right: it was proven with the invention of object-based, disk storage that kept things simple. Think NoSQL key-value stores vs common SQL databases in performance. Eliminating complexity in the underlying mechanism while allowing the app to decide how it's used can certainly benefit performance.
But every CRUD app can links in its own OS as a standardized library.
I agree with you, and here is one more concern: a lot of hardware can't be shared at the hardware level. Think of the soundcard for example. A lot of PCs have simple Intel-HDA audio controllers that don't have hardware-level separate streams. You need a software defined mixer that will share the resource with several applications. For years and years on Linux the situation was that you do get direct hardware access and it sucked balls. Either your card has hardware mixing and you can play like 8 sounds at once, or it doesn't and you can't. In that time, at least 3 different userspace mixers appeared, all incompatible with each other, which of course means that your choice of Gnome vs KDE also dictates which music players you can use.
The OS absolutely needs to define standard usage APIs so we don't end up in the situation where everybody rolls their own. Yes, giving applications bare-metal access is good. But that's a minority of applications in a minority of usage cases. Give people a good simple API for the average case, and THEN let them take exclusive low-level control when they need it.
The OS absolutely needs to define standard usage APIs so we don't end up in the situation where everybody rolls their own. Yes, giving applications bare-metal access is good. But that's a minority of applications in a minority of usage cases. Give people a good simple API for the average case, and THEN let them take exclusive low-level control when they need it.
IOMMUs might have been standard fare in the workstation hardware of the day. SPARCs had them at least.
SCOMP, A1 secure system of 19??-1985, invented them far as I know. It's one of those old concepts that was ignored repeatedly and re-discovered. Thing is, they left off most of the other good feature and assurance activities Orange Book taught. They're in the process of slowly re-discovering those with "timing-related, side channels" being one. Early Orange Book candidates knocked out "covert timing channels" with mandated, covert, channel analysis back in the 1980's-90's, including for virtualization.
I'm just waiting for the rest to be re-discovered by mainstream so we can get on with it and build a secure platform with significant developer support.
SCOMP Final Report (see p17 of PDF or p9 of document on I/O) http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDo...
I'm just waiting for the rest to be re-discovered by mainstream so we can get on with it and build a secure platform with significant developer support.
SCOMP Final Report (see p17 of PDF or p9 of document on I/O) http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDo...
One of the paper's authors, Dawson Engler, went on to found Coverity.
Very interesting: this is directly analogous to something that happened in Java: people started out writing native code to conform to a standard Java interface. They ended up writing Java that mapped to the native code very closely, and then abstracted all of those implementations in Java. SWT is the poster child for this movement, but it happened in other places too.
"The poor reliability, poor adaptability, and poor performance of operating systems would be acceptable if applications could just ignore the operating system and implement their own abstractions."
My first thought was that it seems like we have this these days with VMs, although that can still be fairly complicated to set up due to the way that VMs reliably partition hardware resources. Skimming a bit further I see this is in some ways the opposite of what they have in mind, which is to even be able to save registers in a different "process".
I tend to think that operating systems don't provide enough isolation rather than too much. I don't care too much about how they go about implementing that. I can see the appeal of a more flexible OS implementation, but I don't agree about what the OS should ultimately provide.
I wouldn't mind seeing default-available VMs that are treated more like applications in terms of resource availability and scheduling. It seems like this would at least partly address many of the concerns within a monolithic kernel design.
Can anyone recommend other good papers on exokernels? I feel like I'm not really getting it yet.
My first thought was that it seems like we have this these days with VMs, although that can still be fairly complicated to set up due to the way that VMs reliably partition hardware resources. Skimming a bit further I see this is in some ways the opposite of what they have in mind, which is to even be able to save registers in a different "process".
I tend to think that operating systems don't provide enough isolation rather than too much. I don't care too much about how they go about implementing that. I can see the appeal of a more flexible OS implementation, but I don't agree about what the OS should ultimately provide.
I wouldn't mind seeing default-available VMs that are treated more like applications in terms of resource availability and scheduling. It seems like this would at least partly address many of the concerns within a monolithic kernel design.
Can anyone recommend other good papers on exokernels? I feel like I'm not really getting it yet.
The canonical paper is "The Exokernel Operating System Architecture", which came out two years later by the same author: http://u.cs.biu.ac.il/~wiseman/2os/microkernels/exokernel.pd...
Xen is loosely based on a Cambridge research exokernel called Nemesis[1] (a very long time ago I toured the Cambridge lab and watched a cool demo of Nemesis doing some image recognition). However the evolution of Xen didn't really lead to everyone using exokernels - even if you're running your VMs on AWS, and therefore using Xen, you're not using an exokernel in the sense of this paper.
MirageOS is another project following in the same tradition, but again things have moved on and it's a unikernel which has aspects like an exokernel (choose your own abstractions), but also aspects that are radically different (no userspace and everything linked into a single image).
[1] https://www.cl.cam.ac.uk/research/srg/netos/papers/2003-xens...
MirageOS is another project following in the same tradition, but again things have moved on and it's a unikernel which has aspects like an exokernel (choose your own abstractions), but also aspects that are radically different (no userspace and everything linked into a single image).
[1] https://www.cl.cam.ac.uk/research/srg/netos/papers/2003-xens...
[deleted]
Pushing operating system abstractions into user-space was pretty much what IBM's VM/370[1] operating system did (starting in the late 1960s!). VM/370's control program (CP), which would be the "kernel" in today's terminology, controlled the physical hardware resources. Each "process" running under CP was a virtual machine whose operating system API was mostly just the IBM/370 instruction set (i.e., no abstraction above the hardware architecture). For example, CP provided only a virtual disk drive that you could manipulate with machine instructions like SIO (Start I/O) - the file system was implemented by the code running in user space. You could actually run a different guest operating system (i.e., a different set of OS abstractions at user level) on each virtual machine.
The authors of this paper do mention VM/370 in their "Related Work" section (page 5). They say their approach is similar, except that they "export" hardware resources rather than emulating them, which is more efficient.
[1] https://en.wikipedia.org/wiki/VM_%28operating_system%29
The authors of this paper do mention VM/370 in their "Related Work" section (page 5). They say their approach is similar, except that they "export" hardware resources rather than emulating them, which is more efficient.
[1] https://en.wikipedia.org/wiki/VM_%28operating_system%29
And KVM/370 was first to do it with some security. Unfortunately, people need ACM/IEEE membership for those papers. At least VAX VMM Security Kernel papers are still around. Pretty much anything Karger wrote will help new efforts. :)