Implementation of LRU

There are several ways to implement the LRU algorithm. However, there are two fairly well-known are counter and stack
counter
How this is done by using a counter or a logical clock. Each page has a value that was originally initialized to 0. When access to a new page, the value of the clock on the page will get one. The more often the page is accessed, the greater the value of its counter and vice versa. To do so required an extra write to memory. In addition to containing the pages that are loaded, the memory also contains the counter of each page. The page is a page that has replaced the smallest clock which is the most frequently accessed pages. Disadvantages of this approach is counter to require additional support hardware.
How this is done by using a stack that indicates which pages in memory. Every time a page is accessed, will be placed at the top of the stack. If there is a page that needs to be replaced, then the page is located at the bottom of the stack will be replaced so that every time a new page is accessed not have to look back pages to be replaced. Compared to the implementation of the counter, the cost to implement the LRU algorithm using a stack would be more expensive because the entire contents of the stack must be updated each time you access the page, while the counter, the counter only changed pages are accessed, no need to change the counter from all pages that existing.

Image. LRU algorithm with Stack

Image. LRU algorithm

Another algorithm
Actually there are many algorithms which replace the page other than the three main algorithms that have been discussed earlier (the main does not mean most often used). The following are two examples of other algorithms are also quite popular and easy to implement.
The first algorithm is a second chance algorithm. Second chance algorithm is based on an enhanced FIFO algorithm. This algorithm uses the additional reference bit whose value is 0 or 1. If the FIFO using the stack, then the second chance using a circular queue. The new page is loaded or a new use will be given the value 1 in its reference bit. Pages that its reference bit set to 1 will not be directly replaced even though he is on the bottom line (in contrast to FIFO).


The sequence of work steps second chance algorithm is as follows:

• When a page fault and there is no free frame, it will be carried out raids (search for victims) the page reference bit is 0 it starts from the bottom of the queue (such as FIFO).
• Each page that is not in-swap (because of its reference bit value 1), each as raids passed its reference bit is set to 0.
• If found a page that its reference bit is 0, then the page that are swap.
• If the queue until the end of a page not found its reference bit is 0, then the raid carried out again from scratch.

In the picture below, we will illustrate the second chance algorithm and the algorithm FIFO as a comparison.

Image. Second Chance Algorithm.

Image. FIFO algorithm

The second algorithm is a random algorithm. Random algorithm is fairly simple algorithm is also in addition to the FIFO algorithm. In this algorithm, the selected page is victim selected at random . But the algorithm is relatively low cost, because it does not require a stack, queue, or counter. Compared to FIFO, average page fault rate case showed random algorithm is lower than the FIFO algorithm. While compared to LRU, random algorima is superior in terms of looping memory reference, because random algorithm does not require looping.

Image. Random algorithm

source : Kemal Nasir & Renggo Pribadi @CSUT