操作系统第九版部分课后作业习题答案分析解析.docx

操作系统第九版部分课后作业习题答案分析解析.docx

《操作系统第九版部分课后作业习题答案分析解析.docx》由会员分享，可在线阅读，更多相关《操作系统第九版部分课后作业习题答案分析解析.docx（15页珍藏版）》请在冰点文库上搜索。

操作系统第九版部分课后作业习题答案分析解析

CHAPTER9VirtualMemory

PracticeExercises

9.1Underwhatcircumstancesdopagefaultsoccur?

Describetheactions

takenbytheoperatingsystemwhenapagefaultoccurs.

Answer:

Apagefaultoccurswhenanaccesstoapagethathasnotbeen

broughtintomainmemorytakesplace.Theoperatingsystemverifies

thememoryaccess,abortingtheprogramifitisinvalid.Ifitisvalid,a

freeframeislocatedandI/Oisrequestedtoreadtheneededpageinto

thefreeframe.UponcompletionofI/O,theprocesstableandpagetable

areupdatedandtheinstructionisrestarted.

9.2Assumethatyouhaveapage-referencestringforaprocesswithm

frames（initiallyallempty）.Thepage-referencestringhaslengthp;

ndistinctpagenumbersoccurinit.Answerthesequestionsforany

page-replacementalgorithms:

a.Whatisalowerboundonthenumberofpagefaults?

b.Whatisanupperboundonthenumberofpagefaults?

Answer:

a.n

b.p

9.3ConsiderthepagetableshowninFigure9.30forasystemwith12-bit

virtualandphysicaladdressesandwith256-bytepages.Thelistoffree

pageframesisD,E,F（thatis,Disattheheadofthelist,Eissecond,

andFislast）.

Convertthefollowingvirtualaddressestotheirequivalentphysical

addressesinhexadecimal.Allnumbersaregiveninhexadecimal.（A

dashforapageframeindicatesthatthepageisnotinmemory.）

•9EF

•111

2930Chapter9VirtualMemory

•700

•0FF

Answer:

•9EF-0EF

•111-211

•700-D00

•0FF-EFF

9.4Considerthefollowingpage-replacementalgorithms.Rankthesealgorithmsonafive-pointscalefrom“bad”to“perfect”accordingtotheir

page-faultrate.SeparatethosealgorithmsthatsufferfromBelady’s

anomalyfromthosethatdonot.

a.LRUreplacement

b.FIFOreplacement

c.Optimalreplacement

d.Second-chancereplacement

Answer:

RankAlgorithmSufferfromBelady’sanomaly

1Optimalno

2LRUno

3Second-chanceyes

4FIFOyes

9.5Discussthehardwaresupportrequiredtosupportdemandpaging.

Answer:

Foreverymemory-accessoperation,thepagetableneedstobeconsulted

tocheckwhetherthecorrespondingpageisresidentornotandwhether

theprogramhasreadorwriteprivilegesforaccessingthepage.These

checkshavetobeperformedinhardware.ATLBcouldserveasacache

andimprovetheperformanceofthelookupoperation.

9.6Anoperatingsystemsupportsapagedvirtualmemory,usingacentral

processorwithacycletimeof1microsecond.Itcostsanadditional1

microsecondtoaccessapageotherthanthecurrentone.Pageshave1000

words,andthepagingdeviceisadrumthatrotatesat3000revolutions

perminuteandtransfers1millionwordspersecond.Thefollowing

statisticalmeasurementswereobtainedfromthesystem:

•1percentofallinstructionsexecutedaccessedapageotherthanthe

currentpage.

•

Oftheinstructionsthataccessedanotherpage,80percentaccessed

apagealreadyinmemory.PracticeExercises31

•

Whenanewpagewasrequired,thereplacedpagewasmodified50

percentofthetime.

Calculatetheeffectiveinstructiontimeonthissystem,assumingthatthe

systemisrunningoneprocessonlyandthattheprocessorisidleduring

drumtransfers.

Answer:

effectiveaccesstime=0.99×（1sec+0.008×（2sec）

+0.002×（10,000sec+1,000sec）

+0.001×（10,000sec+1,000sec）

=（0.99+0.016+22.0+11.0）sec

=34.0sec

9.7Considerthetwo-dimensionalarrayA:

intA[][]=newint[100][100];

whereA[0][0]isatlocation200inapagedmemorysystemwithpages

ofsize200.Asmallprocessthatmanipulatesthematrixresidesinpage

0（locations0to199）.Thus,everyinstructionfetchwillbefrompage0.

Forthreepageframes,howmanypagefaultsaregeneratedby

thefollowingarray-initializationloops,usingLRUreplacementand

assumingthatpageframe1containstheprocessandtheothertwo

areinitiallyempty?

a.for（intj=0;j<100;j++）

for（inti=0;i<100;i++）

A[i][j]=0;

b.for（inti=0;i<100;i++）

for（intj=0;j<100;j++）

A[i][j]=0;

Answer:

a.5,000

b.50

9.8Considerthefollowingpagereferencestring:

1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6.

Howmanypagefaultswouldoccurforthefollowingreplacement

algorithms,assumingone,two,three,four,five,six,orsevenframes?

Rememberallframesareinitiallyempty,soyourfirstuniquepageswill

allcostonefaulteach.

•

LRUreplacement

•FIFOreplacement

•

Optimalreplacement32Chapter9VirtualMemory

Answer:

NumberofframesLRUFIFOOptimal

1202020

2181815

3151611

410148

58107

67107

7777

9.9Supposethatyouwanttouseapagingalgorithmthatrequiresareference

bit（suchassecond-chancereplacementorworking-setmodel）,but

thehardwaredoesnotprovideone.Sketchhowyoucouldsimulatea

referencebitevenifonewerenotprovidedbythehardware,orexplain

whyitisnotpossibletodoso.Ifitispossible,calculatewhatthecost

wouldbe.

Answer:

Youcanusethevalid/invalidbitsupportedinhardwaretosimulatethe

referencebit.Initiallysetthebittoinvalid.Onfirstreferenceatraptothe

operatingsystemisgenerated.Theoperatingsystemwillsetasoftware

bitto1andresetthevalid/invalidbittovalid.

9.10Youhavedevisedanewpage-replacementalgorithmthatyouthinkmay

beoptimal.Insomecontortedtestcases,Belady’sanomalyoccurs.Isthe

newalgorithmoptimal?

Explainyouranswer.

Answer:

No.AnoptimalalgorithmwillnotsufferfromBelady’sanomalybecause

—bydefinition—anoptimalalgorithmreplacesthepagethatwillnot

beusedforthelongesttime.Belady’sanomalyoccurswhenapagereplacementalgorithmevictsapagethatwillbeneededintheimmediate

future.Anoptimalalgorithmwouldnothaveselectedsuchapage.

9.11Segmentationissimilartopagingbutusesvariable-sized“pages.”Define

twosegment-replacementalgorithmsbasedonFIFOandLRUpagereplacementschemes.Rememberthatsincesegmentsarenotthesame

size,thesegmentthatischosentobereplacedmaynotbebigenough

toleaveenoughconsecutivelocationsfortheneededsegment.Consider

strategiesforsystemswheresegmentscannotberelocated,andthose

forsystemswheretheycan.

Answer:

a.FIFO.Findthefirstsegmentlargeenoughtoaccommodatethe

incomingsegment.Ifrelocationisnotpossibleandnoonesegment

islargeenough,selectacombinationofsegmentswhosememories

arecontiguous,whichare“closesttothefirstofthelist”and

whichcanaccommodatethenewsegment.Ifrelocationispossible,

rearrangethememorysothatthefirstNsegmentslargeenoughfor

theincomingsegmentarecontiguousinmemory.Addanyleftover

spacetothefree-spacelistinbothcases.PracticeExercises33

b.LRU.Selectthesegmentthathasnotbeenusedforthelongest

periodoftimeandthatislargeenough,addinganyleftoverspace

tothefreespacelist.Ifnoonesegmentislargeenough,select

acombinationofthe“oldest”segmentsthatarecontiguousin

memory（ifrelocationisnotavailable）andthatarelargeenough.

Ifrelocationisavailable,rearrangetheoldestNsegmentstobe

contiguousinmemoryandreplacethosewiththenewsegment.

9.12Considerademand-pagedcomputersystemwherethedegreeofmultiprogrammingiscurrentlyfixedatfour.ThesystemwasrecentlymeasuredtodetermineutilizationofCPUandthepagingdisk.Theresults

areoneofthefollowingalternatives.Foreachcase,whatishappening?

CanthedegreeofmultiprogrammingbeincreasedtoincreasetheCPU

utilization?

Isthepaginghelping?

a.CPUutilization13percent;diskutilization97percent

b.CPUutilization87percent;diskutilization3percent

c.CPUutilization13percent;diskutilization3percent

Answer:

a.Thrashingisoccurring.

b.CPUutilizationissufficientlyhightoleavethingsalone,and

increasedegreeofmultiprogramming.

c.Increasethedegreeofmultiprogramming.

9.13Wehaveanoperatingsystemforamachinethatusesbaseandlimit

registers,butwehavemodifiedthemachinetoprovideapagetable.

Canthepagetablesbesetuptosimulatebaseandlimitregisters?

How

cantheybe,orwhycantheynotbe?

Answer:

Thepagetablecanbesetuptosimulatebaseandlimitregistersprovided

thatthememoryisallocatedinfixed-sizesegments.Inthisway,thebase

ofasegmentcanbeenteredintothepagetableandthevalid/invalidbit

usedtoindicatethatportionofthesegmentasresidentinthememory.

Therewillbesomeproblemwithinternalfragmentation.

9.27.Considerademand-pagingsystemwiththefollowingtime-measuredutilizations:

CPU utilization20%

Pagingdisk97.7%

Other I/O devices5%

Which（ifany）ofthefollowingwill（probably）improveCPUutilization?

Explainyouranswer.

a.Installafaster CPU.

b.Installabiggerpagingdisk.

c.Increasethedegreeofmultiprogramming.

d.Decreasethedegreeofmultiprogramming.

e.Installmoremainmemory.

f.Installafasterharddiskormultiplecontrollerswithmultipleharddisks.

g.Addprepagingtothepagefetchalgorithms.

h.Increasethepagesize.

Answer:

 Thesystemobviouslyisspendingmostofitstimepaging,indicatingover-allocation

ofmemory.Ifthelevelofmultiprogrammingisreducedresidentprocesses

wouldpagefaultlessfrequentlyandthe CPU utilizationwouldimprove.Anotherwayto

improveperformancewouldbetogetmorephysicalmemoryorafasterpagingdrum.

a.Getafaster CPU—No.

b.Getabiggerpagingdrum—No.

c.Increasethedegreeofmultiprogramming—No.

d.Decreasethedegreeofmultiprogramming—Yes.

e.Installmoremainmemory—Likelytoimprove CPU utilizationasmorepagescan

remainresidentandnotrequirepagingtoorfromthedisks.

f.I