Simulating LRU in Software

Simulating LRU in Software

Although both of the previous LRU algorithms are (in principle) realizable, few, if any, machines have the required hardware. Instead, a solution that can be implemented in software is required One possibility is called the NFU (Not Frequently Used) algorithm. It requires a software counter  associated with each page, initially zero. At each clock interrupt, the operating system scans all the pages in memory. For each page, the R bit, which is 0 or 1, is added to the counter. The counters roughly keep track of how often each page has been referenced. When a page fault takes place, the page with the lowest counter is chosen for replacement.

The main problem with NFU is that it never forgets anything. For instance, in a multipass compiler, pages that were heavily used during pass 1  may still have a high count well into later passes. Indeed, if pass 1 happens to have the longest execution time of all the passes, the pages  containing the code for subsequent passes may always have lower counts than the pass 1 pages. As a result, the operating system will  remove useful pages instead of pages no longer in use.

Fortunately, a small alteration to NFU makes it able to simulate LRU quite well. The modification has two parts. First, the counters are each  shifted right 1 bit before the R bit is added in. Second, the R bit is added to the leftmost rather than the rightmost bit.

Figure 1 shows how the modified algorithm, known as aging, works. Assume that after the first clock tick the R bits for pages 0 to 5 have  the values 1, 0, 1, 0, 1 and 1, respectively (page 0 is 1, page 1 is 0, page 2 is 1, etc.). In other words, between tick 0 and tick 1, pages 0, 2, 4,  and 5 were referenced, setting their R bits to 1, while the other ones remain 0. After the six corresponding counters have been shifted and the R bit inserted at the left, they have the values shown in Figure 1(a). The four remaining columns show the six counters after the next four clock  ticks.

The aging algorithm simulates LRU in software

When a page fault takes place, the page whose counter is the lowest is removed. It is clear that a page that has not been referenced for, say, four  clock ticks will have four leading zeros in its counter and therefore will have a lower value than a counter that has not been referenced for three clock  ticks.

This algorithm differs from LRU in two ways. Look at  pages 3 and 5 in Figure 1(e). Neither has been referenced for two clock ticks; both were referenced in the tick prior to that. According to LRU, if a page must be replaced, we should choose one of these two. The trouble is, we do not know which of them was referenced last in the interval between tick 1 and tick 2. By recording only one bit per time interval, we have lost the ability to distinguish references early in the clock interval from those occurring later. All we can do is remove page 3, because page 5 was also  referenced two ticks earlier and page 3 was not.

The second difference between LRU and aging is that in aging the counters have a limited number of bits (8 bits in this example) which limits its  past horizon. Assume that two pages each have a counter value of 0. All we can do is pick one of them at random. In fact, it may well be that  one of the pages was last referenced nine ticks ago and the other was last referenced 1000 ticks ago. We have no way of seeing that. In practice, however, 8 bits is usually enough if a clock tick is around 20 msec. If a page has not been referenced in 160 rnsec, it possibly is not that important.


Tags

nfu algorithm, software counter, memory, aging