Effective Access Time = 200ns = (1-p) * (100ns) + p * (16.4ms) = 100ns
- 16,399,900*p So p < 0.000006097, or the maximum acceptable page fault
is 1 in every 163,999 accesses.
#2
a) Given that the array is 100 elements long and the page size is 200
elements, we have a page fault on every access (100 page faults) in the
inner loop and a page fault on every other iteration of the outer loop
(50 page faults). Therefore, we have a total of 50 * 100 = 5,000 page faults.
b) Here we are referencing by row and we have a page fault on every
other iteration of the outside loop, for a total of 50 page faults.
#3
a) The memory references 10, 11, 104, 170, 73, 309, 185, 245, 246,
434, 458, 364 are mapped the following reference string:
0, 0, 1, 1, 0, 3, 1, 2, 2, 4, 4, 3
b)
[i] FIFO Replacement
Page Ref | 0 0 1 1 0 3 1 2
2 4 4 3
Frame 0 | 0 0 0 0 0 3 3
3 3 4 4 4
Frame 1 | - - 1 1 1 1
1 2 2 2 2 3
Fault | X - X
- - X - X - X - X
Total Page Faults = 6
[ii] Second Chance (reference bit *)
Page Ref | 0 0 1
1 0 3 1
2 2 4 4
3
Frame 0 | 0* 0* 0* 0* 0* 3*
3* 3 3 4* 4* 4
Frame 1 | - - 1*
1* 1* 1 1* 2* 2* 2*
2* 3*
Fault | X -
X - - X
- X - X
- X
Total Faults = 6
[iii] LRU (LRU *)
Page Ref | 0 0 1
1 0 3 1
2 2 4 4
3
Frame 0 | 0 0 0* 0*
0 0* 1 1* 1* 4
4 4*
Frame 1 | -* -* 1 1
1* 3 3* 2 2
2* 2* 3
Fault | X -
X - - X
X X - X
- X
Total Faults = 7
#4
Reference String = 1 2 3 4 5 2 3 4 3 2 4 4 2 4 4 4
The minimum working set size for 5 page faults to occur is 4:
Time Page reference Working set
Page fault
t1
1
{1}
x
t2
2
{1, 2}
x
t3
3
{1, 2, 3} x
t4
4
{1, 2, 3, 4} x
t5
5
{2, 3, 4, 5} x
t6
2
{2, 3, 4, 5} -
t7
3
{2, 3, 4, 5} -
t8
4
{2, 3, 4, 5} -
t9
3
{2, 3, 4} -
t10
2
{2, 3, 4} -
t11
4
{2, 3, 4} -
t12
4
{2, 3, 4} -
t13
2
{2, 4}
-
t14
4
{2, 4}
-
t15
4
{2, 4}
-
t16
4
{2, 4}
-