Distributed processes A concurrent programming con

DISTRIBUTEDPROCESSES:ACONCURRENTPROGRAMMINGCONCEPTPERBRINCHHANSEN(1978)Alanguageconceptforconcurrentprocesseswithoutcommonvariablesisin-troduced.Theseprocessescommunicateandsynchronizebymeansofproce-durecallsandguardedregions.Thisconceptisproposedforreal-timeapplica-tionscontrolledbymicrocomputernetworkswithdistributedstorage.Thepa-pergivesseveralexamplesofdistributedprocessesandshowsthattheyincludeprocedures,coroutines,classes,monitors,processes,semaphores,bu®ers,pathexpressions,andinput/outputasspecialcases.1INTRODUCTIONThispaperintroducesdistributedprocesses|anewlanguageconceptforcon-currentprogramming.Itisproposedforreal-timeapplicationscontrolledbymicrocomputernetworkswithdistributedstorage.Thepapergivesseveralexamplesofdistributedprocessesandshowsthattheyincludeprocedures,coroutines,classes,monitors,processes,semaphores,bu®ers,pathexpres-sionsandinput/outputasspecialcases.Real-timeapplicationspushcomputerandprogrammingtechnologytoitslimits(andsometimesbeyond).Areal-timesystemisexpectedtomoni-torsimultaneousactivitieswithcriticaltimingconstraintscontinuouslyandreliably.Theconsequencesofsystemfailurecanbeserious.P.BrinchHansen,Distributedprocesses:Aconcurrentprogrammingconcept,Communi-cationsoftheACM21,11(November1978),934{941.Copyrightc°1978,AssociationforComputingMachinery,Inc.12PERBRINCHHANSENReal-timeprogramsmustachievetheultimateinsimplicity,reliability,ande±ciency.Otherwiseonecanneitherunderstandthem,dependonthem,norexpectthemtokeeppacewiththeirenvironments.Tomakereal-timeprogramsmanageableitisessentialtowritetheminanabstractprogram-minglanguagethathidesirrelevantmachinedetailandmakesextensivecom-pilationcheckspossible.Tomakereal-timeprogramse±cientatthesametimewillprobablyrequirethedesignofcomputerarchitecturestailoredtoabstractlanguages(oreventoparticularapplications).Fromalanguagedesigner'spointofview,real-timeprogramshavethesecharacteristics:1.Areal-timeprograminteractswithanenvironmentinwhichmanythingshappensimultaneouslyathighspeeds.2.Areal-timeprogrammustrespondtoavarietyofnondeterministicrequestsfromitsenvironment.Theprogramcannotpredicttheorderinwhichtheserequestswillbemadebutmustrespondtothemwithincertaintimelimits.Otherwise,inputdatamaybelostoroutputdatamaylosetheirsigni¯cance.3.Areal-timeprogramcontrolsacomputerwitha¯xedcon¯gurationofprocessorsandperipheralsandperforms(inmostcases)a¯xednumberofconcurrenttasksinitsenvironment.4.Areal-timeprogramneverterminatesbutcontinuestoserveitsenvi-ronmentaslongasthecomputerworks.(Theoccasionalneedtostopareal-timeprogram,sayattheendofanexperiment,canbehandledbyadhocmechanisms,suchasturningthemachineo®orloadinganotherprogramintoit.)Whatisneededthenforreal-timeapplicationsistheabilitytospecifya¯xednumberofconcurrenttasksthatcanrespondtonondeterministicrequests.TheprogramminglanguagesConcurrentPascalandModulacomeclosetosatisfyingtherequirementsforabstractconcurrentprogramming(BrinchHansen1975,1977;Wirth1977).Bothofthemarebasedonthemonitorconcept(BrinchHansen1973;Hoare1974).Modula,however,isprimarilyorientedtowardsmultiprogrammingonasingleprocessor.AndastraightforwardimplementationofConcurrentPascalrequiresasinglepro-cessororamultiprocessorwithacommonstore.Intheirpresentform,theselanguagesarenotidealforamicrocomputernetworkwithdistributedstorageonly.DISTRIBUTEDPROCESSES3ItmaywellbepossibletomodifyConcurrentPascaltosatisfythecon-straintsofdistributedstorage.Theideasproposedherearemoreattractive,however,becausetheyunifythemonitorandprocessconceptsandresultinmoreelegantprograms.Thenewlanguageconceptsforreal-timeapplica-tionshavethefollowingproperties:1.Areal-timeprogramconsistsofa¯xednumberofconcurrentprocessesthatarestartedsimultaneouslyandexistforever.Eachprocesscanaccessitsownvariablesonly.Therearenocommonvariables.2.Aprocesscancallcommonproceduresde¯nedwithinotherprocesses.Theseproceduresareexecutedwhentheotherprocessesarewaitingforsomeconditionstobecometrue.Thisistheonlyformofprocesscommunication.3.Processesaresynchronizedbymeansofnondeterministicstatementscalledguardedregions(Hoare1972;BrinchHansen1978).Theseprocessescanbeusedasprogrammodulesinamultiprocessorsys-temwithcommonordistributedstorage.Tosatisfythereal-timeconstraintseachprocessorwillbededicatedtoasingleprocess.Whenaprocessoriswaitingforsomeconditiontobecometruethenitsprocessorisalsowaitinguntilanexternalprocedurecallmakestheconditiontrue.Thisdoesnotrepresentawasteofresourcesbutratheratemporarylackofusefulworkforthatprocessor.Parameterpassingbetweenprocessescanbeimplementedei-therbycopyingwithinacommonstoreorbyinput/outputbetweenseparatestores.Theproblemsofdesigningveri¯cationrulesandcomputerarchitecturesfordistributedprocessesarecurrentlybeingstudiedandarenotdiscussed.Thispaperalsoignorestheseriousproblemsofperformanceevaluationandfaulttolerance.2LANGUAGECONCEPTSAconcurrentprogramconsistsofa¯xednumberofsequentialprocessesthatareexecutedsimultaneously.Aprocessde¯nesitsownvariables,somecommonprocedures,andaninitialstatementprocessnameownvariablescommonproceduresinitialstatement4PERBRINCHHANS