完整word版期末复习题.docx

完整word版期末复习题.docx

《完整word版期末复习题.docx》由会员分享，可在线阅读，更多相关《完整word版期末复习题.docx（7页珍藏版）》请在冰点文库上搜索。

完整word版期末复习题

1processesP1,P2,andP3，Definesemaphores,andsynchronizetheexecutionofP1,P2,andP3bywait（）andsignal（）onthesesemaphores.

2DrawthreeGanttcharts，

WhatistheturnaroundtimeofeachprocessforSJF,andRR

Whataretheaveragewaitingtimeandtheaverageturnaroundtime

3Considerthefollowingpage-referencestring:

（1）LRUpagereplacement

（2）Optimalpagereplacement

（3）FIFOreplacementalgorithm

pagefaulttimes，Pagefaultsrate

4

（1）Isthesysteminasafeorunsafestate?

Why?

（2）IfPirequestresourceof（0,1,0,0）,canresourcesbeallocatedtoit?

Why?

Inademandpagingsystem,thepagesizeis1kbytes,andthepagetableisasfollows（assumingusedecimalvalues）,translatealogicaladdress10intoitscorrespondingphysicaladdress,andwhy?

frame

2

1

6

A．8202B．4106C．2058D．1034

Inademandpagingsystem,thepagesizeis1024bytes,andthepagetableisasfollows,wouldthefollowingvirtualaddresses（assumingusedecimalvalues）resultinapagefault?

Andwhy?

valid/invalid

#frame

i

20

v

15

v

20

v

29

i

80

i

53

（1）2500

（2）5100

Pagetable

（1）2500=2*1024+452page2isvalid,sonopagefault

（2）5100=4*1024+1004page4isinvalid,apagefaultoccurs

Considerasimplepagingsystemwithapagetablecontaining1024entriesof14bits（includingonevalid/invalidbit）each,andapagesizeof1024bytes（5points）

（a）howmanybitsareinthelogicaladdress?

（b）howmanybitsareinthephysicaladdress?

（c）whatisthesizeofthelogicaladdressspace?

（d）howmanybitsinthelogicaladdressspecifythepagenumber?

（e）howmanybitsinthephysicaladdressspecifytheoffsetwithintheframe?

1）20

2）23

3）220B

4）10

5）10

（a）Thereare10+10=20bitsinthelogicaladdress

（b）Thereare13+10=23bitsinthephysicaladdress

（c）Thesizeofthelogicaladdressspaceis220bytes

（d）Thereare10bitsinthelogicaladdressspecifyingthepagenumber

（e）Thereare10bitsinthephysicaladdressspecifyingtheoffsetwithintheframe

Considerasystemusingsegmentationwithpagingmanagementscheme,whosephysicalmemoryisof235bytes.Thelogicaladdressspaceconsistsofupto8segments.Eachsegmentcanbeupto213pages,andpagesizeof512bytes,

（1）Howmanybitsinthelogicaladdressspecifythepagenumber?

（2）Howmanybitsarethereintheentirelogicaladdress?

（3）Whatisthesizeofaframe?

（4）Howmanybitsinthephysicaladdressspecifytheframenumber?

（5）Howmanybitsinthephysicaladdressspecifytheframeoffset?

（6）Howmanyentriesarethereinthepagetableforeachsegmentation,i.e.howlongisthepagetableforeachsegmentation?

（1）Eachsegmentconsistsofupto213pages,solog2（213）=13bitsinthelogicaladdressspecifythepagenumber

（2）Theentirelogicaladdressconsistsofsegmentationandoffsetinsegmentation,andoffsetinsegmentationisdividedintopagenumberandpageoffset,soentirelogicaladdresshas

log2（8）+log2（213）+log2（512）=3+13+9=25bits

（3）thesizeofaframeisequaltothatofapage,i.e.,512bytes

（4）thetotalsizeofphysicalmemoryis235bytes,andeachframeis29=512bytes,sothereare26=（35–9）bitsinthephysicaladdressspecifytheframenumber

（5）thenumberofbitsinthephysicaladdressspecifyingtheframeoffsetdependsonthesizeoftheframe,solog2（29）=9bitsinthephysicaladdressspecifytheframeoffset

（6）eachentryinthepagetablecorrespondstoapageinthesegment,eachsegmentcanbeupto213pages,sothereare213entriesinthepagetableforeachsegment.

Afilesystemuses256-bytephysicalblocks.Eachfilehasadirectoryentrygivingthefilename,locationofthefirstblock,lengthoffile,andlastblockposition.Assumingthelastphysicalblockreadis100,block100andthedirectoryentryarealreadyinmainmemory.

Forthefollowingtwofileallocationalgorithms,howmanyphysicalblocksmustbereadtoaccessthespecificblock600（includingthereadingofblock600itself）,andwhy?

（1）contiguousallocation

（2）linkedallocation

（1）1

Contiguousallocationsupportsdirectaccessonarbitrtaryphysicalblocksinafile.Toaccessphysicalblock600,thebolck600canbedirectoryreadintomemory.

（2）500

Linkedallocationisusedonlyforsequential-accessfiles,filesystemcanonlyreadblocksonebyone,directedbyfilepointers.

Tofindthephyicalblock600inthefile,filesystemlocatesonthe101thblockfollowingthe100thblockjustread,andreadsblock101,block102,…,untilblock600.

Considerafilesysteminwhichadirectoryentrycanstoreupto32diskblockaddresses.Forthefilesthatisnotlargerthan32blocks,the32addressesintheentryservesasthefile’sindextable.Forthefilesthatislargerthan32blocks,eachofthe32addressespointstoanindirectblockthatinturnpointsto512fileblocksonthedisk,andthesizeofablockis512-bytes.Whatisthelargestsizeofafile?

32x512=16384fileblocks

16384x512=8388608bytes

or

25x29x29=223bytes

Inthefilesystemonadiskwithphysicalblocksizesof512bytes,afileismadeupof128-bytelogicalrecords,andeachlogicalrecordcannotbeseparatelystoredintwodifferentblocks.Thediskspaceofthefileisorganizedonthebasisofindexedallocation,andablockaddressisstoredin4bytes.Supposethat2-levelindexblocksbeusedtomanagethedatablocksofthefile,answerthefollowingquestions:

1）Whatisthelargestsizeofthefile?

2）Given2000,thenumberofalogicalrecordinthefile,howtofindoutthephysicaladdressoftherecord2000inaccordancewiththe2-levelindexblocks.

1）

512/4=128

128*128*512=128*64KB=8192KB

or=223bytes=8MB

or=8388680

2）

512/128=4

2000/4=500

in3blockinthefirst–levelindexblock

in116blockinthesecond-levelindexblock

Afileismadeupof128-bytefix-sizedlogicalrecordsandstoredonthediskintheunitoftheblockthatisof1024bytes.Thesizeofthefileis10240bytes.PhysicalI/OoperationstransferdataonthediskintoanOSbufferinmainmemory,intermsof1024-byteblock.Ifaprocessissuesreadrequeststoreadthefile’srecordsinthesequentialaccessmanner,whatisthepercentageofthereadrequeststhatwillresultinI/Ooperations?

1024/128=8record

10240/8=80record

10240/1024=10block

10/80=1/8=0.125

or12.5%

Considerapagingsystemwiththepagetablestoredinmemory.

a.Ifamemoryreferencetakes300timeunit,howlongdoesittaketoaccessaninstructionordatainapagethathasbeenpagedintomemory?

b.IfweaddTLB（translationlook-asidebuffers）,and80percentofallpage-tableentriescanbefoundintheTLB,whatistheeffectivememoryaccesstime?

（Assumethatfindingapage-tableentryintheassociativeregisterstakes20timeunit,iftheentryisthere.）

a.300x2=600

b.0.8x（300+20）+0.2x（600+20）=256+124=380