操作系統(tǒng)第九版部分課后作業(yè)習題答案

1、CHAPTER 9Virtual MemoryPractice Exercises9.1 Un der what circumsta nces do page faults occur? Describe the acti ons take n by the operati ng system whe n a page fault occurs.An swer:A page fault occurs whe n an access to a page that has not bee n brought into mai n memory takes place. The operat ing

2、 system veri?es the memory access, abort ing the program if it is in valid. If it is valid, a free frame is located and I/O is requested to read the n eeded page into the free frame. Upon completio n of I/O, the process table and page table are updated and the in structi on is restarted.9.2 Assume t

3、hat you have a page-refere nee stri ng for a process with m frames (in itially all empty). The page-refere nee stri ng has len gth p;n disti net page nu mbers occur in it. An swer these questi ons for any page-replaceme nt algorithms:a. What is a lower bound on the nu mber of page faults?b. What is

4、an upper bound on the nu mber of page faults?An swer:a. nb. p9.3 Con sider the page table show n in Figure 9.30 for a system with 12-bit virtual 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 sec ond,and F is last).

5、Convert the followi ng virtual addresses to their equivale nt physicaladdresses in hexadecimal. All nu mbers are give n in hexadecimal. (Adash for a page frame in dicates that the page is not in memory.)? 9EF? 1112930 Chapter 9 Virtual Memory? 700? OFFAn swer:? 9E F- 0E F?111- 211? 700- DOO? 0F F- E

6、FF9.4 Consider the following page-replacement algorithms. Rank thesealgorithms on a ?ve-point scale from“ bad ” to “ perfect ” according to thepagefault rate. Separate those algorithms that suffer from Belady' sano maly from those that do not.a. LRU replaceme ntb. FIFO replaceme ntc. Optimal rep

7、laceme ntd. Secon d-cha nee replaceme ntAn swer:Rank Algorithm Suffer from Belady' s anomaly1 Optimal no2 LRU no3 Secon d-cha nee yes4 FIFO yes9.5 Discuss the hardware support required to support dema nd pagi ng.An swer:For every memory-access operati on, the page table n eeds to be con sulted t

8、o check whether the corresp onding page is reside nt or not and whether the program has read or write privileges for access ing the page. These checks have to be performed in hardware. A TLB could serve as a cache and improve the performa nee of the lookup operati on.9.6 An operati ng system support

9、s a paged virtual memory, using a cen tral processor with a cycle time of 1 microsec on d. It costs an additi onal 1 microsec ond to access a page other tha n the curre nt one. Pages have 1000 words, and the pag ing device is a drum that rotates at 3000 revoluti onsper min ute and tran sfers 1 milli

10、o n words per sec ond. The followi ng statistical measureme nts were obta ined from the system:? 1 perce nt of all in structi ons executed accessedpage other tha n the curre nt page.Of the in structi ons that accessed ano ther page, 80 perce nt accessed a page already in memory.Practice Exercises 31

11、?Whe n a new page was required, the replaced page was modi?ed 50 perce nt of the time.Calculate the effective in structi on time on this system, assu ming that the system is running one process only and that the processor is idle duri ng drum tran sfers.An swer:effective access time = 0.99 (1sec +)0

12、.008(2<sec)+ 0.002 )0,000 sec + 1,000 sec)+ 0.001)0,000 sec + 1,000 sec)9.7 Con sider the two-dime nsional array A:int A = new in t100100;where A00 is at locati on 200 in a paged memory system with pages of size 200. A small process that mani pulates the matrix resides in page 0 (locati ons 0 to

13、199). Thus, every in structi on fetch will be from page 0.For three page frames, how many page faults are gen erated bythe followi ng array-i nitializati on loops, using LRU replaceme nt and assu ming that page frame 1 contains the process and the other two are in itially empty?a. for (i nt j = 0; j

14、 < 100; j+)for (i nt i = 0; i < 100; i+)Aij = 0;b. for (i nt i = 0; i < 100; i+)for (i nt j = 0; j < 100; j+)Aij = 0;An swer:a. 5,000b. 509.8 Con sider the followi ng page refere nee stri ng: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 th

15、e follow ing replaceme nt algorithms, assu ming one, two, three, four, ?ve, six, or seve n frames? Remember all frames aren itially empty, so your ?rst unique pages will all cost one fault each.?LRU replaceme nt? FIFO replaceme ntOptimal replaceme nt32 Chapter 9 Virtual MemoryAn swer:Number of frame

16、s 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 pagi ng algorithm that requires a refere neebit (such as see on d-eha nee replaeeme nt or work in g-set model), but the hardware does not provide one. Sketeh how you eould simulate a ref

17、erence bit eve n if one were not provided by the hardware, or expla in why it is not possible to do so. If it is possible, ealeulate what the eost would be.An swer:You can use the valid/i nv alid bit supported in hardware to simulate the refere nee bit. In itially set the bit to inv alid. On ?rst re

18、fere nee a trap to the operati ng system is gen erated. The operat ing system will set a software bit to 1 and reset the valid/i nvalid bit to valid.9.10 You have devised a new page-replaeeme nt algorithm that you thi nkmay be optimal. In some contorted test cases, Belady ' s anomaly occurs. Is

19、thenew algorithm optimal? Expla in your an swer.An swer:No. An optimal algorithm will not suffer from Belady' s anomaly becaby de?n iti on aoptimal algorithm replaces the page that will not be used for the Iongest time. Belady ' ©nomaly occurs when a pagereplacementalgorithm evicts a pa

20、ge that will be needed in the immediatefuture. An optimal algorithm would not have selected such a page.9.11 Segme ntatio n is similar topag ingbutusesvariable-sized “ pages. ”nDe?twosegment-replacementalgorithmsbasedon FIFOandLRUpagereplaceme ntschemes. Remember that since segme nts are not the sam

21、esize, the segme nt that is chose n to be replaced may not be big eno ughto leave eno ugh con secutive locati ons for the n eeded segme nt. Con siderstrategies for systems where segme nts cannot be relocated, and thosefor systems where they can.An swer:a. FIFO. Find the ?rst segme nt large eno ugh t

22、o accommodate the incoming segme nt. If relocati on is not possible and no one segme ntandis large eno ugh, select a comb in ati on of segme nts whose memories are con tiguous, which are“ closest to the ?rst of the listwhich can accommodate the new segme nt. If relocati on is possible, rearra nge th

23、e memory so that the ?rstNsegme nts large eno ugh for the incoming segme nt are con tiguous in memory. Add any leftover space to the free-space list in both cases.Practice Exercises 33b. LRU. Select the segme nt that has not bee n used for the Ion gest period of time and that is large eno ugh, addi

24、ng any leftover space to the free space list. If no one segme nt is large eno ugh, select a comb in ati on of the“ oldest ” segme nts that are con tiguous inmemory (if relocati on is not available) and that are large eno ugh.If relocati on is available, rearra nge the oldest N segme nts to be con ti

25、guous in memory and replace those with the new segme nt.9.12 Con sider a dema nd-paged computer system where the degree of multiprogramming is currently ?xed at four. The system was recently measured to determ ine utilizati on of CPU and the pagi ng disk. The results are one of the follow ing alter

26、natives. For each case, what is happe ning? Can the degree of multiprogram ming be in creased to in crease the CPU utilizati on? Is the pagi ng help ing?a. CPU utilizatio n 13 perce nt; disk utilizati on 97 perce ntb. CPU utilizati on 87 perce nt; disk utilizatio n 3 perce ntc. CPU utilizati on 13 p

27、erce nt; disk utilizati on 3 perce ntAn swer:a. Thrashi ng is occurri ng.b. CPU utilizati on is suf?cie ntly high to leave thi ngs alone, andin crease degree of multiprogram ming.c. In crease the degree of multiprogram ming.9.13 We have an operati ng system for a machi ne that uses base and limit re

28、gisters, but we have modi?ed the mchine to provide a page table.Can the page tables be set up to simulate base and limit registers? How can they be, or why can they not be?An swer:The page table can be set up to simulate base and limit registers provided that the memory is allocated in ?(ed-size seg

29、me nts. In this way, the base of a segme nt can be en tered into the page table and the valid/i nv alid bit used to in dicate that porti on of the segme nt as reside nt in the memory. There will be some problem with in ternal fragme ntatio n.9.27.C on sider a dema nd-pag ing system with the followi

30、ng time-measured utilizati ons:CPU utilization 20%Pagi ng disk 97.7%Other I/O devices 5%Which (if any) of the followi ng will (probably) improve CPU utilizati on? Expla in your an swer.a. I nstall a faster CPU.b. In stall a bigger pagi ng disk.c. In crease the degree of multiprogram ming.d. Decrease

31、 the degree of multiprogram ming.e. I nstall more mai n memory.f. In stall a faster hard disk or multiple con trollers with multiple hard disks.g. Add prepagi ng to the page fetch algorithms.h. In crease the page size.Answer: The system obviously is spending most of its time paging, in dicati ng ove

32、r-allocatio nof memory. If the level of multiprogram ming is reduced reside nt processeswould page fault less freque ntly and the CPU utilizati on would improve.Ano ther way toimprove performa nee would be to get more physical memory or a faster pagi ng drum.a. Get a faster CPU No.b. Get a bigger pa

33、g ing drum- No.c. In crease the degree of multiprogram min No.d. Decrease the degree of multiprogram minY es.e. In stall more main memory Likely to improve CPU utilizati on as more pages canrema in reside nt and not require pag ing to or from the disks.f. In stall a faster hard disk, or multiple con

34、 trollers with multiple hard disks Also animproveme nt, for as the disk bottle neck is removed by faster resp onse and morethroughput to the disks, the CPU will get more data more quickly.g. Add prepagi ng to the page fetch algorithmsAga in, the CPU will get more datafaster, so it will be more in us

35、e. This is only the case if the pag ing acti onis ame nableto prefetch ing (i.e., some of the access is seque ntial).h. In crease the page size In creas ing the page size will result in fewer page faults ifdata is being accessed seque ntially. If data access is more or less ran dom, morepagi ng acti

36、 on could en sue becausefewer pagesca n be kept in memory and moredata is tra nsferred per page fault. So this cha nge is as likely to decrease utilizati onas it is to in crease it.10.1、Is disk scheduling, other than FCFS scheduling, useful in asin gle-useren vir onment? Expla in your an swer.Answer

37、: In a single-user environment, the I/O queue usually is empty. Requestsgenerally arrive from a single process for one block or for a seque nee of con secutive blocks. In these cases, FCFS is an econo mical method of disk scheduling. But LOOK is nearly as easy to program and will give much better pe

38、rformanee when multiple processes are perform ing con curre nt I/O, such as whe n aWeb browser retrieves data in the background while the operating system is paging and another applicati on is active in the foregro und.10.2. Explain why SSTF scheduling tends to favor middle cylinders over theinn erm

39、ost and outermost cyli nders.The center of the disk is the location having the smallest average distanee to all other tracks.Thus the disk head tends to move away from the edges of the disk.Here is ano ther way to thi nk of it.The current location of the head divides the cylinders into two groupsf t

40、he head is not in the center of the disk and a new request arrives,the new request is more likely to be in the group that includes the center of the disk;thus,the head is more likely to move in that directi on.10.11、Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is curre

41、ntly serving a request at cylinder 143, and the previous request was at cyli nder 125. The queue of pending requests, in FIFO order, is86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130Starti ng from the curre nt head positi on, what is the total dista nee (incylinders) that the disk arm moves to satis

42、fy all the pending requests, for each of the following disk-scheduling algorithms?a. FCFSb. SSTFc. SCANd. LOOKe. C-SCANAnswer:a. The FCFS schedule is 143, 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130. The total seek distance is 7081.b. The SSTF schedule is 143, 130, 86, 913, 948, 1022, 1470, 1509

43、, 1750, 1774. The total seek dista nce is 1745.c. The SCAN schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 130, 86. The total seek dista nce is 9769.d. The LOOK schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 86. The total seek distance is 3319.e. The C-SCAN schedule is

44、143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 86, 130. The total seek dista nee is 9813.f. (Bonus.) The C-LOOK schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130. The total seek dista nee is 3363.12CHAPTERFile-SystemImpleme ntati onPractice Exercises12.1 Consider a ?le currently c

45、onsisting of 100 blocks. Assume that the ?lec on trol block (and the in dex block, in the case of in dexed allocati on) is already in memory. Calculate how many disk I/O operati ons are required for con tiguous, li nked, and in dexed (sin gle-level) allocati on strategies, if, for one block, the fol

46、lowi ng con diti ons hold. In the con tiguous-allocatio n case, assume that there is no room to grow at the begi nning but there is room to grow at the end. Also assume that the block information to be added is stored in memory.a. The block is added at the beg inning.b. The block is added in the mid

47、dle.c. The block is added at the end.d. The block is removed from the beg inning.e. The block is removed from the middle.f. The block is removed from the end.An swer:The results are:Con tiguous Linked In dexeda. 201 1 1b. 101 52 1c. 1 3 1d. 198 1 0e. 98 52 0f. 0 100 012.2 What problems could occur i

48、f a system allowed a ?le system to be moun ted simulta neously at more tha n one locatio n?An swer:4344 Chapter 12 File-System Impleme ntatio nThere would be multiple paths to the same ?le, which could con fuse users or en courage mistakes (delet ing a ?le with one path deletes the ?le in all the ot

49、her paths).12.3 Why must the bit map for ?le allocation be kept on mass storage, ratherthan in main memory?An swer:In case of system crash (memory failure) the free-space list would not be lost as it would be if the bit map had been stored in main memory.12.4 Consider a system that supports the stra

50、tegies of contiguous, linked, and indexed allocation. What criteria should be used in deciding which strategy is best utilized for a particular ?le?An swer:?Con tiguous if ?le is usually accessed seque ntially, if ?le is relatively small.?Linked if ?le is large and usually accessed sequentially.? In

51、 dexed if ?le is large and usually accessed ran domly.12.5 One problem with contiguous allocation is that the user must preallocate eno ugh space for each ?le. If the ?le grows to be larger tha n thespace allocated for it, special actions must be taken. One solution to this problem is to de?ne a ?le

52、 structure consisting of an initial contiguous area (of a speci?ed size). If this area is ?lled, the operating system automatically de?nes an over?ow area that is linked to the initial con tiguous area. If the over?ow area is ?lled, ano ther over?ow area is allocated. Compare this implementation of a ?le with the standard contiguous and linked implementations.An swer:This method requires more overhead the n the sta ndard con tiguous allocati on .It requires less overheadtha n the sta ndard lin ked allocatio n.12.6