Assignment Description
Write a Python program that implements the F IF O, LRU , and optimal page replacement algorithms presented in Chapter 9: Virtual Memory of Sil-berschatz et al. [Silberschatz et al., 2012].
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 F IF O, LRU , and optimal (OPT) replacement algorithms so that the number of page frames can vary from 1 to 7. Assume that demand paging is used. The main function should include the following.:
def main():
#...TODO...
size = int(sys.argv[1])
print ’FIFO’, FIFO(size,pages), ’page faults.’ print ’LRU’, LRU(size,pages), ’page faults.’ print ’OPT’, OPT(size,pages), ’page faults.’
if __name__ == "__main__":
if len(sys.argv) != 2:
print ’Usage: python paging.py [number of pages]’ else:
main()
1
Implement these FIFO, LRU and OPT algorithms as functions within one file called paging.py, making sure that you clearly identify yourself (name and student number) in comments at the top of the file.
The total assignment mark (100) will be calculated as follows.:
1. Correct implementation and functioning of FIFO. (30%)
2. Correct implementation and functioning of LRU. (30%)
3. Correct implementation and functioning of OPT. (40%)
Note: Values in bold parentheses are the percentage weighting of each ques-tion as a portion of the total assignment mark.
References
[Silberschatz et al., 2012] Silberschatz, A., Galvin, P., and Gagne, G. (2012). Operating Sys-tem Concepts - 9th Edition. John Wiley & Sons, New York, USA.
2
