Need help on this homework problem. 4. (25 poiuts ) A computer has four page fra

Question

Need help on this homework problem.

4. (25 poiuts ) 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): Page Loaded Last Reference R M 0 126 230 120 150 279 260 272 280 2 Answer and explain briefly your answer for each of the following: a) Which page will NRU replace ? b) Which page will FIFO replace? e) Which page will LRU replace? d) Which page will FIFO with second chance replace ?

Explanation / Answer

a) NRU

The not recently used (NRU) page replacement algorithm is an algorithm that favours keeping pages in memory that have been recently used. This algorithm works on the following principle: when a page is referenced, a referenced bit is set for that page, marking it as referenced. Similarly, when a page is modified (written to), a modified bit is set. The setting of the bits is usually done by the hardware, although it is possible to do so on the software level as well.

At a certain fixed time interval, a timer interrupt triggers and clears the referenced bit of all the pages, so only pages referenced within the current timer interval are marked with a referenced bit.

When a page needs to be replaced, the operating system divides the pages into four classes:

referenced, modified

referenced, not modified

not referenced, modified

not referenced, not modified

Although it does not seem possible for a page to be modified yet not referenced, this happens when a page has its referenced bit cleared by the timer interrupt.

The NRU algorithm picks a random page from the lowest category for removal.

So out of the above four page categories, the NRU algorithm will replace a not-referenced, not-modified page if such a page exists.

In our question there is one page, with category of not-referenced, not-modified i.e., "Page 0". Hence answer for option a is "Page 0".

b) FIFO

The first-in, first-out (FIFO) page replacement algorithm is a low-overhead algorithm that requires little bookkeeping on the part of the operating system. The operating system keeps track of all the pages in memory in a queue, with the most recent arrival at the back, and the oldest arrival in front. When a page needs to be replaced, the page at the front of the queue (the oldest page) is selected.

In our question, the oldest page loaded is "Page 2", which is loaded at 120. Hence answer for option b is "Page2".

c) LRU

The least recently used (LRU) page replacement algorithm keeps track of page usage over a short period of time, while NRU just looks at the usage in the last clock interval. LRU works on the idea that pages that have been most heavily used in the past few instructions are most likely to be used heavily in the next few instructions too. While LRU can provide near-optimal performance in theory (almost as good as adaptive replacement cache), it is rather expensive to implement in practice.

In our question, "page1" was loaded at 230 and and last referenced at 260. "Page 1" gets replaced by LRU since it got loaded at 230, where as other pages were loaded a lot earlier than "Page 1" and got last referenced time is much greater than loaded time. Hence answer for option c is "Page 1".

d) FIFO with second chance

In the Second Chance page replacement policy, the candidate pages for removal are consider in a round robin matter, and a page that has been accessed between consecutive considerations will not be replaced.

In our example, its unclear that which page was accessed consecutively. Require more info to answer this option.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.