操作系统第九版部分课后作业习题答案分析解析

CHAPTER 9 Virtual MemoryPracticeExercisesUnderwhatcircumstancesdopagefaultsoccur?Describetheactionstakenbytheoperatingsystemwhenapagefaultoccurs.Answer:Apagefaultoccurswhenanaccesstoapagethathasnotbeenbroughtintomainmemorytakesplace.Theoperatingsystemveriesthememoryaccess,abortingtheprogramifitisinvalid.Ifitisvalid,afreeframeislocatedandI/Oisrequestedtoreadtheneededpageintothefreeframe.UponcompletionofI/O,theprocesstableandpagetableareupdatedandtheinstructionisrestarted.Assumethatyouhaveareferencestringforaprocesswithmframes(initiallyallempty).Thereferencestringhaslengthp;ndistinctpagenumbersoccurinit.Answerthesequestionsforreplacementalgorithms:Whatisalowerboundonthenumberofpagefaults?Whatisanupperboundonthenumberofpagefaults?Answer:npConsiderthepagetableshowninFigure9.30forasystemwith12-bitvirtualandphysicaladdressesandwith256-bytepages.ThelistoffreepageframesisD,E,F(thatis,Disattheheadofthelist,Eissecond,andFislast).Convertthefollowingvirtualaddressestotheirequivalentphysicaladdressesinhexadecimal.Allnumbersaregiveninhexadecimal.dashforapageframeindicatesthatthepageisnotinmemory.)9EF1112930Chapter9VirtualMemory7000FFAnswer:9EF-0EF111-211700-D000FF-EFFConsiderthefollowingreplacementalgorithms.Rankalgorithmsonafive-pointscalefrom“bad”to“perfect”accordingtotheirfaultrate.SeparatethosealgorithmsthatsufferfromBelady’sanomalyfromthosethatdonot.LRUreplacementFIFOreplacementOptimalreplacementSecond-chancereplacementAnswer:RankAlgorithmSufferfromBelady’sanomalyOptimalnoLRUnoSecond-chanceyesFIFOyesDiscussthehardwaresupportrequiredtosupportdemandpaging.Answer:Foreverymemory-accessoperation,thepagetableneedstobeconsultedtocheckwhetherthecorrespondingpageisresidentornotandwhethertheprogramhasreadorwriteprivilegesforaccessingthepage.Thesecheckshavetobeperformedinhardware.ATLBcouldserveasacacheandimprovetheperformanceofthelookupoperation.Anoperatingsystemsupportsapagedvirtualmemory,usingacentralprocessorwithacycletimeof1microsecond.Itcostsanadditional1microsecondtoaccessapageotherthanthecurrentone.Pageshave1000words,andthepagingdeviceisadrumthatrotatesat3000revolutionsperminuteandtransfers1millionwordspersecond.Thefollowingstatisticalmeasurementswereobtainedfromthesystem:1percentofallinstructionsexecutedaccessedapageotherthanthecurrentpage.•Oftheinstructionsthataccessedanotherpage,80percentaccessedapagealreadyinmemory.PracticeExercises31•Whenanewpagewasrequired,thereplacedpagewasmodified50percentofthetime.Calculatetheeffectiveinstructiontimeonthissystem,assumingthatsystemisrunningoneprocessonlyandthattheprocessorisidleduringdrumtransfers.Answer:effectiveaccesstime=0.99×(1 sec+0.008×(2 sec)+0.002×(10,000 sec+1,000 sec)+0.001×(10,000 sec+1,000 sec)=(0.99+0.016+22.0+11.0)sec=34.0 secConsiderthetwo-dimensionalarrayA:intA[][]=newint[100][100];whereA[0][0]isatlocation200inapagedmemorysystemwithpagesofsize200.Asmallprocessthatmanipulatesthematrixresidesinpage0(locations0to199).Thus,everyinstructionfetchwillbefrompage0.Forthreepageframes,howmanypagefaultsaregeneratedbythefollowingarray-initializationloops,usingLRUreplacementandassumingthatpageframe1containstheprocessandtheotherareinitiallyempty?a.for(intj=0;j<100;for(inti=0;i<100;i++)A[i][j]=0;b.for(inti=0;i<100;for(intj=0;j<100;j++)A[i][j]=0;Answer:a.5,000b.50Considerthefollowingpagereferencestring:1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6.Howmanypagefaultswouldoccurforthefollowingreplacementalgorithms,assumingone,two,three,four,five,six,orsevenframes?Rememberallframesareinitiallyempty,soyourfirstuniquepageswillallcostonefaulteach.•LRUreplacementFIFOreplacement•Optimalreplacement32Chapter9VirtualMemoryAnswer:NumberofframesLRUFIFOOptimal12020202181815315161141014858107671077777Supposethatyouwanttouseapagingalgorithmthatrequiresreferencebit(suchassecond-chancereplacementorworking-setmodel),butthehardwaredoesnotprovideone.Sketchhowyoucouldsimulatereferencebitevenifonewerenotprovidedbythehardware,orexplainwhyitisnotpossibletodoso.Ifitispossible,calculatewhatthecostwouldbe.Answer:Youcanusethevalid/invalidbitsupportedinhardwaretosimulatethereferencebit.Initiallysetthebittoinvalid.rstreferenceatraptotheoperatingsystemisgenerated.Theoperatingsystemwillsetasoftwarebitto1andresetthevalid/invalidbittovalid.Youhavedevisedanewreplacementalgorithmthatyouthinkmaybeoptimal.Insomecontortedtestcases,Belady’sanomalyoccurs.Isthenewalgorithmoptimal?ExplainyourAnswer:No.AnoptimalalgorithmwillnotsufferfromBelady’sanomalybecause—bydefinition—anoptimalalgorithmreplacesthepagethatwillnotbeusedforthelongesttime.Belady’sanomalyoccurswhenapagereplacementalgorithmevictsapagethatwillbeneededintheimmediatefuture.Anoptimalalgorithmwouldnothaveselectedsuchapage.Segmentationissimilartopagingbutvariable-sized“pages.”Definetwosegment-replacementalgorithmsbasedonFIFOandLRUpagereplacementschemes.Rememberthatsincesegmentsarenotthesamesize,thesegmentthatischosentobereplacedmaynotbebigenoughtoleaveenoughconsecutivelocationsfortheneededsegment.Considerstrategiesforsystemswheresegmentscannotberelocated,andthoseforsystemswheretheycan.Answer:FIFO.Findthefirstsegmentlargeenoughtoaccommodatetheincomingsegment.Ifrelocationisnotpossibleandnoonesegmentislargeenough,selectacombinationofsegmentswhosememoriesarecontiguous,whichare“closesttothefirstofthelist”andwhichcanaccommodatethenewsegment.Ifrelocationispossible,rearrangethememorysothatthefirstNsegmentslargeenoughfortheincomingsegmentarecontiguousinmemory.Addanyleftoverspacetothefree-spacelistinbothcases.PracticeExercises33LRU.Selectthesegmentthathasnotbeenusedforthelongestperiodoftimeandthatislargeenough,addinganyleftoverspacetothefreespacelist.Ifnoonesegmentislargeenough,selectacombinationofthe“oldest”segmentsthatarecontiguousinmemory(ifrelocationisnotavailable)andthatarelargeenough.Ifrelocationisavailable,rearrangetheoldestNsegmentstobecontiguousinmemoryandreplacethosewiththenewsegment.Considerademanddcomputersystemwherethedegreeofmultiprogrammingiscurrentlyfixedatfour.ThesystemwasrecentlymeasuredtodetermineutilizationofCPUandthepagingdisk.Theresultsareoneofthefollowingalternatives.Foreachcase,whatishappening?CanthedegreeofmultiprogrammingbeincreasedtoincreasetheCPUutilization?Isthepaginghelping?CPUutilization13percent;diskutilization97percentCPUutilization87percent;diskutilization3percentCPUutilization13percent;diskutilization3percentAnswer:Thrashingisoccurring.CPUutilizationissufficientlyhightoleavethingsalone,andincreasedegreeofmultiprogramming.Increasethedegreeofmultiprogramming.Wehaveanoperatingsystemforamachinethatusesbaseandlimitregisters,butwehavemodifiedthemachinetoprovideapagetable.Canthepagetablesbesetuptosimulatebaseandlimitregisters?Howcantheybe,orwhycantheynotbe?Answer:Thepagetablecanbesetuptosimulatebaseandlimitregistersprovidedthatthememoryisallocatedinfixed-sizesegments.Inthisway,thebaseofasegmentcanbeenteredintothepagetableandthevalid/invalidbitusedtoindicatethatportionofthesegmentasresidentinthememory.Therewillbesomeproblemwithinternalfragmentation.9.27.Considerademand-pagingsystemwiththefollowingtime-measuredutilizations:CPUutilization20%Pagingdisk97.7%OtherI/OdevicesWhich(ifany)ofthefollowingwill(probably)improveCPUutilization?Explainyouranswer.InstallafasterCPU.Installabiggerpagingdisk.Increasethedegreeofmultiprogramming.Decreasethedegreeofmultiprogramming.Installmoremainmemory.Installafasterharddiskormultiplecontrollerswithmultipledisks.Addprepagingtothepagefetchalgorithms.Increasethepagesize.Answer:Thesystemobviouslyisspendingmostofitstimepaging,indicatingover-allocationofmemory.IfthelevelofmultiprogrammingisreducedresidentprocesseswouldpagefaultlessfrequentlyandtheCPUutilizationwouldimprove.Anotherwaytoimproveperformancewouldbetogetmorephysicalmemoryorafasterpagingdrum.GetafasterCPU—No.Getabiggerpagingdrum—No.Increasethedegreeofmultiprogramming—No.Decreasethedegreeofmultiprogramming—Yes.Installmoremainmemory—LikelytoimproveCPUutilizationmorepagescanremainresidentandnotrequirepagingtoorfromthedisks.Installafasterharddisk,ormultiplecontrollerswithmultipledisks—Alsoanimprovement,forasthediskbottleneckisremovedbyfasterresponseandmorethroughputtothedisks,theCPUwillgetmoredatamorequickly.Addprepagingtothepagefetchalgorithms—Again,theCPUwillgetmoredatafaster,soitwillbemoreinuse.Thisisonlythecaseifthepagingactionisamenabletoprefetching(i.e.,someoftheaccessissequential).Increasethepagesize—Increasingthepagesizewillresultinpagefaultsifdataisbeingaccessedsequentially.Ifdataaccessismoreorlessrandom,morepagingactioncouldensuebecausefewerpagescanbekeptinmemoryandmoredataistransferredperpagefault.Sothischangeisaslikelytodecreaseutilizationasitistoincreaseit.10.110.1、Isdiskscheduling,otherthanFCFSscheduling,usefulinasingle-usersingle-userenvironment?Explainyourenvironment?Explainyouranswer.Answer:Answer:Inasingle-userenvironment,theI/Oqueueusuallyisempty.RequestsRequestsgenerallyarrivefromasingleprocessforoneblockorforaperformingconcurrentI/O,suchaswhenaWebbrowserretrievesdatainthebackgroundwhiletheoperatingsystemispagingandanothersequenceofconsecutiveblocks.Inthesecases,FCFSisaneconomicalmethodofdiskscheduling.ButperformingconcurrentI/O,suchaswhenaWebbrowserretrievesdatainthebackgroundwhiletheoperatingsystemispagingandanotherapplicationisactiveintheforeground.10.2.Explain10.2.ExplainwhySSTFschedulingtendstofavormiddlecylindersovertheovertheinnermostandoutermostinnermostandoutermostcylinders.The center of the disk is the location having the The center of the disk is the location having the smallesttheheadisnotinthecenterofthediskandanewrequestarrives,thenewrequestismorelikelytobeinthegroupthatincludesthecenteraveragedistancetotheheadisnotinthecenterofthediskandanewrequestarrives,thenewrequestismorelikelytobeinthegroupthatincludesthecenterofthedisk;thus,theheadismorelikelytomoveinthatdirection.10.11Supposethatadiskdrivehas5000cylinders,numbered0to4999.Thedriveiscurrentlyservingarequestatcylinder143,andthepreviousrequestwasatcylinder125.Thequeueofpendingrequests,inFIFOorder,is86,1470,913,1774,948,1509,1022,1750,130Startingfromthecurrentheadposition,whatisthetotaldistance(incylinders)thatthediskarmmovestosatisfyallthependingrequests,foreachofthefollowingdisk-schedulingalgorithms?FCFSSSTFSCANLOOKC-SCANAnswer:a.TheFCFSscheduleis143,86,1470,913,1774,948,1509,1022,1750,130.Thetotalseekdistanceis7081.b.TheSSTFscheduleis143,130,86,913,948,1022,1470,1509,1750,1774.Thetotalseekdistanceis1745.c.TheSCANscheduleis143,913,948,1022,1470,1509,1750,1774,4999,130,86.Thetotalseekdistanceis9769.d.TheLOOKscheduleis143,913,948,1022,1470,1509,1750,1774,130,86.Thetotalseekdistanceis3319.e.TheC-SCANscheduleis143,913,948,1022,1470,1509,1750,1774,4999,86,130.Thetotalseekdistanceis9813.f.(Bonus.)TheC-LOOKscheduleis143,913,948,1022,1470,1509,1750,1774,86,130.Thetotalseekdistanceis3363.12CHAPTER12CHAPTERImplementationPracticeExercises12.1Considerafilecurrentlyconsistingof100blocks.Assumethatthe12.1Considerafilecurrentlyconsistingof100blocks.Assumethatthefilecontrolblock(andtheindexblock,inthecaseofindexedallocation)filecontrolblock(andtheindexblock,inthecaseofindexedallocation)isalreadyinmemory.CalculatehowmanydiskI/Ooperationsarerequiredforcontiguous,linked,andindexed(single-level)allocationstrategies,if,foroneblock,thefollowingconditionshold.Inthecontiguous-allocationcontiguous-allocationcase,assumethatthereisnoroomtogrowthethebeginningbutthereisroomtogrowattheend.Alsoassumetheblockinformationtobeaddedisstoredinmemory.Theblockisaddedatthebeginning.Theblockisaddedinthemiddle.c.c.Theblockisaddedattheend.d.Theblockisremovedfromthebeginning.e.Theblockisremovedfromthemiddle.f.Theblockisremovedfromtheend.Answer:Theresultsare:ContiguousLinkedIndexedContiguousLinkedIndexeda.20111b.101521c.131d.19810e.98520f.f.0100012.2Whatproblemscouldoccurifasystemallowedafilesystemtobemountedsimultaneouslyatmorethanonelocation?Answer:4344Chapter12 ImplementationTherewouldbemultiplepathstothesamefile,whichcouldconfuseusersorencouragemistakes(deletingafilewithonepathdeletestheTherewouldbemultiplepathstothesamefile,whichcouldconfuseusersorencouragemistakes(deletingafilewithonepathdeletesthefileinalltheotherpaths).Whymustthebitmapfor fileallocationbekeptonmassstorage, ratherthanthaninmainmemory?Answer:Incaseofsystemcrash(memoryfailure)thefree-spacelistwouldbelostasitwouldbeifthebitmaphadbeenstoredinmainmemory.Considerasystemthatsupportsthestrategiesofcontiguous,linked,andindexedallocation.Whatcriteriashouldbeusedindecidingwhichstrategyisbestutilizedforaparticularfile?strategyisbestutilizedforaparticularfile?Answer:Answer:•Contiguous—iffileisusuallyaccessedsequentially,iffileisrelativelysmall.•Linked—Linked—iffileislargeandusuallyaccessedsequentially.Indexed—iffileislargeandusuallyaccessedrandomly.Oneproblemwithcontiguousallocationisthattheusermustpreallocateenoughspaceforeachfile.Ifthefilegrowstobelargerthanthespacespaceallocatedforit,specialactionsmustbetaken.Onesolutiontothisproblemistodefineafilestructureconsistingofaninitialcontiguousproblemistodefineafilestructureconsistingofaninitialcontiguousarea(ofaspecifiedsize).Ifthisareaisfilled,theoperatingsystemautomaticallydefinesanoverflowareathatislinkedtotheinitialcontiguousarea.Iftheoverflowareaisfilled,anotheroverflowareaisallocated.Comparethisimplementationofafilewiththestandardisallocated.Comparethisimplementationofafilewiththestandardcontiguousandlinkedcontiguousandlinkedimplementations.Answer:Thismethodrequiresmoreoverheadthenthestandardcontiguousallocation.Itrequireslessoverheadthanthestandardlinkedallocation.Howdocacheshelpimproveperformance?Whydosystemsnotusemoreormoreorlargercachesiftheyaresouseful?Answer:Cachesallowcompon