Page Replacement Algorithms

Introduction

This handout shows how the various page replacement algorithms work. We shall call the pages of the program a, b, c, ... to distinguish them from the time (1, 2, 3, ...).

Fixed Number of Frames

We shall demonstrate these algorithms by running them on the reference string w = cadbebabcd and assume that, initialy, pages a, b, c, and d occupy frames 0, 1, 2, and 3 respectively. When appropriate, the little arrow -> indicates the location of the "pointer" which indicates where the search for the next victim will begin.

First In/First Out (FIFO)

This policy replaces pages in the order of arrival in memory.
time012345678910
w cadbebabcd
frame 0a-a-a-a-a-eeeee-d
frame 1bbbbbb-b-aaaa-
frame 2cccccccc-bbb
frame 3ddddddddd*cc
page fault     12345
page(s) loaded     e abcd
page(s) removed     a bcde

Optimal (OPT, MIN)

This policy selects for replacement the page that will not be referenced for the longest tile in the future.
time012345678910
w cadbebabcd
frame 0aaaaaaaaaad
frame 1bbbbbbbbbbb
frame 2ccccccccccc
frame 3dddddeeeeee
page fault     1    2
page(s) loaded     e    d
page(s) removed     d    a

Least Recently Used (LRU)

This policy selects for replacement the page that has not been used for the longest period of time.
time012345678910
wcadbebabcd
frame 0aaaaaaaaaaa
frame 1bbbbbbbbbbb
frame 2ccccceeeeed
frame 3dddddddddcc
page fault     1   23
page(s) loaded    e   cd
page(s) removed    c   de
stack (top) cadbebabcd
  --cadbebabc
  ----caddeeab
stack (bottom) ------caaddea

Not-Recently-Used or Not Used Recently (NRU, NUR)

This policy selects for replacement a random page from the following classes (in the order given): not used or modified, not used but modified, used and not modified, used and modified. In the following, assume references 2, 4, and 7 are writes. The two numbers written after each page are the use and modified bits, respectively.)

time012345678910
w ca*db*eba*bcd
frame 0aa/00a/11a/11a/11a/01a/01a/11a/11a/01a/01
frame 1bb/00b/00b/00b/11b/01b/11b/11b/11b/01b/01
frame 2cc/10c/10c/10c/10e/10e/10e/10e/10e/00d/10
frame 3dd/00d/00d/10d/10d/00d/00d/00d/00c/10c/10
page fault     1   23
page(s) loaded     e   cd
page(s) removed     c   de

Clock

This policy is similar to LRU and FIFO. Whenever a page is referenced, the use bit is set. When a page must be replaced, the algorithm begins with the page frame pointed to. If the frame's use bit is set, it is cleared and the pointer advanced. If not, the page in that frame is replaced. Here the number after the page is the use bit; we'll assume all pages have been referenced initially.

time012345678910
w cadbebabcd
frame 0aa/1-a/1-a/1-a/1-e/1e/1e/1e/1e/1-d/1
frame 1bb/1b/1b/1b/1b/0-b/1-b/0b/1b/1b/0
frame 2cc/1c/1c/1c/1c/0c/0a/1a/1a/1a/0
frame 3dd/1d/1d/1d/1d/0d/0d/0-d/0-c/1c/0
page fault     1 2 34
page(s) loaded     e a cd
page(s) removed     a c de

Second-chance Cyclic

This policy merges the clock algorithm and the NRU algorithm. Each page frame has a use and a modified bit. Whenever a page is referenced, the use bit is set; whenever modified, the modify bit is set. When a page must be replaced, the algorithm begins with the page frame pointed to. If the frame's use bit and modify bit are set, the use bit is cleared and the pointer advanced; if the use bit is set but the modify bit is not, the use bit is cleared and the pointer advanced; if the use bit is clear but the modify bit is set, the modify bit is cleared (and the algorithm notes that the page must be copied out before being replaced) and the pointer is advanced; if both the use and modify bits are clear, the page in that frame is replaced. In the following, assume references 2, 4, and 7 are writes. The two numbers written after each page are the use and modified bits, respectively.) Initially, all pages have been used but none are modified.

time012345678910
w ca*db*eba*bcd
frame 0aa/10-a/11-a/11-a/11-a/00*a/00*a/11a/11a/11-a/00*
frame 1bb/10b/10b/10b/11b/00*b/10*b/10*b/10*b/10*d/10
frame 2cc/10c/10c/10c/10e/10e/10e/10e/10e/10e/00-
frame 3dd/10d/10d/10d/10d/00-d/00-d/00-d/00-c/10c/00
page fault     1   23
page(s) loaded     e   cd
page(s) removed     c   db

Variable Number of Frames

We shall demonstrate these algorithms by running them on the reference string w = ccdbcecead.

Working Set (WS)

This policy tries to keep all pages in a process' working set in memory. This table shows the pages consitiuting the working set at each reference. Here, we take the working set to be that set of pages which has been referenced during the last t = 4 units. We also assume that a was referenced at time 0, d at time -1, and e at time -2.

time012345678910
w ccdbcecead
Page aaaaa----------aa
Page b--------bbbb------
Page c--cccccccccc
Page dddddddd------d
Page eee--------eeeee
page fault 1  2 3  45
page(s) loaded c  b e  ad
page(s) removed e  a d    

Page Fault Frequency (PFF)

This approximation to the working set policy tries to keep page faulting to some prespecified range. If the time between the current and the previous page fault exceeds some critical value t, then all pages not referenced during that interval are removed. This table shows the pages resident at each reference. Here, we take t = 2 units and assume that initially, a, d, and e are resident.

time012345678910
w ccdbcecead
Page aaaaa----------aa
Page b--------bbbbb----
Page c--cccccccccc
Page dddddddddd--d
Page eeeee----eeeee
page fault 1  2 3  45
page(s) loaded c  b e  ad
page(s) removed ?  a,e    b,d 


Send email to cs150@csif.cs.ucdavis.edu.

Department of Computer Science
University of California at Davis
Davis, CA 95616-8562



Page last modified on 6/2/99