Operating Systems #1 — Computer System Overview

Before talking about the operating system, look at the machine it sits on. A CPU and main memory connected by a bus, main memory being volatile, peripherals hanging off the outside. That's the starting point.

Registers

A register is a small storage device inside the CPU. They fall into two groups.

User-visible registers are the ones a programmer can use directly when writing assembly. Everything else is reachable only through the OS.

Control/status registers control the CPU's operation and hold its state.

• PC — the memory address of the next instruction to fetch. At program start it holds the address of the first instruction; fetching an instruction moves it to the next address.
• IR — holds the instruction fetched from the address in PC. The CPU reads it from here and executes it.
• PSW — condition codes (positive, negative, zero, overflow), whether interrupts are enabled, and the current mode.

Memory transfers use MAR (address) and MBR (data); I/O devices have their own I/O AR and I/O BR. The important part is that I/O happens through memory. A secondary storage controller has its own buffer memory, and main memory holds a mapping to that buffer's address.

Fetch-Execute

An instruction is processed in two steps.

1. Fetch — take the instruction PC points at into IR, then advance PC to the next instruction.
2. Execute — run the instruction sitting in IR.

If PC holds 300, the value at address 300 goes into IR (IR = 1940) and PC advances. Then the opcode is decoded — say opcode 1 means "load the value at address 940 into AC" — and executed. This repeats through the last instruction.

There are four broad instruction categories: transfers between processor and memory (load, store), transfers between processor and I/O device, arithmetic and logic, and control instructions like jump.

Why interrupts exist

You should still be able to move the mouse or type while a video is playing. That is: when an event occurs at an I/O device, the CPU needs to pause what it's doing, handle it, and return. That's an interrupt.

So a step is added to the fetch-execute cycle: interrupt check, right after execute. And if the work really must not be interrupted, interrupts can be disabled.

Here's the order of what happens when an interrupt arrives:

1. The device controller sends the interrupt.
2. The processor finishes the current instruction, then does its interrupt check.
3. The processor sends an acknowledgment.
4. To be able to come back, it saves PSW and PC onto the control stack.
5. PC is set to the address of the interrupt handler.
6. The remaining registers are saved.
7. The handler runs.
8. When it finishes, the saved values are restored and the original instruction resumes.

The stack pointer points at the top of the structure holding this state, and it decreases as things are pushed. When the handler hits its return, the saved PC and registers are restored and the stack pointer goes back to where it was.

Without interrupts

Consider code that does I/O. User code can't touch hardware directly, so it calls a system call like WRITE. The system call issues the actual I/O command, and when the I/O completes it does the cleanup and returns.

The problem is that the CPU sits idle while the disk works. With interrupts, the I/O command is issued and the CPU moves on to other work; when the completion interrupt arrives, it does the cleanup then. The process's wait time disappears.

But interrupts alone aren't enough. If the I/O takes long enough that no interrupt has arrived by the time a second WRITE comes along, then in principle that second WRITE must not run. The first I/O command has to complete and be handled first. (This principle gets broken later — that comes in a later lecture.)

Which is where multiprogramming comes in. If you'd have to wait, run a completely unrelated third program instead. One processor runs many programs, and CPU scheduling decides the order. So when an interrupt handler finishes, there's no requirement to return to the program that was running — any program currently eligible will do.

Memory hierarchy and cache

Storage is tiered by access frequency: frequently accessed data on fast devices, rarely accessed data on slow ones. This works because of locality of reference — the CPU doesn't access all data and instructions uniformly, it uses particular ones over and over.

Backup devices are attached only when needed, so they're off-line. A hard disk powers up with the machine but sits outside the mainboard, so it's outboard storage. Main memory is on the board, so it's onboard storage.

The gap between CPU and D-RAM speed is severe. During I/O the disk is the bottleneck, but with no I/O memory is the bottleneck. Hence the cache.

• CPU ↔ cache moves data a word at a time (one instruction, one datum).
• Cache ↔ main memory moves data a block at a time.

The cache is checked for the address RA being read; on a miss, the whole block containing RA is pulled from main memory into the cache and only RA goes to the CPU. Blocks are the unit because using an instruction or a datum makes its neighbours likely to be used soon. But blindly enlarging the block drags in things you won't use and wastes cache space.

Two things have to be decided in cache design:

• Mapping function — you must be able to check quickly whether a block is in the cache.
• Write policy — when does a cached update reach memory? Writing through on every update costs too much, so typically the update is written back when the dirty block is evicted.

On multicore, each core has its own cache, so the same datum can hold different values per core — the cache coherence problem. When one cache updates a value, an invalidation message goes to the other caches holding that datum so they refetch it.

There's also a disk cache, acting as a cache between memory and disk. It doesn't use separate RAM — it uses part of main memory.

Who actually does the I/O

I/O is really transfer between memory and the buffer inside a controller. Input pulls from the controller's buffer into memory; output pushes from memory into the controller's buffer. Once output reaches a disk, the disk's controller then writes the buffer's contents to the magnetic disk.

An I/O device's controller doesn't know which part of memory to touch, and has no permission to touch it. So the CPU is involved in every I/O through the buffer. This arrangement improves in stages.

1. Polling — the CPU keeps checking the device's busy bit. While spinning in the not-ready loop it repeats meaningless work. Wasteful.
2. Interrupt-driven I/O — the CPU does useful work and handles the interrupt when it arrives. But the CPU works a word at a time, so moving the data word by word is inefficient.
3. DMA — a separate device does the I/O instead of the CPU. The CPU asks DMA to do the read and goes back to its own work; DMA finishes and sends an interrupt, and the CPU uses the result.

Cores

You can think of one CPU as one core. A single core contains everything a CPU needs; we just bundle several of them together and call the bundle a CPU.