Exokernel
CS450-002: Operating Systems
Fall 2003
Jennifer Rose, Daniel Stanaland, Amy Turlington
Table Of Contents
Table Of Contents
Introduction
Overview
Resource Management
Memory Management
File Management
Privileged Instructions
Data Structures
Process Model
Scheduling
Mutual Exclusion
Deadlock
Summary
Bibliography
Exokernel - Page 1 of 7
Introduction
An operating system is a program that runs on a computer, betweenthe hardware of a computer and the applications a user might run. There are any number of operating systems, both in current use and having passed into obsolescence. The design of these operating systems varies greatly; some are batch systems, others are multiprogrammed; some use a command line interface, others have GUIs; some are for use on mainframes, others for personal computers. What all operating systems have in common is that they act as some kind of interface between hardware and applications.
Overview
Far from being simply another operating system, MIT’s exokernel is a departure from the standard view of operating system design. In fact, Exokernel is not, strictly speaking, an operating system, as much as a innovation in kernel design, going a step beyond the concept of a microkernel.
Traditionally, the purpose of the kernel has been to both multiplex and abstract hardware resources, giving applications predefined interfaces.This is shown both in monolithic kernels and in microkernels, such as Mach. The exokernel, on the other hand, is based on the philosophy that abstracting resources limits their speed, flexibility, and usefulness. Consequently, an exokernel merely multiplexes resources, and places abstractions for resource management in the user-space. This allows for application level libraries to customize interfaces for such things as interprocess communication or virtual memory management.
The result is an operating system which is extremely fast and flexible, although complicated to implement.
Resource Management
One of the unique things about an exokernel is the way it manages physical resources. It doesn’t. That is, the kernel itself does not manage the resources. Memory and file management are performed almost exclusively on the application level, the exception being what is needed for protection.
Memory Management
“Physical memory is one of the simplest resources to multiplex,” (Engler, 1998). It is carried out, like most resources, extensively in user space. For example, when an library-level OS (such as ExOS) “allocates a physical memory page, the exokernel records the owner and permissions (e.g., read and write) of the allocating process. The owner of a page has the power to change the capabilities associated with it, to share it, and to deallocate it,” (Engler, 1998). Thereafter, accesses to the memory page are guarded by the exokernel, requiring capability for any admittance.
Analogousprotections are used if a TLB (translation look-aside buffer) or a page-table interface are defined by the underlying hardware. All other management of memory is left to the library-level OS and applications.This is noteworthy, since with Aegis, the exokernel for MIPS architecture, applications can define their own page tables. This is not the case with Xok, the exokernel for the Intel x86 architecture, since it uses hardware defined page tables, but applications are still able to control page attributes.
File Management
File systems are also defined at the library level. The exokernel has similar responsibilities with file management as it does with memory management. Multiplexing the disk in a secure, powerful way is, however, a difficult task. Access control presents the hardest problem. The solution to this problem is to rely on the file systems themselves to keep track of which disk blocks they can use, and enforcing correctness on the bookkeeping data structures within the file system.
Privileged Instructions
Exokernelsare unique is the way that it handles privileged instructions. Privileged instructions are instructions that could cause harm, and therefore are only available to be used by a selected portion of applications. Traditional operating systems have trusted and untrusted applications, those that are and are not allowed to execute privileged instructions. Exokernel tries to allow the applications as much power and control as possible, and because of this “applications have access to privileged instructions,” (Engler, 1998). “Exokernels separate protection from management: they protect resources but delegate management to applications. For example, each application manages its own disk-block across all applications. Thus, the exokernel protects pages and disk blocks, but applications manage them,” (Kaashoek et al., 1997). This is different because in “traditional” operating systems, untrusted applications cannot manage system resources. This could be a potential problem because “the implementation of such an interface would need to resolve all tradeoffs and anticipate all ways the interface could be used,” (Kaashoek et al., 1997). Exokernel implementation reduces the work of the kernel in terms of the tradeoffs, and allows for more power to the untrusted applications.
Data Structures
In order for an operation system to run it must keep track of different kinds of information necessary for managing processes, memory, and files. The information needed is stored in data structures. For example, when processes are taken in and out of main memory, by the scheduler, certain information must be known to restart the process. The exokernel saves "application specific data [that] can be associated with" each process. This data includes the "record of the numeric id of a process's parent, it's running status, and program name" just to name a few. With this data the operating system can make the best use of its resources by having the ability to temporally remove processes from main memory and restore them as if nothing happened (Engler, 1998). The process scheduler also employs a unique data structure called a quantum, which is employed in a vector, which will be discussed in greater detail in the scheduling section.
The same type of data structures are needed to appropriately manage memory. As process are created, taken in and out of main memory, and then finally completed how memory is managed is very important. The exokernel keeps track of a number of data structures to ensure that memory is managed correctly. Some of these include, “freelists, disk arm positions, and cached TLB (Translation look-aside buffer)…” (Engler et al., 1995). It is also set to “record an approximate least-recently-used ordering of all physical pages….[and] resource attributes such as the number format and current set of the TLB mappings or the number and size of incoming and outgoing network buffers,” (Engler, 1998).
For the management of the files, exokernel also does something very special and unique. This “comes from noticing that correct applications track what resources they have access to, rendering operating system bookkeeping redundant” (Engler, 1998) So instead of making a new set of data structures the operating system reuses the applications data structures. For “file systems,… the exokernel can reuse the library file system's ‘meta data’ [which is] the data structures it uses to map files to blocks,” (Engler, 1998).
Process Model
The process model for the exokernel is simple, due to application-level control. The terms “process” and “environment” are used interchangeably; a process (or environment) is a minimal set consisting of capabilities, entry points, a page table, accounting information on the process, and a u-area for miscellaneous data. Each process handles its own sub-processes, or threads. The kernel does not work with the threads of a process, as it only is concerned with the process itself (Pinckney, 1998).
Scheduling
With an exokernel, CPU Scheduling is very flexible, giving the applications a high degree of freedom. The kernel handles scheduling of processes in a way similar to round-robin; each process is allowed a fixed time quantum, and with that time slice they may use their own scheduling algorithms to schedule the sub-processes. The kernel notifies processes when the time quantum is up and expects the processes to handle saving the process state, as in the register contents and other data for the process. Processes are responsible for context-switches, instead of the operating system being responsible, keeping with the idea of leaving management decisions to the applications (Engler et al., 1995).
The series of time slices are organized into a circular array, and the number of ticks of a time slice is a fixed number determined by the system clock. Notification of the environment of the beginning of the time slice is done with prologue code and the end with epilogue code (Engler et al., 1995). The prologue and epilogue code are stored in the u-area of each process. Processes may also give up the remaining part of their time slices to other processes if they finish before the time quantum is up. If a process is “sleeping” (waiting), the time slice allotted to it is just skipped over. A sleeping process relies on another process to wake it up, unless it uses wakeup predicates (Pinckney, 1998).
An application may insert a wakeup predicate, which is basically a Boolean expression, into the kernel and remain sleeping until the condition is satisfied. Once the Boolean expression is evaluated to true, the application wakes up and is scheduled. Wakeup predicates are useful in the exokernel, since most of the operating system functionality is in the applications and not the kernel itself (Kaashoek et al., 1997).
Mutual Exclusion
The exokernel relies on libraries to implement typical operating system abstractions, such as protected sharing.Mutual exclusion is accomplished by processes having strong critical sections. This is accomplished by disabling software interrupts (for example, an upcall to end a time slice). Critical sections are used instead of locks, so processes do not have to communicate with each other to manage locks or use special algorithms if a process terminates while holding a lock.
Protected sharing is also achieved by using software regions, capabilities, and wakeup predicates. Software regions are areas of memory accessible only by system calls. Capabilities included in an environment are similar to permissions; a capability must be explicitly specified on a system call, and the capability is checked before access is read or write access is granted to the calling process. If the capability is wrong, the process does not get memory access permission. Wakeup predicates protect against crashed processes disrupting other processes running normally (Kaashoek et al., 1997).
Deadlock
One of the dilemmas of timesharing/multitasking systems is deadlock. Deadlock is a situation whereby process A needs a resource which is held by process B and process B need a resource held by process A thereby stopping both processes from continuing. There are several different ways that an operating system can proactively deal with this stalemate situation: Deadlock Prevention, Deadlock Avoidance, or Deadlock Detection-and-Resolution. Alternately, deadlock can be ignored, in the event that it happens. One example of how exokernel deals with the problem of deadlock is by the way it handles the deadlock of spin-waiting processors in a multiprocessor system. "Deadlock is avoided easily: when a processor spin waits for a response, it periodically checks its message queue for pending messages," (Benjie, 2000). This is called Deadlock Detection-and-Resolution. This means that even though exokernel allows a state of deadlock to occur for, it is for a short time. It periodically checks its message queue, and takes action to remedy the deadlock. The message queue consists of inter-processor communications, which allow the processors to communicate. This is an example of how, in a multiprocessor situation, exokernel handles deadlock.
Summary
Exokernels are a very innovative take on operating system design. It has a number of virtues, including speed, efficiency, and flexibility. The powerful adaptability of the exokernel in terms of interface makes it a very good contender for special purpose machines. On the down side, the kernel sacrifices some control over how resources are employed, and the complicated nature of the interface makes the exokernel unsuitable for general use.
Exokernel - Page 1 of 7
Bibliography
Benjie, C. (2000) “Multiprocessing with the Exokernel Operating System.” URL: <Engler, D. (1998) “The Exokernel Operating System Architecture.” URL: <
Engler, D., Kaashoek, M. (1995). “Eliminate All Operating System Abstractions.” Proceedings of the 5th Workshop on Hot Topics in Operating Systems (HotOS-V), 73-83.
Engler, D., Kaashoek, M., O’Toole, J. Jr. (1995). “Exokernel: An Operating System Architecture for Application-level Resource Management.”Proceedings of the 15thACM Symposium on Operating Systems Principles, 251-266.
Kaashoek, M., Engler, D., Ganger, G., Briceño, H., Hunt, R., Mazières, D., Pinckney, T., Grimm, R., Jannotti, J., Mackenzie, K. (1997). “Application Performance and Flexibility on Exokernel Systems.”Proceedings of the 16thACM Symposium on Operating Systems Principles, 62-65.
Lam, I. (1998). “Overview of the Exokernel Operating System.” URL: <
Pinckney, Thomas (1998). “Internal Structure of Xok/ExOS.” URL:
Exokernel - Page 1 of 7