SWAPPING moves an entire process out of main memory to a BACKING STORE (disk) and later brings it back. SWAP OUT memory → disk (a process is suspended) SWAP IN disk → memory (it is resumed) This produces the two extra states of the seven-state process model: SUSPENDED READY and SUSPENDED BLOCKED. The MEDIUM-TERM scheduler makes the decision. WHY IT WORKS: execution-time binding. Because the MMU translates addresses at every access, a process can be brought back at a DIFFERENT physical address with no change to its code. With compile-time binding it would have to return to the exact same place. THE COST — and it is why swapping whole processes is obsolete: transfer time = process size / transfer rate WORKED EXAMPLE: a 100 MB process, disk transfer 50 MB/s swap out = 100 / 50 = 2.0 seconds swap in = 100 / 50 = 2.0 seconds total = 4.0 seconds per swap Four seconds of pure overhead. For a time quantum measured in milliseconds that is unthinkable — the process would spend 1000× longer being moved than running. On an SSD at 2 GB/s: 100/2000 = 0.05 s each way, 0.1 s total. Better by 40×, and still 100 ms of doing nothing. CONCLUSION: swapping whole processes is only viable under severe memory pressure. Modern systems SWAP PAGES instead (paging), because moving 16 KB costs microseconds rather than seconds. WHAT MODERN SYSTEMS ACTUALLY DO: · PAGING — move individual pages, not whole processes · COMPRESSION — compress inactive pages in RAM rather than writing them out. macOS does this by default; Linux offers zram/zswap. Compressing 16 KB costs a few microseconds of CPU versus ~100 µs of SSD I/O, so it wins whenever the data is compressible. · MEASURED ON THIS MACHINE: vm_stat reports Pages free 4,171 Pages active 201,820 Pages inactive 199,306 Pages wired 152,264 at 16 KB per page that is free 0.06 GB (65 MB — almost nothing spare) active 3.08 GB inactive 3.04 GB wired 2.32 GB The INACTIVE list is the swap candidate pool — pages not recently used, kept in memory until something needs the frame. WIRED pages cannot be swapped at all (kernel data, real-time buffers).

The OS must know which memory is free. Two representations: BIT MAP (bit vector) one bit per allocation unit: 0 = free, 1 = allocated. unit size 4 KB, memory 1 GB units = 1 GB / 4 KB = 262,144 bitmap = 262,144 bits = 32 KB (0.003% overhead) ✔ tiny, and trivially easy to find a free unit ✔ finding n CONSECUTIVE free units is a bit-scan ✗ the scan is O(n) in the worst case WORKED, at this machine's 16 KB page size: 16 GiB / 16 KiB = 1,048,576 pages bitmap = 1,048,576 bits = 128 KiB → 128 KB to track 16 GB. Negligible. LINKED LIST of free holes each free block holds its size and a pointer to the next. ✔ no space wasted on allocated regions ✔ allocation strategies (first/best/worst fit) operate directly on it ✗ finding n consecutive units means walking the list ✗ the list nodes live in the free memory itself, so a wild pointer write corrupts the allocator COALESCING — the essential operation: when a block is freed, MERGE it with adjacent free blocks. Without coalescing, memory degrades into a large number of small holes and external fragmentation becomes fatal. before free(B): [free 20K][B 30K][free 10K] after free(B): [free 60K] ← coalesced This is why a free-list node stores its size: you must know where a block ends to test whether the next one is free. THE BUDDY SYSTEM — a compromise used in the Linux kernel: · memory is split into power-of-two sized blocks · to satisfy a request, repeatedly halve a block until the smallest power of two that fits is reached · each half is the other's "buddy"; when both are free they merge automatically WORKED EXAMPLE — a 1 MB region, request 70 KB: 1024 KB split → 512 + 512 512 KB split → 256 + 256 256 KB split → 128 + 128 128 KB ≥ 70 KB → ALLOCATE 128 KB internal fragmentation = 128 − 70 = 58 KB wasted (45%) ✔ coalescing is O(1): a buddy's address differs by exactly one bit, so it is found by XOR rather than by searching ✔ fast allocation and free ✗ internal fragmentation up to nearly 50% — as the 58 KB above shows Linux uses the buddy system for physical page allocation and a SLAB allocator on top of it for small objects, precisely because the buddy system alone wastes too much on small requests.

THRASHING is the state where a system spends more time paging than executing. THE MECHANISM — and note that it is a feedback loop, which is why it collapses so suddenly: 1. memory is overcommitted; page faults rise 2. the CPU is idle waiting for page-in I/O 3. the OS observes low CPU utilisation and concludes it should INCREASE the degree of multiprogramming 4. more processes are admitted, each needing frames 5. every process now has fewer frames → MORE faults 6. go to step 2 The OS's own corrective action makes it worse. That is why CPU utilisation does not degrade gracefully — it falls off a cliff. CPU util ┤ ╭──────╮ ┤ ╭─╯ ╲ ┤ ╭─╯ ╲ ← thrashing begins ┤ ╭─╯ ╲ ┤╭─╯ ╲___________ └──────────────────────────────► degree of multiprogramming THE WORKING SET MODEL — the standard defence. W(t, Δ) = the set of pages referenced in the last Δ references (the "working set window") · |W| approximates how many frames the process actually NEEDS right now · sum the working-set sizes of all processes: D = Σ |W_i| (total demand) · if D > available frames → THRASHING is inevitable · the OS then SUSPENDS a process, freeing its frames for the rest. Reducing multiprogramming is the correct response — the opposite of what the naive feedback loop does. CHOOSING Δ matters: too small → misses part of the true locality too large → includes pages no longer needed PAGE-FAULT FREQUENCY (PFF) — a more direct control: measure each process's fault rate. rate too HIGH → give it more frames rate too LOW → take frames away If no frames can be freed, suspend a process. This controls the symptom directly rather than estimating the working set. LOCALITY OF REFERENCE is why any of this works: TEMPORAL a page referenced now is likely referenced again soon SPATIAL a page near one referenced now is likely referenced soon Without locality, the working set would be the whole program and virtual memory would be useless. Measured evidence of locality appears in the next topic: a second pass over 64 MB produced ZERO page faults because everything was already resident.