The not recently used (NRU) page replacement algorithm is an algorithm that favors 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.
- When a page fault occurs, the operating system inspects all the pages and divides them into four categories based on the current values of their R (referenced; read or written) and M (modified) bits:
* Class 0: not referenced, not modified.
* Class 1: not referenced, modified.
* Class 2: referenced, not modified.
* Class 3: referenced, modified.
- Although class 1 pages seems, at first glance, impossible, they occur when a class 3 page has its R bit cleared by a clock interrupt. Clock interrupts do not clear the M bit because this information is needed to know whether the page has to be rewritten to disk or not. Clearing R but not M leads to a class 1 page.
- The NRU (Not Recently Used) algorithm removes a page at random from the lowest numbered nonempty class.
- It is better to remove a modified page that has not been referenced in at least one clock tick (typically 20 msec) than a clean page that is in heavy use.
- The main attraction of NRU is that it is easy to understand, moderately efficient to implement, and gives a performance that, while certainly not optimal, may be adequate.
Thursday, January 14, 2010
Not Recently Used (NRU) Page Replacement Algorithm
Posted by Sunflower at 1/14/2010 05:29:00 PM
Labels: Algorithms, Not Recently Used, NRU, Page Fault, Page Replacement, pages
Subscribe by Email |
|
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment