Question

4. (25 points ) A computer has four page frames, The time of loading, time of last access, and the R ( referenced ) and M ( Modified ) bits for each page are shown below ( the times are in clock ticks) : Loaded 126 M Page Last Reference R. 0 0 279 1 230 260 120 150 272 2 1 280 1 3 Answer and explain briefly your answer for each of the following: a) Which page will NRU replace? b) Which page will FIFO replace? c) Which page will LRU replace? d) Which page will FIFO with second chance replace?

Answer 1

Q4.

(a) NRU (Not Recently Used) makes an approximation to replace the page based on referenced and modified bits. Based upon R and M bits, there arise four cases as below-

case 1: not referenced and not modified (R = M = 0)

case 2: not referenced, modified (R=0 and M=1)

case 3: referenced, not modified (R=1 and M=0)

case 4: referenced and modified (M=1 R=1)

The NRU algorithm removes a page from lowest numbered nonempty case.

Here, page 0 belongs to case 1

page 1 belongs to case 2

page 2 belongs to case 4

page 3 belongs to case 4

So lowest numbered nonempty case, PAGE-0 needs to be replaced by NRU.

(b). FIFO replacement algorithm works in a way that it will replace the page that arrived the earliest. So, FIFO will replace PAGE-2.

(c). LRU (Least recently used) is a page replacement algorithm that replaces the page that is least recently used.

Thus LRU takes decision on the basis of the Last Reference and page having least Last Reference is being replaced.

LRU will replace PAGE-1.

(d). Second chance algorithm works by adding a 'second chance' bit to each memory frame whenever page is referenced associated to that frame, this bit is set and when replacement is needed, this bit is reset (set to 0).

FIFO with second chance replacement algorithm will replace PAGE-2.