操作系統(tǒng)精髓與設(shè)計(jì)原理第五版 課后題答案

Chapter2

OperatingSystem

OverviewReviewQuestionsConvenience:Anoperatingsystemmakesacomputermoreconvenienttouse.Efficiency:Anoperatingsystemallowsthecomputersystemresourcestobeusedinanefficientmanner.Abilitytoevolve:Anoperatingsystemshouldbeconstructedinsuchawayastopermittheeffectivedevelopment,testing,andintroductionofnewsystemfunctionswithoutinterferingwithservice.2.5Theexecutioncontext,orprocessstate,istheinternaldatabywhichtheoperatingsystemisabletosuperviseandcontroltheprocess.Thisinternalinformationisseparatedfromtheprocess,becausetheoperatingsystemhasinformationnotpermittedtotheprocess.Thecontextincludesalloftheinformationthattheoperatingsystemneedstomanagetheprocessandthattheprocessorneedstoexecutetheprocessproperly.Thecontextincludesthecontentsofthevariousprocessorregisters,suchastheprogramcounteranddataregisters.Italsoincludesinformationofusetotheoperatingsystem,suchasthepriorityoftheprocessandwhethertheprocessiswaitingforthecompletionofaparticularI/Oevent.ProblemsTheanswersarethesamefor(a)and(b).Assumethatalthoughprocessoroperationscannotoverlap,I/Ooperationscan.1Job:TAT=NTProcessorutilization=50%2Jobs:TAT=NTProcessorutilization=100%4Jobs:TAT=(2N-1)NTProcessorutilization=100%Asystemcallisusedbyanapplicationprogramtoinvokeafunctionprovidedbytheoperatingsystem.Typically,thesystemcallresultsintransfertoasystemprogramthatrunsinkernelmode.ChapterChapterProcessdescriptionandcontrolReviewQuestionsLessstateinformationisinvolved.Addressspace,fileresources,executionprivilegesareexamples.1.Threadswitchingdoesnotrequirekernelmodeprivilegesbecauseallofthethreadmanagementdatastructuresarewithintheuseraddressspaceofasingleprocess.Therefore,theprocessdoesnotswitchtothekernelmodetodothreadmanagement.Thissavestheoverheadoftwomodeswitches(usertokernel;kernelbacktouser).2.Schedulingcanbeapplicationspecific.Oneapplicationmaybenefitmostfromasimpleround-robinschedulingalgorithm,whileanothermightbenefitfromapriority-basedschedulingalgorithm.TheschedulingalgorithmcanbetailoredtotheapplicationwithoutdisturbingtheunderlyingOSscheduler.3.ULTscanrunonanyoperatingsystem.NochangesarerequiredtotheunderlyingkerneltosupportULTs.Thethreadslibraryisasetofapplication-levelutilitiessharedbyallapplications.1.Inatypicaloperatingsystem,manysystemcallsareblocking.Thus,whenaULTexecutesasystemcall,notonlyisthatthreadblocked,butalsoallofthethreadswithintheprocessareblocked.2.InapureULTstrategy,amultithreadedapplicationcannottakeadvantageofmultiprocessing.Akernelassignsoneprocesstoonlyoneprocessoratatime.Therefore,onlyasinglethreadwithinaprocesscanexecuteatatime.ProblemsBecause,withULTs,thethreadstructureofaprocessisnotvisibletotheoperatingsystem,whichonlyschedulesonthebasisofprocesses.Chapter5

Concurrency：Mutual

Exclusionand

SynchronizationReviewQuestionsCommunicationamongprocesses,sharingofandcompetingforresources,synchronizationoftheactivitiesofmultipleprocesses,andallocationofprocessortimetoprocesses.5.9Abinarysemaphoremayonlytakeonthevalues0and1.Ageneralsemaphoremaytakeonanyintegervalue.ProblemsABCDE;ABDCE;ABDEC;ADBCE;ADBEC;ADEBC;DEABC;DAEBC;DABEC;DABCEConsiderthecaseinwhichturnequals0andP(1)setsblocked[1]totrueandthenfindsblocked[0]settofalse.P(0)willthensetblocked[0]totrue,findturn=0,andenteritscriticalsection.P(1)willthenassign1toturnandwillalsoenteritscriticalsection.ChapterReviewQuestions6.2Mutualexclusion.Onlyoneprocessmayusearesourceatatime.Holdandwait.Aprocessmayholdallocatedresourceswhileawaitingassignmentofothers.Nopreemption.Noresourcecanbeforciblyremovedfromaprocessholdingit.Theabovethreeconditions,plus:Circularwait.Aclosedchainofprocessesexists,suchthateachprocessholdsatleastoneresourceneededbythenextprocessinthechain.Problems6.4a.00000750622ReviewQuestions6.2Mutualexclusion.Onlyoneprocessmayusearesourceatatime.Holdandwait.Aprocessmayholdallocatedresourceswhileawaitingassignmentofothers.Nopreemption.Noresourcecanbeforciblyremovedfromaprocessholdingit.Theabovethreeconditions,plus:Circularwait.Aclosedchainofprocessesexists,suchthateachprocessholdsatleastoneresourceneededbythenextprocessinthechain.Problems6.4a.0000075062220020320tod.Runningthebanker'salgorithm,weseeprocessescanfinishintheorderp1,p4,p5,p2,p3.e.Changeavailableto(2,0,0,0)andp3'srowof"stillneeds"to(6,5,2,2).Nowp1,p4,p5canfinish,butwithavailablenow(4,6,9,8)neitherp2norp3's"stillneeds"canbesatisfied.Soitisnotsafetograntp3'srequest.1.W=(2100)MarkP3;W=(2100)+(0120)=(2220)MarkP2;W=(2220)+(2001)=(4221)MarkP1;nodeadlockdetectedChapter7

MemoryManagementReviewQuestionsRelocation,protection,sharing,logicalorganization,physicalorganization.Alogicaladdressisareferencetoamemorylocationindependentofthecurrentassignmentofdatatomemory;atranslationmustbemadetoaphysicaladdressbeforethememoryaccesscanbeachieved.Arelativeaddressisaparticularexampleoflogicaladdress,inwhichtheaddressisexpressedasalocationrelativetosomeknownpoint,usuallythebeginningoftheprogram.Aphysicaladdress,orabsoluteaddress,isanactuallocationinmainmemory.Problemsa.The40Mblockfitsintothesecondhole,withastartingaddressof80M.The20Mblockfitsintothefirsthole,withastartingaddressof20M.The10Mblockisplacedatlocation120M.40M40M60M40M40M40M40M40M60M40M40M40MThethreestartingaddressesare230M,20M,and160M,forthe40M,20M,and10Mblocks,respectively.iiiillnrng240Mg240M60Mg￡60M40Mg30M40M40MThethreestartingaddressesare80M,120M,and160M,forthe40M,20M,and10Mblocks,respectively.7.127.12a.Thenumberofbytesinthelogicaladdressspaceis(216pages)(210bytes/page)=226bytes.Therefore,26bitsarerequiredforthelogicaladdress.Aframeisthesamesizeasapage,210bytes.Thenumberofframesinmainmemoryis(232bytesofmainmemory)/(210bytes/frame)=222frames.So22bitsisneededtospecifytheframe.Thereisoneentryforeachpageinthelogicaladdressspace.Thereforethereare216entries.Inadditiontothevalid/invalidbit,22bitsareneededtospecifytheframelocationinmainmemory,foratotalof23bits.5E40M40MEg￡60M40Mg30M40M40MThethreestartingaddressesare80M,230M,and360M,forthe40M,20M,and10Mblocks,respectively.Chapter8

VirtualMemoryReviewQuestionsSimplepaging:allthepagesofaprocessmustbeinmainmemoryforprocesstorun,unlessoverlaysareused.Virtualmemorypaging:notallpagesofaprocessneedbeinmainmemoryframesfortheprocesstorun.;pagesmaybereadinasneededAphenomenoninvirtualmemoryschemes,inwhichtheprocessorspendsmostofitstimeswappingpiecesratherthanexecutinginstructions.Problemsa.Splitbinaryaddressintovirtualpagenumberandoffset;useVPNasindexintopagetable;extractpageframenumber;concatenateoffsettogetphysicalmemoryaddress(i)1052=1024+28mapstoVPN1inPFN7,(7x1024+28=7196)2221=2x1024+173mapstoVPN2,pagefault5499=5x1024+379mapstoVPN5inPFN0,(0x1024+379=379)a.PFN3sinceloadedlongestagoattime20PFN1sincereferencedlongestagoattime160ClearRinPFN3(oldestloaded),clearRinPFN2(nextoldestloaded),victimPFNis0sinceR=0ReplacethepageinPFN3sinceVPN3(inPFN3)isusedfurthestinthefuturee.Thereare6faults,indicatedby**4000*2*42*1*0*32VPNof340002421032pagesin03444024210memoryin203300421LRUorder1242Chapter9

Uniprocessor

SchedulingReviewQuestions9.1Long-termscheduling:Thedecisiontoaddtothepoolofprocessestobeexecuted.Medium-termscheduling:Thedecisiontoaddtothenumberofprocessesthatarepartiallyorfullyinmainmemory.Short-termscheduling:ThedecisionastowhichavailableprocesswillbeexecutedbytheprocessorTurnaroundtimeisthetotaltimethatarequestspendsinthesystem(waitingtimeplusservicetime.Responsetimeistheelapsedtimebetweenthesubmissionofarequestuntiltheresponsebeginstoappearasoutput.ProblemsEachsquarerepresentsonetimeunit;thenumberinthesquarereferstothecurrently-runningprocess.FCFSRR,q=1RR,q=4SPNFCFSRR,q=1RR,q=4SPNSRTHRRNFeedback,q=1Feedback,q=2iAAABBBBBCCDDDDDEEEEEABABCABCBDBDEDEDEDEEAAABBBBCCBDDDDEEEEDEAAACCBBBBBDDDDDEEEEEAAACCBBBBBDDDDDEEEEEAAABBBBBCCDDDDDEEEEEABACBCABBDBDEDEDEDEEABAACBBCBBDDEDDEEDEEABCDETa013912Ts35255FCFSTf38101520Tr3.007.007.006.008.006.20Tr/Ts1.001.403.501.201.601.74RRq=1Tf6.0011.008.0018.0020.00Tr6.0010.005.009.008.007.60Tr/Ts2.002.002.501.801.601.98RRq=4Tf3.0010.009.0019.0020.00Tr3.009.006.0010.008.007.20Tr/Ts1.001.803.002.001.601.88SPNTf3.0010.005.0015.0020.00Tr3.009.002.006.008.005.60Tr/Ts1.001.801.001.201.601.32SRTTf3.0010.005.0015.0020.00Tr3.009.002.006.008.005.60Tr/Ts1.001.801.001.201.601.32HRRNTf3.008.0010.0015.0020.00Tr3.007.007.006.008.006.20Tr/Ts1.001.403.501.201.601.74FBq=1Tf7.0011.006.0018.0020.00Tr7.0010.003.009.008.007.40Tr/Ts2.332.001.501.801.601.85FBTf4.0010.008.0018.0020.00q=2iTr4.009.005.009.008.007.00Tr/Ts1.331.802.501.801.601.81

9.16a.Sequencewithwhichprocesseswillget1minofprocessortime:12345ElapsedtimeABCDE5ABCDE10ABCDE15ABDE19ABDE23ABDE27ABE30ABE33ABE36AE38AE40AE42A43A44A45Theturnaroundtimeforeachprocess:A=45min,B=35min,C=13min,D=26min,E=42minTurnaroundTimeTheaverageturnaroundtimeis=(45+35+13+26+42)/5=32.2minTurnaroundTime3B4E6A7C9D99+12=2121+15=3636+3=3939+6=45Theaverageturnaroundtimeis:(9+21+36+39+4b.5=30minPriorityJobc.JobTurnaroundTime"a15B15+9=24C24+3=27D27+6=33E33+12=45Theaverageturnaroundtimeis:(15+24+27+33+45)/5=28.8mind.

RunningTimeJobTurnaroundTime3C36D3+6=99B9+9=1812E18+12=3015A30+15=45Theaverageturnaroundtimeis:(3+9+18+30+45)/5=21minChapter10

Multiprocessorandreal-Time

SchedulingReviewQuestionsFine:Parallelisminherentinasingleinstructionstream.Medium:Parallelprocessingormultitaskingwithinasingleapplication.Coarse:Multiprocessingofconcurrentprocessesinamultiprogrammingenvironment.VeryCoarse:Distributedprocessingacrossnetworknodestoformasinglecomputingenvironment.Independent:Multipleunrelatedprocesses.Ahardreal-timetaskisonethatmustmeetitsdeadline;otherwiseitwillcauseundesirabledamageorafatalerrortothesystem.Asoftreal-timetaskhasanassociateddeadlinethatisdesirablebutnotmandatory;itstillmakessensetoscheduleandcompletethetaskevenifithaspasseditsdeadline.ProblemsForfixedpriority,wedothecaseinwhichthepriorityisA,B,C.Eachsquarerepresentsfivetimeunits;theletterinthesquarereferstothecurrently-runningprocess.Thefirstrowisfixedpriority;thesecondrowisearliestdeadlineschedulingusingcompletiondeadlines.AABBAACCAABBAACCAAAABBACCACAABBAACCCAAForfixedpriorityscheduling,processCalwaysmissesitsdeadline.10.4slockedT2T3byT1sunlockedsunlockedslockedbyTT2T3byT1sunlockedsunlockedslockedbyTOnceTentersitscriticalsection,itisassignedapriorityhigherthanT1.3WhenT3leavesitscriticalsection,itispreemptedbyT1.Chapter11I/OManagementanddiskSchedulingReviewQuestionsProgrammedI/O:TheprocessorissuesanI/Ocommand,onbehalfofaprocess,toanI/Omodule;thatprocessthenbusy-waitsfortheoperationtobecompletedbeforeproceeding.Interrupt-drivenI/O:TheprocessorissuesanI/Ocommandonbehalfofaprocess,continuestoexecutesubsequentinstructions,andisinterruptedbytheI/Omodulewhenthelatterhascompleteditswork.Thesubsequentinstructionsmaybeinthesameprocess,ifitisnotnecessaryforthatprocesstowaitforthecompletionoftheI/O.Otherwise,theprocessissuspendedpendingtheinterruptandotherworkisperformed.Directmemoryaccess(DMA):ADMAmodulecontrolstheexchangeofdatabetweenmainmemoryandanI/Omodule.TheprocessorsendsarequestforthetransferofablockofdatatotheDMAmoduleandisinterruptedonlyaftertheentireblockhasbeentransferred.Seektime,rotationaldelay,accesstime.ProblemsIfthecalculationtimeexactlyequalstheI/Otime(whichisthemostfavorablesituation),boththeprocessorandtheperipheraldevicerunningsimultaneouslywilltakehalfaslongasiftheyranseparately.Formally,letCbethecalculationtimefortheentireprogramandletTbethetotalI/Otimerequired.Thenthebestpossiblerunningtimewithbufferingismax(C,T),whiletherunningtimewithoutbufferingisC+T;andofcourse((C+T)/2)<max(C,T)<(C+T).Source:[KNUT97].

11.3Diskheadisinitiallymovinginthedirectionofdecreasingtracknumber:FIFOSSTFSCANC-SCANNexttrackNumberNexttrackNumberNexttrackNumberNexttrackNumberaccessedoftracksaccessedoftracksaccessedoftracksaccessedoftrackstraversedtraversedtraversedtraversed2773110106436643612910212010412341231101912992714271418676147181017101714739186391101001861764110664122120101473910314123129912918645427141471812091205610171863911010Average61.8Average29.1Average29.6Average38Ifthediskheadisinitiallymovinginthedirectionofincreasingtracknumber,onlytheSCANandC-SCANresultschange:SCANC-SCANNexttrackNumberNexttrackNumberaccessedoftracksaccessedoftrackstraversedtraversed1101011010120101201012991299147181471818639186396412210176412327172714411410176423Average29.1Average35.1Chapter12

FileManagementReviewQuestionsAfieldisthebasicelementofdatacontainingasinglevalue.Arecordisacollectionofrelatedfieldsthatcanbetreatedasaunitbysomeapplicationprogram.Pile:Dataarecollectedintheorderinwhichtheyarrive.Eachrecordconsistsofoneburstofdata.Sequentialfile:Afixedformatisusedforrecords.Allrecordsareofthesamelength,consistingofthesamenumberoffixed-lengthfieldsinaparticularorder.Becausethelengthandpositionofeachfieldisknown,onlythevaluesoffieldsneedtobestored;thefieldnameandlengthforeachfieldareattributesofthefilestructure.Indexedsequentialfile:Theindexedsequentialfilemaintainsthekeycharacteristicofthesequentialfile:recordsareorganizedinsequencebasedonakeyfield.Twofeaturesareadded;anindextothefiletosupportrandomaccess,andanoverflo