Tekn. Dr. Bo Sanden, Associate Professor, George Mason University, bsanden@gmu.edu
Det finns allmänt talat två systematiska sätt att utforma program med lättviktsprocesser. I det ena fallet startar man med en dataflödesmodell av problemet och bygger sedan processer genom slå samman transformer. (Transformerna är bubblorna i ett dataflödesdiagram. De kallas också processer, men det uttrycket reserveras här för de parallella processerna.) Det andra sättet är att bygga parallellismen i programvaran direkt på en naturlig parallellism i problemdomänen. I det följande uppehåller vi oss först något ytterligare vid dataflödesmetoderna och övergår sedan till att beskriva entity-life modeling (ELM), som är ett exempel på det alternativa och mera direkta sättet.
Med dataflödesmetoden [1, 3], studerar man varje insignal till systemet och de beräkningar som behövs för att transformera den till något slags utsignal. Varje transform eller grupp av transformer implementeras sedan som en process. Processerna kommunicerar via gemensamma datastrukturer, ofta meddelandeköer. De aktiveras antingen periodiskt eller också låter man dem hänga på kön och aktiveras när ett meddelande kommer.
Dataflödesmetoderna är systematiska -- i vissa fall kokboksbetonade -- och kan förvisso leda till fungerande lösningar. Dock kan utvecklingsprocessen bli mycket omständlig och blanda in flera olika slags diagram såväl som ren text för att ge mening åt dataflödesdiagrammen. Därigenom blir det en stor affär att utveckla även ganska triviala system. Metoden leder också till onödigt många processer, som ofta inte exekverar parallellt utan i kaskader, den ena efter den andra. Det är också svårt att bedöma systemets totala svarstid för en given insignal eftersom systemets reaktion inte finns samlad på ett ställe i programtexten utan är utspridd över flera processer.
Det andra och mera direkta sättet att utforma parallell programvara utgår från händelser i problemdomänen. Man kan ät.ex.å arrangera dessa i sekvensiella trådar (threads), vilka sedan blir processer i programvaran. Förutsatt att problemet har naturlig parallellism leder detta till en mindre fragmenterad lösning, där systemets reaktion på en given insignal finns på ett ställe och behandlingen av sammanhörande, successiva insignaler är samlad i texten för en process. En metod för detta -- entity-life modeling -- presenteras i detalj nedan och tillämpas sedan på ett kontrollsystem för flexibel tillverkning. Sedan följer ytterligare exempel på problem där metoden är användbar.
För att identifiera parallismen i ett problem kan man göra följande tankeexperiment:
(1) Lägg ut alla händelser som programvaran måste ta hänsyn till längs en tidsaxel. Inkludera insignaler, utsignaler som måste produceras vid bestämda tidpunkter och andra tidsbestämda händelser som t.ex. sampling.
(2) Dela in händelsesekvensen i trådar (threads) där varje tråd är en mängd händelser sådan att
(a) varje händelse tillhör en och endast en tråd
(b) händelserna i varje tråd är åtskilda av tillräcklig tid för behandlingen av varje händelse.
Väsentligen innebär detta att händelser som inträffar samtidigt tillhör olika trådar. Resultatet är en uppsättning trådar som vi kallar för en trådmodell av problemet.
Generellt sett blir trådarna parallella processer i programmet. Varje händelse hanteras av en och endast en process och att ingen process blir översvämmad av händelser i alltför tät följd. (I praktiken kan programstrukturen skilja sig från trådmodellen: I vissa fall behöver inte varje tråd en egen process. I andra fall behövs extra processer [7].)
En trådmodell kan innehålla hur många trådar som helst. Den kallas minimal om all trådarna är nödvändiga i den meningen att det finns en tidpunkt där en händelse inträffar i varje tråd. Detta är en situation där alla processer samtidigt antingen får en insignal eller måste producera en tidsbestämd utsignal.
Man kan i allmänhet associera trådar med aktiva objekt i problemet, som t.ex. en hiss, en robot, osv. Tråden beskriver då objektets levnadslopp. Ett förenklat exempel är ett kontrollsystem för hissar i en kontors- eller hotellbyggnad, där händelserna är hissarnas ankomster till och avgångar från olika våningar. Man kan då ha en tråd per hiss, eftersom de händelser den är inblandad i är utspridda i tiden. å andra sidan kan man inte inkludera alla händelser i hissproblemet i en tråd eftersom händelser för olika hissar kan vara samtidiga. Av samma anledning går det inte att att knyta en tråd till varje våning, eftersom olika hissar kan anlända till och avgå från våningen samtidigt.
Det finns en del likheter mellan ELM och en teknik baserad på scenarios ("use cases") i objekt-orienterad analys [2]. Ett use case är en serie operationer på olika objekt initierade av en extern aktör med ett bestämt syfte. Ofta är det en tidsbegränsad dialog mellan systemet och en mänsklig operatör. Uttag av pengar från en bankautomat kan vara ett exempel. Systemet är gjort för att hantera en mängd sådana dialoger. I ett realtidssystem är aktörerna ofta mekaniska eller elektriska system som hissarna i exemplet ovan. Dessa aktörer motsvarar aktiva objekt i ELM och ger upphov till processer i programvaran.
I valet mellan olika trådmodeller av ett givet problem är det ofta fördelaktigt att finna aktiva objekt som är antingen tidsbundna (delayable) eller köbundna (queueable). Detta definieras som följer:
(1) Ett tidsbundet objekt har händelser som måste ske på givna tidpunkter. Detta går lätt att modellera i programvaran eftersom processer har en inbyggd förmåga att uppskjuta sin egen exekvering med hjälp av "delay". Hissobjekten blir tidsbundna om vi inkluderar ytterligare händelser och t.ex. låter hissdörrarna stängas automatiskt när de varit öppna en viss tid.
(2) Köbundna objekt konkurrerar om gemensamma resurser. (Mera exakt behöver ett köbundet objekt exklusiv tillgång till flera resurser samtidigt.) Detta kan också modelleras direkt i programvaran genom att en process kan avbryta sin verksamhet och köa för en resurs.
Trådar kan lätt implementeras i Ada och speciellt Ada 95, eftersom processer är en del av syntaxen och väl integrerade med språket. Gemensamma resurser representeras ofta av skyddade enheter i Ada 95.
Ytterligare beskrivning av ELM finns i [4, 5, 6, 7, 8]. Nästa avsnitt illustrerar metoden med hjälp av ett exempel.
3.1 Problembeskrivning
Ett flexibelt tillverkningssystem (FMS) kontrollerar jobben i en automatiserad fabrik [5, 8]. Varje jobb går ut på att utforma ett arbetsstycke, som börjar som råmaterial och sedan borras, fräses, svarvas osv. i en serie jobbsteg utförda vid olika arbetsstationer. Serien av jobbsteg är definierad i en individuell arbetsplan för varje jobb.
Arbetsstyckena flyttas mellan arbetsstationer med hjälp av automatiska fordon (AGV). Ett automatiskt lager används för råmaterial och färdiga produkter och även för mellanlagring mellan jobbsteg. Varje jobb har sin egen lagercell. Automatiska gaffeltruckar transporterar arbetsstycken mellan cellen och ett antal lagerställ, där de är tillgängliga för AGVerna.
Det kan finnas flera automatiska arbetsstationer av varje typ (borr, fräs, svarv osv.) Varje station har ett inställ, ett verktyg, ett utställ och en robot som flyttar arbetsstyckena från inställ till verktyg och från verktyg till utställ.
Systemet övervakas från en terminal. Så snart råmaterialet till ett arbetsstycke, A, finns i sin cell i lagret skapar operatören ett jobb genom att knyta cellnumret till en arbetsplan. Jobbet skeduleras sedan för en arbetsstation av rätt typ för sitt första arbetssteg. Om ingen sådan station är ledig, köas jobbet på den arbetsstationstypen. Arbetsstycket A stannar kvar i cellen tills instället, säg IN1, till en lämplig arbetsstation, blir ledigt. Då transporterar gaffeltrucken det till ett av lagerställen, varifrån en AGV tar det till IN1.
A stannar på IN1 tills IN1s verktyg blir ledigt och flyttas sedan in i verktyget med hjälp av roboten. När verktygsoperationen är klar flyttar roboten A till utstället UT1, och jobbet skeduleras för en arbetsstation för nästa jobbsteg.
A stannar på UT1 tills antingen en lämplig arbetsstation blir ledig eller ett annat jobb behöver utstället. Om ett inställ, säg IN2, blir ledigt, flyttas A dit av en AGV. Om A är kvar på UT1 när nästa jobb blir färdigt i verktyget, bumpas A och placeras i mellanlagring. När detta händer, tas A ut ur arbetsstationskön, transporteras av en AGV till ett lagerställ och sedan av en gaffeltruck till sin cell. Väl där ställs jobbet åter i kö för lämplig arbetsstationstyp. Detta fortsätter tills jobbet har avslutat sin arbetsplan. Då placeras det i sin cell där det hämtas på något sätt som ligger utanför denna problembeskrivning.
3.1 Analys
Exampel på händelser i FMS är: "stycke lastas på en AGV", "stycke lastas på gaffeltruck", "gaffeltruck startar", "stycke flyttas från verktyg", "stycke flyttas till utställ" osv. och även "jobb tilldelas gaffeltruck" osv. Vi ska nu definiera tre olika trådmodeller av FMS-problemet genom att dela in händelserna i trådar.
3.1.1 Modell 1
Varje händelse i FMS-problemet berör ett specifikt arbetsstycke och ett specifikt jobb. Ingen händelse berör två eller flera jobb. Inga händelser under ett jobb är samtidiga. Vi kan alltså ge varje jobb en tråd, som vi kallar Jobb. Intuitivt sett driver jobben denna modell genom att genomföra sin arbetsplan steg för steg. Jobben är köbundna objekt eftersom de behöver kombinationer av resurser som arbetsstation, AGV och gaffeltruck.
Modell 1 är inte minimal annat än om antalet jobb är ovanligt litet. Normalt representerar många av dess trådar jobb som är overksamma i lagret. Dock tydliggör modellen konkurrensen om resurser och visar varför bumpning måste till för att förhindra låsning. (Man kan lätt inse detta genom att betrakta två arbetsstationer, S1 och S2. Varje station har ett jobb på sitt inställ, ett annat på sitt utställ och ett tredje i verktyget. Jobbet på S1s utställ försöker komma åt S2s inställ och jobbet på S2s utställ försöker komma åt S1s inställ.)
3.1.2 Modell 2
I Modell 2 låter vi, intuitivt sett, inställen driva systemet genom att successivt hämta till sig stycken att arbeta på allteftersom stycken flyttas in i verktyget. Modell 2 har tre trådar per arbetsstation: In, Verktyg och Ut. Intråden flyttar stycken till instället och sedan in i verktyget. Verktyg sköter förflyttningen från verktyget till utstället, och Ut hanterar en eventuell förflyttning från utställ till lager.
Man kan säga att Modell 2 bryter upp Jobb-tråden från Modell 1 i tre delar: förflyttning till, inom och från arbetsstation. En fördel med denna modell är att ett jobb som befinner sig i lagret inte behöver någon tråd.
3.1.3 Modell 3
Resonemanget bakom Modell 3 är att varje händelse i FMS kräver antingen en AGV, en gaffeltruck eller en arbetsstation. Man kan då betrakta problemet så att arbetsstyckena passivt förs mellan individer av dessa tre slag, eventuellt via köer. I denna modell är varje arbetsstation, AGV och truck ett aktivt objekt och har alltså sin egen tråd.
Modell 3 är minimal för vissa värden på antalet arbetsstationer, AGV och truckar. Man inser att om dessa storheter väljs optimalt finns det ett tillfälle när de alla är verksamma.
AGV-, Truck- och Arbetsstationsprocesserna kan vara köade i väntan på jobb. Dock är de inte användare av flera samtidiga gemensamma resurser. Resurskonflikterna uppstår inte mellan dem utan är istället dolda i denna lösning: En del av jobben i AGV-kön har exklusiv tillgång till ett lagerställ, osv. Av den anledningen lämpar sig denna modell inte direkt för låsningsanalys.
3.2 Design
Var och en av trådmodellerna svarar mot en möjlig utformning av FMS-programmet, där varje tråd blir en process:
Modell 1 resulterar in en köbunden processtyp, Jobb, som beskriver de steg som behövs för att flytta ett arbetsstycke från lager till arbetsstation och vidare till antingen lagret eller en annan arbetsstation tills jobbet är klart.
I en implementering av Modell 2 flyttar en processtyp (In) arbetsstycken till instället och vidare in i verktyget. En annan, (Ut) flyttar dem från utstället till lagret när detta är nödvändigt. (Processtypen Verktyg flyttar styckena från verktyg till utställ.) In och Ut är köbundna processer som konkurrerar om lagerställ, AGVer och truckar. Förutom bumpningsproblemet, som kvarstår, innehåller Modell 2 en tävlingssituation (race condition) där en In-process och en Ut-process tävlar om ett arbetsstycke, A, på ett utställ. Detta händer när ett inställ av lämplig typ blir ledigt just som ett jobb blir färdigt i verktyget till den arbetsstation där A befinner sig.
En implementering av Modell 3 är uppbyggd kring en kö av jobb som väntar på en AGV, en annan kö av jobb som väntar på en gaffeltruck, osv. Det finns en process per AGV, truck och arbetsstation. Varje process hämtar ett jobb från en viss kö, flyttar eller bearbetar arbetsstycket och ställer sedan åter jobbet i kö.
ELM har framgångsrikt tillämpats på många realistiska problem i laboratorieskala. Problemen kan i allmänhet indelas i följande kategorier:
4.1 Periodiska problem
Dessa problem är strukturellt enkla och grundar sig på tidsbundna processer. Ett exampel är ett cruise-kontrollsystem för en bil: En regulatorprocess jämför regelbundet bilens hastighet med en målhastighet och justerar luftintaget till motorn i enlighet med någon styrlag.
4.2 Problem med användartrådar
Dessa problem har en mänsklig operatör som aktivt objekt. Ett kassörssystem för ett snabbköp eller en bank och olika varuautomater är några exempel.
4.3 Löpandebandssystem
I dessa system är de aktiva objekten typiskt behandlingsstationer med ett flöde av arbetsstycken mellan sig. Varje station bearbetar stycket när det kommer. Ett bra exempel är ett bagagehanteringssystem för en flygplats. Stationerna kan där vara växlar mellan en huvudslinga och en sidoslinga som kommer från incheckning eller går till lastning.
Modell 3 ovan är ett försök att betrakta FMS som ett slags löpandebandssystem. Denna överförenkling leder till problem efterson man i denna problemtyp normalt inte behöver ta hänsyn till risken för låsning. FMS är i stället ett exempel på ett resurskonfliktproblem.
4.4 Resurskonfliktproblem
I dessa system, som kan vara komplicerade, konkurrerar de aktiva objekten om gemensamma resurser. Fallet där varje aktivt objekt behöver mer än en resurs i taget är av speciellt intresse eftersom det kan leda till låsning. Detta kan förebyggas vid programutformningen. FMS är ett typiskt exempel. Andra exampel är en automatiserad rangerbangård, där växellok är aktiva objekt som konkurrerar om spårsegment eller växlar, och ett automatiskt parkeringshus, där bilar konkurrerar om trolleys att åka på och om segment av körbanan i garaget. I dessa system användes Adaprocesser för att representera aktiva objekt i problemdomänen som väntar på och använder resurser.
Realtidsprogram med lättviktsprocesser kan bygga på en problemmodell som antingen är baserad på dataflöde eller på parallellism i själva problemet. Medan dataflödesmetoderna föreskriver en stegvis utveckling med flera mellanmodeller, är entity-life modeling, som bygger på parallellism, mera direkt. Det är mera en princip för sambandet mellan problem och lösning än en serie steg för att komma från det ena till den andra. Denna direkta koppling är viktig i samband med underhåll och återanvänding av programvara, där programutvecklingen inte kan börja med en förutsättningslös funktionell analys av problemet utan måste ta hänsyn till befintliga program.
Man kan göra observationen att ett simuleringsprogram för ett system som FMS skulle kunna ha samma struktur som vi här diskuterat för kontrollsystemet. Detta är ingen tillfällighet. Kontrollsystemet och simuleringsprogrammet behöver inte vara strukturellt olika bara för att det ena är "stimulerat" och det andra simulerat. En simulering tar fasta på mekanismen som får det verkliga systemet att fungera. Principen bakom ELM är att bygga styrprogrammet på samma mekanism.
Referenser
[1] H. Gomaa. Software Design Methods for Concurrent and Real-time Systems. Addison-Wesley, 1993.
[2] I. Jacobsson. Object-oriented Software Engineering. Addison-Wesley 1992.
[3] K. W. Nielsen och K. Shumate. Designing large real-time systems with Ada. Communications of the ACM, 30(8):695-715, augusti 1987.
[4] B. Sanden. An entity-life modeling approach to the design of concurrent software. Communications of the ACM, 32(3):330-343, mars 1989.
[5] B. Sanden. Software Systems Construction with Examples in Ada. Prentice-Hall, 1994.
[6] B. Sanden. Design of concurrent software. In Proceedings, Seventh Annual Software Technology Conference, Salt Lake City, Utah, april 1995.
[7] B. Sanden. Design of concurrent software based on problem concurrency. Proceedings, Ada in Europe Conference, Frankfurt, oktober 1995
[8] B. Sanden. Designing control systems with entity-life modeling. Journal of Systems and Software, 28: 225-237, april 1995.
Om artikelförfattaren
Bo Sanden är civilingenjör (F) från LTH och teknologie doktor från KTH. Sedan 1987 är han professor i progamvaruteknik vid George Mason University, Fairfax, Virginia, en förstad till Washington, DC. Han har givit ut "Systemprogrammering med JSP" (Studentlitteratur) och "Software systems construction with examples in Ada" (Prentice-Hall 1994). Han ger regelbundet tutorials om entity-life modeling. I mars 1996 hålls en veckolång kurs i Mariadatas regi i Stockholm.