Question 1 : Replacement [42 Pts] Consider the following page reference string:

g, e,b, c,e, c,a, g,d, a,g, b

With four frames, how many page faults would occur with the following page replacement algorithms?

2,970

Explanation:

The string are arranged as follow: a,a,b,b,c,c,d,e,e,g,g,g

There are 12 combinations and with four frames

Then, it can be computed thus: nCr, where n = 12 and r = 4 = n!/r(n - r)!

∴ 12C4 = 12!/4(8)! = 2970

Optimal

Time 123456789101112

RS. ecbeagdcegda

F0. e e a

F1 c c c c c c c c c c c

F2 b b b g g g g g g g

F3 a a d d d d d d

Page fault? * * * * * * *

Total page fault:7

2. LRU

Time 1 2 3 4 5 6 7 8 9 10 11 12

RS e c b e a g d c e g d a

F0 e e e e e e e c c c c a

F1 c c c c g g g g g g g

F2 b b b b d d d d d d

F3 a a a a e e e e

Page fault? Y Y Y N Y Y Y Y Y N N Y Total page fault:9

3. LRU approximation algorithm: Second chance

Time 1 2 3 4 5 6 7 8 9 10 11 12

RS e c b e a g d c e g d a

F0 0,e 0,e 0,e 1,e 1,e 0,e 0,e 0,e 1,e 1,e 1,e 0,e

F1 0,c 0,c 0,c 0,c 0,g 0,g 0,g 0,g 1,g 1,g 0,g

F20,b0,b0,b0,b0,d0,d0,d0,d1,d0,dF30,a0,a0,a0,c0,c0,c0,c0,a

Page fault? YYYNNNNY

Total page fault: 8