If FIFO page replacement is used with three page frames avai

If FIFO page replacement is used with three page frames available to the process, how many page faults will occur with the reference string 123412341234 if the three frames are initially empty? Repeat for LRU. Repeat again for MRU.

Solution

FIFO

1             2               3            4               1             2            3             4             1             2              3            4

1

1

1

4

4

4

3

3

3

2

2

2

2

2

2

1

1

1

4

4

4

3

3

3

3

3

2

2

2

1

1

1

4

F                F               F           F                       F            F                     F              F              F              F                 F                 F                       

FAULTS = 12

LRU

1             2               3            4               1             2            3             4             1             2              3            4

1

1

1

4

4

4

3

3

3

2

2

2

2

2

2

1

1

1

4

4

4

3

3

3

3

3

2

2

2

1

1

1

4

F                 F              F                  F            F                      F              F              F              F              F              F                   F      

FAULTS =12                       

                As there is sequence 1234 in the pages LRU and FIFO behaves similar.

MRU

1             2               3            4               1             2            3             4             1             2              3            4

1

1

1

1

1

1

1

1

1

2

2

2

2

2

2

2

2

3

3

3

3

3

3

3

4

4

4

4

4

4

4

4

4

F                F                 F             F                 H            H              F                    H             H             F                  H               H                      

FAULTS =6

1	1	1	4	4	4	3	3	3	2	2	2
	2	2	2	1	1	1	4	4	4	3	3
		3	3	3	2	2	2	1	1	1	4