Page Replacement Algorithms

1.What is Demand paging?

Virtual memory is commonly implemented by demand paging. In demand paging, the pager brings only those necessary pages into memory instead of swapping in a whole process. Thus it avoids reading into memory pages that will not be used anyway, decreasing the swap time and the amount of physical memory needed.

2.Define lazy swapper.

Rather than swapping the entire process into main memory, a lazy swapper is used. A lazy swapper never swaps a page into memory unless that page will be needed.

3.What is a pure demand paging?

When starting execution of a process with no pages in memory, the operating system sets the instruction pointer to the first instruction of the process, which is on a non-memory resident page, the process immediately faults for the page. After this page is brought into memory, the process continues to execute, faulting as necessary until every page that it needs is in memory. At that point, it can execute with no more faults.This schema is pure demand paging.

4.Define effective access time.

Let p be the probability of a page fault (0£p£1). The value of p is expected to be close to 0; that is, there will be only a few page faults. The effective access time is Effective access time = (1-p) * ma + p* page fault time.ma : memory-access time

5.Define secondary memory.

This memory holds those pages that are not present in main memory. The secondary memory is usually a high speed disk. It is known as the swap evice, and the section of the disk used for this purpose is known as swap space.

6.What is the basic approach of page replacement?

If no frame is free is available, find one that is not currently being used and free it. A frame can be freed by writing its contents to swap space, and changing the page table to indicate that the page is no longer in memory.Now the freed frame can be used to hold the page for which the process faulted.

7.What are the various page replacement algorithms used for page replacement?

•   FIFO page replacement

•   Optimal page replacement

•   LRU page replacement

•   LRU approximation page replacement

•   Counting based page replacement

•   Page buffering algorithm.

8.What are the major problems to implement demand paging?

The two major problems to implement demand paging is developing

a.   Frame allocation algorithm

b.  Page replacement algorithm

9.What is a reference string?

An algorithm is evaluated by running it on a particular string of memory references and computing the number of page faults. The string of memory reference is called a reference string.