Skådespelarmodellen är en matematisk modell av parallell beräkning , byggd kring begreppet en skådespelare ( eng. skådespelare "aktör; agerande subjekt"), som anses vara en universell primitiv för parallellt utförande. En aktör i denna modell interagerar genom att utbyta meddelanden med andra aktörer, och var och en som svar på mottagna meddelanden kan fatta lokala beslut, skapa nya aktörer, skicka sina egna meddelanden och bestämma hur de ska svara på efterföljande meddelanden.
Skapat som en teoretisk grund för ett antal praktiska implementeringar av parallella system .
Huvudidéerna och grunden för modellen lades fast 1973 genom publiceringen av Hewitt, Bishop och Steiger [1] . Programmeringsspråken Lisp , Simula och tidiga versioner av Smalltalk , såväl som metoder för parametriskt skydd och paketväxling , påverkade processen för modellbildning . Den främsta motivationen för att skapa modellen var uppgiften att bygga distribuerade datorsystem baserade på hundratals och tusentals oberoende datorer utrustade med sina egna lokala minne och kommunikationsgränssnitt [2] . Med tillkomsten av multiprocessorsystem och multi-core arkitekturer ökade intresset för aktörsmodellen även utanför sammanhanget av distribuerade system.
1975 utvecklades operativ semantik för skådespelaremodellen [3] [4] . 1977 utvecklades ett system av axiomatiska lagar för skådespelaremodeller [5] . 1981 skapades, utvecklades och generaliserades den denotationssemantik av modellen (semantik av övergångar) [2] [6] 1985 [7] ; som ett resultat av dessa arbeten erkänns teorin om skådespelarmodeller som utvecklad och utvecklad.
På 1990-talet skapades formalismer som inte helt överensstämmer med aktörsmodellen (formaliserar inte garanterad meddelandeleverans), men som är av praktiskt intresse, i synnerhet flera olika aktörsalgebror [8] [9] och tolkning baserad på linjär logik [10] .
I analogi med filosofin om objektorienterad programmering , där varje primitiv betraktas som ett objekt, pekar skådespelarens modell ut begreppet "aktör" som en universell enhet. En aktör är en beräkningsenhet som, som svar på ett mottaget meddelande, samtidigt kan:
Det antas inte att det finns en specifik sekvens av ovanstående åtgärder och de kan alla utföras parallellt.
Separationen av avsändaren från de skickade meddelandena var en grundläggande prestation av aktörsmodellen: den ger asynkron kommunikation och kontroll av strukturer i form av meddelandeförmedling [11] .
Mottagare av meddelanden identifieras med en adress, ibland kallad "postadress". En aktör kan alltså bara interagera med de aktörer vars adresser den har, kan extrahera adresser från mottagna meddelanden eller känna till dem i förväg om skådespelaren skapat dem själv.
Modellen kännetecknas av inneboende parallellism av beräkningar inom och mellan aktörer, dynamiskt skapande av aktörer, inkludering av aktörsadresser i meddelanden och interaktion endast genom direkta asynkrona meddelanden utan några begränsningar i ordningen för ankomsten av meddelanden.
Aktörsmodellen kan användas som grund för modellering, förståelse och resonemang på ett brett spektrum av samtidiga system , till exempel:
De första parallella programmen var kanske avbrottshanterare . Under drift måste en dator som regel svara på externa händelser som kan inträffa vid en tidigare okänd tidpunkt (asynkront med avseende på det program som körs för närvarande) - till exempel för att ta emot information utifrån (tecken från tangentbordet) , paket från nätverket och så vidare ). Den mest effektiva hanteringen av sådana händelser genomförs med hjälp av så kallade avbrott. När en händelse inträffar "avbryts exekveringen av det aktuella programmet", och avbrottshanteraren startas , som utför de åtgärder som krävs för att svara på händelsen (till exempel tar emot inkommande information och lagrar den i en buffert, varifrån den kan läsas senare), varefter huvudprogrammet fortsätter att arbeta där det slutade .
I början av 1960-talet började avbrott användas för att simulera den samtidiga exekveringen av flera program på en enda processor [13] . Förekomsten av parallellitet med delat minne har lett till problemet med samtidighetskontroll. Ursprungligen var denna uppgift tänkt som en av mutexerna på en separat dator. Edsger Dijkstra utvecklade semaforer , och senare, mellan 1971 och 1973, utvecklades monitorer [14] [15] [16] av Charles Hoare och Per Hansen för att lösa mutexproblemet . Ingen av dessa lösningar skapade dock konstruktioner i programmeringsspråk som skulle inkapsla tillgång till delade resurser. Inkapsling gjordes senare av Hewitt och Atkinson med användning av serialiseringskonstruktioner ([Hewitt, Atkinson 1977, 1979] och [Atkinson 1980]).
De första beräkningsmodellerna (t.ex. Turing -maskin , Post-maskin , lambda-kalkyl, etc.) baserades på matematik och använde begreppet en global stat för att definiera "beräkningssteget" (senare generaliserades dessa begrepp i verk av McCarthy och Dijkstra [17] [18] ). Varje beräkningssteg gick från ett globalt beräkningstillstånd till nästa. Den globala tillståndsstrategin har fortsatt inom automatteorin för finita automater och stackmaskiner, inklusive deras icke- deterministiska versioner. Sådana icke-deterministiska automater har egenskapen begränsad icke-determinism. Det vill säga, om maskinen alltid står innan den går till initialtillståndet, så finns det en gräns för antalet tillstånd som den kan vara i.
Dijkstra utvecklade den icke-deterministiska globala statsansatsen vidare. Dijkstras modell har gett upphov till kontroverser om obegränsad icke-determinism, en egenskap hos parallell beräkning där mängden latens vid betjäning av en begäran kan bli obegränsad till följd av arbitragekonkurrens om delade resurser, samtidigt som den garanterar att begäran så småningom kommer att bli servad. Hewitt menade att aktörsmodellen borde ge garantier för tillhandahållandet av en tjänst. Även om det i Dijkstras modell inte kan gå en obegränsad tid mellan exekveringen av sekventiella operationer på en dator, kan ett program som körs parallellt, som började sitt arbete i ett strikt definierat tillstånd, bara avbrytas i ett begränsat antal tillstånd [18 ] . Därför kan Dijkstras modell inte ge garantier för tillhandahållandet av en tjänst. Dijkstra hävdade att det var omöjligt att implementera obegränsad icke-determinism.
Hewitt hävdade något annat: det finns ingen gräns för den tid som ägnas åt arbetet med den sektion av beräkningar, som kallas skiljemannen för att lösa konflikter. Skiljemän hanterar lösningen av sådana situationer. Datorklockan fungerar asynkront med externa ingångar: tangentbordsingång, diskåtkomst, nätverksingång och så vidare. Så det kan ta en obegränsad tid att ta emot ett meddelande som skickas till en dator, och under den tiden kan datorn gå igenom ett obegränsat antal tillstånd.
Obegränsad icke-determinism är ett karakteristiskt drag i skådespelarmodellen, som använder sig av Klingers matematiska modell baserad på teorin om regioner [2] . Det finns ingen global stat i skådespelarmodellen.
Meddelanden i skådespelarmodellen är inte nödvändigtvis buffrade. Detta är dess skarpa skillnad från tidigare metoder för simultanberäkningsmodellen. Bristen på buffring orsakade många missförstånd under utvecklingen av skådespelaremodellen, och är fortfarande föremål för kontroverser än i dag. Vissa forskare hävdar att meddelanden buffras i "luften" eller "miljön". Dessutom skickas meddelanden i aktörsmodellen helt enkelt (till exempel paket i IP ). Det finns inget krav på ett synkront handslag med mottagaren.
En naturlig utveckling av skådespelarmodellen var förmågan att skicka adresser i meddelanden. Påverkad av paketkopplade nätverk, föreslog Hewitt att utveckla en ny modell för samtidig datoranvändning där länken inte skulle ha några obligatoriska fält alls, som alla kunde vara tomma. Om avsändaren av meddelandet önskar att mottagaren ska få tillgång till adresser som han inte redan har, ska adressen skickas i meddelandet.
Under beräkningen kan det bli nödvändigt att skicka ett meddelande till en mottagare från vilken ett svar senare ska tas emot. Sättet att göra detta är att skicka ett meddelande som innehåller adressen till en annan aktör, kallat ett CV (kallas ibland även en fortsättning eller samtalsstack ). Mottagaren kan sedan skapa ett svarsmeddelande som ska skickas vid CV .
Skapandet av aktörer plus införandet av deltagaradresser i meddelanden gör att aktörsmodellen har en potentiellt variabel topologi i sin relation till varandra, liknande objekt i Simula-språket som också har en variabel topologi i sin relation till varandra.
I motsats till det tidigare tillvägagångssättet baserat på att kombinera sekventiella processer, utformades aktörsmodellen som en simultan modell i sin essens. Som skrivet i teorin om skådespelaremodeller är sekvensen i den ett specialfall som härrör från samtidiga beräkningar.
Hewitt var emot att inkludera krav på att meddelanden måste komma fram i den ordning de skickades till skådespelarens modell. Om man önskar beställa inkommande meddelanden kan detta modelleras med en aktörskö som ger denna funktionalitet. Sådana aktörsköer skulle ordna inkommande meddelanden så att de tas emot i FIFO - ordning . I allmänhet, om en aktör X sänder ett meddelande Ml till en aktör Y , och sedan samma aktör X sänder ett annat meddelande M2 till Y , så finns det inget krav på att M1 anländer till Y före M2 .
I detta avseende speglar aktörsmodellen paketväxlingssystemet, vilket inte garanterar att paketen kommer att tas emot i den ordning de skickades. Bristen på garantier för meddelandeleveransorder tillåter paketväxlingssystemet att buffra paket, använda flera sökvägar för att skicka paket, skicka om skadade paket och använda andra optimeringstekniker.
Till exempel kan aktörer använda en pipeline för meddelandebehandling. Detta betyder att aktören under behandlingen av meddelande M1 kan variera beteendet som kommer att användas för att behandla nästa meddelande. I synnerhet betyder detta att den kan börja bearbeta ytterligare ett meddelande M2 innan bearbetningen av M1 är klar . Bara för att en aktör beviljas rätt att använda en pipeline för meddelandebehandling betyder det inte att den måste använda den pipeline. Huruvida ett meddelande kommer att skickas i pipeline eller inte är en fråga om teknisk kompromiss. Hur kan en utomstående observatör veta att en aktörs meddelandebehandling har gått igenom pipelinen? Det finns ingen tvetydighet om en aktörs användning av pipelining-kapaciteten i detta avseende. Endast om, i en viss implementering, implementeringen av pipelined optimering görs felaktigt, kan något annat än det förväntade beteendet inträffa.
En annan viktig egenskap hos aktörsmodellen är lokalitet: när en aktör bearbetar ett meddelande kan en aktör bara skicka meddelanden till de adresser den fick från meddelandet, till de adresser den redan hade innan den tog emot meddelandet och till de adresser den skapade under bearbetningen av meddelandet. meddelande.
Lokalitet innebär också att flera adressändringar inte kan ske samtidigt. I detta avseende skiljer sig aktörsmodellen från vissa andra samtidighetsmodeller, såsom Petrinets , där implementeringar samtidigt kan tas bort från flera positioner och placeras på olika adresser.
Idén att komponera system av skådespelare till större enheter är en viktig aspekt av modularitet, som utvecklades i Gool Ags doktorsexamen .
Den främsta innovationen i aktörsmodellen var introduktionen av begreppet beteende, definierat som en matematisk funktion som uttrycker en aktörs handlingar när den bearbetar meddelanden, inklusive definitionen av ett nytt beteende för att bearbeta nästa inkommande meddelande. Beteendet ger funktionen hos den matematiska modellen för parallellism.
Beteendet frigör också aktörsmodellen från implementeringsdetaljer, som till exempel i Smalltalk-72, trådtolkningsmarkören gör. Det är dock viktigt att förstå att en effektiv implementering av de system som beskrivs av aktörsmodellen kräver avancerad optimering.
Andra system för samtidighet (som processkalkyl ) kan modelleras i aktörsmodellen med hjälp av tvåfasprotokollet [19] .
I aktörsmodellen finns ett beräkningsrepresentationsteorem för slutna system, i den meningen att de inte tar emot meddelanden utifrån. I matematisk notation är ett slutet system, betecknat som S , byggt som den bästa approximationen för det initiala beteendet, kallat ⊥ S , med hjälp av en approximativ progressionsfunktion för S -beteende byggd för S enligt följande (enligt Hewitts 2008-publikation):
Beteckna S ≡ ⊔ i∈ω progression S i (⊥ S )Således kan S matematiskt karakteriseras i termer av alla dess möjliga beteenden (inklusive att ta hänsyn till obegränsad icke-determinism). Även om Denote S inte är en implementering av S , kan den användas för att bevisa följande generalisering av Church-Turing-tesen [20] : om en aktör som är primitiv i ett slutet system av aktörer är effektiv, så är dess möjliga utdata rekursivt uppräknade. Beviset följer direkt av beräkningsrepresentationssatsen.
Utvecklingen av skådespelaremodellen har ett intressant samband med matematisk logik. En av de viktigaste motiven för dess utveckling var behovet av att hantera aspekter som uppstod under utvecklingen av programmeringsspråket Planner . När skådespelarmodellen ursprungligen formulerades blev det viktigt att fastställa modellens kraft i förhållande till Robert Kowalskis tes att "beräkningar kan grupperas efter slutsatser." Kowalskis tes visade sig vara falsk för samtidiga beräkningar i skådespelarmodellen. Detta resultat är fortfarande diskutabelt och motsäger vissa tidigare idéer, eftersom Kowalskis avhandling är sann för sekventiella beräkningar och även för vissa typer av parallella beräkningar, till exempel för lambda-kalkyler.
Ändå har försök gjorts att utvidga logisk programmering till samtidig beräkning. Emellertid hävdar Hewitt och Aga i en artikel från 1999 att det resulterande systemet inte är deduktivt i följande mening: beräkningsstegen i parallella logiska programmeringssystem följer inte deduktivt från tidigare steg.
Migration i aktörsmodellen är en aktörs förmåga att byta plats. Till exempel modellerade Aki Yonezawa i sin avhandling en posttjänst där klientaktörer kunde gå in, byta plats medan de sprang och lämna. En aktör som kunde migrera modellerades som en aktör med en specifik plats som förändras när skådespelaren migrerar. Men tillförlitligheten av denna simulering är kontroversiell och är föremål för forskning.
Skådespelare kan säkras på något av följande sätt:
En subtil punkt i skådespelarens modell är förmågan att syntetisera adressen till en skådespelare. I vissa fall kan säkerhetssystemet förbjuda syntesen av adresser. Eftersom adressen till en skådespelare bara är en bitsträng är det uppenbarligen möjligt att syntetisera den, men om bitsträngen är tillräckligt lång är det ganska svårt eller till och med omöjligt att hitta skådespelarens adress. SOAP använder URL :en där skådespelaren finns som slutpunktsadress . Eftersom URL : en är en sträng av tecken är det uppenbarligen möjligt att syntetisera den, men om kryptering tillämpas är det nästan omöjligt att plocka upp strängen.
Aktöradresssyntes modelleras vanligtvis med en kartläggning. Tanken är att använda aktörssystemet för att kartlägga till skådespelarnas faktiska adresser. Till exempel kan en dators minnesstruktur modelleras som ett system av aktörer som ger en kartläggning. När det gäller SOAP- adresser är detta DNS- modellering och URL - mappning .
Robin Milners första publicerade arbete om samtidighet [21] var anmärkningsvärt för att inte vara baserat på sekventiell processsammansättning, skiljer sig från skådespelarmodellen eftersom det var baserat på ett fast antal processer, ett fast antal länkar i radtopologin som användes för att synkronisera länken. Den ursprungliga Cooperating Serial Processes (CSP)-modellen publicerad av Anthony Hoare [22] skiljer sig från aktörsmodellen eftersom den är baserad på den parallella sammansättningen av ett fast antal sekventiella processer länkade i en fast topologi och kommunicerar med hjälp av synkron meddelandeöverföring baserat på process namn. Senare versioner av CSP har gått bort från kommunikation baserad på processnamn och antagit principen om anonym kommunikation över rör. Detta tillvägagångssätt används också i Milners arbete med calculus of communicating systems och pi-calculus .
Båda dessa tidiga modeller av Milner och Hoare har begränsad icke-determinism. Moderna teoretiska modeller av interagerande system [23] ger direkt obegränsad icke-determinism.
Fyrtio år efter publiceringen av Moores lag beror den fortsatta ökningen av chipprestanda på metoder för lokal och global massiv parallellism. Lokal parallellism används i nya chips för 64-bitars flerkärniga mikroprocessorer, i multi-chip moduler och i högpresterande kommunikationssystem. Global samtidighet är för närvarande aktiverad i ny trådbunden och trådlös bredbandspaketväxlingshårdvara . Lagringskapaciteten på grund av både lokal och global parallellitet växer exponentiellt.
Modellen syftar till att lösa följande problem med att bygga datorsystem:
Många av idéerna som introducerats i skådespelarmodeller används nu också i multiagentsystem av samma skäl [24] . Den viktigaste skillnaden är att systemets agent (i de flesta definitioner) lägger ytterligare restriktioner på aktörerna, vilket vanligtvis kräver att de använder åtaganden och mål.
Aktörsmodellen används även i cloud computing- klienter [25] .
Tidiga programmeringsspråk med skådespelarestöd inkluderar Akt 1, 2 och 3 [26] [27] , Acttalk [28] , Ani [29] , Cantor [30] , Rosette [31]
Nyare skådespelarmodellorienterade språk: Actor-Based Concurrent Language (ABCL), ActorScript, AmbientTalk [32] , Axum [33] . Allmänt använda programmeringsspråk som använder begreppet skådespelare inkluderar E , Elixir [34] , Erlang , Io , SALSA [35] , Scala [36] [37] .
Bibliotek och tabellstrukturer med skådespelare har utvecklats för att ge en skådespelareliknande programmeringsstil på språk som inte har inbyggda skådespelare.
| Bibliotek och bordsstrukturer med skådespelare | |||
|---|---|---|---|
| namn | Senaste releasedatum | Licens | Programmeringsspråk |
| ActiveJava | 2008 | ? | Java |
| Skådespelare | 2013-05-31 | MIT | Java |
| Skådespelare-CPP | 2012-03-10 [38] | GPL 2.0 | C++ |
| Skådespelare Framework | 2013-11-13 | Apache 2.0 | .NETTO |
| ActorKit | 2011-09-13 [39] | BSD | Mål-C |
| Akka | 2015-04-23 | Apache 2.0 | Java och Scala |
| Akka.NET | 2016-01-18 | Apache 2.0 | .NETTO |
| C++ Actor Framework (CAF) | 2015-11-25 [40] | Boost Software License 1.0 och BSD 3-klausul | C++11 |
| Celluloid | 2016-01-19 [41] | MIT | rubin |
| Cloud Haskell | 2015-06-17 [42] | BSD | Haskell |
| CloudI | 2015-12-24 [43] | BSD | C/C++, Elixir/Erlang/LFE, Java, Javascript, Perl, PHP, Python, Ruby |
| Funktionell Java | 2016-02-15 [44] | BSD | Java |
| GPars | 2014-05-09 [45] | Apache 2.0 | Häftig |
| jetlang | 2013-05-30 [46] | NewBSD | Java |
| Korus | 2010-02-04 | GPL 3 | Java |
| [ 47 ] | 2011-10-13 [48] | MIT | Java |
| LabVIEW Actor Framework | 2012-03-01 [49] | ? | LabVIEW |
| libprocess | 2013-06-19 | Apache 2.0 | C++ |
| NAct | 2012-02-28 | LGPL 3.0 | .NETTO |
| OOSMOS | 2016-02-17 [50] | GPL 2.0 och kommersiella | C, C++ |
| Bana | 2016-02-16 [51] | NewBSD | Java |
| Orleans | 2019-06-04 [52] | MIT | .NETTO |
| Panini | 2014-05-22 | MPL 1.1 | Eget programmeringsspråk |
| Peernetisk | 2007-06-29 | LGPL 3.0 | Java |
| PostSharp | 2014-09-24 | Kommersiell / Freemium | .NETTO |
| Pulsar | 2016-11-24 [53] | NewBSD | Pytonorm |
| Pulsar | 2016-02-18 [54] | LGPL / Eclipse | Clojure |
| Pykka | 2022-05-28 [55] | Apache 2.0 | Pytonorm |
| React.Net | ? | MIT | .NETTO |
| Retlang | 2011-05-18 [56] | NewBSD | .NETTO |
| rotor | 2022-05-23 | MIT | C++17 |
| S4 | 2012-07-31 [57] | Apache 2.0 | Java |
| SObjectizer | 2016-02-11 | NewBSD | C++11 |
| Termitschema | 2009-05-21 | LGPL | Schema |
| Theron | 2014-01-18 [58] | M.I.T. [59] | C++ |
| Thespian | 2019-09-11 [60] | GoDaddy Public Release [61] | Pytonorm |
| QP | 2015-09-29 [62] | GPL 2.0 och kommersiella | C och C++ |
| kvasar | 2016-01-18 [63] | LGPL / Eclipse | Java |