File Management OS — Access Methods & UNIX Permissions

Section 01

The Story That Explains Page Replacement

📖 Real World Analogy

The Bakery Display Shelf

A small bakery has one glass display shelf that holds exactly 6 pastries. The kitchen keeps baking new items, and customers keep asking for whichever pastry catches their eye. When a customer wants a chocolate éclair and it's on the shelf, wonderful — she grabs it. But what if the éclair is still in the kitchen and the shelf is already full? Someone has to remove one pastry from the shelf to make room.

Which one to remove? The shopkeeper has several policies:
• FIFO — remove whichever pastry has been on the shelf longest, regardless of demand.
• LRU — remove whichever pastry hasn't been touched or looked at recently.
• Optimal — magically remove the pastry that won't be asked for again for the longest time. Only possible if you can predict the future.

In an operating system, the display shelf is RAM (with a limited number of frames), the pastries are pages, and the customers are the CPU's memory accesses. When a needed page isn't in RAM, we page-fault. When RAM is full, we must replace a page — and the algorithm that decides which one determines everything.

💡

The Core Problem

A page fault on a system with all frames in use requires the OS to choose a victim frame to free. A good choice minimises future faults; a poor choice forces the freshly-evicted page to be re-loaded almost immediately. The algorithm choice can vary total faults by 2–3× on realistic workloads.

Section 02

Basic Page Replacement — The Six Steps

📋 What Happens on a Page Fault When RAM Is Full

Find the desired page's location on disk.

Find a free frame. If no free frame, run the page-replacement algorithm to pick a victim.

Write the victim page back to disk (only if it was modified — the "dirty bit"). Update the victim's page table entry.

Read the desired page into the newly free frame.

Update the requesting process's page table (valid bit + new frame number).

Restart the faulted instruction.

⚠️

The Dirty Bit Optimisation

Every frame carries a dirty bit. If the victim page was only read (never written to since being loaded), its disk copy is still valid — no write-back needed. This halves the cost of a fault on clean pages. Never underestimate it.

Section 03

FIFO — First In, First Out

The simplest algorithm. Keep a FIFO queue of pages in the order they were loaded. When you need to evict, remove the one at the head (oldest arrival). Push the newly loaded page onto the tail.

✅

Pros

simple to implement

Just a queue. No timestamps, no counters. Constant-time eviction. Uses zero extra hardware — pure software.

❌

Cons

ignores usage

A frequently-used page can be evicted just because it happens to be old. The oldest page might be the most important. FIFO doesn't care.

🤯

Belady's Anomaly

more frames → more faults!

Adding more frames sometimes increases the fault count in FIFO. Counterintuitive and dangerous. See Section 05.

🎮 Interactive — FIFO Simulation

Reference string: 1, 3, 0, 3, 5, 6, 3, 1. Three frames available. Click Next to trace each memory access.

FIFO Page Replacement — step through each reference

Reference string (current access highlighted)

Physical Frames (3)

FIFO Queue (oldest → newest)

[ ]

Access #: 0 / 8 Hits: 0 Faults: 0 Fault rate: —

Step 0 of 8

START Empty frames. Empty queue. Click Next to process page 1.

Section 04

Belady's Anomaly — When More Memory Hurts

In 1969, László Bélády discovered that FIFO can produce more faults with a larger frame allocation than with a smaller one — the exact opposite of intuition. Modern algorithms (stack algorithms like LRU) don't suffer from this, but FIFO does.

🎮 Interactive — Belady's Anomaly Demo

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Run FIFO on it with 3 frames and 4 frames side by side. Watch the 4-frame version produce more faults.

Belady's Anomaly — 3 vs 4 frames, same reference string

Reference string

FIFO with 3 Frames

          Faults: 0 / 12
        

FIFO with 4 Frames

          Faults: 0 / 12
        

      Ready — click Next to compare
    

Step 0 of 12

START Both configurations start empty. Same 12-page reference string will be processed in parallel. Click Next.

Section 05

LRU — Least Recently Used

LRU replaces the page that has been unused for the longest time. Intuition: a page you haven't touched in a while is probably not going to be needed soon. LRU is a practical approximation to the optimal algorithm.

✅ Advantages

Uses past behaviour (locality) as predictor of future

Stack algorithm — no Belady's anomaly, guaranteed

Close to optimal on real workloads with good locality

❌ Disadvantages

Expensive to implement precisely — needs a timestamp or stack per access

Requires hardware support: counter or reference bit

Real systems use approximations (Second-Chance, Aging)

Two Implementation Techniques

🕑

Counters

timestamp per page

Every page table entry gets a "time of last use" field. On each memory reference, copy the CPU clock into the referenced page's field. On eviction, scan all pages and evict the one with the smallest timestamp. Overhead: one write per access + O(n) evict search.

📚

Stack

doubly-linked list

Maintain a stack of page numbers ordered from most-recently used (top) to least (bottom). On each reference, move the page to the top. On eviction, remove the bottom. Overhead: constant-time evict but each reference costs 6 pointer updates.

🔧

Real Systems: Approximation

clock / second-chance

True LRU is too expensive per-access. Real hardware provides a single reference bit per frame. OS periodically inspects and clears these bits. Clock algorithm cycles through frames.

Section 06

Optimal (OPT / MIN) — The Best You Could Possibly Do

Belady's optimal algorithm: replace the page that will not be used for the longest time in the future. Provably minimises page faults — no other algorithm can do better on a given reference string.

🚩

Why OPT Is Not Implementable

OPT requires knowing the future reference string. In a live OS this is impossible — you don't know what memory the process will touch next. OPT is used as a benchmark: run your favourite algorithm on the same reference string, then compare to OPT to see how much room for improvement exists.

🎮 Interactive — Three Algorithms Side by Side

Same reference string as the FIFO demo (1, 3, 0, 3, 5, 6, 3, 1) with 3 frames. Watch how each algorithm makes different choices.

FIFO vs LRU vs OPT — same input, different verdicts

Reference string

FIFO

          Faults: 0
        

LRU

          Faults: 0
        

OPT

          Faults: 0
        

      Ready — click Next to process the first reference
    

Step 0 of 8

START Three algorithms will process the same 8-reference string. Watch as they diverge on which frame to evict.

Section 07

Numerical Problem 1 — Compare All Three on the Same Input

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3. Frame count: 3. Run FIFO, LRU, and OPT. Count faults for each.

FIFO Trace

👥 FIFO Step-by-Step (queue shown, oldest → newest)

MISS(1). Frames = {7}. Queue = [7].

MISS(2). Frames = {7,0}. Queue = [7,0].

MISS(3). Frames = {7,0,1}. Queue = [7,0,1].

MISS(4). Evict oldest = 7. Frames = {2,0,1}. Queue = [0,1,2].

HIT.

MISS(5). Evict 0. Frames = {2,3,1}. Queue = [1,2,3].

MISS(6). Evict 1. Frames = {2,3,0}. Queue = [2,3,0].

MISS(7). Evict 2. Frames = {4,3,0}. Queue = [3,0,4].

MISS(8). Evict 3. Frames = {4,2,0}. Queue = [0,4,2].

MISS(9). Evict 0. Frames = {4,2,3}. Queue = [4,2,3].

FIFO

Total: 9 faults out of 10 = 90% fault rate.

LRU Trace

🕑 LRU Step-by-Step (recency order shown)

MISS(1). {7}.

MISS(2). {7,0}. Order: 7,0.

MISS(3). {7,0,1}. Order: 7,0,1.

MISS(4). Evict LRU = 7. {0,1,2}. Order: 0,1,2.

HIT. Order: 1,2,0.

MISS(5). Evict LRU = 1. {0,2,3}. Order: 2,0,3.

HIT. Order: 2,3,0.

MISS(6). Evict LRU = 2. {0,3,4}. Order: 3,0,4.

MISS(7). Evict LRU = 3. {0,2,4}. Order: 0,4,2.

MISS(8). Evict LRU = 0. {2,3,4}. Order: 4,2,3.

LRU

Total: 8 faults out of 10 = 80% fault rate.

OPT Trace

🔭 OPT Step-by-Step (evict page unused farthest in future)

MISS(1). {7}.

MISS(2). {7,0}.

MISS(3). {7,0,1}.

MISS(4). Future: 0,3,0,4,2,3. 7 never, 0 at pos 5, 1 never. Evict 7. {2,0,1}.

HIT.

MISS(5). Future: 0,4,2,3. 2 at pos 9, 0 at pos 7, 1 never. Evict 1. {2,0,3}.

HIT.

MISS(6). Future: 2,3. 2 at pos 9, 0 never, 3 at pos 10. Evict 0. {2,4,3}.

HIT.

OPT

Total: 6 faults out of 10 = 60% fault rate.

🏆

Summary

For this reference string with 3 frames: FIFO = 9 faults, LRU = 8 faults, OPT = 6 faults. FIFO is 50% worse than OPT; LRU is 33% worse. LRU consistently sits between FIFO (naive) and OPT (unreachable) on real workloads.

Section 08

Numerical Problem 2 — Interactive Walkthrough (LRU)

New reference string: 4, 1, 2, 4, 5, 3, 4, 1, 2, 5. Frames: 3. Apply LRU. Click Next to walk through each reference.

Numerical 2 — LRU walkthrough with recency tracking

Reference string

Physical Frames

Recency order (LRU → MRU)

[ ]

Access #: 0 / 10 Hits: 0 Faults: 0 Fault rate: —

Step 0 of 10

START Empty state. Click Next to process reference 4.

Section 09

Thrashing — When Paging Kills Performance

If a process doesn't have enough frames to hold its working set (the pages it's actively touching), every page reference causes a fault. The process spends more time paging than computing. This is thrashing.

CPU Utilization vs Degree of Multiprogramming — the Thrashing Cliff

🚩

Why It Happens

As multiprogramming grows, CPU utilisation initially rises. Beyond the peak, each new process eats frames from the others' working sets. Everyone starts faulting. Faults block processes → CPU idle → OS adds more processes to raise utilisation → even more thrashing. Positive feedback loop.

Section 10

Handling Thrashing — The Working Set Model

Denning's Working Set Model is the classic fix. Define a working-set window Δ (say, 10 000 recent references). A process's working set at time t is the set of unique pages referenced in the interval (t − Δ, t). Its size, WSS_i, is that process's memory demand.

📋 Working Set Strategy

Measure

OS periodically counts each process's working set size WSS_i.

Sum

Total demand D = Σ WSS_i. This is the total number of frames all runnable processes need.

Compare

If D < number of physical frames → fine. If D > frames → thrashing is imminent.

React

Suspend one process. Its frames become available. D drops. Others' working sets fit again.

🔑

Alternate Approach — Page Fault Frequency (PFF)

Establish upper and lower bounds on tolerable fault rate. If a process's rate goes above upper bound, give it more frames. If below lower bound, take frames away. Direct control loop, simpler than measuring working sets.

Section 11

Comparison of Algorithms

Algorithm	Implementation	Overhead	Faults	Belady?
FIFO	Queue of arrival order	Very low	Highest (poor)	Yes
LRU (true)	Timestamps or stack per access	High	Close to OPT	No (stack algorithm)
LRU Approximation	Reference bits, clock algorithm	Medium	Good	No
Optimal (OPT)	Requires future knowledge	N/A	Provably minimum	No

Section 12

Real-World Applications

💾

Linux Kernel

Uses a two-list variation of LRU: an "active" list of recently used pages and an "inactive" list of eviction candidates. Pages move between lists based on access. Approximates LRU with low overhead.

Two-list LRU

🖥️

Windows Working Sets

Windows tracks per-process working sets and trims them under memory pressure. Direct implementation of Denning's model from the 1970s, still running on every PC today.

Working set trimming

📁

Database Buffer Pools

Oracle, PostgreSQL, MySQL all use LRU (or 2Q, ARC variants) to manage their in-memory caches of disk blocks. Same problem, different scale.

LRU · 2Q · ARC

🌐

Web Caches (Nginx, Varnish, CDN)

CDN edge caches use LRU-inspired eviction to decide which web objects to keep and which to drop. Same theory — pages are HTML/images, frames are edge server disk.

LRU · TTL-aware

📱

Mobile OS Low-Memory Killer

Android's LMK deliberately kills background apps rather than let the system thrash. Aggressive prevention beats fighting the cliff. iOS uses a similar approach.

LMK · Jetsam

⚡

CPU L1/L2/L3 Caches

Hardware caches use approximated LRU (or PLRU, Pseudo-LRU) to decide which cache lines to evict. Same problem as OS paging but at nanosecond scale.

Pseudo-LRU

Section 13

Golden Rules — Page Replacement & Thrashing

🔑 Galvin's Non-Negotiable Rules

FIFO is the simplest but poorly performing algorithm. It suffers from Belady's Anomaly — adding more frames can increase fault count. Never use in production.

OPT (replace the page unused farthest in the future) is provably optimal. It cannot be implemented directly because it needs future knowledge, but it is the benchmark to measure other algorithms against.

LRU approximates OPT by assuming the recent past predicts the near future. It's a stack algorithm and thus immune to Belady's Anomaly.

True LRU is expensive: needs a timestamp per access or a stack update per reference. Real systems use approximations — reference bit, clock (second-chance), aging.

The dirty bit halves the cost of a fault when the evicted page is clean (no write-back to disk). Never disable it.

Thrashing occurs when a process (or the system) has fewer frames than its working set. Every access faults. CPU utilisation collapses.

Thrashing is a positive feedback loop: low CPU utilisation → OS admits more processes → less memory per process → more thrashing. The OS must break the loop by suspending processes.

Denning's Working Set Model: measure each process's working set size WSS_i. If total demand exceeds available frames, suspend one process.

Alternative: Page Fault Frequency control. If fault rate exceeds upper threshold, give more frames. If below lower, take frames away.

The goal of a good replacement algorithm is not zero faults — that's impossible. The goal is to keep the fault rate low enough that EAT ≈ memory access time. Typically requires fault rate below 1 in 100 000 accesses.