现代操作系统(第三版)答案

MODERN

OPERATING

SYSTEMS

THIRDEDITION

PROBLEMSOLUTIONS

AUM

VrijeUniversiteit

Amsterdam,TheNetherlands

PRENTICEHALL

UPPERSADDLERIVER,NJ07458

CopyrightPearsonEducation,Inc.2008

SOLUTIONSTOCHAPTER1PROBLEMS

rogrammingistherapidswitchingoftheCPUbetweenmultipleproc-

mmonlyusedtokeeptheCPUbusywhileoneor

moreprocessesaredoingI/O.

poolingisthetechniqueofreadinginjobs,forexample,fromcards,

ontothedisk,sothatwhenthecurrentlyexecutingprocessesarefinished,

spoolingconsistsoffirst

copyingprintablefilestodiskbeforeprintingthem,ratherthanprintingdi-

poolingonapersonalcomputerisnot

verylikely,butoutputspoolingis.

mereasonformultiprogrammingistogivetheCPUsomethingtodo

whilewaitingforI/eisnoDMA,theCPUisfullyoccu-

pieddoingI/O,sothereisnothingtobegained(atleastintermsofCPUutili-

zation)erhowmuchI/Oaprogramdoes,the

CPUwillbe100%courseassumesthemajordelayisthewait

ulddootherworkiftheI/Owereslowfor

otherreasons(arrivingonaserialline,forinstance).

mple,IntelmakesPentiumI,II,andIII,and4CPUs

withavarietyofdifferentpropertiesincludingspeedandpowerconsumption.

fferonlyin

priceandperformance,whichistheessenceofthefamilyidea.

5.A25×

1024×768pixel24-bitcolorbitmaprequires2,359,1980these

twooptionswouldhavecost$10and$11,520,rent

prices,checkonhowmuchRAMcurrentlycosts,probablylessthan$1/MB.

ssrequiresthateachprocessbeallo-

cateditsresourcesinafairway,withnoprocessgettingmorethanitsfair

therhand,realtimerequiresthatresourcesbeallocatedbased

-

timeprocessmaygetadisproportionateshareoftheresources.

s(a),(c),and(d)shouldberestrictedtokernelmode.

ake20,25or30msectocompletetheexecutionoftheseprograms

0andP1are

scheduledonthesameCPUandP2isscheduledontheotherCPU,itwill

0andP2arescheduledonthesameCPUandP1is

scheduledontheotherCPU,1andP2arescheduled

onthesameCPUandP0isscheduledontheotherCPU,itwilltake30msec.

IfallthreeareonthesameCPU,itwilltake35msec.

2

PROBLEMSOLUTIONSFORCHAPTER1

ansthe

notmatterat

allhowmanystagesthepipelinehas.A10-stagepipelinewith1nsecper

tmattersis

howoftenafinishedinstructionpopsouttheendofthepipeline.

eaccesstime=

0.95×2nsec(wordiscache)

+0.05×0.99×10nsec(wordisinRAM,butnotincache)

+0.05×0.01×10,000,000nsec(wordondiskonly)

=5002.395nsec

=5.002395μsec

uscriptcontains80×50×700=,of

course,impossibletofitintotheregistersofanycurrentlyavailableCPUand

istoobigfora1-MBcache,butifsuchhardwarewereavailable,the

manuscriptcouldbescannedin2.8msecfromtheregistersor5.8msecfrom

reapproximately27001024-byteblocksofdata,soscan-

ningfromthediskwouldrequireabout27seconds,andfromtape2minutes7

se,singand

rewritingthedatawouldincreasethetime.

allergetscontrolbackandimmediatelyoverwritesthedata,

whenthewritefinallyoccurs,r,ifthe

driverfirstcopiesthedatatoaprivatebufferbeforereturning,thenthecaller

rpossibilityistoallowthe

callertocontinueandgiveitasignalwhenthebuffermaybereused,butthis

istrickyanderrorprone.

nstructionswitchestheexecutionmodeofaCPUfromtheusermode

structionallowsauserprogramtoinvokefunc-

tionsintheoperatingsystemkernel.

rogramis

runagainandagain,thetrapwillalwaysoccuratexactlythesamepositionin

rruptiscausedbyanexternaleventandits

timingisnotreproducible.

cesstableisneededtostorethestateofaprocessthatiscurrently

suspended,tneededinasingleprocesssys-

tembecausethesingleprocessisneversuspended.

ngafilesystemmakesanyfilesalreadyinthemountpointdirectory

inaccessible,r,asystemadmin-

istratormightwanttocopysomeofthemostimportantfilesnormallylocated

inthemounteddirectorytothemountpointsotheycouldbefoundintheir

normalpathinanemergencywhenthemounteddevicewasbeingrepaired.

PROBLEMSOLUTIONSFORCHAPTER1

3

mcallallowsauserprocesstoaccessandexecuteoperatingsystem

ogramsusesystemcallstoinvokeoperat-

ingsystemservices.

18.

Fork

canfailiftherearenofreeslotsleftintheprocesstable(andpossiblyif

thereisnomemoryorswapspaceleft).

Exec

canfailifthefilenamegiven

doesnotexistorisnotavalidexecutablefile.

Unlink

canfailifthefiletobe

unlinkeddoesnotexistorthecallingprocessdoesnothavetheauthorityto

unlinkit.

allfails,forexamplebecausefdisincorrect,itcanreturn−

alsofailbecausethediskisfullanditisnotpossibletowritethenumberof

recttermination,italwaysreturnsnbytes.

ainsthebytes:1,5,9,2.

retrievethefile=

1*50ms(Timetomovethearmovertrack#50)

+5ms(Timeforthefirstsectortorotateunderthehead)

+10/100*1000ms(Read10MB)

=155ms

pecialfilesconsistofnumberedblocks,eachofwhichcanbereador

ssibletoseektoanyblock

notpossiblewithcharacterspecialfiles.

callsdonotreallyhavenames,otherthaninadocumentationsense.

Whenthelibraryprocedurereadtrapstothekernel,itputsthenumberofthe

mberisusedtoindexintoa

therhand,thename

ofthelibraryprocedureisveryimportant,sincethatiswhatappearsinthe

program.

an,especiallyifthekernelisamessage-passingsystem.

sprogramlogicisconcerneditdoesnotmatterwhetheracalltoali-

erformanceisanissue,ifa

taskcanbeaccomplishedwithoutasystemcalltheprogramwillrunfaster.

Everysystemcallinvolvesoverheadtimeinswitchingfromtheusercontext

rmore,onamultiusersystemtheoperatingsys-

temmayscheduleanotherprocesstorunwhenasystemcallcompletes,

furtherslowingtheprogressinrealtimeofacallingprocess.

l

UNIX

callshavenocounterpartintheWin32API:

Link:aWin32programcannotrefertoafilebyanalternativenameorseeit

,attemptingtocreatealinkisaconvenient

waytotestforandcreatealockonafile.

4

PROBLEMSOLUTIONSFORCHAPTER1

Mountandumount:aWindowsprogramcannotmakeassumptionsabout

standardpathnamesbecauseonsystemswithmultiplediskdrivesthedrive

namepartofthepathmaybedifferent.

Chmod:Windowsusesaccesscontrollists

Kill:Windowsprogrammerscannotkillamisbehavingprogramthatisnot

cooperating.

ystemarchitecturehasitsownsetofinstructionsthatitcanexecute.

ThusaPentiumcannotexecuteSPARCprogramsandaSPARCcannotexe-

,differentarchitecturesdifferinbusarchitecture

used(suchasVME,ISA,PCI,MCA,SBus,...)aswellasthewordsizeofthe

CPU(usually32or64bit).Becauseofthesedifferencesinhardware,itisnot

y

portableoperatingsystemwillconsistoftwohigh-levellayers---amachine-

hine-dependent

layeraddressesthespecificsofthehardware,andmustbeimplementedsepa-

yerprovidesauniforminterfaceonwhich

hine-independentlayerhasto

ghlyportable,thesizeofthemachine-

dependentlayermustbekeptassmallaspossible.

tionofpolicyandmechanismallowsOSdesignerstoimplementa

rimitivesaresim-

plified,nthen

beusedtoimplementmorecomplexmechanismsandpoliciesattheuser

level.

versionsarestraightforward:

(a)Amicroyearis10

−6

×365×24×3600=31.536sec.

(b)1000metersor1km.

(c)Thereare2

40

bytes,whichis1,099,511,627,776bytes.

(d)Itis6×10

24

kg.

SOLUTIONSTOCHAPTER2PROBLEMS

ethataprocess

isblockedonI/OandtheI/OfiPUisotherwiseidle,theproc-

ermissingtransition,

fromreadytoblocked,processcannotdoI/Oorany-

unningprocesscanblock.

PROBLEMSOLUTIONSFORCHAPTER2

5

ldhavearegistercontainingapointertothecurrentprocesstable

/Ocompleted,theCPUwouldstorethecurrentmachinestatein

wouldgototheinterruptvectorforthe

interruptingdeviceandfetchapointertoanotherprocesstableentry(theser-

viceprocedure).Thisprocesswouldthenbestartedup.

lly,high-levellanguagesdonotallowthekindofaccesstoCPUhard-

tance,aninterrupthandlermayberequiredto

enableanddisabletheinterruptservicingaparticulardevice,ortomanipulate

datawithinaprocess’,interruptserviceroutinesmustexe-

cuteasrapidlyaspossible.

,youdonotwanttheoperatingsystemtocrashbe-

causeapoorlywrittenuserprogramdoesnotallowforenoughstackspace.

Second,ifthekernelleavesstackdatainauserprogram’smemoryspace

uponreturnfromasystemcall,amalicioususermightbeabletousethisdata

tofindoutinformationaboutotherprocesses.

jobhas50%I/Owait,thenitwilltake20minutestocompleteinthe

equentially,thesecondonewillfinish40

minutesafterthefiojobs,theapproximateCPUutiliza-

tionis1−0.5

2

.Thuseachonegets0.375CPUminuteperminuteofreal

mulate10minutesofCPUtime,ajobmustrunfor10/0.375

minutes,nningsequentiallythejobsfinish

after40minutes,butrunninginparalleltheyfinishafter26.67minutes.

dbedifficult,ifnotimpossible,tokeepthefi-

posethataclientprocesssendsarequesttoserverprocess1toupdateafile.

ythereafter,anoth-

erclientprocesssendsarequesttoserver2toreadthatfiunately,if

thefileisalsocachedthere,server2,initsinnocence,willreturnobsolete

firstprocesswritesthefilethroughtothediskaftercachingit,

andserver2checksthediskoneveryreadtoseeifitscachedcopyisup-to-

date,thesystemcanbemadetowork,butitispreciselyallthesediskac-

cessesthatthecachingsystemistryingtoavoid.

gle-threadedprocessisblockedonthekeyboard,itcannotfork.

user-levelthreadsarebeingused,thisactionwillblocktheentireprocess,

isessentialthatkernelthreads

areusedtopermitsomethreadstoblockwithoutaffectingtheothers.

erverisentirelyCPUbound,thereisnoneedtohavemultiple

ample,consideratele-

phonedirectoryassistancenumber(like555-1212)foranareawith1million

6

PROBLEMSOLUTIONSFORCHAPTER2

(name,telephonenumber)recordis,say,64characters,the

entiredatabasetakes64megabytes,andcaneasilybekeptintheserver’s

memorytoprovidefastlookup.

hreadisstopped,stbesaved,

ro-

grammingthreadsisnodifferentthanmultiprogrammingprocesses,soeach

threadneedsitsownregistersavearea.

d-

ingisneededforthegoodoftheapplication,

all,itisusuallythesameprogrammerwhowritesthecodeforallofthem.

-levelthreadscannotbepreemptedbytheclockunlessthewholeproc-

ess’-levelthreadscanbepreemptedindivi-

attercase,ifathreadrunstoolong,theclockwillinterruptthe

nelisfreetopickadif-

ferentthreadfromthesameprocesstorunnextifitsodesires.

ingle-threadedcase,thecachehitstake15msecandcachemissestake

ghtedaverageis2/3×15+1/3×emeanre-

ltithreaded

server,allthewaitingforthediskisoverlapped,soeveryrequesttakes15

msec,andtheservercanhandle662/3requestspersecond.

gestadvantageistheeffistothekernelareneededto

gestdisadvantageisthatifonethreadblocks,theen-

tireprocessblocks.

,achcalltopthread

本文标签： 套用 函数