Algorithm in operating system

This algorithm is the simplest algorithm. The principle of this algorithm is like the principle of the queue (no priority queue), the inside first page it will come out first as well. These algorithms use a stack data structure. If no free frame during a page fault, the victim is selected stack frame in the bottom, the page that was the longest in memory.

Image. FIFO algorithm

At first, the algorithm is considered to adequately address concerns about the turn of the page up in the 70's, Belady find oddities in this algorithm is then known as Belady anomaly. Belady anomaly is a condition in which the page fault rate increases with the number of frames, as can be seen in the example below.

Image. Anomaly FIFO algorithm.

When the number of frames plus from 3 frames to 4 frames, the number of page faults that occur to be increased (from 14 page fault until 15 page fault). This usually occurs in the case of a page you just want a swap-out in advance. Therefore, sought for other algorithms that can better handling of page changes, as discussed below.

Optimal algorithm

This algorithm is the most optimal algorithm as the name implies. The principle of this algorithm is to replace the page that will not be used anymore for a long time, so that efficiency will increase the turn of the page (page fault that occurred less) and free from Belady anomaly. This algorithm has the lowest page fault rate of all algorithms in all cases. However, the optimal algorithm is not yet perfect because it means it is very difficult to implement. The system can not find any pages that will be used next.

Algoritma LRU (Least Recently Used)

Optimal algorithm is very difficult to its implementation, then made another algorithm which performance is close to the optimal algorithm with a slightly greater cost. The algorithm is to replace the old pages which are not needed. The assumption was that the page has not been used are no longer needed and most likely a new page is loaded will be used again.

Just as the optimal algorithm, LRU algorithm does not have Belady anomaly. The algorithm uses a linked list to record which pages long unused. Linked list is what makes the cost to grow, because they have to update the linked list each time a page in the access. The page is located at the front is a linked list of recently used pages. The longer it is not used, pages will increasingly be in the back and in the last position is the most pages long unused and ready for the swap.

source : Kemal Nasir & Renggo Pribadi @CSUI