Policies

LRU algorithm

The Least Recently Used policy selects for replacement the frame that has not been referenced the longest.

• Based on the principle of locality of reference, if a frame is not referenced for a long time, it is likely that it will not be referenced in the near future.

Each frame must be labeled with the time of the last reference.

• Additional specific hardware may be required.

On page replacement, the list of occupied frames must be traversed to find out the one with the oldest last access time.

High cost of implementation and not very efficient.

NRU algorithm

The Not Recently Used policy selects for replacement a frame based on classes.

Bits Ref and Mod, fields of the entry of the page table, and typically processed by conventional MMU, are used to define classes of frames.

On page replacement, the algorithm selects at random a frame from the lowest non-empty class.

Periodically, the system traverses the list of occupied frames and puts Ref at zero.

FIFO algorithm

The FIFO policy selects for replacement based on the length of stay in memory.

• Based on the assumption that the longer a page resides in memory, the less likely it is to be referenced in the future.

The list of occupied frames is considered to be organized in a FIFO that reflects the loading order of the corresponding pages in the main memory.

On page replacement, the frame with the oldest page is selected.

The assumption in itself is extremely fallible.

• Consider for instance system shared libraries.

• But can be interesting with a refinement.

Second chance algorithm

The second chance policy is an improvement of the FIFO algorithm, giving a page a second chance before it is replaced.

On-page replacement:

• The frame with the oldest page is selected as a candidate.

• If its Ref bit is at zero, the selection is done.

• If not, the Ref bit of the candidate frame is reset, the frame is inserted again in the FIFO, and the process proceeds with the next frame.

• The process ends when a frame with the Ref bit at zero is found.

Note that such a frame is always found.

Clock algorithm

The clock policy is an improvement of the second chance algorithm, avoiding the removal and reinsertion of elements in the FIFO.

The list is transformed into a circular one and a pointer signals the oldest element.

• The action of removal followed by reinsertion corresponds to a pointer advance.

On-page replacement:

• While the Ref bit of a frame is non-zero, that bit is reset and the pointer advances to the next frame.

• The first frame with the Ref bit at zero is chosen for replacement.

• After replacement, the pointer is placed pointing to the next element.