操作系统第九版部分课后作业习题答案.doc 18页

'CHAPTER9VirtualMemoryPracticeExercises9.1Underwhatcircumstancesdopagefaultsoccur?Describetheactionstakenbytheoperatingsystemwhenapagefaultoccurs.Answer:Apagefaultoccurswhenanaccesstoapagethathasnotbeenbroughtintomainmemorytakesplace.Theoperatingsystemverifiesthememoryaccess,abortingtheprogramifitisinvalid.Ifitisvalid,afreeframeislocatedandI/Oisrequestedtoreadtheneededpageintothefreeframe.UponcompletionofI/O,theprocesstableandpagetableareupdatedandtheinstructionisrestarted.9.2Assumethatyouhaveapage-referencestringforaprocesswithmframes(initiallyallempty).Thepage-referencestringhaslengthp;ndistinctpagenumbersoccurinit.Answerthesequestionsforanypage-replacementalgorithms:a.Whatisalowerboundonthenumberofpagefaults?b.Whatisanupperboundonthenumberofpagefaults?Answer:a.nb.p9.3ConsiderthepagetableshowninFigure9.30forasystemwith12-bitvirtualandphysicaladdressesandwith256-bytepages.Thelistoffree pageframesisD,E,F(thatis,Disattheheadofthelist,Eissecond,andFislast).Convertthefollowingvirtualaddressestotheirequivalentphysicaladdressesinhexadecimal.Allnumbersaregiveninhexadecimal.(Adashforapageframeindicatesthatthepageisnotinmemory.)•9EF•1112930Chapter9VirtualMemory•700•0FFAnswer:•9EF-0EF•111-211•700-D00•0FF-EFF9.4Considerthefollowingpage-replacementalgorithms.Rankthesealgorithmsonafive-pointscalefrom“bad”to“perfect”accordingtotheirpage-faultrate.SeparatethosealgorithmsthatsufferfromBelady’sanomalyfromthosethatdonot.a.LRUreplacementb.FIFOreplacementc.Optimalreplacement d.Second-chancereplacementAnswer:RankAlgorithmSufferfromBelady’sanomaly1Optimalno2LRUno3Second-chanceyes4FIFOyes9.5Discussthehardwaresupportrequiredtosupportdemandpaging.Answer:Foreverymemory-accessoperation,thepagetableneedstobeconsultedtocheckwhetherthecorrespondingpageisresidentornotandwhethertheprogramhasreadorwriteprivilegesforaccessingthepage.Thesecheckshavetobeperformedinhardware.ATLBcouldserveasacacheandimprovetheperformanceofthelookupoperation.9.6Anoperatingsystemsupportsapagedvirtualmemory,usingacentralprocessorwithacycletimeof1microsecond.Itcostsanadditional1microsecondtoaccessapageotherthanthecurrentone.Pageshave1000words,andthepagingdeviceisadrumthatrotatesat3000revolutionsperminuteandtransfers1millionwordspersecond.Thefollowingstatisticalmeasurementswereobtainedfromthesystem:•1percentofallinstructionsexecutedaccessedapageotherthanthecurrentpage. •Oftheinstructionsthataccessedanotherpage,80percentaccessedapagealreadyinmemory.PracticeExercises31•Whenanewpagewasrequired,thereplacedpagewasmodified50percentofthetime.Calculatetheeffectiveinstructiontimeonthissystem,assumingthatthesystemisrunningoneprocessonlyandthattheprocessorisidleduringdrumtransfers.Answer:effectiveaccesstime=0.99×(1sec+0.008×(2sec)+0.002×(10,000sec+1,000sec)+0.001×(10,000sec+1,000sec)=(0.99+0.016+22.0+11.0)sec=34.0sec9.7Considerthetwo-dimensionalarrayA:intA[][]=newint[100][100];whereA[0][0]isatlocation200inapagedmemorysystemwithpagesofsize200.Asmallprocessthatmanipulatesthematrixresidesinpage0(locations0to199).Thus,everyinstructionfetchwillbefrompage0.Forthreepageframes,howmanypagefaultsaregeneratedbythefollowingarray-initializationloops,usingLRUreplacementand assumingthatpageframe1containstheprocessandtheothertwoareinitiallyempty?a.for(intj=0;j<100;j++)for(inti=0;i<100;i++)A[i][j]=0;b.for(inti=0;i<100;i++)for(intj=0;j<100;j++)A[i][j]=0;Answer:a.5,000b.509.8Considerthefollowingpagereferencestring: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.•LRUreplacement•FIFOreplacement•Optimalreplacement32Chapter9VirtualMemory Answer:NumberofframesLRUFIFOOptimal120202021818153151611410148581076710777779.9Supposethatyouwanttouseapagingalgorithmthatrequiresareferencebit(suchassecond-chancereplacementorworking-setmodel),butthehardwaredoesnotprovideone.Sketchhowyoucouldsimulateareferencebitevenifonewerenotprovidedbythehardware,orexplainwhyitisnotpossibletodoso.Ifitispossible,calculatewhatthecostwouldbe.Answer:Youcanusethevalid/invalidbitsupportedinhardwaretosimulatethereferencebit.Initiallysetthebittoinvalid.Onfirstreferenceatraptotheoperatingsystemisgenerated.Theoperatingsystemwillsetasoftwarebitto1andresetthevalid/invalidbittovalid.9.10Youhavedevisedanewpage-replacementalgorithmthatyouthink maybeoptimal.Insomecontortedtestcases,Belady’sanomalyoccurs.Isthenewalgorithmoptimal?Explainyouranswer.Answer:No.AnoptimalalgorithmwillnotsufferfromBelady’sanomalybecause—bydefinition—anoptimalalgorithmreplacesthepagethatwillnotbeusedforthelongesttime.Belady’sanomalyoccurswhenapagereplacementalgorithmevictsapagethatwillbeneededintheimmediatefuture.Anoptimalalgorithmwouldnothaveselectedsuchapage.9.11Segmentationissimilartopagingbutusesvariable-sized“pages.”Definetwosegment-replacementalgorithmsbasedonFIFOandLRUpagereplacementschemes.Rememberthatsincesegmentsarenotthesamesize,thesegmentthatischosentobereplacedmaynotbebigenoughtoleaveenoughconsecutivelocationsfortheneededsegment.Considerstrategiesforsystemswheresegmentscannotberelocated,andthoseforsystemswheretheycan.Answer:a.FIFO.Findthefirstsegmentlargeenoughtoaccommodatetheincomingsegment.Ifrelocationisnotpossibleandnoonesegment islargeenough,selectacombinationofsegmentswhosememoriesarecontiguous,whichare“closesttothefirstofthelist”andwhichcanaccommodatethenewsegment.Ifrelocationispossible,rearrangethememorysothatthefirstNsegmentslargeenoughfortheincomingsegmentarecontiguousinmemory.Addanyleftoverspacetothefree-spacelistinbothcases.PracticeExercises33b.LRU.Selectthesegmentthathasnotbeenusedforthelongestperiodoftimeandthatislargeenough,addinganyleftoverspacetothefreespacelist.Ifnoonesegmentislargeenough,selectacombinationofthe“oldest”segmentsthatarecontiguousinmemory(ifrelocationisnotavailable)andthatarelargeenough.Ifrelocationisavailable,rearrangetheoldestNsegmentstobecontiguousinmemoryandreplacethosewiththenewsegment.9.12Considerademand-pagedcomputersystemwherethedegreeofmultiprogrammingiscurrentlyfixedatfour.ThesystemwasrecentlymeasuredtodetermineutilizationofCPUandthepagingdisk.Theresultsareoneofthefollowingalternatives.Foreachcase,whatishappening?CanthedegreeofmultiprogrammingbeincreasedtoincreasetheCPUutilization?Isthepaginghelping?a.CPUutilization13percent;diskutilization97percentb.CPUutilization87percent;diskutilization3percentc.CPUutilization13percent;diskutilization3percent Answer:a.Thrashingisoccurring.b.CPUutilizationissufficientlyhightoleavethingsalone,andincreasedegreeofmultiprogramming.c.Increasethedegreeofmultiprogramming.9.13Wehaveanoperatingsystemforamachinethatusesbaseandlimitregisters,butwehavemodifiedthemachinetoprovideapagetable.Canthepagetablesbesetuptosimulatebaseandlimitregisters?Howcantheybe,orwhycantheynotbe?Answer:Thepagetablecanbesetuptosimulatebaseandlimitregistersprovidedthatthememoryisallocatedinfixed-sizesegments.Inthisway,thebaseofasegmentcanbeenteredintothepagetableandthevalid/invalidbitusedtoindicatethatportionofthesegmentasresidentinthememory.Therewillbesomeproblemwithinternalfragmentation.9.27.Considerademand-pagingsystemwiththefollowingtime-measuredutilizations:CPU utilization20%Pagingdisk97.7%Other I/O devices5%Which(ifany)ofthefollowingwill(probably)improveCPUutilization?Explainyouranswer. a.Installafaster CPU.b.Installabiggerpagingdisk.c.Increasethedegreeofmultiprogramming.d.Decreasethedegreeofmultiprogramming.e.Installmoremainmemory.f.Installafasterharddiskormultiplecontrollerswithmultipleharddisks.g.Addprepagingtothepagefetchalgorithms.h.Increasethepagesize.Answer: Thesystemobviouslyisspendingmostofitstimepaging,indicatingover-allocationofmemory.Ifthelevelofmultiprogrammingisreducedresidentprocesseswouldpagefaultlessfrequentlyandthe CPU utilizationwouldimprove.Anotherwaytoimproveperformancewouldbetogetmorephysicalmemoryorafasterpagingdrum.a.Getafaster CPU—No.b.Getabiggerpagingdrum—No.c.Increasethedegreeofmultiprogramming—No.d.Decreasethedegreeofmultiprogramming—Yes. e.Installmoremainmemory—Likelytoimprove CPU utilizationasmorepagescanremainresidentandnotrequirepagingtoorfromthedisks.f.Installafasterharddisk,ormultiplecontrollerswithmultipleharddisks—Alsoanimprovement,forasthediskbottleneckisremovedbyfasterresponseandmorethroughputtothedisks,the CPU willgetmoredatamorequickly.g.Addprepagingtothepagefetchalgorithms—Again,the CPU willgetmoredatafaster,soitwillbemoreinuse.Thisisonlythecaseifthepagingactionisamenabletoprefetching(i.e.,someoftheaccessissequential).h.Increasethepagesize—Increasingthepagesizewillresultinfewerpagefaultsifdataisbeingaccessedsequentially.Ifdataaccessismoreorlessrandom,morepagingactioncouldensuebecausefewerpagescanbekeptinmemoryandmoredataistransferredperpagefault.Sothischangeisaslikelytodecreaseutilizationasitistoincreaseit. 10.1、Isdiskscheduling,otherthanFCFSscheduling,usefulinasingle-userenvironment?Explainyouranswer.Answer:Inasingle-userenvironment,theI/Oqueueusuallyisempty.Requestsgenerallyarrivefromasingleprocessforoneblockorforasequenceofconsecutiveblocks.Inthesecases,FCFSisaneconomicalmethodofdiskscheduling.ButLOOKisnearlyaseasytoprogramandwillgivemuchbetterperformancewhenmultipleprocessesareperformingconcurrentI/O,suchaswhenaWebbrowserretrievesdatainthebackgroundwhiletheoperatingsystemispagingandanotherapplicationisactiveintheforeground.10.2.ExplainwhySSTFschedulingtendstofavormiddlecylindersovertheinnermostandoutermostcylinders.Thecenterofthediskisthelocationhavingthesmallestaveragedistancetoallothertracks.Thusthediskheadtendstomoveawayfromtheedgesofthedisk.Hereisanotherwaytothinkofit.Thecurrentlocationoftheheaddividesthecylindersintotwogroups.Iftheheadisnotinthecenterofthediskandanewrequestarrives,thenewrequestismorelikelytobeinthegroupthatincludesthecenterofthedisk;thus,theheadismorelikelytomoveinthatdirection. 10.11、Supposethatadiskdrivehas5000cylinders,numbered0to4999.Thedriveiscurrentlyservingarequestatcylinder143,andthepreviousrequestwasatcylinder125.Thequeueofpendingrequests,inFIFOorder,is  86,1470,913,1774,948,1509,1022,1750,130 Startingfromthecurrentheadposition,whatisthetotaldistance(incylinders)thatthediskarmmovestosatisfyallthependingrequests,foreachofthefollowingdisk-schedulingalgorithms?a.FCFS b.SSTF c.SCAN d.LOOK e.C-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.Thetotalseekdistanceis 3319. 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.12CHAPTERFile-SystemImplementationPracticeExercises12.1Considerafilecurrentlyconsistingof100blocks.Assumethatthefilecontrolblock(andtheindexblock,inthecaseofindexedallocation)isalreadyinmemory.CalculatehowmanydiskI/Ooperationsarerequiredforcontiguous,linked,andindexed(single-level)allocationstrategies,if,foroneblock,thefollowingconditionshold.Inthecontiguous-allocationcase,assumethatthereisnoroomtogrowatthebeginningbutthereisroomtogrowattheend.Alsoassumethattheblockinformationtobeaddedisstoredinmemory.a.Theblockisaddedatthebeginning.b.Theblockisaddedinthemiddle.c.Theblockisaddedattheend.d.Theblockisremovedfromthebeginning.e.Theblockisremovedfromthemiddle.f.Theblockisremovedfromtheend. Answer:Theresultsare:ContiguousLinkedIndexeda.20111b.101521c.131d.19810e.98520f.0100012.2Whatproblemscouldoccurifasystemallowedafilesystemtobemountedsimultaneouslyatmorethanonelocation?Answer:4344Chapter12File-SystemImplementationTherewouldbemultiplepathstothesamefile,whichcouldconfuseusersorencouragemistakes(deletingafilewithonepathdeletesthefileinalltheotherpaths).12.3Whymustthebitmapforfileallocationbekeptonmassstorage,ratherthaninmainmemory?Answer:Incaseofsystemcrash(memoryfailure)thefree-spacelistwouldnotbelostasitwouldbeifthebitmaphadbeenstoredinmainmemory. 12.4Considerasystemthatsupportsthestrategiesofcontiguous,linked,andindexedallocation.Whatcriteriashouldbeusedindecidingwhichstrategyisbestutilizedforaparticularfile?Answer:•Contiguous—iffileisusuallyaccessedsequentially,iffileisrelativelysmall.•Linked—iffileislargeandusuallyaccessedsequentially.•Indexed—iffileislargeandusuallyaccessedrandomly.12.5Oneproblemwithcontiguousallocationisthattheusermustpreallocateenoughspaceforeachfile.Ifthefilegrowstobelargerthanthespaceallocatedforit,specialactionsmustbetaken.Onesolutiontothisproblemistodefineafilestructureconsistingofaninitialcontiguousarea(ofaspecifiedsize).Ifthisareaisfilled,theoperatingsystemautomaticallydefinesanoverflowareathatislinkedtotheinitialcontiguousarea.Iftheoverflowareaisfilled,anotheroverflowareaisallocated.Comparethisimplementationofafilewiththestandardcontiguousandlinkedimplementations.Answer:Thismethodrequiresmoreoverheadthenthestandardcontiguous allocation.Itrequireslessoverheadthanthestandardlinkedallocation.12.6Howdocacheshelpimproveperformance?Whydosystemsnotusemoreorlargercachesiftheyaresouseful?Answer:Cachesallowcomponentsofdifferingspeedstocommunicatemoreefficientlybystoringdatafromtheslowerdevice,temporarily,inafasterdevice(thecache).Cachesare,almostbydefinition,moreexpensivethanthedevicetheyarecachingfor,soincreasingthenumberorsizeofcacheswouldincreasesystemcost.12.7Whyisitadvantageousfortheuserforanoperatingsystemtodynamicallyallocateitsinternaltables?Whatarethepenaltiestotheoperatingsystemfordoingso?Answer:Dynamictablesallowmoreflexibilityinsystemusegrowth—tablesareneverexceeded,avoidingartificialuselimits.Unfortunately,kernelstructuresandcodearemorecomplicated,sothereismorepotentialforbugs.Theuseofoneresourcecantakeawaymoresystemresources(bygrowingtoaccommodatetherequests)thanwithstatictables.PracticeExercises4512.8ExplainhowtheVFSlayerallowsanoperatingsystemtosupportmultipletypesoffilesystemseasily.Answer: VFSintroducesalayerofindirectioninthefilesystemimplementation.Inmanyways,itissimilartoobject-orientedprogrammingtechniques.Systemcallscanbemadegenerically(independentoffilesystemtype).EachfilesystemtypeprovidesitsfunctioncallsanddatastructurestotheVFSlayer.AsystemcallistranslatedintotheproperspecificfunctionsforthetargetfilesystemattheVFSlayer.Thecallingprogramhasnofile-system-specificcode,andtheupperlevelsofthesystemcallstructureslikewisearefilesystem-independent.ThetranslationattheVFSlayerturnsthesegenericcallsintofile-system-specificoperations.'