操作系统精髓与设计原理第五版课后题答案

OperatingSystem

Overview

ReviewQuestions

Convenience:Anoperatingsystemmakesacomputermoreconvenienttouse.Efficiency:Anoperatingsystemallowsthecomputersystemresourcestobeusedinanefficientmanner.Abilitytoevolve:Anoperatingsystemshouldbeconstructedinsuchawayastopermittheeffectivedevelopment,testing,andintroductionofnewsystemfunctionswithoutinterferingwithservice.

Theexecutioncontext,orprocessstate,istheinternaldatabywhichtheoperatingsystemisabletosuperviseandcontroltheprocess.Thisinternalinformationisseparatedfromtheprocess,becausetheoperatingsystemhasinformationnotpermittedtotheprocess.Thecontextincludesalloftheinformationthattheoperatingsystemneedstomanagetheprocessandthattheprocessorneedstoexecutetheprocessproperly.Thecontextincludesthecontentsofthevariousprocessorregisters,suchastheprogramcounteranddataregisters.Italsoincludesinformationofusetotheoperatingsystem,suchasthepriorityoftheprocessandwhethertheprocessiswaitingforthecompletionofaparticularI/Oevent.

Problems

Theanswersarethesamefor(a)and(b).Assumethatalthoughprocessoroperationscannotoverlap,I/Ooperationscan.

1Job:

TAT

=NT

Processorutilization

=50%

2Jobs:

TAT

=NT

Processorutilization

=100%

4Jobs:

TAT

=(2N-1)NT

Processorutilization

=100%

Asystemcallisusedbyanapplicationprogramtoinvokeafunctionprovidedbytheoperatingsystem.Typically,thesystemcallresultsintransfertoasystemprogramthatrunsinkernelmode.

Processdescriptionand

Control

ReviewQuestions

3.5Swappinginvolvesmovingpartorallofaprocessfrommainmemorytodisk.WhennoneoftheprocessesinmainmemoryisintheReadystate,theoperatingsystemswapsoneoftheblockedprocessesoutontodiskintoasuspendqueue,sothatanotherprocessmaybebroughtintomainmemorytoexecute.

3.10Theusermodehasrestrictionsontheinstructionsthatcanbeexecutedandthememoryareasthatcanbeaccessed.Thisistoprotecttheoperatingsystemfromdamageoralteration.Inkernelmode,theoperatingsystemdoesnothavetheserestrictions,sothatitcanperformitstasks.

Problems

3.1*Creationanddeletionofbothuserandsystemprocesses.Theprocessesinthesystemcanexecuteconcurrentlyforinformationsharing,computationspeedup,modularity,andconvenience.Concurrentexecutionrequiresamechanismforprocesscreationanddeletion.Therequiredresourcesaregiventotheprocesswhenitiscreated,orallocatedtoitwhileitisrunning.Whentheprocessterminates,theOSneedstoreclaimanyreusableresources.

•Suspensionandresumptionofprocesses.Inprocessscheduling,theOSneedstochangetheprocess'sstatetowaitingorreadystatewhenitiswaitingforsomeresources.Whentherequiredresourcesareavailable,OSneedstochangeitsstatetorunningstatetoresumeitsexecution.

•Provisionofmechanismforprocesssynchronization.Cooperatingprocessesmaysharedata.Concurrentaccesstoshareddatamayresultindatainconsistency.OShastoprovidemechanismsforprocessessynchronizationtoensuretheorderlyexecutionofcooperatingprocesses,sothatdataconsistencyismaintained.

•Provisionofmechanismforprocesscommunication.TheprocessesexecutingundertheOSmaybeeitherindependentprocessesorcooperatingprocesses.Cooperatingprocessesmusthavethemeanstocommunicatewitheachother.

•Provisionofmechanismsfordeadlockhandling.Inamultiprogrammingenvironment,severalprocessesmaycompeteforafinitenumberofresources.Ifadeadlockoccurs,allwaitingprocesseswillneverchangetheirwaitingstatetorunningstateagain,resourcesarewastedandjobswillneverbecompleted.

3.3Figure9.3showstheresultforasingleblockedqueue.Thefigurereadilygeneralizestomultipleblockedqueues.

Processdescriptionand

Control

ReviewQuestions

Lessstateinformationisinvolved.

Addressspace,fileresources,executionprivilegesareexamples.

1.Threadswitchingdoesnotrequirekernelmodeprivilegesbecauseallofthethreadmanagementdatastructuresarewithintheuseraddressspaceofasingleprocess.Therefore,theprocessdoesnotswitchtothekernelmodetodothreadmanagement.Thissavestheoverheadoftwomodeswitches(usertokernel;kernelbacktouser).2.Schedulingcanbeapplicationspecific.Oneapplicationmaybenefitmostfromasimpleround-robinschedulingalgorithm,whileanothermightbenefitfromapriority-basedschedulingalgorithm.TheschedulingalgorithmcanbetailoredtotheapplicationwithoutdisturbingtheunderlyingOSscheduler.3.ULTscanrunonanyoperatingsystem.NochangesarerequiredtotheunderlyingkerneltosupportULTs.Thethreadslibraryisasetofapplication-levelutilitiessharedbyallapplications.

1.Inatypicaloperatingsystem,manysystemcallsareblocking.Thus,whenaULTexecutesasystemcall,notonlyisthatthreadblocked,butalsoallofthethreadswithintheprocessareblocked.2.InapureULTstrategy,amultithreadedapplicationcannottakeadvantageofmultiprocessing.Akernelassignsoneprocesstoonlyoneprocessoratatime.Therefore,onlyasinglethreadwithinaprocesscanexecuteatatime.

Problems

Because,withULTs,thethreadstructureofaprocessisnotvisibletotheoperatingsystem,whichonlyschedulesonthebasisofprocesses.

CONCURRENCY:MUTUAL

EXCLUSIONAND

Synchronization

ReviewQuestions

Communicationamongprocesses,sharingofandcompetingforresources,synchronizationoftheactivitiesofmultipleprocesses,andallocationofprocessortimetoprocesses.

Abinarysemaphoremayonlytakeonthevalues0and1.Ageneralsemaphoremaytakeonanyintegervalue.

Problems

ABCDE;ABDCE;ABDEC;ADBCE;ADBEC;ADEBC;

DEABC;DAEBC;DABEC;DABCE

Considerthecaseinwhichturnequals0andP(1)setsblocked[1]totrueandthenfindsblocked[0]settofalse.P(0)willthensetblocked[0]totrue,findturn=0,andenteritscriticalsection.P(1)willthenassign1toturnandwillalsoenteritscriticalsection.

CONCURRENCY:DEADLOCKAND

Starvation

ReviewQuestions

Mutualexclusion.Onlyoneprocessmayusearesourceatatime.Holdandwait.Aprocessmayholdallocatedresourceswhileawaitingassignmentofothers.Nopreemption.Noresourcecanbeforciblyremovedfromaprocessholdingit.

Theabovethreeconditions,plus:Circularwait.Aclosedchainofprocessesexists,suchthateachprocessholdsatleastoneresourceneededbythenextprocessinthechain.

Problems

a.0000

0750

6622

2002

0320

b.tod.Runningthebanker'salgorithm,weseeprocessescanfinishintheorderpl,p4,p5,p2,p3.

e.Changeavailableto(2,0,0,0)andp3'srowof"stillneeds"to(6,5,2,2).Nowpl,p4,p5canfinish,butwithavailablenow(4,6,9,8)neitherp2norp3's"stillneeds"canbesatisfied.Soitisnotsafetograntp3'srequest.

1.W=(2100)

MarkP3; W=(2100)+(0120)=(2220)

MarkP2; W=(2220)+(2001)=(4221)

MarkP1; nodeadlockdetected

MemoryManagement

ReviewQuestions

Relocation,protection,sharing,logicalorganization,physicalorganization.

Alogicaladdressisareferencetoamemorylocationindependentofthecurrentassignmentofdatatomemory;atranslationmustbemadetoaphysicaladdressbeforethememoryaccesscanbeachieved.Arelativeaddressisaparticularexampleoflogicaladdress,inwhichtheaddressisexpressedasalocationrelativetosomeknownpoint,usuallythebeginningoftheprogram.Aphysicaladdress,orabsoluteaddress,isanactuallocationinmainmemory.

Problems

a.The40Mblockfitsintothesecondhole,withastartingaddressof80M.The20Mblockfitsintothefirsthole,withastartingaddressof20M.The10Mblockisplacedatlocation120M.

zmnii□□

<540M40MggSg 60M 40Mg30M40M40M

曷曷 一—Ri 演

Thethreestartingaddressesare230M,20M,and160M,forthe40M,20M,and10Mblocks,respectively.

4040 40M 60Mg60 60M 40M白30M40M 40M

Thethreestartingaddressesare80M,120M,and160M,forthe40M,20M,and10Mblocks,respectively.

7.12a.Thenumberofbytesinthelogicaladdressspaceis(216pages)(210

bytes/page)=226bytes.Therefore,26bitsarerequiredforthelogicaladdress.

Aframeisthesamesizeasapage,210bytes.

Thenumberofframesinmainmemoryis(232bytesofmain

memory)/(2i0bytes/frame)=222frames.So22bitsisneededtospecifytheframe.

Thereisoneentryforeachpageinthelogicaladdressspace.Thereforethereare216entries.

Inadditiontothevalid/invalidbit,22bitsareneededtospecifytheframelocationinmainmemory,foratotalof23bits.

马马40M 40M£g60M 40Mg30M40M 40M

d.Thethreestartingaddressesare80M,230M,and360M,forthe40M,20M,and10Mblocks,respectively.

Chapter8

VirtualMemory

ReviewQuestions

Simplepaging:allthepagesofaprocessmustbeinmainmemoryforprocesstorun,unlessoverlaysareused.Virtualmemorypaging:notallpagesofaprocessneedbeinmainmemoryframesfortheprocesstorun.;pagesmaybereadinasneeded

Aphenomenoninvirtualmemoryschemes,inwhichtheprocessorspendsmostofitstimeswappingpiecesratherthanexecutinginstructions.

Problems

a.Splitbinaryaddressintovirtualpagenumberandoffset;useVPNasindexintopagetable;extractpageframenumber;concatenateoffsettogetphysicalmemoryaddress

b.(i) 1052=1024+28mapstoVPN1inPFN7,(7x1024+28=7196)

2221=2x1024+173mapstoVPN2,pagefault

5499=5x1024+379mapstoVPN5inPFN0,(0x1024+379=379)

8.4a.PFN3sinceloadedlongestagoattime20

PFN1sincereferencedlongestagoattime160

ClearRinPFN3(oldestloaded),clearRinPFN2(nextoldestloaded),victimPFNis0sinceR=0

ReplacethepageinPFN3sinceVPN3(inPFN3)isusedfurthestinthefuture

e.There

are6faults,indicatedby*

* * * * * *

40002421032

VPNofpagesinmemoryinLRUorder

34000242103203444024210

2 0 3 3 0 0 4 2 1

12 42

Uniprocessor

Scheduling

ReviewQuestions

Long-termscheduling:Thedecisiontoaddtothepoolofprocessestobeexecuted.Medium-termscheduling:Thedecisiontoaddtothenumberofprocessesthatarepartiallyorfullyinmainmemory.Short-termscheduling:Thedecisionastowhichavailableprocesswillbeexecutedbytheprocessor

Turnaroundtimeisthetotaltimethatarequestspendsinthesystem(waitingtimeplusservicetime.Responsetimeistheelapsedtimebetweenthesubmissionofarequestuntiltheresponsebeginstoappearasoutput.

Problems

Eachsquarerepresentsonetimeunit;thenumberinthesquarereferstothecurrently-runningprocess.

FCFS

A

A

A

B

B

B

B

B

C

C

D

D

D

D

D

E

E

E

E

E

RR,q=1

A

B

A

B

C

A

B

C

B

D

B

D

E

D

E

D

E

D

E

E

RR,q=4

A

A

A

B

B

B

B

C

C

B

D

D

D

D

E

E

E

E

D

E

SPN

A

A

A

C

C

B

B

B

B

B

D

D

D

D

D

E

E

E

E

E

SRT

A

A

A

C

C

B

B

B

B

B

D

D

D

D

D

E

E

E

E

E

HRRN

A

A

A

B

B

B

B

B

C

C

D

D

D

D

D

E

E

E

E

E

Feedback,q=1

A

B

A

C

B

C

A

B

B

D

B

D

E

D

E

D

E

D

E

E

Feedback,q=2i

A

B

A

A

C

B

B

C

B

B

D

D

E

D

D

E

E

D

E

E

A

B

C

D

E

Ta

0

1

3

9

12

Ts

3

5

2

5

5

FCFS

Tf

3

8

10

15

20

Tr

3.00

7.00

7.00

6.00

8.00

6.20

Tr"s

1.00

1.40

3.50

1.20

1.60

1.74

RRq=1

Tf

6.00

11.00

8.00

18.00

20.00

Tr

6.00

10.00

5.00

9.00

8.00

7.60

Tr"s

2.00

2.00

2.50

1.80

1.60

1.98

RRq=4

Tf

3.00

10.00

9.00

19.00

20.00

Tr

3.00

9.00

6.00

10.00

8.00

7.20

Tr"s

1.00

1.80

3.00

2.00

1.60

1.88

SPN

Tf

3.00

10.00

5.00

15.00

20.00

Tr

3.00

9.00

2.00

6.00

8.00

5.60

Tr"s

1.00

1.80

1.00

1.20

1.60

1.32

SRT

Tf

3.00

10.00

5.00

15.00

20.00

Tr

3.00

9.00

2.00

6.00

8.00

5.60

Tr"s

1.00

1.80

1.00

1.20

1.60

1.32

HRRN

Tf

3.00

8.00

10.00

15.00

20.00

Tr

3.00

7.00

7.00

6.00

8.00

6.20

Tr"s

1.00

1.40

3.50

1.20

1.60

1.74

FBq=1

Tf

7.00

11.00

6.00

18.00

20.00

Tr

7.00

10.00

3.00

9.00

8.00

7.40

Tr"s

2.33

2.00

1.50

1.80

1.60

1.85

FB

Tf

4.00

10.00

8.00

18.00

20.00

q=2i

Tr

4.00

9.00

5.00

9.00

8.00

7.00

Tr"s

1.33

1.80

2.50

1.80

1.60

1.81

9.16a.Sequencewithwhichprocesseswillget1minofprocessortime:

1

2

3

4

5

Elapsedtime

A

B

C

D

E

5

A

B

C

D

E

10

A

B

C

D

E

15

A

B

D

E

19

A

B

D

E

23

A

B

D

E

27

A

B

E

30

A

B

E

33

A

B

E

36

A

E

38

A

E

40

A

E

42

A

43

A

44

A

45

Theturnaroundtimeforeachprocess:

A=45min,B=35min,C=13min,D=26min,E=42min

Theaverageturnaroundtimeis=(45+35+13+26+42)/5=32.2min

b.

Theaverageturnaroundtimeis:

(9+21+36+39+45)/5=30min

Priority

Job

TurnaroundTime

3

B

9

4

E

9+12=21

6

A

21+15=36

7

C

36+3=39

9

D

39+6=45

c.

JobTurnaroundTime

A

15

B

15+9=24

C

24+3=27

D

27+6=33

E

33+12=45

Theaverageturnaroundtimeis:(15+24+27+33+45)/5=28.8min

d.

RunningJobTurnaroundTime

Time

Theaverageturnaroundtimeis:

(3+9+18+30+45)/5=21min

3

C

3

6

D

3+6=9

9

B

9+9=18

12

E

18+12=30

15

A

30+15=45

Multiprocessorandreal-TimeScheduling

ReviewQuestions

Fine：Parallelisminherentinasingleinstructionstream.Medium:Parallelprocessingormultitaskingwithinasingleapplication.Coarse:Multiprocessingofconcurrentprocessesinamultiprogrammingenvironment.VeryCoarse:Distributedprocessingacrossnetworknodestoformasinglecomputingenvironment.Independent:Multipleunrelatedprocesses.

Ahardreal-timetaskisonethatmustmeetitsdeadline;otherwiseitwillcauseundesirabledamageorafatalerrortothesystem.Asoftreal-timetaskhasanassociateddeadlinethatisdesirablebutnotmandatory;itstillmakessensetoscheduleandcompletethetaskevenifithaspasseditsdeadline.

Problems

Forfixedpriority,wedothecaseinwhichthepriorityisA,B,C.Eachsquarerepresentsfivetimeunits;theletterinthesquarereferstothecurrently-runningprocess.Thefirstrowisfixedpriority;thesecondrowisearliestdeadlineschedulingusingcompletiondeadlines.

A

A

B

B

A

A

C

C

A

A

B

B

A

A

C

C

A

A

A

A

B

B

A

C

C

A

C

A

A

B

B

A

A

C

C

C

A

A

Forfixedpriorityscheduling,processCalwaysmissesitsdeadline.

10.4

T1

slocked

byT

Tt3

slocked

byT

1sunlocked

sunlocked

[Inormalexecution

executionincriticalsection

OnceT3entersitscriticalsection,itisassignedapriorityhigherthanT1.

WhenT3leavesitscriticalsection,itispreemptedbyT/

I/OManagementandDiskScheduling

ReviewQuestions

ProgrammedI/O:TheprocessorissuesanI/Ocommand,onbehalfofaprocess,toanI/Omodule;thatprocessthenbusy-waitsfortheoperationtobecompletedbeforeproceeding.Interrupt-drivenI/O:TheprocessorissuesanI/Ocommandonbehalfofaprocess,continuestoexecutesubsequentinstructions,andisinterruptedbytheI/Omodulewhenthelatterhascompleteditswork.Thesubsequentinstructionsmaybeinthesameprocess,ifitisnotnecessaryforthatprocesstowaitforthecompletionoftheI/O.Otherwise,theprocessissuspendedpendingtheinterruptandotherworkisperformed.Directmemoryaccess(DMA):ADMAmodulecontrolstheexchangeofdatabetweenmainmemoryandanI/Omodule.TheprocessorsendsarequestforthetransferofablockofdatatotheDMAmoduleandisinterruptedonlyaftertheentireblockhasbeentransferred.

Seektime,rotationaldelay,accesstime.

Problems

IfthecalculationtimeexactlyequalstheI/Otime(whichisthemostfavorablesituation),boththeprocessorandtheperipheraldevicerunningsimultaneouslywilltakehalfaslongasiftheyranseparately.Formally,letCbethecalculationtimefortheentireprogramandletTbethetotalI/Otimerequired.Thenthebestpossiblerunningtimewithbufferingismax(C,T),whiletherunningtimewithoutbufferingisC+T;andofcourse((C+T)/2)<max(C,T)<(C+T).Source:[KNUT97].

Diskheadisinitiallymovinginthedirectionofdecreasingtracknumber:

FIFO

SSTF

SCAN

C-SCAN

Nexttrack

Number

Nexttrack

Number

Nexttrack

Number

Nexttrack

Number

accessed

oftracks

accessed

oftracks

accessed

oftracks

accessed

oftracks

traversed

traversed

traversed

traversed

27

73

110

10

64

36

64

36

129

102

120

10

41

23

41

23

110

19

129

9

27

14

27

14

186

76

147

18

10

17

10

17

147

39

186

39

110

100

186

176

41

106

64

122

120

10

147

39

10

31

41

23

129

9

129

18

64

54

27

14

147

18

120

9

120

56

10

17

186

39

110

10

Average

61.8

Average

29.1

Average

29.6

Average

38

Ifthediskheadisinitiallymovinginthedirectionofincreasingtracknumber,onlytheSCANandC-SCANresultschange:

SCAN C-SCAN

Nexttrack

Number

Nexttrack

Number

accessed

oftracks

accessed

oftracks

traversed

traversed

110

10

110

10

120

10

120

10

129

9

129

9

147

18

147

18

186

39

186

39

64

122

10

176

41

23

27

17

27

14

41

14

10

17

64

23

Average

29.1

Average

35.1

FileManagement

ReviewQuestions

Afieldisthebasicelementofdatacontainingasinglevalue.Arecordisacollectionofrelatedfieldsthatcanbetreatedasaunitbysomeapplicationprogram.

Pile:Dataarecollectedintheorderinwhichtheyarrive.Eachrecordconsistsofoneburstofdata.Sequentialfile:Afixedformatisusedforrecords.Allrecordsareofthesamelength,consistingofthesamenumberoffixed-lengthfieldsinaparticularorder.Becausethelengthandpositionofeachfieldisknown,onlythevaluesoffieldsneedtobestored;thefieldnameandlengthforeachfield