Page Replacement Need

Consider a simple question: when evicting a page from memory, how does the operating system know whether it needs to write the page to disk?

Without this knowledge, the OS would have two choices—both terrible:

1. Always write every evicted page — Wasteful. Most evicted pages haven't changed. Writing unmodified pages doubles I/O without benefit.

2. Never write any page — Catastrophic. Modified data would be lost. This isn't even viable.

The solution is elegant: a single bit of hardware support called the dirty bit (also called the modified bit). This humble bit, maintained automatically by the processor for every page, answers the critical question: "Has this page been written to since it was loaded?"

This page explores the dirty bit in comprehensive detail—its mechanism, implementation, role in page replacement, and the optimization opportunities it enables.

The dirty bit (also called the modify bit or M bit) is a single bit in each page table entry (PTE) that indicates whether the corresponding page has been modified (written to) since it was loaded into memory.

Formal Definition:

Dirty Bit = 1 : Page has been written to since last load/clear
Dirty Bit = 0 : Page has NOT been written to (clean)

Location in Page Table Entry:

Typical 64-bit Page Table Entry Layout (x86-64):
┌────┬───┬───┬───┬───┬───┬───┬───┬──────────────────────────────┬───────────┐
│ NX │ 0 │ 0 │ A │ D │PCD│PWT│U/S│ Physical Frame Number        │   Flags   │
│  1 │   │   │ 1 │ 1 │ 1 │ 1 │ 1 │        40 bits               │  3 bits   │
└────┴───┴───┴───┴───┴───┴───┴───┴──────────────────────────────┴───────────┘
                     ↑
                     └── Dirty Bit (D)

Where:
  D = Dirty bit (set by hardware on write)
  A = Accessed bit (set by hardware on any access)

The Invariant:

If Dirty = 0: Page contents in memory == Page contents on disk/backing store
If Dirty = 1: Page contents in memory != Page contents on disk/backing store
              (memory has newer data)

This invariant is critical: a clean page can be discarded without loss; a dirty page must be written first.

Page States Based on Dirty Bit:

Types of Backing Store:

Depending on the page type, a dirty page is written to different locations:

Understanding exactly when and how the dirty bit is set and cleared is essential for appreciating its role in memory management.

When the Dirty Bit Is Set:

The dirty bit is set automatically by the MMU during the address translation process for a write operation:

Write Operation Sequence:

1. CPU executes store instruction (e.g., MOV [addr], value)
2. MMU receives virtual address and write intent
3. MMU walks page table to find PTE
4. MMU checks PTE permissions:
   - If not writable → Protection fault
   - If not present → Page fault
   - If writable and present → Proceed
5. MMU atomically:
   a. Sets Dirty bit = 1 in PTE
   b. Sets Accessed bit = 1 in PTE
   c. Performs translation
6. Write completes to physical memory

Atomic Update Requirement:

The dirty bit update must be atomic with respect to the write:

❌ Incorrect (non-atomic):
   1. Translate address
   2. Perform write
   3. Set dirty bit
   
   Problem: If interrupted after step 2, dirty bit never set.
   Page appears clean but has modified data.
   Eviction would lose the write!

✓ Correct (atomic):
   Single hardware operation sets bit AND performs write.
   Cannot be interrupted between.

When the Dirty Bit Is Cleared:

Unlike setting (which is automatic), clearing the dirty bit requires explicit OS action:

Clearing Sequence:

1. OS selects a dirty page for cleaning
2. OS ensures page is not being written (lock or COW)
3. OS initiates write to backing store
4. OS waits for I/O completion
5. OS atomically clears Dirty bit = 0
6. Page is now "clean" and can be evicted without write

Critical: Must ensure no concurrent write during steps 3-5!

Handling Concurrent Writes:

If a process writes to a page while it's being cleaned:

Scenario:
  T1: OS starts writing page to disk (dirty=1)
  T2: Process writes to page
  T3: OS finishes disk write
  T4: OS clears dirty bit (WRONG!)

Problem: Write at T2 is not on disk, but dirty=0 claims it is.
Eviction would lose T2's write.

Solutions:
  1. Write-protect page during cleaning
     - Any write triggers fault
     - Fault handler re-marks dirty
     
  2. Check dirty bit after write completes
     - If set, page was modified during write
     - Either restart write or leave dirty
     
  3. Copy-on-write during cleaning
     - Create copy for cleaning
     - Original can accept writes

The dirty bit fundamentally affects page replacement strategy. Its impact is so significant that most algorithms explicitly factor it into victim selection.

The Cost Differential:

Clean Page Eviction:
  1. Invalidate PTE (valid = 0)
  2. Add frame to free list
  Total time: ~1 microsecond

Dirty Page Eviction:
  1. Initiate disk write
  2. Wait for write completion
  3. Invalidate PTE
  4. Add frame to free list
  Total time: ~10 milliseconds (HDD) or ~100 microseconds (SSD)

The 10,000x Penalty:

On traditional hard drives:

• Clean eviction: ~1 μs
• Dirty eviction: ~10 ms
• Ratio: 10,000x slower

Even on SSDs:

• Clean eviction: ~1 μs
• Dirty eviction: ~100 μs
• Ratio: 100x slower

This massive asymmetry means that preferring clean pages has enormous impact.

Incorporating Dirty Status in Victim Selection:

Algorithms handle dirty pages in several ways:

Approach 1: Prefer Clean, Accept Dirty (Common)

Victim Selection:
  1. Scan for clean, unreferenced pages
  2. If found, select as victim
  3. If none found, scan for dirty, unreferenced pages
  4. Select dirty page as victim (takes longer but necessary)

Approach 2: Enhanced Clock (NRU Classes)

Classify pages into four categories:

Class 0: Referenced=0, Dirty=0  →  Best victim
         Not recently used, clean
         Eviction cost: minimal

Class 1: Referenced=0, Dirty=1  →  Good victim
         Not recently used, but dirty
         Eviction cost: 1 write

Class 2: Referenced=1, Dirty=0  →  Poor victim
         Recently used, but clean
         May fault back soon

Class 3: Referenced=1, Dirty=1  →  Worst victim
         Recently used AND dirty
         High cost and likely to re-fault

Scan order: Class 0 → Class 1 → Class 2 → Class 3

Approach 3: Write-Back First, Then Evict

Some systems write dirty pages asynchronously, then treat them as clean:

1. Background daemon identifies dirty pages
2. Writes them to backing store
3. Clears dirty bit
4. Page now "clean" from eviction perspective
5. When eviction needed, more clean pages available

Operating systems employ sophisticated strategies to keep a pool of clean pages available, minimizing eviction latency during memory pressure.

Strategy 1: Synchronous Write-Back

The simplest approach—wait inline during eviction:

When victim is dirty:
  1. Start write to disk
  2. Block until write completes
  3. Clear dirty bit
  4. Frame now available

Pros: Simple, predictable
Cons: Maximum latency on page fault critical path

Strategy 2: Asynchronous Pre-Cleaning (Background Flush)

Proactively clean pages before they're needed:

Linux flush workers (formerly pdflush/bdflush):

┌────────────────────────────────────────────────────────┐
│                    Memory Pressure                      │
│   HIGH ────────── MEDIUM ────────── LOW                │
│     ↓               ↓                ↓                 │
│  Aggressive      Moderate          Lazy               │
│   cleaning       cleaning        cleaning             │
└────────────────────────────────────────────────────────┘

Behavior:
  - Low pressure: Clean pages older than dirty_expire_centisecs
  - Medium pressure: More aggressive cleaning
  - High pressure: Synchronous cleaning in allocation path

Strategy 3: Clustered Writes

Group nearby dirty pages for efficient I/O:

Scattered Dirty Pages (Inefficient):
  Page at disk block 1000 → seek + write
  Page at disk block 5000 → seek + write
  Page at disk block 1500 → seek + write
  Page at disk block 8000 → seek + write
  Total: 4 seeks (expensive)

Clustered Writes (Efficient):
  Sort pages by disk location
  Page at disk block 1000 → seek + write
  Page at disk block 1500 → small seek + write  
  Page at disk block 5000 → seek + write
  Page at disk block 8000 → seek + write
  Total: Fewer seeks, better throughput

Many systems coalesce: adjacent pages → single larger I/O

Strategy 4: Write-Ahead for Eviction Candidates

Preemptively clean pages likely to be evicted:

Observation: Pages at the tail of LRU are eviction candidates

Strategy:
  1. Monitor inactive list (eviction candidates)
  2. For dirty pages on inactive list:
     a. Initiate background write
     b. Move to "laundering" state
  3. When write completes:
     a. Clear dirty bit
     b. Page now clean for future eviction

Result: When eviction occurs, many candidates are already clean.

How and when dirty pages are written back involves fundamental tradeoffs between performance, reliability, and resource usage.

Policy 1: Write-Back (Lazy Write)

Defer writes until necessary:

Characteristics:
  - Page modified in memory only
  - Dirty bit set, but no I/O
  - Written only when:
    a. Page is being evicted, OR
    b. File is synced (fsync), OR
    c. Dirty time limit exceeded, OR
    d. System is shutting down

Advantages:
  + Fewer total writes (coalescing)
  + Better performance for repeated modifications
  + Reduced disk wear (especially SSDs)

Disadvantages:
  - Data loss window during crashes
  - More dirty pages in memory
  - Higher eviction latency possible

Policy 2: Write-Through (Immediate Write)

Write immediately on every modification:

Characteristics:
  - Every store operation writes to disk
  - Or at least queues for immediate write
  - Dirty bit cleared promptly

Advantages:
  + Minimal data loss window
  + Pages almost always clean
  + Instant eviction capability

Disadvantages:
  - Very high I/O volume
  - Poor performance for write-heavy workloads
  - Excessive disk wear

Usage: Rare in general-purpose OS; used for specific
       reliability-critical file systems/databases.

Policy 3: Hybrid Approaches

Real systems use combinations:

Linux Default Behavior:
  1. Writes to page cache (memory-speed)
  2. Page marked dirty
  3. After 30 seconds, background write
  4. On memory pressure, accelerated write
  5. fsync() forces immediate write

Database Systems (e.g., PostgreSQL):
  1. Write to page cache (fast)
  2. WAL record to disk (synchronous)
  3. Dirty data pages written by checkpoint
  4. Crash recovery replays WAL
  
  Combines: fast writes + durability

Ordered Write-Back:

For file system consistency, writes must be ordered:

Scenario: Create new file
  1. Allocate inode
  2. Initialize inode data
  3. Add directory entry pointing to inode

Correct order: 1 → 2 → 3
  If crash after 2: orphan inode (recoverable)
  
Wrong order: 3 → 1 → 2  
  If crash after 3: directory points to garbage
  
File systems (ext4, XFS) enforce ordering constraints
on which dirty pages can be written before others.

The dirty bit mechanism has profound implications for system reliability and crash recovery. Understanding these is essential for building robust systems.

The Data Loss Window:

Time: ─────────────────────────────────────────────────────────►
      │                    │                    │
    write()           page cleaned            crash
    (dirty=1)          (dirty=0)              (data lost?)
      │                    │                    │
      │←── Data at risk ──►│←── Data safe ────►│

Data written to dirty pages but not yet on disk is lost on crash.

Linux defaults:
  - dirty_expire_centisecs = 3000 (30 seconds)
  - Maximum data loss window without fsync: ~30 seconds

What Survives a Crash:

After unexpected power loss:

✓ Data on disk (including recently fsynced data)
✓ Data in battery-backed disk cache
✓ Data in persistent memory (NVDIMM)

✗ Data in volatile RAM (dirty pages)
✗ Data in non-battery disk cache (if enabled!

Modern Persistent Memory:

Intel Optane DC Persistent Memory and similar technologies change the game:

Traditional:
  CPU ─► DRAM (volatile) ─► Disk (persistent)
  Data loss window: dirty_expire time

With Persistent Memory:
  CPU ─► PMEM (persistent) ─► Disk (backup)
  Data loss window: ~0 (direct persistence)

PMEM access:
  - Load/store instructions persist directly
  - Must use proper ordering (CLWB, SFENCE)
  - Dirty bits may be N/A (always persistent)

Kernel Panic and Dirty Pages:

On kernel panic:
  1. All file systems are NOT unmounted cleanly
  2. Dirty pages in memory are lost
  3. Disk state may be inconsistent

Recovery process:
  1. fsck / file system check on boot
  2. Replay journal if journaled FS
  3. Report lost files/data if unrecoverable
  
Mitigation:
  - Frequent syncs reduce data at risk
  - Reliable power (UPS) allows clean shutdown
  - Hardware watchdog can catch hangs

Visibility into dirty page state is essential for performance tuning and debugging. Here's how to monitor and analyze dirty page behavior.

System-Wide Statistics:

$ cat /proc/meminfo | grep -i dirty
Dirty:             12584 kB    # Currently dirty pages
Writeback:           128 kB    # Currently being written
WritebackTmp:          0 kB    # Writeback using temp pages

$ cat /proc/vmstat | grep -i dirty
nr_dirty 3146                   # Number of dirty pages
nr_writeback 32                 # Pages under writeback
nr_dirtied 1847362             # Total pages ever dirtied
nr_written 1840216             # Total pages written back

Per-Process Statistics:

# From /proc/[pid]/smaps
$ cat /proc/1234/smaps | grep -i dirty
Private_Dirty:         128 kB
Shared_Dirty:            0 kB

# Aggregate per process
$ grep -E "Private_Dirty|Shared_Dirty" /proc/1234/smaps | \
  awk '{sum += $2} END {print sum " kB dirty"}'  

Tracing Writeback Activity:

# Using ftrace to trace writeback events
$ echo 1 > /sys/kernel/debug/tracing/events/writeback/enable
$ cat /sys/kernel/debug/tracing/trace_pipe

# Sample output:
flush-8:0-1234  [001] .... 1234.567: writeback_start: ...
flush-8:0-1234  [001] .... 1234.890: writeback_written: nr=256
flush-8:0-1234  [001] .... 1235.123: writeback_wait: ...

Common Issues and Symptoms:

We've thoroughly explored the dirty bit—a single piece of hardware support with far-reaching implications. Let's consolidate our understanding:

What's Next:

The dirty bit is one of two crucial hardware-supported bits for page replacement. The next page explores the modify bit (also known as the access/reference bit), which serves a different but complementary purpose—tracking whether pages have been recently accessed to guide victim selection based on recency.