计算机科学-hw操作系统概念课后习题答案-ch07

ImportSettings:

BaseSettings:BrownstoneDefault

HighestAnswerLetter:D

MultipleKeywordsinSameParagraph:No

Chapter:Chapter7

MultipleChoice

1.Adeadlockedstateoccurswhenever.

A)aprocessiswaitingforI/Otoadevicethatdoesnotexist

B)thesystemhasnoavailablefreeresources

C)everyprocessinasetiswaitingforaneventthatcanonlybecausedbyanotherprocessin

theset

D)aprocessisunabletoreleaseitsrequestforaresourceafteruse

Ans:C

Feedback:7.1

Difficulty:Medium

zOnenecessaryconditionfordeadlockiswhichstatesthatatleastoneresourcemustbe

inanonsharablemode.

heholdandwait

A)mutualexclusion

B)

c)circularwait

D)nopreemption

Ar

:B

Feedback:7.2.1

Difficulty:Medium

3.Onenecessaryconditionfordeadlockis,whichstatesthataprocessmustbeholding

oneresourceandwaitingtoacquireadditionalresources.

A)holdandwait

B)mutualexclusion

C)circularwait

D)nopreemption

Ans:A

Feedback:7.2.1

Difficulty:Easy

4.Onenecessaryconditionfordeadlockis,whichstatesthataresourcecanbereleased

onlyvoluntarilybytheprocessholdingtheresource.

A)holdandwait

B)mutualexclusion

C)circularwait

D)nopreemption

Ans:D

Feedback:7.2.1

Difficulty:Easy

5.Onenecessaryconditionfordeadlockis,whichstatesthatthereisachainofwaiting

processeswherebyPoiswaitingforaresourceheldbyPi,PiiswaitingforaresourceheldbyP2,

andPniswaitingforaresourceheldbyPo.

A)holdandwait

B)mutualexclusion

C)circularwait

D)nopreemption

Ans:C

Feedback:7.2.1

Difficulty:Easy

6

AThewitnesssoftwareproductisa.

lock-orderverifierthatusesmutual-exclusionlockstoprotectcriticalsections

B\

)

czmodelertodevelopresourceallocationgraphs

driverthatcanbeusedtopreventmutualexclusionfornonsharableresources

D\

l

zimplementationofthebanker'salgorithmavailableformostoperatingsystems

Ans:A

Feedback:7.4.4

Difficulty:Medium

7

AInasystemresource-allocationgraph,.

adirectededgefromaprocesstoaresourceiscalledanassignmentedge

B\

)

zadirectededgefromaresourcetoaprocessiscalledarequestedge

c\

1

7adirectededgefromaprocesstoaresourceiscalledarequestedge

D\

JNoneoftheabove

Ans:C

Feedback:7.2.2

Difficulty:Medium

8.Acycleinaresource-allocationgraphis.

A)anecessaryandsufficientconditionfbrdeadlockinthecasethateachresourcehasmore

thanoneinstance

B)anecessaryandsufficientconditionfbradeadlockinthecasethateachresourcehasexactly

oneinstance

C)asufficientconditionforadeadlockinthecasethateachresourcehasmorethanonce

instance

D)isneithernecessarynorsufficientforindicatingdeadlockinthecasethateachresourcehas

exactlyoneinstance

Ans:B

Feedback:7.2.2

Difficulty:Difficult

9.Tohandledeadlocks,operatingsystemsmostoften,

A\

J

Zpretendthatdeadlocksneveroccur

B\

!

/useprotocolstopreventoravoiddeadlocks

c\

!

/detectandrecoverfromdeadlocks

Dx

—

7Noneoftheabove

Ans:A

Feedback:7.3

Difficulty:Medium

uA

JWhichofthefollowingstatementsistrue?

AX

)

/Asafestateisadeadlockedstate.

B\

—

/Asafestatemayleadtoadeadlockedstate.

c\

—

D/Anunsafestateisnecessarily,andbydefinition,alwaysadeadlockedstate.

Anunsafestatemayleadtoadeadlockedstate.

Ans:D

Feedback:7.5.1

Difficulty:Medium

11.Supposethattherearetenresourcesavailabletothreeprocesses.Attime0,thefollowing

dataiscollected.Thetableindicatestheprocess,themaximumnumberofresourcesneededby

theprocess,andthenumberofresourcescurrentlyownedbyeachprocess.Whichofthe

followingcorrectlycharacterizesthisstate?

ProcessMaximumNeedsCuiTentlvOwned

Po104

Pl31

P264

AX

I

/Itissafe.

B\

1

7Itisnotsafe.

\

cl

z

DThestatecannotbedetermined.

Itisanimpossiblestate.

Ans:B

Feedback:7.5.1

Difficulty:Difficult

12.Supposethatthereare12resourcesavailabletothreeprocesses.Attime0,thefollowing

dataiscollected.Thetableindicatestheprocess,themaximumnumberofresourcesneededby

theprocess,andthenumberofresourcescurrentlyownedbyeachprocess.Whichofthe

followingcorrectlycharacterizesthisstate?

ProcessMaximumNeedsCurrentlyOwned

Po1()4

Pl32

AP274

Itissafe.

Bx

)

czItisnotsafe.

Thestatecannotbedetermined.

D\

l

zItisanimpossiblestate.

Ans:A

Feedback:7.5.1

Difficulty:Difficult

13.Whichofthefollowingdatastructuresinthebanker*salgorithmisavectoroflengthm,

wheremisthenumberofresourcetypes?

AX

I

/Need

B\

l

czAllocation

DMax

Available

Ans:D

Feedback:7.5.3

Difficulty:Easy

14.Assumetherearethreeresources,Ri,R2,and/?3,thatareeachassigneduniqueinteger

values15,10,and25,respectively.Whatisaresourceorderingwhichpreventsacircularwait?

A)/?i,/?2,R3

B)R3,/?2,R\

C)R3,Ri,Ri

D)R2,Ri,R3

Ans:D

Feedback:7.4.4

Difficulty:Medium

15.Acouldbepreemptedfromaprocess.

A)mutexlock

B)CPU

C)semaphore

D)filelock

Ans:B

Feedback:7.4.3

Difficulty:Medium

Essay

16.Explainwhathastohappenforasetofprocessestoachieveadeadlockedstate.

Ans:Forasetofprocessestoexistinadeadlockedstate,everyprocessinthesetmustbe

waitingforaneventthatcanbecausedonlybeanotherprocessintheset.Thus,theprocesses

cannoteverexitthisstatewithoutmanualintervention.

Feedback:7.1

Difficulty:Medium

17.Describethefourconditionsthatmustholdsimultaneouslyinasystemifadeadlockisto

occur.

Ans:Forasetofprocessestobedeadlocked:atleastoneresourcemustremainina

nonsharablemode,aprocessmustholdatleastoneresourceandbewaitingtoacquireadditional

resourcesheldbyotherprocesses,resourcesinthesystemcannotbepreempted,andacircular

waithastoexistbetweenprocesses.

Feedback:7.2.1

Difficulty:Medium

18.Whatarethethreegeneralwaysthatadeadlockcanbehandled?

Ans:Adeadlockcanbepreventedbyusingprotocolstoensurethatadeadlockwillnever

occur.Asystemmayallowadeadlocktooccur,detectit,andrecoverfromit.Lastly,an

operatingsystemmayjustignoretheproblemandpretendthatdeadlockscanneveroccur.

Feedback:7.3

Difficulty:Medium

19.Whatisthedifferencebetweendeadlockpreventionanddeadlockavoidance?

Ans:Deadlockpreventionisasetofmethodsforensuringthatatleastoneofthenecessary

conditionsfordeadlockcannothold.Deadlockavoidancerequiresthattheoperatingsystembe

given,inadvance,additionalinformationconcerningwhichresourcesaprocesswillrequestand

useduringitslifetime.

Feedback:7.4

Difficulty:Medium

20.Describetwoprotocolstoensurethatthehold-and-waitconditionneveroccursinasystem.

Ans:Oneprotocolrequireseachprocesstorequestandbeallocatedallitsresourcesbeforeit

beginsexecution.Wecanimplementthisprovisionbyrequiringthatsystemcallsrequesting

resourcesforaprocessprecedeallothersystemcalls.Analternativeprotocolallowsaprocessto

requestresourcesonlywhenithasnone.Aprocessmayrequestsomeresourcesandusethem.

Beforeitcanrequestanyadditionalresources,however,itmustreleaseailtheresourcesthatitis

currentlyallocated.

Feedback:7.4.2

Difficulty:Medium

21.Whatisonewaytoensurethatacircular-waitconditiondoesnotoccur?

Ans:Onewaytoensurethatthisconditionneverholdsistoimposeatotalorderingofall

resourcetypes,andtorequirethateachprocessrequestsresourcesinanincreasingorderof

enumeration.Thiscanbeaccomplishedbyassigningeachresourcetypeauniqueintegernumber

todeterminewhetheroneprecedesanotherintheordering.

Feedback:7.4.4

Difficulty:Medium

22.Whatdoesaclaimedgesignifyinaresource-allocationgraph?

Ans:Aclaimedgeindicatesthataprocessmayrequestaresourceatsometimeinthefuture.

Thisedgeresemblesarequestedgeindirection,butisrepresentedinthegraphbyadashedline.

Feedback:7.5.2

Difficulty:Medium

23.Describeawait-forgraphandhowitdetectsdeadlock.

Ans:Ifallresourceshaveonlyasingleinstance,thenwecandefineadeadlock-detection

algorithmthatusesavariantoftheresource-allocationgraph,calledawait-forgraph.Weobtain

thisgraphfromtheresource-allocationgraphbyremovingtheresourcenodesandcollapsingthe

appropriateedges.Todetectdeadlocks,thesystemneedstomaintainthewait-forgraphand

periodicallyinvokeanalgorithmthatsearchesforacycleinthegraph.

Feedback:7.6.1

Difficulty:Medium

24.Whatfactorsinfluencethedecisionofwhentoinvokeadetectionalgorithm?

Ans:Thefirstfactorishowoftenadeadlockislikelytooccur;ifdeadlocksoccurfrequently,

thedetectionalgorithmshouldbeinvokedfrequently.Thesecondfactorishowmanyprocesses

willbeaffectedbydeadlockwhenithappens;ifthedeadlock-detectionalgorithmisinvokedfor

everyresourcerequest,aconsiderableoverheadincomputationtimewillbeincurred.

Feedback:7.6,3

Difficulty:Medium

25.Describetwomethodsforeliminatingprocessesbyabortingaprocess.

Ans:Thefirstmethodistoabortalldeadlockedprocesses.Abortingalldeadlockedprocesses

willclearlybreakthedeadlockcycle;however,thedeadlockedprocessesmayhavetobe

computedforalongtime,andresultsofthesepartialcomputationsmustbediscardedandwill

probablyhavetoberecomputedlater.Thesecondmethodistoabortoneprocessatatimeuntil

thedeadlockcycleiseliminated.Abortingoneprocessatatimeincursconsiderableoverhead,

since,aftereachprocessisaborted,adeadlock-detectionalgorithmmustbeinvokedtodetermine

whetheranyprocessesarestilldeadlocked.

Feedback:7.7.1

Difficulty:Medium

26.Namethreeissuesthatneedtobeaddressedifapreemptionisrequiredtodealwith

deadlocks.

Ans:First,theorderofresourcesandprocessesthatneedtobepreemptedmustbedetermined

tominimizecost.Second,ifaresourceispreemptedfromaprocess,theprocessmustberolled

backtosomesafestateandrestartedfromthatstate.Thesimplestsolutionisatotalrollback.

Finally,wemustensurethatstarvationdoesnotoccurfromalwayspreemptingresourcesfrom

thesameprocess.

Feedback:7.7.2

Difficulty:Medium

27.Describehowasafestateensuresdeadlockwillbeavoided.

Ans:Asafestateensuresthatthereisasequenceofprocessestofinishtheirprogramexecution.

Deadlockisnotpossiblewhilethesystemisinasafestate.However,ifasystemgoesfroma

safestatetoanunsafestate,deadlockispossible.Onetechniqueforavoidingdeadlockisto

ensurethatthesystemalwaysstaysinasafestate.Thiscanbedonebyonlyassigningaresource

aslongasitmaintainsthesy