Skuespillermodellen er en matematisk model for parallel computing , bygget op omkring begrebet en aktør ( eng. actor "aktør; handlende subjekt"), som betragtes som en universel primitiv for parallel eksekvering. En aktør i denne model interagerer ved at udveksle beskeder med andre aktører, og hver af dem kan som svar på modtagne beskeder træffe lokale beslutninger, oprette nye aktører, sende deres egne beskeder og bestemme, hvordan de skal reagere på efterfølgende beskeder.
Skabt som et teoretisk grundlag for en række praktiske implementeringer af parallelle systemer .
Hovedideerne og grundlaget for modellen blev fastlagt i 1973 ved udgivelsen af Hewitt, Bishop og Steiger [1] . Programmeringssprogene Lisp , Simula og tidlige versioner af Smalltalk , såvel som metoder til parametrisk beskyttelse og pakkeskift , påvirkede processen med modeldannelse . Hovedmotivationen for at skabe modellen var opgaven med at bygge distribuerede computersystemer baseret på hundreder og tusinder af uafhængige computere udstyret med deres egne lokale hukommelses- og kommunikationsgrænseflader [2] . Med fremkomsten af multiprocessorsystemer og multi-core arkitekturer steg interessen for aktørmodellen også uden for konteksten af distribuerede systemer.
I 1975 blev operationel semantik for skuespillermodellen [3] [4] udviklet . I 1977 blev et system af aksiomatiske love for skuespillermodeller udviklet [5] . I 1981 blev modellens denotationelle semantik (semantik af overgange) [2] [6] skabt , udviklet og generaliseret i 1985 [7] ; som et resultat af disse værker anerkendes teorien om skuespillermodeller som udviklet og uddybet.
I 1990'erne blev der skabt formalismer, som ikke fuldt ud svarer til aktørmodellen (formaliserer ikke garanteret meddelelseslevering), men som er af praktisk interesse, især flere forskellige aktøralgebraer [8] [9] og fortolkning baseret på lineær logik [10] .
I analogi med filosofien om objektorienteret programmering , hvor hver primitiv betragtes som et objekt, fremhæver skuespillermodellen begrebet "aktør" som en universel enhed. En aktør er en beregningsenhed, der som svar på en modtaget besked samtidigt kan:
Det antages ikke, at der er en bestemt rækkefølge af ovenstående handlinger, og de kan alle udføres parallelt.
Adskillelsen af afsenderen fra de sendte beskeder var en grundlæggende præstation af aktørmodellen: den giver asynkron kommunikation og kontrol af strukturer i form af beskedoverførsel [11] .
Modtagere af beskeder identificeres med en adresse, nogle gange omtalt som en "postadresse". En skuespiller kan således kun interagere med de aktører, hvis adresser den har, kan udtrække adresser fra modtagne beskeder eller kende dem på forhånd, hvis skuespilleren selv har skabt dem.
Modellen er karakteriseret ved iboende parallelitet af beregninger inden for og mellem aktører, dynamisk skabelse af aktører, inklusion af aktøradresser i meddelelser og interaktion kun gennem direkte asynkron meddelelse uden nogen begrænsninger i rækkefølgen af meddelelsers ankomst.
Aktørmodellen kan bruges som grundlag for modellering, forståelse og ræsonnement på en bred vifte af samtidige systemer , f.eks.
Måske var de første parallelle programmer interrupt-handlere . Under drift skal en computer som regel reagere på eksterne hændelser, der kan forekomme på et tidligere ukendt tidspunkt (asynkront i forhold til det program, der kører i øjeblikket) - for eksempel for at modtage information udefra (tegn fra tastaturet) , pakker fra netværket og så videre). Den mest effektive håndtering af sådanne hændelser implementeres ved hjælp af såkaldte interrupts. Når en hændelse opstår, "afbrydes udførelsen af det aktuelle program", og interrupt-handleren startes , som udfører de handlinger, der er nødvendige for at reagere på hændelsen (f.eks. modtager indgående information og gemmer den i en buffer, hvorfra den kan læses senere), hvorefter hovedprogrammet fortsætter arbejdet, hvor det slap .
I begyndelsen af 1960'erne begyndte man at bruge interrupts til at simulere den samtidige udførelse af flere programmer på en enkelt processor [13] . Tilstedeværelsen af parallelitet med delt hukommelse har ført til problemet med samtidighedskontrol. Oprindeligt blev denne opgave tænkt som en af mutexes på en separat computer. Edsger Dijkstra udviklede semaforer , og senere, mellem 1971 og 1973, blev monitorer [14] [15] [16] udviklet af Charles Hoare og Per Hansen for at løse mutex-problemet . Imidlertid skabte ingen af disse løsninger konstruktioner i programmeringssprog, der ville indkapsle adgang til delte ressourcer. Indkapsling blev senere udført af Hewitt og Atkinson under anvendelse af serialiseringskonstruktioner ([Hewitt, Atkinson 1977, 1979] og [Atkinson 1980]).
De første beregningsmodeller (f.eks. Turing -maskine , Post-maskine , lambda-regning osv.) var baseret på matematik og brugte begrebet en global stat til at definere "beregningstrinnet" (senere blev disse begreber generaliseret i McCarthys og McCarthys værker. Dijkstra [17] [18] ). Hvert beregningstrin gik fra en global beregningstilstand til den næste. Den globale statstilgang er blevet videreført i automatteori for finite automater og stakmaskiner, inklusive deres ikke- deterministiske versioner. Sådanne ikke-deterministiske automater har egenskaben af begrænset ikke-determinisme. Det vil sige, at hvis maskinen altid står, før den går til starttilstanden, så er der en grænse for, hvor mange tilstande den kan være i.
Dijkstra udviklede den ikke-deterministiske globale statstilgang yderligere. Dijkstras model har givet anledning til uenighed om ubegrænset nondeterminisme, en egenskab ved parallel computing , hvorved mængden af latens i servicering af en anmodning kan blive ubegrænset som følge af arbitragekonkurrence om delte ressourcer, samtidig med at den garanterer, at anmodningen i sidste ende vil blive serviceret. Hewitt argumenterede for, at skuespillermodellen skulle give garantier for leveringen af en service. Selvom der i Dijkstras model ikke kan være ubegrænset tid mellem udførelsen af sekventielle operationer på en computer, kan et program, der kører parallelt, og som begyndte sit arbejde i en strengt defineret tilstand, kun afbrydes i et begrænset antal tilstande [18 ] . Derfor kan Dijkstras model ikke give garantier for levering af en service. Dijkstra hævdede, at det var umuligt at implementere ubegrænset nondeterminisme.
Hewitt hævdede noget andet: der er ingen grænse for den tid, der bruges på arbejdet i den sektion af beregninger, kaldet voldgiftsdommeren til at løse konflikter. Voldgiftsmænd beskæftiger sig med løsningen af sådanne situationer. Computerens ur fungerer asynkront med eksterne indgange: tastaturindgang, diskadgang, netværksinput og så videre. Så det kan tage ubegrænset tid at modtage en besked sendt til en computer, og i den tid kan computeren gå igennem et ubegrænset antal tilstande.
Ubegrænset ikke-determinisme er et karakteristisk træk ved aktørmodellen, som bruger Klingers matematiske model baseret på teorien om regioner [2] . Der er ingen global stat i skuespillermodellen.
Beskeder i skuespillermodellen er ikke nødvendigvis bufret. Dette er dens skarpe forskel fra tidligere tilgange til simultanberegningsmodellen. Manglen på buffering forårsagede en masse misforståelser under udviklingen af skuespillermodellen og er stadig et emne for kontroverser den dag i dag. Nogle forskere hævder, at meddelelser er bufret i "luften" eller "miljøet". Også beskeder i skuespillermodellen sendes simpelthen (for eksempel pakker i IP ). Der er ikke krav om et synkront håndtryk med modtageren.
En naturlig udvikling af skuespillermodellen var evnen til at videregive adresser i beskeder. Påvirket af pakkekoblede netværk foreslog Hewitt at udvikle en ny samtidig computermodel, hvor linket slet ikke ville have nogen påkrævede felter, som alle kunne være tomme. Hvis afsenderen af beskeden ønsker, at modtageren skal have adgang til adresser, som han ikke allerede har, skal adressen sendes i beskeden.
Under beregningen kan det være nødvendigt at sende en besked til en modtager, som der senere skal modtages et svar fra. Måden at gøre dette på er at sende en besked, der indeholder adressen på en anden skuespiller, kaldet et CV (nogle gange også kaldet en fortsættelse eller opkaldsstabel ). Modtageren kan derefter oprette en svarbesked, der skal sendes ved CV .
Skabelsen af aktører plus inddragelse af deltageradresser i beskeder betyder, at aktørmodellen har en potentielt variabel topologi i deres forhold til hinanden, svarende til objekter i Simula-sproget, der også har en variabel topologi i deres forhold til hinanden.
I modsætning til den tidligere tilgang baseret på at kombinere sekventielle processer, blev aktørmodellen designet som en simultanmodel i sin essens. Som skrevet i teorien om skuespillermodeller er sekvensen i den et specialtilfælde, der opstår fra samtidige beregninger.
Hewitt var imod at inkludere krav om, at beskeder skal ankomme i den rækkefølge, de blev sendt til skuespillermodellen. Ønskes det at bestille indgående beskeder, kan dette modelleres med en aktørkø, der leverer denne funktionalitet. Sådanne aktørkøer vil sortere indgående meddelelser, så de modtages i FIFO -rækkefølge . Generelt, hvis en aktør X sender en besked M1 til en aktør Y , og derefter den samme aktør X sender en anden besked M2 til Y , så er der ikke noget krav om, at M1 ankommer til Y før M2 .
I denne henseende afspejler skuespillermodellen pakkekoblingssystemet, som ikke garanterer, at pakker vil blive modtaget i den rækkefølge, de blev sendt. Manglen på meddelelsesleveringsordregarantier gør det muligt for pakkeomskiftersystemet at buffere pakker, bruge flere stier til at sende pakker, sende beskadigede pakker igen og bruge andre optimeringsteknikker.
For eksempel kan aktører bruge en pipeline til meddelelsesbehandling. Dette betyder, at i processen med at behandle besked M1 , kan aktøren variere den adfærd, der vil blive brugt til at behandle den næste besked. Dette betyder især, at den kan begynde at behandle endnu en besked M2 , før behandlingen af M1 er færdig . Bare fordi en aktør får ret til at bruge en meddelelsesbehandlingspipeline, betyder det ikke, at den skal bruge denne pipeline. Hvorvidt en besked vil blive pipelinet eller ej, er et spørgsmål om teknisk kompromis. Hvordan kan en udefrakommende observatør vide, at en skuespillers meddelelsesbehandling er gået igennem pipelinen? Der er ingen tvetydighed om en aktørs brug af pipelining-kapaciteten i denne henseende. Kun hvis implementeringen af pipelinet optimering i en bestemt implementering udføres forkert, kan der opstå andet end den forventede adfærd.
Et andet vigtigt kendetegn ved aktørmodellen er lokalitet: Når en aktør behandler en besked, kan en aktør kun sende beskeder til de adresser, den modtog fra beskeden, til de adresser, den allerede havde før modtagelse af beskeden, og til de adresser, den oprettede under behandlingen af beskeden. besked.
Lokalitet betyder også, at flere adresseændringer ikke kan forekomme på samme tid. I denne henseende adskiller aktørmodellen sig fra nogle andre samtidighedsmodeller, såsom Petri nets , hvor implementeringer samtidigt kan fjernes fra flere positioner og placeres på forskellige adresser.
Ideen om at sammensætte systemer af skuespillere til større enheder er et vigtigt aspekt af modularitet, som blev udviklet i Gool Ag 's Ph.D.
Aktørmodellens vigtigste innovation var introduktionen af adfærdsbegrebet, defineret som en matematisk funktion, der udtrykker en aktørs handlinger, når den behandler beskeder, herunder definitionen af en ny adfærd til behandling af den næste indkommende besked. Adfærden sørger for funktionen af den matematiske model for parallelisme.
Adfærden frigør også aktørmodellen fra implementeringsdetaljer, som for eksempel i Smalltalk-72 trådfortolkermarkøren gør. Det er dog vigtigt at forstå, at effektiv implementering af de systemer, aktørmodellen beskriver, kræver avanceret optimering.
Andre samtidighedssystemer (såsom procesberegning ) kan modelleres i aktørmodellen ved hjælp af den tofasede commit-protokol [19] .
I aktørmodellen er der en beregningsrepræsentationssætning for lukkede systemer, i den forstand at de ikke modtager beskeder udefra. I matematisk notation er et lukket system, betegnet som S , bygget som den bedste tilnærmelse for den indledende adfærd, kaldet ⊥ S , ved hjælp af en tilnærmet progressionsfunktion S adfærdsfunktion bygget til S som følger (ifølge Hewitts 2008-publikation):
Betegn S ≡ ⊔ i∈ω progression S i (⊥ S )S kan således karakteriseres matematisk i forhold til alle dets mulige adfærd (inklusive at tage hensyn til ubegrænset ikke-determinisme). Selvom Denote S ikke er en implementering af S , kan den bruges til at bevise følgende generalisering af Church-Turing-tesen [20] : hvis en aktør, der er primitiv i et lukket system af aktører, er effektiv, så er dens mulige output rekursivt talrige. Beviset følger direkte af beregningsrepræsentationssætningen.
Udviklingen af skuespillermodellen har en interessant sammenhæng med matematisk logik. En af hovedmotivationerne for dets udvikling var behovet for at håndtere aspekter, der opstod under udviklingen af programmeringssproget Planner . Da først aktørmodellen oprindeligt var formuleret, blev det vigtigt at bestemme modellens magt i forhold til Robert Kowalskis tese om, at "beregninger kan grupperes efter slutninger." Kowalskis afhandling viste sig at være falsk for simultane beregninger i skuespillermodellen. Dette resultat er stadig diskutabelt og modsiger nogle tidligere ideer, eftersom Kowalskis afhandling er sand for sekventielle beregninger og endda for nogle former for parallelle beregninger, for eksempel for lambdaregning.
Ikke desto mindre er der blevet gjort forsøg på at udvide logisk programmering til samtidig databehandling. Imidlertid hævder Hewitt og Aga i et papir fra 1999, at det resulterende system ikke er deduktivt i følgende betydning: beregningstrinene i parallelle logiske programmeringssystemer følger ikke deduktivt fra tidligere trin.
Migration i aktørmodellen er en aktørs evne til at ændre sin placering. For eksempel modellerede Aki Yonezawa i sin afhandling en posttjeneste, hvor klientaktører kunne komme ind, skifte placering, mens de løb, og afslutte. En skuespiller, der kunne migrere, blev modelleret som en skuespiller med en bestemt placering, der ændrer sig, når skuespilleren migrerer. Men pålideligheden af denne simulering er kontroversiel og er genstand for forskning.
Skuespillere kan sikres på en af følgende måder:
Et subtilt punkt i skuespillermodellen er evnen til at syntetisere adressen på en skuespiller. I nogle tilfælde kan sikkerhedssystemet forbyde syntese af adresser. Da adressen på en skuespiller kun er en bitstreng, er det naturligvis muligt at syntetisere den, selvom hvis bitstrengen er lang nok, er det ret svært eller endda umuligt at finde skuespillerens adresse. SOAP bruger URL'en , hvor skuespilleren er placeret , som endepunktsadresse . Da URL'en er en streng af tegn, er det naturligvis muligt at syntetisere den, selvom hvis der anvendes kryptering, er det næsten umuligt at opfange strengen.
Aktøradressesyntese modelleres normalt med en kortlægning. Tanken er at bruge aktørsystemet til at kortlægge aktørernes faktiske adresser. For eksempel kan en computers hukommelsesstruktur modelleres som et system af aktører, der giver en kortlægning. I tilfælde af SOAP -adresser er dette DNS - modellering og URL - mapping .
Robin Milners første publicerede arbejde om samtidighed [21] var bemærkelsesværdigt for ikke at være baseret på sekventiel processammensætning, forskellig fra aktørmodellen, fordi den var baseret på et fast antal processer, et fast antal links i rækketopologien, der blev brugt til at synkronisere linket. Den originale Cooperating Serial Processes (CSP) model udgivet af Anthony Hoare [22] adskiller sig fra aktørmodellen, fordi den er baseret på den parallelle sammensætning af et fast antal sekventielle processer forbundet i en fast topologi og kommunikerer ved hjælp af synkron meddelelsesoverførsel baseret på proces navne. Senere versioner af CSP har bevæget sig væk fra kommunikation baseret på procesnavne, idet princippet om anonym kommunikation på tværs af rør er blevet vedtaget. Denne tilgang bruges også i Milners arbejde med calculus af kommunikerende systemer og pi-calculus .
Begge disse tidlige modeller af Milner og Hoare har begrænset ikke-determinisme. Moderne teoretiske modeller af interagerende systemer [23] sørger direkte for ubegrænset nondeterminisme.
Fyrre år efter offentliggørelsen af Moores lov skyldes den fortsatte stigning i chip-ydeevne metoder med lokal og global massiv parallelisme. Lokal parallelitet bruges i nye chips til 64-bit multi-core mikroprocessorer, i multi-chip moduler og i højtydende kommunikationssystemer. Global samtidighed er i øjeblikket aktiveret i ny kablet og trådløs bredbåndspakkeswitchingshardware . Lagerkapaciteten på grund af både lokal og global parallelitet vokser eksponentielt.
Modellen er rettet mod at løse følgende problemer med at bygge computersystemer:
Mange af de ideer, der introduceres i skuespillermodeller, bliver nu også brugt i multi-agent-systemer af samme årsager [24] . Den vigtigste forskel er, at systemets agent (i de fleste definitioner) pålægger aktørerne yderligere begrænsninger, hvilket typisk kræver, at de bruger forpligtelser og mål.
Aktørmodellen bruges også i cloud computing- klienter [25] .
Tidlige programmeringssprog med skuespillerstøtte inkluderer Act 1, 2 og 3 [26] [27] , Acttalk [28] , Ani [29] , Cantor [30] , Rosette [31]
Nyere skuespillermodelorienterede sprog: Actor-Based Concurrent Language (ABCL), ActorScript, AmbientTalk [32] , Axum [33] . Generelle programmeringssprog, der bruger begrebet skuespiller, omfatter E , Elixir [34] , Erlang , Io , SALSA [35] , Scala [36] [37] .
Biblioteker og bordstrukturer med skuespillere er udviklet til at give en skuespillerlignende programmeringsstil på sprog, der ikke har indbyggede skuespillere.
| Biblioteker og bordstrukturer med aktører | |||
|---|---|---|---|
| Navn | Sidste udgivelsesdato | Licens | Programmeringssprog |
| ActiveJava | 2008 | ? | Java |
| Skuespiller | 31-05-2013 | MIT | Java |
| Skuespiller-CPP | 2012-03-10 [38] | GPL 2.0 | C++ |
| Skuespillerramme | 2013-11-13 | Apache 2.0 | .NET |
| ActorKit | 2011-09-13 [39] | BSD | Mål-C |
| Akka | 2015-04-23 | Apache 2.0 | Java og Scala |
| Akka.NET | 2016-01-18 | Apache 2.0 | .NET |
| C++ Actor Framework (CAF) | 25-11-2015 [40] | Boost Software License 1.0 og BSD 3-klausul | C++11 |
| Celluloid | 2016-01-19 [41] | MIT | rubin |
| Cloud Haskell | 2015-06-17 [42] | BSD | Haskell |
| CloudI | 24-12-2015 [43] | BSD | C/C++, Elixir/Erlang/LFE, Java, Javascript, Perl, PHP, Python, Ruby |
| Funktionel Java | 2016-02-15 [44] | BSD | Java |
| GPars | 2014-05-09 [45] | Apache 2.0 | Groovy |
| jetlang | 30-05-2013 [46] | NyBSD | Java |
| Korus | 2010-02-04 | GPL 3 | Java |
| [ 47 ] | 2011-10-13 [48] | MIT | Java |
| LabVIEW Actor Framework | 2012-03-01 [49] | ? | LabVIEW |
| libproces | 2013-06-19 | Apache 2.0 | C++ |
| NAct | 2012-02-28 | LGPL 3.0 | .NET |
| OOSMOS | 2016-02-17 [50] | GPL 2.0 og kommerciel | C, C++ |
| Kredsløb | 2016-02-16 [51] | NyBSD | Java |
| Orleans | 2019-06-04 [52] | MIT | .NET |
| Panini | 2014-05-22 | MPL 1.1 | Eget programmeringssprog |
| Peernetisk | 2007-06-29 | LGPL 3.0 | Java |
| PostSharp | 2014-09-24 | Kommerciel / Freemium | .NET |
| Pulsar | 24-11-2016 [53] | NyBSD | Python |
| Pulsar | 2016-02-18 [54] | LGPL / Eclipse | Clojure |
| Pykka | 28-05-2022 [55] | Apache 2.0 | Python |
| React.Net | ? | MIT | .NET |
| Retlang | 2011-05-18 [56] | NyBSD | .NET |
| rotor | 2022-05-23 | MIT | C++17 |
| S4 | 31-07-2012 [57] | Apache 2.0 | Java |
| SObjectizer | 2016-02-11 | NyBSD | C++11 |
| Termitskema | 2009-05-21 | LGPL | Ordning |
| Theron | 2014-01-18 [58] | M.I.T. [59] | C++ |
| Thespian | 2019-09-11 [60] | GoDaddy Public Release [61] | Python |
| QP | 29-09-2015 [62] | GPL 2.0 og kommerciel | C og C++ |
| Quasar | 2016-01-18 [63] | LGPL / Eclipse | Java |