Use Stacks to Record Recent Page References

used for the longest period of time. Use a page replacement algorithm that ensures the lowest possible page fault rate for a fixed number of frames.

For example, on a sample reference string, the optimal page replacement algorithm generates 9 page faults, as shown in Figure 3.36. The first reference causes a fill fault in 3 empty frames. The reference to page 2 replaces page 7 because 7 will not be used until reference 18, whereas page 0 will be used at 5 and page 1 at 14. The reference to page 3 replaces page 1 because page 1 will be the last of the 3 pages in memory to be referenced again. With only 9 page faults, the optimal replacement is much better than the FIFO algorithm, which has 15 faults. (If we ignore the first 3 faults that all algorithms encounter, the optimal replacement is twice as good as the FIFO replacement.) Indeed, no replacement algorithm can process the reference string in 3 frames with fewer than 9 faults.

However, the optimal page replacement algorithm is difficult to implement because it requires future knowledge of the reference sequence. Therefore, the optimal algorithm is used mainly for comparative studies. For example, it can be useful to know that, although an algorithm is not optimal, it is within 12.3% of the optimal being bad, and within 4.7% of the optimal being average.

Figure 3.36 Optimal page replacement algorithm

Maybe you are interested!

3) Replace LRU page

If the optimal algorithm is not feasible, perhaps an approximation to the optimal algorithm is possible. The main difference between the FIFO and OPT algorithms is that FIFO uses the time when the page is brought into memory; the OPT algorithm uses the time when the page is used. If we are going to use the recent past as an approximation of the near future, then we will replace the page that has not been used for the longest period of time (Figure 3.37). This approach is the least-recently-used (LRU) algorithm.

Figure 3.37 LRU page replacement algorithm

LRU page replacement associates with each page the last time the page was used. When a page must be replaced, LRU selects the page that has not been used for the longest period of time. This strategy is an optimal page replacement algorithm that searches backward in time rather than forward. (Let S R be the reverse order of the reference sequence S, then the page fault rate for the OPT algorithm on S is the same as the page fault rate for the OPT algorithm on S R . Similarly, the page fault rate for the LRU algorithm on S is the same as the page fault rate for the LRU algorithm on S R )

The results of applying LRU replacement to a typical reference string are shown in Figure 3.38. The LRU algorithm generates 12 errors. The first 5 errors are similar to the optimal replacement. However, when the reference to page 4 occurs, the LRU replacement finds that 3 frames in memory, page 2 is the most recently used. The most recently used page is page 0, and just before page 3 is used. Therefore, the LRU algorithm replaces page 2, not knowing that page 2 is about to be used. Then, when it causes a page 2 fault, the LRU algorithm replaces page 3, of the 3 pages in memory {0, 3, 4}, page 3 is the least recently used. Despite this problem, the LRU replacement with 12 errors is still better than the FIFO replacement with 15.

Figure 3.38 page replacement algorithm

LRU policy is often used as a page replacement algorithm and is considered good. The main issue is how to implement LRU replacement. An LRU page replacement algorithm

may require hardware assistance. The problem is to determine the order for the frames defined by the most recent use time. Two possible implementations are:

- Counters : In the simplest case, we attach to each page table entry a usage time field and add to the CPU a logical clock or counter. The clock is incremented for each memory reference. Whenever a reference to a page is made, the contents of the clock register are copied to the usage time field in the page table entry for that page. In this way, we always have the time of the last reference to each page. We replace the page with the smallest usage time value. This mechanism requires a page table lookup to find the LRU page and a write to memory (to the usage time field in the page table) for each memory access. The times must also be maintained when the page tables are changed (due to CPU scheduling). Exceeding the clock limit must be considered.

- Stack : Another approach to implementing LRU replacement is to keep a stack of page numbers. Whenever a page is referenced, it is removed from the stack and placed on the top. In this approach, the top of the stack is always the most recently used page and the bottom is the LRU page (Figure 3.39). Since entries must be removed from the middle of the stack, it is best implemented by a doubly linked list with head and tail pointers. Removing a page and placing it on the top of the stack then requires changing 6 pointers in the worst case. Each update is less expensive but does not require finding a replacement; the tail pointer points to the bottom of the stack as the LRU page. This approach is particularly suitable for software or microcode implementations of LRU replacement.

Optimization and LRU replacement do not suffer from Belady's paradox. There is a class of page replacement algorithms called stack algorithms, which never suffer from Belady's paradox. A stack algorithm is an algorithm for which it can be shown that the set of pages in memory for n frames is always a subset of the set of pages that are in memory for n + 1 frames. For LRU replacement, the set of pages in memory is the n most recently referenced pages. If the number of pages is increased, then these n pages will still be the most recently referenced pages and thus will remain in memory.

Note that LRU implementation will probably have no hardware assistance except for the TLB register. Updates to clock or stack fields must be performed for

per memory reference. If we used interrupts for each memory reference, allowing software to update data structures, it would slow down each memory reference by nearly 1/10. Very few systems can afford that level of memory management overhead.

Figure 3.39 uses the stack to record recent page references.

4) Approximate LRU page replacement algorithm

Very few computer systems provide complete hardware support for LRU page replacement. Some systems do not provide any hardware support and other page replacement algorithms (such as FIFO algorithms) must be used. However, many systems provide some support in the form of a reference bit. The reference bit for a page is set by the hardware whenever that page is referenced (read or written to any bit in the page). The reference bits are associated with each entry in the page table.

Initially, all bits are cleared (to 0) by the operating system. When a user process executes, the bit assigned to each referenced page is set (to 1) by the hardware. After that time, we can determine which pages are used and which are not by examining the reference bits. We do not know the order of use, but we know which pages are used and which are not. The partial order information leads to many page replacement algorithms that approximate LRU replacement.

a) Algorithm for auxiliary reference bits

We can get additional sequence information by recording reference bits at regular intervals. We can keep one byte for each page in a table in memory. At regular intervals (every 100 milliseconds)

seconds), a timer interrupt transfers control to the operating system. The operating system moves the reference bit for each page into the most significant bit of the byte, shifting the remaining bits right by 1 bit. The least significant bit is cleared. The 8-bit shift register can hold a history of page usage for the last 8 times. If the shift register contains 00000000, the page has not been used for 8 times; a page that has been used at least once each time will have a shift register value of 11111111.

A register with a historical register value of 11000100 is more recently used than a page with 01110111. If we interpret these 8 bits as an unsigned integer, the page with the lowest number is the LRU page and it can be replaced. However, these numbers are not guaranteed to be unique, we replace all pages with the lowest value or use a FIFO to choose between them.

Of course, the number of history bits can vary and can be chosen (depending on available hardware) to perform the update as quickly as possible. In extreme cases, the number can be reduced to zero, leaving only the reference bit itself. This algorithm is called the second-chance page-replacement algorithm.

b) Second chance algorithm

Figure 3.40 Second chance page replacement algorithm

The second-chance page replacement algorithm is essentially a FIFO replacement algorithm. However, when a page is selected, we examine its reference bit. If this bit is 0, we proceed to replace the page. However, if the reference bit is set to 1, we give the page a second chance and move to select the next FIFO page. When a page receives a second chance, its reference bit is cleared and its arrival time is reset to the current time. Therefore, a page that is given a second chance will not be replaced until all other pages have been replaced (or given a second chance). Additionally, if a page is used frequently enough to keep its reference bit set, it will never be replaced.

One way to implement the second-chance algorithm is as a circular queue. A pointer indicates which page is to be replaced next. When a frame is requested, the pointer is incremented until it finds a page with the reference bit 0. As it increments, it clears the reference bits (Figure 3.12). Once the victim page is found, the page is replaced and the new page is inserted into the circular queue in that position. Note that, in the worst case when all bits are set, the pointer cycles through the entire queue, giving each page a second chance. Second-chance replacement becomes a FIFO replacement if all bits are set.

c) Advanced Second Chance Algorithm

We can improve the second chance algorithm by considering both the reference and modifier bits as an ordered pair. With these two bits, we have four possible cases:

1) (0,0) is not used recently and has not been modified - the best page to replace.

2) (0,1) is not used recently but has been modified - not so good as the page needs to be written before replacing.

3) (1,0) has been used recently but has not been modified - it will probably be used again soon.

4) (1,1) is recently used and modified-the page will likely be reused soon and the page will need to be written to disk before it can be replaced.

When replacing a requested page, each page is in one of four situations. We use the same mechanism as the clock algorithm, but instead of looking at the page

If the page we are pointing to has the reference bit set to 1, we look at the instance to which the page belongs. We replace the first page encountered in the lowest case that is not empty. We may have to scan the circular queue many times before we find a page to replace.

This algorithm is used in the Macintosh virtual memory management mechanism. The main difference between this algorithm and the simpler clock algorithm is that we refer to those pages which are modified to reduce the amount of I/O required.

d) Replace page based on count

There are many other algorithms that can be used for page replacement. For example, we could keep a reference counter for each page and develop the following two mechanisms:

- The least frequently used (LFU) page-replacement algorithm requires that the page with the smallest count be replaced. The reason for this choice is that the page that is used should have a large reference counter. This algorithm suffers from the situation: the page is used a lot during initialization but is never used again. Because it is used a lot, it has a large counter and remains in memory even though it is no longer needed. One solution is to shift the counter right by 1 bit at regular intervals, forming an exponentially decreasing average usage counter.

- The most frequently used (MFU) page-replacement algorithm replaces the page with the largest count value, that is, the page that is used the most.

3.2.6 Frame allocation

How do we allocate a fixed amount of free memory between different processes? If we have 93 free frames and 2 processes, how many frames will each process get?

The simplest case of virtual memory is a single-tasking system. Consider a single-tasking system with 128 KB of memory made up of 1 KB pages. Therefore, there are 128 page frames. The operating system can take 35 KB, leaving 93 page frames for the user process. Under pure request paging, all the first 93 page frames are placed on the free frame list. When a user process starts

As it executes, it generates a sequence of page faults. The first 93 page faults are free frames from the free frame list. When the free frame list is exhausted, a page replacement algorithm is used to select one of the 93 pages currently in memory to replace with the 94th page, etc. When a process terminates, the 93rd page frame is again replaced on the free frame list.

There are many variations on this simple strategy. We can ask the operating system to allocate all its buffers and table spaces from the free frame list.

When this space is not used by the operating system, it can be used to support user paging. We can try to keep 3 free page frames reserved on the free page frame list at all times. Thus, when a page fault occurs there is a free frame available for the page. While a page swap is occurring, a replacement can be chosen, and the page is then written to disk when the user process resumes execution.

Another change that can be made to the basic strategy is that the user process is allocated any free page frames.

Another problem arises when request paging is combined with multiprogramming.

Multiprogramming places two or more processes in memory at the same time.

- Minimum number of page frames

Frame allocation strategies are constrained in various ways. We cannot allocate more than the total number of available frames (without page sharing). We also allocate at least a minimum number of frames. Note that as the number of frames allocated to each process decreases, the page fault rate increases, reducing process execution.

In addition, the ability to perform unexpected allocations is limited to a few page frames, and there is a minimum number of page frames that must be allocated. The minimum number. This minimum number is specified by the computer architecture. Remember, when a page fault occurs before an instruction completes execution, the instruction must start over. Therefore, we must have enough page frames to hold all the different pages that any single instruction might refer to.

For example, consider a machine in which all instructions refer to memory with only one memory address. Therefore, we need at least one page frame for the instruction and one frame for the

Comment