CHAPTER 9 Virtual MemoryPractice Exercises9.1 Under what circumstances do page faults occur? Describe the actionstaken by the operating system when a page fault occurs.Answer:A page fault occurs when an access to a page that has not beenbrought into main memory takes place. The operating system veriesthe memory access, aborting the program if it is invalid. If it is valid, afree frame is located and I/O is requested to read the needed page intothe free frame. Upon completion of I/O, the process table and page tableare updated and the instruction is restarted.9.2 Assume that you have a page-reference string for a process with mframes (initially all empty). The page-reference string has length p;n distinct page numbers occur in it. Answer these questions for anypage-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. nb. p9.3 Consider the page table shown in Figure 9.30 for a system with 12-bitvirtual and physical addresses and with 256-byte pages. The list of freepage 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 physicaladdresses in hexadecimal. All numbers are given in hexadecimal. (Adash for a page frame indicates that the page is not in memory.) 9EF 1112930 Chapter 9 Virtual Memory 700 0FFAnswer: 9E F - 0E F 111 - 211 700 - D00 0F F - EFF9.4 Consider the following page-replacement algorithms. Rank these algorithms on a ve-point scale from “bad” to “perfect” according to theirpage-fault rate. Separate those algorithms that suffer from Beladysanomaly from those that do not.a. LRU replacementb. FIFO replacementc. Optimal replacementd. Second-chance replacementAnswer:Rank Algorithm Suffer from Beladys anomaly1 Optimal no2 LRU no3 Second-chance yes4 FIFO yes9.5 Discuss the hardware support required to support demand paging.Answer:For every memory-access operation, the page table needs to be consultedto check whether the corresponding page is resident or not and whetherthe program has read or write privileges for accessing the page. Thesechecks have to be performed in hardware. A TLB could serve as a cacheand improve the performance of the lookup operation.9.6 An operating system supports a paged virtual memory, using a centralprocessor with a cycle time of 1 microsecond. It costs an additional 1microsecond to access a page other than the current one. Pages have 1000words, and the paging device is a drum that rotates at 3000 revolutionsper minute and transfers 1 million words per second. The followingstatistical measurements were obtained from the system: 1 percent of all instructions executed accessed a page other than thecurrent page.Of the instructions that accessed another page, 80 percent accesseda page already in memory.Practice Exercises 31When a new page was required, the replaced page was modied 50percent of the time.Calculate the effective instruction time on this system, assuming that thesystem is running one process only and that the processor is idle duringdrum transfers.Answer:effective access time = 0.99 (1sec + 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.0sec9.7 Consider the two-dimensional array A:int A = new int100100;where A00 is at location 200 in a paged memory system with pagesof size 200. A small process that manipulates the matrix resides in page0 (locations 0 to 199). Thus, every instruction fetch will be from page 0.For three page frames, how many page faults are generated bythe following array-initialization loops, using LRU replacement andassuming that page frame 1 contains the process and the other twoare initially empty?a. for (int j = 0; j 100; j+)for (int i = 0; i 100; i+)Aij = 0;b. for (int i = 0; i 100; i+)for (int j = 0; j 100; j+)Aij = 0;Answer:a. 5,000b. 509.8 Consider the following page reference string:1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.How many page faults would occur for the following replacementalgorithms, assuming one, two, three, four, ve, six, or seven frames?Remember all frames are initially empty, so your rst unique pages willall cost one fault each.LRU replacement FIFO replacementOptimal replacement32 Chapter 9 Virtual MemoryAnswer:Number of frames LRU FIFO Optimal1 20 20 202 18 18 153 15 16 114 10 14 85 8 10 76 7 10 77 77 79.9 Suppose that you want to use a paging algorithm that requires a referencebit (such as second-chance replacement or working-set model), butthe hardware does not provide one. Sketch how you could simulate areference bit even if one were not provided by