Question

suppose R=3,2,4,3,4,2,2,3,4,5,6,7,7,6,5,4,5,6,7,2,1 is a page reference stream.if the window size is 6 and assuming pure demand paging.how may page faults will it cause under the working set algorithm

Answer 1

Working set here at any point contains the previous 6 page references (non-distinct).

3 - Working Set = [3], Page fault count = 1

2 - Working Set = [3 2], Page fault count = 2

4 - Working Set = [3 2 4], Page fault count = 3

3 - Working Set = [2 4 3], Page fault count = 3

4 - Working Set = [2 3 4], Page fault count = 3

2 - Working Set = [3 4 2], Page fault count = 3

2 - Working Set = [3 4 2], Page fault count = 3

3 - Working Set = [4 2 3], Page fault count = 3

4 - Working Set = [2 3 4], Page fault count = 3

5 - Working Set = [2 3 4 5], Page fault count = 4

6 - Working Set = [2 3 4 5 6], Page fault count = 5

7 - Working Set = [2 3 4 5 6 7], Page fault count = 6

7 - Working Set = [3 4 5 6 7], Page fault count = 6

6 - Working Set = [4 5 7 6], Page fault count = 6

5 - Working Set = [7 6 5], Page fault count = 6

4 - Working Set = [7 6 5 4], Page fault count = 7

5 - Working Set = [7 6 4 5], Page fault count = 7

6 - Working Set = [7 4 5 6], Page fault count = 7

7 - Working Set = [4 5 6 7], Page fault count = 7

2 - Working Set = [4 5 6 7 2], Page fault count = 8

1 - Working Set = [4 5 6 7 2 1], Page fault count = 9