Introduction

The page stealer (also called pageout daemon or pagedaemon, often process 2) is a kernel process that runs periodically to ensure there are enough free memory pages available. When memory runs low, it selects pages to remove from memory and write to disk, "stealing" them from processes.

When Does the Page Stealer Run?

• The kernel maintains two thresholds:
• lotsfree — the ideal number of free pages.
• minfree — the minimum acceptable number of free pages.
• The page stealer is activated when the number of free pages drops below lotsfree.
• It runs more aggressively as free pages approach minfree.
• It stops (goes to sleep) when enough pages have been freed.

Free Pages:
┌──────────────────────────────────────────────┐
│ minfree         lotsfree                      │
│    ▼               ▼                          │
│    ├───────────────┤                          │
│    │  Page Stealer │  Page Stealer             │
│    │  AGGRESSIVE   │  ACTIVE                   │
│    │               ├──────────────────────────┤
│    │               │  Page Stealer SLEEPING    │
└──────────────────────────────────────────────┘

Page Replacement Algorithm — Two-Handed Clock

The UNIX page stealer uses an enhanced version of the clock algorithm called the two-handed clock (or NRU — Not Recently Used) algorithm.

---

Basic Clock Algorithm (One Hand):

1. All page frames are arranged in a circular list (like a clock).
2. A single "hand" (pointer) sweeps around the clock.
3. At each frame, the hand checks the reference bit (R):

• If R = 1 → the page was recently used → clear R to 0, move to the next frame.
• If R = 0 → the page was NOT recently used → steal this page (candidate for removal).

---

Two-Handed Clock Algorithm (UNIX Enhancement):

UNIX uses two hands separated by a fixed distance (called handspread):

• Front Hand (Examiner): Sweeps ahead and clears the reference bit of each page.
• Back Hand (Stealer): Follows behind and checks the reference bit:
• If R = 0 → the page was NOT accessed between the two hand sweeps → steal it.
• If R = 1 → the page was accessed after the front hand cleared it → leave it.

              Front Hand (clears R bits)
                  │
                  ▼
    ┌───┬───┬───┬───┬───┬───┬───┬───┐
    │ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 1 │  ← Reference bits
    └───┴───┴───┴───┴───┴───┴───┴───┘
                          ▲
                          │
              Back Hand (steals pages with R=0)

    ◄── handspread ──►

Handspread:

• The distance (in pages) between the front and back hands.
• Larger handspread = more time for pages to be re-referenced → fewer pages stolen (conservative).
• Smaller handspread = less time → more pages stolen (aggressive).
• Tunable parameter.

---

What Happens When a Page is Stolen?

1. Check the modify bit (M):

• If M = 0 (clean page) → the page can be simply freed (data already on disk or is a copy of the executable).
• If M = 1 (dirty page) → the page must be written to swap before freeing.

1. The page frame is placed on the free list.

1. The corresponding page table entry is updated:

• Valid bit is cleared (V = 0).
• Swap address is recorded.

1. If the process accesses this page later, a page fault occurs, and the fault handler reloads the page (see next lesson).

Page Stealer Algorithm (Pseudocode)

page_stealer() {
    loop forever {
        sleep until free_pages < lotsfree;

        while (free_pages < lotsfree) {
            // Front hand
            advance front_hand;
            clear reference_bit of page at front_hand;

            // Back hand (handspread behind front hand)
            advance back_hand;
            page = page at back_hand;

            if (page.reference_bit == 0) {
                if (page.modify_bit == 1) {
                    schedule page write to swap;   // async I/O
                }
                free the page frame;
                add frame to free list;
                update page table entry;
                free_pages++;
            }
        }
    }
}

Page Reclaim (Optimization)

• When a page is freed, the frame goes to the free list BUT the data is not immediately erased.
• If the process faults on that page before the frame is reused, the kernel can reclaim the frame from the free list — no disk I/O needed!
• This significantly reduces disk I/O for pages that are freed and re-accessed quickly.

Summary

• The page stealer frees memory pages when the system is running low.
• It uses the two-handed clock algorithm: front hand clears reference bits, back hand steals pages not re-referenced.
• Clean pages are freed immediately; dirty pages are first written to swap.
• The handspread parameter controls how aggressively pages are stolen.
• Page reclaim avoids disk I/O for recently freed pages that are needed again.