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

'课后答案网您最真诚的朋友www.hackshp.cn网团队竭诚为学生服务，免费提供各门课后答案，不用积分，甚至不用注册，旨在为广大学生提供自主学习的平台！课后答案网：www.hackshp.cn视频教程网：www.efanjy.comPPT课件网：www.ppthouse.com INSTRUCTORSMANUALTOACCOMPANYOPERATINGSYSTEMCONCEPTS课后答案网SIXTHEDITIONABRAHAMSILBERSCHATZBellLaboratorieswww.hackshp.cnPETERBAERGALVINCorporateTechnologiesGREGGAGNEWestminsterCollegeCopyrightc2001A.Silberschatz,P.GalvinandGregGagne 课后答案网www.hackshp.cn PREFACEThisvolumeisaninstructorsmanualfortheSixthEditionofOperating-SystemConceptsbyAbrahamSilberschatz,PeterBaerGalvin,andGregGagne.Itconsistsofanswerstotheexercisesintheparenttext.Incaseswheretheanswertoaquestioninvolvesalongprogram,algorithmdevelopment,oranessay,noanswerisgiven,butsimplythekeywordsNoAnswerareadded.Althoughwehavetriedtoproduceaninstructorsmanualthatwillaidalloftheusersofourbookasmuchaspossible,therecanalwaysbeimprovements(improvedanswers,additionalquestions,sampletestquestions,programmingprojects,alternativeordersofpresentationof课后答案网thematerial,additionalreferences,andsoon).Weinviteyou,bothinstructorsandstudents,tohelpusinimprovingthismanual.IfyouhavebettersolutionstotheexercisesorotheritemswhichwouldbeofusewithOperating-SystemConcepts,weinviteyoutosendthemtousforconsiderationinlatereditionsofthismanual.Allcontributionswill,ofcourse,beproperlycreditedtotheircontributor.Internetelectronicmailshouldbeaddressedtoavi@bell-labs.com.PhysicalmailmaybesenttoAviSilberschatz,InformationSciencesResearchCenter,MH2T-310,BellLaboratories,600www.hackshp.cnMountainAvenue,MurrayHill,NJ07974,USA.A.S.P.B.GG.G.iii 课后答案网www.hackshp.cn CONTENTSChapter1Introduction...................................................................1Chapter2Computer-SystemStructures..................................................5Chapter3Operating-SystemStructures..................................................9Chapter4Processes.....................................................................13Chapter5Threads......................................................................15课后答案网Chapter6CPUScheduling.............................................................17Chapter7ProcessSynchronization.....................................................23Chapter8Deadlocks....................................................................27Chapter9MemoryManagement........................................................31Chapter10VirtualMemorywww.hackshp.cn.............................................................37Chapter11File-SystemInterface........................................................45Chapter12File-SystemImplementation................................................53Chapter13I/OSystems.................................................................57Chapter14Mass-StorageStructure......................................................69Chapter15DistributedSystemStructures...............................................75Chapter16DistributedFileSystems....................................................77Chapter17DistributedCoordination....................................................79Chapter18Protection...................................................................81Chapter19Security......................................................................83Chapter20TheLinuxSystem...........................................................87Chapter21Windows2000...............................................................97AppendixATheFreeBSDSystem.......................................................101AppendixBTheMachSystem...........................................................101v 课后答案网www.hackshp.cn Chapter1INTRODUCTIONChapter1introducesthegeneraltopicofoperatingsystemsandahandfulofimportantconcepts(multiprogramming,timesharing,distributedsystem,andsoon).Thepurposeistoshowwhyoperatingsystemsarewhattheyarebyshowinghowtheydeveloped.Inoperatingsystems,asinmuchofcomputerscience,weareledtothepresentbythepathswetookinthepast,andwecanbetterunderstandboththepresentandthefuturebyunderstandingthepast.Additionalworkthatmightbeconsideredislearningabouttheparticularsystemsthatthestudentswillhaveaccesstoatyourinstitution.Thisisstilljustageneraloverview,asspecific课后答案网interfacesareconsideredinChapter3.AnswerstoExercises1.1Whatarethethreemainpurposesofanoperatingsystem?www.hackshp.cnAnswer:Toprovideanenvironmentforacomputerusertoexecuteprogramsoncomputerhardwareinaconvenientandefficientmanner.Toallocatetheseparateresourcesofthecomputerasneededtosolvetheproblemgiven.Theallocationprocessshouldbeasfairandefficientaspossible.Asacontrolprogramitservestwomajorfunctions:(1)supervisionoftheexecutionofuserprogramstopreventerrorsandimproperuseofthecomputer,and(2)manage-mentoftheoperationandcontrolofI/Odevices.1.2Listthefourstepsthatarenecessarytorunaprogramonacompletelydedicatedmachine.Answer:a.Reservemachinetime.b.Manuallyloadprogramintomemory.c.Loadstartingaddressandbeginexecution.d.Monitorandcontrolexecutionofprogramfromconsole.1 2Chapter1Introduction1.3Whatisthemainadvantageofmultiprogramming?Answer:MultiprogrammingmakesefficientuseoftheCPUbyoverlappingthedemandsfortheCPUanditsI/Odevicesfromvarioususers.ItattemptstoincreaseCPUutilizationbyalwayshavingsomethingfortheCPUtoexecute.1.4Whatarethemaindifferencesbetweenoperatingsystemsformainframecomputersandpersonalcomputers?Answer:Thedesigngoalsofoperatingsystemsforthosemachinesarequitedifferent.PCsareinexpensive,sowastedresourceslikeCPUcyclesareinconsequential.Resourcesarewastedtoimproveusabilityandincreasesoftwareuserinterfacefunctionality.Main-framesaretheopposite,soresourceuseismaximized,attheexpensiveofeaseofuse.1.5Inamultiprogrammingandtime-sharingenvironment,severaluserssharethesystemsi-multaneously.Thissituationcanresultinvarioussecurityproblems.a.Whataretwosuchproblems?b.Canweensurethesamedegreeofsecurityinatime-sharedmachineaswehaveinadedicatedmachine?Explainyouranswer.Answer:a.Stealingorcopyingonesprogramsordata;usingsystemresources(CPU,memory,diskspace,peripherals)withoutproperaccounting.b.Probablynot,sinceanyprotectionschemedevisedbyhumanscaninevitablybebro-kenbyahuman,andthemorecomplexthescheme,themoredifficultitistofeelconfidentofitscorrectimplementation.课后答案网1.6Definetheessentialpropertiesofthefollowingtypesofoperatingsystems:a.Batchb.Interactivec.Timesharingd.Realtimewww.hackshp.cne.Networkf.DistributedAnswer:a.Batch.Jobswithsimilarneedsarebatchedtogetherandrunthroughthecomputerasagroupbyanoperatororautomaticjobsequencer.PerformanceisincreasedbyattemptingtokeepCPUandI/Odevicesbusyatalltimesthroughbuffering,off-lineoperation,spooling,andmultiprogramming.Batchisgoodforexecutinglargejobsthatneedlittleinteraction;itcanbesubmittedandpickeduplater.b.Interactive.Thissystemiscomposedofmanyshorttransactionswheretheresultsofthenexttransactionmaybeunpredictable.Responsetimeneedstobeshort(seconds)sincetheusersubmitsandwaitsfortheresult.c.Timesharing.ThissystemsusesCPUschedulingandmultiprogrammingtoprovideeconomicalinteractiveuseofasystem.TheCPUswitchesrapidlyfromoneusertoanother.Insteadofhavingajobdefinedbyspooledcardimages,eachprogramreads AnswerstoExercises3itsnextcontrolcardfromtheterminal,andoutputisnormallyprintedimmediatelytothescreen.d.Realtime.Oftenusedinadedicatedapplication,thissystemreadsinformationfromsensorsandmustrespondwithinafixedamountoftimetoensurecorrectperfor-mance.e.Network.f.Distributed.Thissystemdistributescomputationamongseveralphysicalprocessors.Theprocessorsdonotsharememoryoraclock.Instead,eachprocessorhasitsownlocalmemory.Theycommunicatewitheachotherthroughvariouscommunicationlines,suchasahigh-speedbusortelephoneline.1.7Wehavestressedtheneedforanoperatingsystemtomakeefficientuseofthecomputinghardware.Whenisitappropriatefortheoperatingsystemtoforsakethisprincipleandto“waste”resources?Whyissuchasystemnotreallywasteful?Answer:Single-usersystemsshouldmaximizeuseofthesystemfortheuser.AGUImight“waste”CPUcycles,butitoptimizestheusersinteractionwiththesystem.1.8Underwhatcircumstanceswouldauserbebetteroffusingatime-sharingsystem,ratherthanapersonalcomputerorsingle-userworkstation?Answer:Whentherearefewotherusers,thetaskislarge,andthehardwareisfast,time-sharingmakessense.Thefullpowerofthesystemcanbebroughttobearontheusersproblem.Theproblemcanbesolvedfasterthanonapersonalcomputer.Anothercaseoccurswhenlotsofotherusersneedresourcesatthesametime.Apersonalcomputerisbestwhenthejobissmallenoughtobeexecutedreasonablyonitandwhenperformanceissufficienttoexecutetheprogramtotheuserssatisfaction.课后答案网1.9Describethedifferencesbetweensymmetricandasymmetricmultiprocessing.Whatarethreeadvantagesandonedisadvantageofmultiprocessorsystems?Answer:Symmetricmultiprocessingtreatsallprocessorsasequals,andI/Ocanbepro-cessedonanyCPU.AsymmetricmultiprocessinghasonemasterCPUandtheremainderCPUsareslaves.Themasterdistributestasksamongtheslaves,andI/Oisusuallydonebythemasteronly.Multiprocessorscansavemoneybynotduplicatingpowersupplies,hous-www.hackshp.cnings,andperipherals.Theycanexecuteprogramsmorequicklyandcanhaveincreasedreliability.Theyarealsomorecomplexinbothhardwareandsoftwarethanuniprocessorsystems.1.10Whatisthemaindifficultythataprogrammermustovercomeinwritinganoperatingsystemforareal-timeenvironment?Answer:Themaindifficultyiskeepingtheoperatingsystemwithinthefixedtimecon-straintsofareal-timesystem.Ifthesystemdoesnotcompleteataskinacertaintimeframe,itmaycauseabreakdownoftheentiresystemitisrunning.Thereforewhenwrit-inganoperatingsystemforareal-timesystem,thewritermustbesurethathisschedulingschemesdontallowresponsetimetoexceedthetimeconstraint.1.11Considerthevariousdefinitionsofoperatingsystem.Considerwhethertheoperatingsys-temshouldincludeapplicationssuchasWebbrowsersandmailprograms.Argueboththatitshouldandthatitshouldnot,andsupportyouranswer.Answer:Noanswer.1.12Whatarethetradeoffsinherentinhandheldcomputers?Answer:Noanswer. 4Chapter1Introduction1.13Consideracomputingclusterconsistingoftwonodesrunningadatabase.Describetwowaysinwhichtheclustersoftwarecanmanageaccesstothedataonthedisk.Discussthebenefitsanddetrimentsofeach.Answer:Noanswer.课后答案网www.hackshp.cn Chapter2COMPUTER-SYSTEMSTRUCTURESChapter2discussesthegeneralstructureofcomputersystems.Itmaybeagoodideatore-viewthebasicconceptsofmachineorganizationandassemblylanguageprogramming.Thestudentsshouldbecomfortablewiththeconceptsofmemory,CPU,registers,I/O,interrupts,instructions,andtheinstructionexecutioncycle.Sincetheoperatingsystemistheinterfacebe-tweenthehardwareanduserprograms,agoodunderstandingofoperatingsystemsrequiresanunderstandingofbothhardwareandprograms.课后答案网AnswerstoExercises2.1PrefetchingisamethodofoverlappingtheI/Oofajobwiththatjobsowncomputation.Theideaissimple.Afterareadoperationcompletesandthejobisabouttostartoperatingonthedata,theinputdeviceisinstructedtobeginthenextreadimmediately.TheCPUandinputdevicearethenbothbusy.Withluck,bythetimethejobisreadyforthenextdatawww.hackshp.cnitem,theinputdevicewillhavefinishedreadingthatdataitem.TheCPUcanthenbeginprocessingthenewlyreaddata,whiletheinputdevicestartstoreadthefollowingdata.Asimilarideacanbeusedforoutput.Inthiscase,thejobcreatesdatathatareputintoabufferuntilanoutputdevicecanacceptthem.Comparetheprefetchingschemewiththespoolingscheme,wheretheCPUoverlapstheinputofonejobwiththecomputationandoutputofotherjobs.Answer:Prefetchingisauser-basedactivity,whilespoolingisasystem-basedactivity.SpoolingisamuchmoreeffectivewayofoverlappingI/OandCPUoperations.2.2Howdoesthedistinctionbetweenmonitormodeandusermodefunctionasarudimentaryformofprotection(security)system?Answer:Byestablishingasetofprivilegedinstructionsthatcanbeexecutedonlywheninthemonitormode,theoperatingsystemisassuredofcontrollingtheentiresystematalltimes.2.3Whatarethedifferencesbetweenatrapandaninterrupt?Whatistheuseofeachfunction?Answer:Aninterruptisahardware-generatedchange-of-flowwithinthesystem.Aninterrupthandlerissummonedtodealwiththecauseoftheinterrupt;controlisthenre-5 6Chapter2Computer-SystemStructuresturnedtotheinterruptedcontextandinstruction.Atrapisasoftware-generatedinterrupt.AninterruptcanbeusedtosignalthecompletionofanI/Otoobviatetheneedfordevicepolling.Atrapcanbeusedtocalloperatingsystemroutinesortocatcharithmeticerrors.2.4ForwhattypesofoperationsisDMAuseful?Explainyouranswer.Answer:DMAisusefulfortransferringlargequantitiesofdatabetweenmemoryanddevices.IteliminatestheneedfortheCPUtobeinvolvedinthetransfer,allowingthetransfertocompletemorequicklyandtheCPUtoperformothertasksconcurrently.2.5Whichofthefollowinginstructionsshouldbeprivileged?a.Setvalueoftimer.b.Readtheclock.c.Clearmemory.d.Turnoffinterrupts.e.Switchfromusertomonitormode.Answer:Thefollowinginstructionsshouldbeprivileged:a.Setvalueoftimer.b.Clearmemory.c.Turnoffinterrupts.d.Switchfromusertomonitormode.2.6Somecomputersystemsdonotprovideaprivilegedmodeofoperationinhardware.Con-课后答案网siderwhetheritispossibletoconstructasecureoperatingsystemforthesecomputers.Giveargumentsboththatitisandthatitisnotpossible.Answer:Anoperatingsystemforamachineofthistypewouldneedtoremainincontrol(ormonitormode)atalltimes.Thiscouldbeaccomplishedbytwomethods:a.Softwareinterpretationofalluserprograms(likesomeBASIC,APL,andLISPsys-tems,forexample).Thesoftwareinterpreterwouldprovide,insoftware,whatthewww.hackshp.cnhardwaredoesnotprovide.b.Requiremeantthatallprogramsbewritteninhigh-levellanguagessothatallob-jectcodeiscompiler-produced.Thecompilerwouldgenerate(eitherin-lineorbyfunctioncalls)theprotectionchecksthatthehardwareismissing.2.7Someearlycomputersprotectedtheoperatingsystembyplacingitinamemorypartitionthatcouldnotbemodifiedbyeithertheuserjobortheoperatingsystemitself.Describetwodifficultiesthatyouthinkcouldarisewithsuchascheme.Answer:Thedatarequiredbytheoperatingsystem(passwords,accesscontrols,account-inginformation,andsoon)wouldhavetobestoredinorpassedthroughunprotectedmemoryandthusbeaccessibletounauthorizedusers.2.8Protectingtheoperatingsystemiscrucialtoensuringthatthecomputersystemoperatescorrectly.Provisionofthisprotectionisthereasonbehinddual-modeoperation,memoryprotection,andthetimer.Toallowmaximumflexibility,however,wewouldalsoliketoplaceminimalconstraintsontheuser.Thefollowingisalistofoperationsthatarenormallyprotected.Whatistheminimalsetofinstructionsthatmustbeprotected? AnswerstoExercises7a.Changetousermode.b.Changetomonitormode.c.Readfrommonitormemory.d.Writeintomonitormemory.e.Fetchaninstructionfrommonitormemory.f.Turnontimerinterrupt.g.Turnofftimerinterrupt.Answer:Theminimalsetofinstructionsthatmustbeprotectedare:a.Changetomonitormode.b.Readfrommonitormemory.c.Writeintomonitormemory.d.Turnofftimerinterrupt.2.9Givetworeasonswhycachesareuseful.Whatproblemsdotheysolve?Whatproblemsdotheycause?Ifacachecanbemadeaslargeasthedeviceforwhichitiscaching(forinstance,acacheaslargeasadisk),whynotmakeitthatlargeandeliminatethedevice?Answer:Cachesareusefulwhentwoormorecomponentsneedtoexchangedata,andthecomponentsperformtransfersatdifferingspeeds.Cahcessolvethetransferproblembyprovidingabufferofintermediatespeedbetweenthecomponents.Ifthefastdevicefindsthedataitneedsinthecache,itneednotwaitfortheslowerdevice.Thedatainthecachemustbekeptconsistentwiththedatainthecomponents.Ifacomponenthas课后答案网adatavaluechange,andthedatumisalsointhecache,thecachemustalsobeupdated.Thisisespeciallyaproblemonmultiprocessorsystemswheremorethanoneprocessmaybeaccessingadatum.Acomponentmaybeeliminatedbyanequal-sizedcache,butonlyif:(a)thecacheandthecomponenthaveequivalentstate-savingcapacity(thatis,ifthecomponentretainsitsdatawhenelectricityisremoved,thecachemustretaindataaswell),and(b)thecacheisaffordable,becausefasterstoragetendstobemoreexpensive.www.hackshp.cn2.10Writinganoperatingsystemthatcanoperatewithoutinterferencefrommaliciousorun-debuggeduserprogramsrequiressomehardwareassistance.Namethreehardwareaidsforwritinganoperatingsystem,anddescribehowtheycouldbeusedtogethertoprotecttheoperatingsystem.Answer:a.Monitor/usermodeb.Privilegedinstructionsc.Timerd.Memoryprotection2.11SomeCPUsprovideformorethantwomodesofoperation.Whataretwopossibleusesofthesemultiplemodes?Answer:Noanswer.2.12WhatarethemaindifferencesbetweenaWANandaLAN?Answer:Noanswer. 8Chapter2Computer-SystemStructures2.13Whatnetworkconfigurationwouldbestsuitthefollowingenviron-ments?a.Adormitoryfloorb.Auniversitycampusc.Astated.AnationAnswer:Noanswer.课后答案网www.hackshp.cn Chapter3OPERATING-SYSTEMSTRUCTURESChapter3isconcernedwiththeoperating-systeminterfacesthatusers(oratleastprogrammers)actuallysee:systemcalls.Thetreatmentissomewhatvaguesincemoredetailrequirespickingaspecificsystemtodiscuss.Thischapterisbestsupplementedwithexactlythisdetailforthespecificsystemthestudentshaveathand.Ideallytheyshouldstudythesystemcallsandwritesomeprogramsmakingsystemcalls.Thischapteralsotiestogetherseveralimportantconceptsincludinglayereddesign,virtualmachines,JavaandtheJavavirtualmachine,systemdesignandimplementation,systemgeneration,andthepolicy/mechanismdifference.课后答案网AnswerstoExercises3.1Whatarethefivemajoractivitiesofanoperatingsysteminregardtoprocessmanagement?Answer:www.hackshp.cnThecreationanddeletionofbothuserandsystemprocessesThesuspensionandresumptionofprocessesTheprovisionofmechanismsforprocesssynchronizationTheprovisionofmechanismsforprocesscommunicationTheprovisionofmechanismsfordeadlockhandling3.2Whatarethethreemajoractivitiesofanoperatingsysteminregardtomemorymanage-ment?Answer:Keeptrackofwhichpartsofmemoryarecurrentlybeingusedandbywhom.Decidewhichprocessesaretobeloadedintomemorywhenmemoryspacebecomesavailable.Allocateanddeallocatememoryspaceasneeded.9 10Chapter3Operating-SystemStructures3.3Whatarethethreemajoractivitiesofanoperatingsysteminregardtosecondary-storagemanagement?Answer:Free-spacemanagement.Storageallocation.Diskscheduling.3.4Whatarethefivemajoractivitiesofanoperatingsysteminregardtofilemanagement?Answer:ThecreationanddeletionoffilesThecreationanddeletionofdirectoriesThesupportofprimitivesformanipulatingfilesanddirectoriesThemappingoffilesontosecondarystorageThebackupoffilesonstable(nonvolatile)storagemedia3.5Whatisthepurposeofthecommandinterpreter?Whyisitusuallyseparatefromthekernel?Answer:Itreadscommandsfromtheuserorfromafileofcommandsandexecutesthem,usuallybyturningthemintooneormoresystemcalls.Itisusuallynotpartofthekernelsincethecommandinterpreterissubjecttochanges.3.6Listfiveservicesprovidedbyanoperatingsystem.Explainhoweachprovidesconve-课后答案网niencetotheusers.Explainalsoinwhichcasesitwouldbeimpossibleforuser-levelpro-gramstoprovidetheseservices.Answer:Programexecution.Theoperatingsystemloadsthecontents(orsections)ofafileintomemoryandbeginsitsexecution.Auser-levelprogramcouldnotbetrustedtoproperlyallocateCPUwww.hackshp.cntime.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,transmittedacrossacom-municationsmedium,andreassembledbythedestinationsystem.Packetorderinganddatacorrectionmusttakeplace.Again,userprogramsmightnotcoordinateac-cesstothenetworkdevice,ortheymightreceivepacketsdestinedforotherprocesses. AnswerstoExercises11Errordetection.Errordetectionoccursatboththehardwareandsoftwarelevels.Atthehardwarelevel,alldatatransfersmustbeinspectedtoensurethatdatahavenotbeencorruptedintransit.Alldataonmediamustbecheckedtobesuretheyhavenotchangedsincetheywerewrittentothemedia.Atthesoftwarelevel,mediamustbecheckedfordataconsistency;forinstance,dothenumberofallocatedandunallocatedblocksofstoragematchthetotalnumberonthedevice.There,errorsarefrequentlyprocess-independent(forinstance,thecorruptionofdataonadisk),sotheremustbeaglobalprogram(theoperatingsystem)thathandlesalltypesoferrors.Also,byhavingerrorsprocessedbytheoperatingsystem,processesneednotcontaincodetocatchandcorrectalltheerrorspossibleonasystem.3.7Whatisthepurposeofsystemcalls?Answer:Systemcallsallowuser-levelprocessestorequestservicesoftheoperatingsys-tem.3.8Usingsystemcalls,writeaprogramineitherCorC++thatreadsdatafromonefileandcopiesittoanotherfile.SuchaprogramwasdescribedinSection3.3.Answer:PleaserefertothesupportingWebsiteforsourcecodesolution.3.9WhydoesJavaprovidetheabilitytocallfromaJavaprogramnativemethodsthatarewrittenin,say,CorC++?Provideanexamplewhereanativemethodisuseful.Answer:JavaprogramsareintendedtobeplatformI/Oindependent.Therefore,thelanguagedoesnotprovideaccesstomostspecificsystemresourcessuchasreadingfromI/Odevicesorports.ToperformasystemI/Ospecificoperation,youmustwriteitinalanguagethatsupportssuchfeatures(suchasCorC++.)KeepinmindthataJavapro-gramthatcallsanativemethodwritteninanotherlanguagewillnolongerbearchitecture-neutral.课后答案网3.10Whatisthepurposeofsystemprograms?Answer:Systemprogramscanbethoughtofasbundlesofusefulsystemcalls.Theyprovidebasicfunctionalitytousersandsousersdonotneedtowritetheirownprogramstosolvecommonproblems.3.11Whatisthemainadvantageofthelayeredapproachtosystemdesign?www.hackshp.cnAnswer:Asinallcasesofmodulardesign,designinganoperatingsysteminamodularwayhasseveraladvantages.Thesystemiseasiertodebugandmodifybecausechangesaffectonlylimitedsectionsofthesystemratherthantouchingallsectionsoftheoperatingsystem.Informationiskeptonlywhereitisneededandisaccessibleonlywithinadefinedandrestrictedarea,soanybugsaffectingthatdatamustbelimitedtoaspecificmoduleorlayer.3.12Whatarethemainadvantagesofthemicrokernelapproachtosystemdesign?Answer:Benefitstypicallyincludethefollowing(a)addinganewservicedoesnotrequiremodifyingthekernel,(b)itismoresecureasmoreoperationsaredoneinusermodethaninkernelmode,and(c)asimplerkerneldesignandfunctionalitytypicallyresultsinamorereliableoperatingsystem.3.13Whatisthemainadvantageforanoperating-systemdesignerofusingavirtual-machinearchitecture?Whatisthemainadvantageforauser?Answer:Thesystemiseasytodebug,andsecurityproblemsareeasytosolve.Virtualmachinesalsoprovideagoodplatformforoperatingsystemresearchsincemanydifferentoperatingsystemsmayrunononephysicalsystem. 12Chapter3Operating-SystemStructures3.14Whyisajust-in-timecompilerusefulforexecutingJavaprograms?Answer:Javaisaninterpretedlanguage.ThismeansthattheJVMinterpretsthebyte-codeinstructionsoneatatime.Typically,mostinterpretedenvironmentsareslowerthanrunningnativebinaries,fortheinterpretationprocessrequiresconvertingeachinstructionintonativemachinecode.Ajust-in-time(JIT)compilercompilesthebytecodeforamethodintonativemachinecodethefirsttimethemethodisencountered.ThismeansthattheJavaprogramisessentiallyrunningasanativeapplication(ofcourse,theconversionprocessoftheJITtakestimeaswellbutnotasmuchasbytecodeinterpretation.)Furthermore,theJITcachescompiledcodesothatitmaybereusedthenexttimethemethodisencountered.AJavaprogramthatisrunbyaJITratherthanatraditionalinterpretertypicallyrunsmuchfaster.3.15Whyistheseparationofmechanismandpolicyadesirableproperty?Answer:Mechanismandpolicymustbeseparatetoensurethatsystemsareeasytomodify.Notwosysteminstallationsarethesame,soeachinstallationmaywanttotunetheoperatingsystemtosuititsneeds.Withmechanismandpolicyseparate,thepolicymaybechangedatwillwhilethemechanismstaysunchanged.Thisarrangementprovidesamoreflexiblesystem.3.16TheexperimentalSynthesisoperatingsystemhasanassemblerincorporatedwithinthekernel.Tooptimizesystem-callperformance,thekernelassemblesroutineswithinkernelspacetominimizethepaththatthesystemcallmusttakethroughthekernel.Thisap-proachistheantithesisofthelayeredapproach,inwhichthepaththroughthekernelisextendedsothatbuildingtheoperatingsystemismadeeasier.DiscusstheprosandconsoftheSynthesisapproachtokerneldesignandtosystem-performanceoptimization.Answer:Synthesisisimpressiveduetotheperformanceitachievesthroughon-the-flycompilation.Unfortunately,itisdifficulttodebugproblemswithinthekernelduetothe课后答案网fluidityofthecode.Also,suchcompilationissystemspecific,makingSynthesisdifficulttoport(anewcompilermustbewrittenforeacharchitecture).www.hackshp.cn Chapter4PROCESSESInthischapterweintroducetheconceptsofaprocessandconcurrentexecution;Theseconceptsareattheveryheartofmodernoperatingsystems.Aprocessisisaprograminexecutionandistheunitofworkinamoderntime-sharingsystem.Suchasystemconsistsofacollectionofprocesses:Operating-systemprocessesexecutingsystemcodeanduserprocessesexecutingusercode.Alltheseprocessescanpotentiallyexecuteconcurrently,withtheCPU(orCPUs)multiplexedamongthem.ByswitchingtheCPUbetweenprocesses,theoperatingsystemcanmakethecomputermoreproductive.Wealsointroducethenotionofathread(lightweight课后答案网process)andinterprocesscommunication(IPC).ThreadsarediscussedinmoredetailinChapter5.AnswerstoExerciseswww.hackshp.cn4.1MS-DOSprovidednomeansofconcurrentprocessing.Discussthreemajorcomplicationsthatconcurrentprocessingaddstoanoperatingsystem.Answer:Amethodoftimesharingmustbeimplementedtoalloweachofseveralprocessestohaveaccesstothesystem.ThismethodinvolvesthepreemptionofprocessesthatdonotvoluntarilygiveuptheCPU(byusingasystemcall,forinstance)andthekernelbeingreentrant(somorethanoneprocessmaybeexecutingkernelcodeconcurrently).Processesandsystemresourcesmusthaveprotectionsandmustbeprotectedfromeachother.Anygivenprocessmustbelimitedintheamountofmemoryitcanuseandtheoperationsitcanperformondeviceslikedisks.Caremustbetakeninthekerneltopreventdeadlocksbetweenprocesses,soprocessesarentwaitingforeachothersallocatedresources.4.2Describethedifferencesamongshort-term,medium-term,andlong-termscheduling.Answer:13 14Chapter4ProcessesShort-term(CPUscheduler)selectsfromjobsinmemorythosejobsthatarereadytoexecuteandallocatestheCPUtothem.Medium-termusedespeciallywithtime-sharingsystemsasanintermediateschedul-inglevel.Aswappingschemeisimplementedtoremovepartiallyrunprogramsfrommemoryandreinstatethemlatertocontinuewheretheyleftoff.Long-term(jobscheduler)determineswhichjobsarebroughtintomemoryforpro-cessing.Theprimarydifferenceisinthefrequencyoftheirexecution.Theshort-termmustselectanewprocessquiteoften.Long-termisusedmuchlessoftensinceithandlesplacingjobsinthesystemandmaywaitawhileforajobtofinishbeforeitadmitsanotherone.4.3ADECSYSTEM-20computerhasmultipleregistersets.Describetheactionsofacontextswitchifthenewcontextisalreadyloadedintooneoftheregistersets.Whatelsemusthappenifthenewcontextisinmemoryratherthaninaregistersetandalltheregistersetsareinuse?Answer:TheCPUcurrent-register-setpointerischangedtopointtothesetcontainingthenewcontext,whichtakesverylittletime.Ifthecontextisinmemory,oneofthecontextsinaregistersetmustbechosenandbemovedtomemory,andthenewcontextmustbeloadedfrommemoryintotheset.Thisprocesstakesalittlemoretimethanonsystemswithonesetofregisters,dependingonhowareplacementvictimisselected.4.4Describetheactionsakerneltakestocontextswitchbetweenprocesses.Answer:Ingeneral,theoperatingsystemmustsavethestateofthecurrentlyrunningprocessandrestorethestateoftheprocessscheduledtoberunnext.SavingthestateofaprocesstypicallyincludesthevaluesofalltheCPUregistersinadditiontomemoryalloca-课后答案网tion.Contextswitchesmustalsoperformmanyarchitecture-specificoperations,includingflushingdataandinstructioncaches.4.5Whatarethebenefitsanddetrimentsofeachofthefollowing?Considerboththesystemsandtheprogrammerslevels.a.Symmetricandasymmetriccommunicationwww.hackshp.cnb.Automaticandexplicitbufferingc.Sendbycopyandsendbyreferenced.Fixed-sizedandvariable-sizedmessagesAnswer:Noanswer.4.6ThecorrectproducerconsumeralgorithminSection4.4allowsonlyn;1bufferstobefullatanyonetime.Modifythealgorithmtoallowallbufferstobeutilizedfully.Answer:Noanswer.4.7Considertheinterprocess-communicationschemewheremailboxesareused.a.SupposeaprocessPwantstowaitfortwomessages,onefrommailboxAandonefrommailboxB.Whatsequenceofsendandreceiveshoulditexecute?b.WhatsequenceofsendandreceiveshouldPexecuteifPwantstowaitforonemessageeitherfrommailboxAorfrommailboxB(orfromboth)? AnswerstoExercises15c.Areceiveoperationmakesaprocesswaituntilthemailboxisnonempty.Eitherdeviseaschemethatallowsaprocesstowaituntilamailboxisempty,orexplainwhysuchaschemecannotexist.Answer:Noanswer.4.8Writeasocket-basedFortuneTellerserver.Yourprogramshouldcreateaserverthatlistenstoaspecifiedport.Whenaclientreceivesaconnection,theservershouldrespondwitharandomfortunechosenfromitsdatabaseoffortunes.Answer:Noanswer.课后答案网www.hackshp.cn 课后答案网www.hackshp.cn Chapter5THREADSTheprocessmodelintroducedinChapter4assumedthataprocesswasanexecutingprogramwithasinglethreadofcontrol.Manymodernoperatingsystemsnowprovidefeaturesforaprocesstocontainmultiplethreadsofcontrol.ThischapterintroducesmanyconceptsassociatedwithmultithreadedcomputersystemsandcovershowtouseJavatocreateandmanipulatethreads.WehavefounditespeciallyusefultodiscusshowaJavathreadmapstothethreadmodelofthehostoperatingsystem.课后答案网AnswerstoExercises5.1Providetwoprogrammingexamplesofmultithreadinggivingimprovedperformanceoverasingle-threadedsolution.Answer:(1)AWebserverthatserviceseachrequestinaseparatethread.(2)Aparal-www.hackshp.cnlelizedapplicationsuchasmatrixmultiplicationwheredifferentpartsofthematrixmaybeworkedoninparallel.(3)AninteractiveGUIprogramsuchasadebuggerwhereathreadisusedtomonitoruserinput,anotherthreadrepresentstherunningapplication,andathirdthreadmonitorsperformance.5.2Providetwoprogrammingexamplesofmultithreadingthatwouldnotimproveperfor-manceoverasingle-threadedsolution.Answer:(1)Anykindofsequentialprogramisnotagoodcandidatetobethreaded.Anexampleofthisisaprogramthatcalculatesanindividualtaxreturn.(2)AnotherexampleisashellprogramsuchastheC-shellorKornshell.Suchaprogrammustcloselymonitoritsownworkingspacesuchasopenfiles,environmentvariables,andcurrentworkingdirectory.5.3Whataretwodifferencesbetweenuser-levelthreadsandkernel-levelthreads?Underwhatcircumstancesisonetypebetterthantheother?Answer:(1)User-levelthreadsareunknownbythekernel,whereasthekernelisawareofkernelthreads.(2)Userthreadsarescheduledbythethreadlibraryandthekernelscheduleskernelthreads.(3)Kernelthreadsneednotbeassociatedwithaprocesswhereaseveryuserthreadbelongstoaprocess.17 18Chapter5Threads5.4Describetheactionstakenbyakerneltocontextswitchbetweenkernel-levelthreads.Answer:ContextswitchingbetweenkernelthreadstypicallyrequiressavingthevalueoftheCPUregistersfromthethreadbeingswitchedoutandrestoringtheCPUregistersofthenewthreadbeingscheduled.5.5Describetheactionstakenbyathreadlibrarytocontextswitchbetweenuser-levelthreads.Answer:Contextswitchingbetweenuserthreadsisquitesimilartoswitchingbetweenkernelthreads,althoughitisdependentonthethreadslibraryandhowitmapsuserthreadstokernelthreads.Ingeneral,contextswitchingbetweenuserthreadsinvolvestakingauserthreadofitsLWPandreplacingitwithanotherthread.Thisacttypicallyinvolvessavingandrestoringthestateoftheregisters.5.6Whatresourcesareusedwhenathreadiscreated?Howdotheydifferfromthoseusedwhenaprocessiscreated?Answer:Becauseathreadissmallerthanaprocess,threadcreationtypicallyusesfewerresourcesthanprocesscreation.Creatingaprocessrequiresallocatingaprocesscontrolblock(PCB),aratherlargedatastructure.ThePCBincludesamemorymap,listofopenfiles,andenvironmentvariables.Allocatingandmanagingthememorymapistypicallythemosttime-consumingactivity.Creatingeitherauserorkernelthreadinvolvesallocat-ingasmalldatastructuretoholdaregisterset,stack,andpriority.5.7Assumeanoperatingsystemmapsuser-levelthreadstothekernelusingthemany-to-manymodelwherethemappingisdonethroughLWPs.Furthermore,thesystemallowsthedeveloperstocreatereal-timethreads.Isitnecessarytoboundareal-timethreadtoanLWP?Explain.Answer:NoAnswer.5.8WriteamultithreadedPthreadorJavaprogramthatgeneratestheFibonacciseries.This课后答案网programshouldworkasfollows:TheuserwillruntheprogramandwillenteronthecommandlinethenumberofFibonaccinumbersthattheprogramistogenerate.TheprogramwillthencreateaseparatethreadthatwillgeneratetheFibonaccinumbers.Answer:PleaserefertothesupportingWebsiteforsourcecodesolution.5.9WriteamultithreadedPthreadorJavaprogramthatoutputsprimenumbers.Thisprogramshouldworkasfollows:Theuserwillruntheprogramandwillenteranumberonthewww.hackshp.cncommandline.Theprogramwillthencreateaseparatethreadthatoutputsalltheprimenumberslessthanorequaltothenumberthattheuserentered.Answer:PleaserefertothesupportingWebsiteforsourcecodesolution. Chapter6CPUSCHEDULINGCPUschedulingisthebasisofmultiprogrammedoperatingsystems.ByswitchingtheCPUamongprocesses,theoperatingsystemcanmakethecomputermoreproductive.Inthischap-ter,weintroducethebasicschedulingconceptsanddiscussingreatlengthCPUscheduling.FCFS,SJF,Round-Robin,Priority,andtheotherschedulingalgorithmsshouldbefamiliartothestudents.Thisistheirfirstexposuretotheideaofresourceallocationandscheduling,soitisimportantthattheyunderstandhowitisdone.Ganttcharts,simulations,andplayactingarevaluablewaystogettheideasacross.Showhowtheideasareusedinothersituations(like课后答案网waitinginlineatapostoffice,awaitertimesharingbetweencustomers,evenclassesbeinganinterleavedRound-Robinschedulingofprofessors).AsimpleprojectistowriteseveraldifferentCPUschedulersandcomparetheirperformancebysimulation.ThesourceofCPUandI/Oburstsmaybegeneratedbyrandomnumbergenera-torsorbyatracetape.Theinstructorcanmakethetracetapeupinadvancetoprovidethesamedataforallstudents.ThefilethatIusedwasasetofjobs,eachjobbeingavariablenumberofalternatingCPUandI/Obursts.ThefirstlineofajobwasthewordJOBandthejobnumber.www.hackshp.cnAnalternatingsequenceofCPUnandI/Onlinesfollowed,eachspecifyingabursttime.ThejobwasterminatedbyanENDlinewiththejobnumberagain.ComparethetimetoprocessasetofjobsusingFCFS,Shortest-Burst-Time,andRound-Robinscheduling.Round-Robinismoredifficult,sinceitrequiresputtingunfinishedrequestsbackinthereadyqueue.AnswerstoExercises6.1ACPUschedulingalgorithmdeterminesanorderfortheexecutionofitsscheduledpro-cesses.Givennprocessestobescheduledononeprocessor,howmanypossibledifferentschedulesarethere?Giveaformulaintermsofn.Answer:n!(nfactorial=nn1n2...21)6.2Definethedifferencebetweenpreemptiveandnonpreemptivescheduling.Statewhystrictnonpreemptiveschedulingisunlikelytobeusedinacomputercenter.Answer:Preemptiveschedulingallowsaprocesstobeinterruptedinthemidstofitsexe-cution,takingtheCPUawayandallocatingittoanotherprocess.Nonpreemptiveschedul-19 20Chapter6CPUSchedulingingensuresthataprocessrelinquishescontroloftheCPUonlywhenitfinisheswithitscurrentCPUburst.6.3Considerthefollowingsetofprocesses,withthelengthoftheCPU-bursttimegiveninmilliseconds:ProcessBurstTimePriorityP1103P211P323P414P552TheprocessesareassumedtohavearrivedintheorderP1,P2,P3,P4,P5,allattime0.a.DrawfourGanttchartsillustratingtheexecutionoftheseprocessesusingFCFS,SJF,anonpreemptivepriority(asmallerprioritynumberimpliesahigherpriority),andRR(quantum=1)scheduling.b.Whatistheturnaroundtimeofeachprocessforeachoftheschedulingalgorithmsinparta?c.Whatisthewaitingtimeofeachprocessforeachoftheschedulingalgorithmsinparta?d.Whichoftheschedulesinpartaresultsintheminimalaveragewaitingtime(overallprocesses)?课后答案网Answer:a.ThefourGanttchartsare12345FCFS1123451www.hackshp.cn31551515RR24351SJF25134Priorityb.TurnaroundtimeFCFSRRSJFPriorityP110191916P211211P3137418P4144219P5191496c.Waitingtime(turnaroundtimeminusbursttime) AnswerstoExercises21FCFSRRSJFPriorityP10996P210100P3115216P4133118P514941d.ShortestJobFirst6.4Supposethatthefollowingprocessesarriveforexecutionatthetimesindicated.Eachprocesswillrunthelistedamountoftime.Inansweringthequestions,usenonpreemptiveschedulingandbasealldecisionsontheinformationyouhaveatthetimethedecisionmustbemade.ProcessArrivalTimeBurstTimeP10.08P20.44P31.01a.WhatistheaverageturnaroundtimefortheseprocesseswiththeFCFSschedulingalgorithm?b.WhatistheaverageturnaroundtimefortheseprocesseswiththeSJFschedulingal-gorithm?c.TheSJFalgorithmissupposedtoimproveperformance,butnoticethatwechosetorunprocessP1attime0becausewedidnotknowthattwoshorterprocesseswouldarrivesoon.Computewhattheaverageturnaroundtimewillbeifthe课后答案网CPUisleftidleforthefirst1unitandthenSJFschedulingisused.RememberthatprocessesP1andP2arewaitingduringthisidletime,sotheirwaitingtimemayincrease.Thisalgorithmcouldbeknownasfuture-knowledgescheduling.Answer:a.10.53www.hackshp.cnb.9.53c.6.86Rememberthatturnaroundtimeisfinishingtimeminusarrivaltime,soyouhavetosub-tractthearrivaltimestocomputetheturnaroundtimes.FCFSis11ifyouforgettosubtractarrivaltime.6.5ConsideravariantoftheRRschedulingalgorithmwheretheentriesinthereadyqueuearepointerstothePCBs.a.Whatwouldbetheeffectofputtingtwopointerstothesameprocessinthereadyqueue?b.Whatwouldbethemajoradvantagesanddisadvantagesofthisscheme?c.HowwouldyoumodifythebasicRRalgorithmtoachievethesameeffectwithouttheduplicatepointers?Answer: 22Chapter6CPUSchedulinga.Ineffect,thatprocesswillhaveincreaseditsprioritysincebygettingtimemoreoftenitisreceivingpreferentialtreatment.b.Theadvantageisthatmoreimportantjobscouldbegivenmoretime,inotherwords,higherpriorityintreatment.Theconsequence,ofcourse,isthatshorterjobswillsuffer.c.Allotalongeramountoftimetoprocessesdeservinghigherpriority.Inotherwords,havetwoormorequantumspossibleintheRound-Robinscheme.6.6Whatadvantageisthereinhavingdifferenttime-quantumsizesondifferentlevelsofamultilevelqueueingsystem?Answer:Processesthatneedmorefrequentservicing,forinstance,interactiveprocessessuchaseditors,canbeinaqueuewithasmalltimequantum.Processeswithnoneedforfrequentservicingcanbeinaqueuewithalargerquantum,requiringfewercontextswitchestocompletetheprocessing,makingmoreefficientuseofthecomputer.6.7Considerthefollowingpreemptivepriority-schedulingalgorithmbasedondynamicallychangingpriorities.Largerprioritynumbersimplyhigherpriority.WhenaprocessiswaitingfortheCPU(inthereadyqueuebutnotrunning),itsprioritychangesatarate;whenitisrunning,itsprioritychangesatarate.Allprocessesaregivenapriorityof0whentheyenterthereadyqueue.Theparametersandcanbesettogivemanydifferentschedulingalgorithms.a.Whatisthealgorithmthatresultsfrom>>0?b.Whatisthealgorithmthatresultsfrom<<0?Answer:课后答案网a.FCFSb.LIFO6.8ManyCPUschedulingalgorithmsareparameterized.Forexample,theRRalgorithmre-quiresaparametertoindicatethetimeslice.Multilevelfeedbackqueuesrequireparame-terstodefinethenumberofqueues,theschedulingalgorithmsforeachqueue,thecriteriawww.hackshp.cnusedtomoveprocessesbetweenqueues,andsoon.Thesealgorithmsarethusreallysetsofalgorithms(forexample,thesetofRRalgorithmsforalltimeslices,andsoon).Onesetofalgorithmsmayincludeanother(forexample,theFCFSalgorithmistheRRalgorithmwithaninfinitetimequantum).What(ifany)relationholdsbetweenthefollowingpairsofsetsofalgorithms?a.PriorityandSJFb.MultilevelfeedbackqueuesandFCFSc.PriorityandFCFSd.RRandSJFAnswer:a.Theshortestjobhasthehighestpriority.b.ThelowestlevelofMLFQisFCFS.c.FCFSgivesthehighestprioritytothejobhavingbeeninexistencethelongest. AnswerstoExercises23d.None6.9Supposethataschedulingalgorithm(atthelevelofshort-termCPUscheduling)favorsthoseprocessesthathaveusedtheleastprocessortimeintherecentpast.Whywillthisal-gorithmfavorI/O-boundprogramsandyetnotpermanentlystarveCPU-boundprograms?Answer:ItwillfavortheI/O-boundprogramsbecauseoftherelativelyshortCPUburstrequestbythem;however,theCPU-boundprogramswillnotstarvebecausetheI/O-boundprogramswillrelinquishtheCPUrelativelyoftentodotheirI/O.6.10Explainthedifferencesinthedegreetowhichthefollowingschedulingalgorithmsdis-criminateinfavorofshortprocesses:a.FCFSb.RRc.MultilevelfeedbackqueuesAnswer:a.FCFSdiscriminatesagainstshortjobssinceanyshortjobsarrivingafterlongjobswillhavealongerwaitingtime.b.RRtreatsalljobsequally(givingthemequalburstsofCPUtime)soshortjobswillbeabletoleavethesystemfastersincetheywillfinishfirst.c.MultilevelfeedbackqueuesworksimilartotheRRalgorithmtheydiscriminatefavorablytowardshortjobs.课后答案网www.hackshp.cn 课后答案网www.hackshp.cn Chapter7PROCESSSYNCHRONIZATIONChapter7isconcernedwiththetopicofprocesssynchronizationamongconcurrentlyexecutingprocesses.Concurrencyisgenerallyveryhardforstudentstodealwithcorrectly,andsowehavetriedtointroduceitanditsproblemswiththeclassicprocesscoordinationproblems:mutualexclusion,bounded-buffer,readers/writers,andsoon.Anunderstandingoftheseproblemsandtheirsolutionsispartofcurrentoperating-systemtheoryanddevelopment.Wefirstusesemaphoresandmonitorstointroducesynchronizationtechniques.Next,Javasynchronizationisintroducedtofurtherdemonstratealanguage-basedsynchronizationtech-课后答案网nique.AnswerstoExercises7.1Whatisthemeaningofthetermwww.hackshp.cnbusywaiting?Whatotherkindsofwaitingarethereinanoperatingsystem?Canbusywaitingbeavoidedaltogether?Explainyouranswer.Answer:Noanswer.7.2Explainwhyspinlocksarenotappropriateforuniprocessorsystemsyetmaybesuitableformultiprocessorsystems.Answer:Noanswer.7.3Provethat,inthebakeryalgorithm(Section7.2),thefollowingpropertyholds:IfPiisinitscriticalsectionandPk(k6=i)hasalreadychosenitsnumber[k]6=0,then(number[i],i)<(number[k],k).Answer:Noanswer.7.4Thefirstknowncorrectsoftwaresolutiontothecritical-sectionproblemfortwothreadswasdevelopedbyDekker;itisshowninFigure7.27.Thetwothreads,T0andT1,coordinateactivitysharinganobjectofclassDekker.Showthatthealgorithmsatisfiesallthreerequirementsforthecritical-sectionproblem.Answer:Noanswer.25 26Chapter7ProcessSynchronization7.5Thefirstknowncorrectsoftwaresolutiontothecritical-sectionproblemfornprocesseswithalowerboundonwaitingofn;1turnswaspresentedbyEisenbergandMcGuire.Theprocessessharethefollowingvariables:enumpstatefidle,wantin,incsg;pstateflag[n];intturn;Alltheelementsofflagareinitiallyidle;theinitialvalueofturnisimmaterial(between0andn-1).ThestructureofprocessPiisshowninFig-ure7.28.Provethatthealgorithmsatisfiesallthreerequirementsforthecritical-sectionproblem.Answer:Noanswer.7.6InSection7.3,wementionedthatdisablinginterruptsfrequentlycanaf-fectthesystem"sclock.Explainwhyitcan,andhowsucheffectscanbeminimized.Answer:Noanswer.7.7Showthat,ifthewaitandsignaloperationsarenotexecutedatomically,thenmutualexclusionmaybeviolated.Answer:Noanswer.7.8TheSleeping-BarberProblem.Abarbershopconsistsofawaitingroomwithnchairsandthebarberroomcontainingthebarberchair.Iftherearenocustomerstobeserved,thebarbergoestosleep.Ifacustomerentersthebarbershopandallchairs课后答案网areoccupied,thenthecustomerleavestheshop.Ifthebarberisbusybutchairsareavailable,thenthecustomersitsinoneofthefreechairs.Ifthebarberisasleep,thecustomerwakesupthebarber.Writeaprogramtocoordinatethebarberandthecustomers.Answer:PleaserefertothesupportingWebsiteforsourcecodesolution.7.9TheCigarette-SmokersProblem.Considerasystemwiththreesmokerprocessesandoneagentprocess.www.hackshp.cnEachsmokercontinuouslyrollsacigaretteandthensmokesit.Buttorollandsmokeacigarette,thesmokerneedsthreein-gredients:tobacco,paper,andmatches.Oneofthesmokerprocesseshaspaper,anotherhastobacco,andthethirdhasmatches.Theagenthasaninfinitesupplyofallthreematerials.Theagentplacestwoofthein-gredientsonthetable.Thesmokerwhohastheremainingingredientthenmakesandsmokesacigarette,signalingtheagentoncompletion.Theagentthenputsoutanothertwoofthethreeingredients,andthecyclerepeats.Writeaprogramtosynchronizetheagentandthesmokers.Answer:PleaserefertothesupportingWebsiteforsourcecodesolution.7.10Demonstratethatmonitors,conditionalcriticalregions,andsemaphoresareallequivalent,insofarasthesametypesofsynchronizationproblemscanbeimplementedwiththem.Answer:Noanswer.7.11Writeabounded-buffermonitorinwhichthebuffers(portions)areembed-dedwithinthemonitoritself.Answer:Noanswer. AnswerstoExercises277.12Thestrictmutualexclusionwithinamonitormakesthebounded-buffermon-itorofExercise7.11mainlysuitableforsmallportions.a.Explainwhythisassertionistrue.b.Designanewschemethatissuitableforlargerportions.Answer:Noanswer.7.13Supposethatthesignalstatementcanappearasonlythelaststatementinamonitorprocedure.SuggesthowtheimplementationdescribedinSection7.7canbesimplified.Answer:Noanswer.7.14ConsiderasystemconsistingofprocessesP1,P2,...,Pn,eachofwhichhasauniqueprioritynumber.Writeamonitorthatallocatesthreeidenticallineprinterstotheseprocesses,usingtheprioritynumbersfordecidingtheorderofallocation.Answer:Noanswer.7.15Afileistobesharedamongdifferentprocesses,eachofwhichhasauniquenumber.Thefilecanbeaccessedsimultaneouslybyseveralprocesses,sub-jecttothefollowingconstraint:Thesumofalluniquenumbersassoci-atedwithalltheprocessescurrentlyaccessingthefilemustbelessthann.Writeamonitortocoordinateaccesstothefile.Answer:Noanswer.7.16Supposethatwereplacethewaitandsignaloperationsofmonitorswithasingleconstructawait(B),课后答案网whereBisageneralBooleanexpressionthatcausestheprocessexecutingittowaituntilBbecomestrue.a.Writeamonitorusingthisschemetoimplementthereaders--writersprob-lem.b.Explainwhy,www.hackshp.cningeneral,thisconstructcannotbeimplementedefficiently.c.Whatrestrictionsneedtobeputontheawaitstatementsothatitcanbeimplementedefficiently?(Hint:RestrictthegeneralityofB;seekessels[1977].)Answer:Noanswer.7.17Writeamonitorthatimplementsanalarmclockthatenablesacallingprogramtodelayitselfforaspecifiednumberoftimeunits(ticks).Youmayas-sumetheexistenceofarealhardwareclockthatinvokesaproceduretickinyourmonitoratregularintervals.Answer:Noanswer.7.18WhydoesSolaris2implementmultiplelockingmechanisms?Underwhatcir-cumstancesdoesitusespinlocks,semaphores,adaptivemutexes,conditionalvariables,andreaders--writerslocks?Whydoesituseeachmechanism?Whatisthepurposeofturnstiles?Answer:Solaris2providesdifferentlockingmechanismsdependingontheapplicationdeveloper"sneeds.Spinlocksareusefulformultiprocessorsys-temswhereathreadcanruninabusy-loop(forashortperiodoftime)rather 28Chapter7ProcessSynchronizationthanincurringtheoverheadofbeingputinasleepqueue.Mutexesareuse-fulforlockingresources.Solaris2usesadaptivemutexes,meaningthatthemutexisimplementedwithaspinlockonmultiprocessormachines.Semaphoresandconditionvariablesaremoreappropriatetoolsforsynchronizationwhenaresourcemustbeheldforalongperiodoftimeforspinningisineffi-cientforalongduration.Readers/writerslocksareusefulwhenreadersandwritersbothneedaccesstoaresource,butthereadersaremoreac-tiveandperformancecanbegainednotusingexclusiveaccesslocks.So-laris2usesturnstilestoorderthelistofthreadswaitingtoacquireei-theranadaptivemutexorareader--writerlock.7.19WhydoSolaris2andWindows2000usespinlocksasasynchronizationmech-anismononlymultiprocessorsystemsandnotonuniprocessorsystems?Answer:Noanswer.7.20Explainthedifferences,intermsofcost,amongthethreestoragetypes:volatile,nonvolatile,andstable.Answer:Noanswer.7.21Explainthepurposeofthecheckpointmechanism.Howoftenshouldcheck-pointsbeperformed?Howdoesthefrequencyofcheckpointsaffect:Systemperformancewhennofailureoccurs?Thetimeittakestorecoverfromasystemcrash?Thetimeittakestorecoverfromadiskcrash?Answer:Noanswer.课后答案网7.22Explaintheconceptoftransactionatomicity.Answer:Noanswer.7.23Showthatthetwo-phaselockingprotocolensuresconflictserializability.Answer:Noanswer.7.24Showthatsomescheduleswww.hackshp.cnarepossibleunderthetwo-phaselockingproto-colbutnotpossibleunderthetimestampprotocol,andviceversa.Answer:Noanswer. Chapter8DEADLOCKSDeadlockisaproblemthatcanonlyariseinasystemwithmultipleactiveasynchronouspro-cesses.Itisimportantthatthestudentslearnthethreebasicapproachestodeadlock:prevention,avoidance,anddetection(althoughthetermspreventionandavoidanceareeasytoconfuse).Itcanbeusefultoposeadeadlockprobleminhumantermsandaskwhyhumansystemsneverdeadlock.Canthestudentstransferthisunderstandingofhumansystemstocomputersystems?Projectscaninvolvesimulation:createalistofjobsconsistingofrequestsandreleasesof课后答案网resources(singletypeormultipletypes).Askthestudentstoallocatetheresourcestopreventdeadlock.ThisbasicallyinvolvesprogrammingtheBankersAlgorithm.ThesurveypaperbyCoffman,Elphick,andShoshani[1971]isgoodsupplementalreading,butyoumightalsoconsiderhavingthestudentsgobacktothepapersbyHavender[1968],Habermann[1969],andHolt[1971a].ThelasttwowerepublishedinCACMandsoshouldbereadilyavailable.www.hackshp.cnAnswerstoExercises8.1Listthreeexamplesofdeadlocksthatarenotrelatedtoacomputer-systemenvironment.Answer:Twocarscrossingasingle-lanebridgefromoppositedirections.Apersongoingdownaladderwhileanotherpersonisclimbinguptheladder.Twotrainstravelingtowardeachotheronthesametrack.8.2Isitpossibletohaveadeadlockinvolvingonlyonesingleprocess?Explainyouranswer.Answer:No.Thisfollowsdirectlyfromthehold-and-waitcondition.8.3Peoplehavesaidthatproperspoolingwouldeliminatedeadlocks.Certainly,iteliminatesfromcontentioncardreaders,plotters,printers,andsoon.Itisevenpossibletospooltapes(calledstagingthem),whichwouldleavetheresourcesofCPUtime,memory,anddiskspace.Isitpossibletohaveadeadlockinvolvingtheseresources?Ifitis,howcould29 30Chapter8Deadlockssuchadeadlockoccur?Ifitisnot,whynot?Whatdeadlockschemewouldseembesttoeliminatethesedeadlocks(ifanyarepossible),orwhatconditionisviolated(iftheyarenotpossible)?Answer:Noanswer.8.4ConsiderthetrafficdeadlockdepictedinFigure8.11.a.Showthatthefournecessaryconditionsfordeadlockindeedholdinthisexample.b.Stateasimplerulethatwillavoiddeadlocksinthissystem.Answer:Noanswer.8.5Supposethatasystemisinanunsafestate.Showthatitispossiblefortheprocessestocompletetheirexecutionwithoutenteringadeadlockstate.Answer:Noanswer.Inarealcomputersystem,neithertheresourcesavailablenorthedemandsofprocessesforresourcesareconsistentoverlongperiods(months).Resourcesbreakorarereplaced,newprocessescomeandgo,newresourcesareboughtandaddedtothesystem.Ifdeadlockiscontrolledbythebankersalgorithm,whichofthefollowingchangescanbemadesafely(withoutintroducingthepossibilityofdeadlock),andunderwhatcircumstances?a.IncreaseAvailable(newresourcesadded)b.DecreaseAvailable(resourcepermanentlyremovedfromsystem)c.IncreaseMaxforoneprocess(theprocessneedsmoreresourcesthanallowed,itmaywantmore)d.DecreaseMaxforoneprocess(theprocessdecidesitdoesnotneedthatmanyre-sources)课后答案网e.Increasethenumberofprocessesf.DecreasethenumberofprocessesAnswer:Noanswer.8.6ProvethatthesafetyalgorithmpresentedinSection8.5.3requiresanorderofm2www.hackshp.cnnop-erations.Answer:Noanswer.8.7Considerasystemconsistingoffourresourcesofthesametypethataresharedbythreeprocesses,eachofwhichneedsatmosttworesources.Showthatthesystemisdeadlock-free.Answer:Supposethesystemisdeadlocked.Thisimpliesthateachprocessisholdingoneresourceandiswaitingforonemore.Sincetherearethreeprocessesandfourresources,oneprocessmustbeabletoobtaintworesources.Thisprocessrequiresnomoreresourcesand,thereforeitwillreturnitsresourceswhendone.8.8Considerasystemconsistingofmresourcesofthesametype,beingsharedbynprocesses.Resourcescanberequestedandreleasedbyprocessesonlyoneatatime.Showthatthesystemisdeadlock-freeifthefollowingtwoconditionshold:a.Themaximumneedofeachprocessisbetween1andmresourcesb.Thesumofallmaximumneedsislessthanm+nAnswer:UsingtheterminologyofSection7.6.2,wehave: AnswerstoExercises31a.PnMaxi=1ii)?Answer:DjisasubsetofDi.87 88Chapter18Protection18.4Considerasysteminwhich“computergames”canbeplayedbystudentsonlybetween10P.M.and6A.M.,byfacultymembersbetween5P.M.and8A.M.,andbythecomputercenterstaffatalltimes.Suggestaschemeforimplementingthispolicyefficiently.Answer:Setupadynamicprotectionstructurethatchangesthesetofresourcesavailablewithrespecttothetimeallottedtothethreecategoriesofusers.Astimechanges,sodoesthedomainofuserseligibletoplaythecomputergames.Whenthetimecomesthatauserseligibilityisover,arevocationprocessmustoccur.Revocationcouldbeimmediate,selective(sincethecomputerstaffmayaccessitatanyhour),total,andtemporary(sincerightstoaccesswillbegivenbacklaterintheday).18.5TheRC4000system(andothersystems)havedefinedatreeofprocesses(calledaprocesstree)suchthatallthedescendantsofaprocessaregivenresources(objects)andaccessrightsbytheirancestorsonly.Thus,adescendantcanneverhavetheabilitytodoany-thingthatitsancestorscannotdo.Therootofthetreeistheoperatingsystem,whichhastheabilitytodoanything.Assumethesetofaccessrightswasrepresentedbyanaccessmatrix,A.A(x,y)definestheaccessrightsofprocessxtoobjecty.Ifxisadescendantofz,whatistherelationshipbetweenA(x,y)andA(z,y)foranarbitraryobjecty?Answer:A(x,y)isasubsetofA(z,y).18.6Whathardwarefeaturesareneededforefficientcapabilitymanipulation?Canthesebeusedformemoryprotection?Answer:Noanswer.18.7Consideracomputingenvironmentwhereauniquenumberisassociatedwitheachpro-cessandeachobjectinthesystem.Supposethatweallowaprocesswithnumberntoaccessanobjectwithnumbermonlyifn>m.Whattypeofprotectionstructuredowehave?课后答案网Answer:Hierarchicalstructure.18.8Whatprotectionproblemsmayariseifasharedstackisusedforparameterpassing?Answer:Noanswer.18.9Consideracomputingenvironmentwhereaprocessisgiventheprivilegeofaccessinganobjectonlyntimes.Suggestaschemeforimplementingthispolicy.www.hackshp.cnAnswer:Addanintegercounterwiththecapability.18.10Ifalltheaccessrightstoanobjectaredeleted,theobjectcannolongerbeaccessed.Atthispoint,theobjectshouldalsobedeleted,andthespaceitoccupiesshouldbereturnedtothesystem.Suggestanefficientimplementationofthisscheme.Answer:Referencecounts.18.11Whatistheneed-to-knowprinciple?Whyisitimportantforaprotectionsystemtoadheretothisprinciple?Answer:Aprocessmayaccessatanytimethoseresourcesthatithasbeenauthorizedtoaccessandarerequiredcurrentlytocompleteitstask.Itisimportantinthatitlimitstheamountofdamageafaultyprocesscancauseinasystem.18.12WhyisitdifficulttoprotectasysteminwhichusersareallowedtodotheirownI/O?Answer:Noanswer.18.13Capabilitylistsareusuallykeptwithintheaddressspaceoftheuser.Howdoesthesys-temensurethattheusercannotmodifythecontentsofthelist?Answer:Noanswer. AnswerstoExercises8918.14DescribehowtheJavaprotectionmodelwouldbesacrificedifaJavaprogramwereal-lowedtodirectlyaltertheannotationsofitsstackframe.Answer:Noanswer.课后答案网www.hackshp.cn 课后答案网www.hackshp.cn Chapter19SECURITYTheinformationstoredinthesystem(bothdataandcode),aswellasthephysicalresourcesofthecomputersystem,needtobeprotectedfromunauthorizedaccess,maliciousdestructionoralteration,andaccidentalintroductionofinconsistency.Inthischapter,weexaminethewaysinwhichinformationmaybemisusedorintentionallymadeinconsistent.Wethenpresentmech-anismstoguardagainstthisoccurrence.课后答案网AnswerstoExercises19.1Apasswordmaybecomeknowntootherusersinavarietyofways.Isthereasimplemethodfordetectingthatsuchaneventhasoccurred?Explainyouranswer.Answer:Wheneverauserlogsin,thesystemprintsthelasttimethatuserwasloggedonthesystem.www.hackshp.cn19.2Thelistofallpasswordsiskeptwithintheoperatingsystem.Thus,ifausermanagestoreadthislist,passwordprotectionisnolongerprovided.Suggestaschemethatwillavoidthisproblem.(Hint:Usedifferentinternalandexternalrepresentations.)Answer:Encryptthepasswordsinternallysothattheycanonlybeaccessedincodedform.Theonlypersonwithaccessorknowledgeofdecodingshouldbethesystemoper-ator.19.3AnexperimentaladditiontoUNIXallowsausertoconnectawatchdogprogramtoafile,suchthatthewatchdogisinvokedwheneveraprogramrequestsaccesstothefile.Thewatchdogtheneithergrantsordeniesaccesstothefile.Discusstheprosandconsofusingwatchdogsforsecurity.Answer:Noanswer.19.4TheUNIXprogram,COPS,scansagivensystemforpossiblesecurityholesandalertstheusertopossibleproblems.Whatarethepotentialhazardsofusingsuchasystemforsecurity?Howcantheseproblemsbelimitedoreliminated?Answer:TheCOPSprogramitselfcouldbemodifiedbyanintrudertodisablesomeofitsfeaturesoreventotakeadvantageofitsfeaturestocreatenewsecurityflaws.Even91 92Chapter19SecurityifCOPSisnotcracked,itispossibleforanintrudertogainacopyofCOPS,studyit,andlocatesecuritybreacheswhichCOPSdoesnotdetect.ThenthatintrudercouldpreyonsystemsinwhichthemanagementdependsonCOPSforsecurity(thinkingitisprovidingsecurity),whenallCOPSisprovidingismanagementcomplacency.COPScouldbestoredonareadonlymediaorfilesystemtoavoiditsmodification.Itcouldonlybeprovidedtobonafidesystemsmanagerstopreventitfromfallingintothewronghands.Neitheroftheseisafoolproofsolution,however.19.5DiscusswaysbywhichmanagersofsystemsconnectedtotheInternetcouldhavelimitedoreliminatedthedamagedonebytheworm.Whatarethedrawbacksofmakingsuchchangestothewayinwhichthesystemoperates?Answer:“Firewalls”canbeerectedbetweensystemsandtheInternet.Thesesystemsfilterthepacketsmovingfromonesideofthemtotheother,assuringthatonlyvalidpack-etsownedbyauthorizedusersareallowedtoaccesstheprotectsystems.Suchfirewallsusuallymakeuseofthesystemslessconvenient(andnetworkconnectionslessefficient).19.6ArguefororagainstthesentencehandeddownagainstRobertMorris,Jr.,forhiscreationandexecutionoftheInternetworm.Answer:Noanswer.19.7Makealistofsecurityconcernsforacomputersystemforabank.Foreachitemonyourlist,statewhetherthisconcernrelatestophysicalsecurity,humansecurity,oroperatingsystemsecurity.Answer:Inaprotectedlocation,wellguarded:physical,human.Networktamperproof:physical,human,operatingsystem.Modemaccesseliminatedorlimited:physical,human.Unauthorizeddatatransferspreventedorlogged:human,operatingsystem.Backupmediaprotectedandguarded:physical,human.课后答案网Programmers,dataentrypersonnel,trustworthy:human.19.8Whataretwoadvantagesofencryptingdatastoredinthecomputersystem?Answer:Encrypteddataareguardedbytheoperatingsystemsprotectionfacilities,aswellasapasswordthatisneededtodecryptthem.Twokeysarebetterthanonewhenitcomestosecurity.www.hackshp.cn Chapter20THELINUXSYSTEMChapterAdiscussedtheinternalsofthe4.3BSDoperatingsystemindetail.BSDisjustoneoftheUNIX-likesystems.LinuxisanotherUNIX-likesystemthathasgainedpopularityinrecentyears.Inthischapter,welookatthehistoryanddevelopmentofLinux,andcovertheuserandprogrammerinterfacesthatLinuxpresentsinterfacesthatoweagreatdealtotheUNIXtradition.WealsodiscusstheinternalmethodsbywhichLinuximplementstheseinterfaces.However,sinceLinuxhasbeendesignedtorunasmanystandardUNIXapplicationsaspossible,ithasmuchincommonwithexisting课后答案网UNIXimplementations.WedonotduplicatethebasicdescriptionofUNIXgiveninthepreviouschapter.Linuxisarapidlyevolvingoperatingsystem.ThischapterdescribesspecificallytheLinux2.0kernel,releasedinJune1996.AnswerstoExerciseswww.hackshp.cn20.1Linuxrunsonavarietyofhardwareplatforms.WhatstepsmusttheLinuxdeveloperstaketoensurethatthesystemisportabletodifferentprocessorsandmemory-managementarchitectures,andtominimizetheamountofarchitecture-specifickernelcode?Answer:Theorganizationofarchitecture-dependentandarchitecture-independentcodeintheLinuxkernelisdesignedtosatisfytwodesigngoals:tokeepasmuchcodeaspossiblecommonbetweenarchitecturesandtoprovideacleanwayofdefiningarchitecture-specificpropertiesandcode.Thesolutionmustofcoursebeconsistentwiththeoverridingaimsofcodemaintainabilityandperformance.Therearedifferentlevelsofarchitecturedependenceinthekernel,anddifferenttech-niquesareappropriateineachcasetocomplywiththedesignrequirements.Theselevelsinclude:CPUwordsizeandendiannessTheseareissuesthataffecttheportabilityofallsoftwarewritteninC,butespeciallysoforanoperatingsystem,wherethesizeandalignmentofdatamustbecarefullyarranged.CPUprocessarchitectureLinuxreliesonmanyformsofhardwaresupportforitspro-cessandmemorymanagement.Differentprocessorshavetheirownmechanismsfor93 94Chapter20TheLinuxSystemchangingbetweenprotectiondomains(e.g.,enteringkernelmodefromusermode),reschedulingprocesses,managingvirtualmemory,andhandlingincominginter-rupts.TheLinuxkernelsourcecodeisorganizedsoastoallowasmuchofthekernelaspos-sibletobeindependentofthedetailsofthesearchitecture-specificfeatures.Tothisend,thekernelkeepsnotonebuttwoseparatesubdirectoryhierarchiesforeachhardwarear-chitecture.Onecontainsthecodethatisappropriateonlyforthatarchitecture,includingsuchfunctionalityasthesystemcallinterfaceandlow-levelinterruptmanagementcode.Thesecondarchitecture-specificdirectorytreecontainsCheaderfilesthataredescriptiveofthearchitecture.Theseheaderfilescontaintypedefinitionsandmacrosdesignedtohidethedifferencesbetweenarchitectures.Theyprovidestandardtypesforobtainingwordsofagivenlength,macroconstantsdefiningsuchthingsasthearchitecturewordsizeorpagesize,andfunctionmacrostoperformcommontaskssuchasconvertingawordtoagivenbyte-orderordoingstandardmanipulationstoapagetableentry.Giventhesetwoarchitecture-specificsubdirectorytrees,alargeportionoftheLinuxker-nelcanbemadeportablebetweenarchitectures.Anattentiontodetailisrequired:whena32bitintegerisrequired,theprogrammermustusetheexplicitint32typeratherthanas-sumethananintisagivensize,forexample.However,aslongasthearchitecture-specificheaderfilesareused,thenmostprocessandpage-tablemanipulationcanbeperformedusingcommoncodebetweenthearchitectures.Codethatdefinitelycannotbesharediskeptsafelydetachedfromthemaincommonkernelcode.20.2Dynamicallyloadablekernelmodulesgiveflexibilitywhendriversareaddedtoasystem,butdotheyhavedisadvantagestoo?Underwhatcircumstanceswouldakernelbecom-piledintoasinglebinaryfile,andwhenwoulditbebettertokeepitsplitintomodules?课后答案网Explainyouranswer.Answer:Therearetwoprincipaldrawbackswiththeuseofmodules.Thefirstissize:modulemanagementconsumesunpageablekernelmemory,andabasickernelwithanumberofmodulesloadedwillconsumemorememorythananequivalentkernelwiththedriverscompiledintothekernelimageitself.Thiscanbeaverysignificantissueonmachineswithlimitedphysicalmemory.Theseconddrawbackisthatmodulescanincreasethecomplexityofthekernelbootstrapwww.hackshp.cnprocess.Itishardtoloadupasetofmodulesfromdiskifthedriverneededtoaccessthatdiskasitselfamodulethatneedstobeloaded.Asaresult,managingthekernelboot-strapwithmodulescanrequireextraworkonthepartoftheadministrator:themodulesrequiredtobootstrapneedtobeplacedintoaramdiskimagethatisloadedalongsidetheinitialkernelimagewhenthesystemisinitialized.Incertaincasesitisbettertouseamodularkernel,andinothercasesitisbettertouseakernelwithitsdevicedriversprelinked.Whereminimizingthesizeofthekernelisim-portant,thechoicewilldependonhowoftenthevariousdevicedriversareused.Iftheyareinconstantuse,thenmodulesareunsuitable.Thisisespeciallytruewheredriversareneededforthebootprocessitself.Ontheotherhand,ifsomedriversarenotalwaysneeded,thenthemodulemechanismallowsthosedriverstobeloadedandunloadedondemand,potentiallyofferinganetsavinginphysicalmemory.Whereakernelistobebuiltwhichmustbeusableonalargevarietyofverydifferentmachines,thenbuildingitwithmodulesisclearlypreferabletousingasinglekernelwithdozensofunnecessarydriversconsumingmemory.Thisisparticularlythecaseforcommerciallydistributedkernels,wheresupportingthewidestvarietyofhardwareinthesimplestmannerpossibleisapriority. AnswerstoExercises95However,ifakernelisbeingbuiltforasinglemachinewhoseconfigurationisknowninadvance,thencompilingandusingmodulesmaysimplybeanunnecessarycomplexity.Incaseslikethis,theuseofmodulesmaywellbeamatteroftaste.20.3Multithreadingisacommonlyusedprogrammingtechnique.Describethreedifferentwaysthatthreadscouldbeimplemented.ExplainhowthesewayscomparetotheLinuxclonemechanism.Whenmighteachalternativemechanismbebetterorworsethanusingclones?Answer:Threadimplementationscanbebroadlyclassifiedintotwogroups:kernel-basedthreadsanduser-modethreads.User-modethreadpackagesrelyonsomekernelsupport-theymayrequiretimerinterruptfacilities,forexample-buttheschedulingbe-tweenthreadsisnotperformedbythekernelbutbysomelibraryofuser-modecode.Multiplethreadsinsuchanimplementationappeartotheoperatingsystemasasingleexecutioncontext.Whenthemultithreadedprocessisrunning,itdecidesforitselfwhichofitsthreadstoexecute,usingnon-localjumpstoswitchbetweenthreadsaccordingtoitsownpreemptiveornon-preemptiveschedulingrules.Alternatively,theoperatingsystemkernelmayprovidesupportforthreadsitself.Inthiscase,thethreadsmaybeimplementedasseparateprocessesthathappentoshareacom-pleteorpartialcommonaddressspace,ortheymaybeimplementedasseparateexecu-tioncontextswithinasingleprocess.Whicheverwaythethreadsareorganized,theyappearasfullyindependentexecutioncontextstotheapplication.Hybridimplementationsarealsopossible,wherealargenumberofthreadsaremadeavailabletotheapplicationusingasmallernumberofkernelthreads.Runnableuserthreadsarerunbythefirstavailablekernelthread.InLinux,threadsareimplementedwithinthekernelbyaclonemechanismthatcreatesanewprocesswithinthesamevirtualaddressspaceastheparentprocess.Unlikesome课后答案网kernel-basedthreadpackages,theLinuxkerneldoesnotmakeanydistinctionbetweenthreadsandprocesses:athreadissimplyaprocessthatdidnotcreateanewvirtualaddressspacewhenitwasinitialized.Themainadvantageofimplementingthreadsinthekernelratherthaninauser-modelibraryarethat:kernelthreadedsystemscantakeadvantageofmultipleprocessorsiftheyareavail-www.hackshp.cnable;andifonethreadblocksinakernelserviceroutine(forexample,asystemcallorpagefault),otherthreadsarestillabletorun.Alesseradvantageistheabilitytoassigndifferentsecurityattributestoeachthread.User-modeimplementationsdonothavetheseadvantages.Becausesuchimplementa-tionsrunentirelywithinasinglekernelexecutioncontext,onlyonethreadcaneverberunningatonce,evenifmultipleCPUsareavailable.Forthesamereason,ifonethreadentersasystemcall,nootherthreadscanrununtilthatsystemcallcompletes.Asare-sult,onethreaddoingablockingdiskreadwillholdupeverythreadintheapplication.However,user-modeimplementationsdohavetheirownadvantages.Themostobviousisperformance:invokingthekernelsownschedulertoswitchbetweenthreadsinvolvesenteringanewprotectiondomainastheCPUswitchestokernelmode,whereasswitch-ingbetweenthreadsinuser-modecanbeachievedsimplybysavingandrestoringthemainCPUregisters.User-modethreadsmayalsoconsumelesssystemmemory:mostUNIXsystemswillreserveatleastafullpageforakernelstackforeachkernelthread,andthisstackmaynotbepageable. 96Chapter20TheLinuxSystemThehybridapproach,implementingmultipleuserthreadsoverasmallernumberofker-nelthreads,allowsabalancebetweenthesetradeoffstobeachieved.Thekernelthreadswillallowmultiplethreadstobeinblockingkernelcallsatonceandwillpermitrun-ningonmultipleCPUs,anduser-modethreadswitchingcanoccurwithineachkernelthreadtoperformlightweightthreadingwithouttheoverheadsofhavingtoomanyker-nelthreads.Thedownsideofthisapproachiscomplexity:givingcontroloverthetradeoffcomplicatesthethreadlibrarysuserinterface.20.4Whataretheextracostsincurredbythecreationandschedulingofaprocess,ascomparedtothecostofaclonedthread?Answer:InLinux,creationofathreadinvolvesonlythecreationofsomeverysimpledatastructurestodescribethenewthread.Spacemustbereservedforthenewthreadsexecutioncontextitssavedregisters,itskernelstackpageanddynamicinformationsuchasitssecurityprofileandsignalstatebutnonewvirtualaddressspaceiscreated.Creatingthisnewvirtualaddressspaceisthemostexpensivepartofthecreationofanewprocess.Theentirepagetableoftheparentprocessmustbecopied,witheachpagebeingexaminedsothatcopy-on-writesemanticscanbeachievedandsothatreferencecountstophysicalpagescanbeupdated.Theparentprocesssvirtualmemoryisalsoaffectedbytheprocesscreation:anyprivateread/writepagesownedbytheparentmustbemarkedread-onlysothatcopy-on-writecanhappen(copy-on-writereliesonapagefaultbeinggeneratedwhenawritetothepageoccurs).Schedulingofthreadsandprocessesalsodiffersinthisrespect.Thedecisionalgorithmperformedwhendecidingwhatprocesstorunnextisthesameregardlessofwhethertheprocessisafullyindependentprocessorjustathread,buttheactionofcontext-switchingtoaseparateprocessismuchmorecostlythanswitchingtoathread.AprocessrequiresthattheCPUsvirtualmemorycontrolregistersbeupdatedtopointtothenewvirtualaddressspacespagetables.课后答案网Inbothcasescreationofaprocessorcontextswitchingbetweenprocessestheextravirtualmemoryoperationshaveasignificantcost.OnmanyCPUs,changingpagetablesorswappingbetweenpagetablesisnotcheap:allorpartofthevirtualaddresstranslationlook-asidebuffersintheCPUmustbepurgedwhenthepagetablesarechanged.Thesecostsarenotincurredwhencreatingorschedulingbetweenthreads.20.5TheLinuxschedulerimplementswww.hackshp.cnsoftreal-timescheduling.Whatfeaturesaremissingthatarenecessaryforsomereal-timeprogrammingtasks?Howmighttheybeaddedtothekernel?Answer:Linuxssoftreal-timeschedulingprovidesorderingguaranteesconcerningtheprioritiesofrunnableprocesses:real-timeprocesseswillalwaysbegivenahigherprioritybytheschedulerthannormaltime-sharingprocesses,andareal-timeprocesswillneverbeinterruptedbyanotherprocesswithalowerreal-timepriority.However,theLinuxkerneldoesnotsupporthardreal-timefunctionality.Thatis,whenaprocessisexecutingakernelserviceroutine,thatroutinewillalwaysexecutetocomple-tionunlessityieldscontrolbacktotheschedulereitherexplicitlyorimplicitly(bywaitingforsomeasynchronousevent).Thereisnosupportforpreemptiveschedulingofkernel-modeprocesses.Asaresult,anykernelsystemcallthatrunsforasignificantamountoftimewithoutreschedulingwillblockexecutionofanyreal-timeprocesses.Manyreal-timeapplicationsrequiresuchhardreal-timescheduling.Inparticular,theyoftenrequireguaranteedworst-caseresponsetimestoexternalevents.Toachievetheseguarantees,andtogiveuser-moderealtimeprocessesatruehigherprioritythankernel-modelower-priorityprocesses,itisnecessarytofindawaytoavoidhavingtowaitforlow-prioritykernelcallstocompletebeforeschedulingareal-timeprocess.Forexample, AnswerstoExercises97ifadevicedrivergeneratesaninterruptthatwakesupahigh-priorityreal-timeprocess,thenthekernelneedstobeabletoschedulethatprocessassoonaspossible,evenifsomeotherprocessisalreadyexecutinginkernelmode.Suchpreemptivereschedulingofkernel-moderoutinescomesatacost.Ifthekernelcannotrelyonnon-preemptiontoensureatomicupdatesofshareddatastructures,thenreadsoforupdatestothosestructuresmustbeprotectedbysomeother,finer-granularitylockingmechanism.Thisfine-grainedlockingofkernelresourcesisthemainrequirementforprovisionoftightschedulingguarantees.Manyotherkernelfeaturescouldbeaddedtosupportreal-timeprogramming.Deadline-basedschedulingcouldbeachievedbymakingmodificationstothescheduler.Prioriti-zationofIOoperationscouldbeimplementedintheblock-deviceIOrequestlayer.20.6TheLinuxkerneldoesnotallowpagingoutofkernelmemory.Whateffectdoesthisrestrictionhaveonthekernelsdesign?Whataretwoadvantagesandtwodisadvantagesofthisdesigndecision?Answer:TheprimaryimpactofdisallowingpagingofkernelmemoryinLinuxisthatthenon-preemptabilityofthekernelispreserved.Anyprocesstakingapagefault,whetherinkernelorinusermode,risksbeingrescheduledwhiletherequireddataispagedinfromdisk.Becausethekernelcanrelyonnotbeingrescheduledduringaccesstoitsprimarydatastructures,lockingrequirementstoprotecttheintegrityofthosedatastructuresareverygreatlysimplified.Althoughdesignsimplicityisabenefitinitself,italsoprovidesanimportantperformanceadvantageonuni-processormachinesduetothefactthatitisnotnecessarytodoadditionallockingonmostinternaldatastructures.Thereareanumberofdisadvantagestothelackofpageablekernelmemory,however.Firstofall,itimposesconstraintsontheamountofmemorythatthekernelcanuse.Itisunreasonabletokeepverylargedatastructuresinnon-pageablememory,sincethatrepresentsphysicalmemorythatabsolutelycannotbeusedforanythingelse.Thishas课后答案网twoimpacts:firstofall,thekernelmustprunebackmanyofitsinternaldatastructuresmanually,insteadofbeingabletorelyonasinglevirtualmemorymechanismtokeepphysicalmemoryusageundercontrol.Second,itmakesitinfeasibletoimplementcertainfeaturesthatrequirelargeamountsofvirtualmemoryinthekernel,suchasthe/tmp-filesystem(afastvirtualmemorybasedfile-systemfoundonsomeUNIXsystems).Notethatthecomplexityofmanagingpagefaultswhilerunningkernelcodeisnotanwww.hackshp.cnissuehere.TheLinuxkernelcodeisalreadyabletodealwithpagefaults:itneedstobeabletodealwithsystemcallswhoseargumentsreferenceusermemorywhichmaybepagedouttodisk.20.7InLinux,sharedlibrariesperformmanyoperationscentraltotheoperatingsystem.Whatistheadvantageofkeepingthisfunctionalityoutofthekernel?Arethereanydrawbacks?Explainyouranswer.Answer:Thereareanumberofreasonsforkeepingfunctionalityinsharedlibrariesratherthaninthekernelitself.Theseinclude:Reliability.Kernel-modeprogrammingisinherentlyhigherriskthanuser-modepro-gramming.Ifthekerneliscodedcorrectlysothatprotectionbetweenprocessesisenforced,thenanoccurrenceofabuginauser-modelibraryislikelytoaffectonlythecurrentlyexecutingprocess,whereasasimilarbuginthekernelcouldconceiv-ablybringdowntheentireoperatingsystem.Performance.Keepingasmuchfunctionalityaspossibleinuser-modesharedlibrarieshelpsperformanceintwoways.Firstofall,itreducesphysicalmemoryconsump-tion:kernelmemoryisnon-pageable,soeverykernelfunctionispermanentlyres- 98Chapter20TheLinuxSystemidentinphysicalmemory,butalibraryfunctioncanbepagedinfromdiskonde-mandanddoesnotneedtobephysicallypresentallofthetime.Althoughthelibraryfunctionmayberesidentinmanyprocessesatonce,pagesharingbythevirtualmemorysystemmeansthatatmostonceitisonlyloadedintophysicalmemory.Second,callingafunctioninaloadedlibraryisaveryfastoperation,butcallingakernelfunctionthroughakernelsystemservicecallismuchmoreexpensive.Enter-ingthekernelinvolveschangingtheCPUprotectiondomain,andonceinthekernel,alloftheargumentssuppliedbytheprocessmustbeverycarefullycheckedforcor-rectness:thekernelcannotaffordtomakeanyassumptionsaboutthevalidityoftheargumentspassedin,whereasalibraryfunctionmightreasonablydoso.Bothofthesefactorsmakecallingakernelfunctionmuchslowerthancallingthesamefunctioninalibrary.Manageability.Manydifferentsharedlibrariescanbeloadedbyanapplication.Ifnewfunctionalityisrequiredinarunningsystem,sharedlibrariestoprovidethatfunc-tionalitycanbeinstalledwithoutinterruptinganyalready-runningprocesses.Sim-ilarly,existingsharedlibrariescangenerallybeupgradedwithoutrequiringanysystemdowntime.Unprivilegeduserscancreatesharedlibrariestoberunbytheirownprograms.Alloftheseattributesmakesharedlibrariesgenerallyeasiertoman-agethankernelcode.Thereare,however,afewdisadvantagestohavingcodeinasharedlibrary.Thereareobviousexamplesofcodewhichiscompletelyunsuitableforimplementationinali-brary,includinglow-levelfunctionalitysuchasdevicedriversorfile-systems.Ingen-eral,servicessharedaroundtheentiresystemarebetterimplementedinthekerneliftheyareperformance-critical,sincethealternativerunningthesharedserviceinaseparateprocessandcommunicatingwithitthroughinterprocesscommunicationrequirestwocontextswitchesforeveryservicerequestedbyaprocess.Insomecases,itmaybeap-课后答案网propriatetoprototypeaserviceinuser-modebutimplementthefinalversionasakernelroutine.Securityisalsoanissue.Asharedlibraryrunswiththeprivilegesoftheprocesscallingthelibrary.Itcannotdirectlyaccessanyresourcesinaccessibletothecallingprocess,andthecallingprocesshasfullaccesstoallofthedatastructuresmaintainedbythesharedlibrary.Iftheservicebeingprovidedrequiresanyprivilegesoutsideofanormalprocesss,www.hackshp.cnorifthedatamanagedbythelibraryneedstobeprotectedfromnormaluserprocesses,thenlibrariesareinappropriateandaseparateserverprocess(ifperformancepermits)orakernelimplementationisrequired.20.8Whatarethreeadvantagesofdynamic(shared)linkageoflibrariescomparedtostaticlinkage?Whataretwocaseswherestaticlinkageispreferable.Answer:Theprimaryadvantagesofsharedlibrariesarethattheyreducethememoryanddiskspaceusedbyasystem,andtheyenhancemaintainability.Whensharedlibrariesarebeingusedbyallrunningprograms,thereisonlyoneinstanceofeachsystemlibraryroutineondisk,andatmostoneinstanceinphysicalmemory.Whenthelibraryinquestionisoneusedbymanyapplicationsandprograms,thenthediskandmemorysavingscanbequitesubstantial.Inaddition,thestartuptimeforrun-ningnewprogramscanbereduced,sincemanyofthecommonfunctionsneededbythatprogramarelikelytobealreadyloadedintophysicalmemory.Maintainabilityisalsoamajoradvantageofdynamiclinkageoverstatic.Ifallrunningprogramsuseasharedlibrarytoaccesstheirsystemlibraryroutines,thenupgradingthoseroutines,eithertoaddnewfunctionalityortofixbugs,canbedonesimplybyreplacingthatsharedlibrary.Thereisnoneedtorecompileorrelinkanyapplications; AnswerstoExercises99anyprogramsloadedaftertheupgradeiscompletewillautomaticallypickupthenewversionsofthelibraries.Thereareotheradvantagestoo.Aprogramthatusessharedlibrariescanoftenbeadaptedforspecificpurposessimplybyreplacingoneormoreofitslibraries,oreven(ifthesys-temallowsit,andmostUNIXsincludingLinuxdo)addinganewoneatruntime.Forexample,adebugginglibrarycanbesubstitutedforanormalonetotraceaprobleminanapplication.Sharedlibrariesalsoallowprogrambinariestobelinkedagainstcommercial,proprietarylibrarycodewithoutactuallyincludinganyofthatcodeintheprogramsfinalexecutablefile.ThisisimportantbecauseonmostUNIXsystems,manyofthestandardsharedlibrariesareproprietary,andlicensingissuesmaypreventincludingthatcodeinexecutablefilestobedistributedtothirdparties.Insomeplaces,however,staticlinkageisappropriate.Oneexampleisinrescueenvi-ronmentsforsystemadministrators.Ifasystemadministratormakesamistakewhileinstallinganynewlibraries,orifhardwaredevelopsproblems,itisquitepossiblefortheexistingsharedlibrariestobecomecorrupt.Asaresult,oftenabasicsetofrescueutilitiesarelinkedstatically,sothatthereisanopportunitytocorrectthefaultwithouthavingtorelyonthesharedlibrariesfunctioningcorrectly.Therearealsoperformanceadvantagesthatsometimesmakestaticlinkagepreferableinspecialcases.Forastart,dynamiclinkagedoesincreasethestartuptimeforaprogram,asthelinkingmustnowbedoneatrun-timeratherthanatcompile-time.Dynamiclink-agecanalsosometimesincreasethemaximumworkingsetsizeofaprogram(thetotalnumberofphysicalpagesofmemoryrequiredtoruntheprogram).Inasharedlibrary,theuserhasnocontroloverwhereinthelibrarybinaryfilethevariousfunctionsreside.Sincemostfunctionsdonotpreciselyfillafullpageorpagesofthelibrary,loadingafunctionwillusuallyresultinloadinginpartsofthesurroundingfunctions,too.Withstaticlinkage,absolutelynofunctionsthatarenotreferenced(directlyorindirectly)by课后答案网theapplicationneedtobeloadedintomemory.Otherissuessurroundingstaticlinkageincludeeaseofdistribution:itiseasiertodis-tributeanexecutablefilewithstaticlinkagethanwithdynamiclinkageifthedistributorisnotcertainwhethertherecipientwillhavethecorrectlibrariesinstalledinadvance.Theremayalsobecommercialrestrictionsagainstredistributingsomebinariesassharedlibraries.Forexample,thelicensefortheUNIXMotifgraphicalenvironmentallowsbinariesusingMotiftobedistributedfreelyaslongastheyarestaticallylinked,butthewww.hackshp.cnsharedlibrariesmaynotbeusedwithoutalicense.20.9Comparetheuseofnetworkingsocketswiththeuseofsharedmemoryasamechanismforcommunicatingdatabetweenprocessesonasinglecomputer.Whataretheadvan-tagesofeachmethod?Whenmighteachbepreferred?Answer:Usingnetworksocketsratherthansharedmemoryforlocalcommunicationhasanumberofadvantages.Themainadvantageisthatthesocketprogramminginterfacefeaturesarichsetofsynchronizationfeatures.Aprocesscaneasilydeterminewhennewdatahasarrivedonasocketconnection,howmuchdataispresent,andwhosentit.Processescanblockuntilnewdataarrivesonasocket,ortheycanrequestthatasignalbedeliveredwhendataarrives.Asocketalsomanagesseparateconnections.Aprocesswithasocketopenforreceivecanacceptmultipleconnectionstothatsocketandwillbetoldwhennewprocessestrytoconnectorwhenoldprocessesdroptheirconnections.Sharedmemoryoffersnoneofthesefeatures.Thereisnowayforaprocesstodeterminewhetheranotherprocesshasdeliveredorchangeddatainsharedmemoryotherthanbygoingtolookatthecontentsofthatmemory.Itisimpossibleforaprocesstoblockandrequestawakeupwhensharedmemoryisdelivered,andthereisnostandardmechanismforotherprocessestoestablishasharedmemorylinktoanexistingprocess. 100Chapter20TheLinuxSystemHowever,sharedmemoryhastheadvantagethatitisverymuchfasterthansocketcom-municationsinmanycases.Whendataissentoverasocket,itistypicallycopiedfrommemorytomemorymultipletimes.Sharedmemoryupdatesrequirenodatacopies:ifoneprocessupdatesadatastructureinsharedmemory,thatupdateisimmediatelyvis-ibletoallotherprocessessharingthatmemory.Sendingorreceivingdataoverasocketrequiresthatakernelsystemservicecallbemadetoinitiatethetransfer,butsharedmem-orycommunicationcanbeperformedentirelyinusermodewithnotransferofcontrolrequired.Socketcommunicationistypicallypreferredwhenconnectionmanagementisimportantorwhenthereisarequirementtosynchronizethesenderandreceiver.Forexample,serverprocesseswillusuallyestablishalisteningsockettowhichclientscanconnectwhentheywanttousethatservice.Oncethesocketisestablished,individualrequestsarealsosentusingthesocket,sothattheservercaneasilydeterminewhenanewrequestarrivesandwhoitarrivedfrom.Insomecases,however,sharedmemoryispreferred.Sharedmemoryisoftenabettersolutionwheneitherlargeamountsofdataaretobetransferredorwhentwoprocessesneedrandomaccesstoalargecommondataset.Inthiscase,however,thecommunicat-ingprocessmaystillneedanextramechanisminadditiontosharedmemorytoachievesynchronizationbetweenthemselves.TheXWindowSystem,agraphicaldisplayenvi-ronmentforUNIX,isagoodexampleofthis:mostgraphicrequestsaresentoversock-ets,butsharedmemoryisofferedasanadditionaltransportinspecialcaseswherelargebitmapsaretobedisplayedonthescreen.Inthiscase,arequesttodisplaythebitmapwillstillbesentoverthesocket,butthebulkdataofthebitmapitselfwillbesentviasharedmemory.20.10UNIXsystemsusedtousedisk-layoutoptimizationsbasedontherotationpositionofdiskdata,butmodernimplementations,includingLinux,simplyoptimizeforsequentialdata课后答案网access.Whydotheydoso?Ofwhathardwarecharacteristicsdoessequentialaccesstakeadvantage?Whyisrotationaloptimizationnolongersouseful?Answer:Theperformancecharacteristicsofdiskhardwarehaschangedsubstantiallyinrecentyears.Inparticular,manyenhancementshavebeenintroducedtoincreasethemaximumbandwidththatcanbeachievedonadisk.Inamodernsystem,therecanbealongpipelinebetweentheoperatingsystemandthedisksread-writehead.AdiskI/Owww.hackshp.cnrequesthastopassthroughthecomputerslocaldiskcontroller,overbuslogictothediskdriveitself,andtheninternallytothediskwherethereislikelytobeacomplexcontrollerthatcancachedataaccessesandpotentiallyoptimizetheorderofI/Orequests.Becauseofthiscomplexity,thetimetakenforoneI/Orequesttobeacknowledgedandforthenextrequesttobegeneratedandreceivedbythediskcanfarexceedtheamountoftimebetweenonedisksectorpassingundertheread-writeheadandthenextsectorheaderarriving.Inordertobeabletoefficientlyreadmultiplesectorsatonce,diskswillemployareadaheadcache.Whileonesectorisbeingpassedbacktothehostcomputer,thediskwillbebusyreadingthenextsectorsinanticipationofarequesttoreadthem.Ifreadrequestsstartarrivinginanorderthatbreaksthisreadaheadpipeline,performancewilldrop.Asaresult,performancebenefitssubstantiallyiftheoperatingsystemtriestokeepI/Orequestsinstrictsequentialorder.Asecondfeatureofmoderndisksisthattheirgeometrycanbeverycomplex.Thenumberofsectorspercylindercanvaryaccordingtothepositionofthecylinder:moredatacanbesqueezedintothelongertracksnearertheedgeofthediskthanatthecenterofthedisk.Foranoperatingsystemtooptimizetherotationalpositionofdataonsuchdisks,itwouldhavetohavecompleteunderstandingofthisgeometry,aswellasthetimingcharacteristicsofthediskanditscontroller.Ingeneral,onlythedisksinternallogiccan AnswerstoExercises101determinetheoptimalschedulingofI/Os,andthedisksgeometryislikelytodefeatanyattemptbytheoperatingsystemtoperformrotationaloptimizations.20.11TheLinuxsourcecodeisfreelyandwidelyavailableovertheInternetorfromCD-Romvendors.WhatthreeimplicationsdoesthisavailabilityhaveonthesecurityoftheLinuxsystem?Answer:Theopenavailabilityofanoperatingsystemssourcecodehasbothpositiveandnegativeimpactsonsecurity,anditisprobablyamistaketosaythatitisdefinitelyagoodthingorabadthing.Linuxssourcecodeisopentoscrutinybyboththegoodguysandthebadguys.Initsfavor,thishasresultedinthecodebeinginspectedbyalargenumberofpeoplewhoareconcernedaboutsecurityandwhohaveeliminatedanyvulnerabilitiestheyhavefound.Ontheotherhandisthesecuritythroughobscurityargument,whichstatesthatattack-ersjobsaremadeeasieriftheyhaveaccesstothesourcecodeofthesystemtheyaretryingtopenetrate.Bydenyingattackersinformationaboutasystem,thehopeisthatitwillbeharderforthoseattackerstofindandexploitanysecurityweaknessesthatmaybepresent.Inotherwords,opensourcecodeimpliesboththatsecurityweaknessescanbefoundandfixedfasterbytheLinuxcommunity,increasingthesecurityofthesystem;andthatattackerscanmoreeasilyfindanyweaknessesthatdoremaininLinux.Thereareotherimplicationsforsourcecodeavailability,however.Oneisthatifaweak-nessinLinuxisfoundandexploited,thenafixforthatproblemcanbecreatedanddis-tributedveryquickly.(Typically,securityproblemsinLinuxtendtohavefixesavailabletothepublicwithin24hoursoftheirdiscovery.)Anotheristhatifsecurityisamajorconcerntoparticularusers,thenitispossibleforthoseuserstoreviewthesourcecodetosatisfythemselvesofitslevelofsecurityortomakeanychangesthattheywishtoaddnewsecuritymeasures.课后答案网www.hackshp.cn 课后答案网www.hackshp.cn Chapter21WINDOWS2000TheWindows2000operatingsystemisdesignedtotakeadvantageofthemanyadvancesinprocessortechnology.AlthoughprimarilyrunontheIntelarchitecture,Windows2000wasde-signedtobeportableinordertotakeadvantageofwhateverpromisingtechnologieshappenedtocomealong.Keygoalsforthesystemincludedportability,security,POSIXcompliance,mul-tiprocessorsupport,extensibility,internationalsupport,andcompatibilitywithMS-DOSandMS-Windowsapplications.Windows2000issimilartoMachinthatitisamicro-kernelbasedoperatingsystemthatresultsinastablebaseoperatingsystemandallowsenhancementstobe课后答案网madetoonepartoftheoperatingsystemwithoutchanginganyoftheotherparts.AnswerstoExercises21.1WhataresomereasonswhymovingthegraphicscodeinWindowswww.hackshp.cnNTfromusermodetokernelmodemightdecreasethereliabilityofthesystem?WhichoftheoriginaldesigngoalsforWindowsNTdoesthisdegradationviolate?Answer:Thecodewasmovedtoeliminatetheoverheadofinterprocesscommunica-tion.TheadvantageofthepreviousmethodofhavingthecodeintheWin32subsystemisthatthekernel/executiveaswellasothersubsystemsareprotectedfromanerrorintheWin32subsystem.Thenewmethod,whileofferingaperformanceincreasetomeetmar-ketplaceconcerns,hasthedrawbackthatbadgraphicscodecanbringdowntheentiresystem.Indeed,examplesofthiswereseenpostedontheInternet.Thedesigngoalthatwasviolatedwasthatofindependentsubsystemsthatwouldnotbeabletoaffectothersubsystemsorthekernel.Thiswasbroughtaboutbycomplaintsfromusersoftheolder16-bitwindowsversionswhofeltthatapplicationsransloweronWindows2000.21.2TheWindows2000VMmanagerusesatwo-stageprocesstoallocatememory.Identifyseveralwaysinwhichthisapproachisbeneficial?Answer:AprocessinWindows2000islimitedto2gigabytesaddressspacefordata.Thetwo-stageprocessallowstheaccessofmuchlargerdatasets,byreservingspaceintheprocessesaddressspacefirstandthencommittingthestoragetoamemorymappedfile.Anapplicationcouldthuswindowthroughalargedatabase(bychangingthecom-103 104Chapter21Windows2000mittedsection)withoutexceedingprocessquotasorutilizingahugeamountofphysicalmemory.21.3Discusssomeadvantagesandsomedisadvantagesoftheparticularpage-tablestructureusedinWindows2000.Answer:Eachprocesshasitsownpagedirectorythatrequiresabout4megabytesofstor-age.Sinceitisathreeleveldesign,thismeansthattherecouldbeuptothreepagefaultsjustaccessingavirtualaddress.Sharedmemoryaddsonemorelevel.ThepagefaultscanoccurbecauseWindows2000doesnotcommittherequiredmemory(the4megabytes)un-tilnecessary.Sinceeachprocesshasitsownpagedirectory,thereisnowayforprocessestosharevirtualaddresses.Theprototypepage-tableentryaddsalevelofindirectionbuteliminatestheupdateofmultiplepage-tableentriesforsharedpages.21.4Whatisthemaximumnumberofpagefaultsthatcouldoccurintheaccessof(a)avirtualaddress,andof(b)asharedvirtualaddress?Whathardwaremechanismisprovidedbymostprocessorstodecreasethesenumbers?Answer:4forsharedaddresses.3forothers.TranslationLookasideBuffers.21.5Whatisthepurposeofaprototypepage-tableentryinWindows2000?Answer:Theprototypepage-tableentryisusedtopointtosharedpagesinsteadofhav-ingmultiplepage-tableentriespointtothesamepage.ItaddsanotherlayerofindirectionbutsaveshavingtoupdateNpage-tableentries.21.6Whatarethestepsthecachemanagermusttaketocopydataintoandoutofthecache?Answer:PleaseseeSection22.4.6fordetails.21.7Whatarethemainproblemsinvolvedinrunning16-bitWindowsapplicationsinaVDM?Identifythesolutionschosenby课后答案网Windows2000foreachoftheseproblems.Foreachsolu-tion,nameatleastonedrawback.Answer:Noanswer.21.8WhatchangeswouldbeneededforWindows2000torunaprocessthatusesa64-bitaddressspace?Answer:Primarily,theVMManagerwouldhavetobeextensivelymodified.Thismightentailchangingthepagesize,addinganotherleveltothepage-tablestructure,andsoon.www.hackshp.cnItmaybeimpracticaltosupportthefull64-bitaddressrange.Indeed,the“64-bit”versionofNT,Windows2000Server/E5.0,willsupportamaximumof32megabytesofRAM.Foranotherapproach,seetheAugust1997OracleWhitePaperentitled“OracleVeryLargeMemory(VLM)forDigitalAlphaNT.”21.9Windows2000hasacentralizedcachemanager.Whataretheadvantagesanddisadvan-tagesofthiscachemanager?Answer:Oneofthemajoradvantagesisthateachfilesystemdoesnthavetoprovideitsowncaching.Also,thecachemanageristightlycoupledtotheVMmanager.ThedrawbackisthatsomedeviceswanttodoDMAtransfers.Also,differentcachingschemesmightbeabletosavethedatacopyingthatispresentwiththeWindows2000scheme.21.10Windows2000usesapacket-drivenI/Osystem.Discusstheprosandconsofthepacket-drivenapproachtoI/O.Answer:Thestandardformofthepacketmakesiteasiertowritedriverssincetheycanfollowastandardinterfaceandprocessinghierarchy.Amajordisadvantageisthatallthepacketcopyingleadstoinefficiencies,althoughthatmanyTCP/IPstacksapparentlyhavethesameproblem. AnswerstoExercises10521.11Consideramain-memorydatabaseof1terabytes.WhatmechanismsinWindows2000couldyouusetoaccessthisdatabase?Answer:SeeQuestion21.2.课后答案网www.hackshp.cn 课后答案网www.hackshp.cn AppendixATHEFREEBSDSYSTEMAlthoughoperating-systemconceptscanbeconsideredinpurelytheoreticalterms,itisoftenusefultoseehowtheyareimplementedinpractice.Thisappendixpresentsanin-depthexami-nationofthe4.3BSDoperatingsystem,aversionofUNIX,asanexampleofthevariousconceptspresentedinthisbook.Byexaminingacomplete,realsystem,wecanseehowthevariousconceptsdiscussedinthisbookrelatebothtooneanotherandtopractice.ThisUNIXoperatingsystemwaschoseninpartbecauseatonetimeitwasalmostsmallenoughtounderstandandyetisnota课后答案网“toy”operatingsystem.Mostofitsinternalalgorithmswereselectedforsimplicity,notforspeedorsophistication.UNIXisreadilyavailabletodepart-mentsofcomputerscience,somanystudentsmayhaveaccesstoit.ItmightbebesttohavethestudentsreadthepapersbyRitchieandThompson[1974]andThompson[1978]beforereadingthisappendix.AnswerstoExerciseswww.hackshp.cnA.1HowwerethedesigngoalsofUNIXdifferentfromthoseofotheroperatingsystemsduringtheearlystagesofUNIXdevelopment?Answer:Ratherthanbeingamarket-orientedoperatingsystem,likeMULTICS,withdefinitegoalsandfeatures,UNIXgrewasatooltoallowThompsonandRitchietogettheirresearchdoneatBellLabs.TheyfoundasparePDP-11systemandwroteUNIXtohelpthemwithtext-processingrequirements.Itthereforeexactlysuitedtheirpersonalneeds,notthoseofacompany.A.2WhyaremanydifferentversionsofUNIXcurrentlyavailable?Inwhatwaysisthisdiver-sityanadvantagetoUNIX?Inwhatwaysisitadisadvantage?Answer:AT&TmadethesourcecodeofUNIXavailabletouniversitiesandothersites,whereexperimentationandexpansiontookplace.ThisallowedmanypeopletohaveaninfluenceonUNIXandtotryouttheirownideas.Theseideaswerecirculated,andthebestoneswereculledforinclusioninthestandardvarietiesofUNIX.Thedisadvantagethiscausesisthereisno“standard”versionofUNIX.ProgramswrittenforUNIXmayonlyrunonone,orsome,versionsofUNIXbutrarelyall.107 108AppendixATheFreeBSDSystemA.3Whataretheadvantagesanddisadvantagesofwritinganoperatingsysteminahigh-levellanguage,suchasC?Answer:CmakesUNIXhighlyportable,asevidencedbythemanysystemsitrunson.Itisalso(arguably)fastertowriteanddebugcodeinahigh-levellanguage,allowingUNIXtobemodifiedmorequicklythanassembly-language-basedoperatingsystems.Ofcourse,itrunslessefficientlythanifithadbeenwritteninassemblylanguage,likemostotheroperatingsystems.Itisgenerallylargerthanassembly-languageoperatingsystemstoo.A.4Inwhatcircumstancesisthesystem-callsequenceforkexecvemostappropriate?Whenisvforkpreferable?Answer:Sincevforkisafairlydangeroussystemcall,itshouldonlybeusedwhenalargeprocessneedstobestarted.Forsmallchildprocesses,theforkexecvecallsequenceisalmostasefficientanddoesnotallowitsaddressspacetobeaffected.A.5DoesFreeBSDgiveschedulingprioritytoI/OorCPU-boundprocesses?Forwhatrea-sondoesitdifferentiatebetweenthesecategories,andwhyisonegivenpriorityovertheother?Howdoesitknowwhichofthesecategoriesfitsagivenprocess?Answer:I/O-boundprocesseshavepriority.SinceI/O-boundprocesses(liketexteditors)aremorecloselyassociatedwithauser,abetterperformanceforI/O-boundprocessesgivetheusersquickerresponseandmakesthesystemseem“faster.”UNIXtracksthenumberofinputandoutputcharactersforeachprocess,andthedevicestheyareassociatedwith.ThemorecharactersUNIXseescomingfromttydevices,themoreI/O-boundaprocessis.A.6EarlyUNIXsystemsusedswappingformemorymanagement,whereas4.3BSDusedpag-ingandswapping.Discusstheadvantagesanddisadvantagesofthetwomemorymeth-ods.课后答案网Answer:WhenaCPUisslow,comparedtoitsbackingstore,swappingmakessense.TheCPUcanissueonetransfercommand,andtheI/Osystemcanmoveanentireprocessintooroutofmainmemory.AsCPUsgetfaster,pagingmakesmoresense.TheCPUhasmoretimetodecidewhichpagesarenotbeingusedandtoissuetransferrequests.Paginggenerallyrequires“smarter”hardware,withaccessbitsforeachpageofmemory,oratleastinvalidpagebits.Swappingwastesmemoryduetoexternalfragmentation.Evenonpagingsystems,swappingisusefulwhenthrashingisoccurringduetotoomanyactivewww.hackshp.cnprocessestouchingtoomanypages.A.7DescribethemodificationstoafilesystemthattheFreeBSDmakeswhenaprocessrequeststhecreationofanewfile/tmp/fooandwritestothatfilesequentiallyuntilthefilesizereaches20KB.Answer:Letsassumethattheblocksizeis4K.Thekernelreceivesacreatoropensystemcall(withthe“create”flagset).Itlocatesthedirectoryinwhichthefileisrequestedtobecreatedandverifiesthattheprocesshaswritepermissioninthatdirectory,andthatnofileexistswiththatsamenamewithoutwritepermission.Itlocatesthecylindergroupthatcontainsthedirectory,anditfindsafreeinodeinthatcylindergroupifthereisroom;ifnot,itdoesa“longseek”toanearbygroupthathasroom.Itallocatestheinodebyremovingitfromthefreeinodelist.Itthenmodifiesthefreeinodetoshowthatitisusedandupdatesalltheappropriatefields(writedate,size=0,ownerandgroup,protection,etc.).Thesystemthencreatesanewdirectoryentryintheparentdirectorysdataareathathasthenameofthenewfileandapointertoitsnewlyallocatedinode.Theinodeisthenplacedintheper-processtableofopenfiles,anditsfilepointerissetto0.Thekernelsfile-structuretableandthein-coreinodelistareupdatedtoo.Thedirectoryentryisthenwrittentodisktoassurethatdirectoriesarealwaysconsistent. AnswerstoExercises109Thesystemthenreceives“write”systemcallsuntil20Kofdataisreceived.Ifthecallerisefficient,thewriteswilloccurin4Kchunks(thesizeofacompleteblock).Ifthisisthecase,thesystemlocatesafreeblockinthecylindergroupandchangesthefreeblockbitmaptoshowtheblockisinuse.Itchangestheinodesuchthatthenextfreedirectblockischangedtohavethevalueofthediskblock.Sothefirstwriteof4Kwouldallocatethefirstdirectblock,thesecondwritethesecondblock,andsoon.Thesewritesarebufferedintheblockbuffercacheuntilthesystemdeemsitnecessarytowritethemtodisk.Ifwritesaredoneinotherthan4Kincrements,thesystemmustallocatefragmentsof1Ktohandleanywritesthatdonotendata4Kincrement.Eachfollowingwritewouldrequirethesystemtocopythedatainanyfragmentsleftbylastwriteintoanewblockandwouldstartappendingthenewdatathere.Obviouslythisisveryefficient(2readsandawriteperwrite).Fortunately,thediskbuffercachealleviatessomeofthisoverheadbynotwritingdataimmediatelytodisk.A.8DirectoryblocksinFreeBSDarewrittensynchronouslywhentheyarechanged.Considerwhatwouldhappeniftheywerewrittenasynchronously.Describethestateofthefilesystemifacrashoccurredafterallthefilesinadirectoryweredeletedbutbeforethedirectoryentrywasupdatedondisk.Answer:Thecontentsofthefilesystemandthedescriptionofthatfilesystem(thedirectorystructure)wouldnotcorrespond.Insuchacasepointstoinvalidblocks,orblocksofanotherfile,mightresult.Thefilesystemwouldbeinastateofchaosandunusable.A.9Describetheprocessthatisneededtorecreatethefreelistafteracrashin4.1BSD.Answer:Noanswer.A.10WhateffectsonsystemperformancewouldthefollowingchangestoFreeBSDhave?Ex-plainyouranswers.课后答案网a.Themergingoftheblockbuffercacheandtheprocesspagingspaceb.ClusteringdiskI/Ointolargerchunksc.ImplementingandusingsharedmemorytopassdatabetweenprocessesratherthanusingRPCorsocketswww.hackshp.cnd.UsingtheISOseven-layernetworkingmodelratherthantheARMnetworkmodelAnswer:a.SuchamergewasdoneinSunOS4.1.Theresultisamoregeneralmodelofmemoryuse.Iflotsoffiletransfersareoccurring,morememoryisusedtoholddatablocks.Ifmoreprocessesareexecuting,morestorageisdevotedtopaging.b.AnotherchangetoSunOS.Thischangeresultedinmoreefficientuseofthedisksinthesystemlargerchunksofdataaretransferredwithfewerseeks.c.Moreefficientdatatransferbetweencommunicatingprocesses.d.Lessefficientnetworkuse,asapacketspendsmoretimetraversingthenetworkprotocolstackbeforeandafterbeingtransmittedonthenetwork.A.11Whatsockettypeshouldbeusedtoimplementanintercomputerfile-transferprogram?Whattypeshouldbeusedforaprogramthatperiodicallyteststoseewhetheranothercomputerisuponthenetwork?Explainyouranswer.Answer:Reliabledeliveredmessagewouldbebest,becausetransfersaresuretooc-curbutopenconnectionsarenotneededbetweenthesystems.Datagramsarethenext 110AppendixATheFreeBSDSystembest,becausetheyareunreliable.Perhapsstreamsareanotherchoiceifopenconnectionsaredesired.SunNFSusesdatagramsbecausereliabledeliveredmessagesarenotimple-mented.Adatagramisabouttheonlychoicefortestingtheavailabilityofothersystems,sincetheymayormaynotbeabletoreceiveapacket(disallowingreliabledeliveredmes-sages).课后答案网www.hackshp.cn AppendixBTHEMACHSYSTEMAppendixBismeanttointroducetheMachoperatingsystemthatwasdesignedtoincorpo-ratethemanyrecentinnovationsinoperating-systemresearchtoproduceafullyfunctional,technicallyadvancedoperatingsystem.UnlikeUNIX,whichwasdevelopedwithoutregardformultiprocessing,Machincorporatesmultiprocessingsupportthroughout.Itsmultiprocessingsupportisalsoveryflexible,rangingfromsharedmemorysystemstosystemswithnomemorysharedbetweenprocessors.Machisdesignedtorunoncomputersystemsrangingfromonetothousandsofprocessors.Inaddition,Machiseasilyportedtomanyvariedcomputerarchi-课后答案网tectures.AkeygoalofMachistobeadistributedoperatingsystemcapableoffunctioningonheterogeneoushardware.SinceMachisfullycompatiblewithUNIX,itprovidesauniqueopportunityforustocom-paretwofunctionallysimilar,butinternallydissimilar,operatingsystems.AnswerstoExerciseswww.hackshp.cnB.1WhatthreefeaturesofMachmakeitappropriatefordistributedprocessing?Answer:Efficientmessagepassing,networktransparency(threadsandserversmaybeonanysystemonthenetwork),heterogeneoussystemsupport.B.2Nametwowaysthatportsetsareusefulinimplementingparallelprograms.Answer:Manythreadsortasksmayoperateonagivenproblem,possiblyonmultipleCPUs,andcommunicatewiththecontrollingthreadortaskviaaportset.Eachcooperatingthreadwouldhaveitsowndestinationportinthecontrollingtask.Computationscanbedispatchedtoeachthreadandthecontrollingtaskcansendnewcomputationstoeachthreadasitreturnsvaluesthroughitsport.Thecontrollingtaskcanwaitformessagesthroughitsportsetratherthanpollingeachindividualporttoseeifacomputingthreadhasfinisheditsjob.B.3Consideranapplicationthatmaintainsadatabaseofinformation,andprovidesfacilitiesforothertaskstoadd,delete,andquerythedatabase.Givethreeconfigurationsofports,threads,andmessagetypesthatcouldbeusedtoimplementthissystem.Whichisthebest?Explainyouranswer.111 112AppendixBTheMachSystemAnswer:1threadwith1port,receivingmessagesoftypequery,add,anddelete.3threadsand3portswith1messagetype,data.Arequesttypeisdifferentiatedbytheporttowhichitarrives.Eachthreadhasresponsibilityfor1port,andthusonetypeofoperation.3threadsasabove,but1portand3messagetypesasinthefirstconfiguration.Thesecondsolutionisprobablythemostflexible,especiallyifthedatabaseisexpectedtobeverybusy(manyrequestspersecond).Thefirstisfineforalow-usedatabase.B.4Givetheoutlineofataskthatwouldmigratesubtasks(tasksitcreates)toothersystems.Includeinformationabouthowitwoulddecidewhentomigratetasks,whichtaskstomigrate,andhowthemigrationwouldtakeplace.Answer:Unfortunately,Machdoesnotprovideallthefeaturesneededtodirectlysup-portprocessmigration.Anoutlineofanindirectsolutionfollows,andassumesthattheprocessestobemigratedareallidentical.a.Startthemainprocess.b.Usethe4.3BSDremoteexecutionfacility(thershcommand)tospawndaemonsoneverycomputertowhichtasksaretobemigrated.c.EachofthesedaemonsregistersitselfwiththeNetMsgServersothecontrollingpro-cessisabletocommunicatewiththem.d.Thecontrollingprocessthencomputesthecurrentnumberofrunnableprocesses(theloadaverage)oneachcomputerbyqueryingeachofthedaemonsfortheloadaverageontheirsystems.Iftheloadaveragesvarynoticeably,ataskshouldbemigrated.课后答案网e.Ataskisselectedbasedonthetimeithashadtoexecute.Itismostefficienttomigratethemost-recently-createdorleast-run-time-accumulatedprocess.f.Ataskismigratedbykillingitonitssystemandsendingamessagetothedaemonontheleast-loadedsystemwithenoughinformationtostartanidenticalprocessex-ecuting.www.hackshp.cnB.5NametwotypesofapplicationsforwhichyouwouldusetheMIGpackage.Answer:Anyprogramthatneedstosendorreceivemessages.B.6Whywouldsomeoneusethelow-levelsystemcalls,insteadoftheCThreadspackage?Answer:ToaccessfacilitiesoutsidetherangeoftheCThreadspackageortousethefacil-itiesinadifferentway.Forinstance,portsetsarenotdirectlysupportedbytheCThreadspackage.Low-levelapplications,likedebuggers,needmoredirectaccesstosystemcallsalso.B.7Whyareexternalmemorymanagersnotabletoreplacetheinternalpage-replacementalgorithms?Whatinformationwouldneedtobemadeavailabletotheexternalmanagersforthelattertomakepage-replacementdecisions?Whywouldprovidingthisinformationviolatetheprinciplebehindtheexternalmanagers?Answer:Ifanexternalmemorymanagercrashes,thesystemmustbeabletoremovepagesfrommemory.Withouttheinternalpage-replacementalgorithms,thesystemwouldstarveformemory.Also,theinternalroutineshaveaccesstodatathatexternalonescantreach,so,forinstance,LRUpagereplacementcanonlybeimplementedbytheinternalroutine.Dataneededoutsideofthekernelincludespageaccesscountsortimesandpage AnswerstoExercises113validbits.Externalmanagersmustbesystemindependent.Forinstance,itmightprovidepagestotasksonincompatibleCPUs.Howwouldthepagetableinformationbeprovidedinasystem-independentway?B.8Whyisitdifficulttoimplementmutualexclusionandconditionvariablesinanenviron-mentwherelikeCPUsdonotshareanymemory?WhatapproachandmechanismcouldbeusedtomakesuchfeaturesavailableonaNORMAsystem?Answer:Thebestmutual-exclusionalgorithmsdependonaccesstosharedvariables.Theseroutinesbecomemuchmoredifficulttoimplementandprovecorrectif,forinstance,alllockingnegotiationmustbedoneviamessages.Toimplementlocking,messagesmightbesenttoadaemononalockserverthatwouldallocatelocks,reportvaluesoflockedvariables,andotherwisesimulatethebehavioroftheusualmutexroutines.B.9Whataretheadvantagestorewritingthe4.3BSDcodeasanexternal,user-levellibrary,ratherthanleavingitaspartoftheMachkernel?Arethereanydisadvantages?Explainyouranswer.Answer:Thekernelismuchsmallerandefficient.Thissmallkernelcanbeimplementedonlesspowerfulsystems.Itshouldalsobemorerobustsincethesimplerthekernel,thefewerbugsitshouldhave.Also,sincethekernelislockedintophysicalmemory,thesmalleritisthelessmemoryisneededonthemachinesonwhichitruns.Thedisadvantageisthatthesystemasawholebecomesmorecomplicated,withBSDcodespreadoutamonglibraries,alittlekernel-levelcode,andcodeineachuserprocess.Itisalsodifficulttoimplementcorrectly,tokeepsuchfacilitiesasBSDsignalsworking.课后答案网www.hackshp.cn 课后答案网www.hackshp.cn'