Paging is a memory-management scheme which allows the physical address of a process to be non-contiguous. The concept of paging is used to remove the problem of fragmentation. Here we are able to allocate physical memory to the process in a non-contiguous manner wherever memory is available. Paging avoids external fragmentation and the need for compaction. Paging is done by breaking the physical memory into fixed size blocks called frames and breaking the logical memory into blocks of same size called pages. When a process is being executed, the corresponding pages are fetched and loaded into the available memory frames.

Page Replacement Algorithm:

Page replacement algorithms decide which memory pages to swap out, write to disk when a page of memory needs to be allocated.When a fault occurs, the OS loads the faulted page from disk into a page of memory. The goal of the replacement algorithm is to reduce the fault rate by selecting the best victim page to remove.

A page replacement algorithm is said to satisfy the inclusion property or is called a stack algorithm if the set of pages in a k-frame memory is always a subset of the pages in a (k+1) frame memory.

Following are the page replacement algorithm:

1. First in First out (FIFO)

2. Optimal

3. Least Recently used(LRU)

First in First out(FIFO):

The simplest page-replacement algorithm is a first-in, first-out (FIFO) algorithm.

A FIFO replacement algorithm associates with each page the time when that page was brought into memory.

When a page must be replaced, the oldest page is chosen.

For.eg:

On the one hand, the page replaced may be an initialization module that was used a long time ago and is no longer needed.

On the other hand, it could contain a heavily used variable that was initialized early and is in constant use.

For.eg: Page frame size is 4.

page frame sequences : 2, 3, 4, 2, 1, 3, 7, 5, 4, 3, 2, 3, 1

FIFO: In FIFO page replacement, when a page is needed to be replaced, we select the oldest page.

Page hit: If the file is already present, then it is a Page Hit (indicated by circles in the diagram)

Page Miss: If an entry is not found, then it is a Page miss

No. of page hit=4

No. of page miss=9

Advantages:

• Simple to understand & easy to operate.

• Better for long process

• No starvation

• Maintain a Linked list of all pages in memory.

Disadvantages:

• This scheduling method is Non-Pre-emptive

• Throughput is not emphasized

Optimal page replacement algorithm:

Optimal page replacement algorithm is considered the best possible page replacement policy in a virtual memory theoretically but is difficult to implement. According to the optimal page replacement algorithm, the page in the main memory, which will not be referred to for the longest time is swapped out from the main memory to create room for the requested page.

Here, when a page replacement is needed, it looks ahead in the input queue for the page frame which will be referenced only after a long time. The page with the longest reference is swapped.

For.eg: Page frame size is 4.

page frame sequences : 2, 3, 4, 2, 1, 3, 7, 5, 4, 3, 2, 3, 1

No. of page hit=6

No. of page miss=7

Advantages:

• It reduces the total page replacement timings

• Never suffers from Belady’s anomaly.

• It improves the system performance by reducing overhead for number of page faults and swapping pages in and out, when a page fault occurs.

Disadvantages:

• Difficult to implement

• It needs forecast i.e. Future knowledge.

• It becomes very difficult for an operating system to calculate after what interval a page is to be referred to.

Least Recently Used page replacement:

In this algorithm, the page that has not been used for the longest period of time has to be replaced.LRU is implementable because it works on past knowledge of pages

If there is page A in memory that has been referenced 20 million instructions in past and page B has been referenced 10 million instructions in past, then choose page A for replacement.

There are two ways of finding LRU page frame:

Maintain a List:

Every time a page is referenced, it is moved to the head of the list. When a page fault occurs the LRU frame is at the tail of the list.

Maintain a Counter or Timer:

On every reference store the counter on a table entry associated with the referenced frame. On a page fault, Search through the table for the smallest entry.

This method uses the recent past as an approximation of near future. We replace the page which has not been referenced for a long time in the past.

For.eg: Page frame size is 4.

page frame sequences : 2, 3, 4, 2, 1, 3, 7, 5, 4, 3, 2, 3, 1

No. of page hit=4

No. of page miss=9

Advantages:

• It is amenable to full statistical analysis.

• Never suffers from Belady’s anomaly

Disadvantages:

• Implementation is difficult

• Require substantial hardware assistance.