斯坦福大学2021年操作系统期末考试题(英文)

斯坦福大学2021年操作系统期末考试题(英文)FINALEXAM–INTRODUCTIONTOOPERATINGSYSTEMSCSE421May2,2021(Spring2021)NAME:_____________________________________________________________STUDENTNUMBER:_________-_________INSTRUCTIONSThisisaclosedbookbutyouareallowedtwosheetsofinformationtoreferto.Youhave180minutestocomplete10questions.Pleasewriteneatlyandclearly.Toreceivepartialcredit,youmustshowallworkforyouranswers.Youshouldhave11pagesinthisexambook,someofwhichareblanktoallowroomforyouranswers.RawScore:___________/140=____________/1001)[20Points]DeadlockConsiderthefollowingsnapshotofasystem(P=Process,R=Resource):Answerthefollowingquestionsusingbanker’salgorithm:a)CalculatetheNeedsmatrix:b)Isthesysteminasafestate?Ifso,showasafeorderinwhichtheprocessescanrun.c)CanarequestofoneinstanceofRAbyProcessP0begrantedsafelyaccordingtoBanker’salgorithm?2)[20points]LogicalandPhysicalAddressSpacesTheKiwi?memoryarchitecturedesignteamhasadilemma.Theteamisconsideringseveraldifferentmemoryconfigurationvariationsforanupcomingmachinedesign.Considerthefollowingdesigns(Allmemoryaccessesareintermsofbytes,andallareusingpagingtechniques):a)[6points]Foreachdesign,listthemaximumnumberofpageseachprocesscanaccessinlogicaladdressspace.b)[6points]Foreachdesign,listthemaximumnumberofframesinphysicalmemory.c)[6points]Fordesign3,iftheoutermostpagetableholds32entries,howmanybitsareneededinthelogicaladdresstorepresenttheouterpagetable?Howmanybitsareusedforrepresentingtheoffsetwithinapage?Howmanybitsareneededinthelogicaladdressinordertorepresenttheinnerpagetable?Giventhefollowingreferencestring:021301401234showa)Pagefaultsoccurduringtheprocessingofthereferencescheme?b)Thehitratioisforeachofthefollowingpoliciesinapuredemandpagingsystem?c)WhatdoyouobservewhenyoumovefromScheme1toScheme2?Explain.Scheme1:FIFOwiththreepagesofmainmemoryScheme2:FIFOwithfourpagesofmainmemoryConsiderasystemwherethevirtualmemorypagesizeis2K(2048bytes),andmainmemoryconsistsof4pageframes.Nowconsideraprocesswhichrequires8pagesofstorage.Atsomepointduringitsexecution,thepagetableisasshownbelow:1.Listthevirtualaddressrangesforeachvirtualpage.2.Listthevirtualaddressrangesthatwillresultinapagefault.3.Givethemainmemory(physical)addressesforeachofthefollowingvirtualaddresses(allnumbersdecimal):(i)8500,(ii)14000,(iii)5000,(iv)2100.5)[20points]FileSystemImplementationSupposeafilesystemisconstructedusingblocksof8wordseach.Inthissystem,awordhasalengthof4bytes.Thediskpackusedtoholdthefilesystemconsistsof32blocks.Theinitialblock(block0)containsadirectoryentry.Thedirectoryentrycontainsthefilenameofasinglefileinthisfilesystem,andapointertothefirstI-nodeinblock1.TheI-nodestructureisasfollows(word,value):Thefilecontains16wordsofdata:thefirstdirectindexpointsatblock31,andtheseconddirectindexpointsatblock29.Blocks4,7,10,and15aremarkedbad.Assumethatfreeblocksareallocatedinlogicalorderstartingwithblock0andthatwriteoperationsmodifythefilesystem1blockatatime.Whatwillthestateofthesystemlooklikeafter100additionalwordsareappendedtothefile(drawablockdiagramshowingthestructureoftheI-nodeandtheblocksthatareallocated)6)[16points]DiskSchedulingDiskrequestscomeintothediskdriverforcylinders10,22,20,2,40,6,and38,inthatorder.Assumethatthediskhas100cylinders.Aseektakes6msecpercylindermoved.Computetheaverageseektimefortherequestsequencegivenabovefor1.First-come,First-served2.ShortestSeekTimeFirst(SSTF)3.LOOK(withthedisk-arminitiallymovingtowardshighernumbercylindersfromlowernumbercylinders)4.C-SCANInallthecases,thearmisinitiallyatcylinder20.7)[10points]Security:PublicKeyEncryptionConsiderthepublickeyencryptiondefinedbytheRSA(Rivest,Shamir,Adelman)scheme.Assumethatthetwostartingprimesarepandqare3and7respectivelyanddeterminethe(nontrivial)privatekeyandpublickeypairsaccordingtotheRSAscheme.8)[10Points]Networking:TCP/IPThefollowingflowchartshowstheclientandserverportionsofaTCPcommunicationsession.Fillintheemptybubbles/boxeswiththeappropriatesocketsystemcallnames.CLIENTSERVER9)[10points]EnduringPrinciplesinSystemDesign1.Whenasystemgetscomplexindesignwhatisacommonsolutiontomanagethecomplexity?Giveanexample.2.Whenyouexperienceincompatibilitiesbetweensystemmodules,howwillyousolvethisproblem?Giveanexample.3.Whatisacommondatastructureusedtomanage(theslotsfor)nresources?Giveanexample.4.Thedataitemssuchasinodesandfilesaretypicallylocatedinexternalmemorythatissluggishrelativetothelocalmainmemory.Howaretheeffectiveaccesstimesofthesestructuresminimized?5.Whenatablemaintainingalistofpointersgrowsunmanageablylargehowwillyousolvethisproblemsothat(i)searchtimesofthetableisreasonableand(ii)onlytheregionofinterestinthetableneedtobeinthememory?10)[10points]NachosOperatingSystems1.Listthetwomainoperations(methods)thathavethepotentialforresultinginapagefault.2.Whereistheaddressthatcausedthepagefaultstored?3.YouincrementedthePCaftereverysystemcallyouimplemented?Whynotforpagefaultsystemcall?4.WhatisthepurposeofExec,JoinandExitsystemcalls?5.Explaintheabovewithanexample.6.Howwouldyoucontroltheaccesstoasharedresourcebymultiplethreads?