On this page

OS Algorithms: Deadlock Avoidance, Page Replacement, Disk Scheduling & File Allocation

Every operating-systems course, textbook and campus interview eventually reaches the same handful of algorithms: the Banker's algorithm, page replacement on a reference string, disk-arm scheduling on a request queue, and the inode block-pointer arithmetic. They show up as numericals — "how many page faults with 3 frames?", "is this state safe?", "total head movement under C-LOOK?" — and they are easy marks if you know the procedure exactly and very easy to fumble if you only know the idea.

The rest of this site explains how these mechanisms work in a real kernel: Virtual Memory covers page tables, faults and Linux reclaim; I/O & Storage covers the block layer and NVMe; File Systems covers inodes, journaling and the VFS; Deadlocks, Livelocks & Starvation covers deadlock in application code — lock ordering, tryLock, thread dumps. This page is the algorithms companion: the textbook procedures, each with a fully worked numeric example in step-by-step tables, plus the honest note about what real systems actually do.

How to use this page

Work every example with a pencil before reading the table. The tables are the answer key. CPU-scheduling numericals (FCFS, SJF, SRTF, Round Robin, priority, Gantt charts, waiting and turnaround times) are already covered in CPU Scheduling & Context Switching, so they are not repeated here.


Part 1 — Deadlocks

Coffman conditions: a recap

A deadlock is a set of processes, each waiting for an event (usually a resource release) that only another process in the set can cause. Coffman, Elphick and Shoshani (1971) showed four conditions must all hold simultaneously:

#ConditionMeaningHow to break it
1Mutual exclusionAt least one resource is non-shareableMake the resource shareable (read-only files, lock-free structures) — often impossible
2Hold and waitA process holds one resource while waiting for anotherRequest everything up front, or release everything before requesting more
3No preemptionResources cannot be forcibly taken awayAllow preemption (take the resource, roll the holder back) — works for CPU and memory, not for a half-written printer job
4Circular waitA cycle P1 → P2 → … → Pn → P1 of waitsImpose a global ordering on resources and always acquire in increasing order

The Deadlocks page covers how these show up in Java, Go and databases. Here we care about the formal models the OS textbook uses to reason about them.

Resource-allocation graphs

A resource-allocation graph (RAG) has two node types: processes (circles) and resource types (rectangles, with one dot per instance). Two edge types:

  • Request edge P → R: process P has requested an instance of R and is waiting.
  • Assignment edge R → P: an instance of R has been allocated to P.

Rule 1 — single instance per resource type: a cycle in the graph is necessary and sufficient for deadlock.

Rule 2 — multiple instances: a cycle is necessary but not sufficient. A cycle can exist with no deadlock because some instance outside the cycle may be released.

Graph A — single-instance, cycle, deadlocked:

flowchart LR
    P1(("P1")) -->|"requests"| R2["R2 (1 instance)"]
    R2 -->|"held by"| P2(("P2"))
    P2 -->|"requests"| R1["R1 (1 instance)"]
    R1 -->|"held by"| P1

P1 holds R1 and wants R2; P2 holds R2 and wants R1. Each resource has exactly one instance, so the cycle P1 → R2 → P2 → R1 → P1 means a deadlock. Nobody can proceed.

Graph B — multi-instance, cycle, but NOT deadlocked:

flowchart LR
    P1(("P1")) -->|"requests"| R1["R1 (2 instances)"]
    R1 -->|"held by"| P2(("P2"))
    R1 -->|"held by"| P3(("P3"))
    P3 -->|"requests"| R2["R2 (2 instances)"]
    R2 -->|"held by"| P1
    R2 -->|"held by"| P4(("P4"))

There is a cycle P1 → R1 → P3 → R2 → P1. But P2 holds an instance of R1 and is not waiting for anything; when P2 finishes it releases its R1 instance, P1 gets it, and the cycle breaks. Likewise P4 can finish and release an R2 instance to P3. A cycle in a multi-instance graph only means "possibly deadlocked" — you need the detection algorithm (below) to decide.

Graph C — no cycle, therefore no deadlock (in either model): if P1 waits for R1 held by P2 and P2 is not waiting for anything, P2 eventually runs to completion and releases R1.

Wait-for graph

For single-instance resources you can collapse the RAG into a wait-for graph: remove the resource nodes and draw Pi → Pj whenever Pi waits for a resource Pj holds. Deadlock exists iff the wait-for graph has a cycle. Cycle detection is a DFS, O(V + E). This is exactly what PostgreSQL's deadlock detector and the JVM's ThreadMXBean.findDeadlockedThreads() do.

Four ways to handle deadlock

StrategyIdeaCostWho uses it
PreventionStructurally deny one Coffman condition so deadlock is impossibleLower utilisation, programmer disciplineLock ordering in kernels (Linux lockdep enforces it), "acquire all locks up front" in 2PL variants
AvoidanceKnow each process's maximum claim; grant a request only if the resulting state is safeNeeds advance knowledge of max needs; O(m·n²) per requestTextbooks, some real-time and embedded systems, batch schedulers that reserve resources
Detection and recoveryLet deadlocks happen, periodically detect, then break themPeriodic detection cost + lost work on recoveryDatabases (PostgreSQL, MySQL InnoDB, SQL Server), JVM tooling
Ignorance (ostrich algorithm)Assume deadlocks are rare; reboot or kill if they happenOccasional hangGeneral-purpose OSes for user-level resources — Linux, Windows, macOS

The key distinction interviewers probe: prevention constrains how requests are made (always lock A before B); avoidance examines each request at runtime against known maximums and may refuse a request even though the resources are free.

Prevention, condition by condition

  • Mutual exclusion — usually cannot be denied; a mutex is mutual exclusion. Spooling helps for some devices (the print spooler is the only process that "holds" the printer).
  • Hold and wait — Protocol 1: a process requests all its resources before it starts. Protocol 2: a process may request only when it holds nothing. Both waste resources (held long before use) and can starve processes needing many popular resources.
  • No preemption — if a process holding resources requests one that cannot be granted immediately, it releases everything it holds and restarts later. Works for resources whose state is easily saved (CPU registers, memory pages), not for mutexes guarding half-updated data.
  • Circular wait — number every resource type, F(tape) = 1, F(disk) = 5, F(printer) = 12; a process may request Rj only if F(Rj) > F(every resource it holds). Proof: a cycle would need F(R0) < F(R1) < … < F(Rn) < F(R0), a contradiction. This is the only prevention technique widely used in practice.

Safe and unsafe states

A state is safe if there exists a safe sequence ⟨P1, P2, …, Pn⟩: an order in which every process can obtain its maximum remaining need using the currently available resources plus the resources released by all the processes before it in the sequence.

  • Safe ⇒ no deadlock (the OS can always steer to completion).
  • Unsafe ⇏ deadlock. Unsafe means the OS can no longer guarantee completion — if processes ask for their maximums in a bad order, deadlock will occur.
  • Deadlocked states are a subset of unsafe states.
flowchart TB
    subgraph ALL["All states"]
        S["Safe states: a completion order is guaranteed"]
        subgraph U["Unsafe states"]
            D["Deadlocked states"]
        end
    end

Avoidance algorithms keep the system in the safe region forever: a request is granted only if the state after granting it is still safe.

For single-instance resources, avoidance uses the RAG with claim edges (dashed Pi → Rj meaning "may request in future"): a request is granted only if converting the claim edge to an assignment edge creates no cycle. For multiple instances you need the Banker's algorithm.

The Banker's algorithm

Dijkstra (1965) named it after a bank that never lends out its cash in a way that would leave it unable to satisfy all customers. With n processes and m resource types it keeps four data structures:

StructureShapeMeaning
Availablevector of mFree instances of each resource type right now
Maxn × mMaximum demand each process may ever make (declared in advance)
Allocationn × mInstances currently allocated to each process
Needn × mRemaining possible demand: Need = Max − Allocation

Safety algorithm

1. Work := Available ; Finish[i] := false for all i
2. Find an i with Finish[i] = false and Need[i] <= Work   (component-wise)
   If none exists, go to step 4
3. Work := Work + Allocation[i] ; Finish[i] := true ; append Pi to the sequence ; go to step 2
4. If Finish[i] = true for all i, the state is SAFE; otherwise UNSAFE

Cost: O(m × n²) — up to n passes, each scanning n processes and comparing m resources.

Intuition for step 3: if Pi's remaining need fits in Work, we can pretend to give it everything, let it run to completion, and reclaim all of its allocation.

Resource-request algorithm

When process Pi issues Request[i]:

1. If Request[i] > Need[i]       -> ERROR: process exceeded its declared maximum
2. If Request[i] > Available     -> Pi must WAIT: resources not available
3. Pretend to allocate:
       Available     := Available     - Request[i]
       Allocation[i] := Allocation[i] + Request[i]
       Need[i]       := Need[i]       - Request[i]
4. Run the safety algorithm on the pretended state:
       SAFE   -> grant the request (keep the new state)
       UNSAFE -> roll back to the old state; Pi must WAIT

Note the two distinct reasons for waiting: not available now (step 2) and available but unsafe (step 4). The second one is what makes avoidance avoidance.

Worked example: 5 processes × 3 resources

Resource types A, B, C with 10, 5 and 7 total instances. Snapshot at time T0:

ProcessAllocation (A B C)Max (A B C)Need = Max − Alloc (A B C)
P00 1 07 5 37 4 3
P12 0 03 2 21 2 2
P23 0 29 0 26 0 0
P32 1 12 2 20 1 1
P40 0 24 3 34 3 1
Total allocated7 2 5

Available = Total − Allocated = (10, 5, 7) − (7, 2, 5) = (3, 3, 2).

Step 1: is T0 safe?

Scan the processes in index order repeatedly, picking the first one whose Need ≤ Work.

StepWork beforeCandidate checksChosenNeed ≤ Work?Work after (Work + Alloc)
1(3,3,2)P0 needs (7,4,3): noP1(1,2,2) ≤ (3,3,2) ✓(3,3,2)+(2,0,0) = (5,3,2)
2(5,3,2)P2 needs (6,0,0): 6 > 5 noP3(0,1,1) ≤ (5,3,2) ✓(5,3,2)+(2,1,1) = (7,4,3)
3(7,4,3)—P4(4,3,1) ≤ (7,4,3) ✓(7,4,3)+(0,0,2) = (7,4,5)
4(7,4,5)second pass, start at P0P0(7,4,3) ≤ (7,4,5) ✓(7,4,5)+(0,1,0) = (7,5,5)
5(7,5,5)—P2(6,0,0) ≤ (7,5,5) ✓(7,5,5)+(3,0,2) = (10,5,7)

All Finish = true, so T0 is safe with sequence ⟨P1, P3, P4, P0, P2⟩. The final Work equals the total resources — a useful self-check: if it does not, you made an arithmetic slip.

Safe sequences are not unique

⟨P3, P1, P4, P2, P0⟩ is also safe. Exams accept any valid sequence; show the Work vector at each step so the examiner can verify yours.

Step 2: P1 requests (1, 0, 2) — granted

  1. Request (1,0,2) ≤ Need[P1] (1,2,2)? ✓
  2. Request (1,0,2) ≤ Available (3,3,2)? ✓
  3. Pretend to allocate:
BeforeAfter
Available(3,3,2)(2,3,0)
Allocation[P1](2,0,0)(3,0,2)
Need[P1](1,2,2)(0,2,0)
  1. Safety check on the new state:
StepWork beforeChosenNeedWork after
1(2,3,0)P0? (7,4,3) no → P1(0,2,0) ✓(2,3,0)+(3,0,2) = (5,3,2)
2(5,3,2)P2? (6,0,0) no → P3(0,1,1) ✓(7,4,3)
3(7,4,3)P4(4,3,1) ✓(7,4,5)
4(7,4,5)P0(7,4,3) ✓(7,5,5)
5(7,5,5)P2(6,0,0) ✓(10,5,7)

Safe sequence ⟨P1, P3, P4, P0, P2⟩ exists → request granted. New Available = (2,3,0).

Step 3: P4 requests (3, 3, 0) — must wait (not available)

  1. (3,3,0) ≤ Need[P4] (4,3,1)? ✓
  2. (3,3,0) ≤ Available (2,3,0)? ✗ — A: 3 > 2.

P4 waits. The safety algorithm is never even run.

Step 4: P0 requests (0, 2, 0) — denied (unsafe)

  1. (0,2,0) ≤ Need[P0] (7,4,3)? ✓
  2. (0,2,0) ≤ Available (2,3,0)? ✓ — the resources are physically free.
  3. Pretend: Available = (2,1,0); Allocation[P0] = (0,3,0); Need[P0] = (7,2,3).
  4. Safety check with Work = (2,1,0):
ProcessNeedNeed ≤ (2,1,0)?
P0(7,2,3)✗ (A)
P1(0,2,0)✗ (B: 2 > 1)
P2(6,0,0)✗ (A)
P3(0,1,1)✗ (C: 1 > 0)
P4(4,3,1)✗

No process can finish → the state would be unsafe → roll back; P0 waits even though two B's are sitting idle. That refusal is the whole point of avoidance: granting it would not deadlock immediately, but it would hand the OS a state from which it cannot guarantee completion.

Banker's algorithm in Python

from typing import List, Optional, Tuple

Vec = List[int]

def le(a: Vec, b: Vec) -> bool:
    return all(x <= y for x, y in zip(a, b))

def safety(available: Vec, alloc: List[Vec], need: List[Vec]) -> Optional[List[int]]:
    """Return a safe sequence of process indices, or None if the state is unsafe."""
    work, finish, seq = list(available), [False] * len(alloc), []
    progressed = True
    while progressed:
        progressed = False
        for i in range(len(alloc)):
            if not finish[i] and le(need[i], work):
                work = [w + a for w, a in zip(work, alloc[i])]
                finish[i], progressed = True, True
                seq.append(i)
    return seq if all(finish) else None

def request(i: int, req: Vec, available: Vec, alloc: List[Vec], need: List[Vec]) -> Tuple[str, Optional[List[int]]]:
    if not le(req, need[i]):
        raise ValueError(f"P{i} exceeded its maximum claim")
    if not le(req, available):
        return "wait: not available", None
    # pretend
    avail2 = [a - r for a, r in zip(available, req)]
    alloc2 = [row[:] for row in alloc]; need2 = [row[:] for row in need]
    alloc2[i] = [a + r for a, r in zip(alloc2[i], req)]
    need2[i] = [n - r for n, r in zip(need2[i], req)]
    seq = safety(avail2, alloc2, need2)
    if seq is None:
        return "wait: unsafe", None
    available[:], alloc[:], need[:] = avail2, alloc2, need2   # commit
    return "granted", seq

if __name__ == "__main__":
    alloc = [[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]]
    mx    = [[7,5,3],[3,2,2],[9,0,2],[2,2,2],[4,3,3]]
    total = [10,5,7]
    need  = [[m - a for m, a in zip(mr, ar)] for mr, ar in zip(mx, alloc)]
    avail = [t - sum(r[j] for r in alloc) for j, t in enumerate(total)]
    assert avail == [3,3,2]
    assert safety(avail, alloc, need) == [1,3,4,0,2]
    assert request(1, [1,0,2], avail, alloc, need) == ("granted", [1,3,4,0,2])
    assert request(4, [3,3,0], avail, alloc, need)[0] == "wait: not available"
    assert request(0, [0,2,0], avail, alloc, need)[0] == "wait: unsafe"
    print("all Banker's checks pass")

Why nobody runs Banker's in a general-purpose OS

It needs every process to declare its maximum demand up front, a fixed number of processes and resources, and processes that eventually release everything. A web server does not know how many file descriptors it will open tomorrow. Banker's survives in batch schedulers and resource-reservation systems — and in interviews.

Detection algorithm for multi-instance resources

When you do not know maximums, you let processes request freely and periodically check for deadlock. The detection algorithm looks almost identical to the safety algorithm but uses the current outstanding requests instead of Need:

1. Work := Available
   Finish[i] := true  if Allocation[i] = 0   (holds nothing, cannot be part of a deadlock)
   Finish[i] := false otherwise
2. Find i with Finish[i] = false and Request[i] <= Work ; if none, go to 4
3. Work := Work + Allocation[i] ; Finish[i] := true ; go to 2
4. Every Pi with Finish[i] = false is DEADLOCKED

The optimistic assumption in step 3: if Pi's current request can be satisfied, it will finish and release everything without asking for more. If that is wrong, the next detection run will catch it.

Worked example

Resources A = 7, B = 2, C = 6. Snapshot:

ProcessAllocation (A B C)Request (A B C)
P00 1 00 0 0
P12 0 02 0 2
P23 0 30 0 0
P32 1 11 0 0
P40 0 20 0 2

Allocated total = (7, 2, 6) → Available = (0, 0, 0).

StepWork beforeChosenRequest ≤ Work?Work after
1(0,0,0)P0(0,0,0) ✓(0,1,0)
2(0,1,0)P1? (2,0,2) no → P2(0,0,0) ✓(3,1,3)
3(3,1,3)P3(1,0,0) ✓(5,2,4)
4(5,2,4)P4(0,0,2) ✓(5,2,6)
5(5,2,6)P1(2,0,2) ✓(7,2,6)

All finish → no deadlock, even though Available is zero.

Now suppose P2 requests one more C: Request[P2] = (0, 0, 1).

StepWorkCheck
1(0,0,0)P0 (0,0,0) ✓ → Work = (0,1,0)
2(0,1,0)P1 (2,0,2) ✗, P2 (0,0,1) ✗, P3 (1,0,0) ✗, P4 (0,0,2) ✗ — stuck

P0 finishes but returns only one B. P1, P2, P3 and P4 are deadlocked.

How often to run detection

PolicyTrade-off
On every request that cannot be granted immediatelyFinds the deadlock at once and identifies the process that "caused" it, but expensive
Every N minutesCheap; the graph may contain many tangled cycles by then
When CPU utilisation drops below a threshold (e.g. 40%)Deadlocked processes stop using CPU — a cheap signal
After a timeout on a lock waitWhat databases do: PostgreSQL runs detection after deadlock_timeout (default 1s) of waiting

Recovery

Once you have found a deadlocked set:

Process termination

  • Abort all deadlocked processes — simple, guaranteed, throws away a lot of work.
  • Abort one at a time until the cycle breaks — rerun detection after each abort. Victim selection criteria: priority, CPU time consumed so far, time remaining, resources held, number of resources needed to finish, interactive vs batch, how many must be killed.

Resource preemption

  1. Select a victim — minimise cost (resources held, time consumed).
  2. Rollback — return the victim to a safe earlier state (checkpoint) or abort it entirely (total rollback).
  3. Avoid starvation — the same process must not be picked every time; include the number of rollbacks in the cost factor.

Databases are the canonical real-world user: InnoDB picks the transaction that modified the fewest rows, rolls it back and returns ERROR 1213: Deadlock found when trying to get lock; the application retries. See Concurrency Control for how lock managers build the wait-for graph.


Part 2 — Page Replacement

When a page fault occurs and no frame is free, the OS must pick a victim page to evict. If the victim is dirty it must be written back first, so a replacement can cost two disk I/Os. The Virtual Memory page explains faults, demand paging and Linux reclaim mechanics; here we compare the algorithms on paper.

The cost model: effective access time

With memory access time ma, page-fault service time f and fault probability p:

EAT = (1 - p) x ma + p x f

With ma = 200 ns and f = 8 ms (HDD):

pEATSlowdown
0200 ns1x
1 / 1,000,000200 + 8 = 208 ns1.04x
1 / 100,000≈ 280 ns1.4x
1 / 1,000≈ 8.2 µs41x

For less than 10% degradation you need p < 0.0000025 — one fault in 400,000 accesses. That is why the replacement policy matters so much and why thrashing is so dramatic. (On NVMe, f drops to ~20–100 µs, which softens but does not remove the cliff.)

The reference string

All algorithms are evaluated on a reference string — the sequence of page numbers accessed (consecutive repeats are collapsed because they cannot fault). We use the classic string throughout:

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1      (20 references, pages 0-4 and 7)

Convention in the tables: frames listed left to right in slot order; F = fault, H = hit; "evict" names the victim. The first faults filling empty frames are compulsory (cold) misses — every algorithm pays them.

FIFO

Evict the page that has been in memory the longest. Implement with a queue; O(1) per reference.

FIFO, 3 frames:

#RefFrame 1Frame 2Frame 3ResultEvicted
177F
2070F
31701F
42201F7
50201H
63231F0
70230F1
84430F2
92420F3
103423F0
110023F4
123023H
132023H
141013F2
152012F3
160012H
171012H
187712F0
190702F1
201701F2

FIFO, 3 frames: 15 faults, 5 hits. Notice reference 7: FIFO evicts page 0 just after it was used, because 0 happens to be the oldest arrival — age of arrival says nothing about future use.

Optimal (OPT / MIN)

Evict the page that will not be used for the longest time in the future (Belady, 1966). Provably minimal fault count for a fixed number of frames. Unimplementable online (it needs the future), but it is the yardstick: "LRU is within 12% of OPT on this workload".

OPT, 3 frames:

#RefF1F2F3ResultEvicted (next use)
177F
2070F
31701F
42201F7 (next at #18; 0 at #5, 1 at #14)
50201H
63203F1 (next at #14; 2 at #9, 0 at #7)
70203H
84243F0 (next at #11; 2 at #9, 3 at #10)
92243H
103243H
110203F4 (never used again)
123203H
132203H
141201F3 (never used again)
152201H
160201H
171201H
187701F2 (never used again)
190701H
201701H

OPT, 3 frames: 9 faults. Tie-break rule when several pages are never used again: any choice is optimal; exams usually say "pick the one that arrived first" (FIFO among ties).

LRU — Least Recently Used

Evict the page that has not been used for the longest time in the past. It is OPT run on the reversed past: recency as a predictor of future use (temporal locality).

LRU, 3 frames:

#RefF1F2F3ResultEvicted (last use)
177F
2070F
31701F
42201F7 (#1)
50201H
63203F1 (#3)
70203H
84403F2 (#4)
92402F3 (#6)
103432F0 (#7)
110032F4 (#8)
123032H
132032H
141132F0 (#11)
152132H
160102F3 (#12)
171102H
187107F2 (#15)
190107H
201107H

LRU, 3 frames: 12 faults.

Implementing true LRU

ImplementationOn every referenceOn replacementProblem
Counters / timestampsCopy a logical clock into the page-table entryScan all entries for the minimum timestamp — O(n)A memory write per reference; clock overflow
Stack (doubly linked list)Move the referenced page to the top — six pointer updatesVictim is at the bottom — O(1)Pointer updates on every memory access
Hash map + doubly linked listO(1) move-to-frontO(1)The classic software LRU cache (interview staple) — far too slow for hardware memory references
Matrix (n × n bits)Set row k to 1s, then column k to 0sRow with the smallest binary valueHardware only, small n

No mainstream CPU maintains true LRU for memory pages: it would need a write on every memory access. What hardware provides is a reference (accessed) bit per page-table entry, set by the MMU when the page is touched, plus a dirty bit set on writes. Everything practical is an LRU approximation built from those two bits.

The software version, which you will be asked to write in interviews, is a hash map plus a doubly linked list:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cap, self.data = capacity, OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)          # mark most recently used
        return self.data[key]

    def put(self, key, value) -> None:
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.cap:
            self.data.popitem(last=False)   # evict least recently used

LRU approximations

  • Additional-reference-bits (aging): keep an 8-bit history byte per page. At every timer tick, shift the byte right one bit and copy the reference bit into the high-order bit, then clear the reference bit. Interpret the byte as an unsigned number; the lowest value is the approximate LRU page. 11000100 (used in the last two intervals) beats 01110111.
  • Second chance / Clock — below.
  • Enhanced second chance — Clock using both reference and dirty bits.

Clock (second chance)

Arrange frames in a circular list with a "hand". On a fault:

loop:
    if frame[hand].ref == 0: evict it, load the new page here (ref := 1), advance hand, stop
    else: frame[hand].ref := 0 (second chance), advance hand

On a hit the hardware sets ref := 1 and the hand does not move. If every bit is 1, the hand sweeps a full circle clearing bits and Clock degenerates to FIFO.

Clock, 3 frames (bits shown as reference bits for F1 F2 F3; hand = slot the hand points to after the reference, 0-indexed):

#RefFramesRef bitsHand afterResultWhat happened
177 - -1 0 01Ffill
207 0 -1 1 02Ffill
317 0 11 1 10Ffill
422 0 11 0 01Ffull sweep clears all bits, evict 7
502 0 11 1 01Hset bit on 0
632 0 31 0 10F0 had bit 1 → cleared; 1 has bit 0 → evict 1
702 0 31 1 10H
844 0 31 0 01Fsweep clears 2,0,3; evict 2
924 2 31 1 02Fevict 0 (bit 0)
1034 2 31 1 12H
1104 2 00 0 10Fsweep clears 3,4,2; evict 3
1233 2 01 0 11Fevict 4 (bit 0)
1323 2 01 1 11H
1413 1 00 1 02Fsweep clears 2,0,3; evict 2
1523 1 20 1 10Fevict 0
1600 1 21 1 11Fevict 3
1710 1 21 1 11H
1870 7 20 1 02Fsweep clears 1,2,0; evict 1
1900 7 21 1 02H
2010 7 11 1 10Fevict 2

Clock, 3 frames: 14 faults — between LRU (12) and FIFO (15), as expected for an approximation of LRU that collapses to FIFO when every page is recently used. With only three frames almost every page is "recent"; Clock shines with many frames, where it gets close to LRU at a fraction of the cost.

Enhanced second chance (NRU classes)

Use the (reference, dirty) pair to rank pages into four classes:

Class(ref, dirty)MeaningEviction preference
0(0, 0)Neither recently used nor modifiedBest victim — free to drop
1(0, 1)Not recently used but dirtyMust write back first
2(1, 0)Recently used, cleanProbably needed soon
3(1, 1)Recently used and dirtyWorst victim

The hand scans for the lowest non-empty class (up to four sweeps in the worst case), preferring to evict clean pages because it avoids a write-back I/O. Classic Mac OS used this; Windows' working-set trimmer and the BSDs use close relatives.

LFU and MFU

  • LFU (least frequently used) — evict the page with the smallest reference count. Problem: a page used heavily during initialisation keeps a high count forever. Fix: decay counts (shift right periodically).
  • MFU (most frequently used) — evict the page with the largest count, on the theory that a page with a small count was just brought in and has yet to be used. Rarely good.

Neither is common for OS page replacement. LFU variants are common in application caches: Caffeine's W-TinyLFU and Redis's allkeys-lfu policy (see Application-Level Caching).

The same string with 4 frames

AlgorithmFault pattern (F = fault, H = hit) for the 20 referencesFaults
FIFOF F F F H F H F H H F H H F F H H F H H10
OPTF F F F H F H F H H H H H F H H H F H H8
LRUF F F F H F H F H H H H H F H H H F H H8
ClockF F F F H F H F H H H H H F F H H F H H9

Frame contents for 4-frame LRU, so you can check your work: after #4 7 0 1 2; #6 evicts 7 → 3 0 1 2; #8 evicts 1 → 3 0 4 2; #14 evicts 4 → 3 0 1 2; #18 evicts 3 → 7 0 1 2. OPT happens to tie LRU here (different victims at #14 and #18, same count).

Summary of the classic string:

FramesFIFOClockLRUOPT
31514129
410988

Belady's anomaly

Intuition says more frames means fewer faults. For FIFO, that is false. Reference string:

1 2 3 4 1 2 5 1 2 3 4 5

FIFO, 3 frames:

Ref123412512345
F1111444555555
F222211111333
F33332222244
FFFFFFFHHFFH

9 faults.

FIFO, 4 frames:

Ref123412512345
F1111111555544
F222222211115
F33333332222
F4444444333
FFFFHHFFFFFF

10 faults — one more frame, one more fault. That is Belady's anomaly. The extra frame let pages 1 and 2 survive until 5 arrived, which then pushed the FIFO queue into evicting exactly the pages about to be needed.

For the same string, LRU gives 10 faults with 3 frames and 8 with 4; OPT gives 7 and 6. Neither ever gets worse with more frames.

Stack algorithms: why LRU and OPT are immune

An algorithm is a stack algorithm if, for every reference string and every n, the set of pages in memory with n frames is a subset of the set with n + 1 frames (the inclusion property: M(n, t) ⊆ M(n+1, t)). If that holds, any hit with n frames is also a hit with n + 1 frames, so faults can never increase.

  • LRU is a stack algorithm: with n frames it holds the n most recently used pages, which are always among the n + 1 most recently used.
  • OPT is a stack algorithm: it holds the n pages needed soonest.
  • FIFO is not: in the example above, after reference #7 the 3-frame set is {5, 1, 2} but the 4-frame set is {5, 2, 3, 4} — page 1 is in the smaller memory but not the larger.
  • Clock and second chance are not stack algorithms either (they degenerate to FIFO), so they can in principle exhibit the anomaly.

A practical benefit: for a stack algorithm you can compute the fault count for every memory size in a single pass over the trace (Mattson's stack-distance algorithm) — which is how cache simulators and Redis/CDN sizing tools produce miss-ratio curves.

What Linux actually does

Linux does not run any single textbook algorithm. Its reclaim is a two-list Clock approximation:

  • Pages live on an active and an inactive LRU list, separately for anonymous memory and file-backed (page cache) memory.
  • New pages enter the inactive list. A page referenced again while inactive is promoted to active (second chance with memory).
  • kswapd and direct reclaim scan the tail of the inactive list, checking the accessed bits: referenced pages are rotated; unreferenced clean pages are dropped; dirty ones are written back first; anonymous pages go to swap.
  • When the inactive list gets too small, pages are demoted from the tail of the active list.
  • Workingset detection remembers "shadow entries" for evicted file pages; a quick re-fault means the inactive list is too small, and the kernel rebalances.
  • MGLRU (multi-generational LRU), merged in 6.1 and default on many distros and Android/ChromeOS, replaces the two lists with several generations aged by page-table scans, plus a feedback loop between anon and file. It cut kswapd CPU and improved tail latency significantly on memory-pressured devices.

The Virtual Memory page covers swap, swappiness, PSI and the OOM killer — the operational side of this; Page Cache & fsync covers dirty-page writeback.

Scan resistance

Plain LRU is wrecked by a single large sequential scan (one cat of a 50GB log evicts your whole hot set). The two-list design, ARC, 2Q, LRU-K and MGLRU all exist mainly to be scan resistant: a page has to prove itself with a second reference before it can displace established hot pages. PostgreSQL uses a small ring buffer for big sequential scans for the same reason.

Thrashing

Thrashing is when a system spends more time paging than executing. The classic feedback loop:

flowchart LR
    A["Too many processes for available frames"] --> B["Page faults rise"]
    B --> C["Processes block on paging I/O"]
    C --> D["CPU utilisation drops"]
    D --> E["Long-term scheduler admits more processes to use the idle CPU"]
    E --> A

Plotting CPU utilisation against degree of multiprogramming gives a curve that rises, peaks, then collapses — past the peak, adding processes makes throughput fall off a cliff.

The root cause: the sum of the processes' localities (the sets of pages they actively use) exceeds physical memory. With global replacement one thrashing process steals frames from others and makes them thrash too; local replacement contains the damage but does not cure it.

The working-set model

Denning's (1968) working set WS(t, Δ) is the set of distinct pages referenced in the most recent Δ references (the working-set window).

Example with Δ = 10 on this reference string:

2 6 1 5 7 7 7 7 5 1 | 6 2 3 4 1 2 3 4 4 4 3 4 3 4 4 4 | 1 3 2 3 4 4 4 3 4 4 4
                    t1                                t2
TimeLast 10 referencesWorking setWSS
t1 (after 10th ref)2 6 1 5 7 7 7 7 5 1{1, 2, 5, 6, 7}5
t2 (after 26th ref)3 4 4 4 3 4 3 4 4 4{3, 4}2

The process moved from a 5-page locality to a 2-page locality; its frame demand shrank.

  • Δ too small → does not cover the whole locality → faults.
  • Δ too large → overlaps several localities → wastes frames.
  • Δ = ∞ → the entire program.

Policy: total demand D = Σ WSSi. If D > available frames m, thrashing is imminent — suspend (swap out) a process and give its frames to the others. If D < m with room to spare, admit another process. This keeps multiprogramming as high as possible without thrashing.

Implementation: exact tracking of a moving window is too expensive. Approximate it with a timer interrupt plus reference bits: every 5,000 references, copy each page's reference bit into in-memory history bits and clear it; a page is in the working set if any history bit is set. Linux's workingset-refault accounting and PSI memory pressure (/proc/pressure/memory) are modern descendants.

Page-fault frequency (PFF)

A more direct control loop: measure each process's fault rate.

flowchart TB
    M["Measure fault rate of a process"] --> H{"Rate above upper bound?"}
    H -->|"yes"| G["Give it another frame"]
    H -->|"no"| L{"Rate below lower bound?"}
    L -->|"yes"| T["Take a frame away"]
    L -->|"no"| K["Leave it alone"]
    G --> S{"No free frames left?"}
    S -->|"yes"| SW["Suspend a process, redistribute its frames"]

PFF needs no window parameter and reacts to the symptom (faulting) rather than the model of locality.

Frame allocation

How many frames does each process get?

  • Minimum — set by the architecture: enough frames to complete any single instruction. An instruction that references memory indirectly through memory, with an operand that straddles a page boundary, may touch six pages; the process needs at least that many frames or that instruction can never complete.
  • Equal allocation — m frames, n processes → m / n each. 93 frames, 5 processes → 18 each with 3 left as a free-frame pool.
  • Proportional allocation — ai = (si / S) × m where si is the size (virtual memory) of process i and S = Σ si.

Worked example: m = 62 frames, P1 of size 10 pages, P2 of size 127 pages, S = 137.

ProcessSizeShareFrames
P11010 / 137 × 62 = 4.534
P2127127 / 137 × 62 = 57.4757

(Round down, one frame left for the free pool.) A priority-weighted variant uses priority instead of, or as well as, size.

Global replacementLocal replacement
Victim chosen fromAll frames in the systemOnly the faulting process's frames
Allocation per processVaries over timeFixed (unless an allocator rebalances)
ThroughputUsually higherLower — idle frames in one process cannot help another
PredictabilityA process's fault rate depends on othersDepends only on its own behaviour
Used byLinux (with cgroup limits adding local-ish behaviour), most general-purpose OSesWindows working-set limits, real-time systems

Container memory limits (cgroups) are in effect local replacement bolted onto a global system: a pod hitting memory.max reclaims its own pages first.


Part 3 — Disk Scheduling

For a hard disk the cost of a request is dominated by seek time (moving the arm, ~3–10 ms) and rotational latency (waiting for the sector, ~4 ms average at 7200 rpm); the transfer itself is tiny. When many requests are pending, the order you serve them in determines how far the arm travels. The algorithms below minimise or bound total head movement. The I/O & Storage page has the short version and the Linux schedulers; here is the full worked set.

The worked request queue

  • Cylinders numbered 0 to 199.
  • Head currently at cylinder 53.
  • Pending queue (arrival order): 98, 183, 37, 122, 14, 124, 65, 67.

Requests below the head: 37, 14. Above the head: 65, 67, 98, 122, 124, 183.

FCFS

Serve in arrival order. Fair, no starvation, and no optimisation at all.

MoveFrom → ToDistance
153 → 9845
298 → 18385
3183 → 37146
437 → 12285
5122 → 14108
614 → 124110
7124 → 6559
865 → 672
Total640 cylinders

The wild swings (122 → 14 → 124) are what every other algorithm is trying to avoid.

SSTF — Shortest Seek Time First

Always serve the pending request closest to the current head. It is greedy, like SJF for the disk.

MoveHead atCandidates (distance)ChosenDistance
15365 (12), 37 (16), 67 (14) …6512
26567 (2)672
36737 (30), 98 (31)3730
43714 (23), 98 (61)1423
51498 (84)9884
698122 (24)12224
7122124 (2)1242
8124183 (59)18359
Total236 cylinders

Order: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183.

SSTF is not optimal: 53 → 37 → 14 → 65 → 67 → 98 → 122 → 124 → 183 costs only 208. And it can starve far requests: if new requests keep arriving near the head, a request at cylinder 190 may wait indefinitely.

SCAN (elevator)

The arm moves in one direction serving every request on the way, goes all the way to the end of the disk, then reverses.

SCAN, moving toward 0:

From → ToDistanceNote
53 → 3716
37 → 1423
14 → 014travel to the edge
0 → 6565reverse
65 → 67 → 98 → 122 → 124 → 183118
Total236= 53 + 183

SCAN, moving toward 199:

From → ToDistance
53 → 65 → 67 → 98 → 122 → 124 → 183130
183 → 199 (edge)16
199 → 37162
37 → 1423
Total331 = (199 − 53) + (199 − 14)

Shortcut formula for SCAN: distance to the edge in the current direction, plus the full width from that edge to the farthest request on the other side.

C-SCAN (circular SCAN)

Serve in one direction only; on reaching the end, jump back to the other end without serving anything and continue in the same direction. This treats the cylinders as a circular list and gives a more uniform wait: a request just behind the head waits at most one sweep, rather than two in SCAN (where requests at the far end, just served, get served again soonest and the middle is favoured).

C-SCAN, moving toward 199:

From → ToDistanceNote
53 → … → 183130serve 65, 67, 98, 122, 124, 183
183 → 19916to edge
199 → 0199return sweep, no service
0 → 14 → 3737
Total382 (counting the return)183 excluding the return

C-SCAN, moving toward 0: 53 → 37 → 14 → 0 (53), 0 → 199 return (199), 199 → 183 → … → 65 (134). Total 386, or 187 excluding the return.

Does the return sweep count?

Textbooks disagree. The return is a real seek (the arm physically moves) but it is fast — no service stops, so the drive can accelerate to full speed. State your convention explicitly in an exam: "Total head movement = 382 cylinders including the 199-cylinder return; 183 excluding it."

LOOK and C-LOOK

LOOK is SCAN that reverses at the last pending request instead of the disk edge. C-LOOK is C-SCAN that jumps from the last request in the direction of travel straight to the first request at the other end. Real implementations do this; nobody drives the arm to cylinder 199 for nothing.

LOOK toward 0: 53 → 37 → 14 (39), reverse 14 → 65 → … → 183 (169). Total 208.

LOOK toward 199: 53 → … → 183 (130), reverse 183 → 37 → 14 (169). Total 299.

C-LOOK toward 199: 53 → … → 183 (130), jump 183 → 14 (169), 14 → 37 (23). Total 322 (153 excluding the jump).

C-LOOK toward 0: 53 → 37 → 14 (39), jump 14 → 183 (169), 183 → 124 → 122 → 98 → 67 → 65 (118). Total 326 (157 excluding the jump).

Comparison on this queue

AlgorithmDirectionService orderTotal movement
FCFS—98, 183, 37, 122, 14, 124, 65, 67640
SSTF—65, 67, 37, 14, 98, 122, 124, 183236
SCANtoward 037, 14, (0), 65, 67, 98, 122, 124, 183236
SCANtoward 19965, 67, 98, 122, 124, 183, (199), 37, 14331
LOOKtoward 037, 14, 65, 67, 98, 122, 124, 183208
LOOKtoward 19965, 67, 98, 122, 124, 183, 37, 14299
C-SCANtoward 19965 … 183, (199), (0), 14, 37382 (183)
C-SCANtoward 037, 14, (0), (199), 183 … 65386 (187)
C-LOOKtoward 19965 … 183, 14, 37322 (153)
C-LOOKtoward 037, 14, 183 … 65326 (157)

Figures in brackets exclude the non-servicing return sweep.

Starvation and fairness

AlgorithmStarvationWait-time varianceNotes
FCFSNoneLow, but everyone waits longBaseline
SSTFYes — edge requests can wait foreverHighGreedy, not optimal
SCAN / LOOKNo — bounded by two sweepsMiddle cylinders favouredGood under heavy load
C-SCAN / C-LOOKNo — bounded by one sweep plus the returnMost uniformPreferred when fairness matters
N-step SCAN / FSCANNoBoundedFreeze the queue each sweep so new arrivals cannot monopolise the arm ("arm stickiness")

A disk-scheduling simulator

def total(path):
    return sum(abs(b - a) for a, b in zip(path, path[1:]))

def schedule(head, queue, algo, direction="up", max_cyl=199):
    lo = sorted((c for c in queue if c < head), reverse=True)   # nearest first
    hi = sorted(c for c in queue if c >= head)
    if algo == "FCFS":
        return [head, *queue]
    if algo == "SSTF":
        path, pending, cur = [head], list(queue), head
        while pending:
            cur = min(pending, key=lambda c: abs(c - cur))
            pending.remove(cur); path.append(cur)
        return path
    first, second = (hi, lo) if direction == "up" else (lo, hi)
    edge, other_edge = (max_cyl, 0) if direction == "up" else (0, max_cyl)
    if algo == "SCAN":
        return [head, *first, edge, *second]
    if algo == "LOOK":
        return [head, *first, *second]
    if algo == "C-SCAN":
        return [head, *first, edge, other_edge, *reversed(second)]
    if algo == "C-LOOK":
        return [head, *first, *reversed(second)]
    raise ValueError(algo)

q = [98, 183, 37, 122, 14, 124, 65, 67]
expected = {("FCFS", "up"): 640, ("SSTF", "up"): 236, ("SCAN", "down"): 236, ("SCAN", "up"): 331,
            ("LOOK", "down"): 208, ("LOOK", "up"): 299, ("C-SCAN", "up"): 382, ("C-LOOK", "up"): 322}
for (algo, d), want in expected.items():
    got = total(schedule(53, q, algo, d))
    assert got == want, (algo, d, got)
print("all disk-scheduling totals match")

Why SSDs and NVMe changed everything

The whole of Part 3 assumes a mechanical arm. Flash has no seek and no rotation: a random 4 KiB read costs roughly the same wherever it lands (~20–100 µs on NVMe vs ~5–10 ms on an HDD). Consequences:

  • Reordering by logical block address buys essentially nothing; the FTL remaps addresses anyway, so LBA order is not physical order.
  • The bottleneck becomes parallelism — an NVMe drive has many flash channels and wants a deep queue (64K queues × 64K commands in the spec). The scheduler's job is to keep queues full and avoid lock contention, not to minimise distance.
  • Linux's blk-mq defaults to none for NVMe, mq-deadline for SATA SSDs and HDDs (a deadline-bounded, sorted elevator), with BFQ for interactive desktops and Kyber for latency targets. Even HDDs do their own reordering via NCQ using the rotational position the OS cannot see.
  • Fairness and latency isolation (cgroup io.max, io.latency, io.cost) matter more than seek distance in a multi-tenant system.

The I/O & Storage page covers blk-mq, the FTL, write amplification and io_uring. The elevator algorithms are still worth knowing: they reappear in elevator scheduling LLD questions (Design an Elevator System), tape libraries, and any problem with a moving resource and a request queue.


Part 4 — File Allocation

A file is a sequence of logical blocks; the disk is a sequence of physical blocks. The allocation method decides how logical block i maps to a physical block. Goals: fast sequential access, fast random access, little wasted space, files that can grow. File Systems covers how ext4, XFS and btrfs actually allocate (extents, delayed allocation); this section is the textbook taxonomy.

Contiguous allocation

Each file occupies a run of consecutive blocks. The directory stores (start, length).

FileStartLengthBlocks
count020, 1
tr14314, 15, 16
mail19619 – 24
list28428 – 31
  • Access: logical block i is at start + i — perfect sequential and random access, minimal seeks. That is why CD-ROM/ISO 9660 and many embedded file systems use it.
  • External fragmentation: after deletes, free space is chopped into holes. Placement uses first-fit, best-fit or worst-fit (the same problem as contiguous memory allocation; see Memory Allocators). Compaction (defragmentation) fixes it at great cost.
  • Growth: you must know the size at creation. If the next block is taken, the file must be moved or creation fails. Over-allocating wastes space (internal fragmentation).

Extents are the modern compromise: a file is a short list of contiguous runs, each (start, length). ext4, XFS, NTFS, APFS and btrfs all use extents.

Linked allocation

Each file is a linked list of blocks; each block stores a pointer to the next. The directory stores the first and last block.

flowchart LR
    D["Directory: jeep starts at 9, ends at 25"] --> B9["Block 9"]
    B9 --> B16["Block 16"]
    B16 --> B1["Block 1"]
    B1 --> B10["Block 10"]
    B10 --> B25["Block 25: next = -1"]
  • No external fragmentation; any free block will do; files grow easily.
  • Sequential access only. Reaching block i requires following i pointers — i disk reads for random access.
  • Pointer overhead: a 4-byte pointer in a 512-byte block is 0.78% of space. Clusters (group 4 blocks) reduce overhead and seeks at the cost of internal fragmentation.
  • Reliability: one corrupt pointer loses the rest of the file.

The File Allocation Table moves all next-pointers into one table at the start of the volume, one entry per cluster. The directory entry holds the first cluster; FAT[c] holds the next cluster, an end-of-chain marker, 0 for free, or a bad-cluster marker.

Example: file test starts at cluster 217.

ClusterFAT entry
217618
339EOF
618339

Chain: 217 → 618 → 339 → EOF. Random access now walks the chain in the table — and the table can be cached in RAM, so it costs memory reads rather than disk reads. FAT12/16/32 and exFAT (SD cards, USB sticks, UEFI system partitions) work this way.

FAT size math: a 32 GiB volume with 4 KiB clusters has 2^35 / 2^12 = 2^23 = 8,388,608 clusters; at 4 bytes per FAT32 entry the table is 32 MiB (and FAT32 keeps two copies).

Indexed allocation

Bring all of a file's pointers together into one index block. The directory points to the index block; entry i of the index block is the physical address of logical block i.

  • Direct random access: one read for the index block (usually cached) plus one for the data.
  • No external fragmentation.
  • Wastes a whole block for the index even for a tiny file.
  • How big can a file get? One 4 KiB index block with 4-byte pointers holds 1,024 pointers → 4 MiB maximum. Hence the schemes for large files:
SchemeHow it works
Linked index blocksThe last pointer of an index block points to the next index block
Multilevel indexA first-level index block points to second-level index blocks, which point to data. Two levels with 1,024 pointers each: 1,024² × 4 KiB = 4 GiB
Combined schemeThe Unix inode: a few direct pointers for small files, plus single, double and triple indirect pointers for large ones

The Unix inode: direct and indirect blocks

The classic UFS / ext2 / ext3 inode has 15 block pointers: 12 direct, 1 single indirect, 1 double indirect, 1 triple indirect.

flowchart LR
    I["inode: mode, owner, size, timestamps"] --> D["12 direct pointers"]
    I --> S["single indirect"]
    I --> DD["double indirect"]
    I --> T["triple indirect"]
    D --> DB["12 data blocks"]
    S --> SI["index block: 1024 pointers"] --> SD["1024 data blocks"]
    DD --> D1["index block"] --> D2["1024 index blocks"] --> DDD["1024 x 1024 data blocks"]
    T --> T1["index block"] --> T2["1024 index blocks"] --> T3["1024 x 1024 index blocks"] --> TD["1024 x 1024 x 1024 data blocks"]

Size math with 4 KiB blocks and 4-byte pointers

Pointers per block P = 4096 / 4 = 1,024 = 2^10.

LevelData blocks reachableBytes
12 direct1212 × 4 KiB = 48 KiB
Single indirect2^10 = 1,0242^10 × 2^12 = 2^22 = 4 MiB
Double indirect2^20 = 1,048,5762^32 = 4 GiB
Triple indirect2^302^42 = 4 TiB
Total4 TiB + 4 GiB + 4 MiB + 48 KiB

Same with 1 KiB blocks and 4-byte pointers

P = 1024 / 4 = 256 = 2^8.

LevelBytes
12 direct12 KiB
Single indirect256 × 1 KiB = 256 KiB
Double indirect2^16 × 2^10 = 64 MiB
Triple indirect2^24 × 2^10 = 16 GiB
Total≈ 16.06 GiB

Which pointer serves byte offset X?

With 4 KiB blocks, logical block number b = ⌊X / 4096⌋.

b rangeServed byDisk reads to reach the data (inode cached)
0 – 11direct1
12 – 1,035single indirect2
1,036 – 1,049,611double indirect3
1,049,612 and uptriple indirect4

Example: byte offset 10,000,000 → b = 2,441 → double-indirect region (2,441 − 1,036 = 1,405 into it) → first-level slot ⌊1,405 / 1,024⌋ = 1, second-level slot 1,405 mod 1,024 = 381.

Real limits differ from the pointer math

ext2/ext3 cap files at 2 TiB with 4 KiB blocks because i_blocks counts 512-byte sectors in a 32-bit field — the 4 TiB triple-indirect reach is never usable. ext4 replaced indirect blocks with an extent tree (four extents in the inode, each up to 128 MiB, then a B-tree), which is far more compact for big contiguous files. Interviewers asking about "inode direct and indirect blocks" want the pointer math above; mention extents to show you know it is historical.

Comparing the allocation methods

ContiguousLinkedFATIndexed (inode)Extents
Sequential accessExcellentGoodGoodGoodExcellent
Random accessO(1)O(n) disk readsO(n) table lookups (cached)O(1) – 4 readsO(log n) in tree
External fragmentationYesNoNoNoLittle
GrowthHardEasyEasyEasyEasy
Metadata overheadTinyPointer per blockTable per volumeIndex blocksTiny for contiguous files
Used inISO 9660, early systemsRare todayFAT32, exFATUFS, ext2/3ext4, XFS, NTFS, APFS, btrfs

Free-space management

The file system must track which blocks are free.

Bit vector (bitmap)

One bit per block: 1 = free, 0 = allocated (or the reverse — conventions vary; ext4 uses 1 = in use).

blocks 2,3,4,5,8,9,10,11,12,13,17,18,25,26,27 free
bitmap: 001111001111110001100000011100000...

Finding the first free block is fast with word-at-a-time scanning: skip 64-bit words that are all zero, then use a find-first-set instruction. First free block = (words skipped × 64) + offset of first 1 bit.

Size math: a 1 TiB disk with 4 KiB blocks has 2^40 / 2^12 = 2^28 blocks → 2^28 bits = 2^25 bytes = 32 MiB of bitmap. Fine to cache. ext4 keeps one bitmap block per block group (32,768 blocks per group with 4 KiB blocks, since one 4 KiB bitmap block has 32,768 bits).

Linked list

Link all free blocks together; keep a pointer to the first. No extra space (the pointers live in the free blocks), but traversing is slow and allocating contiguous runs is hard. Allocating one block at a time is O(1). The FAT naturally incorporates this — free clusters are just entries marked 0.

Grouping

The first free block stores the addresses of n other free blocks; the first n − 1 are actually free, the last holds the next group of addresses. Lets the OS find many free blocks with one read.

Counting

Free space often comes in contiguous runs, so store (start, count) pairs: "block 2, 4 free; block 8, 6 free; block 17, 2 free; block 25, 3 free". Much shorter than a list when runs are long. XFS stores free extents in two B+trees (by start block and by size) so it can quickly find either "near here" or "at least this big".

Space maps

ZFS logs allocation and free operations per metaslab into a space map and replays them into an in-memory AVL tree when the metaslab is loaded — counting plus logging, designed for petabyte pools.

TRIM and freed blocks on SSDs

Marking a block free in the bitmap does not tell the SSD the block is garbage. The file system issues TRIM / discard so the FTL can erase it ahead of time. See I/O & Storage.

Directory structures

StructureDescriptionProsCons
Single-levelOne directory for all files of all usersTrivialName collisions; hopeless with many users or files
Two-levelA master file directory with one user file directory per userIsolates users; same name allowed for different usersNo grouping within a user; sharing between users awkward
Tree (hierarchical)Arbitrary-depth tree; absolute and relative path names; current working directoryNatural grouping; efficient searchNo sharing — a file has exactly one parent
Acyclic graphTree plus shared subdirectories/files via linksSharingA file has multiple names (aliasing); deletion needs reference counts; traversal may visit a file twice
General graphLinks may create cyclesMaximum flexibilityTraversal can loop forever; garbage cycles need garbage collection to reclaim
flowchart TB
    R["/"] --> H["home"]
    R --> E["etc"]
    H --> A["alice"]
    H --> B["bob"]
    A --> P["project"]
    B --> S["shared-link"]
    S -.->|"hard link or symlink"| P
    P --> F["notes.txt"]

Unix is an acyclic graph in practice:

  • Hard links add another directory entry pointing at the same inode; the inode's link count tracks how many names exist, and the data is freed when the count reaches zero and no process has the file open. Hard links to directories are forbidden (only . and .. exist), which is precisely how Unix avoids cycles.
  • Symbolic links are small files containing a path; they can point at directories and across file systems, and they can create loops, so path resolution caps the number of symlinks followed (ELOOP after 40 on Linux).

See File Systems for the dcache and how path lookup really works.


Summary

TopicAlgorithmOne-line takeaway
DeadlockRAGCycle = deadlock only if every resource has one instance
DeadlockBanker'sGrant a request only if a safe sequence still exists afterwards; Need = Max − Allocation
DeadlockDetectionLike the safety algorithm but with current Requests; unfinished processes are deadlocked
PagingFIFOSimple, suffers Belady's anomaly
PagingOPTEvict the page used furthest in the future; the unbeatable benchmark
PagingLRUEvict the least recently used page; a stack algorithm, so no anomaly
PagingClockReference-bit approximation of LRU; FIFO when all bits are set
PagingWorking setIf the sum of working sets exceeds memory, suspend a process
DiskSSTFGreedy, starves edges, not optimal
DiskSCAN / LOOKElevator; LOOK turns at the last request
DiskC-SCAN / C-LOOKOne direction only; most uniform wait
FilesIndexed / inode12 direct + single + double + triple; with 4 KiB blocks: 48 KiB, 4 MiB, 4 GiB, 4 TiB
FilesBitmapOne bit per block; 1 TiB at 4 KiB = 32 MiB

Practice Problems

1. Banker's safety. Four processes, resources A B C with totals (6, 4, 7). Allocation: P0 (1,0,1), P1 (2,1,1), P2 (1,1,2), P3 (0,1,1). Max: P0 (3,2,2), P1 (6,1,3), P2 (3,1,4), P3 (4,2,2). Is the state safe? If so, give a safe sequence.

Solution

Allocated = (4, 3, 5) → Available = (2, 1, 2).

Need: P0 (2,2,1), P1 (4,0,2), P2 (2,0,2), P3 (4,1,1).

StepWorkChosenNeedWork after
1(2,1,2)P0? (2,2,1) B 2 > 1 no; P1 no; P2(2,0,2) ✓(3,2,4)
2(3,2,4)P0(2,2,1) ✓(4,2,5)
3(4,2,5)P1(4,0,2) ✓(6,3,6)
4(6,3,6)P3(4,1,1) ✓(6,4,7)

Safe, sequence ⟨P2, P0, P1, P3⟩. Final Work = totals ✓.

2. Banker's request. Using the main worked example at T0 (Available (3,3,2)), P4 requests (3, 3, 0). Granted?

Solution

(3,3,0) ≤ Need[P4] (4,3,1) ✓; (3,3,0) ≤ Available (3,3,2) ✓. Pretend: Available = (0,0,2), Allocation[P4] = (3,3,2), Need[P4] = (1,0,1).

Safety with Work (0,0,2): P0 (7,4,3) ✗, P1 (1,2,2) ✗, P2 (6,0,0) ✗, P3 (0,1,1) ✗, P4 (1,0,1) ✗ (A). No process can run → unsafe → denied, P4 waits.

3. Page faults. Reference string 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6, 3 frames. Count faults for FIFO, LRU and OPT.

Solution
  • FIFO: 16 faults.
  • LRU: 15 faults.
  • OPT: 11 faults.

LRU trace (frame slots after each reference): 1; 1 2; 1 2 3; 4 2 3 (evict 1); hit 2; 4 2 1 (evict 3); 5 2 1 (evict 4); 5 6 1 (evict 2); 5 6 2 (evict 1); 1 6 2 (evict 5); hit 2; 1 3 2 (evict 6); 7 3 2 (evict 1); 7 3 6 (evict 2); hit 3; 2 3 6 (evict 7); 2 3 1 (evict 6); hit 2; hit 3; 2 3 6 (evict 1). That is 15 faults and 5 hits.

OPT's 11 is the lower bound for 3 frames: no algorithm can do better on this string.

4. Belady. Show that LRU on 1 2 3 4 1 2 5 1 2 3 4 5 cannot exhibit Belady's anomaly, then give its fault counts for 3 and 4 frames.

Solution

LRU is a stack algorithm: with n frames it holds the n most recently used pages, which are always a subset of the n + 1 most recently used. So every hit with n frames is a hit with n + 1 frames — faults are non-increasing in n.

Counts: 3 frames → 10 faults, 4 frames → 8 faults. (FIFO: 9 and 10.)

5. Effective access time. Memory access 100 ns; servicing a fault takes 8 ms when the victim is clean and 20 ms when it is dirty; 70% of victims are dirty. What maximum fault rate keeps EAT under 200 ns?

Solution

Average fault time = 0.3 × 8 ms + 0.7 × 20 ms = 2.4 + 14 = 16.4 ms = 16,400,000 ns.

200 ≥ (1 − p) × 100 + p × 16,400,000 → 100 ≥ p × (16,400,000 − 100) → p ≤ 6.1 × 10^-6 — about one fault per 164,000 accesses.

6. Disk scheduling. Cylinders 0–4999, head at 2150 moving toward higher cylinders (previous request was at 1805). Queue: 2069, 1212, 2296, 2800, 544, 1618, 356, 1523, 4965, 3681. Compute total movement for FCFS, SSTF, SCAN, LOOK, C-SCAN and C-LOOK.

Solution
AlgorithmOrderTotal
FCFS2069, 1212, 2296, 2800, 544, 1618, 356, 1523, 4965, 368113,011
SSTF2069, 2296, 2800, 3681, 4965, 1618, 1523, 1212, 544, 3567,586
SCAN2296, 2800, 3681, 4965, (4999), 2069, 1618, 1523, 1212, 544, 3567,492 = 2849 + 4643
LOOK2296 … 4965, 2069 … 3567,424 = 2815 + 4609
C-SCAN2296 … 4965, (4999), (0), 356, 544, 1212, 1523, 1618, 20699,917 incl. return (4,918 excl.)
C-LOOK2296 … 4965, 356 … 20699,137 incl. jump (4,528 excl.)

FCFS detail: 81 + 857 + 1084 + 504 + 2256 + 1074 + 1262 + 1167 + 3442 + 1284 = 13,011.

7. Inode math. Block size 2 KiB, 4-byte pointers, inode with 10 direct, 1 single, 1 double and 1 triple indirect pointer. (a) Maximum file size? (b) How many index blocks does a 5 MiB file need?

Solution

P = 2048 / 4 = 512 pointers.

(a) 10 × 2 KiB + 512 × 2 KiB + 512² × 2 KiB + 512³ × 2 KiB = 20 KiB + 1 MiB + 512 MiB + 256 GiB ≈ 256.5 GiB.

(b) 5 MiB / 2 KiB = 2,560 blocks. Direct covers 10, single covers 512 (one index block), leaving 2,038 for the double-indirect tree: 1 first-level block + ⌈2,038 / 512⌉ = 4 second-level blocks. Index blocks = 1 + 1 + 4 = 6.

8. Bitmap. A 4 TiB volume with 4 KiB blocks. Bitmap size? How many 4 KiB bitmap blocks?

Solution

2^42 / 2^12 = 2^30 blocks → 2^30 bits = 2^27 bytes = 128 MiB. 128 MiB / 4 KiB = 32,768 bitmap blocks (each covering 32,768 data blocks = 128 MiB of disk).

9. Detection. Resources A = 4, B = 3. Allocation: P0 (1,1), P1 (2,0), P2 (1,1). Requests: P0 (1,0), P1 (0,1), P2 (0,0). Deadlock?

Solution

Available = (4,3) − (4,2) = (0,1). P0 needs (1,0) ✗; P1 needs (0,1) ✓ → Work = (2,1); P0 ✓ → (3,2); P2 ✓ → (4,3). No deadlock, order P1, P0, P2. (Strictly, P2 requests nothing so it could finish first; the order is not unique.)

10. Proportional allocation. 120 free frames, three processes of 30, 60 and 150 pages. Frames for each?

Solution

S = 240. P1: 30/240 × 120 = 15; P2: 60/240 × 120 = 30; P3: 150/240 × 120 = 75. Total 120.


Interview Questions

"What is the difference between deadlock prevention and deadlock avoidance?" Prevention makes one of the four Coffman conditions structurally impossible — for example a global lock order eliminates circular wait — so no runtime check is needed. Avoidance allows all four conditions in principle but checks each request at runtime against known maximum claims and refuses any request that would make the state unsafe (Banker's). Prevention costs flexibility; avoidance costs advance knowledge and per-request computation.

"Is an unsafe state a deadlocked state?" No. Deadlocked states are a subset of unsafe states. Unsafe only means the OS can no longer guarantee every process completes if they all ask for their maximums; processes may in fact release resources early and finish fine.

"Does a cycle in a resource-allocation graph mean deadlock?" Only if every resource in the cycle has a single instance. With multiple instances a cycle is necessary but not sufficient — a process outside the cycle may release an instance and break it. Use the detection algorithm to decide.

"What is the time complexity of the Banker's algorithm?" O(m × n²) for the safety check with n processes and m resource types, run on every request. That cost, plus the need for declared maximums, is why general-purpose OSes do not use it.

"Why can't we implement the optimal page-replacement algorithm?" It needs to know the future reference string. It is used offline as a benchmark — you replay a recorded trace to see how close a real policy comes.

"What is Belady's anomaly and which algorithms suffer from it?" More frames causing more faults. FIFO (and FIFO-like algorithms such as Clock and second chance in degenerate cases) can suffer it; stack algorithms — LRU, OPT, LFU with a deterministic tie-break — cannot, because the set of pages held with n frames is always a subset of the set held with n + 1.

"Why don't operating systems use true LRU?" It requires updating a timestamp or a list on every memory reference, which hardware does not do. The MMU only sets a reference bit and a dirty bit; the OS builds approximations — Clock, aging, Linux's active/inactive lists and MGLRU — from those bits.

"What is thrashing and how do you stop it?" The system spends most of its time servicing page faults because the combined working sets exceed physical memory; CPU utilisation collapses. Fix by lowering the degree of multiprogramming (suspend or kill processes), giving the workload more memory, using local replacement or memory limits so one process cannot steal everyone's frames, or controlling allocation with the working-set model or page-fault frequency. In production you see it as high major-fault rates and memory PSI.

"Why does SSTF starve requests and how do SCAN and C-SCAN fix it?" SSTF always picks the nearest request, so a steady stream near the head keeps far requests waiting indefinitely. SCAN bounds the wait to two sweeps by moving monotonically; C-SCAN bounds it to roughly one sweep and evens out wait times by always serving in the same direction.

"Do disk-scheduling algorithms matter for SSDs?" Mostly no. With no seek or rotational latency, reordering by address does nothing useful, and the FTL scrambles physical placement anyway. Linux uses none for NVMe and keeps schedulers like mq-deadline, BFQ and Kyber for latency bounds and fairness rather than seek reduction.

"What is the maximum file size with 4 KiB blocks and a classic Unix inode?" With 4-byte pointers, 1,024 pointers per block: 12 direct (48 KiB) + single indirect (4 MiB) + double (4 GiB) + triple (4 TiB) ≈ 4 TiB. In practice ext2/3 cap at 2 TiB because of the 32-bit sector count, and ext4 uses extents instead.

"Contiguous vs linked vs indexed allocation — trade-offs?" Contiguous: best performance and O(1) random access, but external fragmentation and hard growth. Linked: no fragmentation, easy growth, but O(n) random access and fragile pointers; FAT fixes the random-access cost by caching all pointers in one table. Indexed: O(1) random access with no fragmentation, at the cost of index blocks; the Unix combined scheme keeps small files cheap with direct pointers.

"How does a bitmap free-space manager find a free block quickly?" Scan word by word skipping all-zero (fully allocated) words, then use a find-first-set instruction within the first non-zero word. Group bitmaps per region (ext4 block groups) to keep the scan local and to place a file's blocks near its inode.

"Why can't you create a hard link to a directory?" It would allow cycles in the directory graph, which breaks traversal tools and reference-count-based deletion (a cycle of directories could become unreachable yet never reach a link count of zero). Restricting hard links to files keeps the graph acyclic; symlinks are allowed to point at directories because the kernel caps how many it follows.