In this assignment you will implement a selection of Page Replacement Algorithms and test them against a
simulator that generates random groups of virtual page requests for random numbers of frames (physical pages).
Authenticate with Kerberos: ( do this every time you log in )
$ kinit ( you will be prompted for your Blue CruzID password )
Authenticate with AFS: ( do this every time you log in )
Create a suitable place to work: ( only do this the first time you log in )
$ mkdir –p CSE130/Assignment5
$ cd CSE130/Assignment5
Install the lab environment: ( only do this once )
$ tar xvf /var/classes/CSE130/Assignment5.tar.gz
Build the starter code:
$ cd ~/CSE130/Assignment5 ( always work in this directory )
$ make grade ( runs the required functional tests – see below )
( also tells you what grade you will get – see below )
Run the pager executable:
$ ./pager <algorithm>
Algorithm being one of:
–fifo First In First Out
–lru Least Recently Used
–lfu Least Frequently Used
–sc Second Chance
–cq Circular Queue
The page replacement algorithms covered by this assignment have been discussed in class, so consult the
handouts from Memory 4, but also do you own research on-line and in the textbook.
In addition, a useful tool for checking the expected output from FIFO and Least Recently Used Algorithms is here:
An example of the Second Chance algorithm is here:
A detailed discussion of Page Replacement Algorithms in general is here:
The three frame Second Chance example (see below) is taken from the second link, the five frame Circular Queue
example (see below) is taken from the third link.
Note that in many circumstances, multiple algorithms will produce the same number and sequence of page faults.
If, for example, a program with five frames allocated keeps requesting the same four pages, there will be exactly
four page faults, in the same order, regardless of algorithm.
Provided Non-Random Examples
To aid debugging, a few non-random page sequences are available:
–simple A simple three frame FIFO sequence as described on slide 11 of Memory 4.
FIFO sequences exposing Bélády’s Anomaly as described on slide 12 of Memory 4.
A three and four frame FIFO example
A three and four frame Second Chance example
A three, four, and five frame Circular Queue example
Use these examples to repeatably test your implementation before running random tests.
Successfully implement all five Page Replacement algorithms. Note that to receive a grade for random executions
of a given algorithm, you must pass the relevant non-random examples above.
What steps should I take to tackle this?
Start with FIFO, you may find the supplied queue implementation useful. Then move on to LRU and LFU before
tackling Second Chance (a variation on FIFO) and finally, Circular Queue.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: firstname.lastname@example.org 微信:itcsdx