Transcript Page Replacement

ITFN 2601
Introduction to Operating
Systems
Lecture 15
Page Replacement Algorithms
Agenda
Not Recently Used
First In-First Out
Second Chance
Clocking
LRU
Hardware/Software
Aging
Working Sets
Page Replacement Algorithms
Optimal
Swap unnecessary pages
Look forward in time
Find page with longest wait until being used
Swap it out
Minimal damage/effect
Unimplementable
Not Recently Used
Not Recently Used
00 – Not Referenced, Not Modified
01 – Not Referenced, Modified
10 – Referenced, Not Modified
11 – Referenced, Modified
First bit reset on clock-timer
Swap any page from lowest possible
group
First in Algorithms
FIFO
Swap the oldest page currently in memory
Could still be very active!
Second Chance
Reset “access” bit
Reset load time
First in, Clocking
Clock
Move the clock hand to point to “oldest”
page
Least Recently Used
Listings
Move a page to the front/end of the list each
time it is accessed
Very consuming
Counter
Each entry gets a “last used” time
Entry with oldest one goes *poof*
More LRU
Table
N pages
NxN matrix of bits
Each time page k is used
Row k set to 1’s
Column k set to 0’s
Swap row with the most 0’s
Software LRU
Not Frequently Used
OS maintains counters
Clock tick => Counter + Read bit
Never forgets, old data remains important
Aging
Shift counter right
Append Read bit at beginning
Aging example
Working Set
Working set
Pages used by a process
Working set as a page
Before the process loads, load the pages
Load an entire working set at once
If it doesn’t all fit, back to normal paging
OS must track the pages in the working set
PRA’s (Summary)