Understanding Page Replacement Algorithms

Virtual Memory Management Questions

Page Replacement Algorithms

A computer has four-page frames. The table below shows the time of loading, time of last access, and the R and M bits for each page (the times are in clock ticks):

Which page will each of the following algorithms replace?

• NRU (Not Recently Used)
• FIFO (First-In, First-Out)
• LRU (Least Recently Used)
• Second Chance

Answers:

• NRU replaces page 2.
• FIFO replaces page 3.
• LRU replaces page 1.
• Second chance replaces page 2.

Address Space and Page Size

A computer provides each process with 65,536 bytes of address space divided into pages of 4096 bytes. A particular program has a text size of 32,768 bytes, a data size of 16,386 bytes, and a stack size of 15,870 bytes. Will this program fit in the address space? If the page size were 512 bytes, would it fit? Remember that a page may not contain parts of two different segments.

Solution: The text requires eight pages (32,768 / 4096 = 8), the data requires five pages (16,386 / 4096 = 4.0004, rounded up to 5), and the stack requires four pages (15,870 / 4096 = 3.87, rounded up to 4). Therefore, the program needs 17 (8 + 5 + 4) 4096-byte pages. It will not fit in the 16-page address space (65,536 / 4096 = 16). With a 512-byte page size, the text requires 64 pages (32,768 / 512 = 64), the data requires 33 pages (16,386 / 512 = 32.003, rounded up to 33), and the stack requires 31 pages (15,870 / 512 = 30.99, rounded up to 31). This totals 128 (64 + 33 + 31) 512-byte pages, which fits within the 128-page address space (65,536 / 512 = 128). With the smaller page size, it fits, but not with the larger one.

Shared Pages and Working Sets

Can a page be in two working sets at the same time? Explain.

Answer: Yes, if pages can be shared. For example, if two users of a timesharing system are running the same editor simultaneously, and the program text is shared rather than copied, some of those pages may be in each user’s working set at the same time.

Page Faults and Memory Allocation

It has been observed that the number of instructions executed between page faults is directly proportional to the number of page frames allocated to a program. If the available memory is doubled, the mean interval between page faults is also doubled. Suppose that a normal instruction takes 1 microsecond, but if a page fault occurs, it takes 2001 microseconds (i.e., 2 milliseconds to handle the fault). If a program takes 60 seconds to run, during which time it gets 15,000 page faults, how long would it take to run if twice as much memory were available?

Solution: The program experiences 15,000 page faults, each adding 2 milliseconds of processing time. The total page fault overhead is 30 seconds (15,000 * 0.002). This means that half of the 60-second runtime was spent on page fault overhead. If the memory is doubled, the number of page faults is halved to 7,500. The new page fault overhead is 15 seconds (7,500 * 0.002). The program execution time remains 30 seconds (60 – 30). Therefore, the total runtime with doubled memory is 45 seconds (30 + 15).

Backing Store Optimization

A group of operating system designers for the Frugal Computer Company are thinking about ways to reduce the amount of backing store needed in their new operating system. The head guru has just suggested not bothering to save the program text in the swap area at all, but just page it in directly from the binary file whenever it is needed. Under what conditions, if any, does this idea work for the program text? Under what conditions, if any, does it work for the data?

Answer: This approach works for the program text if the program is read-only (cannot be modified). It works for the data if the data is also read-only. However, while program text is commonly read-only, it is extremely rare for data to be read-only. If the data area in the binary file were overwritten with updated pages, the next time the program started, it would not have the original data.

Situations Where Virtual Memory is Undesirable

Can you think of any situations where supporting virtual memory would be a bad idea, and what would be gained by not having to support virtual memory? Explain.

Answer: General virtual memory support is not needed when the memory requirements of all applications are well-known and controlled. Examples include:

• Special-purpose processors (e.g., network processors)
• Embedded processors
• Super-computers (e.g., for airplane wing design)

In these situations, using more real memory should always be considered. If the operating system did not have to support virtual memory, the code would be much simpler and smaller. However, some concepts from virtual memory, such as program/thread isolation, might still be beneficial, perhaps implemented differently (e.g., paging to flash memory).