北京邮电大学2016-2017学年操作系统期末考试题.docx

北京邮电大学2016-2017学年操作系统期末考试题.docx

《北京邮电大学2016-2017学年操作系统期末考试题.docx》由会员分享，可在线阅读，更多相关《北京邮电大学2016-2017学年操作系统期末考试题.docx（10页珍藏版）》请在冰点文库上搜索。

北京邮电大学2016——2017学年第一学期

《操作系统原理》期末考试试题A卷

1.FILLINBLANKS（1*10points）

（1）Atime-sharedcomputersystemuses schedulingschemeandmultiprogrammingtoprovideeachuserwithasmallportionofCPUtime.

（2）TopreventusersfromperformingillegalI/O,wedefineallI/Oinstructiontobe instructions,whichcanbeexecutedonlyinmonitormode.

（3）ConsideringOSinterfaces,anapplicationprogramcanutilize toacquireservicesprovidedbyOS.

（4）Inoperatingsystems, isthebasicunitofresource-allocationforprogramsexecutingincomputersystems.

（5）Ifasystemcandealwith3real-timeprocesses,5interactiveprocessesand2batchprocessesin400ms,thenthethroughputofthissystemis .

7/10

（6） isahighlevellanguageconstructforprocesssynchronization,andischaracterizedbysharedvariablesandasetofprogrammer-definedoperationsonthesharedvariables.

（7）Withrespecttodeadlocks,asystemis ifthesystemcanallocateresourcestoeachprocess（uptoitsmaximum）insomeorderandstillavoidadeadlock.

（8）Onapagingsystemwith232bytesofphysicalmemory,2111024-bytepagesoflogicaladdressspace, bitsinthephysicaladdressspecifytheframenumber:

（9）Thefilesystemconsistsoftwodistinctparts:

acollection.offilesanda

,whichorganizesandprovidesinformationaboutallfilesinthesystem.

（10）Consideringfileaccessmethodsandfilediskspaceallocation,accessisadapttothefilesoflinkedallocation

2.CHOICE（1*13points）

（1）Whichoneisnotthemaintaskofanoperatingsystem?

A.Processmanagement B.Languagetranslation

C.Filemanagement D.memorymanagement

（2）Whichofthefollowingsystemhasstricttimeconstraint？

A.batchsystemB.time-sharingsystemC.real-timesystemD.interactivesystem

（3）Astarvation-freejob-schedulingpolicyguaranteesthatnojobwaitsindefinitelyforservice.Whichofthefollowingjob-schedulingpoliciesisstarvationfree？

A.RoundRobinB.PriorityC.ShortestJobFirstD.Noneoftheabove

（4）Inoperatingsystems，thesemaphorestandsforinstancesofresource，itisaintegervariablerelevanttoaqueue，itsvaluecanonlybechangedbyoperationWAITandSIGNAL.IfasemaphoreSisinitializedto5，nowit’svalueis2，howmanyprocessesisorarewaitinginthequeuerelevanttoS.

A.3B.2 C.1 D.0

（5）TheBankerAlgorithmisusedfor .

A.deadlockavoidance B.deadlockprevention

C.deadlockdetection. D.deadlockrecovery

（6）Withrespecttobindingofinstructionsanddatatomemoryaddresses,ifaddressbindingisdoneat , thehardwareMMUisneeded.

A.CodingtimeB.compiletimeC.loadtimeD.executiontime

（7）Consideringthefollowingmemorymanagementschemes, willmaximizememoryutilization.

A.fixd-sizedpartitions（MVT）. B.paging C.segmentationwill

（8）Consideramachineinwhichallmemory-referenceinstructionshaveonlyonememoryaddress,andone-levelindirectaddressingisallowed,ifaninstructionisassumedtobestoredinoneframe,thentheminimumnumberofframesperprocessis .

A.one B.two C.three D.four

（9）Thefilesystemitselfisgenerallycomposedofseveraldifferentlevels.Intheselevels,the managesmetadataandisresponsibleforprotectionandsecurity.

A.logicalfilesystem B.file-organizationmodule

C.basicfiesystem D.I/Ocontrol

（10）Whichallocationschemewouldworkbestforafilesystemimplementedonadevice（e.g.atapedrive）thatcanonlybeaccessedsequentially?

A.linkedallocation B.contiguousallocation

C.indexallocation D.noneofthem

（11）Thediskfree-spacelistisimplementedasabitmap.Ifthesizeofthediskspaceis128blocks,andeachblockisof512bytes,then bytesareneededtostorethebitmap.

A.128 B.512 C.16 D.8192

（12）Withrespecttodisk1Ooperations,the executesIOinstructionstocontrolthediskcontrollertoaccessdataondisks

A.filesystem B.kernelI/Osubsystem C.applicationprocessD.driver

（13）Thefollowingcharacteristicsexcept arecorrectfordisks.

A.secondarystorage B.read-writedevices

C.random-accessdevices D.character-streamdevices

3.ESSAYQUESTIONS（27points）

3.1（6points）Explainthefollowingterms

1）deadlock（3points）

（2）demandpaging（3points）

3.2（6points）Inamultiprogrammingsystem,considerthefollowingdiagramofprocessstatetransitions,

1）Isitpossiblethatthetransition2ofaprocesscancausethetransition1foraprocess？

Ifyes，giveanexample；Iinot，why？

（3points）

2）Isitpossiblethatthetransition4ofaprocesscancausethetransition1foraprocess？

Ifyes，giveanexample；Ifnot，why？

（3points）

3.3（4points）Inapagingsystem,thepagetableisstoredinmainmemory,andtheactivepageentriesarealsoboldinhigh-speedassociatememoryTLB（translationlook-asidebuffer）.Ifittakes100nanosecondstosearchtheTLB,and180nanosecondstosearchpagetableinmainmemory.WhatmusttheTLBhitratiobetoachieveaneffectiveaccesstime（EAT）of150ns?

3.4（6points）Inthefilesystemonadiskwithphysicalblocksizesof512bytes,afileismadeupof128-bytelogicalrecords,andeachlogicalrecordcannotbeseparatelystoredintwodifferentblocks.Thediskspaceofthefileisorganizedonthebasisofindexedallocation,andablockaddressisstoredin4bytes.Supposethat2-levelindexblocksisusedtomanagethedatablocksofthefile,answerthefollowingquestions:

1）Whatisthelargestsizeofthefile?

（3points）

2）Given2000,thenumberofalogicalrecordthefile,howtofindoutthephysicaladdressoftherecord2000inaccordancewiththe2-levelindexblocks（3points）

3.5（5points）Afileismadeupof128-bytefix-sizedlogicalrecordsandstoredonthediskintheunitoftheblockthatisof1024bytes.Thesizeofthefileis1024bytes.PhysicalI/OoperationstransferdataonthediskintoanOSbufferinmainmemory,intermsof1024-byteblock.Ifaprocessissuesreadrequeststoreadthefile'srecordsinthesequentialaccessmanner,whatisthepercentageofthereadrequeststhatwillresultinIOoperations?

4.（12points）Consideringareal-timesystem,inwhichthereare4real-timeprocessesP1,P2,P3andP4,thatareaimedtoreactto4criticalenvironmentaleventse1,e2,e3ande4intimerespectively.

Thearrivaltimeofeacheventei,1≤i≤4,（thatis,thearrivaltimeoftheprocessPi）,thelengthoftheCPUbursttimeofeachprocessPi,andthedeadlineforeacheventei;aregivenbelow.Here,thedeadlineforeiisdefinedastheabsolutetimepointbeforewhichtheprocessPimustbecompleted.

Thepriorityforeacheventei（alsoforPi）isalsogiven,andasmallerprioritynumberimpliesahigherpriority.

Events

Process

ArrivalTime

BurstTime

Priorities

Deadline

e1

P1

0.00

4.00

3

7.00

e2

P2

3.00

2.00

1

5.50

e3

P3

4.00

2.00

4

12.01

e4

P4

6.00

4.00

2

11.00

（1）Supposethatpriority-basedpreemptiveschedulingisemployed,（6points）

a）DrawaGanttchartillustratingtheexecutionoftheseprocesses

b）Whataretheaveragewaitingtimeandtheaverageturnaroundtime

c）Whicheventwillbetreatedwihintime,thatistheprocessreactingtothiseventwillbecompletedbeforeitsdeadline?

（2）SupposethatFCFSschedulingisemployed,（6points）

a）Drawa Ganttchartillustratingtheexecutionoftheseprocesses

b）Whataretheaveragewaitingtimeandtheaverageturnaroundtimec）.Whicheventwillbetreatedwithintime?

5.（16points）Hereisaplatethatcancontain3fruits.Thefatherputsapplesandthemotherputsorangesintotheplate.Thedaughtertakesapplesandthesontakesorangesfromtheplatetoeat.Thefather,mother,daughterandsonarepermittedonlytooperateontheplateinamutuallyexclusivemode,andonlyoneappleoroneorangecanbeputintoortakenfromtheplateeachtime.

Pleasedesignfoursemaphore-basedprocessesforthefather,mother,daughterandson-tocorrectlyoperateontheplate.

Requirements:

.

1）Definethesemaphoresusedtosynchronizetheprocesses,describesimplytheroleofeachsemaphore,andgivetheirinitialvalues.（4points）

2）Illustratethestructuresof,processesforthefather,mother,daughterandson.（12points）

Allocation

Request

Available

6.（12points）ConsideringasystemwithfiveprocessesP0throughP4andthreeresourcetypesA,BandC.ResourcetypesAhas4instances,Bhas3instancesandChas6instances.Supposethat,attimeT0,wehavethefollowingresource-allocationstate,

A

B

C

A

B

C

A

B

C

P0

1

0

0

2

3

2

1

1

2

P1

2

1

1

1

0

2

P2

0

1

1

1

0

3

P3

0

0

2

4

2

0

P4

0

0

0

1

0

6

Answerfollowingquestionsbymeansofthedeadlock-detectionalgorithm

（1）Isthesysteminadeadlockedstate?

andwhy?

（6points）

（2）IfP0requestsoneadditionalinstanceoftypeB;whatistheRequestMatrix?

Isthereadeadlockinthesystem?

andwhy?

（6points）

।

7.（10points）Acacheisaregionoffastermemorythatholdscopiesofdata.Mostsystemshaveoneormorehigh-speeddatacachesinthememoryhierarchy.Information（e.g.theinstructionordata）isnormallykeptinmainmemory.Asitisused,itiscopied-intothecache.Whenaparticularpieceofinformationis-needed,wefirstcheckwhetheritisinthecache.Ifitis,weusetheinformationdirectlyfromthecache;ifitismot,weusetheinformationfromthemainmemoryandputacopyinthecacheundertheassumptionthatwewillneeditagainsoon.

8/10

Inapagingsystem,the-mainmemoryisdividedinto1024frames