Write note on: Demand paging and various page replacement policies.

141views

written 7.9 years ago by

Demand paging:

For loading a program in memory, the traditional method goes by loading the entire program in memory. However, it may lead to programs or lines of codes with at the end go untouched.
To overcome this drawback, we use the concept of demand paging where in only the pages needed currently for execution are brought in to memory as and when needed.
The virtual memory system is commonly implemented using the concept of demand paging.
Here we use a lazy swapper to swap the pages from memory. An important feature of a lazy swapper is that it never swaps until that page is needed.( But with reference to paging we would be using the term pager)
When a process is to be swapped in, the pager guesses which pages will be used before the process is swapped out again
The pager then brings only those pages into memory
The valid-invalid bit scheme is used to determine if the page is on the disk
- When bit set to “valid”$→$The page is legal and in memory
- When bit set to “invalid”$→$The page is not in its address specified or it is currently on the disk
A page-table entry is made based in this for every pages.
Access to a page marked invalid in the page-table entry causes a Page Fault. It results in a trap to the operating system. After this the OS swaps page into frame via scheduled disk operation and replacement algorithms.

Page replacement policies:

Page replacement policies are needed because in paging environment, the page frames need to swapped. Various policies are used so that we achieve the very less page fault.

The various page replacement algorithms are as follows:

1) First In First Out(FIFO)

The FIFO algorithm associates with each page the time that it was brought into memory.
When a page is needed to be replaced, we select the oldest page.
A queue is used to main the pages in the memory.
The page present at the head position is removed and the new page is inserted at the tail position.
It is a easy to understand algorithm
However, performance wise it’s not good. The folder files can be the initialisation files which may be required throughout the CPU cycle.
It suffers from Beladys Anomaly which says that the page fault increases with the reduction in page frames.

2) Optimal page-replacement algorithm:

This algorithm is an result of discovery by Beladys anomaly
It has the lowest page fault rate
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.
However this algorithm is difficult to be implemented because there is no provision in the OS to know the future memory references.
However, we still do use this algorithm to compare the efficiency of another algorithm as compared to the Optimal algorithm.

3) Least-recently used Algorithm:

This algorithm too works on the inspiration of the optimal algorithm.
Except that it uses the recent past as an approximation of near future.
We do this by believing that a page which has not been referenced for a long time in the past may not be referenced for a long time in the future either.
We then replace the page which has not been used for the longest period of time.

4) LRU-Approximation Page replacement:

It is a hardware based approach. Many systems provide support for LRU page replacement by providing a reference bit.
These Reference bits are associated with each entry in the page table
Initially all bits are set to 0. Now, when the page is referenced its set to 1 by the hardware mechanism.
This is the basis for approximation of LRU replacement algorithm

5) Counting Algorithms:

Here we have a counter of the number of references that have been made to each page
Based on it we come up with two schemes:
- Least Frequently Used (LFU) Algorithm: It replaces the page with the smallest count. The reason for this is that an actively used page should have a large reference count.
- Most Frequently Used(MFU) Algorithm: it is based on the argument that the page with the smallest count was probably just brought in and has yet to be used

ADD COMMENT EDIT