An introduction to programming with threads

digitalSystemsResearchCenter130LyttonAvenuePaloAlto,California9430135AnIntroductiontoProgrammingwithThreadsbyAndrewD.BirrellJanuary6,1989AnIntroductiontoProgrammingwithThreadsAndrewD.BirrellThispaperprovidesanintroductiontowritingconcurrentprogramswith“threads”.Athreadsfacilityallowsyoutowriteprogramswithmultiplesimultaneouspointsofexecution,synchronizingthroughsharedmemory.Thepaperdescribesthebasicthreadandsynchronizationprimitives,thenforeachprimitiveprovidesatutorialonhowtouseit.Thetutorialsectionsprovideadviceonthebestwaystousetheprimitives,givewarningsaboutwhatcangowrongandofferhintsabouthowtoavoidthesepitfalls.Thepaperisaimedatexperiencedprogrammerswhowanttoacquirepracticalexpertiseinwritingconcurrentprograms.CRcategoriesandSubjectDescriptors:D.1.4[ProgrammingTechniques]:ConcurrentProgramming;D.3.3[ProgrammingLanguages]:LanguageConstructs—Concurrentprogrammingstructures;D.4.1[OperatingSystems]:ProcessManagementGeneralTerms:Design,Languages,PerformanceAdditionalKeyWordsandPhrases:Threads,Concurrency,Multi-processing,SynchronizationCONTENTSIntroduction......................................................................................................1Whyuseconcurrency?........................................................................................2Thedesignofathreadfacility..............................................................................3UsingaMutex:accessingshareddata....................................................................7UsingaConditionvariable:schedulingsharedresources..........................................14UsingFork:workinginparallel.........................................................................22UsingAlert:divertingtheflowofcontrol............................................................27Additionaltechniques.......................................................................................28Buildingyourprogram.....................................................................................30Concludingremarks.........................................................................................31References......................................................................................................31Appendix:otherthreaddesigns...........................................................................33©DigitalEquipmentCorporation1989Thisworkmaynotbecopiedorreproducedinwholeorinpartforanycommercialpurpose.Permissiontocopyinwholeorinpartwithoutpaymentoffeeisgrantedfornon-profiteducationalandresearchpurposesprovidedthatallsuchwholeorpartialcopiesincludethefollowing:anoticethatsuchcopyingisbypermissionoftheSystemsResearchCenterofDigitalEquipmentCorporationinPaloAlto,California;anacknowledgementoftheauthorsandindividualcontributorstothework;andallapplicableportionsofthecopyrightnotice.Copying,reproducing,orrepublishingforanyotherpurposeshallrequirealicensewithpaymentoffeetotheSystemsResearchCenter.Allrightsreserved.AnIntroductiontoProgrammingwithThreadsּּּּּ.ּּּּּ1INTRODUCTIONManyexperimentaloperatingsystems,andsomecommercialones,haverecentlyincludedsupportforconcurrentprogramming.Themostpopularmechanismforthisissomeprovisionforallowingmultiplelightweight“threads”withinasingleaddressspace,usedfromwithinasingleprogram.1Programmingwiththreadsintroducesnewdifficultiesevenforexperiencedprogrammers.Concurrentprogramminghastechniquesandpitfallsthatdonotoccurinsequentialprogramming.Manyofthetechniquesareobvious,butsomeareobviousonlywithhindsight.Someofthepitfallsarecomfortable(forexample,deadlockisapleasantsortofbug—yourprogramstopswithalltheevidenceintact),butsometaketheformofinsidiousperformancepenalties.Thepurposeofthispaperistogiveyouanintroductiontotheprogrammingtechniquesthatworkwellwiththreads,andtowarnyouabouttechniquesorinteractionsthatworkoutbadly.Itshouldprovidetheexperiencedsequentialprogrammerwithenoughhintstobeabletobuildasubstantialmulti-threadedprogramthatworks—correctly,efficiently,andwithaminimumofsurprises.A“thread”isastraightforwardconcept:asinglesequentialflowofcontrol.Inahigh-levellanguageyounormallyprogramathreadusingprocedures,wheretheprocedurecallsfollowthetraditionalstackdiscipline.Withinasinglethread,thereisatanyinstantasinglepointofexecution.Theprogrammerneedlearnnothingnewtouseasinglethread.Having“multiplethreads”inaprogrammeansthatatanyinstanttheprogramhasmultiplepointsofexecution,oneineachofitsthreads.Theprogrammercanmostlyviewthethreadsasexecutingsimultaneously,asifthecomputerwereendowedwithasmanyprocessorsastherearethreads.Theprogrammerisrequiredtodecidewhenandwheretocreatemultiplethreads,ortoacceptsuchdecisionsmadeforhimbyimplementersofexistinglibrarypackagesorruntimesystems.Additionally,theprogrammermustoccasionallybeawarethatthecomputermightnotinfactexecuteallhisthreadssimultaneously.Havingthethreadsexecutewithina“singleaddressspace”meansthatthecomputer’saddressinghardwareisconfiguredsoastopermitthethreadstoreadandwritethesamememorylocations.Inahigh-levellanguage,thisusuallycorrespondstothefactthattheoff-