IA Operating Systems — Exam Cram

Process vs Program

Program

Static artifact on disk (text + data).

Process

Program in execution — dynamic. Has text, data, heap, and one or more threads. It is the unit of protection and resource allocation.

Thread

An execution context within a process. Each has its own PC, stack, and registers. In Linux, both processes and threads are "tasks".

Process States (Linux: 5 states)

new ──► Ready (R) ──► Running (R) ──► Terminated
               ▲    ◄── preempt ──┤
               │                  │
               │ wakeup     block on I/O
               │                  ▼
        Interruptible Sleep (S) / Uninterruptible Sleep (D)
               │
        SIGSTOP► Stopped (T) ◄─ SIGCONT

Process Control Block (PCB)

The OS data structure for a process. Contains:

• PID — process identifier
• State — running, ready, waiting…
• CPU registers — PC, stack pointer, general registers (the "scheduling context")
• Memory-management info — page table base register (PTBR), memory limits
• Scheduling info — priority, nice value, vruntime (CFS)
• I/O status — open file table pointer, allocated devices
• Accounting — CPU time used

Context Switch

fork / exec in Unix

Key Metrics

Turnaround time

Completion time − Arrival time

Waiting time

Turnaround time − CPU burst time (time spent in Ready queue)

Response time

First run time − Arrival time

Algorithm Comparison

Worked: FCFS / SJF / SRTF

Round Robin — key facts

SJF Burst Prediction — Exponential Averaging

where t_n = actual nth burst, τ_n+1 = predicted next burst, α ∈ [0,1].

• α ≈ 1: prediction ≈ last burst (history ignored)
• α ≈ 0: prediction ≈ old estimate (recent ignored)
• Good predictor when variance is small and doesn't change quickly

Target latency

The interval in which every runnable task should run at least once. E.g., 6ms with 3 equal-priority tasks → each gets 2ms.

Minimum granularity

Minimum time a process runs per scheduling turn, regardless of target latency. Prevents excessive switching when there are many tasks.

vruntime

Virtual run time: CFS picks the task with the smallest vruntime. For equal-priority tasks, vruntime = actual run time. Lower priority → vruntime grows faster (decays more).

Implementation

Red-black tree (O(log n) insert/remove). Leftmost (smallest vruntime) node is cached. This is the next task to run.

CFS Worked Example (2024 Q3)

Address Binding

Logical vs Physical Addresses

Logical (virtual) address: generated by the CPU. Physical address: seen by RAM. The MMU maps between them at runtime.

Segmentation

Fragmentation

External fragmentation

Total free memory is enough but it isn't contiguous. Fix: compaction (expensive — requires dynamic relocation).

Internal fragmentation

Allocated block is slightly larger than requested. Inherent with fixed-size pages/partitions. On average ½ frame per process.

Segmentation vs Paging

Paging Basics

Physical memory divided into fixed-size frames. Logical memory divided into same-size pages. A page table maps page numbers to frame numbers.

If logical address space = 2^m and page size = 2ⁿ: page number uses (m−n) bits, offset uses n bits.

Paging Arithmetic — How To Solve Any Question

Worked: 2021 Q3(a)

Multi-level Page Tables

Reason: a flat page table for a 32-bit system with 4KB pages needs 2²⁰ × 4 bytes = 4 MB contiguous in memory per process. Multi-level paging allows unused portions to be paged out.

TLB and Effective Access Time (EAT)

Worked: 2025 Q4(c)

2025 Q4: 5-level page table deep dive

Demand Paging EAT Formula

where p = page fault rate, t_mem = memory access time, t_fault = page fault service time.

Worked: 2023 Q3(b)

Page Replacement Algorithms

Worked: 2024 Q4(b) — OPT, LRU, FIFO on string 1 2 3 2 4 3 5 1 3 2 3 4

Ref:  1* 2* 3* 2  4* 3  5* 1* 3  2* 3  4*
OPT: [1] [1,2] [1,2,3] hit [2,3,4] hit [3,4,5] [1,4,5] hit [2,4,5] hit [2,4,3] → 8 faults
LRU: [1] [1,2] [1,2,3] hit [2,3,4] hit [3,4,5] [1,3,5] hit [1,2,3] hit [2,3,4] → 8 faults  
FIFO: [1] [1,2] [1,2,3] hit [2,3,4] hit [3,4,5] [1,4,5] hit [1,2,5] hit [2,3,5] [2,3,4] → ...
(Work through carefully, FIFO evicts the oldest loaded page each miss)

Emulating Reference & Dirty Bits Without Hardware Support

Thrashing & Working Set

Dual-mode Operation

CPUs have at least two modes: user mode (restricted) and kernel mode (privileged). A mode bit tracks the current mode. Privileged instructions are only executable in kernel mode.

Mode switch to kernel: via a trap (system call, exception). The trap vector ensures control jumps to a fixed OS entry point — an application can't jump to arbitrary kernel code.

Access Matrix

Abstract model: rows = domains (subjects/principals), columns = objects, cells = permitted operations.

UNIX File Permissions

Every file/directory has: owner (user), group, and world ("other") — each with read/write/execute bits.

UNIX File Descriptors as Capabilities

Redirecting stdout — kernel interactions (2022 Q4(a))

I/O Methods

Interrupt Handling (2023 Q3(a))

Buffering (Tripos 2020 Q4)

UNIX i-nodes

An i-node (index node) is the FCB in UNIX. It stores metadata (owner, permissions, timestamps, size) and pointers to data blocks.

Worked: Disk Accesses to Read a File (2021 Q3(b))

Hard Links vs Symbolic Links

Hard link

Another directory entry pointing to the same inode. Reference-counted. Deleting either entry decrements count; file deleted when count = 0. Can't span filesystems (different inode number spaces). Can't link directories (prevents cycles).

Symbolic (soft) link

A special file whose data is a path. Can cross filesystems and point to directories. Dangling if target deleted.

Idle Process and Defragmentation (2022 Q4(c))

2025 Q3 — Access Matrix Construction

2024 Q3 — CFS Schedule

2024 Q4 — Page Replacement on 1 2 3 2 4 3 5 1 3 2 3 4

Ref:   1  2  3  2  4  3  5  1  3  2  3  4
       *  *  *  -  *  -  *  *  -  *  -  *
Frames after each step:
[1]  [1,2]  [1,2,3]  [1,2,3]  [2,3,4]  [2,3,4]
[3,4,5]  [4,5,1]  [4,5,1]  [5,1,2]  [5,1,2]  [1,2,4]
FIFO faults: 1,2,3,4,5,1,2,4 = 8 faults (marked *)

Ref:   1  2  3  2  4  3  5  1  3  2  3  4
       *  *  *  -  *  -  *  *  -  *  -  *
At fault, evict page used longest ago:
t=4: frames=[1,2,3], ref=4 → evict 1 (LRU) → [2,3,4]
t=6: frames=[2,3,4], ref=5 → evict 2 → [3,4,5]  
t=7: frames=[3,4,5], ref=1 → evict 4 → [3,5,1]
t=9: frames=[3,5,1], ref=2 → evict 5 → [3,1,2]
t=11: frames=[3,1,2], ref=4 → evict 1 → [3,2,4]
LRU faults = 8

t=4: frames=[1,2,3], ref=4. Next uses: 1→t=7, 2→t=9, 3→t=5. Evict 2 (farthest). → [1,3,4]
t=6: miss on 5? No — check: frames after t=4: [1,3,4]. Ref 3: hit. Ref 5 at t=6: [1,3,4]→evict 4 → [1,3,5]
t=7: ref=1: hit. t=8: ref=3: hit. t=9: ref=2: miss → evict 5 → [1,3,2]. t=11: ref=4 → evict 1 → [3,2,4]
OPT faults: 1,2,3,4,5,2,4 = 7 faults

Key Formulas

UNIX Permission Patterns

Process Creation in UNIX

pid = fork();          // clone process; COW pages
if (pid == 0) {        // child
    execve("/bin/prog", argv, envp);
} else {               // parent
    wait(&status);
}

Common Gotchas in Exams

Lecture Topics vs Exam Mapping

Last-Minute Checklist

• I can calculate TLB EAT for any number of page table levels
• I can trace OPT, LRU, FIFO page replacement on a reference string
• I know why FIFO suffers Bélády's anomaly but OPT/LRU don't
• I can calculate average waiting time for FCFS, SJF, SRTF, RR
• I know what the context switch saves and what must be flushed (TLB)
• I can build a UNIX access matrix from policy statements
• I can work out UNIX read/write/execute for any user given rwx + groups
• I understand setuid and what it does
• I can calculate circular buffer capacity for burst scenarios
• I can describe how demand paging EAT changes with page fault rate
• I understand CFS: vruntime, target latency, minimum granularity
• I know the structure of a UNIX i-node and how to count disk accesses for path traversal
• I can explain why pipes are more efficient than file-based IPC
• I understand the two representations of the access matrix and when to prefer each