Assignment 4: Due Monday, December 1. 



Part 1:

For each of the paging algorithms (FIFO, FIFO second chance and LRU)
discussed in the seminar and tutorial
(see link on  home page), 
simulate the algorithm on some "randomly" chosen
sequence of at least 25 page requests for the case of 5 fast memory
pages and 10 virtual pages. Here is one way to generate 
a random sequence of requests:

Consider your full (first, middle, last) English name as a 
sequence of characters and then convert to a sequence of 
decimal digits (in 1, ..., 26) in the obvious way with 
a = 1, ..., z = 26 and blank = 27. (If your name contains
non latin symbols then use 28, 29,   .)
Now view this as a sequence S of decimal digits (in 0, ..., 9).
If your name is not long enough to generate 25 decimal
digits then append a prefix of my name to yours. 

Assuming that the fast memory has 5 pages and the virtual memory
has 10 pages (corresponding to the decimal digits), simulate the
algorithms on the sequence S that you generated assuming that
initially the fast memory is empty. That is, indicate for each page
requested (i.e. each decimal digit in the sequence S) whether or not
the page request would result in a page fault. 

Part 2: 

For every ordered pair (A,A') of the three paging algorithms above, 
try to find a sequence S where  A performs better than A'.


Part 3: Based on the limited experience of this assignment,
and any discussions in class or anything you have read, 
which algorithm do you prefer and why? Please cite any references
that you use.