操作系统概念 第七版 (Abraham Silberschatz Peter Baer Galvin Greg Gagne 著) 高等教育出版社 课后答案 113页

'课后答案网，用心为你服务！大学答案---中学答案---考研答案---考试答案最全最多的课后习题参考答案，尽在课后答案网（www.khdaw.com）！Khdaw团队一直秉承用心为大家服务的宗旨，以关注学生的学习生活为出发点，旨在为广大学生朋友的自主学习提供一个分享和交流的平台。爱校园（www.aixiaoyuan.com）课后答案网（www.khdaw.com）淘答案（www.taodaan.com） 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3solutionstotheexercisesChapter11.1Inamultiprogrammingandtime-sharingenvironment,severaluserssharethesystemsimultaneously.Thissituationcanresultinvarioussecurityproblems.a.Whataretwosuchproblems?b.Canweensurethesamedegreeofsecurityinatime-sharedmachineasinadedicatedmachine?Explainyouranswer.Answer:a.Stealingorcopyingone’sprogramsordata;usingsystemresources(CPU,memory,diskspace,peripherals)withoutproperaccounting.b.Probablynot,sinceanyprotectionschemedevisedbyhumanscaninevitablybebrokenbyahuman,andthemorecomplexthescheme,themoredifficultitistofeelconfidentofitscorrectimplementation.1.2Theissueofresourceutilizationshowsupindifferentformsindifferenttypesofoperatingsystems.Listwhatresourcesmustbemanagedcarefullyinthefollowingsettings:a.Mainframeorminicomputersystemsb.Workstationsconnectedtoserversc.HandheldcomputersAnswer:a.Mainframes:memoryandCPUresources,storage,networkbandwidth.b.Workstations:memoryandCPUresoucesc.Handheldcomputers:powerconsumption,memoryresources.1.3UnderwhatcircumstanceswouldauserbebetteroffusingatimesharingsystemratherthanaPCorsingle-userworkstation?Answer:Whentherearefewotherusers,thetaskislarge,andthehardwareisfast,time-sharingmakessense.Thefullpowerofthesystemcanbebroughttobearontheuser’sproblem.Theproblemcanbesolvedfasterthanonapersonalcomputer.Anothercaseoccurswhenlotsofotherusersneedresourcesatthesametime.Apersonalcomputerisbestwhenthejobissmallenoughtobeexecutedreasonablyonitandwhenperformanceissufficienttoexecutetheprogramtotheuser’ssatisfaction.1.4Whichofthefunctionalitieslistedbelowneedtobesupportedbytheoperatingsystemforthefollowingtwosettings:(a)handhelddevicesand(b)real-timesystems.a.Batchprogrammingb.Virtualmemoryc.TimesharingAnswer:Forreal-timesystems,theoperatingsystemneedstosupportvirtualmemory 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3andtimesharinginafairmanner.Forhandheldsystems,theoperatingsystemneedstoprovidevirtualmemory,butdoesnotneedtoprovidetime-sharing.Batchprogrammingisnotnecessaryinbothsettings.1.5Describethedifferencesbetweensymmetricandasymmetricmultiprocessing.Whatarethreeadvantagesandonedisadvantageofmultiprocessorsystems?Answer:Symmetricmultiprocessingtreatsallprocessorsasequals,andI/OcanbeprocessedonanyCPU.AsymmetricmultiprocessinghasonemasterCPUandtheremainderCPUsareslaves.Themasterdistributestasksamongtheslaves,andI/Oisusuallydonebythemasteronly.Multiprocessorscansavemoneybynotduplicatingpowersupplies,housings,andperipherals.Theycanexecuteprogramsmorequicklyandcanhaveincreasedreliability.Theyarealsomorecomplexinbothhardwareandsoftwarethanuniprocessorsystems.1.6Howdoclusteredsystemsdifferfrommultiprocessorsystems?Whatisrequiredfortwomachinesbelongingtoaclustertocooperatetoprovideahighlyavailableservice?Answer:Clusteredsystemsaretypicallyconstructedbycombiningmultiplecomputersintoasinglesystemtoperformacomputationaltaskdistributedacrossthecluster.MultiprocessorsystemsontheotherhandcouldbeasinglephysicalentitycomprisingofmultipleCPUs.Aclusteredsystemislesstightlycoupledthanamultiprocessorsystem.Clusteredsystemscommunicateusingmessages,whileprocessorsinamultiprocessorsystemcouldcommunicateusingsharedmemory.Inorderfortwomachinestoprovideahighlyavailableservice,thestateonthetwomachinesshouldbereplicatedandshouldbeconsistentlyupdated.Whenoneofthemachinesfail,theothercouldthentake-overthefunctionalityofthefailedmachine.1.7Distinguishbetweentheclient-serverandpeer-to-peermodelsofdistributedsystems.Answer:Theclient-servermodelfirmlydistinguishestherolesoftheclientandserver.Underthismodel,theclientrequestsservicesthatareprovidedbytheserver.Thepeer-to-peermodeldoesn’thavesuchstrictroles.Infact,allnodesinthesystemareconsideredpeersandthusmayactaseitherclientsorserversorboth.Anodemayrequestaservicefromanotherpeer,orthenodemayinfactprovidesuchaservicetootherpeersinthesystem.Forexample,let’sconsiderasystemofnodesthatsharecookingrecipes.Undertheclient-servermodel,allrecipesarestoredwiththeserver.Ifaclientwishestoaccessarecipe,itmustrequesttherecipefromthespecifiedserver.Usingthepeer-to-peermodel,apeernodecouldaskotherpeernodesforthespecifiedrecipe. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Thenode(orperhapsnodes)withtherequestedrecipecouldprovideittotherequestingnode.Noticehoweachpeermayactasbothaclient(i.e.itmayrequestrecipes)andasaserver(itmayproviderecipes.)1.8Consideracomputingclusterconsistingoftwonodesrunningadatabase.Describetwowaysinwhichtheclustersoftwarecanmanageaccesstothedataonthedisk.Discussthebenefitsanddisadvantagesofeach.Answer:Considerthefollowingtwoalternatives:asymmetricclusteringandparallelclustering.Withasymmetricclustering,onehostrunsthedatabaseapplicationwiththeotherhostsimplymonitoringit.Iftheserverfails,themonitoringhostbecomestheactiveserver.Thisisappropriateforprovidingredundancy.However,itdoesnotutilizethepotentialprocessingpowerofbothhosts.Withparallelclustering,thedatabaseapplicationcanruninparallelonbothhosts.Thedifficultyimplementingparallelclustersisprovidingsomeformofdistributedlockingmechanismforfilesontheshareddisk.1.9Howarenetworkcomputersdifferentfromtraditionalpersonalcomputers?Describesomeusagescenariosinwhichitisadvantageoustousenetworkcomputers.Answer:Anetworkcomputerreliesonacentralizedcomputerformostofitsservices.Itcanthereforehaveaminimaloperatingsystemtomanageitsresources.Apersonalcomputerontheotherhandhastobecapableofprovidingalloftherequiredfunctionalityinastandalonemannerwithoutrelyingonacentralizedmanner.Scenarioswhereadministrativecostsarehighandwheresharingleadstomoreefficientuseofresourcesarepreciselythosesettingswherenetworkcomputersarepreferred.1.10Whatisthepurposeofinterrupts?Whatarethedifferencesbetweenatrapandaninterrupt?Cantrapsbegeneratedintentionallybyauserprogram?Ifso,forwhatpurpose?Answer:Aninterruptisahardware-generatedchange-of-flowwithinthesystem.Aninterrupthandlerissummonedtodealwiththecauseoftheinterrupt;controlisthenreturnedtotheinterruptedcontextandinstruction.Atrapisasoftware-generatedinterrupt.AninterruptcanbeusedtosignalthecompletionofanI/Otoobviatetheneedfordevicepolling.Atrapcanbeusedtocalloperatingsystemroutinesortocatcharithmeticerrors.1.11Directmemoryaccessisusedforhigh-speedI/OdevicesinordertoavoidincreasingtheCPU′sexecutionload.a.HowdoestheCPUinterfacewiththedevicetocoordinatethetransfer?b.HowdoestheCPUknowwhenthememoryoperationsarecomplete?c.TheCPUisallowedtoexecuteotherprogramswhiletheDMAcontrolleris 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3transferringdata.Doesthisprocessinterferewiththeexecutionoftheuserprograms?Ifso,describewhatformsofinterferencearecaused.Answer:TheCPUcaninitiateaDMAoperationbywritingvaluesintospecialregistersthatcanbeindependentlyaccessedbythedevice.ThedeviceinitiatesthecorrespondingoperationonceitreceivesacommandfromtheCPU.Whenthedeviceisfinishedwithitsoperation,itinterruptstheCPUtoindicatethecompletionoftheoperation.BoththedeviceandtheCPUcanbeaccessingmemorysimultaneously.Thememorycontrollerprovidesaccesstothememorybusinafairmannertothesetwoentities.ACPUmightthereforebeunabletoissuememoryoperationsatpeakspeedssinceithastocompetewiththedeviceinordertoobtainaccesstothememorybus.1.12Somecomputersystemsdonotprovideaprivilegedmodeofoperationinhardware.Isitpossibletoconstructasecureoperatingsystemforthesecomputersystems?Giveargumentsboththatitisandthatitisnotpossible.Answer:Anoperatingsystemforamachineofthistypewouldneedtoremainincontrol(ormonitormode)atalltimes.Thiscouldbeaccomplishedbytwomethods:a.Softwareinterpretationofalluserprograms(likesomeBASIC,Java,andLISPsystems,forexample).Thesoftwareinterpreterwouldprovide,insoftware,whatthehardwaredoesnotprovide.b.Requiremeantthatallprogramsbewritteninhigh-levellanguagessothatallobjectcodeiscompiler-produced.Thecompilerwouldgenerate(eitherin-lineorbyfunctioncalls)theprotectionchecksthatthehardwareismissing.1.13Givetworeasonswhycachesareuseful.Whatproblemsdotheysolve?Whatproblemsdotheycause?Ifacachecanbemadeaslargeasthedeviceforwhichitiscaching(forinstance,acacheaslargeasadisk),whynotmakeitthatlargeandeliminatethedevice?Answer:Cachesareusefulwhentwoormorecomponentsneedtoexchangedata,andthecomponentsperformtransfersatdifferingspeeds.Cachessolvethetransferproblembyprovidingabufferofintermediatespeedbetweenthecomponents.Ifthefastdevicefindsthedataitneedsinthecache,itneednotwaitfortheslowerdevice.Thedatainthecachemustbekeptconsistentwiththedatainthecomponents.Ifaomponenthasadatavaluechange,andthedatumisalsointhecache,thecachemustalsobeupdated.Thisisespeciallyaproblemonmultiprocessorsystemswheremorethanoneprocessmaybeaccessingadatum.Acomponentmaybeeliminatedbyanequal-sizedcache,butonlyif:(a)thecacheandthecomponenthaveequivalentstate-savingcapacity(thatis,ifthecomponentretainsitsdatawhenelectricityisremoved,thecachemustretaindataaswell),and(b)thecacheisaffordable,becausefasterstoragetendstobemoreexpensive. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.31.14Discuss,withexamples,howtheproblemofmaintainingcoherenceofcacheddatamanifestsitselfinthefollowingprocessingenvironments:a.Single-processorsystemsb.Multiprocessorsystemsc.DistributedsystemsAnswer:Insingle-processorsystems,thememoryneedstobeupdatedwhenaprocessorissuesupdatestocachedvalues.Theseupdatescanbeperformedimmediatelyorinalazymanner.Inamultiprocessorsystem,differentprocessorsmightbecachingthesamememorylocationinitslocalcaches.Whenupdatesaremade,theothercachedlocationsneedtobeinvalidatedorupdated.Indistributedsystems,consistencyofcachedmemoryvaluesisnotanissue.However,consistencyproblemsmightarisewhenaclientcachesfiledata.1.15Describeamechanismforenforcingmemoryprotectioninordertopreventaprogramfrommodifyingthememoryassociatedwithotherprograms.Answer:Theprocessorcouldkeeptrackofwhatlocationsareassociatedwitheachprocessandlimitaccesstolocationsthatareoutsideofaprogram’sextent.Informationregardingtheextentofaprogram’smemorycouldbemaintainedbyusingbaseandlimitsregistersandbyperformingacheckforeverymemoryaccess.1.16Whatnetworkconfigurationwouldbestsuitthefollowingenvironments?a.Adormitoryfloorb.Auniversitycampusc.Astated.AnationAnswer:a.Adormitoryfloor-ALAN.b.Auniversitycampus-ALAN,possibleaWANforverylargecampuses.c.Astate-AWAN.d.Anation-AWAN.1.17Definetheessentialpropertiesofthefollowingtypesofoperatingsystems:a.Batchb.Interactivec.Timesharingd.Realtimee.Networkf.Parallelg.Distributedh.Clusteredi.Handheld 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Answer:a.Batch.Jobswithsimilarneedsarebatchedtogetherandrunthroughthecomputerasagroupbyanoperatororautomaticjobsequencer.PerformanceisincreasedbyattemptingtokeepCPUandI/Odevicesbusyatalltimesthroughbuffering,off-lineoperation,spooling,andmultiprogramming.Batchisgoodforexecutinglargejobsthatneedlittleinteraction;itcanbesubmittedandpickeduplater.b.Interactive.Thissystemiscomposedofmanyshorttransactionswheretheresultsofthenexttransactionmaybeunpredictable.Responsetimeneedstobeshort(seconds)sincetheusersubmitsandwaitsfortheresult.c.Timesharing.ThissystemsusesCPUschedulingandmultiprogrammingtoprovideeconomicalinteractiveuseofasystem.TheCPUswitchesrapidlyfromoneusertoanother.Insteadofhavingajobdefinedbyspooledcardimages,eachprogramreadsitsnextcontrolcardfromtheterminal,andoutputisnormallyprintedimmediatelytothescreen.d.Realtime.Oftenusedinadedicatedapplication,thissystemreadsinformationfromsensorsandmustrespondwithinafixedamountoftimetoensurecorrectperformance.e.Network.Providesoperatingsystemfeaturesacrossanetworksuchasfilesharing.f.SMP.UsedinsystemswheretherearemultipleCPU’seachrunningthesamecopyoftheoperatingsystem.Communicationtakesplaceacrossthesystembus.g.Distributed.Thissystemdistributescomputationamongseveralphysicalprocessors.Theprocessorsdonotsharememoryoraclock.Instead,eachprocessorhasitsownlocalmemory.Theycommunicatewitheachotherthroughvariouscommunicationlines,suchasahigh-speedbusorlocalareanetwork.h.Clustered.Aclusteredsystemcombinesmultiplecomputersintoasinglesystemtoperformcomputationaltaskdistributedacrossthecluster.i.Handheld.Asmallcomputersystemthatperformssimpletaskssuchascalendars,email,andwebbrowsing.Handheldsystemsdifferfromtraditionaldesktopsystemswithsmallermemoryanddisplayscreensandslowerprocessors.1.18Whatarethetradeoffsinherentinhandheldcomputers?Answer:HandheldcomputersaremuchsmallerthantraditionaldesktopPC’s.Thisresultsinsmallermemory,smallerscreens,andslowerprocessingcapabilitiesthanastandarddesktopPC.Becauseoftheselimitations,mosthandheldscurrentlycanperformonlybasictaskssuchascalendars,email,andsimplewordprocessing.However,duetotheirsmallsize,theyarequiteportableand,whentheyareequippedwithwirelessaccess,canprovideremoteaccesstoelectronicmailandtheworldwideweb. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Chapter22.1Theservicesandfunctionsprovidedbyanoperatingsystemcanbedividedintotwomaincategories.Brieflydescribethetwocategoriesanddiscusshowtheydiffer.Answer:Oneclassofservicesprovidedbyanoperatingsystemistoenforceprotectionbetweendifferentprocessesrunningconcurrentlyinthesystem.Processesareallowedtoaccessonlythosememorylocationsthatareassociatedwiththeiraddressspaces.Also,processesarenotallowedtocorruptfilesassociatedwithotherusers.Aprocessisalsonotallowedtoaccessdevicesdirectlywithoutoperatingsystemntervention.Thesecondclassofservicesprovidedbyanoperatingsystemistoprovidenewfunctionalitythatisnotsupporteddirectlybytheunderlyinghardware.Virtualmemoryandfilesystemsaretwosuchexamplesofnewservicesprovidedbyanoperatingsystem.2.2Listfiveservicesprovidedbyanoperatingsystemthataredesignedtomakeitmoreconvenientforuserstousethecomputersystem.Inwhatcasesitwouldbeimpossibleforuser-levelprogramstoprovidetheseservices?Explain.Answer:•Programexecution.Theoperatingsystemloadsthecontents(orsections)ofafileintomemoryandbeginsitsexecution.Auser-levelprogramcouldnotbetrustedtoproperlyallocateCPUtime.•I/Ooperations.Disks,tapes,seriallines,andotherdevicesmustbecommunicatedwithataverylowlevel.Theuserneedonlyspecifythedeviceandtheoperationtoperformonit,whilethesystemconvertsthatrequestintodevice-orcontroller-specificcommands.User-levelprogramscannotbetrustedtoonlyaccessdevicestheyshouldhaveaccesstoandtoonlyaccessthemwhentheyareotherwiseunused.•File-systemmanipulation.Therearemanydetailsinfilecreation,deletion,allocation,andnamingthatusersshouldnothavetoperform.Blocksofdiskspaceareusedbyfilesandmustbetracked.Deletingafilerequiresremovingthenamefileinformationandfreeingtheallocatedblocks.Protectionsmustalsobecheckedtoassureproperfileaccess.Userprogramscouldneitherensureadherencetoprotectionmethodsnorbetrustedtoallocateonlyfreeblocksanddeallocateblocksonfiledeletion.•Communications.Messagepassingbetweensystemsrequiresmessagesbeturnedintopacketsofinformation,senttothenetworkcontroller,transmittedacrossacommunicationsmedium,andreassembledbythedestinationsystem.Packetorderinganddatacorrectionmusttakeplace.Again,userprogramsmightnotcoordinateaccesstothenetworkdevice,ortheymightreceivepacketsdestinedforotherprocesses.•Errordetection.Errordetectionoccursatboththehardwareandsoftwarelevels.Atthehardwarelevel,alldatatransfersmustbeinspectedtoensurethatdatahave 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3notbeencorruptedintransit.Alldataonmediamustbecheckedtobesuretheyhavenotchangedsincetheywerewrittentothemedia.Atthesoftwarelevel,mediamustbecheckedfordataconsistency;forinstance,dothenumberofallocatedandunallocatedblocksofstoragematchthetotalnumberonthedevice.There,errorsarefrequentlyprocess-independent(forinstance,thecorruptionofdataonadisk),sotheremustbeaglobalprogram(theoperatingsystem)thathandlesalltypesoferrors.Also,byhavingerrorsprocessedbytheoperatingsystem,processesneednotcontaincodetocatchandcorrectalltheerrorspossibleonasystem.2.3Describethreegeneralmethodsforpassingparameterstotheoperatingsystem.Answer:a.Passparametersinregistersb.Registerspassstartingaddressesofblocksofparametersc.Parameterscanbeplaced,orpushed,ontothestackbytheprogram,andpoppedoffthestackbytheoperatingsystem.2.4Describehowyoucouldobtainastatisticalprofileoftheamountoftimespentbyaprogramexecutingdifferentsectionsofitscode.Discusstheimportanceofobtainingsuchastatisticalprofile.Answer:Onecouldissueperiodictimerinterruptsandmonitorwhatinstructionsorwhatsectionsofcodearecurrentlyexecutingwhentheinterruptsaredelivered.Astatisticalprofileofwhichpiecesofcodewereactiveshouldbeconsistentwiththetimespentbytheprogramindifferentsectionsofitscode.Oncesuchastatisticalprofilehasbeenobtained,theprogrammercouldoptimizethosesectionsofcodethatareconsumingmoreoftheCPUresources.2.5Whatarethefivemajoractivitiesofanoperatingsysteminregardtofilemanagement?Answer:•Thecreationanddeletionoffiles•Thecreationanddeletionofdirectories•Thesupportofprimitivesformanipulatingfilesanddirectories•Themappingoffilesontosecondarystorage•Thebackupoffilesonstable(nonvolatile)storagemedia2.6Whataretheadvantagesanddisadvantagesofusingthesamesystemcallinterfaceformanipulatingbothfilesanddevices?Answer:Eachdevicecanbeaccessedasthoughitwasafileinthefilesystem.Sincemostofthekerneldealswithdevicesthroughthisfileinterface,itisrelatively 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3easytoaddanewdevicedriverbyimplementingthehardware-specificcodetosupportthisabstractfileinterface.Therefore,thisbenefitsthedevelopmentofbothuserprogramcode,whichcanbewrittentoaccessdevicesandfilesinthesamemanner,anddevicedrivercode,whichcanbewrittentosupportawell-definedAPI.ThedisadvantagewithusingthesameinterfaceisthatitmightbedifficulttocapturethefunctionalityofcertaindeviceswithinthecontextofthefileaccessAPI,therebyeitherresultinginalossoffunctionalityoralossofperformance.Someofthiscouldbeovercomebytheuseofioctloperationthatprovidesageneralpurposeinterfaceforprocessestoinvokeoperationsondevices.2.7Whatisthepurposeofthecommandinterpreter?Whyisitusuallyseparatefromthekernel?Woulditbepossiblefortheusertodevelopanewcommandinterpreterusingthesystem-callinterfaceprovidedbytheoperatingsystem?Answer:Itreadscommandsfromtheuserorfromafileofcommandsandexecutesthem,usuallybyturningthemintooneormoresystemcalls.Itisusuallynotpartofthekernelsincethecommandinterpreterissubjecttochanges.Anusershouldbeabletodevelopanewcommandinterpreterusingthesystem-callinterfaceprovidedbytheoperatingsystem.Thecommandinterpreterallowsanusertocreateandmanageprocessesandalsodeterminewaysbywhichtheycommunicate(suchasthroughpipesandfiles).Asallofthisfunctionalitycouldbeaccessedbyanuser-levelprogramusingthesystemcalls,itshouldbepossiblefortheusertodevelopanewcommand-lineinterpreter.2.8Whatarethetwomodelsofinterprocesscommunication?Whatarethestrengthsandweaknessesofthetwoapproaches?Answer:Thetwomodelsofinterprocesscommunicationaremessage-passingmodelandtheshared-memorymodel.2.9Whyistheseparationofmechanismandpolicydesirable?Answer:Mechanismandpolicymustbeseparatetoensurethatsystemsareeasytomodify.Notwosysteminstallationsarethesame,soeachinstallationmaywanttotunetheoperatingsystemtosuititsneeds.Withmechanismandpolicyseparate,thepolicymaybechangedatwillwhilethemechanismstaysunchanged.Thisarrangementprovidesamoreflexiblesystem.2.10WhydoesJavaprovidetheabilitytocallfromaJavaprogramnativemethodsthatarewrittenin,say,CorC++?Provideanexampleofasituationinwhichanativemethodisuseful.Answer:JavaprogramsareintendedtobeplatformI/Oindependent.Therefore,thelanguagedoesnotprovideaccesstomostspecificsystemresourcessuchasreading 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3fromI/Odevicesorports.ToperformasystemI/Ospecificoperation,youmustwriteitinalanguagethatsupportssuchfeatures(suchasCorC++.)KeepinmindthataJavaprogramthatcallsanativemethodwritteninanotherlanguagewillnolongerbearchitecture-neutral.2.11Itissometimesdifficulttoachievealayeredapproachiftwocomponentsoftheoperatingsystemaredependentoneachother.Identifyascenarioinwhichitisunclearhowtolayertwosystemcomponentsthatrequiretightcouplingoftheirfunctionalities.Answer:Thevirtualmemorysubsystemandthestoragesubsystemaretypicallytightly-coupledandrequirescarefuldesigninalayeredsystemduetothefollowinginteractions.Manysystemsallowfilestobemappedintothevirtualmemoryspaceofanexecutingprocess.Ontheotherhand,thevirtualmemorysubsystemtypicallyusesthestoragesystemtoprovidethebackingstoreforpagesthatdonotcurrentlyresideinmemory.Also,updatestothefilesystemaresometimesbufferedinphysicalmemorybeforeitisflushedtodisk,therebyrequiringcarefulcoordinationoftheusageofmemorybetweenthevirtualmemorysubsystemandthefilesystem.2.12Whatisthemainadvantageofthemicrokernelapproachtosystemdesign?Howdouserprogramsandsystemservicesinteractinamicrokernelarchitecture?Whatarethedisadvantagesofusingthemicrokernelapproach?Answer:Benefitstypicallyincludethefollowing(a)addinganewservicedoesnotrequiremodifyingthekernel,(b)itismoresecureasmoreoperationsaredoneinusermodethaninkernelmode,and(c)asimplerkerneldesignandfunctionalitytypicallyresultsinamorereliableoperatingsystem.Userprogramsandsystemservicesinteractinamicrokernelarchitecturebyusinginterprocesscommunicationmechanismssuchasmessaging.Thesemessagesareconveyedbytheoperatingsystem.Theprimarydisadvantageofthemicrokernelarchitecturearetheoverheadsassociatedwithinterprocesscommunicationandthefrequentuseoftheoperatingsystem’smessagingfunctionsinordertoenabletheuserprocessandthesystemservicetointeractwitheachother.2.13Inwhatwaysisthemodularkernelapproachsimilartothelayeredapproach?Inwhatwaysdoesitdifferfromthelayeredapproach?Answer:Themodularkernelapproachrequiressubsystemstointeractwitheachotherthroughcarefullyconstructedinterfacesthataretypicallynarrow(intermsofthefunctionalitythatisexposedtoexternalmodules).Thelayeredkernelapproachissimilarinthatrespect.However,thelayeredkernelimposesastrictorderingofsubsystemssuchthatsubsystemsatthelowerlayersarenotallowedtoinvokeoperationscorrespondingtotheupper-layersubsystems.Therearenosuchrestrictionsinthemodular-kernelapproach,whereinmodulesarefreetoinvokeeach 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3otherwithoutanyconstraints.2.14Whatisthemainadvantageforanoperating-systemdesignerofusingavirtual-machinearchitecture?Whatisthemainadvantageforauser?Answer:Thesystemiseasytodebug,andsecurityproblemsareeasytosolve.Virtualmachinesalsoprovideagoodplatformforoperatingsystemresearchsincemanydifferentoperatingsystemsmayrunononephysicalsystem.2.15Whyisajust-in-timecompilerusefulforexecutingJavaprograms?Answer:Javaisaninterpretedlanguage.ThismeansthattheJVMinterpretsthebytecodeinstructionsoneatatime.Typically,mostinterpretedenvironmentsareslowerthanrunningnativebinaries,fortheinterpretationprocessrequiresconvertingeachinstructionintonativemachinecode.Ajust-in-time(JIT)compilercompilesthebytecodeforamethodintonativemachinecodethefirsttimethemethodisencountered.ThismeansthattheJavaprogramisessentiallyrunningasanativeapplication(ofcourse,theconversionprocessoftheJITtakestimeaswellbutnotasmuchasbytecodeinterpretation.)Furthermore,theJITcachescompiledcodesothatitmaybereusedthenexttimethemethodisencountered.AJavaprogramthatisrunbyaJITratherthanatraditionalinterpretertypicallyrunsmuchfaster.2.16WhatistherelationshipbetweenaguestoperatingsystemandahostoperatingsysteminasystemlikeVMware?Whatfactorsneedtobeconsideredinchoosingthehostoperatingsystem?Answer:Aguestoperatingsystemprovidesitsservicesbymappingthemontothefunctionalityprovidedbythehostoperatingsystem.Akeyissuethatneedstobeconsideredinchoosingthehostoperatingsystemiswhetheritissufficientlygeneralintermsofitssystem-callinterfaceinordertobeabletosupportthefunctionalityassociatedwiththeguestoperatingsystem.2.17TheexperimentalSynthesisoperatingsystemhasanassemblerincorporatedwithinthekernel.Tooptimizesystem-callperformance,thekernelassemblesroutineswithinkernelspacetominimizethepaththatthesystemcallmusttakethroughthekernel.Thisapproachistheantithesisofthelayeredapproach,inwhichthepaththroughthekernelisextendedtomakebuildingtheoperatingsystemeasier.DiscusstheprosandconsoftheSynthesisapproachtokerneldesignandtosystem-performanceoptimization.Answer:Synthesisisimpressiveduetotheperformanceitachievesthroughon-the-flycompilation.Unfortunately,itisdifficulttodebugproblemswithinthekernelduetothefluidityofthecode.Also,suchcompilationissystemspecific,makingSynthesisdifficulttoport(anewcompilermustbewrittenforeach 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3architecture).2.18InSection2.3,wedescribedaprogramthatcopiesthecontentsofonefiletoadestinationfile.Thisprogramworksbyfirstpromptingtheuserforthenameofthesourceanddestinationfiles.WritethisprogramusingeithertheWindows32orPOSIXAPI.Besuretoincludeallnecessaryerrorchecking,includingensuringthatthesourcefileexists.Onceyouhavecorrectlydesignedandtestedtheprogram,ifyouusedasystemthatsupportsit,runtheprogramusingautilitythattracessystemcalls.Linuxsystemsprovidetheptraceutility,andSolarissystemsusethetrussordtracecommand.OnMacOSX,thektracefacilityprovidessimilarfunctionality.Answer://Solution///Solution/Solution1:11::TheCopyprogramimplementedwithfilesystemcallsofLinux.//ThisprogramwaswrittenbyWendellonMar.5,2008.//Usage:copysrcdst#include#include#include#include#defineBUFSIZE8192intmain(intargc,char**argv){if(argc!=3){printf("nusage:copysrcdstn");return-1;}intsrc,dst;charbuf[BUFSIZE];intn;src=open(argv[1],O_RDONLY);dst=open(argv[2],O_RDWR|O_CREAT|O_TRUNC,S_IRUSR|S_IWUSR|S_IXUSR);while((n=read(src,buf,BUFSIZE))>0){if(write(dst,buf,n)!=n)printf("writeerror!");}if(n<0)printf("readerror!"); 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3close(src);close(dst);exit(0);}//solution///solution/solution2:22::usingWindowsCopyFile#include#include#defineBUF_SIZE256intmain(intargc,LPTSTRargv[]){HANDLEhIn,hOut;DWORDnIn,nOut;CHARBuffer[BUF_SIZE];if(argc!=3){printf("Usage:cpfile1file2n");return1;}hIn=CreateFile(argv[1],GENERIC_READ,FILE_SHARE_READ,NULL,OPEN_EXISTING,FILE_ATTRIBUTE_NORMAL,NULL);if(hIn==INVALID_HANDLE_VALUE){printf("Cannotopeninputfile.Error:%xn",GetLastError());return2;}hOut=CreateFile(argv[2],GENERIC_WRITE,0,NULL,CREATE_ALWAYS,FILE_ATTRIBUTE_NORMAL,NULL);if(hOut==INVALID_HANDLE_VALUE){printf("Cannotopenoutputfile.Error:%xn",GetLastError());return3;}while(ReadFile(hIn,Buffer,BUF_SIZE,&nIn,NULL)&&nIn>0){WriteFile(hOut,Buffer,nIn,&nOut,NULL);if(nIn!=nOut){printf("Fatalwriteerror:%xn",GetLastError());return4;}}CloseHandle(hIn); 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3CloseHandle(hOut);return0;}//solution///solution/solution3:33::usingWindowsAPI#include#include#defineBUF_SIZE256intmain(intargc,LPTSTRargv[]){if(argc!=3){printf("Usage:cpfile1file2n");return1;}if(!CopyFile(argv[1],argv[2],FALSE)){printf("CopyFileError:%xn",GetLastError());return2;}return0;}/*Sorry,Thecopyprogramhasn’tfinishednowusingPOSIXAPI,SolarisAPIorMacOsXAPI.*/ 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Chapter33.1Describethedifferencesamongshort-term,medium-term,andlong-termscheduling.Answer:�Short-term(CPUscheduler)——selectsfromjobsinmemorythosejobsthatarereadytoexecuteandallocatestheCPUtothem.�Medium-term——usedespeciallywithtime-sharingsystemsasanintermediateschedulinglevel.Aswappingschemeisimplementedtoremovepartiallyrunprogramsfrommemoryandreinstatethemlatertocontinuewheretheyleftoff.�Long-term(jobscheduler)——determineswhichjobsarebroughtintomemoryforprocessing.Theprimarydifferenceisinthefrequencyoftheirexecution.Theshort-termmustselectanewprocessquiteoften.Long-termisusedmuchlessoftensinceithandlesplacingjobsinthesystemandmaywaitawhileforajobtofinishbeforeitadmitsanotherone.3.2Describetheactionstakenbyakerneltocontext-switchbetweenpro-cesses.Answer:Ingeneral,theoperatingsystemmustsavethestateofthecurrentlyrunningprocessandrestorethestateoftheprocessscheduledtoberunnext.SavingthestateofaprocesstypicallyincludesthevaluesofalltheCPUregistersinadditiontomemoryallocation.Contextswitchesmustalsoperformmanyarchitecture-specificoperations,includingflushingdataandinstructioncaches.3.3ConsidertheRPCmechanism.Describetheundesirablecircumstancesthatcouldarisefromnotenforcingeitherthe"atmostonce"or"exactlyonce"semantics.Describepossibleusesforamechanismthathadneitheroftheseguarantees.Answer:IfanRPCmechanismcouldnotsupporteitherthe“atmostonce”or“atleastonce”semantics,thentheRPCservercannotguaranteethataremoteprocedurewillnotbeinvokedmultipleoccurrences.Considerifaremoteprocedurewerewithdrawingmoneyfromabankaccountonasystemthatdidnotsupportthesesemantics.Itispossiblethatasingleinvocationoftheremoteproceduremightleadtomultiplewithdrawalsontheserver.Forasystemtosupporteitherofthesesemanticsgenerallyrequirestheservermaintainsomeformofclientstatesuchasthetimestampdescribedinthetext.Ifasystemwereunabletosupporteitherofthesesematics,thensuchasystemcouldonlysafelyprovideremoteproceduresthatdonotalterdataorprovidetime-sensitiveresults.Usingourbankaccuntasanexample,wecertainlyrequire“atmostonce”or“atleastonce”semanticsforperformingawithdrawal(ordeposit!)However,aninquiryintoanaccountbalanceorotheraccuntinformationsuchasname,address,etc.doesnotrequirethesesemantics. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.33.4UsingtheprogramshowninFigure3.24,explainwhatwillbeoutputatLineA.Answer:PARENT:value=53.5Whatarethebenefitsanddetrimentsofeachofthefollowing?Considerboththesystemsandtheprogrammers"levels.a.Symmetricandasymmetriccommunicationb.Automaticandexplicitbufferingc.Sendbycopyandsendbyreferenced.Fixed-sizedandvariable-sizedmessagesAnswer:a.Symmetricandasymmetriccommunication—Abenefitofsymmetriccommunicationisthatitallowsarendezvousbetweenthesenderandreceiver.Adisadvantageofablockingsendisthatarendezvousmaynotberequiredandthemessagecouldbedeliveredasynchronously;receivedatapointofnointeresttothesender.Asaresult,message-passingsystemsoftenprovidebothformsofsynchronization.b.Automaticandexplicitbuffering—Automaticbufferingprovidesaqueuewithindefinitelength;thusensuringthesenderwillneverhavetoblockwhilewaitingtocopyamessage.Therearenospecificationshowautomaticbufferingwillbeprovided;oneschememayreservesufficientlylargememorywheremuchofthememoryiswasted.Explicitbufferingspecifieshowlargethebufferis.Inthissituation,thesendermaybeblockedwhilewaitingforavailablespaceinthequeue.However,itislesslikelymemorywillbewastedwithexplicitbuffering.c.Sendbycopyandsendbyreference—Sendbycopydoesnotallowthereceivertoalterthestateoftheparameter;sendbyreferencedoesallowit.Abenefitofsendbyreferenceisthatitallowstheprogrammertowriteadistributedversionofacentralizedapplication.Java’sRMIprovidesboth,howeverpassingaparameterbyreferencerequiresdeclaringtheparameterasaremoteobjectaswell.d.Fixed-sizedandvariable-sizedmessages—Theimplicationsofthisaremostlyrelatedtobufferingissues;withfixed-sizemessages,abufferwithaspecificsizecanholdaknownnumberofmessages.Thenumberofvariable-sizedmessagesthatcanbeheldbysuchabufferisunknown.ConsiderhowWindows2000handlesthissituation:withfixed-sizedmessages(anything<256bytes),themessagesarecopiedfromtheaddressspaceofthesendertotheaddressspaceofthereceivingprocess.Largermessages(i.e.variable-sizedmessages)usesharedmemorytopassthemessage.3.6TheFibonaccisequenceistheseriesofnumbers0,1,1,2,3,5,8,....Formally,itcanbeexpressedas:fib0=0fib1=1fibn=fibn-1+fibn-2 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3WriteaCprogramusingthefork()systemcallthatthatgeneratestheFibonaccisequenceinthechildprocess.Thenumberofthesequencewillbeprovidedinthecommandline.Forexample,if5isprovided,thefirstfivenumbersintheFibonaccisequencewillbeoutputbythechildprocess.Becausetheparentandchildprocesseshavetheirowncopiesofthedata,itwillbenecessaryforthechildtooutputthesequence.Havetheparentinvokethewait()calltowaitforthechildprocesstocompletebeforeexitingtheprogram.Performnecessaryerrorcheckingtoensurethatanon-negativenumberispassedonthecommandline.Answer://Thisprogramsolvesexercise3.6intmain(intargc,char*argv[]){if(argc!=2)exit(0);pid_tpid;inti,a,b,fib;intn=atoi(argv[1]);/*forkanotherprocess*/pid=fork();if(pid<0){/*erroroccurred*/fprintf(stderr,"ForkFailedn");exit(-1);}elseif(pid==0){/*childprocess*/if(n==1)printf("0n");elseif(n==2)printf("0,1n");elseif(n>2){a=0;b=1;printf("0,1,");for(i=3;i#include#defineMAX_STRING256intmain(intargc,char*argv[]){if(argc<2)exit(0);STARTUPINFOsi;PROCESS_INFORMATIONpi;charcommand[MAX_STRING];ZeroMemory(&si,sizeof(si));si.cb=sizeof(si);ZeroMemory(&pi,sizeof(pi));sprintf(command,"fib.exe%d",atoi(argv[1]));//Startthechildprocess.if(!CreateProcess(NULL,//Nomodulename(usecommandline).command,//Commandline.NULL,//Processhandlenotinheritable. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3NULL,//Threadhandlenotinheritable.FALSE,//SethandleinheritancetoFALSE.0,//Nocreationflags.NULL,//Useparent"senvironmentblock.NULL,//Useparent"sstartingdirectory.&si,//PointertoSTARTUPINFOstructure.&pi)//PointertoPROCESS_INFORMATIONstructure.){printf("CreateProcessfailed(%d).n",GetLastError());return-1;}//Waituntilchildprocessexits.WaitForSingleObject(pi.hProcess,INFINITE);//Closeprocessandthreadhandles.CloseHandle(pi.hProcess);CloseHandle(pi.hThread);}//program2:fib#include#includeintmain(intargc,char*argv[]){intmax=atoi(argv[1]);if(max<=0)exit(0);else{if(max==1)printf("0n");elseif(max==2)printf("0,1n");else{inta=0;intb=1;intfib;printf("0,1,");for(inti=3;i#include#include#include#include 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3#definePERMS(S_IRUSR|S_IWUSR)#defineMAX_SEQUENCE10typedefstruct{longfib_sequence[MAX_SEQUENCE];intsequence_size;}shared_data;intmain(intargc,char*argv[]){inti,seq_size;/*theprocessidentifier*/pid_tpid;/*theidofthesharedmemorysegment*/intsegment_id;/*apointertothesharedmemorysegment*/shared_data*shared_memory;/*dosomeerrorcheckingtoensuretheparameterwaspassed*/if(argc!=2){fprintf(stderr,"Usage:./shm-fibn");return-1;}seq_size=atoi(argv[1]);if(seq_size>MAX_SEQUENCE){fprintf(stderr,"sequencesizemustbe<%dn",MAX_SEQUENCE);return-1;}/*allocateasharedmemorysegment*/if((segment_id=shmget(IPC_PRIVATE,sizeof(shared_data),PERMS))==-1){fprintf(stderr,"Unabletocreatesharedmemorysegmentn");return1;}printf("Createdsharedmemorysegment%dn",segment_id);/*nowattachthesharedmemorysegmentatthespecifiedaddress*/if((shared_memory=(shared_data*)shmat(segment_id,0,0))==(shared_data*)-1){ 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3fprintf(stderr,"Unabletoattachtosegment%dn",segment_id);return0;}/*setthesizeofthesequence*/shared_memory->sequence_size=seq_size;/*nowforkachildprocess*/if((pid=fork())==(pid_t)-1){return1;}/***nowcreateachildprocessandhavethechildprocessset*thethesharedmemorysegmenttoacertainvalue.*Theparentprocesswillinquireonthissharedvaluewhen*itreturnsfromwait().Thus,thecalltowait()providesthesynchronization.*/if(pid==0){/**childcode*/printf("CHILD:sharedmemoryattachedataddress%pn",shared_memory);/*nowhavethechildgeneratetheFibonaccisequence....*/shared_memory->fib_sequence[0]=0;shared_memory->fib_sequence[1]=1;for(i=2;isequence_size;i++)shared_memory->fib_sequence[i]=shared_memory->fib_sequence[i-1]+shared_memory->fib_sequence[i-2];/*nowdetachthesharedmemorysegment*/shmdt((void*)shared_memory);}else{/*parentcode*/wait(NULL);for(i=0;isequence_size;i++)printf("PARENT:%d:%ldn",i,shared_memory->fib_sequence[i]);/*nowdetachandremovethesharedmemorysegment*/shmdt((void*)shared_memory);shmctl(segment_id,IPC_RMID,NULL);} 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3return0;}3.11MostUNIXandLinuxsystemsprovidetheipcscommand.ThiscommandliststhestatusofvariousPOSIXinterprocesscommunicationmechanisms,includingshared-memorysegments.Muchoftheinformationforthecommandcomesfromthedatastructurestructshmid_ds,whichisavailableinthe/usr/include/sys/shm.hfile.Someofthefieldsofthisstructureinclude:�intshmsegsz—sizeoftheshared-memorysegment�shortshmnattch—numberofattachestotheshared-memorysegment�structipcpermshmperm—permissionstructureoftheshared-memorysegmentThestructipcpermdatastructure(whichisavailableinthefile/usr/include/sys/ipc.h)containsthefields:�unsignedshortuid—identifieroftheuseroftheshared-memorysegment�unsignedshortmode—permissionmodes�keytkey(onLinuxsystems,key)—user-specifiedkeyidentifierThepermissionmodesaresetaccordingtohowtheshared-memorysegmentisestablishedwiththeshmget()systemcall.Permissionsareidentifiedaccordingtothefollowing:ModeMeaning0400Readpermissionofowner.0200Writepermissionofowner.0040Readpermissionofgroup.0020Writepermissionofgroup.0004Readpermissionofworld.0002Writepermissionofworld.PermissionscanbeaccessedbyusingthebitwiseANDoperator&.Forexample,ifthestatementmode&0400evaluatestotrue,thepermissionmodeallowsreadpermissionbytheowneroftheshared-memorysegment.Shared-memorysegmentscanbeidentifiedaccordingtoauser-specifiedkeyoraccordingtotheintegervaluereturnedfromtheshmget()systemcall,whichrepresentstheintegeridentifieroftheshared-memorysegmentcreated.Theshmdsstructureforagivenintegersegmentidentifiercanbeobtainedwiththefollowingshmctl()systemcall:/*identifierofthesharedmemorysegment*/intsegmentid;shmdsshmbuffer;shmctl(segmentid,IPCSTAT,&shmbuffer);Ifsuccessful,shmctl()returns0;otherwise,itreturns-1.WriteaCprogramthatispassedanidentifierforashared-memorysegment.Thisprogramwillinvoketheshmctl()functiontoobtainitsshmdsstructure.Itwillthenoutputthefollowingvaluesofthegivenshared-memorysegment:�SegmentID�Key�Mode 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3�OwnerUID�Size�NumberofattachesAnswer://ThisprogramillustratesthefunctionalityoftheipcscommandonPOSIXsystems.//ThisprogramiswrittenforLinux2.4systems.//GettingittoworkonSolaris,OSX,etc.willrequiremodifyingthesourcecodewherecommented.//Usage:gcc-osmsm.c//./sm#include#include#includeintmain(intargc,char*argv[]){/*thesegmentnumber*/intsegment_id;/*permissionsofthesegment*/unsignedshortmode;/**thesharedmemorysegment*/structshmid_dsshmbuffer;/**dosomeerrorchecking*/if(argc<2){fprintf(stderr,"Usage:smn");return-1;}/***thisneedstobesettothe*sharedmemorysegmentnumber*beingattachedto.*/segment_id=atoi(argv[1]);/*gettheshm_dsinformation*/if(shmctl(segment_id,IPC_STAT,&shmbuffer)==-1){fprintf(stderr,"Unabletoaccesssegment%dn",segment_id); 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3return-1;}/**nowreportthefieldsinshm_ds*/printf("IDttKEYtMODEttOWNERtSIZEtATTTACHESn");printf("--tt---t----tt-----t----t---------n");/**Linuxhas__keyratherthankeyfield*/printf("%dt%dt",segment_id,shmbuffer.shm_perm.__key);/**MacOSXDarwinusesthekeyfield*///printf("%dt%dt",segment_id,shmbuffer.shm_perm.key);/**reportonthepermission*/mode=shmbuffer.shm_perm.mode;/**reportonthepermission*/mode=shmbuffer.shm_perm.mode;/**OWNER*/if(mode&0400)printf("r");elseprintf("-");if(mode&0200)printf("w");elseprintf("-");if(mode&0100)printf("a");elseprintf("-");/**GROUP*/if(mode&0040)printf("r");elseprintf("-");if(mode&0020)printf("w");elseprintf("-");if(mode&0010)printf("a"); 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3elseprintf("-");/**WORLD*/if(mode&0004)printf("r");elseprintf("-");if(mode&0002)printf("w");elseprintf("-");if(mode&0001)printf("a");elseprintf("-");/**Darwin(MacOSX)hasuser_from_uid()function*///printf("t%st",user_from_uid(shmbuffer.shm_perm.uid,0));printf("t%dt",shmbuffer.shm_perm.uid);printf("%dt",shmbuffer.shm_segsz);printf("%dt",shmbuffer.shm_nattch);//printf("timeoflastattach%dn",shmbuffer.shm_atime);printf("n");return0;} 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Chapter44.1Providetwoprogrammingexamplesinwhichmultithreadingdoesnotprovidebetterperformancethanasingle-threadedsolutionAnswer:(1)Anykindofsequentialprogramisnotagoodcandidatetobethreaded.Anexampleofthisisaprogramthatcalculatesanindividualtaxreturn.(2)Anotherexampleisa"shell"programsuchastheC-shellorKornshell.Suchaprogrammustcloselymonitoritsownworkingspacesuchasopenfiles,environmentvariables,andcurrentworkingdirectory.4.2Describetheactionstakenbyathreadlibrarytocontextswitchbetweenuser-levelthreads.Answer:Contextswitchingbetweenuserthreadsisquitesimilartoswitchingbetweenkernelthreads,althoughitisdependentonthethreadslibraryandhowitmapsuserthreadstokernelthreads.Ingeneral,contextswitchingbetweenuserthreadsinvolvestakingauserthreadofitsLWPandreplacingitwithanotherthread.Thisacttypicallyinvolvessavingandrestoringthestateoftheregisters.4.3Underwhatcircumstancesdoesamultithreadedsolutionusingmultiplekernelthreadsprovidebetterperformancethanasingle-threadedsolutiononasingle-processorsystem?Answer:Whenakernelthreadsuffersapagefault,anotherkernelthreadcanbeswitchedintousetheinterleavingtimeinausefulmanner.Asingle-threadedprocess,ontheotherhand,willnotbecapableofperformingusefulworkwhenapagefaulttakesplace.Therefore,inscenarioswhereaprogrammightsufferfromfrequentpagefaultsorhastowaitforothersystemevents,amulti-threadedsolutionwouldperformbetterevenonasingle-processorsystem.4.4Whichofthefollowingcomponentsofprogramstatearesharedacrossthreadsinamultithreadedprocess?a.Registervaluesb.Heapmemoryc.Globalvariablesd.StackmemoryAnswer:Thethreadsofamultithreadedprocessshareheapmemoryandglobalvariables.Eachthreadhasitsseparatesetofregistervaluesandaseparatestack.4.5Canamultithreadedsolutionusingmultipleuser-levelthreadsachieve 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3betterperformanceonamultiprocessorsystemthanonasingle-processorsystem?Answer:Amultithreadedsystemcomprisingofmultipleuser-levelthreadscannotmakeuseofthedifferentprocessorsinamultiprocessorsystemsimultaneously.Theoperatingsystemseesonlyasingleprocessandwillnotschedulethedifferentthreadsoftheprocessonseparateprocessors.Consequently,thereisnoperformancebenefitassociatedwithexecutingmultipleuser-levelthreadsonamultiprocessorsystem.4.6AsdescribedinSection4.5.2,Linuxdoesnotdistinguishbetweenprocessesandthreads.Instead,Linuxtreatsbothinthesameway,allowingatasktobemoreakintoaprocessorathreaddependingonthesetofflagspassedtotheclone()systemcall.However,manyoperatingsystems—suchasWindowsXPandSolaris—treatprocessesandthreadsdifferently.Typically,suchsystemsuseanotationwhereinthedatastructureforaprocesscontainspointerstotheseparatethreadsbelongingtotheprocess.Contrastthesetwoapproachesformodelingprocessesandthreadswithinthekernel.Answer:Ononehand,insystemswhereprocessesandthreadsareconsideredassimilarentities,someoftheoperatingsystemcodecouldbesimplified.Ascheduler,forinstance,canconsiderthedifferentprocessesandthreadsinequalfootingwithoutrequiringspecialcodetoexaminethethreadsassociatedwithaprocessduringeveryschedulingstep.Ontheotherhand,thisuniformitycouldmakeithardertoimposeprocess-wideresourceconstraintsinadirectmanner.Instead,someextracomplexityisrequiredtoidentifywhichthreadscorrespondtowhichprocessandperformtherelevantaccountingtasks.4.7TheprogramshowninFigure4.11usesthePthreadsAPI.WhatwouldbeoutputfromtheprogramatLINECandLINEP?include#includeintvalue=0;void*runner(void*param);/*thethread*/intmain(){intpid;pthread_ttid;pthread_attr_tattr;pid=fork();if(pid==0){pthread_attr_init(&attr); 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3pthread_create(&tid,&attr,runner,NULL);pthread_join(tid,NULL);printf("CHILD:value=%dn",value);/*LINEC*/}elseif(pid>0){wait(NULL);printf("PARENT:value=%dn",value);/*LINEP*/}}void*runner(void*param){value=5;pthread_exit(0);}Answer:OutputatLINECisCHILD:CCHILD:HILD:value=5vvalue=5alue=5.OutputatLINEPisPARENT:PPARENT:ARENT:value=0vvalue=0alue=0.4.8Consideramultiprocessorsystemandamultithreadedprogramwrittenusingthemany-to-manythreadingmodel.Letthenumberofuser-levelthreadsintheprogrambemorethanthenumberofprocessorsinthesystem.Discusstheperformanceimplicationsofthefollowingscenarios.a.Thenumberofkernelthreadsallocatedtotheprogramislessthanthenumberofprocessors.b.Thenumberofkernelthreadsallocatedtotheprogramisequaltothenumberofprocessors.c.Thenumberofkernelthreadsallocatedtotheprogramisgreaterthanthenumberofprocessorsbutlessthanthenumberofuserlevelthreads.Answer:Whenthenumberofkernelthreadsislessthanthenumberofprocessors,thensomeoftheprocessorswouldremainidlesincetheschedulermapsonlykernelthreadstoprocessorsandnotuser-levelthreadstoprocessors.Whenthenumberofkernelthreadsisexactlyequaltothenumberofprocessors,thenitispossiblethatalloftheprocessorsmightbeutilizedsimultaneously.However,whenakernelthreadblocksinsidethekernel(duetoapagefaultorwhileinvokingsystemcalls),thecorrespondingprocessorwouldremainidle.Whentherearemorekernelthreadsthanprocessors,ablockedkernelthreadcouldbeswappedoutinfavorofanotherkernelthreadthatisreadytoexecute,therebyincreasingtheutilizationofthemultiprocessorsystem.4.9WriteamultithreadedJava,Pthreads,orWin32programthatoutputsprimenumbers.Thisprogramshouldworkasfollows:Theuserwillruntheprogramandwillenteranumberonthecommandline.Theprogramwillthencreateaseparatethreadthatoutputsalltheprimenumberslessthanorequaltothenumberenteredbytheuser. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Answer:(1)//amultithreadedJavaprogramclassPrimesThreadimplementsRunnable{privateintnum;privateint[]primeNums;publicPrimesThread(intnum){if(num<2)thrownewIllegalArgumentException();this.num=num;}publicvoidrun(){inti,j;primeNums=newint[num+1];primeNums[1]=0;for(i=2;i<=num;i++)primeNums[i]=1;for(i=2;i<=num/2;i++)for(j=2;j<=num/i;j++)primeNums[i*j]=0;for(i=1;i<=num;i++)if(primeNums[i]>0)System.out.println(i);}}publicclassPrimes{publicstaticvoidmain(Stringargs[]){if(args.length==0){System.out.println("Usage:Primes");System.exit(0);}elsenewThread(newPrimesThread(Integer.parseInt(args[0]))).start();}}(2)Win32programthatoutputsprimenumbers#include#include 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3/**wewillonlyallowupto256primenumbers*/#defineMAX_SIZE256intprimes[MAX_SIZE];/*thethreadrunsinthisseparatefunction*/DWORDWINAPISummation(PVOIDParam){DWORDupper=*(DWORD*)Param;inti,j;primes[1]=0;for(i=2;i<=upper;i++)primes[i]=1;for(i=2;i<=upper/2;i++)for(j=2;j<=upper/i;j++)primes[i*j]=0;return0;}intmain(intargc,char*argv[]){DWORDThreadId;HANDLEThreadHandle;intParam;//dosomebasicerrorcheckingif(argc!=2){fprintf(stderr,"Anintegerparameterisrequiredn");return-1;}Param=atoi(argv[1]);if(Param<2){fprintf(stderr,"aninteger>=2isrequiredn");return-1;}//createthethreadThreadHandle=CreateThread(NULL,0,Summation,&Param,0,&ThreadId);if(ThreadHandle!=NULL){WaitForSingleObject(ThreadHandle,INFINITE);CloseHandle(ThreadHandle); 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3/**nowoutputtheprimenumbers*/for(inti=1;i<=Param;i++)if(primes[i]>0)printf("%dn",i);}}(3)Posixprogramthatoutputsprimenumbers#include#include/**wewillonlyallowupto256primenumbers*/#defineMAX_SIZE256intprimes[MAX_SIZE];void*runner(void*param);/*thethread*/intmain(intargc,char*argv[]){inti;pthread_ttid;/*thethreadidentifier*/pthread_attr_tattr;/*setofattributesforthethread*/if(argc!=2){fprintf(stderr,"usage:a.outn");return-1;}if(atoi(argv[1])<2){fprintf(stderr,"Argument%dmustbe>=2n",atoi(argv[1]));return-1;}/*getthedefaultattributes*/pthread_attr_init(&attr);/*createthethread*/pthread_create(&tid,&attr,runner,argv[1]);/*nowwaitforthethreadtoexit*/pthread_join(tid,NULL);/**nowoutputtheprimenumbers*/for(i=1;i<=atoi(argv[1]);i++)if(primes[i]>0)printf("%dn",i);}/*GenerateprimesusingtheSieveofEratosthenes.*/ 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3void*runner(void*param){inti,j;intupper=atoi(param);primes[1]=0;for(i=2;i<=upper;i++)primes[i]=1;for(i=2;i<=upper/2;i++)for(j=2;j<=upper/i;j++)primes[i*j]=0;pthread_exit(0);}4.10Modifythesocket-baseddateserver(Figure3.19)inChapter3sothattheserverserviceseachclientrequestinaseparatethread.Answer:/*Server.javaThisisthedateserverwhereeachclientisservicedinaseparatethread.Theserverlistensonport6013.*/importjava.net.*;importjava.io.*;publicclassConnectionimplementsRunnable{privateSocketoutputLine;publicConnection(Sockets){outputLine=s;}publicvoidrun(){//getOutputStreamreturnsanOutputStreamobject//allowingordinaryfileIOoverthesocket.try{//createanewPrintWriterwithautomaticflushingPrintWriterpout=newPrintWriter(outputLine.getOutputStream(),true);//nowsendthecurrentdatetotheclientpout.println(newjava.util.Date());//nowclosethesocketoutputLine.close();}catch(java.io.IOExceptione){System.out.println(e);}}} 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3/*Connection.javaThisistheseparatethreadthatserviceseachrequest.Thisreadsarandomfortunefromthelistoffortunes.*/importjava.net.*;importjava.io.*;publicclassConnectionimplementsRunnable{privateSocketoutputLine;publicConnection(Sockets){outputLine=s;}publicvoidrun(){//getOutputStreamreturnsanOutputStreamobject//allowingordinaryfileIOoverthesocket.try{//createanewPrintWriterwithautomaticflushingPrintWriterpout=newPrintWriter(outputLine.getOutputStream(),true);//nowsendthecurrentdatetotheclientpout.println(newjava.util.Date());//nowclosethesocketoutputLine.close();}catch(java.io.IOExceptione){System.out.println(e);}}}4.11TheFibonaccisequenceistheseriesofnumbers0,1,1,2,3,5,8,....Formally,itcanbeexpressedas:fib0=0fib1=1fibn=fibn−1+fibn−2WriteamultithreadedprogramthatgeneratestheFibonacciseriesusingeithertheJava,Pthreads,orWin32threadlibrary.Thisprogramshouldworkasfollows:TheuserwillenteronthecommandlinethenumberofFibonaccinumbersthattheprogramistogenerate.Theprogramwillthencreateaseparatethreadthatwillgenerate 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3theFibonaccinumbers,placingthesequenceindatathatissharedbythethreads(anarrayisprobablythemostconvenientdatastructure).Whenthethreadfinishesexecution,theparentthreadwilloutputthesequencegeneratedbythechildthread.BecausetheparentthreadcannotbeginoutputtingtheFibonaccisequenceuntilthechildthreadfinishes,thiswillrequirehavingtheparentthreadwaitforthechildthreadtofinishusingthetechniquesdescribedinSection4.3.Answer:(1)Javaprogram//GeneratestheFibonaccisequenceinaseparatethread.classFibThreadimplementsRunnable{privateint[]fibNums;publicFibThread(int[]fibNums){this.fibNums=fibNums;}publicvoidrun(){intlength=fibNums.length;if(length==0)return;elseif(length==1)fibNums[0]=0;elseif(length==2){fibNums[0]=0;fibNums[1]=1;}else{//length>2fibNums[0]=0;fibNums[1]=1;for(inti=2;i");System.exit(0);}elseif(Integer.parseInt(args[0])<0){System.out.println("Sequencesizemustbe>=0n"); 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3System.exit(0);}else{int[]sequence=newint[Integer.parseInt(args[0])];Threadworker=newThread(newFibThread(sequence));worker.start();try{worker.join();}catch(InterruptedExceptionie){}for(inti=0;i#include/**wewillonlyallowupto256Fibonaccinumbers*/#defineMAX_SIZE256intfibs[MAX_SIZE];/*thethreadrunsinthisseparatefunction*/DWORDWINAPISummation(PVOIDParam){DWORDupper=*(DWORD*)Param;inti;if(upper==0)return0;elseif(upper==1)fibs[0]=0;elseif(upper==2){fibs[0]=0;fibs[1]=1;}else{//sequence>2fibs[0]=0;fibs[1]=1;for(i=2;i256)){fprintf(stderr,"aninteger>=0and<256isrequiredn");return-1;}//createthethreadThreadHandle=CreateThread(NULL,0,Summation,&Param,0,&ThreadId);if(ThreadHandle!=NULL){WaitForSingleObject(ThreadHandle,INFINITE);CloseHandle(ThreadHandle);/**nowoutputtheFibonaccinumbers*/for(inti=0;i#include/**wewillonlyallowupto256fibonaccinumbers*/#defineMAX_SIZE256intfibs[MAX_SIZE];void*runner(void*param);/*thethread*/intmain(intargc,char*argv[]){inti;pthread_ttid;/*thethreadidentifier*/ 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3pthread_attr_tattr;/*setofattributesforthethread*/if(argc!=2){fprintf(stderr,"usage:a.outn");return-1;}if(atoi(argv[1])<0){fprintf(stderr,"Argument%dmustbe>=0n",atoi(argv[1]));return-1;}/*getthedefaultattributes*/pthread_attr_init(&attr);/*createthethread*/pthread_create(&tid,&attr,runner,argv[1]);/*nowwaitforthethreadtoexit*/pthread_join(tid,NULL);/**nowoutputtheFibonaccinumbers*/for(i=0;i2fibs[0]=0; 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3fibs[1]=1;for(i=2;iα>0?b.Whatisthealgorithmthatresultsfromα<β<0?Answer:a.FCFSb.LIFO5.10Explainthedifferencesinthedegreetowhichthefollowingschedulingalgorithmsdiscriminateinfavorofshortprocesses:a.FCFSb.RRc.MultilevelfeedbackqueuesAnswer:a.FCFS—discriminatesagainstshortjobssinceanyshortjobsarrivingafterlongjobswillhavealongerwaitingtime.b.RR—treatsalljobsequally(givingthemequalburstsofCPUtime)soshortjobswillbeabletoleavethesystemfastersincetheywillfinishfirst.c.Multilevelfeedbackqueues—worksimilartotheRRalgorithm—theydiscriminatefavorablytowardshortjobs.5.11UsingtheWindowsXPschedulingalgorithm,whatisthenumericpriorityofa 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3threadforthefollowingscenarios?a.AthreadintheREALTIMEPRIORITYCLASSwitharelativepriorityofHIGHEST.b.AthreadintheNORMALPRIORITYCLASSwitharelativepriorityofNORMAL.c.AthreadintheHIGHPRIORITYCLASSwitharelativepriorityofABOVENORMAL.Answer:a.26b.8c.145.12ConsidertheschedulingalgorithmintheSolarisoperatingsystemfortimesharingthreads:a.Whatisthetimequantum(inmilliseconds)forathreadwithpriority10?Withpriority55?b.Assumeathreadwithpriority35hasuseditsentiretimequantumwithoutblocking.Whatnewprioritywilltheschedulerassignthisthread?c.Assumeathreadwithpriority35blocksforI/Obeforeitstimequantumhasexpired.Whatnewprioritywilltheschedulerassignthisthread?Answer:a.160and40b.35c.545.13ThetraditionalUNIXschedulerenforcesaninverserelationshipbetweenprioritynumbersandpriorities:Thehigherthenumber,thelowerthepriority.Theschedulerrecalculatesprocessprioritiesoncepersecondusingthefollowingfunction:Priority=(RecentCPUusage/2)+Basewherebase=60andrecentCPUusagereferstoavalueindicatinghowoftenaprocesshasusedtheCPUsinceprioritieswerelastrecalculated.AssumethatrecentCPUusageforprocessP1is40,processP2is18,andprocessP3is10.Whatwillbethenewprioritiesforthesethreeprocesseswhenprioritiesarerecalculated?Basedonthisinformation,doesthetraditionalUNIXschedulerraiseorlowertherelativepriorityofaCPU-boundprocess?Answer:Theprioritiesassignedtotheprocessesare80,69,and65respectively.TheschedulerlowerstherelativepriorityofCPU-boundprocesses. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Chapter66.1Thefirstknowncorrectsoftwaresolutiontothecritical-sectionproblemfortwoprocesseswasdevelopedbyDekker.Thetwoprocesses,P0andP1,sharethefollowingvariables:booleanflag[2];/*initiallyfalse*/intturn;ThestructureofprocessPi(i==0or1)isshowninFigure6.25;theotherprocessisPj(j==1or0).Provethatthealgorithmsatisfiesallthreerequirementsforthecritical-sectionproblem.Answer:Thisalgorithmsatisfiesthethreeconditionsofmutualexclusion.(1)Mutualexclusionisensuredthroughtheuseoftheflagandturnvariables.Ifbothprocessessettheirflagtotrue,onlyonewillsucceed.Namely,theprocesswhoseturnitis.Thewaitingprocesscanonlyenteritscriticalsectionwhentheotherprocessupdatesthevalueofturn.(2)Progressisprovided,againthroughtheflagandturnvariables.Thisalgorithmdoesnotprovidestrictalternation.Rather,ifaprocesswishestoaccesstheircriticalsection,itcansettheirflagvariabletotrueandentertheircriticalsection.Itonlysetsturntothevalueoftheotherprocessuponexitingitscriticalsection.Ifthisprocesswishestoenteritscriticalsectionagain-beforetheotherprocess-itrepeatstheprocessofenteringitscriticalsectionandsettingturntotheotherprocessuponexiting.(3)BoundedwaitingispreservedthroughtheuseoftheTTturnvariable.Assumetwoprocesseswishtoentertheirrespectivecriticalsections.Theybothsettheirvalueofflagtotrue,howeveronlythethreadwhoseturnitiscanproceed,theotherthreadwaits.Ifboundedwaitingwerenotpreserved,itwouldthereforebepossiblethatthewaitingprocesswouldhavetowaitindefinitelywhilethefirstprocessrepeatedlyentered-andexited-itscriticalsection.However,Dekker’salgorithmhasaprocesssetthevalueofturntotheotherprocess,therebyensuringthattheotherprocesswillenteritscriticalsectionnext.6.2Thefirstknowncorrectsoftwaresolutiontothecritical-sectionproblemfornprocesseswithalowerboundonwaitingofn?1turnswaspresentedbyEisenbergandMcGuire.Theprocessessharethefollowingvariables:enumpstate{idle,want_in,in_cs};pstateflag[n];intturn;Alltheelementsofflagareinitiallyidle;theinitialvalueofturnisimmaterial(between0andn-1).ThestructureofprocessPiisshowninFigure6.26.Provethatthealgorithmsatisfiesallthreerequirementsforthecritical-sectionproblem. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Answer:Thisalgorithmsatisfiesthethreeconditions.Beforeweshowthatthethreeconditionsaresatisfied,wegiveabriefexplanationofwhatthealgorithmdoestoensuremutualexclusion.WhenaprocessIrequiresaccesstocriticalsection,itfirstsetsitsflagvariabletowantintoindicateitsdesire.Itthenperformsthefollowingsteps:(1)Itensuresthatallprocesseswhoseindexliesbetweenturnandiareidle.(2)Ifso,itupdatesitsflagtoin_csandcheckswhetherthereisalreadysomeotherprocessthathasupdateditsflagtoin_cs.(3)Ifnotandifitisthisprocess’sturntoenterthecriticalsectionoriftheprocessindicatedbytheturnvariableisidle,itentersthecriticalsection.Giventheabovedescription,wecanreasonabouthowthealgorithmsatisfiestherequirementsinthefollowingmanner:�Mutualexclusionisensured:Noticethataprocessentersthecriticalsectiononlyifthefollowingrequirementsissatisfied:nootherprocesshasitsflagvariablesettoin_cs.Sincetheprocesssetsitsownflagvariablesettoin_csbeforecheckingthestatusofotherprocesses,weareguaranteedthatnotwoprocesseswillenterthecriticalsectionsimultaneously.�Progressrequirementissatisfied:Considerthesituationwheremultipleprocessessimultaneouslysettheirflagvariablestoin_csandthencheckwhetherthereisanyotherprocesshastheflagvariablesettoin_cs.Whenthishappens,allprocessesrealizethattherearecompetingprocesses,enterthenextiterationoftheouterwhile(1)loopandresettheirflagvariablestowantin.Nowtheonlyprocessthatwillsetitsturnvariabletoin_csistheprocesswhoseindexisclosesttoturn.Itishoweverpossiblethatnewprocesseswhoseindexvaluesareevenclosertoturnmightdecidetoenterthecriticalsectionatthispointandthereforemightbeabletosimultaneouslysetitsflagtoin_cs.Theseprocesseswouldthenrealizetherearecompetingprocessesandmightrestarttheprocessofenteringthecriticalsection.However,ateachiteration,theindexvaluesofprocessesthatsettheirflagvariablestoin_csbecomeclosertoturnandeventuallywereachthefollowingcondition:onlyoneprocess(sayk)setsitsflagtoin_csandnootherprocesswhoseindexliesbetweenturnandkhassetitsflagtoin_cs.Thisprocessthengetstoenterthecriticalsection.�Bounded-waitingrequirementismet:Theboundedwaitingrequirementissatisfiedbythefactthatwhenaprocesskdesirestoenterthecriticalsection,itsflagisnolongersettoidle.Therefore,anyprocesswhoseindexdoesnotliebetweenturnandkcannotenterthecriticalsection.Inthemeantime,allprocesseswhoseindexfallsbetweenturnandkanddesiretoenterthecriticalsectionwouldindeedenterthecriticalsection(duetothefactthatthesystemalwaysmakesprogress)andtheturnvaluemonotonicallybecomesclosertok.Eventually,eitherturnbecomeskortherearenoprocesseswhoseindexvaluesliebetweenturnandk,andthereforeprocesskgetstoenterthecriticalsection.6.3Whatisthemeaningofthetermbusywaiting?Whatotherkindsofwaitingarethereinanoperatingsystem?Canbusywaitingbeavoidedaltogether?Explainyour 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3answer.Answer:Busywaitingmeansthataprocessiswaitingforaconditiontobesatisfiedinatightloopwithoutrelinquishtheprocessor.Alternatively,aprocesscouldwaitbyrelinquishingtheprocessor,andblockonaconditionandwaittobeawakenedatsomeappropriatetimeinthefuture.Busywaitingcanbeavoidedbutincurstheoverheadassociatedwithputtingaprocesstosleepandhavingtowakeitupwhentheappropriateprogramstateisreached.6.4Explainwhyspinlocksarenotappropriateforsingle-processorsystemsyetareoftenusedinmultiprocessorsystems.Answer:Spinlocksarenotappropriateforsingle-processorsystemsbecausetheconditionthatwouldbreakaprocessoutofthespinlockcouldbeobtainedonlybyexecutingadifferentprocess.Iftheprocessisnotrelinquishingtheprocessor,otherprocessesdonotgettheopportunitytosettheprogramconditionrequiredforthefirstprocesstomakeprogress.Inamultiprocessorsystem,otherprocessesexecuteonotherprocessorsandtherebymodifytheprogramstateinordertoreleasethefirstprocessfromthespinlock.6.5Explainwhyimplementingsynchronizationprimitivesbydisablinginterruptsisnotappropriateinasingle-processorsystemifthesynchronizationprimitivesaretobeusedinuser-levelprograms.Answer:Ifauser-levelprogramisgiventheabilitytodisableinterrupts,thenitcandisablethetimerinterruptandpreventcontextswitchingfromtakingplace,therebyallowingittousetheprocessorwithoutlettingotherprocessestoexecute.6.6Explainwhyinterruptsarenotappropriateforimplementingsynchronizationprimitivesinmultiprocessorsystems.Answer:Interruptsarenotsufficientinmultiprocessorsystemssincedisablinginterruptsonlypreventsotherprocessesfromexecutingontheprocessorinwhichinterruptsweredisabled;therearenolimitationsonwhatprocessescouldbeexecutingonotherprocessorsandthereforetheprocessdisablinginterruptscannotguaranteemutuallyexclusiveaccesstoprogramstate.6.7DescribehowtheSwap()instructioncanbeusedtoprovidemutualexclusionthatsatisfiesthebounded-waitingrequirement.Answer:do{waiting[i]=TRUE;key=TRUE; 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3while(waiting[i]&&key)key=Swap(&lock,&key);waiting[i]=FALSE;/*criticalsection*/j=(i+1)%n;while((j!=i)&&!waiting[j])j=(j+1)%n;if(j==i)lock=FALSE;elsewaiting[j]=FALSE;/*remaindersection*/}while(TRUE);6.8Serverscanbedesignedtolimitthenumberofopenconnections.Forexample,aservermaywishtohaveonlyNsocketconnectionsatanypointintime.AssoonasNconnectionsaremade,theserverwillnotacceptanotherincomingconnectionuntilanexistingconnectionisreleased.Explainhowsemaphorescanbeusedbyaservertolimitthenumberofconcurrentconnections.Answer:Asemaphoreisinitializedtothenumberofallowableopensocketconnections.Whenaconnectionisaccepted,theacquire()methodiscalled,whenaconnectionisreleased,therelease()methodiscalled.Ifthesystemreachesthenumberofallowablesocketconnections,subsequentcallstoacquire()willblockuntilanexistingconnectionisterminatedandthereleasemethodisinvoked.6.9Showthat,ifthewait()andsignal()semaphoreoperationsarenotexecutedatomically,thenmutualexclusionmaybeviolated.Answer:Awaitoperationatomicallydecrementsthevalueassociatedwithasemaphore.Iftwowaitoperationsareexecutedonasemaphorewhenitsvalueis1,ifthetwooperationsarenotperformedatomically,thenitispossiblethatbothoperationsmightproceedtodecrementthesemaphorevaluetherebyviolatingmutualexclusion.6.10Showhowtoimplementthewait()andsignal()semaphoreoperationsinmultiprocessorenvironmentsusingtheTestAndSet()instruction.Thesolutionshouldexhibitminimalbusywaiting.Answer:Hereisthepseudocodeforimplementingtheoperations:intguard=0;intsemaphorevalue=0;wait(){while(TestAndSet(&guard)==1);if(semaphorevalue==0){atomicallyaddprocesstoaqueueofprocesseswaitingforthesemaphoreandsetguardto0;}else{ 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3semaphorevalue--;guard=0;}}signal(){while(TestAndSet(&guard)==1);if(semaphorevalue==0&&thereisaprocessonthewaitqueue)wakeupthefirstprocessinthequeueofwaitingprocesses;elsesemaphorevalue++;guard=0;}6.11TheSleeping-BarberProblem.Abarbershopconsistsofawaitingroomwithnchairsandabarberroomwithonebarberchair.Iftherearenocustomerstobeserved,thebarbergoestosleep.Ifacustomerentersthebarbershopandallchairsareoccupied,thenthecustomerleavestheshop.Ifthebarberisbusybutchairsareavailable,thenthecustomersitsinoneofthefreechairs.Ifthebarberisasleep,thecustomerwakesupthebarber.Writeaprogramtocoordinatethebarberandthecustomers.Answer:(1)BarberShop.java//ThisclassdefinestheBarberShopScenario.//ThisscenarioallowsNcustomerstoenterit.//Italsocontainsanumberofchairsthatallowthecustomerstowaitin.publicclassBarberShop{privateintchairNum;privateintbarber;privateintchairState[];staticfinalintFULL=-1;staticfinalintEMPTY=0;staticfinalintOCUPIED=1;staticfinalintSLEEPING=2;staticfinalintDONE=3;staticfinalintWAITED=4;/*============================================================ConstructanewBarberShopscenarioforcustomerstogethaircutsat.Setthebarber 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3shoptohaveNnumberofchairstowaitin.Thenmakeallthechairstobeinitiallyempty.Alsosetthebarbertobeasleepsothatwhenhisfirstcustomercomesinhecanwakehimup.@parampChairNumThenumberofwaitingchairsinthisbarbershop==================================================================*/publicBarberShop(intpChairNum){chairNum=pChairNum;chairState=newint[chairNum];barber=SLEEPING;//initializeeverychairinthewaitingroomtobeemptyfor(inti=0;i0){numavail--;return;}waitingprocesses[numwaiting]=procnumber;numwaiting++;sort(waitingprocesses);while(numavail==0&&waitingprocesses[0]!=procnumber)c.wait();waitingprocesses[0]=waitingprocesses[numwaiting-1];numwaiting--;sort(waitingprocesses);numavail--;}voidreleaseprinter(){numavail++;c.broadcast();} 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3}6.19Afileistobesharedamongdifferentprocesses,eachofwhichhasauniquenumber.Thefilecanbeaccessedsimultaneouslybyseveralprocesses,subjecttothefollowingconstraint:Thesumofalluniquenumbersassociatedwithalltheprocessescurrentlyaccessingthefilemustbelessthann.Writeamonitortocoordinateaccesstothefile.Answer:Thepseudocodeisasfollows:monitorfileaccess{intcurrsum=0;intn;conditionc;voidaccessfile(intmynum){while(currsum+mynum>=n)c.wait();currsum+=mynum;}voidfinishaccess(intmynum){currsum-=mynum;c.broadcast();}}6.20Whenasignalisperformedonaconditioninsideamonitor,thesignalingprocesscaneithercontinueitsexecutionortransfercontroltotheprocessthatissignaled.Howwouldthesolutiontotheprecedingexercisedifferwiththetwodifferentwaysinwhichsignalingcanbeperformed?Answer:Thesolutiontothepreviousexerciseiscorrectunderbothsituations.However,itcouldsufferfromtheproblemthataprocessmightbeawakenedonlytofindthatitisstillnotpossibleforittomakeforwardprogresseitherbecausetherewasnotsufficientslacktobeginwithwhenaprocesswasawakenedorifaninterveningprocessgetscontrol,obtainsthemonitorandstartsaccessingthefile.Also,notethatthebroadcastoperationwakesupallofthewaitingprocesses.Ifthesignalalsotransferscontrolandthemonitorfromthecurrentthreadtothetarget,thenonecouldcheckwhetherthetargetwouldindeedbeabletomakeforwardprogressandperformthesignalonlyifititwerepossible.Thenthe“while”loopforthewaitingthreadcouldbereplacedby“if”conditionsinceitisguaranteedthattheconditionwillbesatisfiedwhentheprocessiswokenup.6.21Supposewereplacethewait()andsignal()operationsofmonitorswithasingleconstructawait(B),whereBisageneralBooleanexpressionthatcausestheprocessexecutingittowaituntilBbecomestrue.a.Writeamonitorusingthisschemetoimplementthereaders–writersproblem. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3b.Explainwhy,ingeneral,thisconstructcannotbeimplementedefficiently.c.Whatrestrictionsneedtobeputontheawaitstatementsothatitcanbeimplementedefficiently?(Hint:RestrictthegeneralityofB;seeKessels[1977].)Answer:�Thereaders-writersproblemcouldbemodifiedwiththefollowingmoregenerateawaitstatements:Areadercanperform“await(activewriters==0&&waitingwriters==0)”tocheckthattherearenoactivewritersandtherearenowaitingwritersbeforeitentersthecriticalsection.Thewritercanperforma“await(activewriters==0&&activereaders==0)”checktoensuremutuallyexclusiveaccess.�Thesystemwouldhavetocheckwhichoneofthewaitingthreadshavetobeawakenedbycheckingwhichoneoftheirwaitingconditionsaresatisfiedafterasignal.Thisrequiresconsiderablecomplexityaswellasmightrequiresomeinteractionwiththecompilertoevaluatetheconditionsatdifferentpointsintime.Onecouldrestrictthebooleanconditiontobeadisjunctionofconjunctionswitheachcomponentbeingasimplecheck(equalityorinequalitywithrespecttoastaticvalue)onaprogramvariable.Inthatcase,thebooleanconditioncouldbecommunicatedtotheruntimesystem,whichcouldperformthecheckeverytimeitneedstodeterminewhichthreadtobeawakened.6.22Writeamonitorthatimplementsanalarmclockthatenablesacallingprogramtodelayitselfforaspecifiednumberoftimeunits(ticks).Youmayassumetheexistenceofarealhardwareclockthatinvokesaproceduretickinyourmonitoratregularintervals.Answer:Hereisapseudocodeforimplementingthis:monitoralarm{conditionc;voiddelay(intticks){intbegintime=readclock();while(readclock()0))oktocross.wait();numwaitingnorth--;prev=0;}voidexitbridgenorth(){onbridge=0;oktocross.broadcast();}voidenterbridgesouth(){numwaitingsouth++;while(onbridge||(prev==1&&numwaitingnorth>0))oktocross.wait();numwaitingsouth--;prev=1;}voidexitbridgesouth(){onbridge=0;oktocross.broadcast();}}Chapter8 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.38.1Explainthedifferencebetweeninternalandexternalfragmentation.Answer:InternalFragmentationistheareainaregionorapagethatisnotusedbythejoboccupyingthatregionorpage.Thisspaceisunavailableforusebythesystemuntilthatjobisfinishedandthepageorregionisreleased.8.2Considerthefollowingprocessforgeneratingbinaries.Acompilerisusedtogeneratetheobjectcodeforindividualmodules,andalinkageeditorisusedtocombinemultipleobjectmodulesintoasingleprogrambinary.Howdoesthelinkageeditorchangethebindingofinstructionsanddatatomemoryaddresses?Whatinformationneedstobepassedfromthecompilertothelinkageeditortofacilitatethememorybindingtasksofthelinkageeditor?Answer:Thelinkageeditorhastoreplaceunresolvedsymbolicaddresseswiththeactualaddressesassociatedwiththevariablesinthefinalprogrambinary.Inordertoperformthis,themodulesshouldkeeptrackofinstructionsthatrefertounresolvedsymbols.Duringlinking,eachmoduleisassignedasequenceofaddressesintheoverallprogrambinaryandwhenthishasbeenperformed,unresolvedreferencestosymbolsexportedbythisbinarycouldbepatchedinothermodulessinceeveryothermodulewouldcontainthelistofinstructionsthatneedtobepatched.8.3Givenfivememorypartitionsof100KB,500KB,200KB,300KB,and600KB(inorder),howwouldeachofthefirst-fit,best-fit,andworst-fitalgorithmsplaceprocessesof212KB,417KB,112KB,and426KB(inorder)?Whichalgorithmmakesthemostefficientuseofmemory?Answer:(1)First-fit:a.212Kisputin500Kpartitionb.417Kisputin600Kpartitionc.112Kisputin288Kpartition(newpartition288K=500K-212K)d.426Kmustwait(2)Best-fit:e.212Kisputin300Kpartitionf.417Kisputin500Kpartitiong.112Kisputin200Kpartitionh.426Kisputin600Kpartition(3)Worst-fit:i.212Kisputin600Kpartitionj.417Kisputin500Kpartitionk.112Kisputin388Kpartitionl.426KmustwaitInthisexample,Best-fitturnsouttobethebest. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.38.4Mostsystemsallowprogramstoallocatemorememorytoitsaddressspaceduringexecution.Dataallocatedintheheapsegmentsofprogramsisanexampleofsuchallocatedmemory.Whatisrequiredtosupportdynamicmemoryallocationinthefollowingschemes:a.contiguous-memoryallocationb.puresegmentationc.purepagingAnswer:�contiguous-memoryallocation:mightrequirerelocationoftheentireprogramsincethereisnotenoughspacefortheprogramtogrowitsallocatedmemoryspace.�puresegmentation:mightalsorequirerelocationofthesegmentthatneedstobeextendedsincethereisnotenoughspaceforthesegmenttogrowitsallocatedmemoryspace.�purepaging:incrementalallocationofnewpagesispossibleinthisschemewithoutrequiringrelocationoftheprogram’saddressspace.8.5Comparethemainmemoryorganizationschemesofcontiguous-memoryallocation,puresegmentation,andpurepagingwithrespecttothefollowingissues:a.externalfragmentationb.internalfragmentationc.abilitytosharecodeacrossprocessesAnswer:ontiguousmemoryallocationschemesuffersfromexternalfragmentationasaddressspacesareallocatedcontiguouslyandholesdevelopasoldprocessesdiesandnewprocessesareinitiated.Italsodoesnotallowprocessestosharecode,sinceaprocess’svirtualmemorysegmentisnotbrokenintonon-contiguousfinegrainedsegments.Puresegmentationalsosuffersfromexternalfragmentationasasegmentofaprocessislaidoutcontiguouslyinphysicalmemoryandfragmentationwouldoccurassegmentsofdeadprocessesarereplacedbysegmentsofnewprocesses.Segmentation,however,enablesprocessestosharecode;forinstance,twodifferentprocessescouldshareacodesegmentbuthavedistinctdatasegments.Purepagingdoesnotsufferfromexternalfragmentation,butinsteadsuffersfrominternalfragmentation.Processesareallocatedinpagegranularityandifapageisnotcompletelyutilized,itresultsininternalfragmentationandacorrespondingwastageofspace.Pagingalsoenablesprocessestosharecodeatthegranularityofpages.8.6Onasystemwithpaging,aprocesscannotaccessmemorythatitdoesnotown;why?Howcouldtheoperatingsystemallowaccesstoothermemory?Whyshoulditorshoulditnot?Answer:Anaddressonapagingsystemisalogicalpagenumberandanoffset.Thephysicalpageisfoundbysearchingatablebasedonthelogicalpagenumbertoproduceaphysicalpagenumber.Becausetheoperatingsystemcontrolsthecontentsofthistable,itcanlimitaprocesstoaccessingonlythosephysicalpagesallocated 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3totheprocess.Thereisnowayforaprocesstorefertoapageitdoesnotownbecausethepagewillnotbeinthepagetable.Toallowsuchaccess,anoperatingsystemsimplyneedstoallowentriesfornon-processmemorytobeaddedtotheprocess’spagetable.Thisisusefulwhentwoormoreprocessesneedtoexchangedata—theyjustreadandwritetothesamephysicaladdresses(whichmaybeatvaryinglogicaladdresses).Thismakesforveryefficientinterprocesscommunication.8.7Comparepagingwithsegmentationwithrespecttotheamountofmemoryrequiredbytheaddresstranslationstructuresinordertoconvertvirtualaddressestophysicaladdresses.Answer:Pagingrequiresmorememoryoverheadtomaintainthetranslationstructures.Segmentationrequiresjusttworegisterspersegment:onetomaintainthebaseofthesegmentandtheothertomaintaintheextentofthesegment.Pagingontheotherhandrequiresoneentryperpage,andthisentryprovidesthephysicaladdressinwhichthepageislocated.8.8Programbinariesinmanysystemsaretypicallystructuredasfollows.Codeisstoredstartingwithasmallfixedvirtualaddresssuchas0.Thecodesegmentisfollowedbythedatasegmentthatisusedforstoringtheprogramvariables.Whentheprogramstartsexecuting,thestackisallocatedattheotherendofthevirtualaddressspaceandisallowedtogrowtowardslowervirtualaddresses.Whatisthesignificanceoftheabovestructureonthefollowingschemes:a.contiguous-memoryallocationb.puresegmentationc.purepagingAnswer:1)Contiguous-memoryallocationrequirestheoperatingsystemtoallocatetheentireextentofthevirtualaddressspacetotheprogramwhenitstartsexecuting.Thiscouldbemuchhigherthantheactualmemoryrequirementsoftheprocess.2)Puresegmentationgivestheoperatingsystemflexibilitytoassignasmallextenttoeachsegmentatprogramstartuptimeandextendthesegmentifrequired.3)Purepagingdoesnotrequiretheoperatingsystemtoallocatethemaximumextentofthevirtualaddressspacetoaprocessatstartuptime,butitstillrequirestheoperatingsystemtoallocatealargepagetablespanningalloftheprogram’svirtualaddressspace.Whenaprogramneedstoextendthestackortheheap,itneedstoallocateanewpagebutthecorrespondingpagetableentryispreallocated.8.9Considerapagingsystemwiththepagetablestoredinmemory.a.Ifamemoryreferencetakes200nanoseconds,howlongdoesapagedmemoryreferencetake?b.Ifweaddassociativeregisters,and75percentofallpage-tablereferencesarefoundintheassociativeregisters,whatistheeffectivememoryreferencetime?(Assumethatfindingapage-tableentryintheassociativeregisterstakeszerotime, 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3iftheentryisthere.)Answer:a.400nanoseconds;200nanosecondstoaccessthepagetableand200nanosecondstoaccessthewordinmemory.b.Effectiveaccesstime=0.75×(200nanoseconds)+0.25×(400nanoseconds)=250nanoseconds.8.10Whyaresegmentationandpagingsometimescombinedintoonescheme?Answer:Segmentationandpagingareoftencombinedinordertoimproveuponeachother.Segmentedpagingishelpfulwhenthepagetablebecomesverylarge.Alargecontiguoussectionofthepagetablethatisunusedcanbecollapsedintoasinglesegmenttableentrywithapage-tableaddressofzero.Pagedsegmentationhandlesthecaseofhavingverylongsegmentsthatrequirealotoftimeforallocation.Bypagingthesegments,wereducewastedmemoryduetoexternalfragmentationaswellassimplifytheallocation.8.11Explainwhyitiseasiertoshareareentrantmoduleusingsegmentationthanitistodosowhenpurepagingisused.Answer:Sincesegmentationisbasedonalogicaldivisionofmemoryratherthanaphysicalone,segmentsofanysizecanbesharedwithonlyoneentryinthesegmenttablesofeachuser.Withpagingtheremustbeacommonentryinthepagetablesforeachpagethatisshared.8.12Considerthefollowingsegmenttable:SegmentBaseLength02196001230014290100313275804195296Whatarethephysicaladdressesforthefollowinglogicaladdresses?a.0,430b.1,10c.2,500d.3,400e.4,112Answer:a.219+430=649b.2300+10=2310c.illegalreference,traptooperatingsystemd.1327+400=1727e.illegalreference,traptooperatingsystem8.13Whatisthepurposeofpagingthepagetables? 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Answer:Incertainsituationsthepagetablescouldbecomelargeenoughthatbypagingthepagetables,onecouldsimplifythememoryallocationproblem(byensuringthateverythingisallocatedasfixed-sizepagesasopposedtovariable-sizedchunks)andalsoenabletheswappingofportionsofpagetablethatarenotcurrentlyused.8.14ConsiderthehierarchicalpagingschemeusedbytheVAXarchitecture.Howmanymemoryoperationsareperformedwhenanuserprogramexecutesamemoryloadoperation?Answer:Whenamemoryloadoperationisperformed,therearethreememoryoperationsthatmightbeperformed.Oneistotranslatethepositionwherethepagetableentryforthepagecouldbefound(sincepagetablesthemselvesarepaged).Thesecondaccessistoaccessthepagetableentryitself,whilethethirdaccessistheactualmemoryloadoperation.8.15Comparethesegmentedpagingschemewiththehashedpagetablesschemeforhandlinglargeaddressspaces.Underwhatcircumstancesisoneschemepreferrableovertheother?Answer:Whenaprogramoccupiesonlyasmallportionofitslargevirtualaddressspace,ahashedpagetablemightbepreferredduetoitssmallersize.Thedisadvantagewithhashedpagetableshoweveristheproblemthatarisesduetoconflictsinmappingmultiplepagesontothesamehashedpagetableentry.Ifmanypagesmaptothesameentry,thentraversingthelistcorrespondingtothathashtableentrycouldincurasignificantoverhead;suchoverheadsareminimalinthesegmentedpagingschemewhereeachpagetableentrymaintainsinformationregardingonlyonepage.8.16ConsidertheInteladdresstranslationschemeshowninFigure8.22.a.DescribeallthestepsthattheIntel80386takesintranslatingalogicaladdressintoaphysicaladdress.b.Whataretheadvantagestotheoperatingsystemofhardwarethatprovidessuchcomplicatedmemorytranslationhardware?c.Arethereanydisadvantagestothisaddress-translationsystem?Ifso,whatarethey?Ifnot,whyisitnotusedbyeverymanufacturer?Answer:a.Theselectorisanindexintothesegmentdescriptortable.Thesegmentdescriptorresultplustheoriginaloffsetisusedtoproducealinearaddresswithadir,page,andoffset.Thedirisanindexintoapagedirectory.Theentryfromthepagedirectoryselectsthepagetable,andthepagefieldisanindexintothepagetable.Theentryfromthepagetable,plustheoffset,isthephysicaladdress.b.Suchapagetranslationmechanismofferstheflexibilitytoallowmostoperatingsystemstoimplementtheirmemoryschemeinhardware,insteadofhavingtoimplement 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3somepartsinhardwareandsomeinsoftware.Becauseitcanbedoneinhardware,itismoreefficient(andthekernelissimpler).c.Addresstranslationcantakelongerduetothemultipletablelookupsitcaninvoke.Cacheshelp,buttherewillstillbecachemisses.Chapter9 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.39.1Giveanexamplethatillustratestheproblemwithrestartingtheblockmoveinstruction(MVC)ontheIBM360/370whenthesourceanddestinationregionsareoverlapping.Answer:Assumethatthepageboundaryisat1024andthemoveinstructionismovingvaluesfromasourceregionof800:1200toatargetregionof700:1100.Assumethatapagefaultoccurswhileaccessinglocation1024.Bythistimethelocationsof800:923havebeenoverwrittenwiththenewvaluesandthereforerestartingtheblockmoveinstructionwouldresultincopyingthenewvaluesin800:923tolocations700:823,whichisincorrect.9.2Discussthehardwaresupportrequiredtosupportdemandpaging.Answer:Foreverymemoryaccessoperation,thepagetableneedstobeconsultedtocheckwhetherthecorrespondingpageisresidentornotandwhethertheprogramhasreadorwriteprivilegesforaccessingthepage.Thesecheckswouldhavetobeperformedinhardware.ATLBcouldserveasacacheandimprovetheperformanceofthelookupoperation.9.3Whatisthecopy-on-writefeatureandunderwhatcircumstancesisitbeneficialtousethisfeature?Whatisthehardwaresupportrequiredtoimplementthisfeature?Answer:Whentwoprocessesareaccessingthesamesetofprogramvalues(forinstance,thecodesegmentofthesourcebinary),thenitisusefultomapthecorrespondingpagesintothevirtualaddressspacesofthetwoprogramsinawrite-protectedmanner.Whenawritedoesindeedtakeplace,thenacopymustbemadetoallowthetwoprogramstoindividuallyaccessthedifferentcopieswithoutinterferingwitheachother.Thehardwaresupportrequiredtoimplementissimplythefollowing:oneachmemoryaccess,thepagetableneedstobeconsultedtocheckwhetherthepageiswrite-protected.Ifitisindeedwrite-protected,atrapwouldoccurandtheoperatingsystemcouldresolvetheissue.9.4Acertaincomputerprovidesitsuserswithavirtual-memoryspaceof232bytes.Thecomputerhas218bytesofphysicalmemory.Thevirtualmemoryisimplementedbypaging,andthepagesizeis4096bytes.Auserprocessgeneratesthevirtualaddress11123456.Explainhowthesystemestablishesthecorrespondingphysicallocation.Distinguishbetweensoftwareandhardwareoperations.Answer:Thevirtualaddressinbinaryformis00010001000100100011010001010110Sincethepagesizeis212,thepagetablesizeis220.Thereforethelow-order12bits“010001010110”areusedasthedisplacementintothepage,whiletheremaining20bits“00010001000100100011”areusedasthedisplacementinthepagetable. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.39.5Assumewehaveademand-pagedmemory.Thepagetableisheldinregisters.Ittakes8millisecondstoserviceapagefaultifanemptypageisavailableorthereplacedpageisnotmodified,and20millisecondsifthereplacedpageismodified.Memoryaccesstimeis100nanoseconds.Assumethatthepagetobereplacedismodified70percentofthetime.Whatisthemaximumacceptablepage-faultrateforaneffectiveaccesstimeofnomorethan200nanoseconds?Answer:0.2μsec＝(1－P)×0.1μsec+(0.3P)×8millisec+(0.7P)×20millisec0.1P＝－0.1P+2400P＋14000PP≈0.0000069.6Assumethatyouaremonitoringtherateatwhichthepointerintheclockalgorithm(whichindicatesthecandidatepageforreplacement)moves.Whatcanyousayaboutthesystemifyounoticethefollowingbehavior:a.pointerismovingfastb.pointerismovingslowAnswer:Ifthepointerismovingfast,thentheprogramisaccessingalargenumberofpagessimultaneously.Itismostlikelythatduringtheperiodbetweenthepointatwhichthebitcorrespondingtoapageisclearedanditischeckedagain,thepageisaccessedagainandthereforecannotbereplaced.Thisresultsinmorescanningofthepagesbeforeavictimpageisfound.Ifthepointerismovingslow,thenthevirtualmemorysystemisfindingcandidatepagesforreplacementextremelyefficiently,indicatingthatmanyoftheresidentpagesarenotbeingaccessed.9.7Discusssituationsunderwhichtheleastfrequentlyusedpage-replacementalgorithmgeneratesfewerpagefaultsthantheleastrecentlyusedpage-replacementalgorithm.Alsodiscussunderwhatcircumstancedoestheoppositeholds.Answer:Considerthefollowingsequenceofmemoryaccessesinasystemthatcanholdfourpagesinmemory.Sequence:1123451.Whenpage5isaccessed,theleastfrequentlyusedpage-replacementalgorithmwouldreplaceapageotherthan1,andthereforewouldnotincurapagefaultwhenpage1isaccessedagain.Ontheotherhand,forthesequence“123452,”theleastrecentlyusedalgorithmperformsbetter.9.8Discusssituationsunderwhichthemostfrequentlyusedpage-replacementalgorithmgeneratesfewerpagefaultsthantheleastrecentlyusedpage-replacementalgorithm.Alsodiscussunderwhatcircumstancedoestheoppositeholds.Answer:Considerthesequenceinasystemthatholdsfourpagesinmemory:12344451.Themostfrequentlyusedpagereplacementalgorithmevictspage4whilefetchingpage5,whiletheLRUalgorithmevictspage1.Thisisunlikelytohappenmuchinpractice.Forthesequence“12344451,”theLRUalgorithmmakesthe 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3rightdecision.9.9TheVAX/VMSsystemusesaFIFOreplacementalgorithmforresidentpagesandafree-framepoolofrecentlyusedpages.Assumethatthefree-framepoolismanagedusingtheleastrecentlyusedreplacementpolicy.Answerthefollowingquestions:a.Ifapagefaultoccursandifthepagedoesnotexistinthefree-framepool,howisfreespacegeneratedforthenewlyrequestedpage?b.Ifapagefaultoccursandifthepageexistsinthefree-framepool,howistheresidentpagesetandthefree-framepoolmanagedtomakespacefortherequestedpage?c.Whatdoesthesystemdegeneratetoifthenumberofresidentpagesissettoone?d.Whatdoesthesystemdegeneratetoifthenumberofpagesinthefree-framepooliszero?Answer:�Whenapagefaultoccursandifthepagedoesnotexistinthefree-framepool,thenoneofthepagesinthefree-framepoolisevictedtodisk,creatingspaceforoneoftheresidentpagestobemovedtothefree-framepool.Theaccessedpageisthenmovedtotheresidentset.�Whenapagefaultoccursandifthepageexistsinthefree-framepool,thenitismovedintothesetofresidentpages,whileoneoftheresidentpagesismovedtothefree-framepool.�Whenthenumberofresidentpagesissettoone,thenthesystemdegeneratesintothepagereplacementalgorithmusedinthefree-framepool,whichistypicallymanagedinaLRUfashion.�Whenthenumberofpagesinthefree-framepooliszero,thenthesystemdegeneratesintoaFIFOpagereplacementalgorithm.9.10Considerademand-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.Answer:Thesystemobviouslyisspendingmostofitstimepaging,indicatingover-allocationofmemory.IfthelevelofmultiprogrammingisreducedresidentprocesseswouldpagefaultlessfrequentlyandtheCPUutilizationwouldimprove.Anotherwaytoimproveperformancewouldbetogetmorephysicalmemoryorafaster 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3pagingdrum.a.GetafasterCPU—No.b.Getabiggerpagingdrum—No.c.Increasethedegreeofmultiprogramming—No.d.Decreasethedegreeofmultiprogramming—Yes.e.Installmoremainmemory—LikelytoimproveCPUutilizationasmorepagescanremainresidentandnotrequirepagingtoorfromthedisks.f.Installafasterharddisk,ormultiplecontrollerswithmultipleharddisks—Alsoanimprovement,forasthediskbottleneckisremovedbyfasterresponseandmorethroughputtothedisks,theCPUwillgetmoredatamorequickly.g.Addprepagingtothepagefetchalgorithms—Again,theCPUwillgetmoredatafaster,soitwillbemoreinuse.Thisisonlythecaseifthepagingactionisamenabletoprefetching(i.e.,someoftheaccessissequential).h.Increasethepagesize—Increasingthepagesizewillresultinfewerpagefaultsifdataisbeingaccessedsequentially.Ifdataaccessismoreorlessrandom,morepagingactioncouldensuebecausefewerpagescanbekeptinmemoryandmoredataistransferredperpagefault.Sothischangeisaslikelytodecreaseutilizationasitistoincreaseit.9.11Supposethatamachineprovidesinstructionsthatcanaccessmemorylocationsusingtheone-levelindirectaddressingscheme.Whatisthesequenceofpagefaultsincurredwhenallofthepagesofaprogramarecurrentlynon-residentandthefirstinstructionoftheprogramisanindirectmemoryloadoperation?Whathappenswhentheoperatingsystemisusingaper-processframeallocationtechniqueandonlytwopagesareallocatedtothisprocess?Answer:Thefollowingpagefaultstakeplace:pagefaulttoaccesstheinstruction,apagefaulttoaccessthememorylocationthatcontainsapointertothetargetmemorylocation,andapagefaultwhenthetargetmemorylocationisaccessed.Theoperatingsystemwillgeneratethreepagefaultswiththethirdpagereplacingthepagecontainingtheinstruction.Iftheinstructionneedstobefetchedagaintorepeatthetrappedinstruction,thenthesequenceofpagefaultswillcontinueindefinitely.Iftheinstructioniscachedinaregister,thenitwillbeabletoexecutecompletelyafterthethirdpagefault.9.12Supposethatyourreplacementpolicy(inapagedsystem)istoexamineeachpageregularlyandtodiscardingthatpageifithasnotbeenusedsincethelastexamination.WhatwouldyougainandwhatwouldyoulosebyusingthispolicyratherthanLRUorsecond-chancereplacement?Answer:Suchanalgorithmcouldbeimplementedwiththeuseofareferencebit.Aftereveryexamination,thebitissettozero;setbacktooneifthepageisreferenced.Thealgorithmwouldthenselectanarbitrarypageforreplacementfromthesetof 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3unusedpagessincethelastexamination.Theadvantageofthisalgorithmisitssimplicity-nothingotherthanareferencebitneedbemaintained.Thedisadvantageofthisalgorithmisthatitignoreslocalitybyonlyusingashorttimeframefordeterminingwhethertoevictapageornot.Forexample,apagemaybepartoftheworkingsetofaprocess,butmaybeevictedbecauseitwasnotreferencedsincethelastexamination(i.e.notallpagesintheworkingsetmaybereferencedbetweenexaminations.)9.13Apage-replacementalgorithmshouldminimizethenumberofpagefaults.Wecandothisminimizationbydistributingheavilyusedpagesevenlyoverallofmemory,ratherthanhavingthemcompeteforasmallnumberofpageframes.Wecanassociatewitheachpageframeacounterofthenumberofpagesthatareassociatedwiththatframe.Then,toreplaceapage,wesearchforthepageframewiththesmallestcounter.《页替换算法应尽量减少页错误。我们可以做到这一点通过尽量减少大量使用分布均匀页上的所有存储，而不是让他们竞争少数页面帧。我们可以联系每个页内柜台的数量，页相关的框架。然后，以取代一个页，我们寻求的最小的数量的页帧。》a.Defineapage-replacementalgorithmusingthisbasicidea.Specificallyaddresstheproblemsof(1)whattheinitialvalueofthecountersis,(2)whencountersareincreased,(3)whencountersaredecreased,and(4)howthepagetobereplacedisselected.《定义一个页面替换算法利用这一基本思想。具体处理的问题（1）计数器的初始值是什么，（2）当计数器增加，（3）当计数器减少，（4）如何选中被取代的页。》b.Howmanypagefaultsoccurforyouralgorithmforthefollowingreferencestring,forfourpageframes?1,2,3,4,5,3,4,1,6,7,8,7,8,9,7,8,9,5,4,5,4,2.c.Whatistheminimumnumberofpagefaultsforanoptimalpage-replacementstrategyforthereferencestringinpartbwithfourpageframes?Answer:a.Defineapage-replacementalgorithmaddressingtheproblemsof:(1)Initialvalueofthecounters—0.(2)Countersareincreased—wheneveranewpageisassociatedwiththatframe.(3)Countersaredecreased—wheneveroneofthepagesassociatedwiththatframeisnolongerrequired.(4)Howthepagetobereplacedisselected—findaframewiththesmallestcounter.UseFIFOforbreakingties.b.14pagefaultsc.11pagefaults9.14Considerademand-pagingsystemwithapagingdiskthathasanaverageaccessandtransfertimeof20milliseconds.Addressesaretranslatedthroughapagetableinmainmemory,withanaccesstimeof1microsecondpermemoryaccess.Thus,each 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3memoryreferencethroughthepagetabletakestwoaccesses.Toimprovethistime,wehaveaddedanassociativememorythatreducesaccesstimetoonememoryreference,ifthepage-tableentryisintheassociativememory.Assumethat80percentoftheaccessesareintheassociativememoryandthat,oftheremaining,10percent(or2percentofthetotal)causepagefaults.Whatistheeffectivememoryaccesstime?Answer:effectiveaccesstime=0.8×1μsec+0.1×2μsec+0.1×5002μsec=501.2sec=0.5millisec9.15Whatisthecauseofthrashing?Howdoesthesystemdetectthrashing?Onceitdetectsthrashing,whatcanthesystemdotoeliminatethisproblem?《系统抖动的原因是什么？系统如何检测系统抖动？一旦侦测到系统抖动，怎么做的系统，以消除这个问题？》Answer:Thrashingiscausedbyunderallocationoftheminimumnumberofpagesrequiredbyaprocess,forcingittocontinuouslypagefault.ThesystemcandetectthrashingbyevaluatingthelevelofCPUutilizationascomparedtothelevelofmultiprogramming.Itcanbeeliminatedbyreducingthelevelofmultiprogramming.9.16Isitpossibleforaprocesstohavetwoworkingsets?Onerepresentingdataandanotherrepresentingcode?Explain.Answer:Yes,infactmanyprocessorsprovidetwoTLB’sforthisveryreason.Asanexample,thecodebeingaccessedbyaprocessmayretainthesameworkingsetforalongperiodoftime.However,thedatathecodeaccessesmaychange,thusreflectingachangeintheworkingsetfordataaccesses.9.17Considertheparameterusedtodefinetheworking-setwindowintheworking-setmodel.Whatistheeffectofsettingtoasmallvalueonthepagefaultfrequencyandthenumberofactive(non-suspended)processescurrentlyexecutinginthesystem?Whatistheeffectwhenissettoaveryhighvalue?Answer:Whenissettoasmallvalue,thenthesetofresidentpagesforaprocessmightbeunderestimatedallowingaprocesstobescheduledeventhoughallofitsrequiredpagesarenotresident.Thiscouldresultinalargenumberofpagefaults.Whenissettoalargevalue,thenaprocess’sresidentsetisoverestimatedandthismightpreventmanyprocessesfrombeingscheduledeventhoughtheirrequiredpagesareresident.However,onceaprocessisscheduled,itisunlikelytogeneratepagefaultssinceitsresidentsethasbeenoverestimated.9.18Assumethereisaninitial1024KBsegmentwherememoryisallocatedusingtheBuddySystem.UsingFigure9.27asaguide,drawthetreeillustratinghowthe 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3followingmemoryrequestsareallocated:�request240bytes�request120bytes�request60bytes�request130bytesNext,modifythetreeforthefollowingreleasesofmemory.Performcoalescingwheneverpossible:�release240bytes�release60bytes�release120bytesAnswer:ThefollowingallocationismadebytheBuddysystem:The240byterequestisassigneda256bytesegment.The120byterequestisassigneda128bytesegement,the60byterequestisassigneda64bytesegmentandthe130byterequestisassigneda256bytesegment.Aftertheallocation,thefollowingsegmentsizesareavailable:64bytes,256bytes,1K,2K,4K,8K,16K,32K,64K,128K,256K,and512K.Afterthereleasesofmemory,theonlysegmentinusewouldbea256bytesegmentcontaining130bytesofdata.Thefollowingsegmentswillbefree:256bytes,512bytes,1K,2K,4K,8K,16K,32K,64K,128K,256K,and512K.9.19Theslaballocationalgorithmusesaseparatecacheforeachdifferentobjecttype.Assumingthereisonecacheperobjecttype,explainwhythisdoesn’tscalewellwithmultipleCPUs.Whatcouldbedonetoaddressthisscalabilityissue?Answer:Thishadlongbeenaproblemwiththeslaballocator-poorscalabilitywithmultipleCPUs.Theissuecomesfromhavingtolocktheglobalcachewhenitisbeingaccesses.Thishastheeffectofserializingcacheaccessesonmultiprocessorsystems.Solarishasaddressedthisbyintroducingaper-CPUcache,ratherthanasingleglobalcache.9.20Considerasystemthatallocatespagesofdifferentsizestoitsprocesses.Whataretheadvantagesofsuchapagingscheme?Whatmodificationstothevirtualmemorysystemareprovidethisfunctionality?Answer:Theprogramcouldhavealargecodesegmentoruselargesizedarraysasdata.Theseportionsoftheprogramcouldbeallocatedtolargerpages,therebydecreasingthememoryoverheadsassociatedwithapagetable.Thevirtualmemorysystemwouldthenhavetomaintainmultiplefreelistsofpagesforthedifferentsizesandshouldalsoneedtohavemorecomplexcodeforaddresstranslationtotakeintoaccountdifferentpagesizes.9.21WriteaprogramthatimplementstheFIFOandLRUpage-replacementalgorithmspresentedinthischapter.First,generatearandompage-referencestringwherepagenumbersrangefrom0..9.Applytherandompage-referencestringtoeachalgorithm 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3andrecordthenumberofpagefaultsincurredbyeachalgorithm.Implementthereplacementalgorithmssuchthatthenumberofpageframescanvaryfrom1..7.Assumethatdemandpagingisused.Answer:Pleaserefertotheexperimentmanualforsourcecodesolution.9.22TheCatalannumbersareanintegersequenceCnthatappearintreeenumerationproblems.ThefirstCatalannumbersforn=1,2,3,...are1,2,5,14,42,132,....AformulageneratingCnis⎛1⎞⎛2n⎞(2n)!Cn=⎜⎟⎜⎟=⎝n+1⎠⎝n⎠(n+1)n!DesigntwoprogramsthatcommunicatewithsharedmemoryusingtheWin32APIasoutlinedinSection9.7.2.TheproducerprocesswillgeneratetheCatalansequenceandwriteittoasharedmemoryobject.Theconsumerprocesswillthenreadandoutputthesequencefromsharedmemory.Inthisinstance,theproducerprocesswillbepassedanintegerparameteronthecommandlinespecifyingthenumberofCatalannumberstoproduce,i.e.providing5onthecommandlinemeanstheproducerprocesswillgeneratethefirst5Catalannumbers.Answer:(Ihavenotcompletedituptonow.Maybesomedayitwillbereleased.) 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Chapter1010.1Considerafilesystemwhereafilecanbedeletedanditsdiskspacereclaimedwhilelinkstothatfilestillexist.Whatproblemsmayoccurifanewfileiscreatedinthesamestorageareaorwiththesameabsolutepathname?Howcantheseproblemsbeavoided?Answer:LetF1betheoldfileandF2bethenewfile.AuserwishingtoaccessF1throughanexistinglinkwillactuallyaccessF2.NotethattheaccessprotectionforfileF1isusedratherthantheoneassociatedwithF2.Thisproblemcanbeavoidedbyinsuringthatalllinkstoadeletedfilearedeletedalso.Thiscanbeaccomplishedinseveralways:a.maintainalistofalllinkstoafile,removingeachofthemwhenthefileisdeletedb.retainthelinks,removingthemwhenanattemptismadetoaccessadeletedfilec.maintainafilereferencelist(orcounter),deletingthefileonlyafteralllinksorreferencestothatfilehavebeendeleted.10.2Theopen-filetableisusedtomaintaininformationaboutfilesthatarecurrentlyopen.Shouldtheoperatingsystemmaintainaseparatetableforeachuserorjustmaintainonetablethatcontainsreferencestofilesthatarebeingaccessedbyallusersatthecurrenttime?Ifthesamefileisbeingaccessedbytwodifferentprogramsorusers,shouldtherebeseparateentriesintheopenfiletable?Answer:Bykeepingacentralopen-filetable,theoperatingsystemcanperformthefollowingoperationthatwouldbeinfeasibleother-wise.Considerafilethatiscurrentlybeingaccessedbyoneormoreprocesses.Ifthefileisdeleted,thenitshouldnotberemovedfromthediskuntilallprocessesaccessingthefilehaveclosedit.Thischeckcouldbeperformedonlyifthereiscentralizedaccountingofnumberofprocessesaccessingthefile.Ontheotherhand,iftwoprocessesareaccessingthefile,thenseparatestateneedstobemaintainedtokeeptrackofthecurrentlocationofwhichpartsofthefilearebeingaccessedbythetwoprocesses.Thisrequirestheoperatingsystemtomaintainseparateentriesforthetwoprocesses.10.3Whataretheadvantagesanddisadvantagesofasystemprovidingmandatorylocksinsteadofprovidingadvisorylockswhoseusageislefttotheusers’discretion?Answer:Inmanycases,separateprogramsmightbewillingtotolerateconcurrentaccesstoafilewithoutrequiringtheneedtoobtainlocksandtherebyguaranteeingmutualexclusiontothefiles.Mutualexclusioncouldbeguaranteedbyotherprogram 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3structuressuchasmemorylocksorotherformsofsynchronization.Insuchsituations,themandatorylockswouldlimittheflexibilityinhowfilescouldbeaccessedandmightalsoincreasetheoverheadsassociatedwithaccessingfiles.10.4Whataretheadvantagesanddisadvantagesofrecordingthenameofthecreatingprogramwiththefile’sattributes(asisdoneintheMacintoshOperatingSystem)?Answer:Byrecordingthenameofthecreatingprogram,theoperatingsystemisabletoimplementfeatures(suchasautomaticprograminvocationwhenthefileisaccessed)basedonthisinformation.Itdoesaddoverheadintheoperatingsystemandrequirespaceinthefiledescriptor,however.10.5Somesystemsautomaticallyopenafilewhenitisreferencedforthefirsttime,andclosethefilewhenthejobterminates.Discusstheadvantagesanddisadvantagesofthisschemeascomparedtothemoretraditionalone,wheretheuserhastoopenandclosethefileexplicitly.Answer:Automaticopeningandclosingoffilesrelievestheuserfromtheinvocationofthesefunctions,andthusmakesitmoreconvenienttotheuser;however,itrequiresmoreoverheadthanthecasewhereexplicitopeningandclosingisrequired.10.6Iftheoperatingsystemweretoknowthatacertainapplicationisgoingtoaccessthefiledatainasequentialmanner,howcoulditexploitthisinformationtoimproveperformance?Answer:Whenablockisaccessed,thefilesystemcouldprefetchthesubsequentblocksinanticipationoffuturerequeststotheseblocks.Thisprefetchingoptimizationwouldreducethewaitingtimeexperiencedbytheprocessforfuturerequests.10.7Giveanexampleofanapplicationthatcouldbenefitfromoperatingsystemsupportforrandomaccesstoindexedfiles.Answer:Anapplicationthatmaintainsadatabaseofentriescouldbenefitfromsuchsupport.Forinstance,ifaprogramismaintainingastudentdatabase,thenaccessestothedatabasecannotbemodeledbyanypredeterminedaccesspattern.Theaccesstorecordsarerandomandlocatingtherecordswouldbemoreefficientiftheoperatingsystemweretoprovidesomeformoftree-basedindex.10.8Discussthemeritsanddemeritsofsupportinglinkstofilesthatcrossmountpoints(thatis,thefilelinkreferstoafilethatisstoredinadifferentvolume).Answer:Theadvantageisthatthereisgreatertransparencyinthesensethattheuserdoesnotneedtobeawareofmountpointsandcreatelinksinallscenarios.Thedisadvantagehoweveristhatthefilesystemcontainingthelinkmightbemounted 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3whilethefilesystemcontainingthetargetfilemightnotbe,andthereforeonecannotprovidetransparentaccesstothefileinsuchascenario;theerrorconditionwouldexposetotheuserthatalinkisadeadlinkandthatthelinkdoesindeedcrossfilesystemboundaries.10.9Somesystemsprovidefilesharingbymaintainingasinglecopyofafile;othersystemsmaintainseveralcopies,oneforeachoftheuserssharingthefile.Discusstherelativemeritsofeachapproach.Answer:Withasinglecopy,severalconcurrentupdatestoafilemayresultinuserobtainingincorrectinformation,andthefilebeingleftinanincorrectstate.Withmultiplecopies,thereisstoragewasteandthevariouscopiesmaynotbeconsistentwithrespecttoeachother.10.10Discusstheadvantagesanddisadvantagesofassociatingwithremotefilesystems(storedonfileservers)adifferentsetoffailuresemanticsfromthatassociatedwithlocalfilesystems.Answer:Theadvantageisthattheapplicationcandealwiththefailureconditioninamoreintelligentmannerifitrealizesthatitincurredanerrorwhileaccessingafilestoredinaremotefilesystem.Forinstance,afileopenoperationcouldsimplyfailinsteadofhangingwhenaccessingaremotefileonafailedserverandtheapplicationcoulddealwiththefailureinthebestpossiblemanner;iftheoperationweretosimplyhang,thentheentireapplicationhangswhichisnotdesirable.Thedisadvantagehoweveristhelackofuniformityinfailuresemanticsandtheresultingcomplexityinapplicationcode.10.11WhataretheimplicationsofsupportingUNIXconsistencysemanticsforsharedaccessforthosefilesthatarestoredonremotefilesystems.Answer:UNIXconsistencysemanticsrequiresupdatestoafiletobeimmediatelyavailabletootherprocesses.Supportingsuchasemanticsforsharedfilesonremotefilesystemscouldresultinthefollowinginefficiencies:allupdatesbyaclienthavetobeimmediatelyreportedtothefileserverinsteadofbeingbatched(orevenignorediftheupdatesaretoatemporaryfile),andupdateshavetobecommunicatedbythefileservertoclientscachingthedataimmediatelyagainresultinginmorecommunication. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Chapter1111.1Considerafilesystemthatusesamodifedcontiguous-allocationschemewithsupportforextents.Afileisacollectionofextents,witheachextentcorrespondingtoacontiguoussetofblocks.Akeyissueinsuchsystemsisthedegreeofvariabilityinthesizeoftheextents.Whataretheadvantagesanddisadvantagesofthefollowingschemes:a.Allextentsareofthesamesize,andthesizeispredetermined.b.Extentscanbeofanysizeandareallocateddynamically.c.Extentscanbeofafewfixedsizes,andthesesizesarepredetermined.Answer:Ifallextentsareofthesamesize,andthesizeispredetermined,thenitsimplifiestheblockallocationscheme.Asimplebitmaporfreelistforextentswouldsuffice.Iftheextentscanbeofanysizeandareallocateddynamically,thenmorecomplexallocationschemesarerequired.Itmightbedifficulttofindanextentoftheappropriatesizeandtheremightbeexternalfragmentation.OnecouldusetheBuddysystemallocatordiscussedinthepreviouschapterstodesignanappropriateallocator.Whentheextentscanbeofafewfixedsizes,andthesesizesarepredetermined,onewouldhavetomaintainaseparatebitmaporfreelistforeachpossiblesize.Thisschemeisofintermediatecomplexityandofintermediateflexibilityincomparisontotheearlierschemes.11.2WhataretheadvantagesofthevariationoflinkedallocationthatusesaFATtochaintogethertheblocksofafile?Answer:Theadvantageisthatwhileaccessingablockthatisstoredatthemiddleofafile,itslocationcanbedeterminedbychasingthepointersstoredintheFATasopposedtoaccessingalloftheindividualblocksofthefileinasequentialmannertofindthepointertothetargetblock.Typically,mostoftheFATcanbecachedinmemoryandthereforethepointerscanbedeterminedwithjustmemoryaccessesinsteadofhavingtoaccessthediskblocks.11.3Considerasystemwherefreespaceiskeptinafree-spacelist.a.Supposethatthepointertothefree-spacelistislost.Canthesystemreconstructthefree-spacelist?Explainyouranswer.b.ConsiderafilesystemsimilartotheoneusedbyUNIXwithindexedallocation.HowmanydiskI/Ooperationsmightberequiredtoreadthecontentsofasmalllocalfileat/a/b/c?Assumethatnoneofthediskblocksiscurrentlybeingcached.c.Suggestaschemetoensurethatthepointerisneverlostasaresultofmemoryfailure. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Answer:a.Inordertoreconstructthefreelist,itwouldbenecessarytoperform“garbagecollection.”Thiswouldentailsearchingtheentiredirectorystructuretodeterminewhichpagesarealreadyallocatedtojobs.Thoseremainingunallocatedpagescouldberelinkedasthefree-spacelist.b.Thefree-spacelistpointercouldbestoredonthedisk,perhapsinseveralplaces.c.11.4Somefilesystemsallowdiskstoragetobeallocatedatdifferentlevelsofgranularity.Forinstance,afilesystemcouldallocate4KBofdiskspaceasasingle4-KBblockoraseight512-byteblocks.Howcouldwetakeadvantageofthisflexibilitytoimproveperformance?Whatmodificationswouldhavetobemadetothefree-spacemanagementschemeinordertosupportthisfeature?Answer:Suchaschemewoulddecreaseinternalfragmentation.Ifafileis5KB,thenitcouldbeallocateda4KBblockandtwocontiguous512-byteblocks.Inadditiontomaintainingabitmapoffreeblocks,onewouldalsohavetomaintainextrastateregardingwhichofthesubblocksarecurrentlybeingusedinsideablock.Theallocatorwouldthenhavetoexaminethisextrastatetoallocatesubblocksandcoallescethesubblockstoobtainthelargerblockwhenallofthesubblocksbecomefree.11.5Discusshowperformanceoptimizationsforfilesystemsmightresultindifficultiesinmaintainingtheconsistencyofthesystemsintheeventofcomputercrashes.Answer:Theprimarydifficultythatmightariseisduetodelayedupdatesofdataandmetadata.Updatescouldbedelayedinthehopethatthesamedatamightbeupdatedinthefutureorthattheupdateddatamightbetemporaryandmightbedeletedinthenearfuture.However,ifthesystemweretocrashwithouthavingcommittedthedelayedupdates,thentheconsistencyofthefilesystemisdestroyed.11.6Considerafilesystemonadiskthathasbothlogicalandphysicalblocksizesof512bytes.Assumethattheinformationabouteachfileisalreadyinmemory.Foreachofthethreeallocationstrategies(contiguous,linked,andindexed),answerthesequestions:a.Howisthelogical-to-physicaladdressmappingaccomplishedinthissystem?(Fortheindexedallocation,assumethatafileisalwayslessthan512blockslong.)b.Ifwearecurrentlyatlogicalblock10(thelastblockaccessedwasblock10)andwanttoaccesslogicalblock4,howmanyphysicalblocksmustbereadfromthedisk?Answer:LetZbethestartingfileaddress(blocknumber). 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3a.Contiguous.Dividethelogicaladdressby512withXandYtheresultingquotientandremainderrespectively.(1)AddXtoZtoobtainthephysicalblocknumber.Yisthedisplacementintothatblock.(2)1b.Linked.Dividethelogicalphysicaladdressby511withXandYtheresultingquotientandremainderrespectively.(1)Chasedownthelinkedlist(gettingX+1blocks).Y+1isthedisplacementintothelastphysicalblock.(2)4c.Indexed.Dividethelogicaladdressby512withXandYtheresultingquotientandremainderrespectively.(1)Gettheindexblockintomemory.PhysicalblockaddressiscontainedintheindexblockatlocationX.Yisthedisplacementintothedesiredphysicalblock.(2)211.7Fragmentationonastoragedevicecouldbeeliminatedbyrecompactionoftheinformation.Typicaldiskdevicesdonothaverelocationorbaseregisters(suchasareusedwhenmemoryistobecompacted),sohowcanwerelocatefiles?Givethreereasonswhyrecompactingandrelocationoffilesoftenareavoided.Answer:Relocationoffilesonsecondarystorageinvolvesconsiderableoverhead—datablockswouldhavetobereadintomainmemoryandwrittenbackouttotheirnewlocations.Furthermore,relocationregistersapplyonlytosequentialfiles,andmanydiskfilesarenotsequential.Forthissamereason,manynewfileswillnotrequirecontiguousdiskspace;evensequentialfilescanbeallocatednoncontiguousblocksiflinksbetweenlogicallysequentialblocksaremaintainedbythedisksystem.11.8InwhatsituationswouldusingmemoryasaRAMdiskbemoreusefulthanusingitasadiskcache?Answer:Incaseswheretheuser(orsystem)knowsexactlywhatdataisgoingtobeneeded.Cachesarealgorithm-based,whileaRAMdiskisuser-directed.11.9Considerthefollowingaugmentationofaremote-file-accessprotocol.Eachclientmaintainsanamecachethatcachestranslationsfromfilenamestocorrespondingfilehandles.Whatissuesshouldwetakeintoaccountinimplementingthenamecache?Answer:Oneissueismaintainingconsistencyofthenamecache.Ifthecacheentrybecomesinconsistent,thenitshouldbeeitherupdatedoritsinconsistencyshouldbedetectedwhenitisusednext.Iftheinconsistencyisdetectedlater,thenthereshouldbeafallbackmechanismfordeterminingthenewtranslationforthename. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Also,anotherrelatedissueiswhetheranamelookupisperformedoneelementatatimeforeachsubdirectoryinthepathnameorwhetheritisperformedinasingleshotattheserver.Ifitisperfomedoneelementatatime,thentheclientmightobtainmoreinformationregardingthetranslationsforalloftheintermediatedirectories.Ontheotherhand,itincreasesthenetworktrafficasasinglenamelookupcausesasequenceofpartialnamelookups.11.10Explainwhyloggingmetadataupdatesensuresrecoveryofafilesystemafterafilesystemcrash.Answer:Forafilesystemtoberecoverableafteracrash,itmustbeconsistentormustbeabletobemadeconsistent.Therefore,wehavetoprovethatloggingmetadataupdateskeepsthefilesysteminaconsistentorable-to-be-consistentstate.Forafilesystemtobecomeinconsistent,themetadatamustbewrittenincompletelyorinthewrongordertothefilesystemdatastructures.Withmetadatalogging,thewritesaremadetoasequentiallog.Thecompletetransactioniswrittentherebeforeitismovedtothefilesystemstructures.Ifthesystemcrashesduringfilesystemdataupdates,theupdatescanbecompletedbasedontheinformationinthelog.Thus,loggingensuresthatfilesystemchangesaremadecompletely(eitherbeforeorafteracrash).Theorderofthechangesareguaranteedtobecorrectbecauseofthesequentialwritestothelog.Ifachangewasmadeincompletelytothelog,itisdiscarded,withnochangesmadetothefilesystemstructures.Therefore,thestructuresareeitherconsistentorcanbetriviallymadeconsistentviametadataloggingreplay.11.11Considerthefollowingbackupscheme:�Day1.Copytoabackupmediumallfilesfromthedisk.�Day2.Copytoanothermediumallfileschangedsinceday1.�Day3.Copytoanothermediumallfileschangedsinceday1.ThiscontraststotheschedulegiveninSection11.7.2byhavingallsubsequentbackupscopyallfilesmodifiedsincethefirstfullbackup.WhatarethebenefitsofthissystemovertheoneinSection11.7.2?Whatarethedrawbacks?Arerestoreoperationsmadeeasierormoredifficult?Explainyouranswer.Answer:Restoresareeasierbecauseyoucangotothelastbackuptape,ratherthanthefulltape.Nointermediatetapesneedberead.Moretapeisusedasmorefileschange. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Chapter1212.1Noneofthedisk-schedulingdisciplines,exceptFCFS,istrulyfair(starvationmayoccur).a.Explainwhythisassertionistrue.b.DescribeawaytomodifyalgorithmssuchasSCANtoensurefairness.c.Explainwhyfairnessisanimportantgoalinatime-sharingsystem.d.GivethreeormoreexamplesofcircumstancesinwhichitisimportantthattheoperatingsystembeunfairinservingI/Orequests.Answer:a.Newrequestsforthetrackoverwhichtheheadcurrentlyresidescantheoreticallyarriveasquicklyastheserequestsarebeingserviced.b.Allrequestsolderthansomepredeterminedagecouldbe“forced”tothetopofthequeue,andanassociatedbitforeachcouldbesettoindicatethatnonewrequestcouldbemovedaheadoftheserequests.ForSSTF,therestofthequeuewouldhavetobereorganizedwithrespecttothelastofthese“old”requests.c.Topreventunusuallylongresponsetimes.d.Pagingandswappingshouldtakepriorityoveruserrequests.Itmaybedesirableforotherkernel-initiatedI/O,suchasthewritingoffilesystemmetadata,totakeprecedenceoveruserI/O.Ifthekernelsupportsreal-timeprocesspriorities,theI/Orequestsofthoseprocessesshouldbefavored.12.2Supposethatadiskdrivehas5000cylinders,numbered0to4999.Thedriveiscurrentlyservingarequestatcylinder143,andthepreviousrequestwasatcylinder125.Thequeueofpendingrequests,inFIFOorder,is86,1470,913,1774,948,1509,1022,1750,130Startingfromthecurrentheadposition,whatisthetotaldistance(incylinders)thatthediskarmmovestosatisfyallthependingrequests,foreachofthefollowingdisk-schedulingalgorithms?a.FCFSb.SSTFc.SCANd.LOOKe.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.Thetotalseekdistanceis3319. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3e.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.12.3Fromelementaryphysics,weknowthatwhenanobjectissubjectedtoaconstantaccelerationa,therelationshipbetweendistancedandtimetisgivenby12d=at.2Supposethat,duringaseek,thediskinExercise12.2acceleratesthediskarmataconstantrateforthefirsthalfoftheseek,thendeceleratesthediskarmatthesamerateforthesecondhalfoftheseek.Assumethatthediskcanperformaseektoanadjacentcylinderin1millisecondandafull-strokeseekoverall5000cylindersin18milliseconds.a.Thedistanceofaseekisthenumberofcylindersthattheheadmoves.Explainwhytheseektimeisproportionaltothesquarerootoftheseekdistance.b.Writeanequationfortheseektimeasafunctionofthes√eekdistance.Thisequationshouldbeoftheformt=x+yL,wheretisthetimeinmillisecondsandListheseekdistanceincylinders.c.CalculatethetotalseektimeforeachoftheschedulesinExercise12.2.Determinewhichscheduleisthefastest(hasthesmallesttotalseektime).d.Thepercentagespeedupisthetimesaveddividedbytheoriginaltime.WhatisthepercentagespeedupofthefastestscheduleoverFCFS?Answer:12a.Solvingd=atfortgivest=(2d/a).2b.Solvethesimultaneousequationst=x+yLthatresultfrom(t=1,L=1)and(t=18,L=4999)toobtaint=0.7561+0.2439Lc.Thetotalseektimesare:FCFS65.20;SSTF31.52;SCAN62.02;LOOK40.29;C-SCAN62.10;(andC-LOOK40.42).Thus,SSTFisfastesthere.d.(65.20-31.52)/65.20=0.52ThepercentagespeedupofSSTFoverFCFSis52%,withrespecttotheseektime.Ifweincludetheoverheadofrotationallatencyanddatatransfer,thepercentagespeedupwillbeless.12.4SupposethatthediskinExercise12.3rotatesat7200RPM.a.Whatistheaveragerotationallatencyofthisdiskdrive?b.Whatseekdistancecanbecoveredinthetimethatyoufoundforparta?Answer:a.7200rpmgives120rotationspersecond.Thus,afullrotationtakes8.33ms, 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3andtheaveragerotationallatency(ahalfrotation)takes4.167ms.b.Solvingt=0.7561+0.2439Lfort=4.167givesL=195.58,sowecanseekover195tracks(about4%ofthedisk)duringanaveragerotationallatency.12.5WriteaJavaprogramfordiskschedulingusingtheSCANandC-SCANdisk-schedulingalgorithms.Answer:(Ihavenotcompletedituptonow.Maybesomedayitwillbereleased.)12.6ComparetheperformanceofC-SCANandSCANscheduling,assumingauniformdistributionofrequests.Considertheaverageresponsetime(thetimebetweenthearrivalofarequestandthecompletionofthatrequest’sservice),thevariationinresponsetime,andtheeffectivebandwidth.Howdoesperformancedependontherelativesizesofseektimeandrotationallatency?Answer:Thereisnosimpleanalyticalargumenttoanswerthefirstpartofthisquestion.Itwouldmakeagoodsmallsimulationexperimentforthestudents.TheanswercanbefoundinFigure2ofWorthingtonetal.[1994].(Worthingtonetal.studiedtheLOOKalgorithm,butsimilarresultsobtainforSCAN.Figure2inWorthingtonetal.showsthatC-LOOKhasanaverageresponsetimejustafewpercenthigherthanLOOKbutthatC-LOOKhasasignificantlylowervarianceinresponsetimeformediumandheavyworkloads.TheintuitivereasonforthedifferenceinvarianceisthatLOOK(andSCAN)tendtofavorrequestsnearthemiddlecylinders,whereastheC-versionsdonothavethisimbalance.TheintuitivereasonfortheslowerresponsetimeofC-LOOKisthe“circular”seekfromoneendofthedisktothefarthestrequestattheotherend.Thisseeksatisfiesnorequests.Itonlycausesasmallperformancedegradationbecausethesquare-rootdependencyofseektimeondistanceimpliesthatalongseekisn’tterriblyexpensivebycomparisonwithmoderatelengthseeks.Forthesecondpartofthequestion,weobservethatthesealgorithmsdonotscheduletoimproverotationallatency;therefore,asseektimesdecreaserelativetorotationallatency,theperformancedifferencesbetweenthealgorithmswilldecrease.12.7Requestsarenotusuallyuniformlydistributed.Forexample,acylindercontainingthefilesystemFATorinodescanbeexpectedtobeaccessedmorefrequentlythanacylinderthatonlycontainsfiles.Supposeyouknowthat50percentoftherequestsareforasmall,fixednumberofcylinders.a.Wouldanyoftheschedulingalgorithmsdiscussedinthischapterbeparticularlygoodforthiscase?Explainyouranswer.b.Proposeadisk-schedulingalgorithmthatgivesevenbetterperformancebytakingadvantageofthis“hotspot”onthedisk.c.Filesystemstypicallyfinddatablocksviaanindirectiontable,suchasaFAT 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3inDOSorinodesinUNIX.Describeoneormorewaystotakeadvantageofthisindirectiontoimprovethediskperformance.Answer:a.SSTFwouldtakegreatestadvantageofthesituation.FCFScouldcauseunnecessaryheadmovementifreferencestothe“high-demand”cylinderswereinterspersedwithreferencestocylindersfaraway.b.Herearesomeideas.Placethehotdatanearthemiddleofthedisk.ModifySSTFtopreventstarvation.Addthepolicythatifthediskbecomesidleformorethan,say,50ms,theoperatingsystemgeneratesananticipatoryseektothehotregion,sincethenextrequestismorelikelytobethere.c.Cachethemetadatainprimarymemory,andlocateafile’sdataandmetadatainclosephysicalproximityonthedisk.(UNIXaccomplishesthelattergoalbyallocatingdataandmetadatainregionscalledcylindergroups.)12.8CouldaRAIDLevel1organizationachievebetterperformanceforreadrequeststhanaRAIDLevel0organization(withnonredundantstripingofdata)?Ifso,how?Answer:Yes,aRAIDLevel1organizationcouldachievebetterperformanceforreadrequests.Whenareadoperationisperformed,aRAIDLevel1systemcandecidewhichofthetwocopiesoftheblockshouldbeaccessedtosatisfytherequest.Thischoicecouldbebasedonthecurrentlocationofthediskheadandcouldthereforeresultinperformanceoptimizationsbychoosingadiskheadwhichisclosertothetargetdata.12.9ConsideraRAIDLevel5organizationcomprisingfivedisks,withtheparityforsetsoffourblocksonfourdisksstoredonthefifthdisk.Howmanyblocksareaccessedinordertoperformthefollowing?a.Awriteofoneblockofdatab.AwriteofsevencontinuousblocksofdataAnswer:a.Awriteofoneblockofdatarequiresthefollowing:readoftheparityblock,readoftheolddatastoredinthetargetblock,computationofthenewparitybasedonthedifferencesbetweenthenewandoldcontentsofthetargetblock,andthewriteoftheparityblockandthetargetblock.b.Assumethatthesevencontiguousblocksbeginatafour-blockboundary.Awriteofsevencontiguousblocksofdatacouldbeperformedbywritingthesevencontiguousblocks,writingtheparityblockofthefirstfourblocks,readingtheeightblock,computingtheparityforthenextsetoffourblocksandwritingthecorrespondingparityblockontodisk.12.10ComparethethroughputachievedbyaRAIDLevel5organizationwiththatachievedbyaRAIDLevel1organizationforthefollowing: 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3a.Readoperationsonsingleblocksb.ReadoperationsonmultiplecontiguousblocksAnswer:1)TheamountofthroughputdependsonthenumberofdisksintheRAIDsystem.ARAIDLevel5comprisingofaparityblockforeverysetoffourblocksspreadoverfivediskscansupportfourtofiveoperationssimultaneously.ARAIDLevel1comprisingoftwodiskscansupporttwosimultaneousoperations.Ofcourse,thereisgreaterflexibilityinRAIDLevel1astowhichcopyofablockcouldbeaccessedandthatcouldprovideperformancebenefitsbytakingintoaccountpositionofdiskhead.2)RAIDLevel5organizationachievesgreaterbandwidthforaccessestomultiplecontiguousblockssincetheadjacentblockscouldbesimultaneouslyaccessed.SuchbandwidthimprovementsarenotpossibleinRAIDLevel1.12.11ComparetheperformanceofwriteoperationsachievedbyaRAIDLevel5organizationwiththatachievedbyaRAIDLevel1organization.Answer:RAIDLevel1organizationcanperformwritesbysimplyissuingthewritestomirroreddataconcurrently.RAIDLevel5,ontheotherhand,wouldrequiretheoldcontentsoftheparityblocktobereadbeforeitisupdatedbasedonthenewcontentsofthetargetblock.ThisresultsinmoreoverheadforthewriteoperationsonaRAIDLevel5system.12.12AssumethatyouhaveamixedconfigurationcomprisingdisksorganizedasRAIDLevel1andasRAIDLevel5disks.Assumethatthesystemhasflexibilityindecidingwhichdiskorganizationtouseforstoringaparticularfile.WhichfilesshouldbestoredintheRAIDLevel1disksandwhichintheRAIDLevel5disksinordertooptimizeperformance?Answer:FrequentlyupdateddataneedtobestoredonRAIDLevel1diskswhiledatawhichismorefrequentlyreadasopposedtobeingwrittenshouldbestoredinRAIDLevel5disks.12.13Isthereanywaytoimplementtrulystablestorage?Explainyouranswer.Answer:Trulystablestoragewouldneverlosedata.Thefundamentaltechniqueforstablestorageistomaintainmultiplecopiesofthedata,sothatifonecopyisdestroyed,someothercopyisstillavailableforuse.Butforanyscheme,wecanimaginealargeenoughdisasterthatallcopiesaredestroyed.12.14Thereliabilityofahard-diskdriveistypicallydescribedintermsofaquantitycalledmeantimebetweenfailures(MTBF).Althoughthisquantityiscalleda“time,”theMTBFactuallyismeasuredindrive-hoursperfailure.a.Ifadiskfarmcontains1000drives,eachofwhichhasa750,000hourMTBF,whichofthefollowingbestdescribeshowoftenadrivefailurewilloccurinthatdisk 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3farm:onceperthousandyears,oncepercentury,onceperdecade,onceperyear,oncepermonth,onceperweek,onceperday,onceperhour,onceperminute,oroncepersecond?b.Mortalitystatisticsindicatethat,ontheaverage,aU.S.residenthasabout1chancein1000ofdyingbetweenages20and21years.DeducetheMTBFhoursfor20yearolds.Convertthisfigurefromhourstoyears.WhatdoesthisMTBFtellyouabouttheexpectedlifetimeofa20yearold?c.Themanufacturerclaimsa1-millionhourMTBFforacertainmodelofdiskdrive.Whatcanyousayaboutthenumberofyearsthatoneofthosedrivescanbeexpectedtolast?Answer:a.750,000drive-hoursperfailuredividedby1000drivesgives750hoursperfailure—about31daysoroncepermonth.b.Thehuman-hoursperfailureis8760(hoursinayear)dividedby0.001failure,givingavalueof8,760,000“hours”fortheMTBF.8760,000hoursequals1000years.Thistellsusnothingabouttheexpectedlifetimeofapersonofage20.c.TheMTBFtellsnothingabouttheexpectedlifetime.Harddiskdrivesaregenerallydesignedtohavealifetimeof5years.Ifsuchadrivetrulyhasamillion-hourMTBF,itisveryunlikelythatthedrivewillfailduringitsexpectedlifetime.12.15Discusstherelativeadvantagesanddisadvantagesofsectorsparingandsectorslipping.Answer:Sectorsparingcancauseanextratrackswitchandrotationallatency,causinganunluckyrequesttorequireanextra8msoftime.Sectorslippinghaslessimpactduringfuturereading,butatsectorremappingtimeitcanrequirethereadingandwritingofanentiretrack’sworthofdatatoslipthesectorspastthebadspot.12.16Discussthereasonswhytheoperatingsystemmightrequireaccurateinformationonhowblocksarestoredonadisk.Howcouldtheoperatingsystemimprovefilesystemperformancewiththisknowledge?Answer:Whileallocatingblocksforafile,theoperatingsystemcouldallocateblocksthataregeometricallyclosebyonthediskifithadmoreinformationregardingthephysicallocationoftheblocksonthedisk.Inparticular,itcouldallocateablockofdataandthenallocatethesecondblockofdatainthesamecylinderbutonadifferentsurfaceatarotationallyoptimalplacesothattheaccesstothenextblockcouldbemadewithminimalcost.12.17Theoperatingsystemgenerallytreatsremovabledisksassharedfilesystemsbutassignsatapedrivetoonlyoneapplicationatatime.Givethreereasonsthatcouldexplainthisdifferenceintreatmentofdisksandtapes.Describeadditionalfeaturesthatwouldberequiredoftheoperatingsystemto 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3supportsharedfile-systemaccesstoatapejukebox.Wouldtheapplicationssharingthetapejukeboxneedanyspecialproperties,orcouldtheyusethefilesasthoughthefilesweredisk-resident?Explainyouranswer.Answer:a.Diskshavefastrandom-accesstimes,sotheygivegoodperformanceforinterleavedaccessstreams.Bycontrast,tapeshavehighpositioningtimes.Consequently,iftwousersattempttoshareatapedriveforreading,thedrivewillspendmostofitstimeswitchingtapesandpositioningtothedesireddata,andrelativelylittletimeperformingdatatransfers.Thisperformanceproblemissimilartothethrashingofavirtualmemorysystemthathasinsufficientphysicalmemory.b.Tapecartridgesareremovable.Theownerofthedatamaywishtostorethecartridgeoff-site(farawayfromthecomputer)tokeepacopyofthedatasafefromafireatthelocationofthecomputer.c.Tapecartridgesareoftenusedtosendlargevolumesofdatafromaproducerofdatatotheconsumer.Suchatapecartridgeisreservedforthatparticulardatatransferandcannotbeusedforgeneral-purposesharedstoragespace.Tosupportsharedfile-systemaccesstoatapejukebox,theoperatingsystemwouldneedtoperformtheusualfile-systemduties,including�Manageafile-systemnamespaceoverthecollectionoftapes�Performspaceallocation�ScheduletheI/OoperationsTheapplicationsthataccessatape-residentfilesystemwouldneedtobetolerantoflengthydelays.Forimprovedperformance,itwouldbedesirablefortheapplicationstobeabletodisclosealargenumberofI/Ooperationssothatthetape-schedulingalgorithmscouldgenerateefficientschedules.12.18Whatwouldbetheeffectoncostandperformanceiftapestorageweretoachievethesamearealdensityasdiskstorage?(Arealdensityisthenumberofgigabitspersquareinch.)Answer:Toachievethesamearealdensityasamagneticdisk,thearealdensityofatapewouldneedtoimprovebytwoordersofmagnitude.Thiswouldcausetapestoragetobemuchcheaperthandiskstorage.Thestoragecapacityofatapewouldincreasetomorethan1terabyte,whichcouldenableasingletapetoreplaceajukeboxoftapesintoday’stechnology,furtherreducingthecost.Thearealdensityhasnodirectbearingonthedatatransferrate,butthehighercapacitypertapemightreducetheoverheadoftapeswitching.12.19Youcanusesimpleestimatestocomparethecostandperformanceofaterabytestoragesystemmadeentirelyfromdiskswithonethatincorporatestertiarystorage.Supposethatmagneticdiskseachhold10gigabytes,cost$1000,transfer5megabytespersecond,andhaveanaverageaccesslatencyof15milliseconds.Supposethatatapelibrarycosts$10pergigabyte,transfers10megabytespersecond,andhasan 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3averageaccesslatencyof20seconds.Computethetotalcost,themaximumtotaldatarate,andtheaveragewaitingtimeforapuredisksystem.Ifyoumakeanyassumptionsabouttheworkload,describeandjustifythem.Now,supposethat5percentofthedataarefrequentlyused,sotheymustresideondisk,buttheother95percentarearchivedinthetapelibrary.Furthersupposethat95percentoftherequestsarehandledbythedisksystemandtheother5percentarehandledbythelibrary.Whatarethetotalcost,themaximumtotaldatarate,andtheaveragewaitingtimeforthishierarchicalstoragesystem?Answer:Firstlet’sconsiderthepuredisksystem.Oneterabyteis1024GB.Tobecorrect,weneed103disksat10GBeach.Butsincethisquestionisaboutapproximations,wewillsimplifythearithmeticbyroundingoffthenumbers.Thepuredisksystemwillhave100drives.Thecostofthediskdriveswouldbe$100,000,plusabout20%forcables,powersupplies,andenclosures,i.e.,around$120,000.Theaggregatedataratewouldbe100×5MB/s,or500MB/s.Theaveragewaitingtimedependsontheworkload.Supposethattherequestsarefortransfersofsize8KB,andsupposethattherequestsarerandomlydistributedoverthediskdrives.Ifthesystemislightlyloaded,atypicalrequestwillarriveatanidledisk,sotheresponsetimewillbe15msaccesstimeplusabout2mstransfertime.Ifthesystemisheavilyloaded,thedelaywillincrease,roughlyinproportiontothequeuelength.Nowlet’sconsiderthehierarchicalstoragesystem.Thetotaldiskspacerequiredis5%of1TB,whichis50GB.Consequently,weneed5disks,sothecostofthediskstorageis$5,000(plus20%,i.e.,$6,000).Thecostofthe950GBtapelibraryis$9500.Thusthetotalstoragecostis$15,500.Themaximumtotaldataratedependsonthenumberofdrivesinthetapelibrary.Wesupposethereisonly1drive.Thentheaggregatedatarateis6×10MB/s,i.e.,60MB/s.Foralightlyloadedsystem,95%oftherequestswillbesatisfiedbythediskswithadelayofabout17ms.Theother5%oftherequestswillbesatisfiedbythetapelibrary,withadelayofslightlymorethan20seconds.Thustheaveragedelaywillbe(95×0.017+5×20)/100,orabout1second.Evenwithanemptyrequestqueueatthetapelibrary,thelatencyofthetapedriveisresponsibleforalmostallofthesystem’sresponselatency,because1/20thoftheworkloadissenttoadevicethathasa20secondlatency.Ifthesystemismoreheavilyloaded,theaveragedelaywillincreaseinproportiontothelengthofthequeueofrequestswaitingforservicefromthetapedrive.Thehierarchicalsystemismuchcheaper.Forthe95%oftherequeststhatareservedbythedisks,theperformanceisasgoodasapure-disksystem.Butthemaximumdatarateofthehierarchicalsystemismuchworsethanforthepure-disksystem,asistheaverageresponsetime.12.20Imaginethataholographicstoragedrivehasbeeninvented.Supposethataholographicdrivecosts$10,000andhasanaverageaccesstimeof40milliseconds.Supposethatitusesa$100cartridgethesizeofaCD.Thiscartridgeholds40,000images,andeachimageisasquareblack-and-whitepicturewithresolution6000× 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.36000pixels(eachpixelstores1bit).Supposethatthedrivecanreadorwrite1picturein1millisecond.Answerthefollowingquestions.a.Whatwouldbesomegoodusesforthisdevice?b.HowwouldthisdeviceaffecttheI/Operformanceofacomputingsystem?c.Whichotherkindsofstoragedevices,ifany,wouldbecomeobsoleteasaresultofthisdevicebeinginvented?Answer:First,calculateperformanceofthedevice.6000×6000bitspermillisecond=4394KBpermillisecond=4291MB/sec(!).Clearlythisisordersofmagnitudegreaterthancurrentharddisktechnology,asthebestproductionharddrivesdolessthan40MB/sec.Thefollowinganswersassumethatthedevicecannotstoredatainsmallerchunksthan4MB.a.Thisdevicewouldfindgreatdemandinthestorageofimages,audiofiles,andotherdigitalmedia.b.Assumingthatinterconnectionspeedtothisdevicewouldequalitsthroughputability(thatis,theothercomponentsofthesystemcouldkeepitfed),large-scaledigitalloadandstoreperformancewouldbegreatyenchanced.Manipulationtimeofthedigitalobjectwouldstaythesameofcourse.Theresultwouldbegreatlyenhancedoverallperformance.c.Currently,objectsofthatsizearestoredonopticalmedia,tapemedia,anddiskmedia.Presumably,demandforthosewoulddecreaseastheholographicstoragebecameavailable.Therearelikelytobeusesforallofthosemediaeveninthepresenceofholographicstorage,soitisunlikelythatanywouldbecomeobsolete.Harddiskswouldstillbeusedforrandomaccesstosmalleritems(suchasuserfiles).Tapeswouldstillbeusedforoff-site,archiving,anddisasterrecoveryuses,andopticaldisks(CDRWforinstance)foreasyinterchangewithothercomputers,andlowcostbulkstorage.Dependingonthesizeoftheholographicdevice,anditspowerrequirements,itwouldalsofinduseinreplacingsolidstatememoryfordigitalcameras,MP3players,andhand-heldcomputers.12.21Supposethataone-sided5.25-inchoptical-diskcartridgehasanarealdensityof1gigabitpersquareinch.Supposethatamagnetictapehasanarealdensityof20megabitspersquareinch,andis1/2inchwideand1800feetlong.Calculateanestimateofthestoragecapacitiesofthesetwokindsofstoragecartridges.Supposethatanopticaltapeexiststhathasthesamephysicalsizeasthetape,butthesamestoragedensityastheopticaldisk.Whatvolumeofdatacouldtheopticaltapehold?Whatwouldbeamarketablepricefortheopticaltapeifthemagnetictapecost$25?Answer:Theareaofa5.25inchdiskisabout19.625squareinches.Ifwesupposethatthediameterofthespindlehubis1.5inches,thehuboccupiesanareaofabout1.77squareinches,leaving17.86squareinchesfordatastorage.Therefore,weestimatethestoragecapacityoftheopticaldisktobe2.2gigabytes.Thesurfaceareaofthetapeis10,800squareinches,soitsstoragecapacityisabout26 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3gigabytes.Ifthe10,800squareinchesoftapehadastoragedensityof1gigabitpersquareinch,thecapacityofthetapewouldbeabout1,350gigabytes,or1.3terabytes.Ifwechargethesamepricepergigabytefortheopticaltapeasformagnetictape,theopticaltapecartridgewouldcostabout50timesmorethanthemagnetictape,i.e.,$1,250.12.22Discusshowanoperatingsystemcouldmaintainafree-spacelistforatape-residentfilesystem.Assumethatthetapetechnologyisappend-only,andthatitusestheEOTmarkandlocate,space,andreadpositioncommandsasdescribedinSection12.9.2.1.Answer:Sincethistapetechnologyisappend-only,allthefreespaceisattheendofthetape.Thelocationofthisfreespacedoesnotneedtobestoredatall,becausethespacecommandcanbeusedtopositiontotheEOTmark.TheamountofavailablefreespaceaftertheEOTmarkcanberepresentedbyasinglenumber.Itmaybedesirabletomaintainasecondnumbertorepresenttheamountofspaceoccupiedbyfilesthathavebeenlogicallydeleted(buttheirspacehasnotbeenreclaimedsincethetapeisappend-only)sothatwecandecidewhenitwouldpaytocopythenondeletedfilestoanewtapeinordertoreclaimtheoldtapeforreuse.Wecanstorethefreeanddeletedspacenumbersondiskforeasyaccess.Anothercopyofthesenumberscanbestoredattheendofthetapeasthelastdatablock.Wecanoverwritethislastdatablockwhenweallocatenewstorageonthetape. 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3Chapter1313.1Whenmultipleinterruptsfromdifferentdevicesappearataboutthesametime,apriorityschemecouldbeusedtodeterminetheorderinwhichtheinterruptswouldbeserviced.Discusswhatissuesneedtobeconsideredinassigningprioritiestodifferentinterrupts.Answer:Anumberofissuesneedtobeconsideredinordertodeterminethepriorityschemetobeusedtodeterminetheorderinwhichtheinterruptsneedtobeserviced.First,interruptsraisedbydevicesshouldbegivenhigherprioritythantrapsgeneratedbytheuserprogram;adeviceinterruptcanthereforeinterruptcodeusedforhandlingsystemcalls.Second,interruptsthatcontroldevicesmightbegivenhigherprioritythaninterruptsthatsimplyperformtaskssuchascopyingdataservedupadevicetouser/kernelbuffers,sincesuchtaskscanalwaysbedelayed.Third,devicesthathaverealtimeconstraintsonwhenitsdataishandledshouldbegivenhigherprioritythanotherdevices.Also,devicesthatdonothaveanyformofbufferingforitsdatawouldhavetobeassignedhigherprioritysincethedatacouldbeavailableonlyforashortperiodoftime.13.2Whataretheadvantagesanddisadvantagesofsupportingmemory-mappedI/Otodevicecontrolregisters?Answer:Theadvantageofsupportingmemory-mappedI/OtodevicecontrolregistersisthatiteliminatestheneedforspecialI/OinstructionsfromtheinstructionsetandthereforealsodoesnotrequiretheenforcementofprotectionrulesthatpreventuserprogramsfromexecutingtheseI/Oinstructions.Thedisadvantageisthattheresultingflexibilityneedstobehandledwithcare;thememorytranslationunitsneedtoensurethatthememoryaddressesassociatedwiththedevicecontrolregistersarenotaccessiblebyuserprogramsinordertoensureprotection.13.3ConsiderthefollowingI/Oscenariosonasingle-userPC.a.Amouseusedwithagraphicaluserinterfaceb.Atapedriveonamultitaskingoperatingsystem(assumenodevicepreallocationisavailable)c.Adiskdrivecontaininguserfilesd.Agraphicscardwithdirectbusconnection,accessiblethroughmemory-mappedI/OForeachoftheseI/Oscenarios,wouldyoudesigntheoperatingsystemtousebuffering,spooling,caching,oracombination?WouldyouusepolledI/O,orinterrupt-drivenI/O?Givereasonsforyourchoices.Answer: 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3a.AmouseusedwithagraphicaluserinterfaceBufferingmaybeneededtorecordmousemovementduringtimeswhenhigher-priorityoperationsaretakingplace.Spoolingandcachingareinappropriate.InterruptdrivenI/Oismostappropriate.b.Atapedriveonamultitaskingoperatingsystem(assumenodevicepreallocationisavailable)BufferingmaybeneededtomanagethroughputdifferencebetweenthetapedriveandthesourceordestinationoftheI/O,Cachingcanbeusedtoholdcopiesofdatathatresidesonthetape,forfasteraccess.Spoolingcouldbeusedtostagedatatothedevicewhenmultipleusersdesiretoreadfromorwritetoit.InterruptdrivenI/Oislikelytoallowthebestperformance.c.AdiskdrivecontaininguserfilesBufferingcanbeusedtoholddatawhileintransitfromuserspacetothedisk,andvisaversa.Cachingcanbeusedtoholddisk-residentdataforimprovedperformance.Spoolingisnotnecessarybecausedisksareshared-accessdevices.Interrupt-drivenI/Oisbestfordevicessuchasdisksthattransferdataatslowrates.d.Agraphicscardwithdirectbusconnection,accessiblethroughmemory-mappedI/OBufferingmaybeneededtocontrolmultipleaccessandforperformance(double-bufferingcanbeusedtoholdthenextscreenimagewhiledisplayingthecurrentone).Cachingandspoolingarenotnecessaryduetothefastandshared-accessnaturesofthedevice.PollingandinterruptsareonlyusefulforinputandforI/Ocompletiondetection,neitherofwhichisneededforamemory-mappeddevice.13.4Inmostmultiprogrammedsystems,userprogramsaccessmemorythroughvirtualaddresses,whiletheoperatingsystemusesrawphysicaladdressestoaccessmemory.WhataretheimplicationsofthisdesignontheinitiationofI/Ooperationsbytheuserprogramandtheirexecutionbytheoperatingsystem?Answer:Theuserprogramtypicallyspecifiesabufferfordatatobetransmittedtoorfromadevice.Thisbufferexistsinuserspaceandisspecifiedbyavirtualaddress.ThekernelneedstoissuetheI/OoperationandneedstocopydatabetweentheuserbufferanditsownkernelbufferbeforeoraftertheI/Ooperation.Inordertoaccesstheuserbuffer,thekernelneedstotranslatethevirtualaddressprovidedbytheuserprogramtothecorrespondingphysicaladdresswithinthecontextoftheuserprogram’svirtualaddressspace.Thistranslationistypicallyperformedinsoftwareandthereforeincursoverhead.Also,iftheuserbufferisnotcurrentlypresentinphysicalmemory,thecorrespondingpage(s)needtoobtainedfromtheswapspace.Thisoperationmightrequirecarefulhandlingandmightdelaythedatacopyoperation.13.5Whatarethevariouskindsofperformanceoverheadsassociatedwithservicinganinterrupt?Answer:Whenaninterruptoccursthecurrentlyexecutingprocessisinterruptsand 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3itsstateisstoredintheappropriateprocesscontrolblock.Theinterruptserviceroutineisthendispatchinordertodealwiththeinterrupt.Oncompletionofhandlingoftheinterrupt,thestateoftheprocessisrestoredandtheprocessisresumed.Therefore,theperformanceoverheadsincludethecostofsavingandrestoringprocessstateandthecostofflushingtheinstructionpipelineandrestoringtheinstructionsintothepipelinewhentheprocessisrestarted.13.6DescribethreecircumstancesunderwhichblockingI/Oshouldbeused.DescribethreecircumstancesunderwhichnonblockingI/Oshouldbeused.WhynotjustimplementnonblockingI/Oandhaveprocessesbusy-waituntiltheirdeviceisready?Answer: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.13.7Typically,atthecompletionofadeviceI/O,asingleinterruptisraisedandappropriatelyhandledbythehostprocessor.Incertainsettings,however,thecodethatistobeexecutedatthecompletionoftheI/Ocanbebrokenintotwoseparatepieces,oneofwhichexecutesimmediatelyaftertheI/Ocompletesandschedulesasecondinterruptfortheremainingpieceofcodetobeexecutedatalatertime.Whatisthepurposeofusingthisstrategyinthedesignofinterrupthandlers?Answer:Thepurposeofthisstrategyistoensurethatthemostcriticalaspectoftheinterrupthandlingcodeisperformedfirstandthelesscriticalportionsofthecodeisdelayedforthefuture.Forinstance,whenadevicefinishesanI/Ooperation,thedevicecontroloperationscorrespondingtodeclaringthedeviceasnolongerbeingbusyaremoreimportantinordertoissuefutureoperations.However,thetaskofcopyingthedataprovidedbythedevicetotheappropriateuserorkernelmemoryregionscanbedelayedforafuturepointwhentheCPUisidle.Insuchascenario,alatterlowerpriorityinterrupthandlerisusedtoperformthecopyoperation.13.8SomeDMAcontrollerssupportdirectvirtualmemoryaccess,wherethetargetsofI/OoperationsarespecifiedasvirtualaddressesandatranslationfromvirtualtophysicaladdressisperformedduringtheDMA.Howdoesthisdesigncomplicate 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3thedesignoftheDMAcontroller?Whataretheadvantagesofprovidingsuchafunctionality?Answer:Directvirtualmemoryaccessallowsadevicetoperformatransferfromtwomemory-mappeddeviceswithouttheinterventionoftheCPUortheuseofmainmemoryasastagingground;thedevicesimplyissuememoryoperationstothememory-mappedaddressesofatargetdeviceandtheensuingvirtualaddresstranslationguaranteesthatthedataistransferredtotheappropriatedevice.Thisfunctionality,however,comesatthecostofhavingtosupportvirtualaddresstranslationonaddressesaccessedbyaDMAcontrollerandrequirestheadditionofanaddresstranslationunittotheDMAcontroller.TheaddresstranslationresultsinbothhardwareandsoftwarecostsandmightalsoresultincoherenceproblemsbetweenthedatastructuresmaintainedbytheCPUforaddresstranslationandcorrespondingstructuresusedbytheDMAcontroller.Thesecoherenceissueswouldalsoneedtobedealtwithandresultsinfurtherincreaseinsystemcomplexity.13.9UNIXcoordinatestheactivitiesofthekernelI/Ocomponentsbymanipulatingsharedin-kerneldatastructures,whereasWindowsNTusesobject-orientedmessagepassingbetweenkernelI/Ocomponents.Discussthreeprosandthreeconsofeachapproach.Answer:ThreeprosoftheUNIXmethod:Veryefficient,lowoverheadandlowamountofdatamovementFastimplementation—nocoordinationneededwithotherkernelcomponentsSimple,solesschanceofdatalossThreecons:Nodataprotection,andmorepossibleside-effectsfromchangessomoredifficulttodebugDifficulttoimplementnewI/Omethods:newdatastructuresneededratherthanjustnewobjectsComplicatedkernelI/Osubsystem,fullofdatastructures,accessroutines,andlockingmechanisms13.10Write(inpseudocode)animplementationofvirtualclocks,includingthequeuingandmanagementoftimerrequestsforthekernelandapplications.Assumethatthehardwareprovidesthreetimerchannels.Answer:Eachchannelwouldrunthefollowingalgorithm:/**datadefinitions**///alistofinterruptssortedbyearliest-time-firstorderListinterruptList//thelistthatassociatesarequestwithanentryininterruptListListrequestList//aninterrupt-basedtimerTimertimerwhile(true){/**Getthenextearliesttimeinthelist**/timer.setTime=interruptList.next();/**Aninterruptwilloccurattimetimer.setTime**/ 课后答案网www.khdaw.comOperatingsystemconcepts(Seventhedition)2008.3/**nowwaitforthetimerinterrupti.e.forthetimertoexpire**/notify(requestList.next());}13.11DiscusstheadvantagesanddisadvantagesofguaranteeingreliabletransferofdatabetweenmodulesintheSTREAMSabstraction.Answer:Reliabletransferofdatarequiresmodulestocheckwhetherspaceisavailableonthetargetmoduleandtoblockthesendingmoduleifspaceisnotavailable.Thischeckrequiresextracommunicationbetweenthemodules,buttheoverheadenablesthesystemtoprovideastrongerabstractionthanonewhichdoesnotguaranteereliabletransfer.Thestrongerabstractiontypicallyreducesthecomplexityofthecodeinthemodules.IntheSTREAMSabstraction,however,thereisunreliabilityintroducedbythedriverend,whichisallowedtodropmessagesifthecorrespondingdevicecannothandletheincomingdata.Consequently,evenifthereisreliabletransferofdatabetweenthemodules,messagescouldbedroppedatthedeviceifthecorrespondingbufferfillsup.Thisrequiresretransmissionofdataandspecialcodeforhandlingsuchretransmissions,therebysomewhatlimitingtheadvantagesthatareassociatedwithreliabletransferbetweenthemodules.'