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:
| # | Condition | Meaning | How to break it |
|---|---|---|---|
| 1 | Mutual exclusion | At least one resource is non-shareable | Make the resource shareable (read-only files, lock-free structures) — often impossible |
| 2 | Hold and wait | A process holds one resource while waiting for another | Request everything up front, or release everything before requesting more |
| 3 | No preemption | Resources cannot be forcibly taken away | Allow preemption (take the resource, roll the holder back) — works for CPU and memory, not for a half-written printer job |
| 4 | Circular wait | A cycle P1 → P2 → … → Pn → P1 of waits | Impose 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
| Strategy | Idea | Cost | Who uses it |
|---|---|---|---|
| Prevention | Structurally deny one Coffman condition so deadlock is impossible | Lower utilisation, programmer discipline | Lock ordering in kernels (Linux lockdep enforces it), "acquire all locks up front" in 2PL variants |
| Avoidance | Know each process's maximum claim; grant a request only if the resulting state is safe | Needs advance knowledge of max needs; O(m·n²) per request | Textbooks, some real-time and embedded systems, batch schedulers that reserve resources |
| Detection and recovery | Let deadlocks happen, periodically detect, then break them | Periodic detection cost + lost work on recovery | Databases (PostgreSQL, MySQL InnoDB, SQL Server), JVM tooling |
| Ignorance (ostrich algorithm) | Assume deadlocks are rare; reboot or kill if they happen | Occasional hang | General-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:
| Structure | Shape | Meaning |
|---|---|---|
Available | vector of m | Free instances of each resource type right now |
Max | n × m | Maximum demand each process may ever make (declared in advance) |
Allocation | n × m | Instances currently allocated to each process |
Need | n × m | Remaining 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:
| Process | Allocation (A B C) | Max (A B C) | Need = Max − Alloc (A B C) |
|---|---|---|---|
| P0 | 0 1 0 | 7 5 3 | 7 4 3 |
| P1 | 2 0 0 | 3 2 2 | 1 2 2 |
| P2 | 3 0 2 | 9 0 2 | 6 0 0 |
| P3 | 2 1 1 | 2 2 2 | 0 1 1 |
| P4 | 0 0 2 | 4 3 3 | 4 3 1 |
| Total allocated | 7 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.
| Step | Work before | Candidate checks | Chosen | Need ≤ Work? | Work after (Work + Alloc) |
|---|---|---|---|---|---|
| 1 | (3,3,2) | P0 needs (7,4,3): no | P1 | (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 no | P3 | (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 P0 | P0 | (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
- Request (1,0,2) ≤ Need[P1] (1,2,2)? ✓
- Request (1,0,2) ≤ Available (3,3,2)? ✓
- Pretend to allocate:
| Before | After | |
|---|---|---|
| Available | (3,3,2) | (2,3,0) |
| Allocation[P1] | (2,0,0) | (3,0,2) |
| Need[P1] | (1,2,2) | (0,2,0) |
- Safety check on the new state:
| Step | Work before | Chosen | Need | Work 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)
- (3,3,0) ≤ Need[P4] (4,3,1)? ✓
- (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)
- (0,2,0) ≤ Need[P0] (7,4,3)? ✓
- (0,2,0) ≤ Available (2,3,0)? ✓ — the resources are physically free.
- Pretend: Available = (2,1,0); Allocation[P0] = (0,3,0); Need[P0] = (7,2,3).
- Safety check with Work = (2,1,0):
| Process | Need | Need ≤ (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:
| Process | Allocation (A B C) | Request (A B C) |
|---|---|---|
| P0 | 0 1 0 | 0 0 0 |
| P1 | 2 0 0 | 2 0 2 |
| P2 | 3 0 3 | 0 0 0 |
| P3 | 2 1 1 | 1 0 0 |
| P4 | 0 0 2 | 0 0 2 |
Allocated total = (7, 2, 6) → Available = (0, 0, 0).
| Step | Work before | Chosen | Request ≤ 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).
| Step | Work | Check |
|---|---|---|
| 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
| Policy | Trade-off |
|---|---|
| On every request that cannot be granted immediately | Finds the deadlock at once and identifies the process that "caused" it, but expensive |
| Every N minutes | Cheap; 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 wait | What 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
- Select a victim — minimise cost (resources held, time consumed).
- Rollback — return the victim to a safe earlier state (checkpoint) or abort it entirely (total rollback).
- 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):
| p | EAT | Slowdown |
|---|---|---|
| 0 | 200 ns | 1x |
| 1 / 1,000,000 | 200 + 8 = 208 ns | 1.04x |
| 1 / 100,000 | ≈ 280 ns | 1.4x |
| 1 / 1,000 | ≈ 8.2 µs | 41x |
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:
| # | Ref | Frame 1 | Frame 2 | Frame 3 | Result | Evicted |
|---|---|---|---|---|---|---|
| 1 | 7 | 7 | F | |||
| 2 | 0 | 7 | 0 | F | ||
| 3 | 1 | 7 | 0 | 1 | F | |
| 4 | 2 | 2 | 0 | 1 | F | 7 |
| 5 | 0 | 2 | 0 | 1 | H | |
| 6 | 3 | 2 | 3 | 1 | F | 0 |
| 7 | 0 | 2 | 3 | 0 | F | 1 |
| 8 | 4 | 4 | 3 | 0 | F | 2 |
| 9 | 2 | 4 | 2 | 0 | F | 3 |
| 10 | 3 | 4 | 2 | 3 | F | 0 |
| 11 | 0 | 0 | 2 | 3 | F | 4 |
| 12 | 3 | 0 | 2 | 3 | H | |
| 13 | 2 | 0 | 2 | 3 | H | |
| 14 | 1 | 0 | 1 | 3 | F | 2 |
| 15 | 2 | 0 | 1 | 2 | F | 3 |
| 16 | 0 | 0 | 1 | 2 | H | |
| 17 | 1 | 0 | 1 | 2 | H | |
| 18 | 7 | 7 | 1 | 2 | F | 0 |
| 19 | 0 | 7 | 0 | 2 | F | 1 |
| 20 | 1 | 7 | 0 | 1 | F | 2 |
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:
| # | Ref | F1 | F2 | F3 | Result | Evicted (next use) |
|---|---|---|---|---|---|---|
| 1 | 7 | 7 | F | |||
| 2 | 0 | 7 | 0 | F | ||
| 3 | 1 | 7 | 0 | 1 | F | |
| 4 | 2 | 2 | 0 | 1 | F | 7 (next at #18; 0 at #5, 1 at #14) |
| 5 | 0 | 2 | 0 | 1 | H | |
| 6 | 3 | 2 | 0 | 3 | F | 1 (next at #14; 2 at #9, 0 at #7) |
| 7 | 0 | 2 | 0 | 3 | H | |
| 8 | 4 | 2 | 4 | 3 | F | 0 (next at #11; 2 at #9, 3 at #10) |
| 9 | 2 | 2 | 4 | 3 | H | |
| 10 | 3 | 2 | 4 | 3 | H | |
| 11 | 0 | 2 | 0 | 3 | F | 4 (never used again) |
| 12 | 3 | 2 | 0 | 3 | H | |
| 13 | 2 | 2 | 0 | 3 | H | |
| 14 | 1 | 2 | 0 | 1 | F | 3 (never used again) |
| 15 | 2 | 2 | 0 | 1 | H | |
| 16 | 0 | 2 | 0 | 1 | H | |
| 17 | 1 | 2 | 0 | 1 | H | |
| 18 | 7 | 7 | 0 | 1 | F | 2 (never used again) |
| 19 | 0 | 7 | 0 | 1 | H | |
| 20 | 1 | 7 | 0 | 1 | H |
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:
| # | Ref | F1 | F2 | F3 | Result | Evicted (last use) |
|---|---|---|---|---|---|---|
| 1 | 7 | 7 | F | |||
| 2 | 0 | 7 | 0 | F | ||
| 3 | 1 | 7 | 0 | 1 | F | |
| 4 | 2 | 2 | 0 | 1 | F | 7 (#1) |
| 5 | 0 | 2 | 0 | 1 | H | |
| 6 | 3 | 2 | 0 | 3 | F | 1 (#3) |
| 7 | 0 | 2 | 0 | 3 | H | |
| 8 | 4 | 4 | 0 | 3 | F | 2 (#4) |
| 9 | 2 | 4 | 0 | 2 | F | 3 (#6) |
| 10 | 3 | 4 | 3 | 2 | F | 0 (#7) |
| 11 | 0 | 0 | 3 | 2 | F | 4 (#8) |
| 12 | 3 | 0 | 3 | 2 | H | |
| 13 | 2 | 0 | 3 | 2 | H | |
| 14 | 1 | 1 | 3 | 2 | F | 0 (#11) |
| 15 | 2 | 1 | 3 | 2 | H | |
| 16 | 0 | 1 | 0 | 2 | F | 3 (#12) |
| 17 | 1 | 1 | 0 | 2 | H | |
| 18 | 7 | 1 | 0 | 7 | F | 2 (#15) |
| 19 | 0 | 1 | 0 | 7 | H | |
| 20 | 1 | 1 | 0 | 7 | H |
LRU, 3 frames: 12 faults.
Implementing true LRU
| Implementation | On every reference | On replacement | Problem |
|---|---|---|---|
| Counters / timestamps | Copy a logical clock into the page-table entry | Scan 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 updates | Victim is at the bottom — O(1) | Pointer updates on every memory access |
| Hash map + doubly linked list | O(1) move-to-front | O(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 0s | Row with the smallest binary value | Hardware 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) beats01110111. - 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):
| # | Ref | Frames | Ref bits | Hand after | Result | What happened |
|---|---|---|---|---|---|---|
| 1 | 7 | 7 - - | 1 0 0 | 1 | F | fill |
| 2 | 0 | 7 0 - | 1 1 0 | 2 | F | fill |
| 3 | 1 | 7 0 1 | 1 1 1 | 0 | F | fill |
| 4 | 2 | 2 0 1 | 1 0 0 | 1 | F | full sweep clears all bits, evict 7 |
| 5 | 0 | 2 0 1 | 1 1 0 | 1 | H | set bit on 0 |
| 6 | 3 | 2 0 3 | 1 0 1 | 0 | F | 0 had bit 1 → cleared; 1 has bit 0 → evict 1 |
| 7 | 0 | 2 0 3 | 1 1 1 | 0 | H | |
| 8 | 4 | 4 0 3 | 1 0 0 | 1 | F | sweep clears 2,0,3; evict 2 |
| 9 | 2 | 4 2 3 | 1 1 0 | 2 | F | evict 0 (bit 0) |
| 10 | 3 | 4 2 3 | 1 1 1 | 2 | H | |
| 11 | 0 | 4 2 0 | 0 0 1 | 0 | F | sweep clears 3,4,2; evict 3 |
| 12 | 3 | 3 2 0 | 1 0 1 | 1 | F | evict 4 (bit 0) |
| 13 | 2 | 3 2 0 | 1 1 1 | 1 | H | |
| 14 | 1 | 3 1 0 | 0 1 0 | 2 | F | sweep clears 2,0,3; evict 2 |
| 15 | 2 | 3 1 2 | 0 1 1 | 0 | F | evict 0 |
| 16 | 0 | 0 1 2 | 1 1 1 | 1 | F | evict 3 |
| 17 | 1 | 0 1 2 | 1 1 1 | 1 | H | |
| 18 | 7 | 0 7 2 | 0 1 0 | 2 | F | sweep clears 1,2,0; evict 1 |
| 19 | 0 | 0 7 2 | 1 1 0 | 2 | H | |
| 20 | 1 | 0 7 1 | 1 1 1 | 0 | F | evict 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) | Meaning | Eviction preference |
|---|---|---|---|
| 0 | (0, 0) | Neither recently used nor modified | Best victim — free to drop |
| 1 | (0, 1) | Not recently used but dirty | Must write back first |
| 2 | (1, 0) | Recently used, clean | Probably needed soon |
| 3 | (1, 1) | Recently used and dirty | Worst 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
| Algorithm | Fault pattern (F = fault, H = hit) for the 20 references | Faults |
|---|---|---|
| FIFO | F F F F H F H F H H F H H F F H H F H H | 10 |
| OPT | F F F F H F H F H H H H H F H H H F H H | 8 |
| LRU | F F F F H F H F H H H H H F H H H F H H | 8 |
| Clock | F F F F H F H F H H H H H F F H H F H H | 9 |
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:
| Frames | FIFO | Clock | LRU | OPT |
|---|---|---|---|---|
| 3 | 15 | 14 | 12 | 9 |
| 4 | 10 | 9 | 8 | 8 |
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:
| Ref | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F1 | 1 | 1 | 1 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 5 |
| F2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | |
| F3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | ||
| F | F | F | F | F | F | F | H | H | F | F | H |
9 faults.
FIFO, 4 frames:
| Ref | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F1 | 1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 4 | 4 |
| F2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 5 | |
| F3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | ||
| F4 | 4 | 4 | 4 | 4 | 4 | 4 | 3 | 3 | 3 | |||
| F | F | F | F | H | H | F | F | F | F | F | F |
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).
kswapdand 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
| Time | Last 10 references | Working set | WSS |
|---|---|---|---|
| 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.
| Process | Size | Share | Frames |
|---|---|---|---|
| P1 | 10 | 10 / 137 × 62 = 4.53 | 4 |
| P2 | 127 | 127 / 137 × 62 = 57.47 | 57 |
(Round down, one frame left for the free pool.) A priority-weighted variant uses priority instead of, or as well as, size.
| Global replacement | Local replacement | |
|---|---|---|
| Victim chosen from | All frames in the system | Only the faulting process's frames |
| Allocation per process | Varies over time | Fixed (unless an allocator rebalances) |
| Throughput | Usually higher | Lower — idle frames in one process cannot help another |
| Predictability | A process's fault rate depends on others | Depends only on its own behaviour |
| Used by | Linux (with cgroup limits adding local-ish behaviour), most general-purpose OSes | Windows 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.
| Move | From → To | Distance |
|---|---|---|
| 1 | 53 → 98 | 45 |
| 2 | 98 → 183 | 85 |
| 3 | 183 → 37 | 146 |
| 4 | 37 → 122 | 85 |
| 5 | 122 → 14 | 108 |
| 6 | 14 → 124 | 110 |
| 7 | 124 → 65 | 59 |
| 8 | 65 → 67 | 2 |
| Total | 640 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.
| Move | Head at | Candidates (distance) | Chosen | Distance |
|---|---|---|---|---|
| 1 | 53 | 65 (12), 37 (16), 67 (14) … | 65 | 12 |
| 2 | 65 | 67 (2) | 67 | 2 |
| 3 | 67 | 37 (30), 98 (31) | 37 | 30 |
| 4 | 37 | 14 (23), 98 (61) | 14 | 23 |
| 5 | 14 | 98 (84) | 98 | 84 |
| 6 | 98 | 122 (24) | 122 | 24 |
| 7 | 122 | 124 (2) | 124 | 2 |
| 8 | 124 | 183 (59) | 183 | 59 |
| Total | 236 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 → To | Distance | Note |
|---|---|---|
| 53 → 37 | 16 | |
| 37 → 14 | 23 | |
| 14 → 0 | 14 | travel to the edge |
| 0 → 65 | 65 | reverse |
| 65 → 67 → 98 → 122 → 124 → 183 | 118 | |
| Total | 236 | = 53 + 183 |
SCAN, moving toward 199:
| From → To | Distance |
|---|---|
| 53 → 65 → 67 → 98 → 122 → 124 → 183 | 130 |
| 183 → 199 (edge) | 16 |
| 199 → 37 | 162 |
| 37 → 14 | 23 |
| Total | 331 = (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 → To | Distance | Note |
|---|---|---|
| 53 → … → 183 | 130 | serve 65, 67, 98, 122, 124, 183 |
| 183 → 199 | 16 | to edge |
| 199 → 0 | 199 | return sweep, no service |
| 0 → 14 → 37 | 37 | |
| Total | 382 (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
| Algorithm | Direction | Service order | Total movement |
|---|---|---|---|
| FCFS | — | 98, 183, 37, 122, 14, 124, 65, 67 | 640 |
| SSTF | — | 65, 67, 37, 14, 98, 122, 124, 183 | 236 |
| SCAN | toward 0 | 37, 14, (0), 65, 67, 98, 122, 124, 183 | 236 |
| SCAN | toward 199 | 65, 67, 98, 122, 124, 183, (199), 37, 14 | 331 |
| LOOK | toward 0 | 37, 14, 65, 67, 98, 122, 124, 183 | 208 |
| LOOK | toward 199 | 65, 67, 98, 122, 124, 183, 37, 14 | 299 |
| C-SCAN | toward 199 | 65 … 183, (199), (0), 14, 37 | 382 (183) |
| C-SCAN | toward 0 | 37, 14, (0), (199), 183 … 65 | 386 (187) |
| C-LOOK | toward 199 | 65 … 183, 14, 37 | 322 (153) |
| C-LOOK | toward 0 | 37, 14, 183 … 65 | 326 (157) |
Figures in brackets exclude the non-servicing return sweep.
Starvation and fairness
| Algorithm | Starvation | Wait-time variance | Notes |
|---|---|---|---|
| FCFS | None | Low, but everyone waits long | Baseline |
| SSTF | Yes — edge requests can wait forever | High | Greedy, not optimal |
| SCAN / LOOK | No — bounded by two sweeps | Middle cylinders favoured | Good under heavy load |
| C-SCAN / C-LOOK | No — bounded by one sweep plus the return | Most uniform | Preferred when fairness matters |
| N-step SCAN / FSCAN | No | Bounded | Freeze 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
nonefor NVMe,mq-deadlinefor 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).
| File | Start | Length | Blocks |
|---|---|---|---|
| count | 0 | 2 | 0, 1 |
| tr | 14 | 3 | 14, 15, 16 |
| 19 | 6 | 19 – 24 | |
| list | 28 | 4 | 28 – 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.
FAT: linked allocation with the links in a table
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.
| Cluster | FAT entry |
|---|---|
| 217 | 618 |
| 339 | EOF |
| 618 | 339 |
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:
| Scheme | How it works |
|---|---|
| Linked index blocks | The last pointer of an index block points to the next index block |
| Multilevel index | A 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 scheme | The 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.
| Level | Data blocks reachable | Bytes |
|---|---|---|
| 12 direct | 12 | 12 × 4 KiB = 48 KiB |
| Single indirect | 2^10 = 1,024 | 2^10 × 2^12 = 2^22 = 4 MiB |
| Double indirect | 2^20 = 1,048,576 | 2^32 = 4 GiB |
| Triple indirect | 2^30 | 2^42 = 4 TiB |
| Total | 4 TiB + 4 GiB + 4 MiB + 48 KiB |
Same with 1 KiB blocks and 4-byte pointers
P = 1024 / 4 = 256 = 2^8.
| Level | Bytes |
|---|---|
| 12 direct | 12 KiB |
| Single indirect | 256 × 1 KiB = 256 KiB |
| Double indirect | 2^16 × 2^10 = 64 MiB |
| Triple indirect | 2^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 range | Served by | Disk reads to reach the data (inode cached) |
|---|---|---|
| 0 – 11 | direct | 1 |
| 12 – 1,035 | single indirect | 2 |
| 1,036 – 1,049,611 | double indirect | 3 |
| 1,049,612 and up | triple indirect | 4 |
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
| Contiguous | Linked | FAT | Indexed (inode) | Extents | |
|---|---|---|---|---|---|
| Sequential access | Excellent | Good | Good | Good | Excellent |
| Random access | O(1) | O(n) disk reads | O(n) table lookups (cached) | O(1) – 4 reads | O(log n) in tree |
| External fragmentation | Yes | No | No | No | Little |
| Growth | Hard | Easy | Easy | Easy | Easy |
| Metadata overhead | Tiny | Pointer per block | Table per volume | Index blocks | Tiny for contiguous files |
| Used in | ISO 9660, early systems | Rare today | FAT32, exFAT | UFS, ext2/3 | ext4, 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
| Structure | Description | Pros | Cons |
|---|---|---|---|
| Single-level | One directory for all files of all users | Trivial | Name collisions; hopeless with many users or files |
| Two-level | A master file directory with one user file directory per user | Isolates users; same name allowed for different users | No grouping within a user; sharing between users awkward |
| Tree (hierarchical) | Arbitrary-depth tree; absolute and relative path names; current working directory | Natural grouping; efficient search | No sharing — a file has exactly one parent |
| Acyclic graph | Tree plus shared subdirectories/files via links | Sharing | A file has multiple names (aliasing); deletion needs reference counts; traversal may visit a file twice |
| General graph | Links may create cycles | Maximum flexibility | Traversal 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 (
ELOOPafter 40 on Linux).
See File Systems for the dcache and how path lookup really works.
Summary
| Topic | Algorithm | One-line takeaway |
|---|---|---|
| Deadlock | RAG | Cycle = deadlock only if every resource has one instance |
| Deadlock | Banker's | Grant a request only if a safe sequence still exists afterwards; Need = Max − Allocation |
| Deadlock | Detection | Like the safety algorithm but with current Requests; unfinished processes are deadlocked |
| Paging | FIFO | Simple, suffers Belady's anomaly |
| Paging | OPT | Evict the page used furthest in the future; the unbeatable benchmark |
| Paging | LRU | Evict the least recently used page; a stack algorithm, so no anomaly |
| Paging | Clock | Reference-bit approximation of LRU; FIFO when all bits are set |
| Paging | Working set | If the sum of working sets exceeds memory, suspend a process |
| Disk | SSTF | Greedy, starves edges, not optimal |
| Disk | SCAN / LOOK | Elevator; LOOK turns at the last request |
| Disk | C-SCAN / C-LOOK | One direction only; most uniform wait |
| Files | Indexed / inode | 12 direct + single + double + triple; with 4 KiB blocks: 48 KiB, 4 MiB, 4 GiB, 4 TiB |
| Files | Bitmap | One 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).
| Step | Work | Chosen | Need | Work 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
| Algorithm | Order | Total |
|---|---|---|
| FCFS | 2069, 1212, 2296, 2800, 544, 1618, 356, 1523, 4965, 3681 | 13,011 |
| SSTF | 2069, 2296, 2800, 3681, 4965, 1618, 1523, 1212, 544, 356 | 7,586 |
| SCAN | 2296, 2800, 3681, 4965, (4999), 2069, 1618, 1523, 1212, 544, 356 | 7,492 = 2849 + 4643 |
| LOOK | 2296 … 4965, 2069 … 356 | 7,424 = 2815 + 4609 |
| C-SCAN | 2296 … 4965, (4999), (0), 356, 544, 1212, 1523, 1618, 2069 | 9,917 incl. return (4,918 excl.) |
| C-LOOK | 2296 … 4965, 356 … 2069 | 9,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.
Related Pages
- Virtual Memory — page tables, faults, reclaim, swap, OOM killer
- I/O & Storage — block layer, Linux I/O schedulers, NVMe, SSD internals
- File Systems — inodes, journaling, VFS, extents, links
- CPU Scheduling & Context Switching — FCFS, SJF, RR numericals, CFS and EEVDF
- Deadlocks, Livelocks & Starvation — deadlock in application code
- Page Cache & fsync — dirty pages and writeback
- Memory Allocators — first-fit, best-fit and fragmentation
- Concurrency Control — how databases detect and resolve deadlocks
- Linux Memory Management — the operator's view