1、操作系统第九版部分课后作业习题答案分析解析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
2、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 tha
3、t 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 o
4、n 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
5、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 pa
6、ge-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 replacementAnsw
7、er: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 an
8、d 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
9、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 s
10、ystem: 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 eff
11、ective 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=
12、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 frame
13、s, 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;
14、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
15、 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 algorith
16、m 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 the hardware, or explainwhy it is not possible to do so. If it is possible, calculate what the
17、costwould be.Answer:You can use the valid/invalid bit supported in hardware to simulate thereference bit. Initially set the bit to invalid. On rst reference a trap to theoperating system is generated. The operating system will set a softwarebit to 1 and reset the valid/invalid bit to valid.9.10 You
18、have devised a new page-replacement algorithm that you think maybe optimal. In some contorted test cases, Beladys anomaly occurs. Is thenew algorithm optimal? Explain your answer.Answer:No. An optimal algorithm will not suffer from Beladys anomaly becauseby denitionan optimal algorithm replaces the
19、page that will notbe used for the longest time. Beladys anomaly occurs when a pagereplacement algorithm evicts a page that will be needed in the immediatefuture. An optimal algorithm would not have selected such a page.9.11 Segmentation is similar to paging but uses variable-sized“pages.”Denetwo seg
20、ment-replacement algorithms based on FIFO and LRU pagereplacement schemes. Remember that since segments are not the samesize, the segment that is chosen to be replaced may not be big enoughto leave enough consecutive locations for the needed segment. Considerstrategies for systems where segments can
21、not be relocated, and thosefor systems where they can.Answer:a. FIFO. Find the rst segment large enough to accommodate theincoming segment. If relocation is not possible and no one segmentis large enough, select a combination of segments whose memoriesare contiguous, which are “closest to the rst of
22、 the list” andwhich can accommodate the new segment. If relocation is possible,rearrange the memory so that the rstNsegments large enough forthe incoming segment are contiguous in memory. Add any leftoverspace to the free-space list in both cases.Practice Exercises 33b. LRU. Select the segment that
23、has not been used for the longestperiod of time and that is large enough, adding any leftover spaceto the free space list. If no one segment is large enough, selecta combination of the “oldest” segments that are contiguous inmemory (if relocation is not available) and that are large enough.If reloca
24、tion is available, rearrange the oldest N segments to becontiguous in memory and replace those with the new segment.9.12 Consider a demand-paged computer system where the degree of multiprogramming is currently xed at four. The system was recently measured to determine utilization of CPU and the pag
25、ing disk. The resultsare one of the following alternatives. For each case, what is happening?Can the degree of multiprogramming be increased to increase the CPUutilization? Is the paging helping?a. CPU utilization 13 percent; disk utilization 97 percentb. CPU utilization 87 percent; disk utilization
26、 3 percentc. CPU utilization 13 percent; disk utilization 3 percentAnswer:a. Thrashing is occurring.b. CPU utilization is sufciently high to leave things alone, andincrease degree of multiprogramming.c. Increase the degree of multiprogramming.9.13 We have an operating system for a machine that uses
27、base and limitregisters, but we have modied the machine to provide a page table.Can the page tables be set up to simulate base and limit registers? Howcan they be, or why can they not be?Answer:The page table can be set up to simulate base and limit registers providedthat the memory is allocated in
28、xed-size segments. In this way, the baseof a segment can be entered into the page table and the valid/invalid bitused to indicate that portion of the segment as resident in the memory.There will be some problem with internal fragmentation.9.27.Consider a demand-paging system with the following time-
29、measured utilizations:CPUutilization 20%Paging disk 97.7%OtherI/Odevices 5%Which (if any) of the following will (probably) improve CPU utilization? Explain your answer.a. Install a fasterCPU.b. Install a bigger paging disk.c. Increase the degree of multiprogramming.d. Decrease the degree of multipro
30、gramming.e. Install more main memory.f. Install a faster hard disk or multiple controllers with multiple hard disks.g. Add prepaging to the page fetch algorithms.h. Increase the page size.Answer:The system obviously is spending most of its time paging, indicating over-allocationof memory. If the lev
31、el of multiprogramming is reduced resident processeswould page fault less frequently and theCPUutilization would improve. Another way toimprove performance would be to get more physical memory or a faster paging drum.a. Get a fasterCPUNo.b. Get a bigger paging drumNo.c. Increase the degree of multiprogrammingNo.d. Decrease the degree of multiprogrammingYes.e. Install more main memoryLikely to improveCPUutilization as more pages canremain resident and not require paging to or from the disks.f. I
