操作系统操作精髓与设计原理习题解答[1]pdf.pdf

《操作系统操作精髓与设计原理习题解答[1]pdf.pdf》由会员分享，可在线阅读，更多相关《操作系统操作精髓与设计原理习题解答[1]pdf.pdf（84页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、SOLUTIONS MANUALOPERATING SYSTEMS:INTERNALS AND DESIGN PRINCIPLESFIFTH EDITIONWILLIAM STALLINGSCopyright 2004:William Stallings-2-2004 by William StallingsAll rights reserved.No part of this document may be reproduced,in anyform or by any means,or posted on the Internet,without permission inwriting

2、from the author.-3-NOTICEThis manual contains solutions to all of the review questions andhomework problems in Operating Systems,Fifth Edition.If you spot anerror in a solution or in the wording of a problem,I would greatlyappreciate it if you would forward the information via email to me .An errata

3、 sheet for this manual,if needed,is available atftp:/ OF CONTENTSChapter 1:Computer System Overview.5Chapter 2:Operating System Overview.11Chapter 3:Process Description and Control.14Chapter 4:Threads,SMP,and Microkernels.18Chapter 5:Concurrency:Mutual Exclusion and Synchronization.21Chapter 6:Concu

4、rrency:Deadlock and Starvation.30Chapter 7:Memory Management.38Chapter 8:Virtual Memory.43Chapter 9:Uniprocessor Scheduling.51Chapter 10:Multiprocessor and Real-Time Scheduling.62Chapter 11:I/O Management and Disk Scheduling.65Chapter 12:File Management.71Chapter 13:Networking.74Chapter 14:Distribut

5、ed Processing,Client/Server,and Clusters.76Chapter 15:Distributed Process Management.79Chapter 16:Security.82-5-A A ANSWERS TO NSWERS NSWERS TO TO QQ QUESTIONSUESTIONSUESTIONS1.1 A main memory,which stores both data and instructions:an arithmetic and logicunit(ALU)capable of operating on binary data

6、;a control unit,which interprets theinstructions in memory and causes them to be executed;and input and output(I/O)equipment operated by the control unit.1.2 User-visible registers:Enable the machine-or assembly-language programmer tominimize main memory references by optimizing register use.For hig

7、h-levellanguages,an optimizing compiler will attempt to make intelligent choices of whichvariables to assign to registers and which to main memory locations.Some high-level languages,such as C,allow the programmer to suggest to the compiler whichvariables should be held in registers.Control and stat

8、us registers:Used by theprocessor to control the operation of the processor and by privileged,operatingsystem routines to control the execution of programs.1.3 These actions fall into four categories:Processor-memory:Data may be transferredfrom processor to memory or from memory to processor.Process

9、or-I/O:Data maybe transferred to or from a peripheral device by transferring between the processorand an I/O module.Data processing:The processor may perform some arithmeticor logic operation on data.Control:An instruction may specify that the sequence ofexecution be altered.1.4 An interrupt is a me

10、chanism by which other modules(I/O,memory)may interruptthe normal sequencing of the processor.1.5 Two approaches can be taken to dealing with multiple interrupts.The first is todisable interrupts while an interrupt is being processed.A second approach is todefine priorities for interrupts and to all

11、ow an interrupt of higher priority to cause alower-priority interrupt handler to be interrupted.1.6 The three key characteristics of memory are cost,capacity,and access time.1.7 Cache memory is a memory that is smaller and faster than main memory and thatis interposed between the processor and main

12、memory.The cache acts as a bufferfor recently used memory locations.1.8 Programmed I/O:The processor issues an I/O command,on behalf of a process,toan I/O module;that process then busy-waits for the operation to be completedbefore proceeding.Interrupt-driven I/O:The processor issues an I/O command o

13、nbehalf of a process,continues to execute subsequent instructions,and is interruptedby the I/O module when the latter has completed its work.The subsequentinstructions may be in the same process,if it is not necessary for that process towait for the completion of the I/O.Otherwise,the process is sus

14、pended pendingthe interrupt and other work is performed.Direct memory access(DMA):A DMACHAPTER 1COMPUTER SYSTEM OVERVIEW-6-module controls the exchange of data between main memory and an I/O module.The processor sends a request for the transfer of a block of data to the DMA moduleand is interrupted

15、only after the entire block has been transferred.1.9 Spatial locality refers to the tendency of execution to involve a number of memorylocations that are clustered.Temporal locality refers to the tendency for a processorto access memory locations that have been used recently.1.10 Spatial locality is

16、 generally exploited by using larger cache blocks and byincorporating prefetching mechanisms(fetching items of anticipated use)into thecache control logic.Temporal locality is exploited by keeping recently usedinstruction and data values in cache memory and by exploiting a cache hierarchy.A A ANSWER

17、S TO NSWERS NSWERS TO TO P P PROBLEMSROBLEMSROBLEMS1.1 Memory(contents in hex):300:3005;301:5940;302:7006Step 1:3005 IR;Step 2:3 ACStep 3:5940 IR;Step 4:3+2=5 ACStep 5:7006 IR;Step 6:AC Device 61.21.a.The PC contains 300,the address of the first instruction.This value is loadedin to the MAR.b.The va

18、lue in location 300(which is the instruction with the value 1940 inhexadecimal)is loaded into the MBR,and the PC is incremented.These twosteps can be done in parallel.c.The value in the MBR is loaded into the IR.2.a.The address portion of the IR(940)is loaded into the MAR.b.The value in location 940

19、 is loaded into the MBR.c.The value in the MBR is loaded into the AC.3.a.The value in the PC(301)is loaded in to the MAR.b.The value in location 301(which is the instruction with the value 5941)isloaded into the MBR,and the PC is incremented.c.The value in the MBR is loaded into the IR.4.a.The addre

20、ss portion of the IR(941)is loaded into the MAR.b.The value in location 941 is loaded into the MBR.c.The old value of the AC and the value of location MBR are added and theresult is stored in the AC.5.a.The value in the PC(302)is loaded in to the MAR.b.The value in location 302(which is the instruct

21、ion with the value 2941)isloaded into the MBR,and the PC is incremented.c.The value in the MBR is loaded into the IR.6.a.The address portion of the IR(941)is loaded into the MAR.b.The value in the AC is loaded into the MBR.c.The value in the MBR is stored in location 941.1.3a.224=16 MBytesb.(1)If th

22、e local address bus is 32 bits,the whole address can be transferred atonce and decoded in memory.However,since the data bus is only 16 bits,itwill require 2 cycles to fetch a 32-bit instruction or operand.-7-(2)The 16 bits of the address placed on the address bus cant access the wholememory.Thus a m

23、ore complex memory interface control is needed to latch thefirst part of the address and then the second part(since the microprocessor willend in two steps).For a 32-bit address,one may assume the first half willdecode to access a row in memory,while the second half is sent later to accessa column i

24、n memory.In addition to the two-step address operation,themicroprocessor will need 2 cycles to fetch the 32 bit instruction/operand.c.The program counter must be at least 24 bits.Typically,a 32-bit microprocessorwill have a 32-bit external address bus and a 32-bit program counter,unless on-chip segm

25、ent registers are used that may work with a smaller program counter.If the instruction register is to contain the whole instruction,it will have to be32-bits long;if it will contain only the op code(called the op code register)thenit will have to be 8 bits long.1.4 In cases(a)and(b),the microprocess

26、or will be able to access 216=64K bytes;theonly difference is that with an 8-bit memory each access will transfer a byte,whilewith a 16-bit memory an access may transfer a byte or a 16-byte word.For case(c),separate input and output instructions are needed,whose execution will generateseparate I/O s

27、ignals(different from the memory signals generated with theexecution of memory-type instructions);at a minimum,one additional output pinwill be required to carry this new signal.For case(d),it can support 28=256 inputand 28=256 output byte ports and the same number of input and output 16-bitports;in

28、 either case,the distinction between an input and an output port is definedby the different signal that the executed input or output instruction generated.1.5 Clock cycle=18 MHz=125 nsBus cycle=4 125 ns=500 ns2 bytes transferred every 500 ns;thus transfer rate=4 MBytes/secDoubling the frequency may

29、mean adopting a new chip manufacturing technology(assuming each instructions will have the same number of clock cycles);doublingthe external data bus means wider(maybe newer)on-chip data bus drivers/latchesand modifications to the bus control logic.In the first case,the speed of the memorychips will

30、 also need to double(roughly)not to slow down the microprocessor;inthe second case,the wordlength of the memory will have to double to be able tosend/receive 32-bit quantities.1.6a.Input from the Teletype is stored in INPR.The INPR will only accept data fromthe Teletype when FGI=0.When data arrives,

31、it is stored in INPR,and FGI isset to 1.The CPU periodically checks FGI.If FGI=1,the CPU transfers thecontents of INPR to the AC and sets FGI to 0.When the CPU has data to send to the Teletype,it checks FGO.If FGO=0,the CPU must wait.If FGO=1,the CPU transfers the contents of the AC toOUTR and sets

32、FGO to 0.The Teletype sets FGI to 1 after the word is printed.b.The process described in(a)is very wasteful.The CPU,which is much fasterthan the Teletype,must repeatedly check FGI and FGO.If interrupts are used,the Teletype can issue an interrupt to the CPU whenever it is ready to accept orsend data

33、.The IEN register can be set by the CPU(under programmer control)-8-1.7 If a processor is held up in attempting to read or write memory,usually no damageoccurs except a slight loss of time.However,a DMA transfer may be to or from adevice that is receiving or sending data in a stream(e.g.,disk or tap

34、e),and cannotbe stopped.Thus,if the DMA module is held up(denied continuing access to mainmemory),data will be lost.1.8 Let us ignore data read/write operations and assume the processor only fetchesinstructions.Then the processor needs access to main memory once everymicrosecond.The DMA module is tr

35、ansferring characters at a rate of 1200characters per second,or one every 833 s.The DMA therefore steals every 833rdcycle.This slows down the processor approximately 1833100%=0.12%1.9a.The processor can only devote 5%of its time to I/O.Thus the maximum I/Oinstruction execution rate is 106 0.05=50,00

36、0 instructions per second.The I/Otransfer rate is therefore 25,000 words/second.b.The number of machine cycles available for DMA control is106(0.05 5+0.95 2)=2.15 106If we assume that the DMA module can use all of these cycles,and ignore anysetup or status-checking time,then this value is the maximu

37、m I/O transferrate.1.10 a.A reference to the first instruction is immediately followed by a reference to thesecond.b.The ten accesses to ai within the inner for loop which occur within a shortinterval of time.1.11DefineCi=Average cost per bit,memory level iSi=Size of memory level iTi=Time to access

38、a word in memory level iHi=Probability that a word is in memory i and in no higher-level memoryBi=Time to transfer a block of data from memory level(i+1)to memory level iLet cache be memory level 1;main memory,memory level 2;and so on,for a totalof N levels of memory.Then Cs=CiSii=1NSii=1NThe deriva

39、tion of Ts is more complicated.We begin with the result fromprobability theory that:Expected Value of x=iPr x=1i=1N-9-We can write:Ts=TiHii=1NWe need to realize that if a word is in M1(cache),it is read immediately.If it is inM2 but not M1,then a block of data is transferred from M2 to M1 and then r

40、ead.Thus:T2=B1+T1FurtherT3=B2+T2=B1+B2+T1Generalizing:Ti=Bj+T1j=1i1So Ts=BjHi()j=1i1i=2N+T1Hii=1NBut Hii=1N=1Finally Ts=BjHi()j=1i1i=2N+T11.12 a.Cost=Cm 8 106=8 103 =$80b.Cost=Cc 8 106=8 104 =$800c.From Equation 1.1:1.1 T1=T1+(1 H)T2(0.1)(100)=(1 H)(1200)H=1190/12001.13There are three cases to consi

41、der:Location of referenced wordProbabilityTotal time for access in nsIn cache0.920Not in cache,but in mainmemory(0.1)(0.6)=0.0660+20=80Not in cache or main memory(0.1)(0.4)=0.0412ms+60+20=12,000,080So the average access time would be:Avg=(0.9)(20)+(0.06)(80)+(0.04)(12000080)=480026 ns-10-1.14Yes,if

42、the stack is only used to hold the return address.If the stack is also used topass parameters,then the scheme will work only if it is the control unit thatremoves parameters,rather than machine instructions.In the latter case,theprocessor would need both a parameter and the PC on top of the stack at

43、 the sametime.-11-A A ANSWERS TO NSWERS NSWERS TO TO QQ QUESTIONSUESTIONSUESTIONS2.1 Convenience:An operating system makes a computer more convenient to use.Efficiency:An operating system allows the computer system resources to be usedin an efficient manner.Ability to evolve:An operating system shou

44、ld beconstructed in such a way as to permit the effective development,testing,andintroduction of new system functions without interfering with service.2.2 The kernel is a portion of the operating system that includes the most heavily usedportions of software.Generally,the kernel is maintained perman

45、ently in mainmemory.The kernel runs in a privileged mode and responds to calls from processesand interrupts from devices.2.3 Multiprogramming is a mode of operation that provides for the interleavedexecution of two or more computer programs by a single processor.2.4 A process is a program in executi

46、on.A process is controlled and scheduled by theoperating system.2.5 The execution context,or process state,is the internal data by which the operatingsystem is able to supervise and control the process.This internal information isseparated from the process,because the operating system has informatio

47、n notpermitted to the process.The context includes all of the information that theoperating system needs to manage the process and that the processor needs toexecute the process properly.The context includes the contents of the variousprocessor registers,such as the program counter and data register

48、s.It also includesinformation of use to the operating system,such as the priority of the process andwhether the process is waiting for the completion of a particular I/O event.2.6 Process isolation:The operating system must prevent independent processes frominterfering with each others memory,both d

49、ata and instructions.Automaticallocation and management:Programs should be dynamically allocated across thememory hierarchy as required.Allocation should be transparent to theprogrammer.Thus,the programmer is relieved of concerns relating to memorylimitations,and the operating system can achieve eff

50、iciency by assigning memoryto jobs only as needed.Support of modular programming:Programmers should beable to define program modules,and to create,destroy,and alter the size ofmodules dynamically.Protection and access control:Sharing of memory,at anylevel of the memory hierarchy,creates the potentia