ThinkOS
ABriefIntroductiontoOperatingSystems
Version0.7.4
ThinkOS
ABriefIntroductiontoOperatingSystems
Version0.7.4
AllenB.DowneyGreenTeaPress
Needham,Massachusetts
Copyright©2015AllenB.Downey.
GreenTeaPress9WashburnAveNeedhamMA02492Permissionisgrantedtocopy,distribute,and/ormodifythisdocumentunderthetermsoftheCreativeCommonsAttribution-NonCommercial-ShareAlike4.0InternationalLicense,whichisavailableat/licenses/by-nc-sa/4.0/.
TheLATEXsourceforthisbookisavailablefrom/thinkos.
Preface
Inputerscienceprograms,OperatingSystemsisanic.Bythetimestudentstakeit,theyknowhowtoprograminC,andtheyhaveprobablytakenaclassinComputerArchitecture.Usuallythegoaloftheclassistoexposestudentstothedesignandimplementationofoperatingsystems,withtheimpliedassumptionthatsomeofthemwilldoresearchinthisarea,orwritepartofanOS.
Thisbookisintendedforadifferentaudience,andithasdifferentgoals.IdevelopeditforaclassatOlinCollegecalledSoftwareSystems.
MoststudentstakingthisclasslearnedtoprograminPython,sooneofthegoalsistohelpthemlearnC.Forthatpartoftheclass,IuseGriffithsandGriffiths,HeadFirstC,fromO’ReillyMedia.Thisbookismeantplementthatone.
Fewofmystudentswilleverwriteanoperatingsystem,butmanyofthemwillwritelow-levelapplicationsinCorworkonembeddedsystems.Myclassincludesmaterialfromoperatingsystems,works,databases,andembeddedsystems,butitemphasizesicsprogrammersneedtoknow.
ThisbookdoesnotassumethatyouhavestudiedComputerArchitecture.Aswegoalong,Iwillexplainwhatweneed.
Ifthisbookisessful,itshouldgiveyouabetterunderstandingofwhatishappeningwhenprogramsrun,andwhatyoucandotomakethemrunbetterandfaster.
Chapter1explainssomeofthedifferencespiledandinterpretedlanguages,withsomeinsightintopilerswork.mendedreading:HeadFirstCChapter1.
Chapter2explainshowtheoperatingsystemusesprocessestoprotectrunningprogramsfrominterferingwitheachother.
Chapter3explainsvirtualmemoryandaddresstranslation.mendedreading:HeadFirstCChapter2.
vi
Chapter0.Preface
Chapter4isaboutfilesystemsanddatastreams.mendedreading:HeadFirstCChapter3.
Chapter5describeshownumbers,letters,andothervaluesareencoded,andpresentsthebitwiseoperators.
Chapter6explainshowtousedynamicmemorymanagement,andhowitworks.mendedreading:HeadFirstCChapter6.
Chapter7isaboutcachingandthememoryhierarchy.
Chapter8isaboutmultitaskingandscheduling.
Chapter9isaboutPOSIXthreadsandmutexes.mendedreading:HeadFirstCChapter12andLittleBookofSemaphoresChapters1and2.
Chapter10isaboutPOSIXconditionvariablesandtheproducer/consumerproblem.mendedreading:LittleBookofSemaphoresChapters3and4.
Chapter11isaboutusingPOSIXsemaphoresandimplementingsemaphoresinC.
Anoteonthisdraft
Thecurrentversionofthisbookisanearlydraft.WhileIamworkingonthetext,Ihavenotyetincludedthefigures.Sothereareafewplaceswhere,I’msure,theexplanationwillbegreatlyimprovedwhenthefiguresareready.
0.1Usingthecode
Examplecodeforthisbookisavailablefrom/AllenDowney/ThinkOS.Gitisaversioncontrolsystemthatallowsyoutokeeptrackofthefilesthatmakeupaproject.AcollectionoffilesunderGit’scontroliscalledarepository.GitHubisahostingservicethatprovidesstorageforGitrepositoriesandaconvenientwebinterface.
TheGitHubhomepageformyrepositoryprovidesseveralwaystoworkwiththecode:
YoucancreateacopyofmyrepositoryonGitHubbypressingtheForkbutton.Ifyoudon’talreadyhaveaGitHubount,you’llneedtocreateone.Afterforking,you’llhaveyourownrepositoryonGitHub
0.1.Usingthecode
vii
thatyoucanusetokeeptrackofcodeyouwritewhileworkingonthisbook.Thenyoucanclonetherepo,whichmeansthatyoucopythefilestoputer.
Oryoucouldclonemyrepository.Youdon’tneedaGitHubounttodothis,butyouwon’tbeabletowriteyourchangesbacktoGitHub.
Ifyoudon’twanttouseGitatall,youcandownloadthefilesinaZipfileusingthebuttoninthelower-rightcorneroftheGitHubpage.
ContributorList
Ifyouhaveasuggestionorcorrection,pleasesendemailtodowney@.IfImakeachangebasedonyourfeedback,Iwilladdyoutothecontributorlist(unlessyouasktobeomitted).
Ifyouincludeatleastpartofthesentencetheerrorappearsin,thatmakesiteasyformetosearch.Pageandsectionnumbersarefine,too,butnotquiteaseasytoworkwith.Thanks!
IamgratefultothestudentsinSoftwareSystemsatOlinCollege,whotestedanearlydraftofthisbookinSpring2014.Theycorrectedmanyerrorsandmademanyhelpfulsuggestions.Iappreciatetheirpioneeringspirit!
JamesPGiannoulesspottedacopy-and-pasteerror. AndyEngleknowsthedifferencebetweenGBandGiB. AashishKarkinotedsomebrokensyntax. OtherpeoplewhofoundtyposanderrorsincludeJimTyson,DonaldRobertson,JeremyVermast,YuzhongHuang,IanHill. viii Chapter0.Preface Contents Preface v 0.1Usingthecode..........................vi 1Compilation
1 1.1Compiledandinterpretedlanguages..............1 1.2Statictypes...........................1 1.3pilationprocess....................3 1.4Objectcode...........................4 1.5Assemblycode..........................5 1.6Preprocessing..........................6 1.7Understandingerrors......................6 2Processes
9 2.1Abstractionandvirtualization.................9 2.2Isolation.............................10 2.3UNIXprocesses.........................12 3Virtualmemory 15 3.1Abitofinformationtheory...................15 3.2Memoryandstorage......................16 3.3Addressspaces.........................16 x Contents 3.4Memorysegments........................173.5Staticlocalvariables......................203.6Addresstranslation.......................20 4Filesandfilesystems 23 4.1Diskperformance........................25 4.2Diskmetadata..........................27 4.3Blockallocation.........................28 4.4Everythingisafile?
.......................28 5Morebitsandbytes 31 5.1Representingintegers......................31 5.2Bitwiseoperators........................32 5.3Representingfloating-pointnumbers..............33 5.4Unionsandmemoryerrors...................35 5.5Representingstrings.......................36 6Memorymanagement 39 6.1Memoryerrors..........................39 6.2Memoryleaks..........................41 6.3Implementation.........................43 7Caching 45 7.1Howprogramsrun.......................45 7.2Cacheperformance.......................47 7.3Locality.............................47 7.4Measuringcacheperformance.................48 7.5Programmingforcacheperformance..............51 7.6Thememoryhierarchy.....................52 7.7Cachingpolicy..........................53 7.8Paging..............................54 Contents xi 8Multitasking 57 8.1Hardwarestate.........................58 8.2Contextswitching........................58 8.3Theprocesslifecycle......................59 8.4Scheduling............................60 8.5Real-timescheduling......................62 9Threads 63 9.1Creatingthreads........................64 9.2Creatingthreads........................64 9.3Joiningthreads.........................66 9.4Synchronizationerrors.....................67 9.5Mutex..............................69 10Conditionvariables 71 10.1Theworkqueue.........................71 10.2Producersandconsumers....................74 10.3Mutualexclusion........................75 10.4Conditionvariables.......................77 10.5Conditionvariableimplementation..............80 11SemaphoresinC 81 11.1POSIXSemaphores.......................81 11.2Producersandconsumerswithsemaphores..........83 11.3Makeyourownsemaphores..................85 xii Contents Chapter1 Compilation 1.1Compiledandinterpretedlanguages Peopleoftendescribeprogramminglanguagesaspiledorinterpreted.“Compiled”meansthatprogramsaretranslatedintomachinelanguageandthenexecutedbyhardware;“interpreted”meansthatprogramsarereadandexecutedbyasoftwareinterpreter.UsuallyCisconsideredpiledlanguageandPythonisconsideredaninterpretedlanguage.Butthedistinctionisnotalwaysclear-cut.First,manylanguagescanbepiledorinterpreted.Forexample,thereareCinterpretersandpilers.Second,therearelanguageslikeJavathatuseahybridapproach,pilingprogramsintoanintermediatelanguageandthenrunningthetranslatedprograminaninterpreter.JavausesanintermediatelanguagecalledJavabytecode,whichissimilartomachinelanguage,butitisexecutedbyasoftwareinterpreter,theJavavirtualmachine(JVM).Sopiledorinterpretedisnotanintrinsiccharacteristicofalanguage;nevertheless,therearesomegeneraldifferencespiledandinterpretedlanguages. 1.2Statictypes Manyinterpretedlanguagessupportdynamictypes,piledlanguagesareusuallylimitedtostatictypes.Inastatically-typedlanguage,youcantell
2 Chapter1.Compilation bylookingattheprogramwhattypeeachvariablerefersto.Inadynamicallytypedlanguage,youdon’talwaysknowthetypeofavariableuntiltheprogramisrunning.Ingeneral,staticreferstothingsthathappenpiletime(whileaprogramispiled),anddynamicreferstothingsthathappenatruntime(whileaprogramisrunning). Forexample,inPythonyoucanwriteafunctionlikethis: defadd(x,y):returnx+y Lookingatthiscode,youcan’ttellwhattypexandywillrefertoatruntime.Thisfunctionmightbecalledseveraltimes,eachtimewithvalueswithdifferenttypes.Anyvaluesthatsupporttheadditionoperatorwillwork;anyothertypeswillcauseanexceptionorruntimeerror. InCyouwouldwritethesamefunctionlikethis: intadd(intx,inty){returnx+y; } Thefirstlineofthefunctionincludestypedeclarationsfortheparametersandthereturnvalue:xandyaredeclaredtobeintegers,whichmeansthatwecancheckpiletimewhethertheadditionoperatorislegalforthistype(itis).Thereturnvalueisalsodeclaredtobeaninteger. Becauseofthesedeclarations,whenthisfunctioniscalledelsewhereintheprogram,pilercancheckwhethertheargumentsprovidedhavetherighttype,andwhetherthereturnvalueisusedcorrectly. Thesecheckshappenbeforetheprogramstartsexecuting,soerrorscanbefoundearlier.Moreimportantly,errorscanbefoundinpartsoftheprogramthathaveneverrun.Furthermore,thesechecksdon’thavetohappenatruntime,whichisoneofthepiledlanguagesgenerallyrunfasterthaninterpretedlanguages. Declaringtypespiletimealsosavesspace.Indynamiclanguages,variablenamesarestoredinmemorywhiletheprogramruns,andtheyareoftenessiblebytheprogram.Forexample,inPythonthebuilt-infunctionlocalsreturnsadictionarythatcontainsvariablenamesandtheirvalues.Here’sanexampleinaPythoninterpreter: >>>x=5>>>printlocals(){'x':
5,'__builtins__':,'__name__':'__main__','__doc__':None,'__package__':None}
1.3.pilationprocess
3 Thisshowsthatthenameofthevariableisstoredinmemorywhiletheprogramisrunning(alongwithsomeothervaluesthatarepartofthedefaultruntimeenvironment). piledlanguages,variablenamesexistpile-timebutnotatruntime.pilerchoosesalocationforeachvariableandrecordstheselocationsaspartofpiledprogram.1Thelocationofavariableiscalleditsaddress.Atruntime,thevalueofeachvariableisstoredatitsaddress,butthenamesofthevariablesarenotstoredatall(unlesstheyareaddedbypilerforpurposesofdebugging). 1.3pilationprocess Asaprogrammer,youshouldhaveamentalmodelofwhathappenspilation.Ifyouunderstandtheprocess,itwillhelpyouinterpreterrormessages,debugyourcode,andmonpitfalls. Thestepspilationare:
1.Preprocessing:Cisoneofseverallanguagesthatincludepreprocessingdirectivesthattakeeffectbeforetheprogrampiled.Forexample,the#includedirectivecausesthesourcecodefromanotherfiletobeinsertedatthelocationofthedirective.
2.Parsing:Duringparsing,pilerreadsthesourcecodeandbuildsaninternalrepresentationoftheprogram,calledanabstractsyntaxtree.Errorsdetectedduringthissteparegenerallysyntaxerrors.
3.Staticchecking:pilercheckswhethervariablesandvalueshavetherighttype,whetherfunctionsarecalledwiththerightnumberandtypeofarguments,etc.Errorsdetectedduringthissteparesometimescalledstaticsemanticerrors.
4.Codegeneration:pilerreadstheinternalrepresentationoftheprogramandgeneratesmachinecodeorbytecode.
5.Linking:Iftheprogramusesvaluesandfunctionsdefinedinalibrary,pilerhastofindtheappropriatelibraryandincludetherequiredcode. 1Thisisasimplification;wewillgointomoredetaillater.
4 Chapter1.Compilation
6.Optimization:Atseveralpointsintheprocess,pilercantransformtheprogramtogeneratecodethatrunsfasteroruseslessspace.Mostoptimizationsaresimplechangesthateliminateobviouswaste,butpilersperformsophisticatedanalysesandtransformations. Normallywhenyourun,itrunsallofthesestepsandgeneratesanexecutablefile.Forexample,hereisaminimalCprogram: #includeintmain(){
printf("HelloWorld\n");}
Ifyousavethiscodeinafilecalledhello.c,youpileandrunitlikethis:
$hello.c$./a.out
Bydefault,storestheexecutablecodeinafilecalleda.out(whichoriginallystoodfor“assembleroutput”).Thesecondlinerunstheexecutable.Theprefix./tellstheshelltolookforitinthecurrentdirectory.
Itisusuallyagoodideatousethe-oflagtoprovideabetternamefortheexecutable:
$hello.c-ohello$./hello
1.4Objectcode
The-cflagtellspiletheprogramandgeneratemachinecode,butnottolinkitorgenerateanexecutable:
$hello.c-cTheresultisafilenamedhello.o,wheretheostandsforobjectcode,whichispiledprogram.Objectcodeisnotexecutable,butitcanbelinkedintoanexecutable.
Themandnmreadsanobjectfileandgeneratesinformationaboutthenamesitdefinesanduses.Forexample:
$nmhello.o0Tmain
Uputs
1.5.Assemblycode
5 Thisoutputindicatesthathello.odefinesthenamemainandusesafunctionnamedputs,whichstandsfor“putstring”.Inthisexample,performsanoptimizationbyreplacingprintf,whichisalargeplicatedfunction,withputs,whichisrelativelysimple. Youcancontrolhowmuchoptimizationdoeswiththe-Oflag.Bydefault,itdoesverylittleoptimization,whichcanmakedebuggingeasier.Theoption-O1turnsonthemonandsafeoptimizations.Highernumbersturnonadditionaloptimizationsthatrequirepilationtime. Intheory,optimizationshouldnotchangethebehavioroftheprogram,otherthantospeeditup.Butifyourprogramhasasubtlebug,youmightfindthatoptimizationmakesthebugappearordisappear.Itisusuallyagoodideatoturnoffoptimizationwhileyouaredevelopingnewcode.Oncetheprogramisworkingandpassingappropriatetests,youcanturnonoptimizationandconfirmthatthetestsstillpass. 1.5Assemblycode Similartothe-cflag,the-Sflagtellspiletheprogramandgenerateassemblycode,whichisbasicallyahuman-readableformofmachinecode. $hello.c-
S Theresultisafilenamedhello.s,whichmightlooksomethinglikethis: .LC0: main:.LFB0: .file.section .string.text.globl.type "hello.c".rodata "HelloWorld" mainmain,@function .cfi_startprocpushq%rbp.cfi_def_cfa_offset16.cfi_offset6,-16movq%rsp,%rbp.cfi_def_cfa_register6movl$.LC0,%edicallputs
6 Chapter1.Compilation .LFE0: movl$
0,%eaxpopq%rbp.cfi_def_cfa7,8ret.cfi_endproc .size.ident.section main,.-main"GCC:(Ubuntu/Linaro4.7.3-1ubuntu1)4.7.3".note.GNU-stack,"",@progbits isusuallyconfiguredtogeneratecodeforthemachineyouarerunningon,soformeitgeneratesx86assemblylanguage,whichrunsonawidevarietyofprocessorsfromIntel,AMD,andothers.Ifyouarerunningonadifferentarchitecture,youmightseedifferentcode. 1.6Preprocessing Takinganotherstepbackwardthroughpilationprocess,youcanusethe-Eflagtorunthepreprocessoronly: $hello.c-ETheresultistheoutputfromthepreprocessor.Inthisexample,itcontainstheincludedcodefromstdio.h,andallthefilesincludedfromstdio.h,andallthefilesincludedfromthosefiles,andsoon.Onmymachine,thetotalismorethan800linesofcode.SincealmosteveryCprogramincludesstdio.h,those800linesofcodepiledalot.If,likemanyCprograms,youalsoincludestdlib.h,theresultismorethan1800linesofcode. 1.7Understandingerrors Nowthatweknowthestepsinpilationprocess,itiseasiertounderstanderrormessages.Forexample,ifthereisanerrorina#includedirective,you’llgetamessagefromthepreprocessor: hello.c:1:20:fatalerror:stdioo.h:Nosuchfileorpilationterminated.Ifthere’sasyntaxerror,yougetamessagefrompiler: hello.c:Infunction'main':hello.c:6:1:error:expected';'before'}'tokenIfyouuseafunctionthat’snotdefinedinanyofthestandardlibraries,yougetamessagefromthelinker: 1.7.Understandingerrors
7 /7iAUbN.o:Infunction`main':hello.c:(.text+0xf):undefinedreferenceto`printff'collect2:error:ldreturned1exitstatus ldisthenameoftheUNIXlinker,sonamedbecause“loading”isanotherstepinpilationprocessthatiscloselyrelatedtolinking. Oncetheprogramstarts,Cdoesverylittleruntimechecking,sothereareonlyafewruntimeerrorsyouarelikelytosee.Ifyoudividebyzero,orperformanotherillegalfloating-pointoperation,youwillgeta“Floatingpointexception.”Andifyoutrytoreadorwriteanincorrectlocationinmemory,youwillgeta“Segmentationfault.”
8 Chapter1.Compilation Chapter2 Processes 2.1Abstractionandvirtualization Beforewetalkaboutprocesses,Iwanttodefineafewwords: Abstraction:Anabstractionisasimplifiedrepresentationofplicated.Forexample,ifyoudriveacar,youunderstandthatwhenyouturnthewheelleft,thecargoesleft,andviceversa.Ofcourse,thesteeringwheelisconnectedtoasequenceofmechanicaland(often)hydraulicsystemsthatturnthewheels,andthewheelsinteractwiththeroadinwaysthatcanplex,butasadriver,younormallydon’thavetothinkaboutanyofthosedetails.Youcangetalongverywellwithasimplementalmodelofsteering.Yourmentalmodelisanabstraction.Similarly,whenyouuseawebbrowser,youunderstandthatwhenyouclickonalink,thebrowserdisplaysthepagethelinkrefersto.Thesoftwaremunicationthatmakethatpossibleplex,butasauser,youdon’thavetoknowthedetails.Alargepartofsoftwareengineeringisdesigningabstractionslikethesethatallowusersandotherprogrammerstousepowerfulplicatedsystemswithouthavingtoknowaboutthedetailsoftheirimplementation. Virtualization:Animportantkindofabstractionisvirtualization,whichistheprocessofcreatingadesirableillusion.Forexample,manypubliclibrariesparticipateininter-librarycollaborationsthatallowthemtoborrowbooksfromeachother.WhenIrequest 10 Chapter2.Processes abook,sometimesthebookisontheshelfatmylocallibrary,butothertimesithastobetransferredfromanothercollection.Eitherway,Igetanotificationwhenitisavailableforpickup.Idon’tneedtoknowwhereitcamefrom,andIdon’tneedtoknowwhichbooksmylibraryhas.Asawhole,thesystemcreatestheillusionthatmylibraryhaseverybookintheworld. Thecollectionphysicallylocatedatmylocallibrarymightbesmall,butthecollectionavailabletomevirtuallyincludeseverybookintheinter-librarycollaboration. Asanotherexample,putersareonlyconnectedtowork,butworkisconnectedtoothers,andsoon.Whatwecalltheisacollectionworksandasetofprotocolsthatforwardpacketsfromworktothenext.Fromthepointofviewofauserorprogrammer,thesystembehavesasifputerontheisconnectedtoeveryputer.Thenumberofphysicalconnectionsissmall,butthenumberofvirtualconnectionsisverylarge. Theword“virtual”isoftenusedinthecontextofavirtualmachine,whichissoftwarethatcreatestheillusionofaputerrunningaparticularoperatingsystem,wheninrealitythevirtualmachinemightberunning,alongwithmanyothervirtualmachines,onputerrunningadifferentoperatingsystem. Inthecontextofvirtualization,wesometimescallwhatisreallyhappening“physical”,andwhatisvirtuallyhappeningeither“logical”or“abstract.” 2.2Isolation Oneofthemostimportantprinciplesofengineeringisisolation:whenyouaredesigningasystemwithponents,itisusuallyagoodideatoisolatethemfromeachothersothatachangeinponentdoesn’thaveundesiredeffectsonponents. Oneofthemostimportantgoalsofanoperatingsystemistoisolateeachrunningprogramfromtheotherssothatprogrammersdon’thavetothinkabouteverypossibleinteraction.Thesoftwareobjectthatprovidesthisisolationisaprocess. Aprocessisasoftwareobjectthatrepresentsarunningprogram.Imean“softwareobject”inthesenseofobject-orientedprogramming;ingeneral,anobjectcontainsdataandprovidesmethodsthatoperateonthedata.Aprocessisanobjectthatcontainsthefollowingdata: 2.2.Isolation 11 Thetextoftheprogram,usuallyasequenceofmachinelanguageinstructions. Dataassociatedwiththeprogram,includingstaticdata(allocatedpiletime)anddynamicdata(allocatedatruntime). Thestateofanypendinginput/outputoperations.Forexample,iftheprocessiswaitingfordatatobereadfromdiskorforapackettoarriveonwork,thestatusoftheseoperationsispartoftheprocess. Thehardwarestateoftheprogram,whichincludesdatastoredinregisters,statusinformation,andtheprogramcounter,whichindicateswhichinstructioniscurrentlyexecuting. Usuallyoneprocessrunsoneprogram,butitisalsopossibleforaprocesstoloadandrunanewprogram. Itisalsopossible,mon,torunthesameprograminmorethanoneprocess.Inthatcase,theprocessessharethesameprogramtextbutgenerallyhavedifferentdataandhardwarestates. Mostoperatingsystemsprovideafundamentalsetofcapabilitiestoisolateprocessesfromeachother: Multitasking:Mostoperatingsystemshavetheabilitytointerruptarunningprocessatalmostanytime,saveitshardwarestate,andthenresumetheprocesslater.Ingeneral,programmersdon’thavetothinkabouttheseinterruptions.Theprogrambehavesasifitisrunningcontinuouslyonadedicatedprocessor,exceptthatthetimebetweeninstructionsisunpredictable. Virtualmemory:Mostoperatingsystemscreatetheillusionthateachprocesshasitsownchunkofmemory,isolatedfromallotherprocesses.Again,programmersgenerallydon’thavetothinkabouthowvirtualmemoryworks;theycanproceedasifeveryprogramhasadedicatedchunkofmemory. Deviceabstraction:Processesrunningontheputersharethediskdrive,workinterface,thegraphicscard,andotherhardware.Ifprocessesinteractedwiththishardwaredirectly,withoutcoordination,chaoswouldensue.Forexample,workdataintendedforoneprocessmightbereadbyanother.Ormultipleprocessesmighttrytostoredatainthesamelocationonaharddrive.Itisuptotheoperatingsystemtomaintainorderbyprovidingappropriateabstractions. 12 Chapter2.Processes Asaprogrammer,youdon’tneedtoknowmuchabouthowthesecapabilitiesareimplemented.Butifyouarecurious,youwillfindalotofinterestingthingsgoingonunderthemetaphoricalhood.Andifyouknowwhat’sgoingon,itcanmakeyouabetterprogrammer. 2.3UNIXprocesses WhileIwritethisbook,theprocessIammostawareofismytexteditor,emacs.EveryonceinawhileIswitchtoaterminalwindow,whichisawindowrunningaUNIXshellthatprovidesmand-lineinterface. WhenImovethemouse,thewindowmanagerwakesup,seesthatthemouseisovertheterminalwindow,andwakesuptheterminal.Theterminalwakesuptheshell.IfItypemakeintheshell,itcreatesanewprocesstorunMake,whichcreatesanotherprocesstorunLaTeXandthenanotherprocesstodisplaytheresults. IfIneedtolooksomethingup,Imightswitchtoanother,whichwakesupthewindowmanageragain.IfIclickontheiconforawebbrowser,thewindowmanagercreatesaprocesstorunthewebbrowser.Somebrowsers,likeChrome,createanewprocessforeachwindowandeachtab. AndthosearejusttheprocessesIamawareof.Atthesametimetherearemanyotherprocessesrunninginthebackground.Manyofthemareperformingoperationsrelatedtotheoperatingsystem. Themandpsprintsinformationaboutrunningprocesses.Ifyourunitinaterminal,youmightseesomethinglikethis: PIDTTY2687pts/12801pts/124762pts/1 TIMECMD00:00:00bash00:01:24emacs00:00:00ps ThefirstcolumnistheuniquenumericalprocessID.Thesecondcolumnistheterminalthatcreatedtheprocess;“TTY”standsforteletypewriter,whichwastheoriginalmechanicalterminal. Thethirdcolumnisthetotalprocessortimeusedbytheprocess,inhours,minutes,andseconds.Thelastcolumnisthenameoftherunningprogram.Inthisexample,bashisthenameoftheshellthatinterpretsmandsItypeintheterminal,emacsismytexteditor,andpsistheprogramgeneratingthisoutput. 2.3.UNIXprocesses 13 Bydefault,pslistsonlytheprocessesassociatedwiththecurrentterminal.Ifyouusethe-eflag,yougeteveryprocess(includingprocessesbelongingtootherusers,whichisasecurityflaw,inmyopinion). Onmysystemtherearecurrently233processes.Herearesomeofthem: PIDTTY1?
2?
3?
4?
8?
9?
10?
47?
48?
49?
50?
51?
52?
53?
54?
55?
56?
57?
TIME00:00:1700:00:0000:00:0200:00:0000:00:0000:00:0000:00:1600:00:0000:00:0000:00:0000:00:0000:00:0000:00:0000:00:0000:00:0000:00:0000:00:0000:00:00 CMDinitkthreaddksoftirqd/0kworker/0:0migration/0rcu_bhrcu_schedcpusetkhelpernsbdi-defaultkintegritydkblockdata_sffkhubdmddevfreq_wq initisthefirstprocesscreatedwhentheoperatingsystemstarts.Itcreatesmanyoftheotherprocesses,andthensitsidleuntiltheprocessesitcreatedaredone. kthreaddisaprocesstheoperatingsystemusestocreatenewthreads.We’lltalkmoreaboutthreadslater,butfornowyoucanthinkofathreadaskindofaprocess.Thekatthebeginningstandsforkernel,whichisthepartoftheoperatingsystemresponsibleforcorecapabilitieslikecreatingthreads.Theextradattheendstandsfordaemon,whichisanothernameforprocesseslikethisthatruninthebackgroundandprovideoperatingsystemservices.Inthiscontext,“daemon”isusedinthesenseofahelpfulspirit,withnoconnotationofevil. Basedonthename,youcaninferthatksoftirqdisalsoakerneldaemon;specifically,ithandlessoftwareinterruptrequests,or“softIRQ”. kworkerisaworkerprocesscreatedbythekerneltodosomekindofprocessingforthekernel. 14 Chapter2.Processes Thereareoftenmultipleprocessesrunningthesekernelservices.Onmysystematthemoment,thereare8ksoftirqdprocessesand35kworkerprocesses. Iwon’tgointomoredetailsabouttheotherprocesses,butifyouareinterestedyoucansearchformoreinformationaboutthem.Youshouldrunpsonyoursystempareyourresultstomine. Chapter3 Virtualmemory 3.1Abitofinformationtheory Abitisabinarydigit;itisalsoaunitofinformation.Ifyouhaveonebit,youcanspecifyoneoftwopossibilities,usuallywritten0and1.Ifyouhavetwobits,thereare4binations,00,01,10,and11.Ingeneral,ifyouhavebbits,youcanindicateoneof2bvalues.Abyteis8bits,soitcanholdoneof256values. Goingintheotherdirection,supposeyouwanttostorealetterofthealphabet.Thereare26letters,sohowmanybitsdoyouneed?
With4bits,youcanspecifyoneof16values,sothat’snotenough.With5bits,youcanspecifyupto32values,sothat’senoughforalltheletters,withafewvaluesleftover. Ingeneral,ifyouwanttospecifyoneofNvalues,youshouldchoosethesmallestvalueofbsothat2b≥
N.Takingthelogbase2ofbothsidesyieldsb≥log2N. SupposeIflipacoinandtellyouthee.Ihavegivenyouonebitofinformation.IfIrollasix-sideddieandtellyouthee,Ihavegivenyoulog26bitsofinformation.Andingeneral,iftheprobabilityoftheeis1inN,thentheecontainslog2Nbitsofinformation. Equivalently,iftheprobabilityoftheeisp,thentheinformationcontentis−log2p.Thisquantityiscalledtheself-informationofthee.Itmeasureshowsurprisingtheeis,whichiswhyitisalsocalledsurprisal.Ifyourhorsehasonlyonechancein16ofwinning,andhewins,youget4bitsofinformation(alongwiththepayout).Butifthefavoritewins75%ofthetime,thenewsofthewincontainsonly0.42bits. 16 Chapter3.Virtualmemory Intuitively,unexpectednewscarriesalotofinformation;conversely,ifthereissomethingyouwerealreadyconfidentof,confirmingitcontributesonlyasmallamountofinformation. Foricsinthisbook,wewillneedtofortableconvertingbackandforthbetweenthenumberofbits,b,andthenumberofvaluestheycanencode,N=2b. 3.2Memoryandstorage Whileaprocessisrunning,mostofitsdataisheldinmainmemory,whichisusuallysomekindofrandomessmemory(RAM).Onmostputers,mainmemoryisvolatile,whichmeansthatwhenputershutsdown,thecontentsofmainmemoryarelost.Atypicalputerhas2–8GiBofmemory.GiBstandsfor“gibibyte,”whichis230bytes. Iftheprocessreadsandwritesfiles,thosefilesareusuallystoredonaharddiskdrive(HDD)orsolidstatedrive(SSD).Thesestoragedevicesarenonvolatile,sotheyareusedforlong-termstorage.CurrentlyatypicalputerhasaHDDwithacapacityof500GBto2TB.GBstandsfor“gigabyte,”whichis109bytes.TBstandsfor“terabyte,”whichis1012bytes. YoumighthavenoticedthatIusedthebinaryunitGiBforthesizeofmainmemoryandthedecimalunitsGBandTBforthesizeoftheHDD.Forhistoricalandtechnicalreasons,memoryismeasuredinbinaryunits,anddiskdrivesaremeasuredindecimalunits.InthisbookIwillbecarefultodistinguishbinaryanddecimalunits,butyoushouldbeawarethattheword“gigabyte”andtheabbreviationGBareoftenusedambiguously. Incasualuse,theterm“memory”issometimesusedforHDDsandSSDsaswellasRAM,butthepropertiesofthesedevicesareverydifferent,sowewillneedtodistinguishthem.IwillusestoragetorefertoHDDsandSSDs. 3.3Addressspaces Eachbyteinmainmemoryisspecifiedbyanintegerphysicaladdress.Thesetofvalidphysicaladdressesiscalledthephysicaladdressspace.Itusuallyrunsfrom0toN−1,whereNisthesizeofmainmemory.Onasystemwith1GiBofphysicalmemory,thehighestvalidaddressis230−1,whichis1,073,741,823indecimal,or0x3fffffffinhexadecimal(theprefix0xindicatesahexadecimalnumber). 3.4.Memorysegments 17 However,mostoperatingsystemsprovidevirtualmemory,whichmeansthatprogramsneverdealwithphysicaladdresses,anddon’thavetoknowhowmuchphysicalmemoryisavailable. Instead,programsworkwithvirtualaddresses,whicharenumberedfrom0toM−1,whereMisthenumberofvalidvirtualaddresses.Thesizeofthevirtualaddressspaceisdeterminedbytheoperatingsystemandthehardwareitrunson. Youhaveprobablyheardpeopletalkabout32-bitand64-bitsystems.Thesetermsindicatethesizeoftheregisters,whichisusuallyalsothesizeofavirtualaddress.Ona32-bitsystem,virtualaddressesare32bits,whichmeansthatthevirtualaddressspacerunsfrom0to0xffffffff.Thesizeofthisaddressspaceis232bytes,or4GiB. Ona64-bitsystem,thesizeofthevirtualaddressspaceis264bytes,or24·10246bytes.That’s16exbibytes,whichisaboutabilliontimesbiggerthancurrentphysicalmemories.Itmightseemstrangethatavirtualaddressspacecanbesomuchbiggerthanphysicalmemory,butwewillseesoonhowthatworks. Whenaprogramreadsandwritesvaluesinmemory,itgeneratesvirtualaddresses.Thehardware,withhelpfromtheoperatingsystem,translatestophysicaladdressesbeforeessingmainmemory.Thistranslationisdoneonaper-processbasis,soeveniftwoprocessesgeneratethesamevirtualaddress,theywouldmaptodifferentlocationsinphysicalmemory. Thus,virtualmemoryisoneimportantwaytheoperatingsystemisolatesprocessesfromeachother.Ingeneral,aprocesscannotessdatabelongingtoanotherprocess,becausethereisnovirtualaddressitcangeneratethatmapstophysicalmemoryallocatedtoanotherprocess. 3.4Memorysegments Thedataofarunningprocessanizedintofivesegments: Thecodesegmentcontainstheprogramtext;thatis,themachinelanguageinstructionsthatmakeuptheprogram. Thestaticsegmentcontainsimmutablevalues,likestringliterals.Forexample,ifyourprogramcontainsthestring"Hello,World",thosecharacterswillbestoredinthestaticsegment. Theglobalsegmentcontainsglobalvariablesandlocalvariablesthataredeclaredstatic. 18 Chapter3.Virtualmemory Theheapsegmentcontainschunksofmemoryallocatedatruntime,mostoftenbycallingtheClibraryfunctionmalloc. Thestacksegmentcontainsthecallstack,whichisasequenceofstackframes.Eachtimeafunctioniscalled,astackframeisallocatedtocontaintheparametersandlocalvariablesofthefunction.Whenthepletes,itsstackframeisremovedfromthestack. Thearrangementofthesesegmentsisdeterminedpartlybypilerandpartlybytheoperatingsystem.Thedetailsvaryfromonesystemtoanother,butinthemonarrangement: Thetextsegmentisnearthe“bottom”ofmemory,thatis,ataddressesnear0. Thestaticsegmentisoftenjustabovethetextsegment,thatis,athigheraddresses. Theglobalsegmentisoftenjustabovethestaticsegment. Theheapisoftenabovetheglobalsegment.Asitexpands,itgrowsuptowardlargeraddresses. Thestackisnearofmemory;thatis,nearthehighestaddressesinthevirtualaddressspace.Asthestackexpands,itgrowsdowntowardsmalleraddresses. Todeterminethelayoutofthesesegmentsonyoursystem,tryrunningthisprogram,whichisinaspace.cintherepositoryforthisbook(seeSection0.1). #include#include
intglobal;
intmain(){
intlocal=5;void*p=malloc(128);char*s="Hello,World";
printf("Addressofmainis%p\n",main);printf("Addressofglobalis%p\n",&global);printf("Addressoflocalis%p\n",&local);
3.4.Memorysegments
19
printf("ppointsto%p\n",p);printf("spointsto%p\n",s);}
mainisthenameofafunction;whenitisusedasavariable,itreferstotheaddressofthefirstmachinelanguageinstructioninmain,whichweexpecttobeinthetextsegment.
globalisaglobalvariable,soweexpectittobeintheglobalsegment.localisalocalvariable,soweexpectittobeonthestack.
sreferstoa“stringliteral”,whichisastringthatappearsaspartoftheprogram(asopposedtoastringthatisreadfromafile,inputbyauser,etc.).Weexpectthelocationofthestringtobeinthestaticsegment(asopposedtothepointer,s,whichisalocalvariable).
pcontainsanaddressreturnedbymalloc,whichallocatesspaceintheheap.“malloc”standsfor“memoryallocate.”
Theformatsequence%ptellsprintftoformateachaddressasa“pointer”,soitdisplaystheresultsinhexadecimal.
WhenIrunthisprogram,theoutputlookslikethis(Iaddedspacestomakeiteasiertoread):
Addressofmainis0x
40057d
Addressofglobalis0x
60104c
Addressoflocalis0x7ffe6085443c
ppointsto
0x
16c3010
spointsto
0x
4006a4
Asexpected,theaddressofmainisthelowest,followedbythelocationofthestringliteral.Thelocationofglobalisnext,thentheaddressppointsto.Theaddressoflocalismuchbigger.
Thelargestaddresshas12hexadecimaldigits.Eachhexdigitcorrespondsto4bits,soitisa48-bitaddress.Thatsuggeststhattheusablepartofthevirtualaddressspaceis248bytes.
Asanexercise,runthisprogramonputerpareyourresultstomine.Addasecondcalltomallocandcheckwhethertheheaponyoursystemgrowsup(towardlargeraddresses).Addafunctionthatprintstheaddressofalocalvariable,andcheckwhetherthestackgrowsdown.
20
Chapter3.Virtualmemory
CPU
virtualaddress
MMU
physicaladdress
MCU
MMU
virtualaddress
virtualpage#
offset
TLB
physicalpage#offsetphysicaladdress
Figure3.1:Diagramoftheaddresstranslationprocess.
3.5Staticlocalvariables
Localvariablesonthestackaresometimescalledautomatic,becausetheyareallocatedautomaticallywhenafunctioniscalled,andfreedautomaticallywhenthefunctionreturns.
InCthereisanotherkindoflocalvariable,calledstatic,whichisallocatedintheglobalsegment.Itisinitializedwhentheprogramstartsandkeepsitsvaluefromonefunctioncalltothenext.
Forexample,thefollowingfunctionkeepstrackofhowmanytimesithasbeencalled.
inttimes_called(){
staticintcounter=0;counter++;returncounter;}Thekeywordstaticindicatesthatcounterisastaticlocalvariable.Theinitializationhappensonlyonce,whentheprogramstarts.
Ifyouaddthisfunctiontoaspace.cyoucanconfirmthatcounterisallocatedintheglobalsegmentalongwithglobalvariables,notinthestack.
3.6Addresstranslation
Howdoesavirtualaddress(VA)gettranslatedtoaphysicaladdress(PA)?
Thebasicmechanismissimple,butasimpleimplementationwouldbetooslowandtaketoomuchspace.Soactualimplementationsareabitplicated. 3.6.Addresstranslation 21 Mostprocessorsprovideamemorymanagementunit(MMU)thatsitsbetweentheCPUandmainmemory.TheMMUperformsfasttranslationbetweenVAsandPAs.
1.Whenaprogramreadsorwritesavariable,theCPUgeneratesaVA.
2.TheMMUsplitstheVAintotwoparts,calledthepagenumberandtheoffset.A“page”isachunkofmemory;thesizeofapagedependsontheoperatingsystemandthehardware,monsizesare1–4KiB.
3.TheMMUlooksupthepagenumberinthetranslationlookasidebuffer(TLB)andgetsthecorrespondingphysicalpagenumber.ThenbinesthephysicalpagenumberwiththeoffsettoproduceaPA.
4.ThePAispassedtomainmemory,whichreadsorwritesthegivenlocation. TheTLBcontainscachedcopiesofdatafromthepagetable(whichisstoredinkernelmemory).Thepagetablecontainsthemappingfromvirtualpagenumberstophysicalpagenumbers.Sinceeachprocesshasitsownpagetable,theTLBhastomakesureitonlyusesentriesfromthepagetableoftheprocessthat’srunning. Figure3.1showsadiagramofthisprocess.Toseehowitallworks,supposethattheVAis32bitsandthephysicalmemoryis1GiB,dividedinto1KiBpages. Since1GiBis230bytesand1KiBis210bytes,thereare220physicalpages,sometimescalled“frames.” Thesizeofthevirtualaddressspaceis232Bandthesizeofapageis210B,sothereare222virtualpages. Thesizeoftheoffsetisdeterminedbythepagesize.Inthisexamplethepagesizeis210B,soittakes10bitstospecifyabyteonapage. IfaVAis32bitsandtheoffsetis10bits,theremaining22bitsmakeupthevirtualpagenumber. Sincethereare220physicalpages,eachphysicalpagenumberis20bits.Addinginthe10bitoffset,theresultingPAsare30bits. Sofarthisallseemsfeasible.Butlet’sthinkabouthowbigapagetablemighthavetobe.Thesimplestimplementationofapagetableisanarraywithoneentryforeachvirtualpage.Eachentrywouldcontainaphysicalpagenumber, 22 Chapter3.Virtualmemory whichis20bitsinthisexample,plussomeadditionalinformationabouteachframe.Soweexpect3–4bytesperentry.Butwith222virtualpages,thepagetablewouldrequire224bytes,or16MiB. Andsinceweneedapagetableforeachprocess,asystemrunning256processeswouldneed232bytes,or4GiB,justforpagetables!
Andthat’sjustwith32-bitvirtualaddresses.With48-or64-bitVAs,thenumbersareridiculous. Fortunately,wedon’tactuallyneedthatmuchspace,becausemostprocessesdon’tuseevenasmallfractionoftheirvirtualaddressspace.Andifaprocessdoesn’tuseavirtualpage,wedon’tneedanentryinthepagetableforit. Anotherwaytosaythesamethingisthatpagetablesare“sparse”,whichimpliesthatthesimpleimplementation,anarrayofpagetableentries,isabadidea.Fortunately,thereareseveralgoodimplementationsforsparsearrays. Oneoptionisamultilevelpagetable,whichiswhatmanyoperatingsystems,includingLinux,use.Anotheroptionisanassociativetable,whereeachentryincludesboththevirtualpagenumberandthephysicalpagenumber.Searchinganassociativetablecanbeslowinsoftware,butinhardwarewecansearchtheentiretableinparallel,soassociativearraysareoftenusedtorepresentthepagetableentriesintheTLB. Youcanreadmoreabouttheseimplementationsat/wiki/Page_table;youmightfindthedetailsinteresting.Butthefundamentalideaisthatpagetablesaresparse,sowehavetochooseagoodimplementationforsparsearrays. Imentionedearlierthattheoperatingsystemcaninterruptarunningprocess,saveitsstate,andthenrunanotherprocess.Thismechanismiscalledacontextswitch.Sinceeachprocesshasitsownpagetable,theoperatingsystemhastoworkwiththeMMUtomakesureeachprocessgetstherightpagetable.Inoldermachines,thepagetableinformationintheMMUhadtobereplacedduringeverycontextswitch,whichwasexpensive.Innewersystems,eachpagetableentryintheMMUincludestheprocessID,sopagetablesfrommultipleprocessescanbeintheMMUatthesametime. Chapter4 Filesandfilesystems Whenapletes(orcrashes),anydatastoredinmainmemoryislost.Butdatastoredonaharddiskdrive(HDD)orsolidstatedrive(SSD)is“persistent;”thatis,itsurvivesafterthepletes,evenifputershutsdown.Harddiskdrivesplicated.Dataisstoredinblocks,whicharelaidoutinsectors,whichmakeuptracks,whicharearrangedinconcentriccirclesonplatters.Solidstatedrivesaresimplerinonesense,becauseblocksarenumberedsequentially,buttheyraiseadiffplication:eachblockcanbewrittenalimitednumberoftimesbeforeitesunreliable.Asaprogrammer,youdon’twanttodealwithplications.Whatyouwantisanappropriateabstractionofpersistentstoragehardware.Themonabstractioniscalleda“filesystem.”Abstractly: A“filesystem”isamappingfromeachfile’snametoitscontents.Ifyouthinkofthenamesaskeys,andthecontentsasvalues,afilesystemisakindofkey-valuedatabase(see/wiki/Key-value_database). A“file”isasequenceofbytes. Filenamesareusuallystrings,andtheyareusually“hierarchical”;thatis,thestringspecifiesapathfrom-leveldirectory(orfolder),throughaseriesofsubdirectories,toaspecificfile. 24 Chapter4.Filesandfilesystems Theprimarydifferencebetweentheabstractionandtheunderlyingmechanismisthatfilesarebyte-basedandpersistentstorageisblock-based.Theoperatingsystemtranslatesbyte-basedfileoperationsintheClibraryintoblock-basedoperationsonstoragedevices.Typicalblocksizesare1–8KiB. Forexample,thefollowingcodeopensafileandreadsthefirstbyte: FILE*fp=fopen("/home/downey/file.txt","r");charc=fgetc(fp);fclose(fp); Whenthiscoderuns: 1.fopenusesthefilenametofind-leveldirectory,called/,thesubdirectoryhome,andthesub-subdirectorydowney.
2.Itfindsthefilenamedfile.txtand“opens”itforreading,whichmeansitcreatesadatastructurethatrepresentsthefilebeingread.Amongotherthings,thisdatastructurekeepstrackofhowmuchofthefilehasbeenread,calledthe“fileposition”. InDOS,thisdatastructureiscalledaFileControlBlock,butIwanttoavoidthattermbecauseinUNIXitmeanssomethingelse.InUNIX,thereseemstobenogoodnameforit.Itisanentryintheopenfiletable,soIwillcallitanOpenFileTableEntry.
3.Whenwecallfgetc,theoperatingsystemcheckswhetherthenextcharacterofthefileisalreadyinmemory.Ifso,itreadsthenextcharacter,advancesthefileposition,andreturnstheresult.
4.Ifthenextcharacterisnotinmemory,theoperatingsystemissuesanI/Orequesttogetthenextblock.Diskdrivesareslow,soaprocesswaitingforablockfromdiskisusuallyinterruptedsoanotherprocesscanrununtilthedataarrives.
5.WhentheI/Ooperationplete,thenewblockofdataisstoredinmemory,andtheprocessresumes.Itreadsthefirstcharacterandstoresitasalocalvariable.
6.Whentheprocessclosesthefile,theoperatingpletesorcancelsanypendingoperations,removesdatastoredinmemory,andfreestheOpenFileTableEntry. Theprocessforwritingafileissimilar,buttherearesomeadditionalsteps.Hereisanexamplethatopensafileforwritingandchangesthefirstcharacter. 4.1.Diskperformance 25 FILE*fp=fopen("/home/downey/file.txt","w");fputc('b',fp);fclose(fp);Whenthiscoderuns:
1.Again,fopenusesthefilenametofindthefile.Ifitdoesnotalreadyexist,itcreatesanewfileandaddsanentryintheparentdirectory,/home/downey.
2.TheoperatingsystemcreatesanOpenFileTableEntrythatindicatesthatthefileisopenforwriting,andsetsthefilepositionto0. 3.fputcattemptstowrite(orre-write)thefirstbyteofthefile.Ifthefilealreadyexists,theoperatingsystemhastoloadthefirstblockintomemory.Otherwiseitallocatesanewblockinmemoryandrequestsanewblockondisk.
4.Aftertheblockinmemoryismodified,itmightnotbecopiedbacktothediskrightaway.Ingeneral,datawrittentoafileis“buffered”,whichmeansitisstoredinmemoryandonlywrittentodiskwhenthereisatleastoneblocktowrite.
5.Whenthefileisclosed,anybufferedda
IamgratefultothestudentsinSoftwareSystemsatOlinCollege,whotestedanearlydraftofthisbookinSpring2014.Theycorrectedmanyerrorsandmademanyhelpfulsuggestions.Iappreciatetheirpioneeringspirit!
JamesPGiannoulesspottedacopy-and-pasteerror. AndyEngleknowsthedifferencebetweenGBandGiB. AashishKarkinotedsomebrokensyntax. OtherpeoplewhofoundtyposanderrorsincludeJimTyson,DonaldRobertson,JeremyVermast,YuzhongHuang,IanHill. viii Chapter0.Preface Contents Preface v 0.1Usingthecode..........................vi 1Compilation
1 1.1Compiledandinterpretedlanguages..............1 1.2Statictypes...........................1 1.3pilationprocess....................3 1.4Objectcode...........................4 1.5Assemblycode..........................5 1.6Preprocessing..........................6 1.7Understandingerrors......................6 2Processes
9 2.1Abstractionandvirtualization.................9 2.2Isolation.............................10 2.3UNIXprocesses.........................12 3Virtualmemory 15 3.1Abitofinformationtheory...................15 3.2Memoryandstorage......................16 3.3Addressspaces.........................16 x Contents 3.4Memorysegments........................173.5Staticlocalvariables......................203.6Addresstranslation.......................20 4Filesandfilesystems 23 4.1Diskperformance........................25 4.2Diskmetadata..........................27 4.3Blockallocation.........................28 4.4Everythingisafile?
.......................28 5Morebitsandbytes 31 5.1Representingintegers......................31 5.2Bitwiseoperators........................32 5.3Representingfloating-pointnumbers..............33 5.4Unionsandmemoryerrors...................35 5.5Representingstrings.......................36 6Memorymanagement 39 6.1Memoryerrors..........................39 6.2Memoryleaks..........................41 6.3Implementation.........................43 7Caching 45 7.1Howprogramsrun.......................45 7.2Cacheperformance.......................47 7.3Locality.............................47 7.4Measuringcacheperformance.................48 7.5Programmingforcacheperformance..............51 7.6Thememoryhierarchy.....................52 7.7Cachingpolicy..........................53 7.8Paging..............................54 Contents xi 8Multitasking 57 8.1Hardwarestate.........................58 8.2Contextswitching........................58 8.3Theprocesslifecycle......................59 8.4Scheduling............................60 8.5Real-timescheduling......................62 9Threads 63 9.1Creatingthreads........................64 9.2Creatingthreads........................64 9.3Joiningthreads.........................66 9.4Synchronizationerrors.....................67 9.5Mutex..............................69 10Conditionvariables 71 10.1Theworkqueue.........................71 10.2Producersandconsumers....................74 10.3Mutualexclusion........................75 10.4Conditionvariables.......................77 10.5Conditionvariableimplementation..............80 11SemaphoresinC 81 11.1POSIXSemaphores.......................81 11.2Producersandconsumerswithsemaphores..........83 11.3Makeyourownsemaphores..................85 xii Contents Chapter1 Compilation 1.1Compiledandinterpretedlanguages Peopleoftendescribeprogramminglanguagesaspiledorinterpreted.“Compiled”meansthatprogramsaretranslatedintomachinelanguageandthenexecutedbyhardware;“interpreted”meansthatprogramsarereadandexecutedbyasoftwareinterpreter.UsuallyCisconsideredpiledlanguageandPythonisconsideredaninterpretedlanguage.Butthedistinctionisnotalwaysclear-cut.First,manylanguagescanbepiledorinterpreted.Forexample,thereareCinterpretersandpilers.Second,therearelanguageslikeJavathatuseahybridapproach,pilingprogramsintoanintermediatelanguageandthenrunningthetranslatedprograminaninterpreter.JavausesanintermediatelanguagecalledJavabytecode,whichissimilartomachinelanguage,butitisexecutedbyasoftwareinterpreter,theJavavirtualmachine(JVM).Sopiledorinterpretedisnotanintrinsiccharacteristicofalanguage;nevertheless,therearesomegeneraldifferencespiledandinterpretedlanguages. 1.2Statictypes Manyinterpretedlanguagessupportdynamictypes,piledlanguagesareusuallylimitedtostatictypes.Inastatically-typedlanguage,youcantell
2 Chapter1.Compilation bylookingattheprogramwhattypeeachvariablerefersto.Inadynamicallytypedlanguage,youdon’talwaysknowthetypeofavariableuntiltheprogramisrunning.Ingeneral,staticreferstothingsthathappenpiletime(whileaprogramispiled),anddynamicreferstothingsthathappenatruntime(whileaprogramisrunning). Forexample,inPythonyoucanwriteafunctionlikethis: defadd(x,y):returnx+y Lookingatthiscode,youcan’ttellwhattypexandywillrefertoatruntime.Thisfunctionmightbecalledseveraltimes,eachtimewithvalueswithdifferenttypes.Anyvaluesthatsupporttheadditionoperatorwillwork;anyothertypeswillcauseanexceptionorruntimeerror. InCyouwouldwritethesamefunctionlikethis: intadd(intx,inty){returnx+y; } Thefirstlineofthefunctionincludestypedeclarationsfortheparametersandthereturnvalue:xandyaredeclaredtobeintegers,whichmeansthatwecancheckpiletimewhethertheadditionoperatorislegalforthistype(itis).Thereturnvalueisalsodeclaredtobeaninteger. Becauseofthesedeclarations,whenthisfunctioniscalledelsewhereintheprogram,pilercancheckwhethertheargumentsprovidedhavetherighttype,andwhetherthereturnvalueisusedcorrectly. Thesecheckshappenbeforetheprogramstartsexecuting,soerrorscanbefoundearlier.Moreimportantly,errorscanbefoundinpartsoftheprogramthathaveneverrun.Furthermore,thesechecksdon’thavetohappenatruntime,whichisoneofthepiledlanguagesgenerallyrunfasterthaninterpretedlanguages. Declaringtypespiletimealsosavesspace.Indynamiclanguages,variablenamesarestoredinmemorywhiletheprogramruns,andtheyareoftenessiblebytheprogram.Forexample,inPythonthebuilt-infunctionlocalsreturnsadictionarythatcontainsvariablenamesandtheirvalues.Here’sanexampleinaPythoninterpreter: >>>x=5>>>printlocals(){'x':
5,'__builtins__':
3 Thisshowsthatthenameofthevariableisstoredinmemorywhiletheprogramisrunning(alongwithsomeothervaluesthatarepartofthedefaultruntimeenvironment). piledlanguages,variablenamesexistpile-timebutnotatruntime.pilerchoosesalocationforeachvariableandrecordstheselocationsaspartofpiledprogram.1Thelocationofavariableiscalleditsaddress.Atruntime,thevalueofeachvariableisstoredatitsaddress,butthenamesofthevariablesarenotstoredatall(unlesstheyareaddedbypilerforpurposesofdebugging). 1.3pilationprocess Asaprogrammer,youshouldhaveamentalmodelofwhathappenspilation.Ifyouunderstandtheprocess,itwillhelpyouinterpreterrormessages,debugyourcode,andmonpitfalls. Thestepspilationare:
1.Preprocessing:Cisoneofseverallanguagesthatincludepreprocessingdirectivesthattakeeffectbeforetheprogrampiled.Forexample,the#includedirectivecausesthesourcecodefromanotherfiletobeinsertedatthelocationofthedirective.
2.Parsing:Duringparsing,pilerreadsthesourcecodeandbuildsaninternalrepresentationoftheprogram,calledanabstractsyntaxtree.Errorsdetectedduringthissteparegenerallysyntaxerrors.
3.Staticchecking:pilercheckswhethervariablesandvalueshavetherighttype,whetherfunctionsarecalledwiththerightnumberandtypeofarguments,etc.Errorsdetectedduringthissteparesometimescalledstaticsemanticerrors.
4.Codegeneration:pilerreadstheinternalrepresentationoftheprogramandgeneratesmachinecodeorbytecode.
5.Linking:Iftheprogramusesvaluesandfunctionsdefinedinalibrary,pilerhastofindtheappropriatelibraryandincludetherequiredcode. 1Thisisasimplification;wewillgointomoredetaillater.
4 Chapter1.Compilation
6.Optimization:Atseveralpointsintheprocess,pilercantransformtheprogramtogeneratecodethatrunsfasteroruseslessspace.Mostoptimizationsaresimplechangesthateliminateobviouswaste,butpilersperformsophisticatedanalysesandtransformations. Normallywhenyourun,itrunsallofthesestepsandgeneratesanexecutablefile.Forexample,hereisaminimalCprogram: #include
5 Thisoutputindicatesthathello.odefinesthenamemainandusesafunctionnamedputs,whichstandsfor“putstring”.Inthisexample,performsanoptimizationbyreplacingprintf,whichisalargeplicatedfunction,withputs,whichisrelativelysimple. Youcancontrolhowmuchoptimizationdoeswiththe-Oflag.Bydefault,itdoesverylittleoptimization,whichcanmakedebuggingeasier.Theoption-O1turnsonthemonandsafeoptimizations.Highernumbersturnonadditionaloptimizationsthatrequirepilationtime. Intheory,optimizationshouldnotchangethebehavioroftheprogram,otherthantospeeditup.Butifyourprogramhasasubtlebug,youmightfindthatoptimizationmakesthebugappearordisappear.Itisusuallyagoodideatoturnoffoptimizationwhileyouaredevelopingnewcode.Oncetheprogramisworkingandpassingappropriatetests,youcanturnonoptimizationandconfirmthatthetestsstillpass. 1.5Assemblycode Similartothe-cflag,the-Sflagtellspiletheprogramandgenerateassemblycode,whichisbasicallyahuman-readableformofmachinecode. $hello.c-
S Theresultisafilenamedhello.s,whichmightlooksomethinglikethis: .LC0: main:.LFB0: .file.section .string.text.globl.type "hello.c".rodata "HelloWorld" mainmain,@function .cfi_startprocpushq%rbp.cfi_def_cfa_offset16.cfi_offset6,-16movq%rsp,%rbp.cfi_def_cfa_register6movl$.LC0,%edicallputs
6 Chapter1.Compilation .LFE0: movl$
0,%eaxpopq%rbp.cfi_def_cfa7,8ret.cfi_endproc .size.ident.section main,.-main"GCC:(Ubuntu/Linaro4.7.3-1ubuntu1)4.7.3".note.GNU-stack,"",@progbits isusuallyconfiguredtogeneratecodeforthemachineyouarerunningon,soformeitgeneratesx86assemblylanguage,whichrunsonawidevarietyofprocessorsfromIntel,AMD,andothers.Ifyouarerunningonadifferentarchitecture,youmightseedifferentcode. 1.6Preprocessing Takinganotherstepbackwardthroughpilationprocess,youcanusethe-Eflagtorunthepreprocessoronly: $hello.c-ETheresultistheoutputfromthepreprocessor.Inthisexample,itcontainstheincludedcodefromstdio.h,andallthefilesincludedfromstdio.h,andallthefilesincludedfromthosefiles,andsoon.Onmymachine,thetotalismorethan800linesofcode.SincealmosteveryCprogramincludesstdio.h,those800linesofcodepiledalot.If,likemanyCprograms,youalsoincludestdlib.h,theresultismorethan1800linesofcode. 1.7Understandingerrors Nowthatweknowthestepsinpilationprocess,itiseasiertounderstanderrormessages.Forexample,ifthereisanerrorina#includedirective,you’llgetamessagefromthepreprocessor: hello.c:1:20:fatalerror:stdioo.h:Nosuchfileorpilationterminated.Ifthere’sasyntaxerror,yougetamessagefrompiler: hello.c:Infunction'main':hello.c:6:1:error:expected';'before'}'tokenIfyouuseafunctionthat’snotdefinedinanyofthestandardlibraries,yougetamessagefromthelinker: 1.7.Understandingerrors
7 /7iAUbN.o:Infunction`main':hello.c:(.text+0xf):undefinedreferenceto`printff'collect2:error:ldreturned1exitstatus ldisthenameoftheUNIXlinker,sonamedbecause“loading”isanotherstepinpilationprocessthatiscloselyrelatedtolinking. Oncetheprogramstarts,Cdoesverylittleruntimechecking,sothereareonlyafewruntimeerrorsyouarelikelytosee.Ifyoudividebyzero,orperformanotherillegalfloating-pointoperation,youwillgeta“Floatingpointexception.”Andifyoutrytoreadorwriteanincorrectlocationinmemory,youwillgeta“Segmentationfault.”
8 Chapter1.Compilation Chapter2 Processes 2.1Abstractionandvirtualization Beforewetalkaboutprocesses,Iwanttodefineafewwords: Abstraction:Anabstractionisasimplifiedrepresentationofplicated.Forexample,ifyoudriveacar,youunderstandthatwhenyouturnthewheelleft,thecargoesleft,andviceversa.Ofcourse,thesteeringwheelisconnectedtoasequenceofmechanicaland(often)hydraulicsystemsthatturnthewheels,andthewheelsinteractwiththeroadinwaysthatcanplex,butasadriver,younormallydon’thavetothinkaboutanyofthosedetails.Youcangetalongverywellwithasimplementalmodelofsteering.Yourmentalmodelisanabstraction.Similarly,whenyouuseawebbrowser,youunderstandthatwhenyouclickonalink,thebrowserdisplaysthepagethelinkrefersto.Thesoftwaremunicationthatmakethatpossibleplex,butasauser,youdon’thavetoknowthedetails.Alargepartofsoftwareengineeringisdesigningabstractionslikethesethatallowusersandotherprogrammerstousepowerfulplicatedsystemswithouthavingtoknowaboutthedetailsoftheirimplementation. Virtualization:Animportantkindofabstractionisvirtualization,whichistheprocessofcreatingadesirableillusion.Forexample,manypubliclibrariesparticipateininter-librarycollaborationsthatallowthemtoborrowbooksfromeachother.WhenIrequest 10 Chapter2.Processes abook,sometimesthebookisontheshelfatmylocallibrary,butothertimesithastobetransferredfromanothercollection.Eitherway,Igetanotificationwhenitisavailableforpickup.Idon’tneedtoknowwhereitcamefrom,andIdon’tneedtoknowwhichbooksmylibraryhas.Asawhole,thesystemcreatestheillusionthatmylibraryhaseverybookintheworld. Thecollectionphysicallylocatedatmylocallibrarymightbesmall,butthecollectionavailabletomevirtuallyincludeseverybookintheinter-librarycollaboration. Asanotherexample,putersareonlyconnectedtowork,butworkisconnectedtoothers,andsoon.Whatwecalltheisacollectionworksandasetofprotocolsthatforwardpacketsfromworktothenext.Fromthepointofviewofauserorprogrammer,thesystembehavesasifputerontheisconnectedtoeveryputer.Thenumberofphysicalconnectionsissmall,butthenumberofvirtualconnectionsisverylarge. Theword“virtual”isoftenusedinthecontextofavirtualmachine,whichissoftwarethatcreatestheillusionofaputerrunningaparticularoperatingsystem,wheninrealitythevirtualmachinemightberunning,alongwithmanyothervirtualmachines,onputerrunningadifferentoperatingsystem. Inthecontextofvirtualization,wesometimescallwhatisreallyhappening“physical”,andwhatisvirtuallyhappeningeither“logical”or“abstract.” 2.2Isolation Oneofthemostimportantprinciplesofengineeringisisolation:whenyouaredesigningasystemwithponents,itisusuallyagoodideatoisolatethemfromeachothersothatachangeinponentdoesn’thaveundesiredeffectsonponents. Oneofthemostimportantgoalsofanoperatingsystemistoisolateeachrunningprogramfromtheotherssothatprogrammersdon’thavetothinkabouteverypossibleinteraction.Thesoftwareobjectthatprovidesthisisolationisaprocess. Aprocessisasoftwareobjectthatrepresentsarunningprogram.Imean“softwareobject”inthesenseofobject-orientedprogramming;ingeneral,anobjectcontainsdataandprovidesmethodsthatoperateonthedata.Aprocessisanobjectthatcontainsthefollowingdata: 2.2.Isolation 11 Thetextoftheprogram,usuallyasequenceofmachinelanguageinstructions. Dataassociatedwiththeprogram,includingstaticdata(allocatedpiletime)anddynamicdata(allocatedatruntime). Thestateofanypendinginput/outputoperations.Forexample,iftheprocessiswaitingfordatatobereadfromdiskorforapackettoarriveonwork,thestatusoftheseoperationsispartoftheprocess. Thehardwarestateoftheprogram,whichincludesdatastoredinregisters,statusinformation,andtheprogramcounter,whichindicateswhichinstructioniscurrentlyexecuting. Usuallyoneprocessrunsoneprogram,butitisalsopossibleforaprocesstoloadandrunanewprogram. Itisalsopossible,mon,torunthesameprograminmorethanoneprocess.Inthatcase,theprocessessharethesameprogramtextbutgenerallyhavedifferentdataandhardwarestates. Mostoperatingsystemsprovideafundamentalsetofcapabilitiestoisolateprocessesfromeachother: Multitasking:Mostoperatingsystemshavetheabilitytointerruptarunningprocessatalmostanytime,saveitshardwarestate,andthenresumetheprocesslater.Ingeneral,programmersdon’thavetothinkabouttheseinterruptions.Theprogrambehavesasifitisrunningcontinuouslyonadedicatedprocessor,exceptthatthetimebetweeninstructionsisunpredictable. Virtualmemory:Mostoperatingsystemscreatetheillusionthateachprocesshasitsownchunkofmemory,isolatedfromallotherprocesses.Again,programmersgenerallydon’thavetothinkabouthowvirtualmemoryworks;theycanproceedasifeveryprogramhasadedicatedchunkofmemory. Deviceabstraction:Processesrunningontheputersharethediskdrive,workinterface,thegraphicscard,andotherhardware.Ifprocessesinteractedwiththishardwaredirectly,withoutcoordination,chaoswouldensue.Forexample,workdataintendedforoneprocessmightbereadbyanother.Ormultipleprocessesmighttrytostoredatainthesamelocationonaharddrive.Itisuptotheoperatingsystemtomaintainorderbyprovidingappropriateabstractions. 12 Chapter2.Processes Asaprogrammer,youdon’tneedtoknowmuchabouthowthesecapabilitiesareimplemented.Butifyouarecurious,youwillfindalotofinterestingthingsgoingonunderthemetaphoricalhood.Andifyouknowwhat’sgoingon,itcanmakeyouabetterprogrammer. 2.3UNIXprocesses WhileIwritethisbook,theprocessIammostawareofismytexteditor,emacs.EveryonceinawhileIswitchtoaterminalwindow,whichisawindowrunningaUNIXshellthatprovidesmand-lineinterface. WhenImovethemouse,thewindowmanagerwakesup,seesthatthemouseisovertheterminalwindow,andwakesuptheterminal.Theterminalwakesuptheshell.IfItypemakeintheshell,itcreatesanewprocesstorunMake,whichcreatesanotherprocesstorunLaTeXandthenanotherprocesstodisplaytheresults. IfIneedtolooksomethingup,Imightswitchtoanother,whichwakesupthewindowmanageragain.IfIclickontheiconforawebbrowser,thewindowmanagercreatesaprocesstorunthewebbrowser.Somebrowsers,likeChrome,createanewprocessforeachwindowandeachtab. AndthosearejusttheprocessesIamawareof.Atthesametimetherearemanyotherprocessesrunninginthebackground.Manyofthemareperformingoperationsrelatedtotheoperatingsystem. Themandpsprintsinformationaboutrunningprocesses.Ifyourunitinaterminal,youmightseesomethinglikethis: PIDTTY2687pts/12801pts/124762pts/1 TIMECMD00:00:00bash00:01:24emacs00:00:00ps ThefirstcolumnistheuniquenumericalprocessID.Thesecondcolumnistheterminalthatcreatedtheprocess;“TTY”standsforteletypewriter,whichwastheoriginalmechanicalterminal. Thethirdcolumnisthetotalprocessortimeusedbytheprocess,inhours,minutes,andseconds.Thelastcolumnisthenameoftherunningprogram.Inthisexample,bashisthenameoftheshellthatinterpretsmandsItypeintheterminal,emacsismytexteditor,andpsistheprogramgeneratingthisoutput. 2.3.UNIXprocesses 13 Bydefault,pslistsonlytheprocessesassociatedwiththecurrentterminal.Ifyouusethe-eflag,yougeteveryprocess(includingprocessesbelongingtootherusers,whichisasecurityflaw,inmyopinion). Onmysystemtherearecurrently233processes.Herearesomeofthem: PIDTTY1?
2?
3?
4?
8?
9?
10?
47?
48?
49?
50?
51?
52?
53?
54?
55?
56?
57?
TIME00:00:1700:00:0000:00:0200:00:0000:00:0000:00:0000:00:1600:00:0000:00:0000:00:0000:00:0000:00:0000:00:0000:00:0000:00:0000:00:0000:00:0000:00:00 CMDinitkthreaddksoftirqd/0kworker/0:0migration/0rcu_bhrcu_schedcpusetkhelpernsbdi-defaultkintegritydkblockdata_sffkhubdmddevfreq_wq initisthefirstprocesscreatedwhentheoperatingsystemstarts.Itcreatesmanyoftheotherprocesses,andthensitsidleuntiltheprocessesitcreatedaredone. kthreaddisaprocesstheoperatingsystemusestocreatenewthreads.We’lltalkmoreaboutthreadslater,butfornowyoucanthinkofathreadaskindofaprocess.Thekatthebeginningstandsforkernel,whichisthepartoftheoperatingsystemresponsibleforcorecapabilitieslikecreatingthreads.Theextradattheendstandsfordaemon,whichisanothernameforprocesseslikethisthatruninthebackgroundandprovideoperatingsystemservices.Inthiscontext,“daemon”isusedinthesenseofahelpfulspirit,withnoconnotationofevil. Basedonthename,youcaninferthatksoftirqdisalsoakerneldaemon;specifically,ithandlessoftwareinterruptrequests,or“softIRQ”. kworkerisaworkerprocesscreatedbythekerneltodosomekindofprocessingforthekernel. 14 Chapter2.Processes Thereareoftenmultipleprocessesrunningthesekernelservices.Onmysystematthemoment,thereare8ksoftirqdprocessesand35kworkerprocesses. Iwon’tgointomoredetailsabouttheotherprocesses,butifyouareinterestedyoucansearchformoreinformationaboutthem.Youshouldrunpsonyoursystempareyourresultstomine. Chapter3 Virtualmemory 3.1Abitofinformationtheory Abitisabinarydigit;itisalsoaunitofinformation.Ifyouhaveonebit,youcanspecifyoneoftwopossibilities,usuallywritten0and1.Ifyouhavetwobits,thereare4binations,00,01,10,and11.Ingeneral,ifyouhavebbits,youcanindicateoneof2bvalues.Abyteis8bits,soitcanholdoneof256values. Goingintheotherdirection,supposeyouwanttostorealetterofthealphabet.Thereare26letters,sohowmanybitsdoyouneed?
With4bits,youcanspecifyoneof16values,sothat’snotenough.With5bits,youcanspecifyupto32values,sothat’senoughforalltheletters,withafewvaluesleftover. Ingeneral,ifyouwanttospecifyoneofNvalues,youshouldchoosethesmallestvalueofbsothat2b≥
N.Takingthelogbase2ofbothsidesyieldsb≥log2N. SupposeIflipacoinandtellyouthee.Ihavegivenyouonebitofinformation.IfIrollasix-sideddieandtellyouthee,Ihavegivenyoulog26bitsofinformation.Andingeneral,iftheprobabilityoftheeis1inN,thentheecontainslog2Nbitsofinformation. Equivalently,iftheprobabilityoftheeisp,thentheinformationcontentis−log2p.Thisquantityiscalledtheself-informationofthee.Itmeasureshowsurprisingtheeis,whichiswhyitisalsocalledsurprisal.Ifyourhorsehasonlyonechancein16ofwinning,andhewins,youget4bitsofinformation(alongwiththepayout).Butifthefavoritewins75%ofthetime,thenewsofthewincontainsonly0.42bits. 16 Chapter3.Virtualmemory Intuitively,unexpectednewscarriesalotofinformation;conversely,ifthereissomethingyouwerealreadyconfidentof,confirmingitcontributesonlyasmallamountofinformation. Foricsinthisbook,wewillneedtofortableconvertingbackandforthbetweenthenumberofbits,b,andthenumberofvaluestheycanencode,N=2b. 3.2Memoryandstorage Whileaprocessisrunning,mostofitsdataisheldinmainmemory,whichisusuallysomekindofrandomessmemory(RAM).Onmostputers,mainmemoryisvolatile,whichmeansthatwhenputershutsdown,thecontentsofmainmemoryarelost.Atypicalputerhas2–8GiBofmemory.GiBstandsfor“gibibyte,”whichis230bytes. Iftheprocessreadsandwritesfiles,thosefilesareusuallystoredonaharddiskdrive(HDD)orsolidstatedrive(SSD).Thesestoragedevicesarenonvolatile,sotheyareusedforlong-termstorage.CurrentlyatypicalputerhasaHDDwithacapacityof500GBto2TB.GBstandsfor“gigabyte,”whichis109bytes.TBstandsfor“terabyte,”whichis1012bytes. YoumighthavenoticedthatIusedthebinaryunitGiBforthesizeofmainmemoryandthedecimalunitsGBandTBforthesizeoftheHDD.Forhistoricalandtechnicalreasons,memoryismeasuredinbinaryunits,anddiskdrivesaremeasuredindecimalunits.InthisbookIwillbecarefultodistinguishbinaryanddecimalunits,butyoushouldbeawarethattheword“gigabyte”andtheabbreviationGBareoftenusedambiguously. Incasualuse,theterm“memory”issometimesusedforHDDsandSSDsaswellasRAM,butthepropertiesofthesedevicesareverydifferent,sowewillneedtodistinguishthem.IwillusestoragetorefertoHDDsandSSDs. 3.3Addressspaces Eachbyteinmainmemoryisspecifiedbyanintegerphysicaladdress.Thesetofvalidphysicaladdressesiscalledthephysicaladdressspace.Itusuallyrunsfrom0toN−1,whereNisthesizeofmainmemory.Onasystemwith1GiBofphysicalmemory,thehighestvalidaddressis230−1,whichis1,073,741,823indecimal,or0x3fffffffinhexadecimal(theprefix0xindicatesahexadecimalnumber). 3.4.Memorysegments 17 However,mostoperatingsystemsprovidevirtualmemory,whichmeansthatprogramsneverdealwithphysicaladdresses,anddon’thavetoknowhowmuchphysicalmemoryisavailable. Instead,programsworkwithvirtualaddresses,whicharenumberedfrom0toM−1,whereMisthenumberofvalidvirtualaddresses.Thesizeofthevirtualaddressspaceisdeterminedbytheoperatingsystemandthehardwareitrunson. Youhaveprobablyheardpeopletalkabout32-bitand64-bitsystems.Thesetermsindicatethesizeoftheregisters,whichisusuallyalsothesizeofavirtualaddress.Ona32-bitsystem,virtualaddressesare32bits,whichmeansthatthevirtualaddressspacerunsfrom0to0xffffffff.Thesizeofthisaddressspaceis232bytes,or4GiB. Ona64-bitsystem,thesizeofthevirtualaddressspaceis264bytes,or24·10246bytes.That’s16exbibytes,whichisaboutabilliontimesbiggerthancurrentphysicalmemories.Itmightseemstrangethatavirtualaddressspacecanbesomuchbiggerthanphysicalmemory,butwewillseesoonhowthatworks. Whenaprogramreadsandwritesvaluesinmemory,itgeneratesvirtualaddresses.Thehardware,withhelpfromtheoperatingsystem,translatestophysicaladdressesbeforeessingmainmemory.Thistranslationisdoneonaper-processbasis,soeveniftwoprocessesgeneratethesamevirtualaddress,theywouldmaptodifferentlocationsinphysicalmemory. Thus,virtualmemoryisoneimportantwaytheoperatingsystemisolatesprocessesfromeachother.Ingeneral,aprocesscannotessdatabelongingtoanotherprocess,becausethereisnovirtualaddressitcangeneratethatmapstophysicalmemoryallocatedtoanotherprocess. 3.4Memorysegments Thedataofarunningprocessanizedintofivesegments: Thecodesegmentcontainstheprogramtext;thatis,themachinelanguageinstructionsthatmakeuptheprogram. Thestaticsegmentcontainsimmutablevalues,likestringliterals.Forexample,ifyourprogramcontainsthestring"Hello,World",thosecharacterswillbestoredinthestaticsegment. Theglobalsegmentcontainsglobalvariablesandlocalvariablesthataredeclaredstatic. 18 Chapter3.Virtualmemory Theheapsegmentcontainschunksofmemoryallocatedatruntime,mostoftenbycallingtheClibraryfunctionmalloc. Thestacksegmentcontainsthecallstack,whichisasequenceofstackframes.Eachtimeafunctioniscalled,astackframeisallocatedtocontaintheparametersandlocalvariablesofthefunction.Whenthepletes,itsstackframeisremovedfromthestack. Thearrangementofthesesegmentsisdeterminedpartlybypilerandpartlybytheoperatingsystem.Thedetailsvaryfromonesystemtoanother,butinthemonarrangement: Thetextsegmentisnearthe“bottom”ofmemory,thatis,ataddressesnear0. Thestaticsegmentisoftenjustabovethetextsegment,thatis,athigheraddresses. Theglobalsegmentisoftenjustabovethestaticsegment. Theheapisoftenabovetheglobalsegment.Asitexpands,itgrowsuptowardlargeraddresses. Thestackisnearofmemory;thatis,nearthehighestaddressesinthevirtualaddressspace.Asthestackexpands,itgrowsdowntowardsmalleraddresses. Todeterminethelayoutofthesesegmentsonyoursystem,tryrunningthisprogram,whichisinaspace.cintherepositoryforthisbook(seeSection0.1). #include
Thebasicmechanismissimple,butasimpleimplementationwouldbetooslowandtaketoomuchspace.Soactualimplementationsareabitplicated. 3.6.Addresstranslation 21 Mostprocessorsprovideamemorymanagementunit(MMU)thatsitsbetweentheCPUandmainmemory.TheMMUperformsfasttranslationbetweenVAsandPAs.
1.Whenaprogramreadsorwritesavariable,theCPUgeneratesaVA.
2.TheMMUsplitstheVAintotwoparts,calledthepagenumberandtheoffset.A“page”isachunkofmemory;thesizeofapagedependsontheoperatingsystemandthehardware,monsizesare1–4KiB.
3.TheMMUlooksupthepagenumberinthetranslationlookasidebuffer(TLB)andgetsthecorrespondingphysicalpagenumber.ThenbinesthephysicalpagenumberwiththeoffsettoproduceaPA.
4.ThePAispassedtomainmemory,whichreadsorwritesthegivenlocation. TheTLBcontainscachedcopiesofdatafromthepagetable(whichisstoredinkernelmemory).Thepagetablecontainsthemappingfromvirtualpagenumberstophysicalpagenumbers.Sinceeachprocesshasitsownpagetable,theTLBhastomakesureitonlyusesentriesfromthepagetableoftheprocessthat’srunning. Figure3.1showsadiagramofthisprocess.Toseehowitallworks,supposethattheVAis32bitsandthephysicalmemoryis1GiB,dividedinto1KiBpages. Since1GiBis230bytesand1KiBis210bytes,thereare220physicalpages,sometimescalled“frames.” Thesizeofthevirtualaddressspaceis232Bandthesizeofapageis210B,sothereare222virtualpages. Thesizeoftheoffsetisdeterminedbythepagesize.Inthisexamplethepagesizeis210B,soittakes10bitstospecifyabyteonapage. IfaVAis32bitsandtheoffsetis10bits,theremaining22bitsmakeupthevirtualpagenumber. Sincethereare220physicalpages,eachphysicalpagenumberis20bits.Addinginthe10bitoffset,theresultingPAsare30bits. Sofarthisallseemsfeasible.Butlet’sthinkabouthowbigapagetablemighthavetobe.Thesimplestimplementationofapagetableisanarraywithoneentryforeachvirtualpage.Eachentrywouldcontainaphysicalpagenumber, 22 Chapter3.Virtualmemory whichis20bitsinthisexample,plussomeadditionalinformationabouteachframe.Soweexpect3–4bytesperentry.Butwith222virtualpages,thepagetablewouldrequire224bytes,or16MiB. Andsinceweneedapagetableforeachprocess,asystemrunning256processeswouldneed232bytes,or4GiB,justforpagetables!
Andthat’sjustwith32-bitvirtualaddresses.With48-or64-bitVAs,thenumbersareridiculous. Fortunately,wedon’tactuallyneedthatmuchspace,becausemostprocessesdon’tuseevenasmallfractionoftheirvirtualaddressspace.Andifaprocessdoesn’tuseavirtualpage,wedon’tneedanentryinthepagetableforit. Anotherwaytosaythesamethingisthatpagetablesare“sparse”,whichimpliesthatthesimpleimplementation,anarrayofpagetableentries,isabadidea.Fortunately,thereareseveralgoodimplementationsforsparsearrays. Oneoptionisamultilevelpagetable,whichiswhatmanyoperatingsystems,includingLinux,use.Anotheroptionisanassociativetable,whereeachentryincludesboththevirtualpagenumberandthephysicalpagenumber.Searchinganassociativetablecanbeslowinsoftware,butinhardwarewecansearchtheentiretableinparallel,soassociativearraysareoftenusedtorepresentthepagetableentriesintheTLB. Youcanreadmoreabouttheseimplementationsat/wiki/Page_table;youmightfindthedetailsinteresting.Butthefundamentalideaisthatpagetablesaresparse,sowehavetochooseagoodimplementationforsparsearrays. Imentionedearlierthattheoperatingsystemcaninterruptarunningprocess,saveitsstate,andthenrunanotherprocess.Thismechanismiscalledacontextswitch.Sinceeachprocesshasitsownpagetable,theoperatingsystemhastoworkwiththeMMUtomakesureeachprocessgetstherightpagetable.Inoldermachines,thepagetableinformationintheMMUhadtobereplacedduringeverycontextswitch,whichwasexpensive.Innewersystems,eachpagetableentryintheMMUincludestheprocessID,sopagetablesfrommultipleprocessescanbeintheMMUatthesametime. Chapter4 Filesandfilesystems Whenapletes(orcrashes),anydatastoredinmainmemoryislost.Butdatastoredonaharddiskdrive(HDD)orsolidstatedrive(SSD)is“persistent;”thatis,itsurvivesafterthepletes,evenifputershutsdown.Harddiskdrivesplicated.Dataisstoredinblocks,whicharelaidoutinsectors,whichmakeuptracks,whicharearrangedinconcentriccirclesonplatters.Solidstatedrivesaresimplerinonesense,becauseblocksarenumberedsequentially,buttheyraiseadiffplication:eachblockcanbewrittenalimitednumberoftimesbeforeitesunreliable.Asaprogrammer,youdon’twanttodealwithplications.Whatyouwantisanappropriateabstractionofpersistentstoragehardware.Themonabstractioniscalleda“filesystem.”Abstractly: A“filesystem”isamappingfromeachfile’snametoitscontents.Ifyouthinkofthenamesaskeys,andthecontentsasvalues,afilesystemisakindofkey-valuedatabase(see/wiki/Key-value_database). A“file”isasequenceofbytes. Filenamesareusuallystrings,andtheyareusually“hierarchical”;thatis,thestringspecifiesapathfrom-leveldirectory(orfolder),throughaseriesofsubdirectories,toaspecificfile. 24 Chapter4.Filesandfilesystems Theprimarydifferencebetweentheabstractionandtheunderlyingmechanismisthatfilesarebyte-basedandpersistentstorageisblock-based.Theoperatingsystemtranslatesbyte-basedfileoperationsintheClibraryintoblock-basedoperationsonstoragedevices.Typicalblocksizesare1–8KiB. Forexample,thefollowingcodeopensafileandreadsthefirstbyte: FILE*fp=fopen("/home/downey/file.txt","r");charc=fgetc(fp);fclose(fp); Whenthiscoderuns: 1.fopenusesthefilenametofind-leveldirectory,called/,thesubdirectoryhome,andthesub-subdirectorydowney.
2.Itfindsthefilenamedfile.txtand“opens”itforreading,whichmeansitcreatesadatastructurethatrepresentsthefilebeingread.Amongotherthings,thisdatastructurekeepstrackofhowmuchofthefilehasbeenread,calledthe“fileposition”. InDOS,thisdatastructureiscalledaFileControlBlock,butIwanttoavoidthattermbecauseinUNIXitmeanssomethingelse.InUNIX,thereseemstobenogoodnameforit.Itisanentryintheopenfiletable,soIwillcallitanOpenFileTableEntry.
3.Whenwecallfgetc,theoperatingsystemcheckswhetherthenextcharacterofthefileisalreadyinmemory.Ifso,itreadsthenextcharacter,advancesthefileposition,andreturnstheresult.
4.Ifthenextcharacterisnotinmemory,theoperatingsystemissuesanI/Orequesttogetthenextblock.Diskdrivesareslow,soaprocesswaitingforablockfromdiskisusuallyinterruptedsoanotherprocesscanrununtilthedataarrives.
5.WhentheI/Ooperationplete,thenewblockofdataisstoredinmemory,andtheprocessresumes.Itreadsthefirstcharacterandstoresitasalocalvariable.
6.Whentheprocessclosesthefile,theoperatingpletesorcancelsanypendingoperations,removesdatastoredinmemory,andfreestheOpenFileTableEntry. Theprocessforwritingafileissimilar,buttherearesomeadditionalsteps.Hereisanexamplethatopensafileforwritingandchangesthefirstcharacter. 4.1.Diskperformance 25 FILE*fp=fopen("/home/downey/file.txt","w");fputc('b',fp);fclose(fp);Whenthiscoderuns:
1.Again,fopenusesthefilenametofindthefile.Ifitdoesnotalreadyexist,itcreatesanewfileandaddsanentryintheparentdirectory,/home/downey.
2.TheoperatingsystemcreatesanOpenFileTableEntrythatindicatesthatthefileisopenforwriting,andsetsthefilepositionto0. 3.fputcattemptstowrite(orre-write)thefirstbyteofthefile.Ifthefilealreadyexists,theoperatingsystemhastoloadthefirstblockintomemory.Otherwiseitallocatesanewblockinmemoryandrequestsanewblockondisk.
4.Aftertheblockinmemoryismodified,itmightnotbecopiedbacktothediskrightaway.Ingeneral,datawrittentoafileis“buffered”,whichmeansitisstoredinmemoryandonlywrittentodiskwhenthereisatleastoneblocktowrite.
5.Whenthefileisclosed,anybufferedda
声明：
该资讯来自于互联网网友发布，如有侵犯您的权益请联系我们。