Page Replacement Algorithms

In virtual memory management, when a job is running, the page being accessed may not be in the main memory. At this point, the page needs to be loaded from external memory (such as disk) into the main memory. If the main memory is full, the system needs to select a page that is already in memory and call it out to make room for the new page. This process is called "page replacement". The algorithm that selects the page to be replaced is the page replacement algorithm.

Jitter phenomenon

Jitter (or thrashing) refers to when pages are frequently swapped between main memory and external memory, causing the system to spend most of its time on page scheduling, while the actual computing work is very little, and the system performance drops sharply. This is usually because the page replacement algorithm is not efficient enough or the allocated memory is unreasonable.

A good page replacement algorithm should minimize jitter, ensure that the number of page scheduling is small, and the system runs smoothly.

Page direction

Page direction refers to the order in which pages are accessed when the program is running. When analyzing page replacement, we usually only care about the order in which pages are accessed, not the specific memory addresses. By simplifying the page direction, it can help evaluate the efficiency of the page replacement algorithm.

Example:

Suppose a program's address sequence is:

0100, 0432, 0101, 0612, 0102, 0103, 0104,
0101, 0611, 0102, 0103, 0104, 0101, 0610,
0102, 0103, 0104, 0101, 0609, 0102, 0105

Suppose the page size is 100 bytes, then the page direction can be simplified to

1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

**How to achieve it? **

To simplify the page direction, first, each address needs to be converted into a corresponding page number according to the given address sequence and page size. Assuming that each page size is 100 bytes, the address sequence gives the address value in bytes. Next, by "dividing" each address by 100 (that is, taking the page number), the corresponding page number can be obtained. The page direction is the sequence of these page numbers.

Address sequence:

0100, 0432, 0101, 0612, 0102, 0103, 0104,
0101, 0611, 0102, 0103, 0104, 0101, 0610,
0102, 0103, 0104, 0101, 0609, 0102, 0105

Step 1: Calculate the page number of each address

We know that the size of each page is 100 bytes. Therefore, we can determine the page number of each address by dividing it by 100. Every time we access an address, we only care about its page number, not the specific address.

0100 / 100 = 1 (page 1)
0432 / 100 = 4 (page 4)
0101 / 100 = 1 (page 1)
0612 / 100 = 6 (page 6)
0102 / 100 = 1 (page 1)
0103 / 100 = 1 (page 1)
0104 / 100 = 1 (page 1)
0101 / 100 = 1 (page 1)
0611 / 100 = 6 (page 6)
0102 / 100 = 1 (page 1)
0103 / 100 = 1 (page 1)
0104 / 100 = 1 (page number 1)
0101 / 100 = 1 (page number 1)
0610 / 100 = 6 (page number 6)
0102 / 100 = 1 (page number 1)
0103 / 100 = 1 (page number 1)
0104 / 100 = 1 (page number 1)
0101 / 100 = 1 (page number 1)
0609 / 100 = 6 (page number 6)
0102 / 100 = 1 (page number 1)
0105 / 100 = 1 (page number 1)

Step 2: Simplify the page path

List the page number corresponding to each address and simplify the pages that are repeatedly accessed. When accessing the same page consecutively, we only keep the first access.

According to the above calculation, the original page number sequence is:

1, 4, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1

After removing duplicate accesses, the simplified page trend sequence is:

1, 4, 6, 1, 6, 1, 6, 1

This means that in the page access sequence, pages 1 and 6 are frequently accessed, while pages 4 and 7 only appear at certain specific times.

Optimal Page Replacement Algorithm

Optimal Page Replacement Algorithm is an idealized algorithm that assumes that future page accesses can be predicted. According to this algorithm, when a page needs to be replaced, the page that has not been accessed the longest in the future should be selected for replacement.

Implementation: Pre-eliminate pages that will not be accessed in the longest time in the future.
Advantage: Can minimize page miss rate.
Disadvantage: Cannot be implemented because the future page access sequence cannot be predicted. Usually used as a performance benchmark for other algorithms.

First-In-First-Out Page Replacement Algorithm

FIFO (First-In-First-Out) is the simplest page replacement algorithm. It assumes that the page that first enters the main memory is the least likely to be accessed in the future, so the page that enters the memory earliest is selected for replacement.

Implementation: Arrange the pages into a queue in the order they enter the main memory, and replace the page at the head of the queue.
Advantage: Simple implementation.
Disadvantage: Cannot consider the access pattern of the program, so it may lead to a high page fault interrupt rate and the Belady phenomenon (that is, increasing the number of memory pages will increase the number of page fault interrupts).

Least Recently Used Page Replacement Algorithm

LRU (Least Recently Used) page replacement algorithm selects the page that has not been accessed for the longest time in the recent period for replacement.

Implementation: By recording the access time of the page (usually implemented through reference bits or stacks), select the page that has not been accessed for the longest time for elimination.
Advantage: It complies with the principle of locality of the program and can effectively reduce page misses.
Disadvantage: It is necessary to maintain the access time, which may lead to high computational overhead.

Clock Page Replacement Algorithm

The clock page replacement algorithm is an approximate algorithm of LRU. It uses a circular queue and a pointer (clock pointer) to simulate the least recently used situation, avoiding the complexity of the LRU algorithm.

Implementation: Add a reference bit to each page, and the pointer points to the current page. When the page is accessed, the reference position is 1; when a page fault occurs, the pointer checks the pages one by one. If the reference bit of a page is 0, the page is eliminated; if the reference bit is 1, the reference bit is cleared and the pointer is moved to continue checking the next page.
Advantage: The implementation is relatively simple and efficient.
Disadvantage: It may not be possible to perfectly simulate the behavior of LRU.

Least Frequently Used Page Replacement Algorithm

LFU (Least Frequently Used) page replacement algorithm selects the page with the least number of accesses in the past period of time for replacement.

Implementation: Maintain a counter for each page. Each time the page is accessed, the counter is increased by 1; when a page fault occurs, the page with the smallest counter is selected for replacement.
Advantage: It can better keep frequently accessed pages in memory.
Disadvantage: The implementation is complex and may not adapt to the dynamic access mode of the program.

--

Page Fault Rate Analysis

Page Fault Rate is an important indicator to measure the efficiency of the page replacement algorithm. It indicates the proportion of the number of page faults to the total number of accesses within a certain period of time. One of the goals of optimizing the page replacement algorithm is to reduce the page fault rate.

Factors affecting the page fault rate:

Number of main memory blocks allocated to the job: The more memory is allocated, the lower the page fault rate, and vice versa.
Page size: Larger pages will cause more data to be dispatched in and out of memory each time a page fault occurs, thus affecting the page fault rate.
Programming method: The access pattern of the program (such as sequential access, locality, etc.) will affect the access frequency of the page, thus affecting the page fault rate.
Page scheduling algorithm: Different page replacement algorithms have different effects on the page fault rate.

Page fault rate formula:

\[ f = \frac{F}{A} \]

Where:

\( f \) is the page fault rate.
\( F \) is the number of page faults.
\( A \) is the total number of page accesses.