OS Full

What does the OS do at a high level vs a low level?

High level: gives developers isolated "resources" and ways to communicate with other applications and the system. Low level: manages the hardware. It hides complexity behind abstractions (files, processes, flat memory, keyboard, monitor, etc.).

Name common OS abstractions

File system, keyboard, monitor, graphics device, sound server, processes, "flat" memory

Who is a "user" in OS terms?

A "user" might not be a person. Applications allocate resources for the benefit of users, and the user can be another program or service.

Desktop OS (kind of OS)

Runs on normal desktops/laptops, tuned for consumer use-cases (e.g. low latency). Examples: Linux, macOS, Windows.

Server OS (kind of OS)

Often headless, tuned for server workloads. Prioritises throughput, extreme stability and hardware scalability (hundreds of cores, hundreds of GB RAM, TB of storage, accelerators).

Embedded OS (kind of OS)

Found in cars, smart TVs, printers, routers, washing machines. Runs for long periods with few or no updates, sometimes in difficult environments, with zero errors expected.

Mobile OS (kind of OS)

Android, iOS. More advanced than a typical embedded OS and approximates a desktop OS, but with strict power management.

Realtime OS (kind of OS)

Used in missiles, assembly-line microcontrollers, pacemakers. If a task isn't completed on time, deterministically, the consequences can be very bad.

Four hard constraints of hardware

1. Space (circuits take physical room and have a minimum size).

2. Distance (far things take longer to reach).

3. Timing (communication that is too fast or too slow is misinterpreted; everything works by clocks).

4. Heat (more energy gives faster clock gives more heat, and too much heat destroys components).

Three soft constraints (the OS's protection jobs)

1. Protect hardware from users.

2. Protect the OS from users.

3. Protect users from users. Motto: Keep It Simple.

What is the CPU?

Central Processing Unit. Performs computations (ALUs = Arithmetic Logic Units) and directs most other components. Can be complex: SMT and/or multi-core.

What is a "coherent bus interconnect"?

Bus = shared communication pathway. Coherent = cache-coherent: everyone on the bus sees the same data and nobody sees a stale value. Interconnect = connects different functional blocks together.

PC (Program Counter)

Register holding the address of the next instruction.

IR (Instruction Register)

Register holding the current instruction.

What is the "uncore"?

Everything that is not the core: not the ALUs, their pipelines, or the core-specific caches. Examples: coherent bus interconnect, memory controllers, shared L3 cache, I/O controllers, PCIe, SATA, USB. Its goal is to feed the cores as quickly and efficiently as possible.

Memory hierarchy and approximate latencies

Registers and L1 (<1ns, SRAM), then L2 per-core and L3 shared (about 3-10ns, SRAM), then RAM (about 10-80ns, DRAM), then local flash storage (about 500-1000ns), then cloud/remote storage (about 10,000,000ns = 100ms or more). The further from the CPU, the more time you spend waiting.

SRAM vs DRAM vs Flash

SRAM: static RAM, uses flip-flops to store data. DRAM: dynamic RAM, uses transistors/capacitors to store data and needs frequent refreshes. Flash: non-volatile memory.

Which caches are per-core and which are shared?

L1 and L2 are per-core. L3 is shared between cores (and lives in the uncore). This is why lscpu shows fewer caches than CPUs.

Userspace (user mode / userland)

Where everything that isn't the OS runs. No direct access to hardware or resources; entirely at the mercy of the OS. Ring 3.

Kernelspace (kernel mode)

Where the OS runs. Direct access to hardware and resources; absolute power over userspace. Ring 0.

Ring 0 vs Ring 3

Ring 0: can execute every instruction the CPU offers (e.g. cache flush), can mark memory as Ring-0 only, can read/write all addresses. Ring 3: only specific arithmetic and logic instructions (everything else is trapped), can only write its own process memory; writing kernel memory is trapped. Enforced by hardware.

Which ring do hypervisors use?

Ring -1

What is a syscall?

A request from userspace that triggers a context switch to kernel mode. The kernel examines the request, does whatever it wishes with it, places the result in userspace, then switches back to userspace. Ring 3 to Ring 0 and back to Ring 3.

Why should you minimise syscalls?

Context-switching is expensive.

Monolithic kernel

Runs all privileged operations in kernelspace (file systems, networking, drivers). Larger attack surface and any failing part (including drivers) can take down the whole OS. Examples: Linux, Windows, OpenBSD, FreeBSD.

Microkernel

Only implements the most basic functions (scheduling, memory management, IPC) in kernelspace; everything else (filesystems, networking, drivers) runs in userspace. Smaller attack surface, more maintainable, more robust, but message-passing involves context switches and can reduce performance. Examples: QNX, seL4.

Monolithic vs microkernel trade-off

Monolithic: faster (no message-passing context switches) but larger attack surface and less robust. Microkernel: smaller attack surface and more stable but slower due to context-switching for message passing.

Jevons Paradox

Increasing the efficiency with which a resource is used can increase (rather than decrease) total demand for that resource.

Why were virtual memory/paging invented?

1950s machines had ~32KB RAM but people wanted to run 100KB programs. Programmers manually overwrote memory with code/data from storage (overlays), which was error-prone. Hardware plus software automated this as paging.

Virtual memory / virtual address space

The memory a process believes it has. Split into fixed-size pages (e.g. 4KB), mapped to physical page frames through a page table. Allows "infinite" memory up to the size of the virtual address space.

Page

Fixed-size region of a virtual address space (e.g. 4KB).

Page frame

Fixed-size region of physical RAM that can hold a page.

Page table

Maps virtual pages to physical page frames (or says the page isn't in RAM). Each entry is typically the CPU's native word size. One page table per process.

Virtual address vs physical address

Virtual address = VPN + offset (address in a process's address space). Physical address = PFN + offset (address in actual RAM).

VPN

Virtual Page Number: which virtual page an address belongs to.

PFN

Physical Frame Number: which physical page frame corresponds to the VPN.

Offset (in paging)

Position within a page/frame. It is unchanged by address translation.

PTE

Page-Table Entry: maps a virtual page to a page frame.

ASID

Address-Space IDentifier: identifies a process's address space (TLB entries are keyed by it).

MMU

Memory Management Unit. Hardware that treats addresses as virtual and checks the page table to translate them to physical addresses; raises a page fault if the page isn't loaded.

Demand paging

Don't load a whole program up front. Load only the initially needed pages and pretend everything is loaded. When a missing page is touched, a page fault occurs and the OS loads it from storage on demand.

How the OS "lies" about memory (steps)

1. When asked to load a program, only load the initially needed pages and pretend all of it is loaded.

2. On each access the MMU looks up the page table.

3. If present, translate and access. If not present, trigger a page fault to the OS; the OS loads the page into a free frame (or evicts a victim), updates the page table, and the instruction is retried and now succeeds.

Page fault steps (8 steps)

1. Instruction causes a fault (synchronous transfer of control to the OS).

2. Save state (PC, registers) to restart later.

3. Control passes to an interrupt service routine / trap handler.

4. OS finds a free frame or picks a victim to evict.

5. OS gets the data onto the page (may read disk, and may write the victim back).

6. OS links the page into the page-table hierarchy (updating parents if needed).

7. OS ensures cached translations (TLB) are correct.

8. ISR returns and the MMU restarts the instruction using saved state.

Why can page faults happen?

Building out the hierarchical page-table tree, demand paging, invalid operation for page permissions, etc. Some are recoverable, some are fatal; the OS must handle all cases.

How do multiple programs coexist in memory?

Keep a separate page table per process. Each process believes it has all addressable memory, but virtual addresses are redirected to different real frames. Process isolation is a consequence of address translation.

Why are pages a fixed size?

Variable-sized allocations would force the OS to remember the exact size of every allocation (costly), search free gaps for exact-sized space and/or periodically compact memory (stopping all processes and fixing every reference). With equal-sized boxes, swapping items is trivial. Trade-off: RAM is cheaper than CPU cycles.

External fragmentation

The OS cannot find a big enough contiguous chunk of memory for a request, even if enough total free memory exists. Paging removes this problem.

Internal fragmentation

The allocated box (page) is bigger than needed, so space inside it is wasted. Paging causes this (larger pages means more internal fragmentation).

Paging trades which fragmentation for which?

Pages remove external fragmentation at the cost of internal fragmentation.

Slab allocator

Allocates memory in larger chunks and divides them into fixed-size objects sized for a particular kernel data structure. Reduces internal-fragmentation waste for frequently-used OS objects.

Problem 1 of paging and its solution

Paging is slow: each memory access needs a page-table lookup plus the actual access (at least 2 accesses, halving RAM speed). Solution: the TLB (Translation Lookaside Buffer).

TLB

Translation Lookaside Buffer: small on-chip cache of recent translations (ASID + virtual page to page frame), speeding up address translation.

Problem 2 of paging and its solution

Page tables take up a lot of space. Solution: hierarchical (multi-level) page tables.

Hierarchical page tables

Instead of one flat page table, use several levels (usually 3-4), treating parts of the virtual address as successive indices. As page faults occur, the OS finds new frames and links in new page tables. Avoids wasting memory on the huge unmapped gap between heap and stack.

Why is there a large unmapped region in virtual memory?

The heap grows up from the bottom of the address space and the stack grows down from the top, so the middle is unmapped.

When are page tables pinned?

If there is no swap space, page tables are pinned in memory and can't be evicted until the process dies.

Present bit (PTE)

Is this page currently in RAM? If 0, trigger a page fault; if 1, go to the PFN.

Dirty bit (PTE)

Has anyone written to this page? If 0, it can simply be overwritten; if 1, it must be written back to disk if swapped out.

Accessed bit (PTE)

Has this page been referenced? If 0 and RAM is short, prefer to swap this unused page out.

User/Supervisor bit (PTE)

Can userspace touch this memory? 1 = yes, 0 = no.

Write bit (PTE)

Can the page be written? 0 = deny writes, 1 = permit writes.

W^X

"Write XOR Execute": a page may be writable or executable but not both. Enabled by the write and NX PTE bits; a modern security technique.

Is malloc a syscall?

No. It is a library call in the C standard library. The allocator does its own memory management (not the OS), which can be faster (no switch into kernel mode) and preserves spatial locality, reducing fragmentation. It is technically outside the OS.

Spatial locality

Data near recently-accessed data is likely to be accessed soon.

Temporal locality

Recently-accessed data is likely to be accessed again soon.

Why was polling a bad way to do I/O?

The CPU asks "are you done yet?" repeatedly. It spends CPU time proportional to the number of devices, you may resume long after the I/O actually completed, and more accuracy needs more frequent sense instructions.

Multiprogramming

Load several programs into memory. When one starts I/O, save its context and context-switch to another task so the CPU isn't idle; switch back when the I/O is done. Running context = registers, process page table, etc.

Multitasking

Multiprogramming plus preemption: context-switching processes against their will while pretending nothing happens, so many users can work interactively with acceptable latency.

What two things are needed to preempt a process?

1. A way of deciding who goes next, fairly, with no human intervention (the scheduler).

2. A way of keeping track of time so that after t units you can context-switch (a monotonic hardware timer).

Process scheduler

OS component that decides who runs next and for how long, and also terminates processes when necessary.

Why did interactive debugging need preemption?

Sharing the machine only works if nobody hogs it. One infinite loop would freeze everyone, so the OS must be able to take the CPU back.

Context switch: what must be saved?

The in-flight execution state: all general registers, execution registers (PC, IR, SP), the address (root) of the page table, interrupt flags, etc. Done so a process never realises it isn't the only one running.

Process states (simplified)

New, Ready, Running, Blocked, Terminated.

Process state transitions

New to Ready: created (pages load on demand). Ready to Running: dispatched (scheduler picks it). Running to Ready: preempted (quantum expired). Running to Blocked: waits for I/O/lock/page fault. Blocked to Ready: awaited event completes. Running to Terminated: exit().

PCB (Process Control Block)

What the OS creates for a program when it becomes a process. Contains identification info (PID, PPID, UID), scheduling state (process state and values needed for scheduling), execution context (saved registers, PC, stack pointer, flags, pointer to page table) and resource state (open files, network connections, IPC resources).

PID

Process Identifier, given by the OS to uniquely identify a process. The first process is typically PID 1; when it exits, OS shutdown is complete.

PPID

Parent Process Identifier: which process (not program) started this process.

UID

User Identifier: which user the process is running as.

Scheduler metric: waiting time

How much of its life a process spends in the ready queue. Waiting = turnaround - burst time.

Scheduler metric: turnaround time

How soon after arrival a process completes (affects throughput = jobs per unit time). Turnaround = completion time - arrival time.

Scheduler metric: response time

How soon after arrival a process first gets to run (affects latency/interactivity). Response = first run time - arrival time.

Two questions every scheduler must answer

1. Who goes next?

2. How much time do they get? "Fair" depends on the OS type (desktop vs embedded). Good schedulers are fair without being expensive.

FCFS (First Come First Served)

Ready queue is a FIFO. Processes run until they complete or block on I/O; no time quantum, so it is non-preemptive. If it blocks it goes to the back of the queue. This is what the Resident Monitor did.

Round Robin (RR)

FIFO ready queue. Processes run until they complete, block on I/O, or exhaust their time quantum, so it is preemptive. A switched-out process goes to the back of the queue.

Interrupt

A hardware event that makes the CPU stop and run a handler, so the CPU doesn't have to poll devices. Originally literally a wire being set; today a memory write. Asynchronous.

How are interrupts set up when the OS boots?

The OS discovers I/O devices and for each fills in the address of an interrupt handler in an agreed-upon place in memory (the vector table / interrupt descriptor table).

Interrupt handling steps

1. Device raises an IRQ.

2. Interrupt controller (state, not event) prioritises, checks the mask, routes to a core; same-priority queue, same-kind coalesce.

3. CPU checks for pending interrupts at instruction boundaries and accepts if priority allows.

4. CPU saves minimal registers, switches to kernel mode, calls the handler.

5. Handler saves more registers and runs in two halves. 6. OS runs any bottom-halves. 7. Return and restore registers.

Top-half vs bottom-half of an interrupt handler

Top-half (immediate): critical work such as clearing the device condition; must be fast, no blocking, few/no interrupts permitted; it sets up the bottom-half. Bottom-half (deferred): interrupts permitted, can allocate, can even wake another process.

Softirq

Linux's deferred bottom-half work for interrupts (e.g. timers, network receive, block I/O, scheduler), run after the quick top-half has finished.

IRQ

Interrupt ReQuest: a signal from a device specifying who raised it and what it is.

Fault vs trap vs interrupt

Fault: synchronous, PC points to the faulting instruction (so it can be restarted, e.g. page fault). Trap: synchronous, PC points to the next instruction (e.g. syscalls). Interrupt: asynchronous, PC points to the next instruction; runs as "nobody" and doesn't block the next instruction.

Synchronous vs asynchronous events

Synchronous: runs in the context of a process and blocks the next instruction until completed. Asynchronous: runs as "nobody" and doesn't block the next instruction.

fork

A process creates a near-exact copy of itself. Parent and child both have the resources set up before the fork (including variable values). Memory-efficient thanks to copy-on-write, but context switching between processes is still somewhat expensive.

What does fork return?

In the child: 0. In the parent: the child's PID. (Use this to tell them apart.)

Copy-on-write (COW)

After fork, parent and child share the same physical pages. A page is only copied when one of them writes to it. In the practical, USS jumps when the child writes to its copy but RSS and VSZ don't change.

fork/wait relationship

Parent is notified of child exit via signals (asynchronous, software mechanism similar to interrupts). When a child exits the parent gets SIGCHLD, for which a responsible parent installs a handler. The parent calls wait to collect the child.

What is a signal?

An asynchronous software notification sent via the OS between processes (conceptually similar to interrupts). A process can set up signal handlers.

Zombie process

A child that has exited but whose parent hasn't called wait. The OS must keep its process info so it can be reaped/queried; if never reaped, PID exhaustion can eventually occur. Shows as state Z (defunct) in ps.

Orphan process / reparenting

If the parent dies while the child is still running, that's fine: the child is reparented to PID 1.

How do you kill a zombie?

You can't kill it with kill (it's already dead; SIGTERM and SIGKILL do nothing). Make its parent wait/reap it, or kill the parent so the zombie is reparented to PID 1, which reaps it.