Page replacement

Introduction

In a paging (or combination of segmentation and paging) architecture, memory is partitioned into frames, each the same size as a page.

• A frame may be either free or occupied (containing a page).

A page in memory may be:

• locked – if it can not be removed from memory (kernel, buffer cache, memory-mapped file).

• unlocked – if it can be removed from memory.

If no free frame is available, an occupied one may need to be released.

• This is the purpose of page replacement.

Page replacement only applies to unlocked pages.

Lists of free and occupied frames

Free frames are organized in a list – list of free frames.

Occupied frames, associated with unlocked pages, are also organized in a list – list of occupied frames.

How the list of occupied frames is organized depends on the page replacement policy.

Action on page fault

On page fault, if the list of free frames is empty, an occupied frame must be selected for replacement.

Alternatively, the system can promote page replacement as to maintain the list of free frames always with some elements.

• This allows to load the faulty page and free a busy frame at the same time.

The question is: which frame should be selected for replacement?

An optimal policy selects a replacement page for which the time to the next reference is the longest.

• Unless we have a Crystal-Ball, it is impossible to implement.

• But, useful as a benchmark.

Covered algorithms:

• Least Recently Used (LRU)

• Not Recently Used (NRU)

• First In First Out (FIFO)

• Second chance

• Clock