The hardware that holds up the operating system — exam-style exercises with the printer, the cache that hits and the base and limit registers (and the ISR that cost me half a point)

Each device hooks onto the bus through its controller, which has a local buffer where the CPU leaves and picks up data. When the operation finishes, the controller notifies the CPU with an interrupt.

The controller is the piece of hardware that sits between the bus and the device. Its local buffer is where data is exchanged with the CPU, and the interrupt is how it reports back. Careful: the driver is OS software, not the piece that connects to the bus.

Answer: It saves the CPU state and then runs the ISR

Order of an interrupt: the CPU saves its state, runs the OS’s interrupt service routine (ISR), restores the state and the interrupted process carries on without noticing.

• Polling → The CPU asks the devices one by one which one interrupted
• Vectored interrupt → The device identifies itself by sending a number over the data bus
• Interrupt vector → Area of main memory with the addresses of all the ISRs
• ISR → OS code that handles one particular event

Polling and vectored interrupts are the two ways of finding out who interrupted. With vectored ones, the number the device sends is an index into the interrupt vector, and the vector entry points to the ISR. The leftover description is the controller’s local buffer.

Answer: Interrupt vector

The interrupt vector holds the address of every ISR. The device’s number is the index: the CPU doesn’t have to ask anyone.

Answer: That it only wakes up when an event happens that it has to deal with

The OS doesn’t switch itself on: an event wakes it up. That is why hardware that generates those events (interrupts, the timer) is needed.

Answer: The printer finishes printing a page · A program executes the write() system call · A program tries to divide an integer by zero

The three kinds of event are hardware interrupts (the printer), system calls (write) and exceptions (division by zero). Everything else is the program’s ordinary work in user mode.

• T — With synchronous I/O, the CPU waits until the I/O finishes.
• T — With asynchronous I/O, the OS uses the wait to run other processes.
• F — Synchronous I/O gets more performance out of the system than asynchronous I/O.
• T — With asynchronous I/O, the OS finds out the operation has ended thanks to an interrupt.
• F — I/O is called asynchronous when the OS waits for the operation to finish before carrying on.

Waiting is synchronous; carrying on with something else and getting notified is asynchronous. That is why asynchronous I/O makes better use of the CPU.

Useful CPU in both cases: 30 + 30 from A and 80 from B = 140 ms.

Synchronous: the CPU waits for each print, so A takes 2 × (30 + 50) = 160 ms and B goes afterwards: 160 + 80 = 240 ms. Usage: 140 / 240 = 58.33 %.

Asynchronous (the chart): A 0-30, B 30-80 while printing, A 80-110, B 110-140 and done; from 140 to 160 the CPU is idle waiting for the last page. Total 160 ms and usage 140 / 160 = 87.5 %.

Correct order:

1. A requests the printing with a system call
2. The OS handles the call and passes the order to the controller
3. The OS does a context switch and puts process B on the CPU
4. The printer finishes and raises an interrupt
5. The OS handles the interrupt and decides to resume A

The system call wakes the OS, the OS talks to the I/O, uses the wait for another process, and the end-of-I/O interrupt gives it control back.

If a device is busy, the OS keeps the request in that device’s wait queue. Every time an operation finishes, the OS hands the device the next pending request.

Each device has its own queue of pending requests, served in order. Your computer’s print queue is exactly that.

• T — System calls are handled like interrupts, but the CPU itself triggers them.
• F — Exceptions are always caused by an I/O device.
• T — There is a machine instruction to trigger a software interrupt, such as INT on Intel.
• F — System calls are implemented with hardware interrupts.
• T — Each kind of event triggers a different ISR through the interrupt vector.

Software interrupt = system call or exception: handled like a hardware one, but triggered by the CPU. The instructions are INT (Intel), TRAP (Motorola) and SYSCALL (MIPS).

Correct order:

1. Registers
2. Cache memory
3. Main memory
4. Solid-state drive (SSD)
5. Magnetic hard disk
6. Magnetic tape

The hierarchy goes from the registers (inside the CPU) down to tape. Ordered by cost per byte it is the same list reversed: the fastest is the dearest.

Answer: Keeping the most frequently used information in the fastest memory

If the most used data is in the fastest memory, most accesses are fast even though the rest of the hierarchy is slow.

• T — The caching principle is also used in the disk cache and the web page cache.
• F — When the cache fills up, it is emptied completely and reloaded.
• T — The replacement policy decides which block leaves when a new one must go in and there is no room.
• F — The faster a memory is, the cheaper per byte it usually is.

When it fills up, a single block leaves, whichever the policy says. And in the hierarchy, speed and price go together: fast is expensive.

• FIFO → The one that came into the cache before the others
• LRU → The one that has gone unused for longest
• LFU → The one that has been used the fewest times
• Random → Any one

FIFO looks at arrival; LRU, at last use; LFU, at how often it is used. Size isn’t a criterion of these policies.

FIFO: only the third access (X) hits. When Z arrives, X leaves because it came in first, so the fifth access (X) misses. Miss rate 5/6: 2 + (5/6) × 40 = 2 + 33.33 = 35.33 ns.

LRU: the third and fifth accesses (X) hit, because using X in the third makes it the most recent and when Z arrives Y leaves. Miss rate 4/6: 2 + (4/6) × 40 = 2 + 26.67 = 28.67 ns.

• Bit → One of two values, 0 or 1
• Byte → 8 bits
• Word → Between 8 and 64 bits depending on the CPU
• 1 KiB → 1024 bytes
• 1 KB → 1000 bytes

KiB is binary (2 to the power of 10) and KB is decimal (10 to the power of 3). The word depends on the processor.

Answer: Read or write the operating system’s memory · Read or write another program’s memory · Give orders directly to the printer controller · Use the CPU for as long as they like

The three protected resources are memory (the OS’s and everyone else’s), I/O and the CPU. Asking the OS for something with a system call is allowed: it is the legal way to do it.

• T — In privileged mode any instruction in the instruction set can be executed.
• F — In privileged mode only privileged instructions can be executed.
• T — If a program in user mode tries a privileged instruction, the CPU raises an exception.
• T — Supervisor mode, system mode and kernel mode are names for the same mode.
• F — Interrupt service routines run in user mode.

In privileged mode anything goes; in user mode, a privileged instruction causes an exception. ISRs are OS code and run in privileged mode.

Correct order:

1. The CPU boots in privileged mode
2. The OS switches to user mode just before handing control to your program
3. Your program executes the system call instruction
4. The CPU switches to privileged mode by itself and runs OS code

It boots with full power, the OS gives it up before handing the CPU to a program, and it only comes back with an interrupt, a system call or an exception.

The system call instruction switches the processor to privileged mode. That way a user program changes mode voluntarily, but what runs next is OS code.

The syscall is the only voluntary door into privileged mode, and on the other side there is only OS code: the program can’t sneak its own instructions in.

Answer: printf() runs in user mode and uses the write() system call to write to the console

The C library is ordinary code in user mode. Only the system call inside it (write) enters the kernel.

Answer: In CPU registers · In a table in main memory · On the stack

Registers are the usual way; if the arguments don’t fit, a table in memory (with its address in a register) or the stack is used.

Valid if address ≥ base and address < base + limit = 38000.

29999 < 30000: exception. 30000 is the first valid one (≥ base). 37999 < 38000: valid, and it is the last one. 38000 is not < 38000: exception.

• T — Special I/O instructions, such as in and out, must be privileged.
• T — If I/O is memory-mapped, its addresses must be forbidden in user mode.
• F — The circuit that checks base and limit is active in supervisor mode.
• F — An access outside the allowed range reaches the bus, but memory ignores it.
• T — The base and limit registers mark out an area of main memory.

The check is made in user mode (in privileged mode the OS can touch all of memory). An illegal access never reaches the bus: it turns into an exception.

So that no process can hog the CPU, the OS uses a timer. It loads it with a value, the counter goes down with every clock tick and, when it reaches zero, it raises an interrupt with which the OS regains control.

The timer guarantees that the OS runs again even if a program is stuck in an infinite loop. And since changing it is privileged, the program can’t switch it off.

• System programs → Utilities such as the shell, ls or the compiler, and background services
• Kernel → The part of the OS that is always in memory and handles system calls and other events
• System call → For the programmer, a subroutine; for the CPU, an instruction that changes mode

System programs are what users perceive as “the OS”; the kernel is what works underneath, and system calls are the way of asking it for things.

• fork → Processes
• sbrk → Memory
• mkdir → Files
• socket → Networks
• chmod → Protection

fork creates processes, sbrk asks for more memory, mkdir creates directories, socket opens a network connection and chmod changes permissions.

Correct order:

1. The CPU starts executing at a fixed memory address
2. A small boot routine stored in ROM runs
3. The routine finds the OS loader (boot loader) and loads it into memory
4. The loader installs the kernel and modules and services load until everything is ready

ROM → loader → kernel → services. The ROM already knows how to read from the devices, which is why it can find the loader.

• Monolithic → The whole kernel in a single address space
• Layered → Each level uses the services of the level below
• Microkernel → The minimum in the kernel; the rest in user space with messages
• Loadable modules → Pieces of code added to the kernel at runtime
• Hybrid → Mixes several of the above

Examples: classic UNIX (monolithic), THE (layered), Mach (microkernel), Linux and Solaris (modules) and Windows, macOS or Android (hybrid).

Answer: Microkernel

The microkernel keeps only the basic mechanisms inside (multitasking, interrupts, communication between processes) and the rest are modules in user space.

• T — A policy is a strategy, such as LRU; a mechanism is what lets you carry it out, such as a wait queue.
• F — In a microkernel, the policies go inside the kernel and the mechanisms outside.
• T — One drawback of the microkernel is that messages between modules cost performance.
• T — One advantage of the microkernel is that less code runs in privileged mode.
• T — Linux is monolithic, but modules can be added to it while it runs.

In the microkernel, mechanisms go inside and policies outside. Less privileged code = more security, at the price of the messages.

Model answer:

A requests the printing with a system call, which is a software interrupt: the CPU switches to privileged mode and the OS runs. The OS handles the call and talks to the printer controller: it leaves the data in its local buffer and gives it the order (if the printer were busy, it would put the request in its wait queue).

Since A has to wait for the printer, the OS doesn’t leave the CPU idle: it does a context switch and runs another process, B. The printer works on its own. When it finishes, its controller raises a hardware interrupt; the CPU saves B’s state, runs the printer’s ISR and the OS decides to resume A.

It performs better because the time the printer takes isn’t wasted: synchronously, the CPU would sit waiting (or asking) without doing anything useful.

Model answer:

With polling, the CPU asks each device, one after another, whether it was the one that interrupted. It is simple but slow: the more devices, the more questions and the more CPU time wasted.

With vectored interrupts, the interrupting device sends a number over the data bus. That number is an index into the interrupt vector, an area of main memory holding the addresses of all the interrupt service routines. The CPU looks up that slot and jumps straight to the right ISR without asking anyone.

The vector also serves every kind of event: hardware interrupts, system calls and exceptions all have their entry.

Model answer:

The CPU defines a set of privileged instructions and works in two modes. In privileged mode (kernel, supervisor or system mode) any instruction can be executed; in user mode, trying a privileged instruction raises an exception.

The CPU boots in privileged mode. Before handing control to a program, the OS switches to user mode, and privileged mode only comes back when the OS regains control: through an interrupt, a system call or an exception. The system call instruction switches mode automatically, but what runs next is OS code.

Memory: the base and limit registers mark out the process’s area of main memory; in user mode, a circuit checks every access and, if it steps outside, raises an exception and the access never reaches the bus. CPU: the timer is loaded with a value, goes down with every clock tick and raises an interrupt at zero, so no process can hog the CPU. Changing these registers and the timer is privileged, which is why the program can’t switch them off.

Model answer:

In a monolithic system, all the kernel’s functionality is in a single address space, “everything in one big lump”. It is the simplest and fastest structure, because the parts call each other directly, but one part can’t be changed on its own: a change affects the rest. Example: classic UNIX.

In a microkernel, only the essentials stay in the kernel (basic multitasking, interrupt handling, communication between processes) and the other services are modules in user space that talk through messages. Example: Mach (1980).

Policies are the strategies for managing a resource (FIFO, LRU, SJF…) and mechanisms are the structures used to carry them out (queues, bitmaps, the timer…). The microkernel keeps the mechanisms inside and the policies outside. Advantages: new services without touching the kernel, easier to port and safer, because there is less privileged code. Drawback: messages between modules cost performance.