Not recently used

from Wikipedia, the free encyclopedia

Not recently used (NRU) is a memory paging strategy . It preferentially swaps out pages that have not been used or modified within a time interval. For this purpose, the pages are marked as unread and unchanged at regular intervals. If a page has to be swapped out, a check is made to determine which pages have not changed these markings.

Basics

One of the tasks of an operating system is to manage the main memory. The main memory is divided into units of a fixed size, the memory pages (tiles) . If the main memory is fully used, a page must be transferred to the hard disk. Since the hard disk is much slower than the main memory, there are strategies to select a page for swapping that is not needed again immediately and has to be swapped in.

implementation

Every entry in the page table has two markings in the NRU algorithm:

  • A bit ( A ccess for access Engl.) Indicates whether an access is made on the side
  • The M-bit ( M odified for English. Changed) indicates whether the page was changed

Whenever a page is accessed, the A bit is set to 1. And whenever the data on a page is changed, the M bit is set to 1. The A bits are reset to 0 at regular intervals.

When a page needs to be swapped out, a randomly selected page is swapped out, which has not changed (M = 0) and which has recently been moved to, i. H. has not been accessed since the A bits were last reset (A = 0). Since it is possible that no page has this property, a page that has been changed or accessed may have to be swapped out. The following list indicates the priority with which a page is paged out:

  1. A = 0, M = 0 (not read, not changed)
  2. A = 0, M = 1 (not read, but changed)
  3. A = 1, M = 0 (read, but not changed)
  4. A = 1, M = 1 (read and changed)

The NRU algorithm ensures that pages that have not been used for a long time and therefore will probably not be used in the near future are given preference. This is to avoid that pages often have to be swapped out so that the slower background memory has to be accessed as few as possible.

The algorithm leads to acceptable results in practice. In addition, it has the advantage that it is easy to implement.