CS 471
Assignmnet
#4
Due Midnight, Thursday
April 12, 2012
Write
the following program.
The
program is called PRE (Page Replacement-Algorithms Evaluations)
It evaluates
the performance of the following algorithms:
· OP: Optimal. Page
will not be used for longest time in the future.
· FF: First-In-First-Out
· LR: Least
Recently Used.
· MR: Most Recently
Used.
· LF: Least Frequently
Used,
· MF: Most
Frequently Used.
· RN: Randomly select
a page to be replaced.
Program
Usage Syntax:
%
PRE [<seqfile>]
The program assumes that:
ü The Program Page Size is 9,
ü The Working Set Size is between 1-9 and
ü The reference sequence stored in a <seqfile>,
where the page numbers (between 1-9) in this file are
separated by spaces.
ü If there is no such file, the program generates a
random sequence of 100 numbers, each is between 1-9.
You may
execute/exercise my solution at:
http://www.cs.odu.edu/~cs471w/spring12/assignments/a4/wahab
EXAMPLE:
%
PRE SequenceFile
Program Page Size = 9
SequenceFile Size = 100
SequenceFile Content:
6 3 6 4 7 9 1 4 3 6 2 6 3 9 2 6 4 9 2 4 2 2 6 5 2 5 5 5
1 5 9 7 6 8 3 9 3 8 2 8 3 3 6 7 1 3 2 4 4 6 8 1 5 7 5 6 3 5 5 6 1 5 8 9 6
3 7 4 6 5 3 8 8 6 5 8 9 7 5 1 4 2 4 1 1 8 4 8 6 3 8 6 2 1 8 5 5 3 1 7
Page Fault Counts:
W OP FF
LR MR
LF MF RN
1
91 91 91 91 91 91 91
2
63 82 81
77 76 81
76
3
47 67 68
66 66 70
69
4
35 55 55 54
54
63 59
5
26 45 48
45 45 54
44
6
20 35 34
32 37 40
34
7
15 21 25
23 26 23
24
8
11 17 15
18 16 17
18
9 9 9 9 9 9 9 9
% PRE
Program Page Size = 9
Random Sequence Size = 100
Content:
3 5 8 9 9 6 8 3 3 5 4 4 6 5 5
4 2 8 3 6 9 8 9 7 4 1 8 4 4 5 5
6 5 6 4 1 1 9 7 3 7 9 4 8 2 6 6
4 2 4 5 3 9 8 5 4 4 2 7 8 3 3
8 7 5 1 8 6 3 3 4 7 6 6 7 7 7 1 7 9 4 4
1 2 2 1 6 7 3 4 8 6 7 1 6 2 6 8 3 7
Page Fault Counts:
W
OP FF LR
MR LF MF
RN
1 84 84 84 84 84 84 84
2 61
75 74
76 75
72 76
3 47
67 65
60 63
62 64
4 34
58 59
47 59
52 60
5 25
48 47 38 44
48 41
6 19
36 35
24 35
32 34
7 14
26 23
16 23
22 27
8 11
17 16
14 14 18
14
9 9 9 9 9 9 9 9