CHAPTER 9 Virtual Memory

Practice Exercises

9.1 Under what circumstances do page faults occur? Describe the actions taken by the operating system when a page fault occurs. Answer:

A page fault occurs when an access to a page that has not been brought into main memory takes place. The operating system veri?es the memory access, aborting the program if it is invalid. If it is valid, a free frame is located and I/O is requested to read the needed page into the free frame. Upon completion of I/O, the process table and page table are updated and the instruction is restarted.

9.2 Assume that you have a page-reference string for a process with m frames (initially all empty). The page-reference string has length p; n distinct page numbers occur in it. Answer these questions for any page-replacement algorithms:

a. What is a lower bound on the number of page faults? b. What is an upper bound on the number of page faults? Answer: a. n b. p

9.3 Consider the page table shown in Figure 9.30 for a system with 12-bit virtual and physical addresses and with 256-byte pages. The list of free

page frames is D, E, F (that is, D is at the head of the list, E is second, and F is last).

Convert the following virtual addresses to their equivalent physical addresses in hexadecimal. All numbers are given in hexadecimal. (A dash for a page frame indicates that the page is not in memory.) ? 9EF ? 111

2930 Chapter 9 Virtual Memory ? 700 ? 0FF Answer: ? 9E F - 0E F ? 111 - 211 ? 700 - D00 ? 0F F - EFF

9.4 Consider the following page-replacement algorithms. Rank these algorithms on a ?ve-point scale from “bad” to “perfect” according to their page-fault rate. Separate those algorithms that suffer from Belady’s anomaly from those that do not. a. LRU replacement b. FIFO replacement c. Optimal replacement

d. Second-chance replacement Answer:

Rank Algorithm Suffer from Belady’s anomaly 1 Optimal no 2 LRU no

3 Second-chance yes 4 FIFO yes

9.5 Discuss the hardware support required to support demand paging. Answer:

For every memory-access operation, the page table needs to be consulted to check whether the corresponding page is resident or not and whether the program has read or write privileges for accessing the page. These checks have to be performed in hardware. A TLB could serve as a cache and improve the performance of the lookup operation.

9.6 An operating system supports a paged virtual memory, using a central processor with a cycle time of 1 microsecond. It costs an additional 1 microsecond to access a page other than the current one. Pages have 1000 words, and the paging device is a drum that rotates at 3000 revolutions per minute and transfers 1 million words per second. The following statistical measurements were obtained from the system:

? 1 percent of all instructions executed accessed a page other than the current page.

?

Of the instructions that accessed another page, 80 percent accessed a page already in memory.Practice Exercises 31 ?

When a new page was required, the replaced page was modi?ed 50 percent of the time.

Calculate the effective instruction time on this system, assuming that the system is running one process only and that the processor is idle during drum transfers. Answer:

effective access time = 0.99 × (1 sec + 0.008 × (2 sec) + 0.002 × (10,000 sec + 1,000 sec) + 0.001 × (10,000 sec + 1,000 sec) = (0.99 + 0.016 + 22.0 + 11.0) sec = 34.0 sec

9.7 Consider the two-dimensional array A: int A[][] = new int[100][100];

where A[0][0] is at location 200 in a paged memory system with pages of size 200. A small process that manipulates the matrix resides in page 0 (locations 0 to 199). Thus, every instruction fetch will be from page 0. For three page frames, how many page faults are generated by the following array-initialization loops, using LRU replacement and