UNIXImplementation K.Thompson ABSTRACT Thispaperdescribesinhigh-leveltermstheimplementationoftheresident UNIX◯rkernel.Thisdiscussionisbrokenintothreeparts.Thefirstpart describeshowtheUNIXsystemviewsprocesses,users,andprograms.Thesecond partdescribestheI/Osystem.ThelastpartdescribestheUNIXfilesystem. 1.INTRODUCTION TheUNIXkernelconsistsofabout10,000linesofCcodeandabout1,000linesofassembly code.Theassemblycodecanbefurtherbrokendowninto200linesincludedforthesakeofefficiency(theycouldhavebeenwritteninC)and800linestoperformhardwarefunctionsnotpossibleinC. Thiscoderepresents5to10percentofwhathasbeenlumpedintothebroadexpression ‘‘theUNIXoperatingsystem.’’ThekernelistheonlyUNIXcodethatcannotbesubstitutedbya usertohisownliking.Forthisreason,thekernelshouldmakeasfewrealdecisionsaspossible. Thisdoesnotmeantoallowtheuseramillionoptionstodothesamething.Rather,itmeansto allowonlyonewaytodoonething,buthavethatwaybetheleast-commondivisorofallthe optionsthatmighthavebeenprovided. Whatisorisnotimplementedinthekernelrepresentsbothagreatresponsibilityanda greatpower.Itisasoap-boxplatformon‘‘thewaythingsshouldbedone.’’Evenso,if‘‘theway’’ istooradical,noonewillfollowit.Everyimportantdecisionwasweighedcarefully.Throughout, simplicityhasbeensubstitutedforefficiency.Complexalgorithmsareusedonlyiftheircomplexitycanbelocalized. 2.PROCESSCONTROL IntheUNIXsystem,auserexecutesprogramsinanenvironmentcalledauserprocess. Whenasystemfunctionisrequired,theuserprocesscallsthesystemasasubroutine.Atsome pointinthiscall,thereisadistinctswitchofenvironments.Afterthis,theprocessissaidtobea systemprocess.Inthenormaldefinitionofprocesses,theuserandsystemprocessesaredifferent phasesofthesameprocess(theyneverexecutesimultaneously).Forprotection,eachsystemprocesshasitsownstack. Theuserprocessmayexecutefromaread-onlytextsegment,whichissharedbyallpro-cessesexecutingthesamecode.Thereisnofunctionalbenefitfromshared-textsegments.An efficiencybenefitcomesfromthefactthatthereisnoneedtoswapread-onlysegmentsout becausetheoriginalcopyonsecondarymemoryisstillcurrent.Thisisagreatbenefittointeractiveprogramsthattendtobeswappedwhilewaitingforterminalinput.Furthermore,iftwoprocessesareexecutingsimultaneouslyfromthesamecopyofaread-onlysegment,onlyonecopy needstoresideinprimarymemory.Thisisasecondaryeffect,becausesimultaneousexecutionof aprogramisnotcommon.Itisironicthatthiseffect,whichreducestheuseofprimarymemory, onlycomesintoplaywhenthereisanoverabundanceofprimarymemory,thatis,whenthereis enoughmemorytokeepwaitingprocessesloaded. Allcurrentread-onlytextsegmentsinthesystemaremaintainedfromthetexttable.Atext tableentryholdsthelocationofthetextsegmentonsecondarymemory.Ifthesegmentisloaded, -2-thattablealsoholdstheprimarymemorylocationandthecountofthenumberofprocessesshar-ingthisentry.Whenthiscountisreducedtozero,theentryisfreedalongwithanyprimaryand secondarymemoryholdingthesegment.Whenaprocessfirstexecutesashared-textsegment,a texttableentryisallocatedandthesegmentisloadedontosecondarymemory.Ifasecondprocessexecutesatextsegmentthatisalreadyallocated,theentryreferencecountissimplyincremented. Auserprocesshassomestrictlyprivateread-writedatacontainedinitsdatasegment.As faraspossible,thesystemdoesnotusetheuser’sdatasegmenttoholdsystemdata.Inparticular,therearenoI/Obuffersintheuseraddressspace. Theuserdatasegmenthastwogrowingboundaries.One,increasedautomaticallybythe systemasaresultofmemoryfaults,isusedforastack.Thesecondboundaryisonlygrown(or shrunk)byexplicitrequests.Thecontentsofnewlyallocatedprimarymemoryisinitializedto zero. Alsoassociatedandswappedwithaprocessisasmallfixed-sizesystemdatasegment.This segmentcontainsallthedataabouttheprocessthatthesystemneedsonlywhentheprocessis active.Examplesofthekindofdatacontainedinthesystemdatasegmentare:savedcentralprocessorregisters,openfiledescriptors,accountinginformation,scratchdataarea,andthestackfor thesystemphaseoftheprocess.Thesystemdatasegmentisnotaddressablefromtheuserprocessandisthereforeprotected. Last,thereisaprocesstablewithoneentryperprocess.Thisentrycontainsallthedata neededbythesystemwhentheprocessisnotactive.Examplesaretheprocess’sname,thelocationoftheothersegments,andschedulinginformation.Theprocesstableentryisallocatedwhen theprocessiscreated,andfreedwhentheprocessterminates.Thisprocessentryisalways directlyaddressablebythekernel. Figure1showstherelationshipsbetweenthevariousprocesscontroldata.Inasense,the processtableisthedefinitionofallprocesses,becauseallthedataassociatedwithaprocessmay beaccessedstartingfromtheprocesstableentry. Fig.1—Processcontroldatastructure. 2.1.Processcreationandprogramexecution Processesarecreatedbythesystemprimitivefork.Thenewlycreatedprocess(child)isa copyoftheoriginalprocess(parent).Thereisnodetectablesharingofprimarymemorybetween thetwoprocesses.(Ofcourse,iftheparentprocesswasexecutingfromaread-onlytextsegment, thechildwillsharethetextsegment.)Copiesofallwritabledatasegmentsaremadeforthechild process.Filesthatwereopenbeforetheforkaretrulysharedafterthefork.Theprocessesare informedastotheirpartintherelationshiptoallowthemtoselecttheirown(usuallynon- -3-identical)destiny.Theparentmaywaitfortheterminationofanyofitschildren. Aprocessmayexecafile.Thisconsistsofexchangingthecurrenttextanddatasegments oftheprocessfornewtextanddatasegmentsspecifiedinthefile.Theoldsegmentsarelost. Doinganexecdoesnotchangeprocesses;theprocessthatdidtheexecpersists,butafterthe execitisexecutingadifferentprogram.Filesthatwereopenbeforetheexecremainopenafter theexec. Ifaprogram,saythefirstpassofacompiler,wishestooverlayitselfwithanotherprogram, saythesecondpass,thenitsimplyexecsthesecondprogram.Thisisanalogoustoa‘‘goto.’’Ifa programwishestoregaincontrolafterexecingasecondprogram,itshouldforkachildprocess, havethechildexecthesecondprogram,andhavetheparentwaitforthechild.Thisisanalogoustoa‘‘call.’’BreakingupthecallintoabindingfollowedbyatransferissimilartothesubroutinelinkageinSL-5.1 2.2.Swapping Themajordataassociatedwithaprocess(theuserdatasegment,thesystemdatasegment, andthetextsegment)areswappedtoandfromsecondarymemory,asneeded.Theuserdatasegmentandthesystemdatasegmentarekeptincontiguousprimarymemorytoreduceswapping latency.(Whenlow-latencydevices,suchasbubbles,CCDs,orscatter/gatherdevices,areused, thisdecisionwillhavetobereconsidered.)Allocationofbothprimaryandsecondarymemoryis performedbythesamesimplefirst-fitalgorithm.Whenaprocessgrows,anewpieceofprimary memoryisallocated.Thecontentsoftheoldmemoryiscopiedtothenewmemory.Theold memoryisfreedandthetablesareupdated.Ifthereisnotenoughprimarymemory,secondary memoryisallocatedinstead.Theprocessisswappedoutontothesecondarymemory,readytobe swappedinwithitsnewsize. Oneseparateprocessinthekernel,theswappingprocess,simplyswapstheotherprocesses inandoutofprimarymemory.Itexaminestheprocesstablelookingforaprocessthatis swappedoutandisreadytorun.Itallocatesprimarymemoryforthatprocessandreadsitssegmentsintoprimarymemory,wherethatprocesscompetesforthecentralprocessorwithother loadedprocesses.Ifnoprimarymemoryisavailable,theswappingprocessmakesmemoryavailablebyexaminingtheprocesstableforprocessesthatcanbeswappedout.Itselectsaprocessto swapout,writesittosecondarymemory,freestheprimarymemory,andthengoesbacktolook foraprocesstoswapin. Thustherearetwospecificalgorithmstotheswappingprocess.Whichofthepossiblymany processesthatareswappedoutistobeswappedin?Thisisdecidedbysecondarystorageresidencetime.Theonewiththelongesttimeoutisswappedinfirst.Thereisaslightpenaltyfor largerprocesses.Whichofthepossiblymanyprocessesthatareloadedistobeswappedout? Processesthatarewaitingforslowevents(i.e.,notcurrentlyrunningorwaitingfordiskI/O)are pickedfirst,byageinprimarymemory,againwithsizepenalties.Theotherprocessesareexaminedbythesameagealgorithm,butarenottakenoutunlesstheyareatleastofsomeage.This addshysteresistotheswappingandpreventstotalthrashing. Theseswappingalgorithmsarethemostsuspectinthesystem.Withlimitedprimarymemory,thesealgorithmscausetotalswapping.Thisisnotbadinitself,becausetheswappingdoes notimpacttheexecutionoftheresidentprocesses.However,iftheswappingdevicemustalsobe usedforfilestorage,theswappingtrafficseverelyimpactsthefilesystemtraffic.Itisexactly thesesmallsystemsthattendtodoubleusageoflimiteddiskresources. 2.3.Synchronizationandscheduling Processsynchronizationisaccomplishedbyhavingprocesseswaitforevents.Eventsare representedbyarbitraryintegers.Byconvention,eventsarechosentobeaddressesoftablesassociatedwiththoseevents.Forexample,aprocessthatiswaitingforanyofitschildrentoterminatewillwaitforaneventthatistheaddressofitsownprocesstableentry.Whenaprocess 1 -4-terminates,itsignalstheeventrepresentedbyitsparent’sprocesstableentry.Signalinganevent onwhichnoprocessiswaitinghasnoeffect.Similarly,signalinganeventonwhichmanyprocessesarewaitingwillwakeallofthemup.ThisdiffersconsiderablyfromDijkstra’sPandVsynchronizationoperations,2inthatnomemoryisassociatedwithevents.Thusthereneedbeno allocationofeventspriortotheiruse.Eventsexistsimplybybeingused. Onthenegativeside,becausethereisnomemoryassociatedwithevents,nonotionof‘‘how much’’canbesignaledviatheeventmechanism.Forexample,processesthatwantmemorymight waitonaneventassociatedwithmemoryallocation.Whenanyamountofmemorybecomes available,theeventwouldbesignaled.Allthecompetingprocesseswouldthenwakeuptofight overthenewmemory.(Inreality,theswappingprocessistheonlyprocessthatwaitsforprimary memorytobecomeavailable.) Ifaneventoccursbetweenthetimeaprocessdecidestowaitforthateventandthetime thatprocessentersthewaitstate,thentheprocesswillwaitonaneventthathasalreadyhappened(andmayneverhappenagain).Thisraceconditionhappensbecausethereisnomemory associatedwiththeeventtoindicatethattheeventhasoccurred;theonlyactionofaneventisto changeasetofprocessesfromwaitstatetorunstate.Thisproblemisrelievedlargelybythefact thatprocessswitchingcanonlyoccurinthekernelbyexplicitcallstotheevent-waitmechanism. Iftheeventinquestionissignaledbyanotherprocess,thenthereisnoproblem.Butiftheevent issignaledbyahardwareinterrupt,thenspecialcaremustbetaken.Thesesynchronizationraces posethebiggestproblemwhenUNIXisadaptedtomultiple-processorconfigurations.3 Theevent-waitcodeinthekernelislikeaco-routinelinkage.Atanytime,allbutoneof theprocesseshascalledevent-wait.Theremainingprocessistheonecurrentlyexecuting.When itcallsevent-wait,aprocesswhoseeventhasbeensignaledisselectedandthatprocessreturns fromitscalltoevent-wait. Whichoftherunableprocessesistorunnext?Associatedwitheachprocessisapriority. Thepriorityofasystemprocessisassignedbythecodeissuingthewaitonanevent.Thisis roughlyequivalenttotheresponsethatonewouldexpectonsuchanevent.Diskeventshavehigh priority,teletypeeventsarelow,andtime-of-dayeventsareverylow.(Fromobservation,thedif-ferenceinsystemprocessprioritieshaslittleornoperformanceimpact.)Alluser-processpriori-tiesarelowerthanthelowestsystempriority.User-processprioritiesareassignedbyanalgorithm basedontherecentratiooftheamountofcomputetimetorealtimeconsumedbytheprocess.A processthathasusedalotofcomputetimeinthelastreal-timeunitisassignedalowuserprior-ity.Becauseinteractiveprocessesarecharacterizedbylowratiosofcomputetorealtime,interac-tiveresponseismaintainedwithoutanyspecialarrangements. Theschedulingalgorithmsimplypickstheprocesswiththehighestpriority,thuspickingall systemprocessesfirstanduserprocessessecond.Thecompute-to-real-timeratioisupdatedevery second.Thus,allotherthingsbeingequal,loopinguserprocesseswillbescheduledround-robin witha1-secondquantum.Ahigh-priorityprocesswakingupwillpreemptarunning,low-priority process.Theschedulingalgorithmhasaverydesirablenegativefeedbackcharacter.Ifaprocess usesitshighprioritytohogthecomputer,itsprioritywilldrop.Atthesametime,ifalowpriorityprocessisignoredforalongtime,itsprioritywillrise. 3.I/OSYSTEM TheI/Osystemisbrokenintotwocompletelyseparatesystems:theblockI/Osystemand thecharacterI/Osystem.Inretrospect,thenamesshouldhavebeen‘‘structuredI/O’’and ‘‘unstructuredI/O,’’respectively;whiletheterm‘‘blockI/O’’hassomemeaning,‘‘characterI/O’’ isacompletemisnomer. Devicesarecharacterizedbyamajordevicenumber,aminordevicenumber,andaclass (blockorcharacter).Foreachclass,thereisanarrayofentrypointsintothedevicedrivers.The majordevicenumberisusedtoindexthearraywhencallingthecodeforaparticulardevice 2 3 -5-driver.Theminordevicenumberispassedtothedevicedriverasanargument.Theminor numberhasnosignificanceotherthanthatattributedtoitbythedriver.Usually,thedriveruses theminornumbertoaccessoneofseveralidenticalphysicaldevices. Theuseofthearrayofentrypoints(configurationtable)astheonlyconnectionbetweenthe systemcodeandthedevicedriversisveryimportant.Earlyversionsofthesystemhadamuch lessformalconnectionwiththedrivers,sothatitwasextremelyhardtohandcraftdifferentlyconfiguredsystems.Nowitispossibletocreatenewdevicedriversinanaverageofafewhours.The configurationtableinmostcasesiscreatedautomaticallybyaprogramthatreadsthesystem’s partslist. 3.1.BlockI/Osystem ThemodelblockI/Odeviceconsistsofrandomlyaddressed,secondarymemoryblocksof 512byteseach.Theblocksareuniformlyaddressed0,1,...uptothesizeofthedevice.The blockdevicedriverhasthejobofemulatingthismodelonaphysicaldevice. TheblockI/Odevicesareaccessedthroughalayerofbufferingsoftware.Thesystemmaintainsalistofbuffers(typicallybetween10and70)eachassignedadevicenameandadevice address.Thisbufferpoolconstitutesadatacachefortheblockdevices.Onareadrequest,the cacheissearchedforthedesiredblock.Iftheblockisfound,thedataaremadeavailabletothe requesterwithoutanyphysicalI/O.Iftheblockisnotinthecache,theleastrecentlyusedblock inthecacheisrenamed,thecorrectdevicedriveriscalledtofilluptherenamedbuffer,andthen thedataaremadeavailable.Writerequestsarehandledinananalogousmanner.Thecorrect bufferisfoundandrelabeledifnecessary.Thewriteisperformedsimplybymarkingthebufferas ‘‘dirty.’’ThephysicalI/Oisthendeferreduntilthebufferisrenamed. ThebenefitsinreductionofphysicalI/Oofthisschemearesubstantial,especiallyconsideringthefilesystemimplementation.Thereare,however,somedrawbacks.Theasynchronous natureofthealgorithmmakeserrorreportingandmeaningfulusererrorhandlingalmostimpossible.ThecavalierapproachtoI/OerrorhandlingintheUNIXsystemispartlyduetotheasynchronousnatureoftheblockI/Osystem.Asecondproblemisinthedelayedwrites.Ifthesystemstopsunexpectedly,itisalmostcertainthatthereisalotoflogicallycomplete,butphysically incomplete,I/Ointhebuffers.ThereisasystemprimitivetoflushalloutstandingI/Oactivity fromthebuffers.Periodicuseofthisprimitivehelps,butdoesnotsolve,theproblem.Finally, theassociativityinthebufferscanalterthephysicalI/OsequencefromthatofthelogicalI/O sequence.Thismeansthattherearetimeswhendatastructuresondiskareinconsistent,even thoughthesoftwareiscarefultoperformI/Ointhecorrectorder.Onnon-randomdevices, notablymagnetictape,theinversionsofwritescanbedisastrous.Theproblemwithmagnetic tapesis‘‘cured’’byallowingonlyoneoutstandingwriterequestperdrive. 3.2.CharacterI/Osystem ThecharacterI/OsystemconsistsofalldevicesthatdonotfallintotheblockI/Omodel. Thisincludesthe‘‘classical’’characterdevicessuchascommunicationslines,papertape,andline printers.Italsoincludesmagnetictapeanddiskswhentheyarenotusedinastereotypedway, forexample,80-bytephysicalrecordsontapeandtrack-at-a-timediskcopies.Inshort,thechar-acterI/Ointerfacemeans‘‘everythingotherthanblock.’’I/Orequestsfromtheuseraresentto thedevicedriveressentiallyunaltered.Theimplementationoftheserequestsis,ofcourse,upto thedevicedriver.Thereareguidelinesandconventionstohelptheimplementationofcertain typesofdevicedrivers. 3.2.1.Diskdrivers Diskdriversareimplementedwithaqueueoftransactionrecords.Eachrecordholdsa read/writeflag,aprimarymemoryaddress,asecondarymemoryaddress,andatransferbyte count.Swappingisaccomplishedbypassingsucharecordtotheswappingdevicedriver.The blockI/Ointerfaceisimplementedbypassingsuchrecordswithrequeststofillandemptysystem buffers.ThecharacterI/Ointerfacetothediskdriverscreateatransactionrecordthatpoints -6-directlyintotheuserarea.Theroutinethatcreatesthisrecordalsoinsuresthattheuserisnot swappedduringthisI/Otransaction.Thusbyimplementingthegeneraldiskdriver,itispossible tousethediskasablockdevice,acharacterdevice,andaswapdevice.Theonlyreallydiskspecificcodeinnormaldiskdriversisthepre-sortoftransactionstominimizelatencyforapartic-ulardevice,andtheactualissuingoftheI/Orequest. 3.2.2.Characterlists Realcharacter-orienteddevicesmaybeimplementedusingthecommoncodetohandlechar-acterlists.Acharacterlistisaqueueofcharacters.Oneroutineputsacharacteronaqueue. Anothergetsacharacterfromaqueue.Itisalsopossibletoaskhowmanycharactersarecurrentlyonaqueue.Storageforallqueuesinthesystemcomesfromasinglecommonpool. Puttingacharacteronaqueuewillallocatespacefromthecommonpoolandlinkthecharacter ontothedatastructuredefiningthequeue.Gettingacharacterfromaqueuereturnsthecorrespondingspacetothepool. Atypicalcharacter-outputdevice(papertapepunch,forexample)isimplementedbypass-ingcharactersfromtheuserontoacharacterqueueuntilsomemaximumnumberofcharactersis onthequeue.TheI/Oisproddedtostartassoonasthereisanythingonthequeueand,once started,itissustainedbyhardwarecompletioninterrupts.Eachtimethereisacompletioninterrupt,thedrivergetsthenextcharacterfromthequeueandsendsittothehardware.The numberofcharactersonthequeueischeckedand,asthecountfallsthroughsomeintermediate level,anevent(thequeueaddress)issignaled.Theprocessthatispassingcharactersfromthe usertothequeuecanbewaitingontheevent,andrefillthequeuetoitsmaximumwhenthe eventoccurs. Atypicalcharacterinputdevice(forexample,apapertapereader)ishandledinaverysimilarmanner. Anotherclassofcharacterdevicesistheterminals.Aterminalisrepresentedbythreecharacterqueues.Therearetwoinputqueues(rawandcanonical)andanoutputqueue.Characters goingtotheoutputofaterminalarehandledbycommoncodeexactlyasdescribedabove.The maindifferenceisthatthereisalsocodetointerprettheoutputstreamasASCIIcharactersandto performsometranslations,e.g.,escapesfordeficientterminals.Anothercommonaspectofterminalsiscodetoinsertreal-timedelayaftercertaincontrolcharacters. Inputonterminalsisalittledifferent.Charactersarecollectedfromtheterminaland placedonarawinputqueue.Somedevice-dependentcodeconversionandescapeinterpretationis handledhere.Whenalineiscompleteintherawqueue,aneventissignaled.Thecodecatching thissignalthencopiesalinefromtherawqueuetoacanonicalqueueperformingthecharacter eraseandlinekillediting.Userreadrequestsonterminalscanbedirectedateithertherawor canonicalqueues. 3.2.3.Othercharacterdevices Finally,therearedevicesthatfitnogeneralcategory.Thesedevicesaresetupascharacter I/Odrivers.AnexampleisadriverthatreadsandwritesunmappedprimarymemoryasanI/O device.Somedevicesaretoofasttobetreatedacharacterattime,butdonotfitthediskI/O mold.Examplesarefastcommunicationslinesandfastlineprinters.Thesedeviceseitherhave theirownbuffersor‘‘borrow’’blockI/Obuffersforawhileandthengivethemback. 4.THEFILESYSTEM IntheUNIXsystem,afileisa(one-dimensional)arrayofbytes.Nootherstructureoffilesis impliedbythesystem.Filesareattachedanywhere(andpossiblymultiply)ontoahierarchyof directories.Directoriesaresimplyfilesthatuserscannotwrite.Forafurtherdiscussionofthe externalviewoffilesanddirectories,seeRef.4. 4Thisissue.

-7-TheUNIXfilesystemisadiskdatastructureaccessedcompletelythroughtheblockI/Osys-tem.Asstatedbefore,thecanonicalviewofa‘‘disk’’isarandomlyaddressablearrayof512-byte blocks.Afilesystembreaksthediskintofourself-identifyingregions.Thefirstblock(address0) isunusedbythefilesystem.Itisleftasideforbootingprocedures.Thesecondblock(address1) containstheso-called‘‘super-block.’’Thisblock,amongotherthings,containsthesizeofthedisk andtheboundariesoftheotherregions.Nextcomesthei-list,alistoffiledefinitions.Eachfile definitionisa64-bytestructure,calledani-node.Theoffsetofaparticulari-nodewithinthei-listiscalleditsi-number.Thecombinationofdevicename(majorandminornumbers)andi-numberservestouniquelynameaparticularfile.Afterthei-list,andtotheendofthedisk,come freestorageblocksthatareavailableforthecontentsoffiles. Thefreespaceonadiskismaintainedbyalinkedlistofavailablediskblocks.Everyblock inthischaincontainsadiskaddressofthenextblockinthechain.Theremainingspacecontains theaddressofupto50diskblocksthatarealsofree.ThuswithoneI/Ooperation,thesystem obtains50freeblocksandapointerwheretofindmore.Thediskallocationalgorithmsarevery straightforward.Sinceallallocationisinfixed-sizeblocksandthereisstrictaccountingofspace, thereisnoneedtocompactorgarbagecollect.However,asdiskspacebecomesdispersed,latency graduallyincreases.Someinstallationschoosetooccasionallycompactdiskspacetoreduce latency. Ani-nodecontains13diskaddresses.Thefirst10oftheseaddressespointdirectlyatthe first10blocksofafile.Ifafileislargerthan10blocks(5,120bytes),thentheeleventhaddress pointsatablockthatcontainstheaddressesofthenext128blocksofthefile.Ifthefileisstill largerthanthis(70,656bytes),thenthetwelfthblockpointsatupto128blocks,eachpointingto 128blocksofthefile.Filesyetlarger(8,459,264bytes)usethethirteenthaddressfora‘‘triple indirect’’address.Thealgorithmendsherewiththemaximumfilesizeof1,082,201,087bytes. Alogicaldirectoryhierarchyisaddedtothisflatphysicalstructuresimplybyaddinganew typeoffile,thedirectory.Adirectoryisaccessedexactlyasanordinaryfile.Itcontains16-byte entriesconsistingofa14-bytenameandani-number.Therootofthehierarchyisataknowni-number(viz.,2).Thefilesystemstructureallowsanarbitrary,directedgraphofdirectorieswith regularfileslinkedinatarbitraryplacesinthisgraph.Infact,veryearlyUNIXsystemsusedsuch astructure.Administrationofsuchastructurebecamesochaoticthatlatersystemswere restrictedtoadirectorytree.Evennow,withregularfileslinkedmultiplyintoarbitraryplacesin thetree,accountingforspacehasbecomeaproblem.Itmaybecomenecessarytorestrictthe entirestructuretoatree,andallowanewformoflinkingthatissubservienttothetreestructure. Thefilesystemallowseasycreation,easyremoval,easyrandomaccessing,andveryeasy spaceallocation.Withmostphysicaladdressesconfinedtoasmallcontiguoussectionofdisk,itis alsoeasytodump,restore,andchecktheconsistencyofthefilesystem.Largefilessufferfrom indirectaddressing,butthecachepreventsmostoftheimpliedphysicalI/Owithoutaddingmuch execution.Thespaceoverheadpropertiesofthisschemearequitegood.Forexample,onone particularfilesystem,thereare25,000filescontaining130Mbytesofdata-filecontent.Theover-head(i-node,indirectblocks,andlastblockbreakage)isabout11.5Mbytes.Thedirectorystruc-turetosupportthesefileshasabout1,500directoriescontaining0.6Mbytesofdirectorycontent andabout0.5Mbytesofoverheadinaccessingthedirectories.Addedupanyway,thiscomesout tolessthana10percentoverheadforactualstoreddata.Mostsystemshavethismuchoverhead inpaddedtrailingblanksalone. 4.1.Filesystemimplementation Becausethei-nodedefinesafile,theimplementationofthefilesystemcentersaroundaccess tothei-node.Thesystemmaintainsatableofallactivei-nodes.Asanewfileisaccessed,the systemlocatesthecorrespondingi-node,allocatesani-nodetableentry,andreadsthei-nodeinto primarymemory.Asinthebuffercache,thetableentryisconsideredtobethecurrentversionof thei-node.Modificationstothei-nodearemadetothetableentry.Whenthelastaccesstothe i-nodegoesaway,thetableentryiscopiedbacktothesecondarystorei-listandthetableentryis freed.

-8-AllI/Ooperationsonfilesarecarriedoutwiththeaidofthecorrespondingi-nodetable entry.Theaccessingofafileisastraightforwardimplementationofthealgorithmsmentioned previously.Theuserisnotawareofi-nodesandi-numbers.Referencestothefilesystemare madeintermsofpathnamesofthedirectorytree.Convertingapathnameintoani-nodetable entryisalsostraightforward.Startingatsomeknowni-node(therootorthecurrentdirectoryof someprocess),thenextcomponentofthepathnameissearchedbyreadingthedirectory.This givesani-numberandanimplieddevice(thatofthedirectory).Thusthenexti-nodetableentry canbeaccessed.Ifthatwasthelastcomponentofthepathname,thenthisi-nodeistheresult. Ifnot,thisi-nodeisthedirectoryneededtolookupthenextcomponentofthepathname,and thealgorithmisrepeated. Theuserprocessaccessesthefilesystemwithcertainprimitives.Themostcommonof theseareopen,create,read,write,seek,andclose.Thedatastructuresmaintainedare showninFig.2. Fig.2—Filesystemdatastructure. Inthesystemdatasegmentassociatedwithauser,thereisroomforsome(usuallybetween10 and50)openfiles.Thisopenfiletableconsistsofpointersthatcanbeusedtoaccesscorrespondingi-nodetableentries.AssociatedwitheachoftheseopenfilesisacurrentI/Opointer.Thisis abyteoffsetofthenextread/writeoperationonthefile.Thesystemtreatseachread/write requestasrandomwithanimpliedseektotheI/Opointer.Theuserusuallythinksofthefileas sequentialwiththeI/Opointerautomaticallycountingthenumberofbytesthathavebeen read/writtenfromthefile.Theusermay,ofcourse,performrandomI/ObysettingtheI/O pointerbeforereads/writes. Withfilesharing,itisnecessarytoallowrelatedprocessestoshareacommonI/Opointer andyethaveseparateI/Opointersforindependentprocessesthataccessthesamefile.With thesetwoconditions,theI/Opointercannotresideinthei-nodetablenorcanitresideinthelist ofopenfilesfortheprocess.Anewtable(theopenfiletable)wasinventedforthesolepurposeof holdingtheI/Opointer.Processesthatsharethesameopenfile(theresultofforks)sharea commonopenfiletableentry.Aseparateopenofthesamefilewillonlysharethei-nodetable entry,butwillhavedistinctopenfiletableentries. Themainfilesystemprimitivesareimplementedasfollows.openconvertsafilesystem pathnameintoani-nodetableentry.Apointertothei-nodetableentryisplacedinanewlycre-atedopenfiletableentry.Apointertothefiletableentryisplacedinthesystemdatasegment -9-fortheprocess.createfirstcreatesanewi-nodeentry,writesthei-numberintoadirectory,and thenbuildsthesamestructureasforanopen.readandwritejustaccessthei-nodeentryas describedabove.seeksimplymanipulatestheI/Opointer.Nophysicalseekingisdone.close justfreesthestructuresbuiltbyopenandcreate.Referencecountsarekeptontheopenfile tableentriesandthei-nodetableentriestofreethesestructuresafterthelastreferencegoesaway. unlinksimplydecrementsthecountofthenumberofdirectoriespointingatthegiveni-node. Whenthelastreferencetoani-nodetableentrygoesaway,ifthei-nodehasnodirectoriespoint-ingtoit,thenthefileisremovedandthei-nodeisfreed.Thisdelayedremovaloffilesprevents problemsarisingfromremovingactivefiles.Afilemayberemovedwhilestillopen.Theresulting unnamedfilevanisheswhenthefileisclosed.Thisisamethodofobtainingtemporaryfiles. ThereisatypeofunnamedFIFOfilecalledapipe.Implementationofpipesconsistsof impliedseeksbeforeeachreadorwriteinordertoimplementfirst-in-first-out.Therearealso checksandsynchronizationtopreventthewriterfromgrosslyoutproducingthereaderandtopreventthereaderfromovertakingthewriter. 4.2.Mountedfilesystems ThefilesystemofaUNIXsystemstartswithsomedesignatedblockdeviceformattedas describedabovetocontainahierarchy.TherootofthisstructureistherootoftheUNIXfilesystem.Asecondformattedblockdevicemaybemountedatanyleafofthecurrenthierarchy.This logicallyextendsthecurrenthierarchy.Theimplementationofmountingistrivial.Amount tableismaintainedcontainingpairsofdesignatedleafi-nodesandblockdevices.Whenconvert-ingapathnameintoani-node,acheckismadetoseeifthenewi-nodeisadesignatedleaf.Ifit is,thei-nodeoftherootoftheblockdevicereplacesit. Allocationofspaceforafileistakenfromthefreepoolonthedeviceonwhichthefilelives. Thusafilesystemconsistingofmanymounteddevicesdoesnothaveacommonpooloffreesecondarystoragespace.Thisseparationofspaceondifferentdevicesisnecessarytoalloweasy unmountingofadevice. 4.3.Othersystemfunctions Therearesomeotherthingsthatthesystemdoesfortheuser−alittleaccounting,alittle tracing/debugging,andalittleaccessprotection.Mostofthesethingsarenotverywelldeveloped becauseouruseofthesystemincomputingscienceresearchdoesnotneedthem.Therearesome featuresthataremissedinsomeapplications,forexample,betterinter-processcommunication. TheUNIXkernelisanI/Omultiplexermorethanacompleteoperatingsystem.Thisisasit shouldbe.Becauseofthisoutlook,manyfeaturesarefoundinmostotheroperatingsystemsthat aremissingfromtheUNIXkernel.Forexample,theUNIXkerneldoesnotsupportfileaccessmethods,filedisposition,fileformats,filemaximumsize,spooling,commandlanguage,logicalrecords, physicalrecords,assignmentoflogicalfilenames,logicalfilenames,morethanonecharacterset, anoperator’sconsole,anoperator,log-in,orlog-out.Manyofthesethingsaresymptomsrather thanfeatures.Manyofthesethingsareimplementedinusersoftwareusingthekernelasatool. Agoodexampleofthisisthecommandlanguage.5Eachusermayhavehisowncommandlanguage.Maintenanceofsuchcodeisaseasyasmaintainingusercode.Theideaofimplementing ‘‘system’’codewithgeneraluserprimitivescomesdirectlyfromMULTICS.6 5Thisissue. 6