《操作系统概念第六版作业解答3》由会员分享，可在线阅读，更多相关《操作系统概念第六版作业解答3（25页珍藏版）》请在金锄头文库上搜索。
1、Chapter 9n9.3 Describe the following allocation algorithms:na. First fitnb. Best fitnc. Worst fitnFirst fit:搜索可用内存列表，分配第一块足够大的nBest fit:搜索整个可用内存块，分配最小足够大的nWorst fit:搜索整个可用内存块，分配最大足够大的9-cont.n9.5 Given memory partitions of 100K, 500K, 200K, 300K, and 600K (in order), how would each of the First-fit,
2、Best-fit, and Worst-fit algorithms place processes of 212K, 417K, 112K, and 426K (in order)? Which algorithm makes the most efficient use of memory?nFirst fitn212 -500(288)n417 -600(183)n112 -288n426 -nonenBest fitn212 -300n417 -500n112 -200 n426 -600nWorst fitn212 -600(388)n417 -500n112 -388 n426 -
3、none9-cont.n9.10 Consider a paging system with the page table stored in memory.na. If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?nb. If we add associative registers, and 75 percent of all page-table references are found in the associative registers, what is
4、 the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.)na. 400, 200(page table)+200(access word)nb. 250, 75%*200+25%*(200+200)9-cont.n9.16 Consider the following segment table:nWhat are the physical addresses
5、 for the following logical addresses?na. 0,430nb. 1,10nc. 2,500nd. 3,400ne. 4,112na. 430600, 219+430 = 649nb. 10100, illegalnd. 40096, illegal9-cont.n9.18 In the IBM/370, memory protection is provided through the use of keys. A key is a 4-bit quantity. Each 2K block of memory has a key (the storage
6、key) associated with it. The CPU also has a key (the protection key) associated with it. A store operation is allowed only if both keys are equal, or if either is zero. Which of the following memory-management schemes could be used successfully with this hardware?na. Bare machinenb. Single-user syst
7、emnc. Multiprogramming with a fixed number of processesnd. Multiprogramming with a variable number of processesne. Pagingnf. Segmentationna. Protection not necessary, set system key to 0.nb. Set system key to 0 when in supervisor mode.nc. Region sizes must be fixed in increments of 2k bytes, allocat
8、e key with memorynblocks.nd. Same as above.ne. Frame sizes must be in increments of 2k bytes, allocate key with pages.nf. Segment sizes must be in increments of 2k bytes, allocate key with segments.Chapter 10n10.1 Under what circumstances do page faults occur? Describe the actions taken by the opera
9、ting system when a page fault occurs.nA page fault occurs when an access to a page that has not been brought into main memory takes place. nThe operating system verifies the memory access, naborting the program if it is invalid. nIf it is valid, a free frame is located and I/O is requested to read t
10、he needed page into the free frame. Upon completion of I/O, the process table and page table are updated and the instruction is restarted.10-cont.n10.6 Consider the following page-replacement algorithms. Rank these algorithms on a five point scale from “bad” to “perfect” according to their page-faul
11、t rate. Separate those algorithms that suffer from Beladys anomaly from those that do not.na. LRU replacementnb. FIFO replacementnc. Optimal replacementnd. Second-chance replacementnRank Algorithm Suffer from Beladys anomalyn1 Optimal non2 LRU non3 Second-chance yesn4 FIFO yes10-cont.n10.9 Consider
12、a demand-paging system with the following time-measured utilizations: CPU utilization 20% Paging disk 97.7% Other I/O devices 5% Which (if any) of the following will (probably) improve CPU utilization? Explain your answer.na. Install a faster CPU.nb. Install a bigger paging disk.nc. Increase the deg
13、ree of multiprogramming.nd. Decrease the degree of multiprogramming.ne. Install more main memory.nf. Install a faster hard disk or multiple controllers with multiple hard disks.ng. Add prepaging to the page fetch algorithms.nh. Increase the page size.10-cont.n10.10 Consider the two-dimensional array
14、 A: int A = new int100100; where A00 is at location 200, in a paged system with pages of size 200. A small process is in page 0 (locations 0 to 199) for manipulating the matrix; thus, every instruction fetch will be from page 0. For three page frames, how many page faults are generated by the follow
15、ing array-initialization loops, using LRU replacement, and assuming page frame 1 has the process in it, and the other two are initially empty:na. for (int j = 0; j 100; j+) for (int i = 0; i 100; i+) Aij = 0;nb. for (int i = 0; i 100; i+) for (int j = 0; j 100; j+) Aij = 0;a. 100x50b. 5010-cont.n10.
16、11 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 replacement algorithms, assuming one, two, three, four, five, six, or seven frames? Remember all frames are initially empty, so your first u
17、nique pages will all cost one fault each.nLRU replacementnFIFO replacementnOptimal replacementnNumber of frames LRU FIFO Optimaln 1 20 20 20n 2 18 18 15n 3 15 16 11n 4 10 14 8n 5 8 10 7n 6 7 10 7n 7 7 7 7Chapter 11n11.3 Why do some systems keep track of the type of a file, while others leave it to t
18、he user or simply do not implement multiple file types? Which system is “better?”nSome systems allow different file operations based on the type of the file (for instance, an ascii file can be read as a stream while a database file can be read via an index to a block). Other systems leave such inter
19、pretation of a files data to the process and provide no help in accessing the data. The method which is “better” depends on the needs of the processes on the system, and the demands the users place on the operating system. If a system runs mostly database applications, it may be more efficient for t
20、he operating system to implement a database-type file and provide operations, rather than making each program implement the same thing (possibly in different ways). For general purpose systems it may be better to only implement basic file types to keep the operating system size smaller and allow max
21、imum freedom to the processes on the system.11-cont.n11.6 Could you simulate a multilevel directory structure with a single-level directory structure in which arbitrarily long names can be used? If your answer is yes, explain how you can do so, and contrast this scheme with the multilevel directory
22、scheme. If your answer is no, explain what prevents your simulations success. How would your answer change if file names were limited to seven characters?nIf arbitrarily long names can be used then it is possible to simulate a multilevel directory structure. This can be done, for example, by using t
23、he character “.” to indicate the end of a subdirectory. Thus, for example, the name jim.pascal.F1 specifies that F1 is a file in subdirectory pascal which in turn is in the root irectory jim. If file names were limited to seven characters, then the above scheme could not be utilized and thus, in gen
24、eral, the answer is no. The next best approach in this situation would be to use a specific file as a symbol table (directory) to map arbitrarily long names (such as jim.pascal.F1) into shorter arbitrary names (such as XX00743), which are then used for actual file access.11-cont.n11.9 Give an exampl
25、e of an application in which data in a file should be accessed in the following order:na. Sequentiallynb. Randomlyna. Print the content of the file.nb. Print the content of record i. This record can be found using hashing or index techniques.n11.12 Consider a system that supports 5000 users. Suppose
26、 that you want to allow 4990 of these users to be able to access one file.na. How would you specify this protection scheme in UNIX?nb. Could you suggest another protection scheme that can be used more effectively for this purpose than the scheme provided by UNIX?na. There are two methods for achievi
27、ng this:ni. Create an access control list with the names of all 4990 users.nii. Put these 4990 users in one group and set the group access accordingly. This scheme cannot always be implemented since user groups are restricted by the system.nb. The universe access information applies to all users unl
28、ess their name appears in the access-control list with different access permission. With this scheme you simply put the names of the remaining ten users in the access control list but with no access privileges allowed.Chapter 12n12.1 Consider a file currently consisting of 100 blocks. Assume that th
29、e file control block (and the index block, in the case of indexed allocation) is already in memory. Calculate how many disk I/O operations are required for contiguous, linked, and indexed (single-level) allocation strategies, if, for one block, the following conditions hold. In the contiguous alloca
30、tion case, assume that there is no room to grow in the beginning, but there is room to grow in the end. Assume that the block information to be added is stored in memory.na. The block is added at the beginning.nb. The block is added in the middle.nc. The block is added at the end.nd. The block is re
31、moved from the beginning.ne. The block is removed from the middle.nf. The block is removed from the end.nContiguous Linked Indexedn 201(100读写+1新写) 1（1新写） 1（1新写）n 101(50读写+1新写) 52（50读+第50块写+1新写） 1（1新写）n 1（1新写） 3（第100块读写+1新写） 1（1新写）n 198（99读写） 1（读第1块） 0n 98（后49块读写） 52（51读+第50块写） 0n 0 100（99读+1写） 012-c
32、ont.n12.2 Consider a system where free space is kept in a free-space list.na. Suppose that the pointer to the free-space list is lost. Can the system reconstruct the free-space list? Explain your answer.nb. Suggest a scheme to ensure that the pointer is never lost as a result of memory failure.na. I
33、n order to reconstruct the free list, it would be necessary to perform “garbage collection.” This would entail searching the entire directory structure to determine which pages are already allocated to jobs. Those remaining unallocated pages could be relinked as the free-space list.nb. The free-spac
34、e list pointer could be stored on the disk, perhaps in several places.12-cont.n12.3 What problems could occur if a system allowed a file system to be mounted simultaneously at more than one location?nThere would be multiple paths to the same file, which could confuse users or encourage mistakes (del
35、eting a file with one path deletes the file in all the other paths).n12.4 Why must the bit map for file allocation be kept on mass storage, rather than in main memory?nIn 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
36、 memory.12-cont.n12.5 Consider a system that supports the strategies of contiguous, linked, and indexed allocation. What criteria should be used in deciding which strategy is best utilized for a particular file?nContiguous if file is usually accessed sequentially, if file is relatively small.n Linke
37、d if file is large and usually accessed sequentially.n Indexed if file is large and usually accessed randomly.n12.6 Consider a file system on a disk that has both logical and physical block sizes of 512 bytes. Assume that the information about each file is already in memory. For each of the three al
38、location strategies (contiguous, linked, and indexed), answer these questions:na. How is the logical-to-physical address mapping accomplished in this system? (For the indexed allocation, assume that a file is always less than 512 blocks long.)nb. If we are currently at logical block 10 (the last blo
39、ck accessed was block 10) and want to access logical block 4, how many physical blocks must be read from the disk?na. Contiguous. Divide the logical address by 512 with X and Y the resulting quotient and remainder respectively.ni. Add X to Z to obtain the physical block number. Y is the displacement
40、 into that block.nii. 1nb. Linked. Divide the logical physical address by 511 with X and Y the resulting quotient and remainder respectively.ni. Chase down the linked list (getting X + 1blocks). Y + 1 is the displacement into the last physical block.nii. 4nc. Indexed. Divide the logical address by 5
41、12 with X and Y the resulting quotient and remainder respectively.ni. Get the index block into memory. Physical block address is contained in the index block at location X. Y is the displacement into the desired physical block.nii. 2Chapter 13n13.1 State three advantages of placing functionality in
42、a device controller, rather than in the kernel. State three disadvantages.nThree advantages: Bugs are less likely to cause an operating system crash Performance can be improved by utilizing dedicated hardware and hard-coded algorithms The kernel is simplified by moving algorithms out of itnThree dis
43、advantages: Bugs are harder to fix - a new firmware version or new hardware is needed Improving algorithms likewise require a hardware update rather than just kernel or device driver update Embedded algorithms could conflict with applications use of the device, causing decreased performance.13-cont.
44、n13.2 Consider the following I/O scenarios on a single-user PC.na. A mouse used with a graphical user interfacenb. A tape drive on a multitasking operating system (assume no device preallocation is available)nc. A disk drive containing user filesnd. A graphics card with direct bus connection, access
45、ible through memory-mapped I/O For each of these I/O scenarios, would you design the operating system to use buffering, spooling, caching, or a combination? Would you use polled I/O, or interrupt-driven I/O? Give reasons for your choices.na. Buffering may be needed to record mouse movement during ti
46、mes when higherpriority operations are taking place. Spooling and caching are inappropriate. Interrupt driven I/O is most appropriate.nb. Buffering may be needed to manage throughput difference between the tape drive and the source or destination of the I/O, Caching can be used to hold copies of dat
47、a that resides on the tape, for faster access. Spooling could be used to stage data to the device when multiple users desire to read from or write to it. Interrupt driven I/O is likely to allow the best performance.nc. Buffering can be used to hold data while in transit from user space to the disk,
48、and visa versa. Caching can be used to hold disk-resident data for improved performance. Spooling is not necessary because disks are shared-access devices. Interrupt driven I/O is best for devices such as disks that transfer data at slow rates.nd. Buffering may be needed to control multiple access a
49、nd for performance (double buffering can be used to hold the next screen image while displaying the current one). Caching and spooling are not necessary due to the fast and shared-access natures of the device. Polling and interrupts are only useful for input and for I/O completion detection, neither
50、 of which is needed for a memory-mapped device.13-cont.n13.4 Describe three circumstances under which blocking I/O should be used. Describe three circumstances under which nonblocking I/O should be used. Why not just implement nonblocking I/O and have processes busy-wait until their device is ready?
51、nGenerally, blocking I/O is appropriate when the process will only be waiting for one specific event. Examples include a disk, tape, or keyboard read by an application program. Non-blocking I/O is useful when I/Omay come from more than one source and the order of the I/O arrival is not predetermined
52、. Examples include network daemons listening to more than one network socket, window managers that accept mouse movement as well as keyboard input, and I/O-management programs, such as a copy command that copies data between I/O devices. In the last case, the program could optimize its performance b
53、y buffering the input and output and using non-blocking I/O to keep both devices fully occupied.nNon-blocking I/O is more complicated for programmers, because of the asynchonous rendezvous that is needed when an I/O occurs. Also, busy waiting is less efficient than interrupt-driven I/O so the overal
54、l system performance would decrease.13-cont.n13.5 Why might a system use interrupt-driven I/O to manage a single serial port, but polling I/O to manage a front-end processor, such as a terminal concentrator?nPolling can be more efficient than interrupt-driven I/O. This is the case when the I/O is fr
55、equent and of short duration. Even though a single serial port will perform I/O relatively infrequently and should thus use interrupts, a collection of serial ports such as those in a terminal concentrator can produce a lot of short I/O operations, and interrupting for each one could create a heavy
56、load on the system. A well-timed polling loop could alleviate that load without wasting many resources through looping with no I/O needed.n13.8 How does DMA increase system concurrency? How does it complicate hardware design?nDMA increases system concurrency by allowing the CPU to perform tasks whil
57、e the DMA system transfers data via the system and memory busses. Hardware design is complicated because the DMA controller must be integrated into the system, and the system must allow the DMA controller to be a bus master. Cycle stealing may also be necessary to allow the CPU and DMA controller to
58、 share use of the memory bus.Chapter 14n14.2 Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently serving a request at cylinder 143, and the previous request was at cylinder 125. The queue of pending requests, in FIFO order, is 86, 1470, 913, 1774, 948, 1509, 1022
59、, 1750, 130 Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following disk scheduling algorithms?na. FCFSnb. SSTFnc. SCANnd. LOOKne. C-SCANna. The FCFS schedule is 143, 86, 1470, 913, 1774
60、, 948, 1509, 1022, 1750, 130. The total seek distance is 7081.nb. The SSTF schedule is 143, 130, 86, 913, 948, 1022, 1470, 1509, 1750, 1774. The total seek distance is 1745.nc. The SCAN schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 130, 86. The total seek distance is 9769.nd. The LO
61、OK schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 86. The total seek distance is 3319.ne. The C-SCAN schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 86, 130. The total seek distance is 9813.nf. (Bonus.) The C-LOOK schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774,
62、 86, 130. The total seek distance is 3363.14-cont.n14.4 Suppose that the disk in Exercise 14.3 rotates at 7200 RPM.na. What is the average rotational latency of this disk drive?nb. What seek distance can be covered in the time that you found for part a?na. 7200 rpm gives 120 rotations per second. Th
63、us, a full rotation takes 8.33 ms, and the average rotational latency (a half rotation) takes 4.167 ms.14-cont.n14.5 The accelerating seek described in Exercise 14.3 is typical of hard-disk drives. By contrast, floppy disks (and many hard disks manufactured before the mid-1980s) typically seek at a
64、fixed rate. Suppose that the disk in Exercise 14.3 has a constant-rate seek rather than a constant-acceleration seek, so the seek time is of the form t = x + yL, where t is the time in milliseconds and L is the seek distance. Suppose that the time to seek to an adjacent cylinder is 1 millisecond, as
65、 before, and is 0.5 milliseconds for each additional cylinder.na. Write an equation for this seek time as a function of the seek distance.nb. Using the seek-time function from part a, calculate the total seek time for each of the schedules in Exercise 14.2. nc. What is the percentage speedup of the
66、fastest schedule over FCFS in this case?na. t = 0.95 + 0.05Lnb. FCFS 362.60; SSTF 95.80; SCAN 497.95; LOOK 174.50; C-SCAN 500.15; (and C-LOOK 176.70). SSTF is still the winner, and LOOK is the runner-up.nc. (362.60 95.80)/362.60 = 0.74 The percentage speedup of SSTF over FCFS is 74%,with respect to the seek time. If we include the overhead of rotational latency and data transfer, the percentage speedup will be less.25 以上有不当之处，请大家给与批评指正，以上有不当之处，请大家给与批评指正，谢谢大家！谢谢大家！
