ud702 ยป



So now we set the stage for discussing the spin and the exokernel approaches to achieving extensibility of the operating system without losing out on protection or performance. Both these approaches start with two premises. The first premise, is that micro-kernel based design compromises on performance due to frequent border crossings. And the second premise is that, monolithic design does not lend itself to extensibility. Because of the starting premises of spin and exokernal. Both these approaches have certain commonality in what they strive to do, although the path taken by these two approaches are very different.

What are we Shooting for in OS Structure

So, let's revisit what we are shooting for in the structure of an operating system. We want the operating system strucure to be thin. That is, like a microkernel. That is only mechanisms should be in the kernel, and no policies should be ingrained in the kernel itself. The structure should allow fine-grained access to system resources without border crossing, as much as possible. That is, it should be like the DOS-like structure. That is, it should have a structure similar to what we saw in DOS. And it should be flexible, meaning resource management should be easily morphed to suit the needs of the application without sacrificing protection and performance. So, the flexibility part of it should be similar to what we can get from microkernel based approach, but at the same time we want the protection and the performance we can get with the monolithic approach. So in other words, in a nutshell what we want in the operating structure is performance, protection, and flexibility.

Approaches to Extensibility

We'll now turn our attention to the issue of extensibility and some of the approaches that have been taken to achieve this goal. Historically I should mention that there was interest in extensibility at least as far back as 1981. With a system that was developed at CMU called the Hydra operating system. The Hydra operating system provided kernel mechanisms for resource allocation. The key word is mechanisms, not policies, just mechanisms for resource allocation in the kernel. And it had a way of providing access to resources, using a capability based approach. The notion of a capability has a special conotation in the operating system, literature. And that is, it is, an entity that can be passed from one to the other. Cannot be forged. And can verified. All of the things that you want in order to make sure that. The system integrity is not compromised, as enshrined in this abstract notion of capability. And as originally envisioned, capability was a heavyweight mechanism in terms of implementing it efficiently in an operating system. And because capability is a heavyweight mechanism. The hydra operating system, resource managers were built as coarse-grained objects, in order to reduce the border crossing overhead, because border crossing in the hydra system would mean that you have to pass capability from one object to another. And validate the capability for entering a particular object, and so on, and for that reason, hydra used coarse-grained objects to implement resource managers. That way, they can reduce the border crossing overhead. And implementing resource managers as coarse-grained objects also means that it limits the opportunities for customization and extensibility. In other word, the closer you make these object, the less opportunity you have for customizing the services. Which is exactly the strike against, monolithic kernel as well. So, while in principle, hydra had all the right ideas of providing minimal mechanisms in the kernel. And having the resource managers implement policies because the fundamental mechanism for accessing the resources was through this capability, which is a heavy weight abstract notion to implement efficiently. In practice, hydra did not fully achieve its goal of extensibility. One of the most well-known extensible operating system of the early 90s was the Mach operating system from CMU. It was microkernel-based, providing very limited mechanisms in the microkernel. And implementing all the services that you expect from an operating system as server processes that run as normal, user level processes above the kernel. And clearly, with this micro kernel based approach, Mach achieved its goal of extensibility. So it focused on extensiblity. And portability. The keyword is portability. And therein lies the rub. Performance took a backseat, because Mach was very much focused on making the operating system portable across different architectures, in addition to paying attention to extensibility. And this, unfortunately, gave a bad press for microkernel based design. Because it focused on these twin goals of portability and extensibility, allowing performance to take a backseat. And since operating systems are generally so focused on performance. This design choice in Mach of supporting portability gave microkernel-based design a bad press. But later on, when we look at L3 approach to microkernel-based design, we will revisit the right way to build a microkernel-based design. But in this lesson, let's focus on Spin Approach to Extensibility. So the key idea in spin is to co-locate a minimal kernel with its extension in the same hardware address space and avoid the border crossing between the components of. The kernel and the extensions of the kernels that are containing the specific services that the applications need. And this core location, also means that we avoid the border crossing which he said is one of the biggest potentials for losing out on performance. But, if you're going to co-locate the kernel and extensions in the same hardware address space, isn't that compromising on protection? Wasn't that the strike against the DOS-like structure that we talked about earlier? Well, the approach that Spin took was to rely on the characteristics of a strongly typed programming language, so that the compiler can enforce the modularity that we need in order to give guarantees about the protection. So, by using a strongly typed language, in the case of Spin they used modular three more on that in a minute. The Colonel is able to provide. Well defined interfaces, all of you may be quite familiar with declaring function prototypes in a hydra file and having the actual implementation of the procedures in other files. In a large software project, this is the same idea that is now taken to the design of the operating system itself. After all, operating system is also a piece of software, a complex piece of software, and why not use a strongly typed language as the basis for building the operating system. That's the idea in the spin approach. Now, what you get when you use a strongly typed language, is that you cannot cheat. For instance, in a language like C, you can type cast pointers so that a given data structure can be viewed completely differently, depending on what you need to get done. At the moment. That's not possible with a strongly typed language. Data abstractions provided by the programming language such as an object serve as containers for logical protection domains. That is, we are no longer reliant on hardware address spaces to provide the protection between different services. And the kernel. As I mentioned the kernel provides only the interfaces and these logical protection domains actually implement the functionality that is enshrined in those interface functions. And there can be several implementations of the interface functions. And that's where the flexability comes in. Applications can dynamically bind different implementations of the same interfaith functions. And that's how we get different instanciations of specific system components. Getting you the flexibility that you want in constructing an operating system. Because we have co-located the kernel and the extension in the same hardware address space, we are making the extensions as cheap as a procedure call. So in a nutshell, what we've accomplished with a Spin approach to extensibility as we are writing on the characteristics of a strongly typed programming language, that enforces strong typing and therefore allows the operating system designer to implement logical protection domains instead of relying on hardware address spaces. And consequently we're making extensions as cheap as procedure calls.

Logical Protection Domains

Modula-3 is a strongly typed language with built-in safety and encapsulation mechanisms. It does automatic management of memory. That is, since it does automatic storage management, there are no memory leaks. Modula-3 supports a data abstraction called an object with well defined entry points. Only the entry points are known outside the object, not the implementation of the code for that entry point, or the data structures that are contained within an object. And therefore there's no cheating possible as you can do with a language like C. And modula-3 allows exposing the externally visible methods inside an object using generic interfaces. And it also supports the notion of threads that execute in the context of the object, and it allows raising exceptions, for example, when there is a memory access violation. All of the features that I mentioned here in a nutshell allows implementing system services as an object with well defined entry points. This modula-3 allows the creation of logical protection domains. What you can do from outside the object is what the entry point methods that are inside the object will let you do and no more. In other words, we are getting the safety property of a monolithic kernel without having to put system code in a separate hardware address space. So in other words the logical protection domains give you both protection and performance, the two things that we strive for. Now, what about flexibility? Well, the genetic interface mechanism allows you to have multiple instances of the same service. And a given application may be able to exploit the different instances of services that are available, that cater to the same generic interface, and that's the way you can get flexibility as well. And objects that implement specific services can be the desired granularity of the system designer. It can be fine-grained, or it can be a collection. You can think of individual hardware resources as fine-grained object. For example, a page frame and what you can do with a particular page frame. You can have interfaces that provide a certain functionality. That can be what an object is. For example a page allocation module can be on object. And it can also make a collection of interfaces into an object. For example, an entire virtual memory subsystem can be an object that is hierarchically composed of page allocation module, and within that, you may have hardware resources defined as objects as well. And all of these objects, whether it is at the course level of a collection of interfaces, or individual interface that is a component of this collection, or specific hardware resources, all of those are accessible via capabilities. Now the word capability may give you jitters, because I just now said that capabilities traditionally in the operating system parlance signifies a heavyweight mechanism. But because we are dealing with a strongly typed language, capabilities to objects can be supported as pointers. Or in other words, the programming language supported pointers can serve as capabilities to the objects. So now, with this idea access to the resources, that is entry point functions within an object that is representing a specific resource, is provided via capabilities that are simply language supported pointers. And because they are language supported pointers, these capabilities that we are talking about here, are much cheaper compared to real capabilities as was used in the hydra operating system.


The question is asking you to differentiate between pointers in in Modula-3 and pointers in C. And the choices I have for you are, there are no differences between pointers in a language like Modula-3 and C, C pointers are more restricted, or Modula-3 pointers are type-specific. So these are the three choices. And one right choice. Good luck.


The right answer is modula -3 pointers are type-specific. That is, pointers in modula-3 cannot be forged, there's no way to subvert the protection mechanism that is built into the language. So if I have a data structure defined In Modula-3. And if I have pointer to the data structure, the only way you can use that pointer, is as a pointer to that type of data structure. You cannot take a data structure and cast it to appear like something else, this is something that we as C programmers, maybe very used to doing, but that's not something that is possible in Modula-3. And that is what allows us to implement logical protection domains in Modula-3 Using objects and capabilities to objects as pointers supported by the programming language.

Spin Mechanisms for Protection Domains

There are three mechanisms in SPIN to create protection domains, and use them. The first one is, of course, the create call that allows creating a logical protection domain. And this mechanism in SPIN allows initiating an object file with the contents and export the names that are contained as entry point methods inside the object to be visible outside. That's what this create call, supported by SPIN, provides to a service creator. For example, if I'm creating a memory management service. I can write the entry point functions in my memory management service and export the names using this create mechanism that's available in SPIN. The second mechanism in SPIN is resolving names. If one protection domain wants to use the names that is there in another protection domain. The way we can accomplish that is by using this resolve primitive that's available in SPIN. Resolve is very similar to linking two separately compiled files together that a compiler does routinely. So, you may be very familiar with the compilation process where you may separately compile files and once you have done the separate compilation of the files, then you go through a link phase of the compiler where the linker resolves the names that are being used by one object file with the names that are defined in another object file. That's the same thing that the resolve mechanism of SPIN does is, it resolves the names that are being used in source, which is a logical protection domain, and the target, which is another logical protection domain. As the result of this resolve step, the source logical protection domain and the target logical prediction domain are dynamically linked or bound together. And once bound together, accessing methods that are inside this target protection domain happens at memory speeds, meaning it is as efficient as a procedure call, once this resolve step has happened. As I mention before, to reduce the proliferation of small logical protection domains you may want to combine protection domains to create an aggregate larger protection domain and SPIN provides a mechanism for that, which is the combined mechanism. Once the names in a source and target protection domain have been resolved, they can be combined to create an aggregate domain. And the aggregate logical protection domain will have entry points, which is the union of the entry points that were exported as names from the source and the target or any number of such domains that have been combined together to create an aggregate domain. So this combined primitive in SPIN is mainly useful as a software engineering management tool to combat the proliferation of many small domains. So, once again, the road map for creating services is, write your code as a Modula-3 program with well defined entry points. And using the SPIN mechanism of create, you can instantiate a service and export the names that are available in that service. And if another logical protection domain wants to use the names that are exported, it can do so by using the SPIN mechanism resolve that causes the dynamic binding of the source and target logical protection domains. And finally, the combined primitive allows aggregation of logical protection domains to create an aggregate domain, that's the union of all the entry points that are available in the component logical protection domains. This is it. This is the secret sauce in SPIN to get protection and performance while allowing flexibility. Everything hinges on the strongly-typed nature of the programming language that is being used for implementing the operating system. That is, the language allows compile time checking, and run time enforcement of the logical protection domains. That's the key to the success of this approach to providing flexibility, protection, and performance, all in one bag.

Customized OS With Spin

So the upshot of the logical protection domain is the ability to extend SPIN to include operating system services and make that all part of the same hardware address space, so no border crossing between the services or the mechanisms provided by SPIN. So here is one example where all these system services are implemented as protection domain and using create, resolve and combine. We've created all these services as logical extensions of SPIN. Here is another extension living on top of the same hardware, concurrently with the first extension. And as you see, each of these mounds represent a completely different operating system. And each of these mounds may have their own subsystems for the same functionality. For instance, this process uses memory manager two. This process uses memory manager one. Both of them implement the same functionality. But very differently, hopefully, to cater to the needs of the applications that need those services. But they may also have common subsystems. For example, the network protocol stack, may be shared by both extensions that live on top the same hardware framework.

Example Extensions

Here is a concrete example of an extension. It's a fairly standard implementation, let's say of Unix operating system, but it is implemented as an extension on top of the spin. Here is a more fun example. A client server application that is implemented directly on top of spin as an extension. In other words, there is no operating system. A display client uses an extension interface to implement the functionality for displaying video that is going to be sent by a video server. So both of these are extensions on top of basic spin, and provide exactly the functionality that is needed for the video server application. And the bounding box here is showing spin and the extensions thereof. And similarly the bounding box here is showing spin and the extension thereof. In this case it is an entire operating system, in this case it is just the client of the video server. And in this case it is just the video server itself as an extension on top of spin.

Border Crossings

Now it's time for a question. I'm showing you three different structures here for the operating system. Here are the monolithic structure and here is the micro-kernel base structure, and here is the spin structure with extensions. And the question to you is, which of the above structures will result in the least number of border crossings? Is it the monolithic structure, is it the micro-kernel structure, or the spin structure, or either spin or monolithic structure? So, these are the four choices available to you, for you to pick one correct choice.

Border Crossings

The right answer, either SPIN or monolithic, will result in the least number of border crossings. Why? In the microkernel based structure, we're assuming that each one of these services are available as server processes. In their own hardware address space and therefore any system service that an application needs may have to go through multiple border crossings. And by border crossing we, of course, mean going across different address spaces and the incumbent loss of locality that it entails. Whereas, in the case of mono, you have only two border crossings. One to get to the monolithic kernel and the other to come out back into the application. And by construction, in SPIN also, because we are taking SPIN and extending it with the services. They're all contained in the same hardware address space. So, even though we may be going through several different protection domains in satisfying the system call emanating from an application. Those prediction domains are all logical prediction domains. It does not involve border crossing that entails change of locality and loss of performance.

Spin Mechanisms for Events

An operating system has to feel external events. For example, external interrupts that may come in when a process is executing. Or, the process itself may incur some exceptions such as a page fault. Or it may make system calls. All of these are events that needs to be fielded by the operating system and SPIN has to support such external events. And SPIN supports such external events using an event based communication model. Services can register what are called event handlers with the SPIN event dispatcher, and SPIN supports several types of mapping. It support a one to one mapping between an event and a handler. It also support one to many mapping between an event and the handlers. And it also supports many to one mapping, many events being mapped to the same handler. And let's look at concrete examples to illustrate the power of this mapping and how it might help in building system services. And what this picture is showing you is a typical protocol stack. And you may have several different interfaces available on your machine. And therefore, a network packet may arrive through one of several interfaces. Let's say you have an Ethernet interface and you have an ATM interface. A network packet may arrive on the Ethernet port or an ATM port. Those are events, and both of those may be IP packets, in which case there is an IP handler that needs to see the events. And so, here is an example of many events mapping to the same handler. Ethernet packet arrival is an event, ATM packet arrival is an event, different events but they map the same handler, which is the IP handler. That's an example of many-to-one mapping. The processing of the packet by this IP handler results in an IP packet arrival event. And there will be several clients of the IP layer of the protocol stack. There will be UDP transport, there will be TCP transport, there will be an ICMP layer. And they are all sitting on top of this IP network layer. So when an IP packet arrival event is figured by this handler, there are multiple clients for that, and this is an example of a one to many mapping, one event, to multiple handlers, that need to get triggered. And the SPIN dispatcher allows any number of handlers to be registered as handling a particular event type. And when that even type is reached, then all the handlers associated with that event type will get scheduled by the SPIN dispatcher. The order in which they get scheduled is not something that the designer can count on, because SPIN has freedom in the ordering which these event handlers may get scheduled when a particular event arise. But all the handlers that are associated with an event will get triggered when that event is released. That's an example of one to many mapping. And finally, here is an example of a one to one mapping. If it's an ICMP packet, the ICMP handler processes the IP packet, and if it is an ICMP packet, then it raises an event than an ICMP packet has arrived, and maybe there is only one client for that particular event, and that may be the ping program, so that's one, two on mapping. Even handlers may also be specified with guards of finer grain handler execution. For example, this handler could specify that only when IP packets arrive it should be executed. So that's a guard that the IP packet handler could specify so that even though different kinds of packets may arrive on these interfaces, this handler will only get triggered when the packet that arrived on the different interfaces than IP packet.

Default Core Services in Spin

So now, we know the toolbox provided by SPIN for building an operating system. Now, one can build each of the services we talked about early on, that an operating system should provide. Such as memory management, CPU scheduling, threads, file system, network protocol stack, and so on, from scratch, as extensions to SPIN. As we know, memory management and CPU scheduling are core services that any operating system should provide. However, an extensible operating system should not dictate how these services should be implemented. SPIN provides interface procedures for implementing these services in the operating system. Physical memory is a precious resource. We know that native operating systems such as Linux or Windows manages the physical memory that is available from the hardware. SPIN wants to allow extensions to manage physical memory allocated to them in whatever fashion they choose to. The macro-allocation of a bunch of physical memory to an extension, it's outside the scope of this discussion. But, assume that the allocation of a bunch of physical memory happens when an extension's charged up. The discussion in this tablet frame is to do with the management of the pre-allocated physical memory by the extension. The interface functions that I'm showing you here from memory management are simply header files provided by SPIN. For example, allocating a page frame. Deallocating a page frame. Reclaiming a page frame. Similarly, allocating a virtual page or deallocating a virtual page which might be used for dynamic memory allocation. Translating, has to do with creating and destroying address spaces, adding or removing mapping between virtual pages, and physical frames. All of those are interface functions, that are provided as header files by SPIN. And memory management, because of what we said earlier about overcommitment of memory. Not all of a processor's address space is going to be fitting in physical memory. So, there are event handlers, that are provided as part of the core service of SPIN for handling page fault, access fault, meaning, if you had a page that is write protected and if a process tries to write to it, that's an access violation. Or, if a process is trying to access a region of memory that it doesn't have access to, generating a bad address exception. All of these are interface functions that are defined as core services of memory management in the SPIN operation system. It is not saying anything about how these services are implemented, but it is giving you just a header file. The implementer of an extension has to write the actual code for these header functions and create a logical protection domain that corresponds to physical address management, virtual address management, translation management, and the handler functions for dealing with these different types of events. Once the logical protection domain is dynamically instantiated, it becomes an extension of SPIN, and after that there's no border crossing between a particular service that has been so instantiated and SPIN itself. And all of these functions are invoked automatically when the hardware events occur, corresponding to a page fault or access violation fault and so on.

Default Core Service in Spin (cont)

SPIN arbitrates another precious resource, which is another core service, namely the CPU. SPIN only decides at a macro level, the amount of time, that is given to a particular extension. That's done through the SPIN global scheduler. The global scheduler interacts with the application threads package. And application is a loose term here. It is the extension that is living on top of SPIN. Which may be an entire operating system or maybe just an application. For example, let's say, we are running Linux and Vista as two extensions on top of SPIN. Each maybe given a particular time slice, say of x milliseconds. How each extension uses the time that has been given to it for scheduling user-level processes running inside the operating system is entirely up to those extensions. And to support the concept of threads in the operating system and management of time, SPIN provides an abstraction called strand. The actual operating systems that extend SPIN will have the threads map to strands. So strand is the unit of scheduling that SPIN's global scheduler uses, but the semantics of the strand is entirely decided by the extension. If, for instance, I'm implementing p-threads, I will define the semantics of the strand to be the semantics of the p-thread's scheduler. And there are event handlers that help in the scheduling that needs to happen in the extensions. And the kind of events that SPIN provides for this core service of CPU scheduling are block, unblock, checkpoint, and resume. And the extensions event handlers have to give the semantic meaning of what needs to happen when these event handlers are called, because these are only interface functions. What needs to happen when this interface function is called is up to the extension. For example, a disk interrupt handler may result in an unblock event being raised for a particular strand that was waiting for the disk IO completion. Similarly, if an application were to make a system call that is a blocking system call, then the service that provides that facility to the application will raise this block event, which will result in the extension taking the appropriate action of saving the state of the currently running process. And putting it in the appropriate queues that it has, to wait for that system call completion. So in a nutshell, what SPIN provides are exactly the kind of primitives that may be needed by an extension that wants to provide the service of CPU scheduling. So SPIN only provides the interface function definitions. The semantics are all up to the extension on how exactly the scheduling is affected. And all that SPIN does is to ensure that the extension gets time on the CPU through this global scheduler that SPIN has for allocating time to different extensions that may be concurrently living on top of SPIN.


There are some deep implications that may not be readily obvious. Core services are trusted services, since they provide access to hardware mechanisms. Why? The services may need to step outside the language-enforced protection model to control the hardware resources. In other words, the applications that run on top of an extension have to trust the extension. Extensions to core services affect only the applications that use that extension. That is, it is not catastrophic and does not affect other applications that do not rely on this particular extension.