Shulou(Shulou.com)06/01 Report--

When the process is running, if the page visited is not in memory and needs to be transferred, but there is no spare space in memory, it is necessary to transfer a page of program or data from memory and send it to the swap area of disk.

The algorithm for selecting the page to call up is called the page replacement algorithm. A good page replacement algorithm should have a low frequency of page changes, that is, pages that will not be visited in the future or will not be visited for a long time in the future should be called out first.

There are four rare permutation algorithms.

1. Best Permutation Algorithm (OPT)

Optimal (OPT) replacement algorithm selected by the deleted pages will never be used in the future, perhaps in the longest time no longer visited pages, so as to ensure that the lowest page missing rate. But because people cannot predict which of the thousands of pages in memory will not be visited for the longest time in the future, the algorithm cannot be completed.

The best permutation algorithm can be used to evaluate other algorithms. Suppose that the system allocates three physical blocks to a process, and consider that there are the following page number invocation strings:

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

When the process is running, the three pages 7, 0 and 1 are loaded into memory in sequence. When visiting page 2 in the process, there is a missing page infix. According to the best replacement algorithm, page 7, which needs to be transferred to the 18th visit, is selected to be eliminated. Then, when page 0 is visited, there is no missing page infix because it is already in memory. When visiting page 3, page 1 will be eliminated according to the best replacement algorithm, and so on, as shown in Figure 3-26. From the figure, we can see the situation when the optimal permutation algorithm is adopted.

As you can see, the number of occurrences of missing page infixes is 9, and the number of page substitutions is 6.

Visit page 70120304230321201701 Physical block 17772

2

2

2

2

7

physical Block 2

000

0

4

0

0

0

Physical Block 3

11

3

3

3

1

1

Missing Page No √

√√

√

√

√

√

√

Figure 3.26. Permutation graph with optimal permutation algorithm.

2. FIFO page replacement algorithm

Priority is given to eliminating the pages that enter memory first, i.e., the pages that have been in memory the longest. The algorithm is complex, just link the pages transferred into memory into a queue according to the order, and set a pointer to always point to the earliest page. However, the algorithm does not conform to the discipline of process practice, because some pages are often visited during the process.

Visit page 70120304230321201701 Physical block 17772

224440

00

777 Physical Block 2

000

333222

11

100 Physical Block 3

11

100033

32

221 Missing Page No √√

√√√√√√

√√

√√√

Figure 3.27. Permutation diagram using FIFO permutation algorithm.

Here is still the following example, using FIFO algorithm to stop page replacement. When the procedure visits page 2, it replaces page 7, which entered memory first. Then when visiting page 3, swap out the most advanced page in memory in 2, 0, 1. As can be seen from Figure 3-27, the FIFO algorithm stops 12 page permutations, which is more than twice as many as the optimal permutation algorithm.

FIFO algorithm also occurs when the number of allocated physical blocks increases and the number of page faults increases instead of decreasing, which was discovered by Belady in 1969, so it is called Belady anomaly, as shown in Figure 3-28. As long as FIFO algorithms can present Belady exceptions, LRU and OPT algorithms will never present Belady exceptions.

Visit page 123412512345 physical block 11114445

,5'5

physical Block 2

222111

33

Physical Block 3

33322

24

Missing Page No √√ √ √√

√√

111

555544 Physical block 2*

222

211115 Physical Block 3*

33

332222 Physical block 4*

4

444333 Missing Page No √√

√√√√√√

Figure 3.28 Belady anomaly

3. Longest Unapplied (LRU) Replacement Algorithm

Select the page that hasn't been visited for the longest time in the past and eliminate it. It thinks that the page that hasn't been visited in the past can and won't be visited in the future. The algorithm sets a visit field for each page to record the time the page has been visited since the previous visit, and selects the largest existing page to be eliminated when eliminating pages.

Then use LRU algorithm to stop page replacement for the following example, as shown in Figure 3-29. The first time the process visits page 2, it replaces page 7, which has not been visited for the longest time. Then when visiting page 3, replace page 1, which has not been used for the longest time.

Visit page 70120304230321201701 Physical block 17772

2

4440

1

1

1

physical Block 2

000

0

0033

3

0

0

Physical Block 3

11

3

3222

2

2

7

Missing Page No √√√

√

√√√√

√

√

√

Figure 3.29 Replacement diagram for LRU page replacement algorithm

In Figure 3.29, the first five permutations are the opposite of the best permutation algorithm, but the two algorithms are not necessarily linked. In practice, the LRU algorithm is "looking forward" based on the previous status of each page, while the best replacement algorithm is "looking backward" based on the future use of each page.

LRU functions well, but requires hardware support for storage and stack. LRU is an algorithm for the inn class. In fact, it can be proved that inn-like algorithms cannot exhibit Belady anomalies. FIFO algorithm is based on queue completion, not inn type algorithm.

4. CLOCK permutation algorithm

LRU algorithm functions close to OPT, but it is difficult to complete, and the cost is large;FIFO algorithm is complex, but the function is poor. So operating piecemeal designers tested many algorithms, trying to approach the LRU function with relatively small cost, and such algorithms are mostly variants of CLOCK algorithm.

The complex CLOCK algorithm assigns an additional bit to each frame association, called the use bit. When a page is first loaded into main memory, the frame's use bit is set to 1; when the page is subsequently visited, its use bit is also set to 1. With respect to the page-swapping algorithm, the aggregation of candidate frames for swapping is treated as a round-robin buffer, and a pointer is associated with it. When a page is swapped, the pointer is set to point to the next frame in the buffer. When a page swap is required, the fragment scan buffer is operated to find a frame whose use bit is set to 0. Each time a frame with a use bit of 1 is encountered, the operation fragment resets the bit to 0; if at the beginning of the process all the use bits in the buffer are 0, the first frame encountered is selected for swapping; if all the use bits in the buffer are 1, the pointer circles the buffer perfectly, sets all the use bits to 0, and stays in the last position to swap the pages in the frame. Because the algorithm recursively reflects on the status of each page, it is called CLOCK algorithm, also known as Not Recently Used (NRU) algorithm.

CLOCK algorithm function is similar to LRU, and by adding the number of bits used, CLOCK algorithm can be made more efficient. Add a correction bit to the base of the usage bit, and the improved CLOCK permutation algorithm is lost. Thus, each frame is in one of four states:

It has not been visited or corrected since (u=0, m=0).

More recently visited but not corrected (u=1, m=0).

Previously unvisited, but corrected (u=0, m=1).

The ratio is visited and corrected (u=1, m=1).

The algorithm performs the following steps:

Scan the frame buffer from the beginning of the subsequent position of the pointer. During this scan process, no corrections are made to the applied bits. Select the first frame encountered (u=0, m=0) for the swap.

If step 1) fails, scan again to find the frame of (u=0, m=1). Select the first such frame encountered for exchange. For each skipped frame during this scan, set its use bit to 0.

If step 2) fails, the pointer will return to its last position and all frame usage bits in the aggregate will be 0. Repeat step 1 and, if necessary, step 2. This will allow you to find frames for exchange.

The improved CLOCK algorithm is superior to the complex CLOCK algorithm in that it prefers unchanged pages when swapping. This saves time because corrected pages must be written back before they can be replaced.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.