COMP 4270: Operating Systems
Task 1 – Implementation of Page Replacement Algorithms (25 pts)
Write a program that implements the LRU algorithm based on the counter-based
implementation method, and the optimal page replacement algorithm presented in class. In
this task, you will examine the impact of the number of frames on both the LRU and optimal
algorithms by varying the number of frames. We will also investigate how the LRU algorithm
performs in terms of the number of page faults in comparison with the optimal algorithm.
Generate a random page-reference string where page numbers range from 0 to 9. The length of
the reference string should be 10 (i.e., consisting of 10 digits). Apply the random pagereference string to each algorithm, and record the number of page faults incurred by each
algorithm. Vary the number of frames from 1 to 7 and repeat the experiment with the same
reference string. Draw a graph that illustrates the results. The x-axis, and y-axis of the graph
should be the number of frames, and the number of page faults, respectively. For example,
your graph may look like this.
Briefly discuss your findings. Submit both the code and report that includes your graph.
Task 2 – Performance Evaluation of the LRU Algorithm (25 pts)
In this task, you will evaluate the performance of the two different versions of the LRU
algorithm that we covered in class, i.e., the timer-based and the stack-based algorithms.
Specifically, you will measure and compare the running times of the timer-based LRU algorithm
and the stack-based LRU algorithm. Since you have already implemented the LRU algorithm
based on the timer-based method in Task 1, in this task, implement the algorithm based on the
stack-based method in order to compare the running times of the two algorithms.
Generate a random-reference string with length 500 (i.e., consisting of 500 digits) where page
numbers range from 0 to 20 (e.g., 0 2 18 12 20 1 …). Measure the running times of both timerbased and stack-based LRU algorithms with the random-reference string as input. Vary the
number of frames from 1 to 10 and repeat the experiment with the same reference string.
Here the running time is defined as the amount of time the algorithm takes to complete
processing the random-reference string. Draw a graph that illustrates the results. The x-axis and
y-axis of the graph should be the number of frames, and running time, respectively. For
example, your graph would look like this.
Briefly discuss your findings and submit both your code and report that includes your graph.
 Operating Systems Concepts 9
th Edition by Silberscharz, Yale, and Gagne, Wiley