《操作系统概念》第六版作业解答3省名师优质课赛课获奖课件市赛课一等奖课件.ppt

Chapter 9n9.3 Describe the following allocation algorithms:na.First fitnb.Best fitnc.Worst fitnFirst fit:搜索可用内存列表，分配第一块足够大nBest fit:搜索整个可用内存块，分配最小足够大nWorst fit:搜索整个可用内存块，分配最大足够大第1页9-cont.n9.5 Given memory partitions of 100K,500K,200K,300K,and 600K(in order),how would each of the First-fit,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-none第2页9-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 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)第3页9-cont.n9.16 Consider the following segment table:nWhat are the physical addresses for the following logical addresses?na.0,430nb.1,10nc.2,500nd.3,400ne.4,112na.430600,219+430=649nb.10100,illegalnd.40096,illegal第4页9-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 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 systemnc.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,allocate 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.第5页Chapter 10n10.1 Under what circumstances do page faults occur?Describe the actions taken by the operating 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 the needed page into the free frame.Upon completion of I/O,the process table and page table are updated and the instruction is restarted.第6页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-fault 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 yes第7页10-cont.n10.9 Consider 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 degree 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.第8页10-cont.n10.10 Consider the two-dimensional array 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 following 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.100 x50b.50第9页10-cont.n10.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 unique 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 7第10页Chapter 11n11.3 Why do some systems keep track of the type of a file,while others leave it to the 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 interpretation 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 the 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 maximum freedom to the processes on the system.第11页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 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 the 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 general,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.第12页11-cont.n11.9 Give an example 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 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 achieving 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 unless 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.第13页Chapter 12n12.1 Consider a file currently consisting of 100 blocks.Assume that the 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 allocation 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 removed 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写）0第14页12-cont.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.In 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-space list pointer could be stored on the disk,perhaps in several places.第15页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(deleting 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 memory.第16页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 Linked 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 allocation 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 block 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 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 512 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.2第17页Chapter 13n13.1 State three advantages of placing functionality in 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 disadvantages: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.第18页13-cont.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,accessible 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 times 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 data 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,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 and 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 of which is needed for a memory-mapped device.第19页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?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.Examples i