Module 8.2 - Page Replacement Algs

Page Frame Allocation

The policy question regarding which specific page frame a new page should be assigned to, noting that because all frames are the same size, any empty frame can be used.

Page Replacement Policy

A well-defined policy used to decide which page should be evicted or de-allocated from main memory when no free page frames are available.

Write Back

The process of writing an evicted page back to disk, which is only required if the page has been modified since it was loaded into memory.

Modified Page Tracking

A function of the page table that keeps track of whether a page has been modified or not to determine if a write back to disk is necessary during eviction.

Optimal Page Replacement Policy

An ideal but impractical policy that evicts the page that will not be used for the longest time in the future, requiring known memory reference patterns.

First-In First-Out (FIFO)

A simple replacement policy that evicts the page that has been in main memory the longest, providing fairness but failing to consider page usage.

TLB Policy

The policy consideration of determining which specific page table entries should be placed in the Translation Lookaside Buffer (TLB).

Second chance

A modification of FIFO that maintains a FIFO list of pages and a reference bit for each page to determine which page to evict.

Reference bit

A bit kept for each page in the second chance algorithm; a value of $0$ indicates the page has not been referenced, while a value of $1$ indicates it has been referenced.

Second Chance Eviction (Bit $0$)

The action taken when an eviction is needed and the reference bit of the oldest page is $0$; the page is evicted.

Second Chance Eviction (Bit $1$)

The action taken when the oldest page's reference bit is $1$; the bit is set to $0$, the page is moved to the end of the list, and the check repeats.

Least Recently Used (LRU)

A page replacement option that evicts the page that has not been used recently.

Locality of reference

A program characteristic that, when present, allows the Least Recently Used (LRU) algorithm to work reasonably well.

optimal page replacement theory

If new page is already in main memory, access is a hit.

Else,

(1) access causes a page fault,

(2) identify page whose next access will be farthest in the future,

(3) replace identified page with newly requested page.

first in first out (FIFO) page replacement theory

If new page is already in main memory, access is a hit.

Else,

(1) access causes a page fault,

(2) identify page that was brought into main memory the longest time ago,

(3) replace identified page with newly requested page.

modified FIFO/second chance page replacement theory

If new page is already in main memory, (1) access is a hit, (2) set reference bit of page to true.

Else,

access causes a page fault,

Do

(1) identify page that was marked as the oldest page,

(2) if identified page has its reference bit set to true, mark identified page as the newest page

(3) set reference bit of identified page to false

(4) else, replace identified page with newly requested page, break out of loop

least recently used page replacement policy

If newly requested page is already in main memory, access is a hit.

Else, (1) access causes a page fault, (2) identify page whpse previous access was fathest in the post, (3) replace identified page with newly requested page.