Page Replacement Algorithms.

Objective
In this homework, you will be asked to simulate two different page replacement algorithms: First-in First-out(FIFO) and Least Recently Used(LRU).
This comparison will give you a better understanding of these two page replacement algorithms.

Introduction to Page Replacement
A program needs to have its code and data reside in memory before it is executed. But sometimes the memory size cannot fit all the code and data of running programs. The solution is to slice both memory and programs into equal-sized pages. An OS can easily swap in the needed page of a program from disk to memory. Paging happens when a page fault occurs. A page fault happens when a needed page is not resident in memory and needs to be swapped in, possibly overwriting another page in memory. A page replacement algorithm decides which memory page must be paged out (swap out, write to disk) to make room for the requested page.
To design a good page replacement algorithm, we don't want to frequently swap the same memory page in and out. So to evaluate a page replacement algorithm, we can run it on a particular string of memory references and determine the number of page faults that occur, the fewer the better.

Understanding Page Replacement Algorithms
(SGG chapter 9.4.2) FIFO: The newly brought-in page will replace the oldest page resident in memory. The idea is that the earliest page brought in will be the first one replaced. A detailed demostration of how FIFO page replacement algorithm works can be found in SGG Figure 9.12.

(SGG chapter 9.4.4) LRU: The Least Recently Used algorithm works on the assumption that pages that are most recently used will most likely to be used next. So the idea is to replace the longest-resident page when a new page is brought in. A detailed demostration of how the LRU algorithm works can be found in SGG Figure 9.15

Homework Description
(SGG) 9.40 Write a program that implements the FIFO and LRU page-replacement algorithms presented in this chapter.
First, generate a random page-reference string where page numbers range from 0 to 9.
Apply the random page-reference string to each algorithm, and record the number of page faults incurred by each algorithm. Implement the replacement algorithms so that the number of page frames can vary from 1 to 7. Assume that demand paging is used.

Page number: the page in the disk which will be demanded to swap in the memory.
Page frame: the page in the computer memory
page-reference string: a sequence of the pages on the disk that are demanded to swap into the memory.

Sample Code
The code will take two arguments: one is the reference range, the other is the number of page frames in memory.(The reference string size is harden coded as 100)
The sample code can be seen here. The command Format:
./pagefault [reference range] [number of page frames].
For example:

csguest@itl:~ ./pagefault 7 3


The displayed information looks as below:The randomized Reference String: 5 2 2 0 4 6 4 4 1 3 4 5 0 4 5 6 2 0 0 1
5 -1 -1
5 2 -1
5 2 -1
5 2 0
4 2 0
.
.
.
0 6 2
1 6 2
page fault of FIFO: 13


The Same Reference String: 5 2 2 0 4 6 4 4 1 3 4 5 0 4 5 6 2 0 0 1
5 -1 -1
5 2 -1
5 2 -1
5 2 0
4 2 0
.
.
.
6 2 0
1 2 0
page fault of LRU: 13

The test driver will generate a random page-reference string and call both the two algorithm functions, each of which will print out its number of page faults.

The page frames are represented by an dynamically-allocated integer array; the variable lementCount will track which is the nextpage frame to be replaced .

In each algorithm, it will simulate the paging process to take in the page-reference string and then decide which page in the page frames will be paged out each time. 

Homework Requirements
The code(either Java or C) should correctly calculate the number of page faults for each algorithm. For convenience, it is better for you to print out the memory page frames each time when page fault occurs so that you can easily check if your algorithm works correctly.
Set the Reference string's length to be large enough as 100.
Set the number of page frame to be 7, and the reference page range to be 9.
Run each of the two page replacement algorithms 5 times, record the number of the page faults in the file README; Then compare the results of the two algorithms and analyze which is better and why(Hints: it depends on the generated reference string/the page demanding scenario). Next, from an implementation aspect, analyze the disadvantages of LRU algorithm in this homework. Can you give a better solution to optimize implementation of the LRU algorithm?
Remember to upload both the README and source code to your polaris directory:/afs/cu/class/cs444/sp10/paging/yourname
Reference
 

http://en.wikipedia.org/wiki/Page_replacement_algorithm
Chapter 9, Operating System Concepts 8th Edition, SGG