Page Replacement Algoritms

Page Replacement Algoritms


9.4.2 FIFO Page Replacement
A simple and obvious page replacement strategy is FIFO, i.e. first-in-first-out.

An interesting effect that can occur with FIFO is Belady's anomaly, in which increasing the number of frames available can actually increase the number of page faults

that occur!


9.4.3 Optimal Page Replacement
The discovery of Belady's anomaly lead to the search for an optimal page-replacement algorithm, which is simply that which yields the lowest of all possible page-

faults, and which does not suffer from Belady's anomaly.

This algorithm is simply "Replace the page that will not be used for the longest time in the future."


9.4.4 LRU Page Replacement

The prediction behind LRU, the Least Recently Used, algorithm is that the page that has not been used in the longest time is the one that will not be used again in the

near future. ( Note the distinction between FIFO and LRU: The former looks at the oldest load time, and the latter looks at the oldest use time. )


9.4.5 LRU-Approximation Page Replacement

http://www.youtube.com/watch?v=pGWbb7QIapQ
http://www.youtube.com/watch?v=GUL2txPndHs
http://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/9_VirtualMemory.html

• Page Replacement Algorithms

Fixed Number of Frames
First In/First Out (FIFO)
Optimal (OPT, MIN)
Least Recently Used (LRU)
Not-Recently-Used or Not Used Recently (NRU, NUR)
Clock
Second-chance Cyclic

Variable Number of Frames
Working Set (WS)
Page Fault Frequency (PFF)
http://nob.cs.ucdavis.edu/classes/ecs150-2008-02/handouts/memory/mm-pagexample.html

• Paging

• If a page is not in physical memory

– find the page on disk
– find a free frame
– bring the page into memory


• What if there is no free frame in memory?
Page Replacement

Basic idea
if there is a free page in memory, use it
if not, select a victim frame
write the victim out to disk
read the desired page into the now free frame
update page tables
restart the process

Page Replacement

• Main objective of a good replacement algorithm is to achieve a low page fault rate
– insure that heavily used pages stay in memory
– the replaced page should not be needed for
some time

• Secondary objective is to reduce latency of a page fault
– efficient code
– replace pages that do not need to be written out


https://docs.google.com/viewer?a=v&q=cache:Z21kbpmJIh4J:pages.cs.wisc.edu/~mattmcc/cs537/notes/Replacement.ppt+&hl=en&pid=bl&srcid=ADGEESj7uIgxkdOGy1nM__CGFctASur2ho79p326r_SPmkGuw_5G0sBrMh9curCHZ-yMfReLi5KTfYDWT-26pMp-ua-0JlYqejMr0MuE5K_g7otBipb33lvXDxWBWmql18tZhNjMFp1J&sig=AHIEtbRh8mSv8F9CqmQBImgSfm0uSEen-g

• Page Replacement Algorithms

Want lowest page-fault rate
Evaluate algorithm by running it on a particular string of memory references (reference string)
and computing the number of page faults on that string

https://docs.google.com/viewer?a=v&q=cache:1EsrAb83UboJ:www.cs.gsu.edu/~sguo/slides/4320/ch9.ppt+&hl=en&pid=bl&srcid=ADGEESg9YCt0XM4M5Kbx0qMipuZRja3jt3YNkX9El58HVxjyc5YUBhRQnDNWjEb-g82gxVAZSnZku0E0YPDcStMOlsGvxNfpe_D9KVxt-Hj-sl2E2H8al0Cf5ovtlio0vk7empKIc3eg&sig=AHIEtbRmJmBULv6rfF0J5nUwxXhs6qZKKA

• Page Replacement Algoritms

http://www.sal.ksu.edu/faculty/tim/ossg/Memory/virt_mem/page_replace.html

• Simulation

http://www.cs.uiuc.edu/class/sp06/cs241/Animations/PageReplace/replacement.html

• Page replacement algorithms

CPU cache
Web server cache of web pages
Buffered I/O (file) caches

https://docs.google.com/viewer?a=v&q=cache:87q4IkXXN4wJ:www.sju.edu/~ggrevera/csc4035/csc4035-4-4.ppt+&hl=en&pid=bl&srcid=ADGEESiss2DUzrHjwkVrMB7ryPxqMJcbpPULKDK2dgWPwLRBZeaGOjjtIwvnJ4Gub_0Niz5e9C5QF7pA1plk2Wi_6AWcZuAmGgZ5RL0JyYLSc6CjWrBGH0u3qvVgPk1vkbOvesVwLywL&sig=AHIEtbSiMSED0PP13zzQIvs5KiXkHgbjCg

• Page-Replacement Algorithms

A page replacement algorithm picks a page to  paged out and free up a frame

https://docs.google.com/viewer?a=v&q=cache:s6l_kPSedtYJ:www.cs.utah.edu/~mflatt/past-courses/cs5460/lecture10.pdf+&hl=en&pid=bl&srcid=ADGEEShMd71xSLfqZl12xDeMg6Ttawvbf94YiUSaGHHDw4vYKerSTntGWld6kN2iJEt2fdIzlJTrJw1Pp7M1rJaTXQaYSKUpIKMOtSttnmXTdjqgoFks2wwE_1n1SEKXZsDzwPRBN2d8&sig=AHIEtbQa2NhT70uDN_TLxB2fuPQ5dUnOwQ