《操作系统概念》第六版作业解答3.ppt

1、Chapter 9,9.3 Describe the following allocation algorithms: a. First fit b. Best fit c. Worst fit First fit:搜索可用内存列表，分配第一块足够大的 Best fit:搜索整个可用内存块，分配最小足够大的 Worst fit:搜索整个可用内存块，分配最大足够大的,9-cont.,9.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? First fit 212 -500(288) 417 -600(183) 112 -288 426 -none Best fit 212 -300 417 -500 112 -200 426 -600 Worst fit 212 -600(388) 417 -500 112 -388 426 -n

3、one,9-cont.,9.10 Consider a paging system with the page table stored in memory. a. If a memory reference takes 200 nanoseconds, how long does a paged memory reference take? b. 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.) a. 400, 200(page table)+200(access word) b. 250, 75%*200+25%*(200+200),9-cont.,9.16 Consider the following segment table: What are the physical addresse

5、s for the following logical addresses? a. 0,430 b. 1,10 c. 2,500 d. 3,400 e. 4,112 a. 430100, illegal d. 40096, illegal,9-cont.,9.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 key) associated with i

6、t. 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? a. Bare machine b. Single-user system c. Multiprogramming

7、 with a fixed number of processes d. Multiprogramming with a variable number of processes e. Paging f. Segmentation a. Protection not necessary, set system key to 0. b. Set system key to 0 when in supervisor mode. c. Region sizes must be fixed in increments of 2k bytes, allocate key with memory bloc

8、ks. d. Same as above. e. Frame sizes must be in increments of 2k bytes, allocate key with pages. f. Segment sizes must be in increments of 2k bytes, allocate key with segments.,Chapter 10,10.1 Under what circumstances do page faults occur? Describe the actions taken by the operating system when a pa

9、ge fault occurs. A page fault occurs when an access to a page that has not been brought into main memory takes place. The operating system verifies 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

10、free frame. Upon completion of I/O, the process table and page table are updated and the instruction is restarted.,10-cont.,10.6 Consider the following page-replacement algorithms. Rank these algorithms on a five point scale from “bad” to “perfect” according to their page-fault rate. Separate those

11、algorithms that suffer from Beladys anomaly from those that do not. a. LRU replacement b. FIFO replacement c. Optimal replacement d. Second-chance replacement Rank Algorithm Suffer from Beladys anomaly 1 Optimal no 2 LRU no 3 Second-chance yes 4 FIFO yes,10-cont.,10.9 Consider a demand-paging system

12、 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. a. Install a faster CPU. b. Install a bigger paging disk. c. Increase the degree of multiprogrammin

13、g. d. Decrease the degree of multiprogramming. 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.,10-cont.,10.10 Consider the two-dimensional array A: int A = new int10

14、0100; 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 following array-initializat

15、ion loops, using LRU replacement, and assuming page frame 1 has the process in it, and the other two are 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; a. 100 x50 b. 50,10-cont.,10.11 Consider the f

16、ollowing 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 unique pages will

17、all cost one fault each. LRU replacement FIFO replacement Optimal replacement Number of frames LRU FIFO Optimal 1 20 20 20 2 18 18 15 3 15 16 11 4 10 14 8 5 8 10 7 6 7 10 7 7 7 7 7,Chapter 11,11.3 Why do some systems keep track of the type of a file, while others leave it to the user or simply do no

18、t implement multiple file types? Which system is “better?” Some 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 interpretation of a files da

19、ta 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 the operating system to

20、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 maximum freedom to the pro

21、cesses on the system.,11-cont.,11.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 scheme. If your answer

22、 is no, explain what prevents your simulations success. How would your answer change if file names were limited to seven characters? If arbitrarily long names can be used then it is possible to simulate a multilevel directory structure. This can be done, for example, by using the character “.” to in

23、dicate 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 general, the answer is no

24、. 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.,11.9 Give an example of an application i

25、n which data in a file should be accessed in the following order: a. Sequentially b. Randomly a. Print the content of the file. b. Print the content of record i. This record can be found using hashing or index techniques. 11.12 Consider a system that supports 5000 users. Suppose that you want to all

26、ow 4990 of these users to be able to access one file. a. How would you specify this protection scheme in UNIX? b. Could you suggest another protection scheme that can be used more effectively for this purpose than the scheme provided by UNIX? a. There are two methods for achieving this: i. Create an

27、 access control list with the names of all 4990 users. ii. 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. b. The universe access information applies to all users unless their name appear

28、s 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 12,12.1 Consider a file currently consisting of 100 blocks. Assume that the file control block

29、 (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 allocation case, assume th

30、at 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. a. The block is added at the beginning. b. The block is added in the middle. c. The block is added at the end. d. The block is removed from the begin

31、ning. e. The block is removed from the middle. f. The block is removed from the end. Contiguous Linked Indexed 201(100读写+1新写) 1（1新写） 1（1新写） 101(50读写+1新写) 52（50读+第50块写+1新写） 1（1新写） 1（1新写） 3（第100块读写+1新写） 1（1新写） 198（99读写） 1（读第1块） 0 98（后49块读写） 52（51读+第50块写） 0 0 100（99读+1写） 0,12-cont.,12.2 Consider a syst

32、em where free space is kept in a free-space list. a. Suppose that the pointer to the free-space list is lost. Can the system reconstruct the free-space list? Explain your answer. b. Suggest a scheme to ensure that the pointer is never lost as a result of memory failure. a. In order to reconstruct th

33、e 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. b. The free-space list pointer could be s

34、tored on the disk, perhaps in several places.,12-cont.,12.3 What problems could occur if a system allowed a file system to be mounted simultaneously at more than one location? There would be multiple paths to the same file, which could confuse users or encourage mistakes (deleting a file with one pa

35、th deletes the file in all the other paths). 12.4 Why must the bit map for file allocation be kept on mass storage, rather than in main memory? 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-cont.,12.5 C

36、onsider 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? Contiguous if file is usually accessed sequentially, if file is relatively small. Linked if file is large and u

37、sually accessed sequentially. Indexed if file is large and usually accessed randomly. 12.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 allocation strategies (cont

38、iguous, linked, and indexed), answer these questions: a. 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.) b. If we are currently at logical block 10 (the last block accessed was block 10)

39、 and want to access logical block 4, how many physical blocks must be read from the disk? a. Contiguous. Divide the logical address by 512 with X and Y the resulting quotient and remainder respectively. i. Add X to Z to obtain the physical block number. Y is the displacement into that block. ii. 1 b

40、. Linked. Divide the logical physical address by 511 with X and Y the resulting quotient and remainder respectively. i. Chase down the linked list (getting X + 1blocks). Y + 1 is the displacement into the last physical block. ii. 4 c. Indexed. Divide the logical address by 512 with X and Y the resul

41、ting quotient and remainder respectively. i. 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. ii. 2,Chapter 13,13.1 State three advantages of placing functionality in a device controller, rat

42、her than in the kernel. State three disadvantages. Three 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 it Three disadvantages: Bugs are har

43、der 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.,13.2 Consider the foll

44、owing I/O scenarios on a single-user PC. a. A mouse used with a graphical user interface b. A tape drive on a multitasking operating system (assume no device preallocation is available) c. A disk drive containing user files d. A graphics card with direct bus connection, accessible through memory-map

45、ped 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. a. Buffering may be needed to record mouse movement during times when higherpriority

46、 operations are taking place. Spooling and caching are inappropriate. Interrupt driven I/O is most appropriate. b. 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 data that resides on the t

47、ape, 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. c. Buffering can be used to hold data while in transit from user space to the disk, and visa versa. Caching

48、 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. d. Buffering may be needed to control multiple access and for performance (dou

49、ble 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 of which is needed for

50、 a memory-mapped device.,13-cont.,13.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? Generally, blocking I

51、/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. Examples include net

52、work 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 by buffering the input

53、and output and using non-blocking I/O to keep both devices fully occupied. Non-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 overall system performance w

54、ould decrease.,13-cont.,13.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? Polling can be more efficient than interrupt-driven I/O. This is the case when the I/O is frequent and of short d

55、uration. 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 load on the system. A

56、 well-timed polling loop could alleviate that load without wasting many resources through looping with no I/O needed. 13.8 How does DMA increase system concurrency? How does it complicate hardware design? DMA increases system concurrency by allowing the CPU to perform tasks while the DMA system tran

57、sfers 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 share use of the mem

58、ory bus.,Chapter 14,14.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, 1750, 130 Starting

59、 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? a. FCFS b. SSTF c. SCAN d. LOOK e. C-SCAN 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, 175