Operating System Support

Why OS Architecture Matters exam

A distributed system is a collection of computers, called nodes, that cooperate by sending messages over a network. It is tempting to think of the operating system on each node as a fixed, boring foundation. This section explains why it is not: the way the OS is built decides how well each node can be fitted to its job.

The starting point is that the nodes play different roles. One node is a phone that only displays things and talks to the network; another is a laptop that edits files; a third is a dedicated server in a machine room that has no screen at all. Each role needs different system software, the programs that manage the machine on behalf of applications (file systems, network protocols, the display, and so on). A one-size-fits-all OS would load everything on every node.

CDK says that an open distributed system, one that can be extended and re-implemented piece by piece rather than being a closed, fixed product, should therefore make four things possible:

1. Run only the system software each node needs for its role. A phone, a laptop and a dedicated server need different services, and loading modules a node does not need wastes memory.
2. Replace or extend a service independently of the other facilities, without destabilising the rest of the system. For example, you should be able to install a better file server without touching the network code.
3. Offer alternatives of the same service, so that different users or applications can each use the version that suits them, for example two file services with different caching behaviour side by side.
4. Introduce new services without harming the integrity of the existing ones.

Check yourselfWhy does OS architecture matter in a distributed system?

Because the nodes have different roles, each one should run only the system software it needs, which saves memory. Services should be replaceable or extensible independently, without destabilising the system. Alternative implementations of a service should be possible for different users or applications, and it should be possible to add new services without harming existing ones. All of this calls for separating mechanism, which belongs in the kernel, from policy, which is implemented by loadable servers.

Check yourselfWhich of these is not one of CDK's requirements for the OS of an open distributed system?

1. Each node runs only the system software its role needs.
2. A service can be replaced without destabilising the rest.
3. Every node runs exactly the same set of services, so behaviour is uniform.
4. New services can be added without harming existing ones.

C. It is the opposite of requirement 1: nodes play different roles and should load different services. A, B and D are three of the four requirements; the missing fourth is offering alternative implementations of the same service.

The Operating System Layer

Middleware such as Java RMI lets a program call a method on an object in another computer as if it were local. But middleware does not talk to disks and network cards itself. It needs something on every node that already turns raw hardware into usable building blocks. That something is the operating system, and this section describes what it provides.

Where the OS sits

Each node runs its own OS on its own hardware, and the middleware sits across the OSs of all the nodes. CDK draws this as a stack of layers (CDK Fig. 7.1).

The point of the system-call interface is that it offers problem-oriented abstractions instead of raw hardware. A program works with files instead of disk blocks: it asks to read the next 512 bytes of notes.txt and never needs to know which numbered blocks on the disk hold them. Likewise it works with sockets instead of raw network access: it writes bytes to a connection and the OS turns them into packets, retransmits lost ones and so on. Middleware then combines these local resources (sockets, threads, memory) to implement remote invocation.

What resource managers must provide exam

In an OS, the code that looks after a resource (a file, a device, a region of memory) is called a resource manager. The kernel and the server processes are the resource managers. CDK says they must provide three things for every resource they manage, and the figure shows all three at once.

• 1Encapsulation. The manager offers a useful service interface to its resource and hides the implementation details, such as how memory and devices are managed, from its clients. Clients call read(); they never see disk blocks.
• 2Protection. Resources are protected from illegitimate access. Files are protected from unauthorised readers, for example, and device registers from application processes. 5.3 looks at what "illegitimate" means.
• 3Concurrent processing. Clients may share a resource and access it at the same time, so the manager must provide concurrency transparency: each client gets correct results as if it were the only one, without having to know about or coordinate with the others.

Invocation mechanisms

Whatever the mechanism, the libraries, kernels and servers between them carry out two invocation-related tasks:

• Communication: passing the operation's parameters to the resource manager and the results back, whether over a network or within one computer.
• Scheduling: deciding when the invoked operation gets processed, inside the kernel or inside the server, for example which thread runs it and when.

These two tasks are exactly where the time goes when an invocation is slow, which is the subject of 5.9.

The core OS components

The work above is done by five core components of the OS (CDK Fig. 7.2), which Part IV describes alongside processes and threads. They are summarised here because Tutorial 6 asks for them (5.12).

Check yourselfWhat must kernels and servers provide for their resources?

They must provide encapsulation, a service interface that hides implementation detail; protection against illegitimate access; and concurrent processing, meaning shared, concurrent access with concurrency transparency. On top of these they carry out the invocation tasks: the communication of parameters and results, and the scheduling of the invoked operations.

Check yourselfA program calls read() on a file and never learns which disk blocks hold the data. Which duty of a resource manager is this?

1. Protection
2. Encapsulation
3. Concurrency transparency
4. Scheduling

B, encapsulation. Hiding implementation details behind a useful interface is encapsulation. Protection (A) is about stopping illegitimate access; concurrency transparency (C) is about many clients sharing safely; scheduling (D) is one of the two invocation tasks, not a duty towards the resource.

The Kernel and Protection

The previous section said resource managers must protect resources. But a resource manager is just code, and so is the program attacking it. Something has to have more power than ordinary programs, or nothing could be enforced. That something is the kernel. This section defines the kernel and then looks closely at the protection problem it exists to solve.

The kernel exam

There are two definitions worth knowing, one from the slides and one from CDK. They describe the same thing from two angles.

Two terms in CDK's definition need unpacking. The MMU (memory management unit) is the hardware that translates every memory address a program uses into a physical address and checks that the program is allowed to touch it. The registers are the processor's own small storage cells, including the special ones that control protection. Whoever programs the MMU decides which memory each program can see, so by keeping that power to itself the kernel decides what everyone else may do.

Protection (CDK §7.3)

Resources need protecting not only from malicious code but also from buggy code: a program with a stray pointer can do as much damage as an attacker. Take a file with two operations, read and write, as the example. There are two quite different kinds of illegitimate access to it, and the figure shows both.

1. Performing an operation without the right to do so. Jones writes to a file she is only allowed to read. The operation itself is legitimate; Jones just lacks the permission. In a distributed system, a full solution to this needs cryptography, because the request arrives over a network where anyone could forge "I am Jones" (see Part X).
2. Sidestepping the exported operations. A program accesses the file-pointer variable directly, in effect inventing a new operation, setFilePointerRandomly, that the file never offered. This breaks encapsulation from the outside.

Two ways to stop the second kind

The second kind of access only works if a program can reach memory it was never given a reference to. There are two ways to make that impossible.

The contrast with C and C++ shows why the language matters. In those languages a cast can turn any number into a pointer, so a program can forge a reference to memory it was never given:

/* C: an integer becomes a pointer, and the program writes wherever it likes */
long *fp = (long *) 0x7ffe1040;   /* guessed address of the file pointer   */
*fp = 999999;                     /* "setFilePointerRandomly" in one line   */

A type-safe language has no such cast, so the only way to hold a reference to the file is to have been handed one, and then only read and write are available through it. Without a type-safe language, the only defence left is the hardware.

Check yourselfName two kinds of illegitimate resource access and two ways of protecting against them.

The two kinds are (1) performing an operation without the right to it, which is handled by access control or cryptography, and (2) bypassing the exported operations, for example by setting the file pointer directly. The two ways of protecting against the second kind are a type-safe language, in which references cannot be forged, and hardware protection through a kernel, using privileged mode plus address spaces.

Check yourselfA C program casts an integer to a pointer and overwrites a driver's internal buffer. Which kind of illegitimate access is it, and would a rights check on the driver's operations have stopped it?

It is kind 2, sidestepping the exported operations: the program never calls any driver operation, so a rights check on those operations never runs and cannot stop it. Only hardware protection enforced by the kernel (the driver's memory is outside the program's address space) or writing everything in a type-safe language (where the cast is impossible) prevents it.

User Mode and Kernel Mode exam

Hardware protection only works if ordinary programs cannot simply reprogram the protection hardware. So the processor itself must know whether the code it is running is trusted. This section explains the two processor modes, the address spaces they guard, and the single controlled doorway between them.

Two modes and many address spaces

The processor has a mode register that records which mode it is currently in. The mode decides whether privileged instructions may run: instructions that could break protection, such as switching the MMU's protection tables or talking directly to devices.

The kernel also sets up address spaces. An address space is a range of virtual memory with its own access rights (for example, "this region readable, that region read-write"). A process cannot access memory outside its address space, so the kernel and all the other processes are protected from it, however buggy or hostile it is.

Crossing the boundary: the system-call trap

A user process often needs the kernel, for instance to read a file. It cannot call kernel code like an ordinary procedure, since that would let it jump anywhere in the kernel. Instead, the only way to cross into the kernel is through an exception: either an interrupt (raised by a device, such as "the disk has finished") or a system call trap (raised deliberately by the program). A TRAP instruction switches the processor to supervisor mode and the kernel address space, and the hardware forces execution to continue at a kernel-supplied handler. Step through one system call below.

The table sums up the two modes. Notice the last row in particular: the mode a piece of code runs in decides how far the damage from a bug in it can spread.

This separation is what gives the system its security and stability: no ordinary program, however broken, can take down the kernel or read another program's memory.

The price of protection

Protection is not free. Switching address spaces takes many processor cycles, and a trap costs more than an ordinary procedure call. Switching from one process to another may also flush the TLB (translation lookaside buffer, the processor's cache of recent address translations) and the memory caches, so the next process starts "cold" and runs slowly for a while (Part IV). These costs are the reason kernel architecture is a trade-off (5.5–5.7) and the reason invocations can be slow (5.9).

Check yourselfDistinguish user mode and kernel mode. How does a user program obtain a kernel service, and why is that costly?

In kernel (supervisor) mode the processor can execute privileged instructions and access all memory and hardware, whereas code in user mode is restricted to its own address space. To obtain a kernel service, a user program executes a system-call TRAP. The hardware switches to supervisor mode and the kernel address space and runs a fixed kernel handler, and a privileged return then goes back to user mode.

This is costly because of the mode switch, the possible switch of address space, the effects on caches and the TLB, and the checking of arguments. It is therefore more expensive than a procedure call.

Check yourselfWhich statement about entering the kernel is correct?

1. A user process may call any kernel procedure directly, as long as it passes valid arguments.
2. Entry is only through exceptions (interrupts or traps), and the hardware forces execution to a kernel-supplied handler.
3. A process switches itself to supervisor mode by writing to the mode register, then calls the kernel.
4. On x86 the kernel runs in ring 3 so that applications in ring 0 cannot reach it.

B. A would let a process jump anywhere in the kernel. C is impossible because writing the mode register is itself a privileged instruction. D has the rings backwards: the kernel is in ring 0 and applications in ring 3.

Monolithic and Layered Kernels exam

Section 5.3 ended with the one question every kernel design must answer: what belongs inside the kernel, in kernel mode, and what runs outside it as ordinary user-space processes? Buyya classifies operating systems by their structure as monolithic, layered or client–server (microkernel), and modern systems are often hybrids of these. This section covers the first two; the microkernel gets its own section next.

Monolithic kernel

In a monolithic kernel, most OS services (process and memory management, file systems, networking and device drivers) execute in kernel space, in one address space. The components are coded in a non-modular way and any module may call any other, which is why Buyya says they are organised "haphazardly".

An application gets a service by trapping into the kernel, exactly as in the stepper of 5.4. From there the request is handled by ordinary procedure calls inside the kernel: the file system calls the disk driver directly, with no further traps or messages. A monolithic kernel can also contain server processes running in its own address space, such as file servers and some networking.

CDK explains the name. "Monolithic" means massive (megabytes of code) and undifferentiated (not divided into separate, protected parts), and therefore intractable: altering any component to adapt it to new requirements is hard, because you cannot be sure what else depends on it.

Examples: classic UNIX and Linux (slides, CDK), Sprite (CDK), and CP/M and MS-DOS (Buyya).

Layered kernel

The layered design tries to tame the monolithic tangle without giving up on running everything in the kernel. A layered kernel organises the OS as a hierarchy of layers, running from the hardware up through the process scheduler, memory management, I/O device management and system services, to the applications. The rule is strict: each layer uses only the interface of the layer below, so layer N uses layer N−1 and serves layer N+1. All the layers still run in kernel mode.

Examples: THE OS (slides), and VAX/VMS and Multics (Buyya); CDK also cites MULTICS as using layering.

Check yourselfCDK calls a monolithic kernel "massive", "undifferentiated" and "intractable". What does each word mean, and why does the third follow from the first two?

Massive: a huge codebase, megabytes of code. Undifferentiated: not divided into separate, protected modules; traditionally non-modular, with any module able to call any other in one address space. Intractable: altering any one component to meet new requirements is difficult. It follows because in a huge body of code with no enforced boundaries you cannot easily tell what a change will break.

Check yourselfIn a layered kernel, which layers run in kernel mode, and what is the cost of layering?

1. Only the bottom layer; the rest run as user-level servers, so IPC is the cost.
2. All the layers; the cost is that requests pass through several layers.
3. All the layers; the cost is weaker fault isolation than a monolithic kernel.
4. Only the top layer; the cost is extra traps between layers.

B. All layers run in kernel mode, and the price is the overhead of passing through every layer. A describes a microkernel. C is wrong because layering does not make isolation worse than monolithic (both are weak to moderate). D invents traps between layers that do not exist.

Microkernels exam

The monolithic kernel's weaknesses (huge, hard to change, one bug can sink everything) all come from putting too much in kernel mode. The microkernel takes the opposite answer to the design question: keep as little as possible in the kernel. It is also the design that fits the mechanism-versus-policy rule of 5.1.

What stays in the kernel

A microkernel is kept minimal. It provides only the most basic abstractions: address spaces, threads (and their scheduling) and local interprocess communication (IPC), meaning passing messages between processes on the same computer; Buyya adds hardware abstraction. Everything else runs as user-level server processes, loaded dynamically, and only on the nodes that need them: the file server, the network (protocol) server, the display server, the memory and process servers, and OS emulators. In other words, the OS is the microkernel plus user-level subsystems (servers). This is why Buyya also calls it the client–server OS structure.

How a service is invoked: messages

Because the file system is now a separate process, an application cannot call it with a procedure call. Services are reached by messages. A client, which may be an application or another OS component, sends a request message to the server through the kernel's message-based IPC; the server performs the operation, and its reply comes back through the kernel. The kernel acts as a "traffic cop": it validates messages, passes them on, and grants access to the hardware. Step through one file request.

The figure the exam asks for: CDK Fig. 7.15 exam

CDK contrasts the two designs in one figure, and it is worth being able to draw it from memory. In a monolithic kernel, servers S1–S3 are part of the kernel's code and data, and only a few (S4) are dynamically loaded. In a microkernel, every server S1–S4 is a dynamically loaded program running above a small kernel.

Advantages and disadvantages

Most of the microkernel's advantages follow directly from that structure:

A context switch is the processor changing from running one thread or process to another, saving one's registers and loading the other's. A domain transition is a crossing between protection domains (address spaces), such as user to kernel.

Examples to know: Mach (CMU), which supports UNIX and OS/2 emulators; Chorus; QNX, a Unix-like real-time OS used in cars and BlackBerry devices; MINIX (Tanenbaum); L4, and seL4 (NICTA/Data61, Australia), which is used by Google KataOS; and C-DAC PARAS (Buyya).

Check yourselfWhich list is exactly what a microkernel keeps in kernel mode?

1. Address spaces, threads and scheduling, local IPC (plus hardware abstraction).
2. Address spaces, threads, the file system and device drivers.
3. Local IPC and network protocols, so that RPC can be fast.
4. Process and memory management, file systems, networking and drivers.

A. B wrongly keeps the file system and drivers in the kernel; C wrongly puts network protocols in the kernel (Mach, Chorus and L4 leave them to a user-level server, 5.9); D is the monolithic kernel.

Check yourselfIn CDK Fig. 7.15, which servers are dynamically loaded in each design?

In the monolithic kernel only S4 is dynamically loaded; S1–S3 are part of the kernel's code and data. In the microkernel all of S1–S4 are dynamically loaded server programs running above the small kernel.

Hybrids and the Big Comparison exam

Neither pure design is ideal: one is fast but fragile, the other robust but slow. So real systems mix them, and this section shows how, then puts all four architectures side by side.

Hybrid kernels

The slides describe hybrid kernels as keeping substantial functionality in kernel space for performance, while using modular subsystems and well-defined interfaces. The example is the Windows NT family.

CDK comes at the same idea from the monolithic side. Monolithic structure can be improved with layering (MULTICS) or object-oriented design (Choices), and Windows uses both, but it "remains massive". As long as the modules share one address space and are written in C/C++, a bug in one module can still corrupt another, since (as 5.3 showed) C can forge pointers.

Microkernels moved towards the middle too. Because of performance problems, Mach and Chorus later let servers be loaded into either kernel or user space, using the same IPC either way.

Other later designs

Several research systems tackle the protection-versus-speed problem in their own ways:

All four side by side

The table puts the four architectures side by side. Read across the rows to see the central trade-off: monolithic kernels and microkernels sit at opposite ends, one with the best performance and weak fault isolation, the other with the lowest performance and strong isolation, while layered and hybrid kernels fall in between.

Fault isolation, watched happening

The "fault isolation" row is the one students find hardest to explain in words, so here it is as a story. The same bug, a disk driver writing through a bad pointer, happens in both designs.

Check yourselfCompare monolithic and microkernel architectures. exam

A monolithic kernel runs almost all services in kernel space, and services are invoked by procedure calls inside the kernel, which makes it the most efficient design. But it is massive and intractable, it has poor fault isolation, and it is hard to extend. UNIX and Linux are examples.

In a microkernel, the kernel provides only address spaces, threads and local IPC, and the other services are user-level servers reached by message passing. This makes it extensible, with modularity enforced by memory protection. Its small kernel is less likely to be buggy, it is portable, and only the needed services are loaded. The cost is speed, because of IPC and context switches. Examples are Mach, Chorus, QNX and L4.

Check yourselfDescribe layered and hybrid kernels.

In a layered kernel, each layer uses only the layer below. That makes it easier to understand, to debug bottom-up and to modify by replacing a layer, but it is slower, because calls traverse several layers. THE is an example. A hybrid kernel keeps much of its functionality in kernel space for performance, but organises it as modules with clean interfaces, as Windows NT does.

Check yourselfWindows is built with layering and object-oriented design. Why does CDK say a bug in one module can still corrupt another?

Because the modules still share one address space and are written in C/C++. Layering and object orientation organise the code, but neither the hardware (no address-space boundary between modules) nor the language (C can forge pointers) stops one module from writing over another's memory. Windows "remains massive".

Check yourselfA team uses Mach and moves its file server from user space into the kernel. What do they gain and what do they lose?

They gain speed: the server no longer needs domain transitions and context switches for every request, though it is still reached by the same IPC. They lose integrity: a bug in the server can now corrupt the kernel, because memory protection no longer separates them.

How a Microkernel Supports Middleware exam

A microkernel on its own offers only threads, address spaces and messages, which is far too little for middleware or ordinary applications to use directly. This section shows how the gap is filled, using CDK Fig. 7.16, and why the idea eventually lost out.

The microkernel sits below a layer of subsystems, each made of libraries plus servers. Middleware has two routes down:

• It can go through a language runtime (a language support subsystem) or an OS emulation subsystem, for portability: middleware written for UNIX keeps working because it still sees the UNIX interface.
• It can use the microkernel directly when performance matters, skipping the subsystem layer.

Binary OS emulation

Binary OS emulation lets several system-call interfaces coexist on one platform. The classic case is UNIX and OS/2 on Mach: a UNIX emulation subsystem and an OS/2 emulation subsystem both run above the same Mach microkernel, so existing UNIX programs and existing OS/2 programs run side by side. In practice, though, its performance was disappointing.

Why microkernels faded

The main reason to want a microkernel with emulation subsystems was to run several subsystems or OSs on one machine with protection between them. Virtualization now meets that need, by running several complete operating systems on one machine with protection between them, and CDK says it has replaced microkernels as the key OS innovation. 5.11 explains why it won: applications run without being rewritten or recompiled.

Check yourselfHow does a microkernel support middleware? exam

It supports middleware through subsystems on top of the microkernel: language runtime support, or OS emulation for binary compatibility, such as UNIX or OS/2 on Mach. Middleware can also use the microkernel directly for performance. As a result, several OS interfaces can coexist on one platform, and services are loaded only where they are needed.

Check yourselfAccording to CDK, what has replaced microkernels as the key OS innovation, and why?

1. Hybrid kernels, because they are nearly as fast as monolithic kernels.
2. Virtualization, because it meets the need to run several OSs or subsystems with protection between them.
3. Layered kernels, because they are easier to debug.
4. Binary OS emulation, because it lets UNIX and OS/2 coexist.

B. D is a microkernel technique, not its replacement, and its performance was disappointing. A and C are kernel structures, not what CDK names.

Communication and Invocation Performance

Remote invocation (RPC and RMI, Part VI) is meant to look like a local call, but it is far slower. If you want to make it faster you first need to know where the time goes. This section (CDK §7.5, covered briefly in the course) looks at what an invocation costs, what the cost is made of, and what the OS can do to reduce it.

Who implements the communication?

Some kernels offered high-level communication primitives. Amoeba, for example, provided doOperation, getRequest and sendReply, the three operations of a request-reply protocol, so that one call replaces a socket write followed by a read. In practice, though, middleware implements RPC/RMI and events at user level over TCP/UDP sockets, because that gives portability and interoperability: sockets exist on every OS, so the same middleware runs everywhere and can talk to any other machine. Mach, Chorus and L4 likewise provide only local IPC and leave network protocols to a user-level server.

What makes one invocation dearer than another exam

CDK Fig. 7.11 sets out the factors that distinguish invocation mechanisms. Apart from whether the call is synchronous (the caller waits), the cost of an invocation depends on three things:

1. whether it involves a domain transition, that is, crossing from one address space (protection domain) into another;
2. whether it involves communication across a network;
3. whether it involves thread scheduling and switching, that is, waking up and switching to a different thread.

The three typical cases show how these factors add up.

• (a) A system call is one thread trapping into the kernel. There is a domain transition, but no new thread is involved.
• (b) An RPC/RMI within one computer goes from thread 1 in user space 1, through the kernel, to thread 2 in user space 2. That needs two domain crossings and the scheduling of another thread.
• (c) An RPC/RMI between computers involves all of the same steps, plus two kernels and the network.

Latency and throughput

On a LAN a null RPC takes about 0.1 ms. Compare that with its parts. A null procedure call takes a fraction of a microsecond, and sending the roughly 100 bytes of a null RPC at 100 Mbit/s takes only about 0.01 ms. So for small calls on a LAN, software overhead (the kernel and the RPC runtime) dominates. Over the Internet, by contrast, what dominates is network latency (round trips of around 400 ms, for example) and server load.

The delay grows with the size of the arguments, and it jumps each time an extra packet is needed. RPC throughput is low for small amounts of data and rises as the fixed overheads are amortised (spread over more bytes).

Where the time goes

Apart from the network transmission itself, the delay of a remote invocation is made up of these components:

• Marshalling and unmarshalling: copying the arguments and converting them into a flat sequence of bytes for the message, and back again at the other end.
• Data copying: across the user–kernel boundary, across protocol layers, and between the network interface and kernel buffers.
• Packet initialisation: filling in headers and checksums.
• Thread scheduling and context switching: for the system calls, for scheduling server threads, and for a separate network manager process if there is one.
• Waiting for acknowledgements, depending on the protocol chosen.

How the OS can reduce the cost

The OS has several techniques. Shared memory regions between processes avoid copying data at all. Persistent TCP connections, as in HTTP 1.1, amortise the cost of setting up a connection over many requests instead of paying it every time. And for calls within one computer (case (b) above) there is Lightweight RPC (LRPC).

LRPC attacks both of case (b)'s extra costs. First, client and server share an A-stack (argument stack), a region of memory mapped into both of them, so arguments are copied once instead of four times. Second, the client's own thread traps to the kernel with a capability (an unforgeable token that grants the right to call that server) and executes the procedure in the server's domain, so no server thread has to be scheduled. The result is about 3× faster than local RPC.

Asynchronous operation

Finally, when latency cannot be removed it can be hidden. Asynchronous operation means the caller does not simply sit and wait for each reply; it hides latency and also copes with disconnection. It comes in three forms:

Check yourselfA null RPC takes 0.1 ms on a LAN, yet sending its 100 bytes takes only 0.01 ms. Where does the rest of the time go?

The rest goes on software overheads. These are marshalling; data copying (between user and kernel, between protocol layers, and to the network interface); packet initialisation; system calls and context switches; scheduling the server thread; and acknowledgements. This fixed latency is what dominates small calls.

Check yourselfAn RMI between two processes on the same computer involves which of CDK's cost factors?

1. Domain transition only.
2. Domain transitions and thread scheduling, but no network.
3. Network communication only, because RMI always uses sockets.
4. None: calls within one machine are as cheap as procedure calls.

B. This is case (b): thread 1 in user space 1 goes through the kernel into user space 2 (two domain crossings) and another thread must be scheduled. A is case (a), a system call. There is no network in case (b), and D ignores the protection boundary entirely.

Check yourselfName the two things LRPC does to speed up calls within one computer.

(1) Client and server share an A-stack, so the arguments are copied once instead of four times. (2) The client's own thread traps to the kernel with a capability and executes the procedure in the server's domain, so no server thread has to be scheduled. Together they make it about 3× faster than local RPC.

OS Support for Distributed Shared Memory

Distributed shared memory (DSM) is an abstraction that lets processes on different computers share memory as though it were local, even though no memory is physically shared (Part VII). Page-based DSM middleware makes remote memory look local by moving whole pages (fixed-size blocks of virtual memory) between machines on demand. It cannot do that alone: it relies on the OS's virtual-memory and protection mechanisms, and this brief section says which ones.

So page-based DSM needs three kinds of support from the OS:

1. User-controlled page protection, such as mprotect. DSM pages are marked not-present or read-only, so touching a non-local page, or writing to a read-only replica, causes a page fault.
2. User-level page-fault handling. The kernel passes the fault to the DSM runtime, which is either a signal handler or, as in Mach, an external pager. The runtime fetches the page, or write ownership of it, by messages, maps the page with the right permissions, and resumes the faulting thread.
3. Cheap messaging and threads, so that other threads can run while one waits for a page.

Check yourselfWhat OS support does page-based DSM middleware need?

It needs user-controllable page protection, and the delivery of page faults to a user-level handler or an external pager. It also needs the ability to map fetched pages with chosen rights, and efficient messaging plus threads.

Virtualization at the OS Level

Section 5.8 ended by saying virtualization took over the microkernel's role of running several protected subsystems on one machine. This section (CDK §7.7) explains how it works, why it won, and how it differs from emulation, which is a favourite one-mark exam question.

System virtualization exam

This is done by a hypervisor, also called a virtual machine monitor (VMM): a thin software layer on the hardware that offers an interface closely based on the physical architecture. There are two approaches:

Why x86 is awkward: the Popek & Goldberg condition

A sensitive instruction is one whose behaviour depends on, or changes, the machine's privileged state (such as which mode it is in). A hypervisor must catch every sensitive instruction a guest OS runs, because the guest must not touch the real machine state. The easy way to catch an instruction is if it is privileged: run in user mode, it traps. Hence the Popek & Goldberg condition: an architecture is virtualizable if all sensitive instructions are privileged instructions, so that they trap to the hypervisor.

x86 has 17 sensitive but unprivileged instructions, such as LAR and LSL. Full virtualization handles them by emulating those instructions in software, whereas paravirtualization rewrites the guest OS to avoid or tolerate them.

Virtualization is used for server consolidation, where VMs, unlike processes, migrate easily from one physical machine to another; for cloud IaaS (infrastructure as a service: renting virtual machines); for on-demand VMs; and for running several OSs on one desktop. It also gives better security, isolation and resource accounting than processes do.

Virtualization vs emulation exam

You should be able to explain the difference between virtualization and emulation. The two figures show the same stream of guest instructions handled each way.

Case study: Xen

Xen's hypervisor is minimal: in the Exokernel style it provides mechanisms without policy, and it virtualizes the CPU, memory and scheduling. Keeping it small matters for two reasons: a bug in the hypervisor crashes everything running on the machine, and its overhead must be low. Above the hypervisor the machine is divided into domains (Xen's name for VMs).

• domain0 is a privileged control-plane domain (XenoLinux) that manages devices and policy. The domainU domains are unprivileged guests.
• Xen uses the x86 rings to keep these levels apart: the hypervisor runs in ring 0, guest OSs in ring 1 and applications in ring 3. Compare a normal OS, where the kernel itself is in ring 0 (5.4).
• In the guest OS, privileged instructions are replaced by hypercalls, which trap to the hypervisor and are asynchronous. Interrupts are delivered to guests as events.

Scheduling happens at three levels, one inside the other:

1. The hypervisor schedules virtual CPUs (VCPUs) onto physical CPUs, using Simple EDF or the Credit scheduler.
2. Each guest OS schedules kernel threads onto its VCPUs.
3. User-level libraries schedule user threads.

Check yourselfpast exam 2016 Q6(b) (1 mark) Explain the difference between virtualization and emulation.

• In virtualization, a hypervisor gives each VM a virtual copy of the same underlying hardware, so guest OSs and applications run (almost) unmodified. Most instructions execute directly and only sensitive or privileged operations are trapped, which makes it efficient.
• In emulation, software imitates an interface that is not natively present: either another OS's system calls on a microkernel, or another machine's instruction set by interpretation or translation. It is more general, but slower.

Check yourselfWhat is paravirtualization, and why does Xen use it?

In paravirtualization the guest OS is ported to a modified interface: it runs in ring 1 and replaces its privileged instructions with hypercalls to the hypervisor, which runs in ring 0. Xen uses it because x86 has sensitive but unprivileged instructions, so it fails the Popek & Goldberg condition. Full emulation of those instructions is slow, whereas paravirtualization gives near-native speed.

Check yourselfThe Popek & Goldberg condition for an architecture to be virtualizable is that…

1. all privileged instructions are sensitive.
2. all sensitive instructions are privileged, so they trap to the hypervisor.
3. no instruction is sensitive.
4. the guest OS runs in ring 0.

B. A reverses the subset. C is impossible for a real machine. D is wrong: the hypervisor must be the most privileged (ring 0 in Xen), with the guest OS in ring 1.

Tutorial 6, Part 1: Official Answers

These are the tutors' official answers from Ed, Tutorial 06 (Week 7), part 1 on operating systems. Staff have confirmed that tutorial content is examinable, so treat these as model answers. Part 2 of the tutorial, on remote invocation, is in Part VI.

T6-1 · officialDiscuss the difference between a network operating system and a distributed operating system.

A network OS provides support for networking operations, and users are expected to make intelligent use of the network commands it provides. Users keep autonomy over their own processing resources, and the OS does not manage processes across nodes. So each host remains autonomous: it can continue to operate when disconnected from the network.

A distributed OS, by contrast, abstracts the network away, so users never specify how networking operations are done and never care where their programs run or where resources are. It controls all the nodes, and transparently places new processes at whatever node suits its scheduling policy, providing a single system image. The other side of this is that a host may not have everything it needs to operate on its own when disconnected.

	Network OS (NOS)	Distributed OS (DOS)
System image	One per node	Single system image
Autonomy	Each node manages its own processes	One OS controls all nodes
Process placement	User chooses (e.g. ssh to a host and run there)	OS places processes transparently
When disconnected	Host still works on its own	Host may not be able to operate
Examples	UNIX/Linux, Windows, Mac OS	Research prototypes only (e.g. Amoeba)

The last-but-one row is the one-line contrast worth remembering: a NOS host still works offline, but a DOS host may not. The full NOS/DOS comparison, and why middleware plus a NOS won, is in Part IV.

T6-2 · officialWhat are the core OS components?

They are the process manager, thread manager, communication manager, memory manager and supervisor (summarised in 5.2). The tutors describe the supervisor as handling privileged operations, meaning those that directly affect shared resources on the host, such as I/O devices. It makes sure the host keeps providing proper service to each client.

T6-3 · officialWhat is the kernel? Discuss popular kernel implementation methods.

The kernel is the part of the OS with full access to the host's resources. It begins executing when the host powers up and runs for as long as the host is operational, sharing access to resources among all the other processes.

UNIX is the tutors' example of how the system divides up, shown in the figure below.

The two implementation methods to compare are monolithic and microkernel (5.5, 5.6):

	Monolithic	Microkernel
Kernel mode	VFS, IPC, file system, scheduler, virtual memory, device drivers, dispatcher	Only basic IPC, virtual memory and scheduling
User mode	Applications, which enter by system call	UNIX server, device drivers, file server (and applications)

The disadvantages of a monolithic OS are captured in CDK's three words. It is massive, with a huge codebase. It is undifferentiated, because it is traditionally non-modular, though modern kernels are more layered. And it is intractable, because altering any one component for new requirements is difficult.

T6-4 · officialWhat is supervisor mode vs user mode?

These are operating modes that the hardware supports at the machine-instruction level. Instructions executed in supervisor (kernel, privileged) mode can access and control every resource on the host. Instructions executed in user (unprivileged) mode are restricted by the processor to the accesses that the kernel defines or grants (5.4).