Diagram: Page replacement algorithm

[[398509]]

This article is reprinted from the WeChat public account "Jingyu", the author is Jingyu. Please contact Jingyu public account to reprint this article.

Page Replacement Algorithm

Function: When a page fault occurs and a new page needs to be loaded but the memory is full, select which physical page in the memory is replaced.

Goal: Reduce the number of page swaps (i.e., page faults) as much as possible. Specifically, swap out pages that will no longer be used in the future or are used less frequently in the short term. This can usually only be predicted based on past statistical data under the guidance of local principles.

Optimal page replacement algorithm

The basic idea is: when a page fault occurs, for each logical page stored in the memory, calculate how long it will take to wait before the next access, and select the one with the longest waiting time as the page to be replaced.

This is just an ideal situation and cannot be achieved in practice because the operating system cannot know how long each page will wait before being accessed again.

It can be used as a basis for performance evaluation of other algorithms (run a program on a simulator and record each page access, and use the optimal algorithm in the second run).

In simple terms, the optimal page replacement algorithm is to replace pages that will not be needed in the longest time in the future.

Assume that the size of the page frame is 4, and the sequence of requested pages is: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2. How many page faults will occur using the optimal page replacement algorithm?

Initially, all page slots are empty, so the requested pages 7 0 1 2 are assigned to empty page slots, resulting in 4 page fault exceptions.

Next, when page 0 is requested, it is found to already exist in the page frame, resulting in 0 page fault exceptions;

When page 3 is requested, page 7 is replaced by 3 because it will not be accessed for the longest time in the future, and a page fault exception occurs.

Page 0 hits, 0 page exceptions;

The requested page 4 does not exist in the page frame, so page 1 is replaced, resulting in 1 page fault exception;

For the subsequent requested page sequences 2, 3, 0, 3, 2, all are hits, so there is no page fault exception.

Therefore, a total of 6 page fault exceptions occurred, which is the Miss state in the figure, where Hit means hit, and no page fault exception occurred.

Simulate and implement an optimal page replacement algorithm:

Input: Page frame number fn = 3

page pg[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};

Output: hits = 11 page faults = 9

Input: Page frame number fn = 4 Page pg[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};

Output: hits = 7 page faults = 6

We take the page frame number 4 and the request sequence {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2} as an example.

First we create an empty array fr to simulate a page frame:

Request page 7, and find that it is not in array fr and the size of array fr is fr.size() < fn page frame size, then directly insert the requested page 7 into array fr:

Requesting pages {0,1,2} is similar to requesting page 7, so add them to the array in turn:

Next, page 0 is requested, and the array fr is traversed. If page 0 is found to be already in the array, the hit count hit is increased by 1.

Request page 3, traverse array fr, and find that it is not in the array and the array is full (fr.size == fn), then you need to find the page to be replaced, and then choose to replace the page that will not be needed in the future. The page that will not be needed in the future can be represented by the subscript of the page array pg[].

Traverse the array fr[] and combine it with the request page array pg[] to find the page that will not be needed in the longest time in the future.

fr[0] = 7, we start from page 3 and search backwards in the array pg[] for page 7, and find that it does not exist at all, which means that page 7 is the page that will not be needed for the longest time in the future. So page 3 replaces page 7.

Visit page 0 again, if it exists, skip it;

Visit page 4 and find that it is not in the page frame array fr, so replace page 1 which will not be needed for the longest time in the future:

After that, the pages {2, 3, 0, 3, 2} were all hits, for a total of 6 hits.

Reference Implementation

 #include <bits/stdc++.h>
 using namespace std; 
 
 // Used to check whether the page key currently being accessed exists in the page frame  
 bool search( int   key , vector< int >& fr)
 {
 for ( int i = 0; i < fr. size (); i++)
 if (fr[i] == key )
 return   true ;
 return   false ;
 } 
 
 // Used to predict the future
 int predict( int pg[], vector< int >& fr, int pn, int   index )
 {
 // Store the index of the page that will be used most recently in the future
 int res = -1, farthest = index ;
 for ( int i = 0; i < fr. size (); i++) {
 int j;
 for (j = index ; j < pn; j++) {
           if (fr[i] == pg[j]) {
                if (j > farthest) {
                     farthest = j;
 res = i;
 }
 break;
 }
 } 
 
 // If a page is never referenced in the future, return it.
 if (j == pn)
 return i;
 }
 // If all pages in fr have not appeared in the future, then returning any of them, we return 0. Otherwise we return res.
 return (res == -1) ? 0 : res;
 } 
 
 /**
 * pg[] request page sequence
 * pn Request page number
 * fn Page Frames
 */
 .
 void optimalPage( int pg[], int pn, int fn)
 {
 // Create an array for the given number of frames and initialize it to empty.
 vector< int > fr; 
 
 // Iterate over the page reference array and check for misses and hits.
 int hit = 0;
 for ( int i = 0; i < pn; i++) {
 // Hit the page in memory: HIT
      if (search(pg[i], fr)) {
 hit++;
 continue ;
 }
 // The page does not exist in memory: MISS
 // If there is available space in the page frame, simply add the missing page to it.
 if ( fr.size () < fn) {
           fr.push_back(pg[i]);
 }
 else { // Find the page to replace
 int j = predict(pg, fr, pn, i + 1);
 fr[j] = pg[i];
 }
 }
 cout << "Number of hits = " << hit << endl;
 cout << "Number of misses = " << pn - hit << endl;
 } 
 
 int main()
 {
 int pg[] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 };
 int pn = sizeof(pg) / sizeof(pg[0]);
 int fn = 4;
 optimalPage(pg, pn, fn);
 return 0;
 }

The search function can be replaced by hash or binary search, etc. The most critical one is the predict() function, which is used to find pages that will not be used in the longest time in the future. In fact, it is two layers of nested for loops.

First-in-first-out algorithm

FIFO (First In, First Out) is a first-in, first-out algorithm.

The basic idea is to select the page that has been in memory the longest and eliminate it. Specifically, the system maintains a linked list that records all logical pages in memory. From the order of the linked list, the page at the head of the chain has the longest residence time, and the page at the end of the chain has the shortest residence time. When a page fault occurs, the page at the head of the chain is eliminated and the new page is added to the end of the linked list.

The performance is poor, the page called out may be a frequently accessed page, and the Belady phenomenon occurs. The FIFO algorithm is rarely used alone.

Assume that the size of the page frame is 4, and the sequence of requested pages is: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2. How many page fault exceptions will occur using the FIFO algorithm?

As shown in the figure above, FIFO, first-in-first-out, has a queue-like feature.

For the requested pages 7, 0, 1, and 2, 4 page faults occur, which are the allocation pages for them respectively;

When accessing page 0, it hits;

When accessing page 3, a page fault exception occurs. At this time, page 7 at the head of the queue will be eliminated, and page 3 will be inserted to the end of the queue. That is, the page that has resided in the memory the longest is selected and eliminated.

Page 0 hits;

When accessing page 4, a page fault exception occurs, and page 0 is eliminated;

When accessing pages 2 and 3, both hits;

When accessing page 0, a page fault occurs, page 1 is eliminated, and page 0 is inserted;

The last visited pages 3 and 2 were both hits.

A total of 7 page fault exceptions occurred.

Least Recently Used Algorithm

For more information about the least recently used page replacement algorithm, please refer to: Least Recently Used LRU Algorithm

Clock Page Replacement Algorithm

Clock page replacement algorithm, an approximation of LRU, an improvement on FIFO;

Basic idea:

• The access bit at the top of the page table is used. When a page is loaded into memory, the bit is initialized to 0. Then if the page is accessed (read or write), the bit is set to 1.
• Organize the pages into a circular linked list (similar to a clock face), with the pointer pointing to the oldest page (the page that came in first);
• When a page fault occurs, check the oldest page pointed to by the pointer. If its access bit is 0, it will be eliminated immediately. If the access bit is 1, the position will be set to 0, and then the pointer will move down one grid. This process will continue until the eliminated page is found, and then the pointer will be moved to its next grid.

Assume that the size of the page frame is 4, and the sequence of requested pages is: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2. How many page fault exceptions will occur using the clock page replacement algorithm?

Initially, the page frame is empty, like a circular linked list as shown in the figure below. Doesn’t it look like a clock?

Requesting page 7 generates a page fault interrupt, so it is loaded into memory and the access bit of the page is initialized to 0:

Visit pages 0, 1, and 2 in sequence, similar to the previous method:

Next, a request is made for page 0. If it is already in memory, the hardware will set the access bit to 1 and move the pointer down:

When page 3 is requested, a page fault occurs. At this time, the access bit of page 7 pointed to by the pointer is 0, so it is immediately eliminated and replaced by page 3, whose access bit is 1:

Request page 0, which is already in memory, and the hardware sets its access bit to 1, the same as in the previous figure, no change;

Request page 4, a page fault occurs, first set the access position of page 3 to 0, the access position of page 0 to 0, move the pointer down, and find that the access bit of page 1 is 0, then eliminate page 1 and replace it with page 4, access position 1 and move the pointer down:

Request page 2, which is already in memory, and the hardware places it at access position 1:

Request page 3, set the access bit of page 3 to 1, and move the pointer down:

Request page 0, set the access position of page 0 to 1, and move the pointer down:

The total number of page faults is 5.

The least commonly used algorithm LFU

Basic idea: When a page fault occurs, select the page with the least number of accesses and eliminate it.

Implementation method: Set an access counter for each page. Whenever a page is accessed, the access counter of the page is increased by 1. When a page fault occurs, the page with the smallest count value is eliminated. If all pages have the same frequency, the LRU method is adopted for the page and the page is deleted.

The difference between LRU and LFU: LRU examines how long it has not been accessed, the shorter the time, the better; while LFU considers the number of visits or frequency, the more visits, the better.

This article is reprinted from the WeChat public account "Jingyu", which can be followed through the following QR code. To reprint this article, please contact Jingyu public account.