Operating systems

Your laptop runs a browser, music, a messenger and an antivirus at the same time, yet it has only a few processor cores and limited memory. Every program believes the whole computer is its own — and the operating system (OS) creates that illusion. The OS shares out processor time, gives each program its own memory, organises files on disk and keeps programs from locking each other up.

Processes, threads and scheduling

Ready processes wait in a queue, and the scheduler decides which one gets the processor. FCFS — first come, first served; SJF — shortest job first (it minimises the average waiting time but needs to know job lengths in advance); Round Robin — each process gets a time quantum q, then goes to the back of the queue. Every switch costs a context switch: saving and restoring registers.

from collections import deque

def fcfs(bursts):
    t, waits = 0, []
    for b in bursts:
        waits.append(t)
        t += b
    return waits

def round_robin(bursts, q):
    rem, t, done = list(bursts), 0, [0] * len(bursts)
    queue = deque(range(len(bursts)))
    while queue:
        i = queue.popleft()
        run = min(q, rem[i])
        t += run
        rem[i] -= run
        if rem[i]:
            queue.append(i)
        else:
            done[i] = t
    return [done[i] - bursts[i] for i in range(len(bursts))]

jobs = [10, 4, 2]
for name, w in [('FCFS', fcfs(jobs)), ('SJF', fcfs(sorted(jobs))), ('RR q=3', round_robin(jobs, 3))]:
    print(name, w, 'average wait:', round(sum(w) / len(w), 2))

FCFS [0, 10, 14] average wait: 8.0
SJF [0, 2, 6] average wait: 2.67
RR q=3 [6, 8, 6] average wait: 6.67

Virtual memory and paging

Each process sees its own virtual address space starting at 0. Memory is split into equal pages (e.g. 4 KB) and physical RAM into equal frames; each process's page table maps page → frame. The hardware (MMU) does the translation and keeps recent translations in the TLB cache. If a page is not in RAM, a page fault occurs and the OS loads it from disk — so programs can use more memory than physical RAM and cannot see each other's memory.

When RAM is full the OS must choose which page to evict to disk. FIFO evicts the page loaded earliest, LRU the one unused for the longest time. The theoretical ideal OPT evicts the page needed furthest in the future, but the future is unknown, so it serves only as a benchmark.

def faults(refs, frames, policy):
    mem, count = [], 0
    for p in refs:
        if p in mem:
            if policy == 'LRU':
                mem.remove(p)
                mem.append(p)
            continue
        count += 1
        if len(mem) == frames:
            mem.pop(0)
        mem.append(p)
    return count

refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
for frames in [3, 4]:
    print(frames, 'frames: FIFO', faults(refs, frames, 'FIFO'), '| LRU', faults(refs, frames, 'LRU'))

page_size, va = 4096, 0x3A7C
page, offset = divmod(va, page_size)
page_table = {3: 7}
pa = page_table[page] * page_size + offset
print('page', page, 'offset', offset, '-> physical', pa, hex(pa))

3 frames: FIFO 9 | LRU 10
4 frames: FIFO 10 | LRU 8
page 3 offset 2684 -> physical 31356 0x7a7c

File systems

A disk is divided into fixed-size blocks (usually 4 KB). In Unix file systems (ext4) each file's inode stores its size, owner, permissions, timestamps and pointers to the data blocks; a directory is just a “name → inode number” table. The classic ext2/ext3 inode has 12 direct pointers plus single, double and triple indirect pointers: with 4 KB blocks and 4-byte pointers, the direct blocks cover 48 KB, the single indirect block another 1024 · 4 KB = 4 MB, the double 4 GB and the triple 4 TB. Journaling (ext4, NTFS) first writes changes to a journal so the file system survives a power cut. In FAT32 a single file must be smaller than 4 GB.

Deadlock

Thread A holds lock 1 and waits for lock 2, while thread B holds lock 2 and waits for lock 1 — neither can move. Deadlock is possible when Coffman's four conditions all hold: mutual exclusion (a resource is used by one at a time), hold and wait, no preemption (resources are not taken away) and circular wait. Breaking any one is enough; the most practical way is to always acquire locks in the same global order, which rules out circular wait.