Understand the principle of page replacement algorithm through code examples

Page replacement algorithm: The essence is to make limited memory able to satisfy wireless processes.

First explain the process of handling page faults:

The paging hardware notices that the invalid bit is set when translating the address through the page tables, and thus traps the operating system. This trap is caused by the operating system's failure to bring the required page into memory.

Handling page faults:

1. Check the internal table of this process to determine whether the reference is a valid memory access (it can be understood that this memory can be used by the current process). If it is invalid, terminate the process directly; if it is valid but the page has not been loaded into the memory, load the page into the memory.

2. Then find an idle frame from the idle frame list.

3. Schedule the disk to read the memory required by the process into the page frame.

4. After the disk read is completed, modify the page table so that the free frame corresponds to the page number. And modify the page table valid-invalid bit to valid.

Note some flags in the page table:

Modification bit: If the effective bit is 1, it means that it has been modified, so the memory needs to be written to the disk when replacing the page; if it is 0, it means that it has not been modified, so the page replacement algorithm is used to release it directly

Protection bit: can be marked as read-only, write.

Valid-invalid bit: i: indicates that the logical page number does not correspond to the physical page frame, V indicates that there is a corresponding physical page frame

Page replacement algorithm:

FIFO: Algorithm

The operating system always replaces the page that has stayed in memory the longest. A pointer can be used to point to this location (the overhead is very small, and a queue can be used to implement it. Every time a page fault occurs, the last page is removed and a new page is added to the head of the queue. If no page fault occurs, there is no need to operate the queue)

LRU algorithm: The operating system always replaces the page that has not been used in the longest time in the memory: We can use a linked list to implement this algorithm. The head of the table indicates the most recently used page, and the tail of the table indicates the page that has not been used for the longest time. Every time, regardless of whether a page fault occurs, the linked list needs to be checked from the addition, deletion, modification, and check to ensure that each linked list is what we need (the overhead is too high)

Approximate LRU algorithm: We add a reference bit clock in the page table. When the clock is 1, it cannot be moved out. When the clock is 0, it indicates that it can be removed.

procedure t: {
  Pointer p: points to the current page p = 0; // points to the initial position boolean: flag bit clock
  The circular linked list of all pages contained in the process: linklist //When the process is running, the linked list exists, and when the process ends, the linked list disappears while (process running) {
    
    if(p.clock == 1){
      p.clock = 0;
      p++; // pointer points to the next }
    if(p.clock == 0){
      Delete the page pointed to by p and add a new page at p;
      p.clock = 1;
      p++;
    }
  }
}

Approximate LRU enhanced algorithm: Combine the modification bit and the reference bit as the replacement condition: when (modification bit, reference bit) = (0, 0), it indicates that it can be replaced

procedure t: {
  Pointer p: points to the current page p = 0; // points to the initial position boolean: flag bit clock
  boolean : Modify bit m
  The circular linked list of all pages contained in the process: linklist //When the process is running, the linked list exists, and when the process ends, the linked list disappears while (process running) {
    
  
    if(p.(clock,m) == (0,0)){
      
      Delete the page pointed to by p and add a new page at p;
      p.(clock,m) = (1,0);
      p++;
    }
    if(p.(clock,m) == (0,1)){
      
      
      p.(clock,m) = (0,0);
      p++;
    }
    if(p.(clock,m) == (1,0)){
      
      
      p.(clock,m) = (0,0);
      p++;
    }
    if(p.(clock,m) == (1,1)){
      
      p.(clock,m) = (0,1);
      p++;
    }
    if (modify page) {
      p.(clock,m) = (1,1);
      p++
    }
    if (read page) {
      p.(clock,m) = (1,0);
      p++;
    }
  }
}

Page buffer algorithm: The operation system reserves a pool of free frames.

When a page fault occurs, the required page reads the free frame and puts the replaced victim frame into the buffer pool. During the paging idle period, the contents of the victim frame in the buffer pool are written to the disk (if the modification bit on the page table is 1) (reducing the process of direct disk access during paging of the operating system and improving paging efficiency).

The second method is to write the contents of the sacrifice frame to disk, but do not release the contents of the frame, because the process may call the previous page, so that the frame in the buffer pool is directly written to the memory, reducing (the operation of reading data from disk).

The above are all local page replacement algorithms, which are page replacement operations performed within a single process. However, different processes can be executed in parallel during the operation of the operating system, so the replacement of pages is not limited to a single process.

Next we learn the global replacement algorithm: we specify a working set and a resident set. The working set indicates the Δ pages that the current program needs to access, and the resident set indicates the pages that the operating system is using.

Working set: WS(Δ, t) = {} The working set is constantly moving, and the operating system replaces pages that are not in the working set

Dynamic working set page replacement algorithm: As shown in the figure below, we set a threshold windows size = 2. We use the difference between two page fault interruptions (indicating how many times there were no interruptions between the two interruptions) to compare with the threshold. If it is larger than the threshold, the pages of the current working set will no longer be swapped out and the size of the working set will be reset. If it is smaller than the threshold, the missing pages will be swapped into the working set and the size of the working set will be reset.

The above is the full content of this article. I hope it will be helpful for everyone’s study. I also hope that everyone will support 123WORDPRESS.COM.