CS 471
Assignmnet
#4
Due Midnight, Thursday
April 18, 2013
Write
the following program in any programming language
PRABA (Page
Replacement Algorithms & Belady’s Anomaly)
Syntax:
PRABA -f
<sfile> |
-b <slength>
<tnumber>
Ø If the –f option is used, the program uses the
sequence stored in <sfile> to 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.
Ø If
the –b option is used, the program
generates a random sequence
of <slength>
and repeatedly try <tnumber> to detect Belay’s anomaly
in above algorithms.
Assume:
ü The Program Page Size is 9.
ü The Working Set Size is rages between
1-9.
ü The reference sequence stored in <sfile> are random numbers in the range
1-9 separated by spaces.
You may try my solution at:
http://www.cs.odu.edu/~cs471w/spring13/assignments/a4/wahab
EXAMPLE:
%
PRABA -f SequenceFile
Using Sequnce stored in File: SequenceFile
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 64
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 34
8 11 17 15 18 16 17 20
9 9 9 9 9 9 9 9
%
PRABA -b 100 5
Testing Belady's Anomaly using 100 random sequences and Trying 5
times
Trial #1:
3 8 9 7 4 8 4 4 6 3 9 5 1 9 4 4
1 2 2 5 2 6 2 5 7 4 9 9 2 5
4 2 6 7 2 3 2 2 5 8 6 7 9 9
5 9 3 8 6 4
9 8 5 6 8 2 9 6 8 2 5 6 7 7 9 1 8 1 2 7 1 2 7 3 1 2 5
2 5 4 7 3 3 9 4 2 4 9 9 5 3
3 4 6 6 2 8 1 3 3
Page Fault Counts:
W OP FF LR MR LF MF RN
1 88 88 88 88 88 88 88
2 62 80 79 75 78 76 80
3 46 68 69 62 62 67 69
4 34 61 58 55 56 64 60
5 24 45 48 44 43 44 50
6 19 30 29 31 36 37 40
7 15 29 24 19 29 33 28
8 11 15 17 12 17 17 23
9 9 9 9 9 9 9 9
Trial #2:
3 2 9 4 9 3 3 2 1 9 1 2 5 7 1 5 3 2 9 8 1 5 7 3 4 1 5
3 4 2 8 2 6 4 8 8 5 9 7 8 9 2 9 7 4 2 4 3 7 6
3 1 5 7 8 3 2 6 9 5 2 5 3 3 6 3 2 2
1 4 5 7 4 8 8 5 7 6 6 9 1 8
6 7 5 8 6 5 8 8 7 9 2 9 2 7 8 4 1 7
Page Fault Counts:
W OP FF LR MR LF MF RN
1 93 93 93 93 93 93 93
2 67 84 84 80 77 79 76
3 50 73 76 70 67 73 66
4 37 59 54 57 58 62 59
5 28 48 46 49 51 49 50
6 21 45 36 40 39 42 39
7 15 27 29 28 26 18 30
8 11 17 19 22 18 18 16
9 9 9 9 9 9 9 9
Trial #3:
3 7 9 2 6 6 3 1 5 4 2 9 1 5 6 8 5 1 7 2 1 5 3 1 1 6 9 6 7 6 3 2 5 1 6 5 8 7 8 7 4 6 9 6 3 4 5 8 1 8
7 4 5 9 8 5 3 7 2 9 7 3 6 9 2 4 5 2 7 2 9 4 9 6 6 9 9 1 8 3 4 3 7 5 7 3 8 9 6 3 2 5 9 3 5 4 8 6 8 2
Page Fault Counts:
W OP FF LR MR LF MF RN
1 96 96 96 96 96 96 96
2 72 86 84 84 83 84 79
3 56 77 75 74 73 72 67
4 43 70 68 59 63 59 58
5 33 57 54 50 50 56 49
6 24 37 49 40 41 46 35
7 17 42 30 32 29 34 27
8 12 18 21 21 21 18 20
9 9 9 9 9 9 9 9
Belady detected: FF W[6]=37
< W[7]=42 (Diffrence
= 5)
Trial #4:
2 4 7 4 9 3 1 1 3 9 6 5 1 4 2 4 8 6 5 3 8 3 2 7 8 1 3
5 2 1 3 3 4 1 2 1 8 2 6 2 5 9 8 5 6 2 2 8 3 2
5 1 6 9 4 7 3 7 8 7 3 3 2 5 9 4 5 4 2 4 5 9 6 5 4 7 4
8 2 5 1 2 1 6 1 5 9 7 7 4 5 2 7 3 9 3 9 4 3 9
Page Fault Counts:
W OP FF LR MR LF MF RN
1 95 95 95 95 95 95 95
2 65 83 80 80 83 79 74
3 48 67 68 72 74 71 67
4 37 59 56 64 62 63 55
5 28 48 49 49 51 51 44
6 21 40 39 40 44 35 38
7 16 30 30 26 36 23 30
8 12 14 17 16 16 18 20
9 9 9 9 9 9 9 9
Trial #5:
1 9 7 1 6 8 9 8 7 6 7 3 5 3 8 5 1 6 3 6 7 3 7 5 6 6 8
8 5 7 7 3 4 7 8 6 2 9 8 2 9
3 8 4 5 4 2 3 4 4
9 3 7 1 3 9 5 6 9 2 8 9 6 2 6 5 8 4 9 1 1 6 4 3 2 1 5
3 3 9 4 7 2 4 2 9 2 2 6 7 8
8 5 6 3 9 9 6 1 4
Page Fault Counts:
W OP FF LR MR LF MF RN
1 91 91 91 91 91 91 91
2 65 81 82 75 78 78 81
3 47 70 68 64 75 69 75
4 35 52 56 53 62 56 58
5 25 40 44 45 44 50 52
6 19 37 35 35 43 34 38
7 15 25 28 20 32 30 24
8 12 15 18 16 20 14 18
9 9 9 9 9 9 9 9
Summery of Belady detected:
3: FF
Bealdy's Occurence
Counts:
OP FF LR MR LF MF RN
0 1 0 0 0 0 0