Counting Based Page replacement, Page-Buffering Algorithms and Applications and Page replacement

Counting Based Page replacement:

There are several algorithms based on counting the number of references that have been made to a given page, such as:

o    . Least Frequently Used, LFU: Replace the page with the lowest reference count. A problem can occur if a page is used frequently initially and then not used any more, as the reference count remains high. A solution to this problem is to right-shift the counters periodically, yielding a time-decaying average reference count

o    Most Frequently Used, MFU: Replace the page with the highest reference count. The logic behind this idea is that pages that have already been referenced a lot have been in the system a long time, and we are probably done with them, whereas pages referenced only a few times have only recently been loaded, and we still need them.

In general counting-based algorithms are not commonly used, as their implementation is expensive and they do not approximate OPT well.

Page-Buffering Algorithms:

There are number of page buffering algorithms often used in addition to a specific page replacement algorithm.

For example, maintain a certain minimum number of free frames at all times. When a page-fault occurs, go ahead and allocate one of the free frames from the free list first, to get the requesting process up and running again as quickly as possible, and then select a victim page to write to disk and free up a frame as a second step.

Keep a list of modified pages, and when the I/O system is otherwise idle, have it write these pages out to disk, and then clear the modify bits, thereby increasing the chance of finding a "clean" page for the next potential victim.

Keep a pool of free frames, but remember what page was in it before it was made free. Since the data in the page is not actually cleared out when the page is freed, it can be made an active page again without having to load in any new data from disk. This is useful when an algorithm mistakenly replaces a page that in fact is needed again soon.

Applications and Page replacement:

·         Some applications ( most notably database programs ) understand their data accessing and caching needs better than the general-purpose OS, and should therefore be given reign to do their own memory management.

·         Sometimes such programs are given a raw disk partition to work with, containing raw data blocks and no file system structure. It is then up to the application to use this disk partition as extended memory or for whatever other reasons it sees fit.

LRU-Approximation Page Replacement

LRU-Approximation Page Replacement

i. Additional reference bits algorithm:

The ordering information can be gained by recording the reference bits at regular intervals:  Storing the most recent 8 reference bits for each page in an 8-bit byte in the page table entry, which is interpreted as an unsigned integer.

At periodic intervals ( clock interrupts ), the OS takes over, and right-shifts each of the reference bytes by one bit.

The high-order ( leftmost ) bit is then filled in with the current value of the reference bit, and the reference bits are cleared.

At any given time, the page with the smallest value for the reference byte is the LRU page.

Ex: 

00000000 indicates page has not been used for eight time periods.

11000100 indicate that page had referenced recently.

If the eight bit are interpreted as unsigned integers, the page with lowest number is the page to be replaced.

ii. Second chance algorithm:

The basic algorithm of second chance replacement is a FIFO replacement algorithm. When a page has been selected, the reference bit is inspected. If the value is 0, the page is replaced but if the reference bit is set to 1, the page is given second chance and move on to select the next FIFO page.

When a page gets a second chance, its reference bit is cleared and its arrival time is reset to the current time. Thus a page that is given a second chance will not be replaced until all other pages have been replaced.

One way to implement the second chance algorithm is a circular queue. Second chance replacement degenerates to FIFO replacement if bits of all pages are set.

iii. Enhanced second-chance algorithm:

The enhanced second chance algorithm looks at the reference bit and the modify bit ( dirty bit ) as an ordered page, and classifies pages into one of four classes:

1. ( 0, 0 ) - Neither recently used nor modified.
2. ( 0, 1 ) - Not recently used, but modified.
3. ( 1, 0 ) - Recently used, but clean.
4. ( 1, 1 ) - Recently used and modified.

This algorithm searches the page table in a circular fashion ( in as many as four passes ), looking for the first page it can find in the lowest numbered category. I.e. it first makes a pass looking for a ( 0, 0 ), and then if it can't find one, it makes another pass looking for a ( 0, 1 ), etc.

The main difference between this algorithm and the previous one is the preference for replacing clean pages if possible.

LRU Page replacement

Least Recently Used (LRU) page replacement algorithm

The idea behind LRU page replacement is to use recent past as an approximation of the near future. Replace the page that has not been used for the longest period of time.

LRU is considered a good replacement policy, and is often used. The problem is how exactly to implement it. There are two simple approaches commonly used:

1. Counters. Every memory access increments a counter, and the current value of this counter is stored in the page table entry for that page. Then finding the LRU page involves simple searching the table for the page with the smallest counter value. Note that overflowing of the counter must be considered.
2. Stack. Another approach is to use a stack, and whenever a page is accessed, pull that page from the middle of the stack and place it on the top. The LRU page will always be at the bottom of the stack. Because this requires removing objects from the middle of the stack, a doubly linked list is the recommended data structure.

Note that both implementations of LRU require hardware support, either for incrementing the counter or for managing the stack, as these operations must be performed for every memory access.

Neither LRU or OPT exhibit Belady's anomaly. Both belong to a class of page-replacement algorithms called stack algorithms, which can never exhibit Belady's anomaly. 

A stack algorithm is one in which the pages kept in memory for a frame set of size N will always be a subset of the pages kept for a frame size of N + 1.

Optimal Page Replacement

Optimal Page Replacement

Result of Belady’s anmoly was the search for an optimal page replacement algorithm, which has the lowest page fault rate of all algorithms and never suffer from Belady’s anamoly.

This algorithm is simple: "Replace the page that will not be used for the longest time in the future."

Optimal replacement is better than FIFO algorithm. Unfortunately the optimal page replacement algorithm is difficult to implement because it requires future knowledge of the reference string. The optimal page replacement algorithm is used mainly for comparison studies.

First In First Out Page replacement

FIFO page replacement

First In First Out page replacement is the simplest page replacement. this algorithm associates with each page the time when that page was brought into memory. When a page must be replace, the oldest page is chosen.

Although FIFO is simple and easy, it is not always optimal, or even efficient. An interesting effect that can occur with FIFO is Belady's anomaly, in which increasing the number of frames available can actually increase the number of page faults that occur. Consider, for example, the following reference string ( 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ). The number of page faults for four frames is 10 and the number of page faults for three frames is 9.

Basic page replacement

Basic page replacement

If no frame is fee, find page that is not currently being used and free it. Frame is freed by writing its contents to swap space and changing the page table to indicate that the page is no longer in memory. The page fault service routine is modified to include page replacement.

1. Find the location of the desired page on the disk, either in swap space or in the file system.
2. Find a free frame:
1. If there is a free frame, use it.
2. If there is no free frame, use a page-replacement algorithm to select an existing frame to be replaced, known as the victim frame.
3. Write the victim frame to disk. Change all related page tables to indicate that this page is no longer in memory.
3. Read in the desired page and store it in the frame. Adjust all related page and frame tables to indicate the change.
4. Restart the process that was waiting for this page.

A modify bit or dirty bit is used to reduce the overhead of disk write. A dirty bit of each page indicate whether or not it has been changed since it was last loaded in from disk. If the dirty bit has not been set, then the page is unchanged, and does not need to be written out to disk. Otherwise the page write is required. It should come as no surprise that many page replacement strategies specifically look for pages that do not have their dirty bit set, and preferentially select clean pages as victim pages.

Page replacement is basic to demand paging. There are two major requirements to implement a successful demand paging system: developing a frame-allocation algorithm and a page-replacement algorithm. . The former decides how many frames are allocated to each process ( and to other needs ), and the latter deals with how to select a page for replacement when there are no free frames available.

The overall goal in selecting and tuning these algorithms is to generate the fewest number of overall page faults. 

Algorithms are evaluated using a given string of memory accesses known as a reference string, and computing the number of page faults. To determine the number of page faults for a particular reference string and page replacement algorithm, number of page frames available is also needed. As the number of page frames available increases the number of page faults decreases.

Page Replacement

Page Replacement 

While a user process is executing, a page fault occurs. the operating system determines where the desired page is residing on the disk. If there are no free frames on the free frame list, the operating system has several options.

            1. It could terminate the user process; this option is not best choice.

2. Swap some process out of memory completely, freeing up its page frames.

3. Find some page in memory that isn't being used right now, and swap that page only out to disk, freeing up a frame that can be allocated to the process requesting it. This is known as page replacement, and is the most common solution.

There are many different algorithms for page replacement:

a. Basic page replacement

b. FIFO page replacement

c. Optimal page replacement

d. LRU page replacement

e. LRU approximation page replacement

f. Counting based page replacement

g. Page- buffering algorithms