《操作系统概念》第六版作业解答3

Chapter99.3Describethefollowingallocationalgorithms:a.Firstfitb.Bestfitc.WorstfitFirstfit:搜索可用内存列表，分配第一块足够大Bestfit:搜索整个可用内存块，分配最小足够大Worstfit:搜索整个可用内存块，分配最大足够大第1页9-cont.9.5Givenmemorypartitionsof100K,500K,200K,300K,and600K(inorder),howwouldeachoftheFirst-fit,Best-fit,andWorst-fitalgorithmsplaceprocessesof212K,417K,112K,and426K(inorder)?Whichalgorithmmakesthemostefficientuseofmemory?Firstfit212->500(288)417->600(183)112->288426->noneBestfit212->300417->500112->200426->600Worstfit212->600(388)417->500112->388426->none第2页9-cont.9.10Considerapagingsystemwiththepagetablestoredinmemory.a.Ifamemoryreferencetakes200nanoseconds,howlongdoesapagedmemoryreferencetake?b.Ifweaddassociativeregisters,and75percentofalltablereferencesarefoundintheassociativeregisters,whatistheeffectivememoryreferencetime?(Assumethatfindingatableentryintheassociativeregisterstakeszerotime,iftheentryisthere.)a.400,200(pagetable)+200(accessword)b.250,75%*200+25%*(200+200)第3页9-cont.9.16Considerthefollowingsegmenttable:Whatarethephysicaladdressesforthefollowinglogicaladdresses?a.0,430b.1,10c.2,500d.3,400e.4,112a.430<600,219+430=649b.10<14,2300+10=2310c.500>100,illegald.400<580,1327+400=1727e.112>96,illegal第4页9-cont.9.18IntheIBM/370,memoryprotectionisprovidedthroughtheuseofkeys.Akeyisa4-bitquantity.Each2Kblockofmemoryhasakey(thestoragekey)associatedwithit.TheCPUalsohasakey(theprotectionkey)associatedwithit.Astoreoperationisallowedonlyifbothkeysareequal,orifeitheriszero.Whichofthefollowingmemory-managementschemescouldbeusedsuccessfullywiththishardware?a.Baremachineb.Single-usersystemc.Multiprogrammingwithafixednumberofprocessesd.Multiprogrammingwithavariablenumberofprocessese.Pagingf.Segmentationa.Protectionnotnecessary,setsystemkeyto0.b.Setsystemkeyto0wheninsupervisormode.c.Regionsizesmustbefixedinincrementsof2kbytes,allocatekeywithmemoryblocks.d.Sameasabove.e.Framesizesmustbeinincrementsof2kbytes,allocatekeywithpages.f.Segmentsizesmustbeinincrementsof2kbytes,allocatekeywithsegments.第5页Chapter1010.1Underwhatcircumstancesdopagefaultsoccur?Describetheactionstakenbytheoperatingsystemwhenapagefaultoccurs.Apagefaultoccurswhenanaccesstoapagethathasnotbeenbroughtintomainmemorytakesplace.Theoperatingsystemverifiesthememoryaccess,abortingtheprogramifitisinvalid.Ifitisvalid,afreeframeislocatedandI/Oisrequestedtoreadtheneededpageintothefreeframe.UponcompletionofI/O,theprocesstableandpagetableareupdatedandtheinstructionisrestarted.第6页10-cont.10.6Considerthefollowingreplacementalgorithms.Rankthesealgorithmsonafivepointscalefrom“bad”to“perfect”accordingtotheirfaultrate.SeparatethosealgorithmsthatsufferfromBelady’sanomalyfromthosethatdonot.a.LRUreplacementb.FIFOreplacementc.Optimalreplacementd.Second-chancereplacementRankAlgorithmSufferfromBelady’sanomaly1Optimalno2LRUno3Second-chanceyes4FIFOyes第7页10-cont.10.9Considerademand-pagingsystemwiththefollowingtime-measuredutilizations:CPUutilization20%Pagingdisk97.7%OtherI/Odevices5%Which(ifany)ofthefollowingwill(probably)improveCPUutilization?Explainyouranswer.a.InstallafasterCPU.b.Installabiggerpagingdisk.c.Increasethedegreeofmultiprogramming.d.Decreasethedegreeofmultiprogramming.e.Installmoremainmemory.f.Installafasterharddiskormultiplecontrollerswithmultipleharddisks.g.Addprepagingtothepagefetchalgorithms.h.Increasethepagesize.第8页10-cont.10.10Considerthetwo-dimensionalarrayA:intA[][]=newint[100][100];whereA[0][0]isatlocation200,inapagedsystemwithpagesofsize200.Asmallprocessisinpage0(locations0to199)formanipulatingthematrix;thus,everyinstructionfetchwillbefrompage0.Forthreepageframes,howmanypagefaultsaregeneratedbythefollowingarray-initializationloops,usingLRUreplacement,andassumingpageframe1hastheprocessinit,andtheothertwoareinitiallyempty: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;a.100x50b.50第9页10-cont.10.11Considerthefollowingpagereferencestring: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.LRUreplacementFIFOreplacementOptimalreplacementNumberofframesLRUFIFOOptimal12020202181815315161141014858107671077777第10页Chapter1111.3Whydosomesystemskeeptrackofthetypeofafile,whileothersleaveittotheuserorsimplydonotimplementmultiplefiletypes?Whichsystemis“better?”Somesystemsallowdifferentfileoperationsbasedonthetypeofthefile(forinstance,anasciifilecanbereadasastreamwhileadatabasefilecanbereadviaanindextoablock).Othersystemsleavesuchinterpretationofafile’sdatatotheprocessandprovidenohelpinaccessingthedata.Themethodwhichis“better”dependsontheneedsoftheprocessesonthesystem,andthedemandstheusersplaceontheoperatingsystem.Ifasystemrunsmostlydatabaseapplications,itmaybemoreefficientfortheoperatingsystemtoimplementadatabase-typefileandprovideoperations,ratherthanmakingeachprogramimplementthesamething(possiblyindifferentways).Forgeneralpurposesystemsitmaybebettertoonlyimplementbasicfiletypestokeeptheoperatingsystemsizesmallerandallowmaximumfreedomtotheprocessesonthesystem.第11页11-cont.11.6Couldyousimulateamultileveldirectorystructurewithasingle-leveldirectorystructureinwhicharbitrarilylongnamescanbeused?Ifyouranswerisyes,explainhowyoucandoso,andcontrastthisschemewiththemultileveldirectoryscheme.Ifyouranswerisno,explainwhatpreventsyoursimulation’ssuccess.Howwouldyouranswerchangeiffilenameswerelimitedtosevencharacters?Ifarbitrarilylongnamescanbeusedthenitispossibletosimulateamultileveldirectorystructure.Thiscanbedone,forexample,byusingthecharacter“.”toindicatetheendofasubdirectory.Thus,forexample,thenamejim.pascal.F1specifiesthatF1isafileinsubdirectorypascalwhichinturnisintherootirectoryjim.Iffilenameswerelimitedtosevencharacters,thentheaboveschemecouldnotbeutilizedandthus,ingeneral,theanswerisno.Thenextbestapproachinthissituationwouldbetouseaspecificfileasasymboltable(directory)tomaparbitrarilylongnames(suchasjim.pascal.F1)intoshorterarbitrarynames(suchasXX00743),whicharethenusedforactualfileaccess.第12页11-cont.11.9Giveanexampleofanapplicationinwhichdatainafileshouldbeaccessedinthefollowingorder:a.Sequentiallyb.Randomlya.Printthecontentofthefile.b.Printthecontentofrecordi.Thisrecordcanbefoundusinghashingorindextechniques.11.12Considerasystemthatsupports5000users.Supposethatyouwanttoallow4990oftheseuserstobeabletoaccessonefile.a.HowwouldyouspecifythisprotectionschemeinUNIX?b.CouldyousuggestanotherprotectionschemethatcanbeusedmoreeffectivelyforthispurposethantheschemeprovidedbyUNIX?a.Therearetwomethodsforachievingthis:i.Createanaccesscontrollistwiththenamesofall4990users.ii.Putthese4990usersinonegroupandsetthegroupaccessaccordingly.Thisschemecannotalwaysbeimplementedsinceusergroupsarerestrictedbythesystem.b.Theuniverseaccessinformationappliestoallusersunlesstheirnameappearsintheaccess-controllistwithdifferentaccesspermission.Withthisschemeyousimplyputthenamesoftheremainingtenusersintheaccesscontrollistbutwithnoaccessprivilegesallowed.第13页Chapter1212.1Considerafilecurrentlyconsistingof100blocks.Assumethatthefilecontrolblock(andtheindexblock,inthecaseofindexedallocation)isalreadyinmemory.CalculatehowmanydiskI/Ooperationsarerequiredforcontiguous,linked,andindexed(single-level)allocationstrategies,if,foroneblock,thefollowingconditionshold.Inthecontiguousallocationcase,assumethatthereisnoroomtogrowinthebeginning,butthereisroomtogrowintheend.Assumethattheblockinformationtobeaddedisstoredinmemory.a.Theblockisaddedatthebeginning.b.Theblockisaddedinthemiddle.c.Theblockisaddedattheend.d.Theblockisremovedfromthebeginning.e.Theblockisremovedfromthemiddle.f.Theblockisremovedfromtheend.ContiguousLinkedIndexed201(100读写+1新写)1（1新写）1（1新写）101(50读写+1新写)52（50读+第50块写+1新写）1（1新写）1（1新写）3（第100块读写+1新写）1（1新写）198（99读写）1（读第1块）098（后49块读写）52（51读+第50块写）00100（99读+1写）0第14页12-cont.12.2Considerasystemwherefreespaceiskeptinafree-spacelist.a.Supposethatthepointertothefree-spacelistislost.Canthesystemreconstructthefree-spacelist?Explainyouranswer.b.Suggestaschemetoensurethatthepointerisneverlostasaresultofmemoryfailure.a.Inordertoreconstructthefreelist,itwouldbenecessarytoperform“garbagecollection.”Thiswouldentailsearchingtheentiredirectorystructuretodeterminewhichpagesarealreadyallocatedtojobs.Thoseremainingunallocatedpagescouldberelinkedasthefree-spacelist.b.Thefree-spacelistpointercouldbestoredonthedisk,perhapsinseveralplaces.第15页12-cont.12.3Whatproblemscouldoccurifasystemallowedafilesystemtobemountedsimultaneouslyatmorethanonelocation?Therewouldbemultiplepathstothesamefile,whichcouldconfuseusersorencouragemistakes(deletingafilewithonepathdeletesthefileinalltheotherpaths).12.4Whymustthebitmapforfileallocationbekeptonmassstorage,ratherthaninmainmemory?Incaseofsystemcrash(memoryfailure)thefree-spacelistwouldnotbelostasitwouldbeifthebitmaphadbeenstoredinmainmemory.第16页12-cont.12.5Considerasystemthatsupportsthestrategiesofcontiguous,linked,andindexedallocation.Whatcriteriashouldbeusedindecidingwhichstrategyisbestutilizedforaparticularfile?Contiguous–iffileisusuallyaccessedsequentially,iffileisrelativelysmall.

Linked–iffileislargeandusuallyaccessedsequentially.

Indexed–iffileislargeandusuallyaccessedrandomly.12.6Considerafilesystemonadiskthathasbothlogicalandphysicalblocksizesof512bytes.Assumethattheinformationabouteachfileisalreadyinmemory.Foreachofthethreeallocationstrategies(contiguous,linked,andindexed),answerthesequestions:a.Howisthelogical-to-physicaladdressmappingaccomplishedinthissystem?(Fortheindexedallocation,assumethatafileisalwayslessthan512blockslong.)b.Ifwearecurrentlyatlogicalblock10(thelastblockaccessedwasblock10)andwanttoaccesslogicalblock4,howmanyphysicalblocksmustbereadfromthedisk?a.Contiguous.Dividethelogicaladdressby512withXandYtheresultingquotientandremainderrespectively.i.AddXtoZtoobtainthephysicalblocknumber.Yisthedisplacementintothatblock.ii.1b.Linked.Dividethelogicalphysicaladdressby511withXandYtheresultingquotientandremainderrespectively.i.Chasedownthelinkedlist(gettingX+1blocks).Y+1isthedisplacementintothelastphysicalblock.ii.4c.Indexed.Dividethelogicaladdressby512withXandYtheresultingquotientandremainderrespectively.i.Gettheindexblockintomemory.PhysicalblockaddressiscontainedintheindexblockatlocationX.Yisthedisplacementintothedesiredphysicalblock.ii.2第17页Chapter1313.1Statethreeadvantagesofplacingfunctionalityinadevicecontroller,ratherthaninthekernel.Statethreedisadvantages.Threeadvantages:BugsarelesslikelytocauseanoperatingsystemcrashPerformancecanbeimprovedbyutilizingdedicatedhardwareandhard-codedalgorithmsThekernelissimplifiedbymovingalgorithmsoutofitThreedisadvantages:Bugsarehardertofix-anewfirmwareversionornewhardwareisneededImprovingalgorithmslikewiserequireahardwareupdateratherthanjustkernelordevicedriverupdateEmbeddedalgorithmscouldconflictwithapplication’suseofthedevice,causingdecreasedperformance.第18页13-cont.13.2ConsiderthefollowingI/Oscenariosonasingle-userPC.a.Amouseusedwithagraphicaluserinterfaceb.Atapedriveonamultitaskingoperatingsystem(assumenodevicepreallocationisavailable)c.Adiskdrivecontaininguserfilesd.Agraphicscardwithdirectbusconnection,accessiblethroughmemory-mappedI/OForeachoftheseI/Oscenarios,wouldyoudesigntheoperatingsystemtousebuffering,spooling,caching,oracombination?WouldyouusepolledI/O,orinterrupt-drivenI/O?Givereasonsforyourchoices.a.Bufferingmaybeneededtorecordmousemovementduringtimeswhenhigherpriorityoperationsaretakingplace.Spoolingandcachingareinappropriate.InterruptdrivenI/Oismostappropriate.b.BufferingmaybeneededtomanagethroughputdifferencebetweenthetapedriveandthesourceordestinationoftheI/O,Cachingcanbeusedtoholdcopiesofdatathatresidesonthetape,forfasteraccess.Spoolingcouldbeusedtostagedatatothedevicewhenmultipleusersdesiretoreadfromorwritetoit.InterruptdrivenI/Oislikelytoallowthebestperformance.c.Bufferingcanbeusedtoholddatawhileintransitfromuserspacetothedisk,andvisaversa.Cachingcanbeusedtoholddisk-residentdataforimprovedperformance.Spoolingisnotnecessarybecausedisksareshared-accessdevices.InterruptdrivenI/Oisbestfordevicessuchasdisksthattransferdataatslowrates.d.Bufferingmaybeneededtocontrolmultipleaccessandforperformance(doublebufferingcanbeusedtoholdthenextscreenimagewhiledisplayingthecurrentone).Cachingandspoolingarenotnecessaryduetothefastandshared-accessnaturesofthedevice.PollingandinterruptsareonlyusefulforinputandforI/Ocompletiondetection,neitherofwhichisneededforamemory-mappeddevice.第19页13-cont.13.4DescribethreecircumstancesunderwhichblockingI/Oshouldbeused.DescribethreecircumstancesunderwhichnonblockingI/Oshouldbeused.WhynotjustimplementnonblockingI/Oandhaveprocessesbusy-waituntiltheirdeviceisready?Generally,blockingI/Oisappropriatewhentheprocesswillonlybewaitingforonespecificevent.Examplesincludeadisk,tape,orkeyboardreadbyanapplicationprogram.Non-blockingI/OisusefulwhenI/OmaycomefrommorethanonesourceandtheorderoftheI/Oarrivalisnotpredetermined.Examplesincludenetworkdaemonslisteningtomorethanonenetworksocket,windowmanagersthatacceptmousemovementaswellaskeyboardinput,andI/O-managementprograms,suchasacopycommandthatcopiesdatabetweenI/Odevices.Inthelastcase,theprogramcouldoptimizeitsperformancebybufferingtheinputandoutputandusingnon-blockingI/Otokeepbothdevicesfullyoccupied.Non-blockingI/Oismorecomplicatedforprogrammers,becauseoftheasynchonousrendezvousthatisneededwhenanI/Ooccurs.Also,busywaitingislessefficientthaninterrupt-drivenI/Osotheoverallsystemperformancewoulddecrease.第20页13-cont.13.5Whymightasystemuseinterrupt-drivenI/Otomanageasingleserialport,butpollingI/Otomanageafront-endprocessor,suchasaterminalconcentrator?Pollingcanbemoreefficientthaninterrupt-drivenI/O.ThisisthecasewhentheI/Oisfrequentandofshortduration.EventhoughasingleserialportwillperformI/Orelativelyinfrequentlyandshouldthususeinterrupts,acollectionofserialportssuchasthoseinaterminalconcentratorcanproducealotofshortI/Ooperations,andinterruptingforeachonecouldcreateaheavyloadonthesystem.Awell-timedpollingloopcouldalleviatethatloadwithoutwastingmanyresourcesthroughloopingwithnoI/Oneeded.13.8HowdoesDMAincreasesystemconcurrency?Howdoesitcomplicatehardwaredesign?DMAincreasessystemconcurrencybyallowingtheCPUtoperformtaskswhiletheDMAsystemtransfersdataviathesystemandmemorybusses.HardwaredesigniscomplicatedbecausetheDMAcontrollermustbeintegratedintothesystem,andthesystemmustallowtheDMAcontrollertobeabusmaster.CyclestealingmayalsobenecessarytoallowtheCPUandDMAcontrollertoshareuseofthememorybus.第21页Chapter1414.2Supposethatadiskdrivehas5000cylinders,numbered0to4999.Thedriveiscurrentlyservingarequestatcylinder143,andthepreviousrequestwasatcylinder125.Thequeueofpendingrequests,inFIFOorder,is86,1470,913,1774,948,1509,1022,1750,130Startingfromthecurrentheadposition,whatisthetotaldistance(incylinders)thatthediskarmmovestosatisfyallthependingrequests,foreachofthefollowingdiskschedulingalgorithms?a.FCFSb.SSTFc.SCANd.LOOKe.C-SCANa.TheFCFSscheduleis143,86,1470,913,1774,948,1509,1022,1750,130.Thetotalseekdistanceis7081.b.TheSSTFscheduleis143,130,86,913,948,1022,1470,1509,1750,1774.Thetotalse