Modelul actorului este un model matematic de calcul paralel , construit în jurul conceptului de actor ( ing. actor „actor; subiect actoric”), care este considerat o primitivă universală de execuție paralelă. Un actor din acest model interacționează prin schimbul de mesaje cu alți actori și fiecare ca răspuns la mesajele primite poate lua decizii locale, poate crea noi actori, trimite propriile mesaje și poate determina cum să răspundă la mesajele ulterioare.
Creat ca bază teoretică pentru o serie de implementări practice ale sistemelor paralele .
Principalele idei și baza pentru model au fost stabilite în 1973 prin publicația lui Hewitt, Bishop și Steiger [1] . Limbajele de programare Lisp , Simula și versiunile timpurii ale Smalltalk , precum și metodele de protecție parametrică și comutare de pachete , au influențat procesul de formare a modelului . Principala motivație pentru crearea modelului a fost sarcina de a construi sisteme de calcul distribuite bazate pe sute și mii de calculatoare independente echipate cu propriile interfețe de comunicare și memorie locală [2] . Odată cu apariția sistemelor multiprocesor și a arhitecturilor multi-core , interesul pentru modelul actorului a crescut și în afara contextului sistemelor distribuite.
În 1975, a fost dezvoltată semantica operațională pentru modelul actorului [3] [4] . În 1977, a fost dezvoltat un sistem de legi axiomatice pentru modelele actorilor [5] . În 1981, semantica denotațională a modelului (semantica tranzițiilor) [2] [6] a fost creată , dezvoltată și generalizată în 1985 [7] ; ca urmare a acestor lucrări, teoria modelelor actorilor este recunoscută ca dezvoltată și elaborată.
În anii 1990, au fost create formalisme care nu corespund pe deplin modelului actorului (nu formalizează livrarea garantată a mesajelor), dar prezintă interes practic, în special, mai multe algebre ale actorilor diferite [8] [9] și interpretare bazată pe logica liniară . [10] .
Prin analogie cu filosofia programării orientate pe obiecte , în care fiecare primitivă este considerată un obiect, modelul actorului evidențiază conceptul de „actor” ca entitate universală. Un actor este o entitate computațională care, ca răspuns la un mesaj primit, poate simultan:
Nu se presupune că există o secvență specifică a acțiunilor de mai sus și toate pot fi efectuate în paralel.
Separarea emițătorului de mesajele transmise a fost o realizare fundamentală a modelului actor: asigură comunicarea asincronă și controlul structurilor sub forma transmiterii mesajelor [11] .
Destinatarii mesajelor sunt identificați printr-o adresă, denumită uneori „adresă poștală”. Astfel, un actor nu poate interacționa decât cu acei actori ale căror adrese le are, poate extrage adrese din mesajele primite sau le poate cunoaște dinainte dacă actorul le-a creat el însuși.
Modelul este caracterizat de paralelismul inerent al calculelor în interiorul și între actori, crearea dinamică a actorilor, includerea adreselor actorilor în mesaje și interacțiunea numai prin mesagerie asincronă directă, fără restricții privind ordinea de sosire a mesajelor.
Modelul actorului poate fi folosit ca bază pentru modelarea, înțelegerea și raționamentul pe o gamă largă de sisteme concurente , de exemplu:
Poate că primele programe paralele au fost manipulatorii de întreruperi . În timpul funcționării, de regulă, un computer trebuie să răspundă la evenimente externe care pot apărea într-un moment necunoscut anterior (în mod asincron în raport cu programul care se execută în prezent) - de exemplu, pentru a primi informații din exterior (caractere de la tastatură). , pachete din rețea și așa mai departe). Cea mai eficientă gestionare a unor astfel de evenimente este implementată folosind așa-numitele întreruperi. Când are loc un eveniment, execuția programului curent este „întreruptă” și este lansat handlerul de întreruperi , care efectuează acțiunile necesare pentru a răspunde la eveniment (de exemplu, primește informațiile primite și le stochează într-un buffer, de unde poate fi citit ulterior), după care programul principal continuă să lucreze de unde a rămas .
La începutul anilor 1960, întreruperile au început să fie folosite pentru a simula execuția simultană a mai multor programe pe un singur procesor [13] . Prezența paralelismului cu memoria partajată a dus la problema controlului concurenței. Inițial, această sarcină a fost concepută ca unul dintre mutexurile de pe un computer separat. Edsger Dijkstra a dezvoltat semafoare , iar mai târziu, între 1971 și 1973, monitoare [14] [15] [16] au fost dezvoltate de Charles Hoare și Per Hansen pentru a rezolva problema mutexului . Cu toate acestea, niciuna dintre aceste soluții nu a creat constructe în limbaje de programare care să încapsuleze accesul la resursele partajate. Încapsularea a fost realizată mai târziu de Hewitt și Atkinson folosind constructe serializatoare ([Hewitt, Atkinson 1977, 1979] și [Atkinson 1980]).
Primele modele de calcul (de exemplu , mașina Turing , mașina Post , calculul lambda etc.) s-au bazat pe matematică și au folosit conceptul de stare globală pentru a defini „etapa de calcul” (mai târziu aceste concepte au fost generalizate în lucrările lui McCarthy și Dijkstra [17] [18 ] ). Fiecare pas de calcul a trecut de la o stare globală de calcul la următoarea. Abordarea globală a stării a fost continuată în teoria automatelor pentru automate finite și mașini de stivă, inclusiv versiunile lor nedeterministe . Astfel de automate nedeterministe au proprietatea de nedeterminism limitat. Adică, dacă mașina stă întotdeauna înainte de a trece la starea inițială, atunci există o limită a numărului de stări în care poate fi.
Dijkstra a dezvoltat mai departe abordarea nedeterministă a stării globale. Modelul lui Dijkstra a dat naștere la controverse cu privire la nondeterminismul nelimitat, o proprietate a calculului paralel prin care cantitatea de latență în deservirea unei cereri poate deveni nelimitată ca urmare a competiției de arbitraj pentru resursele partajate, garantând în același timp că cererea va fi în cele din urmă. deservite. Hewitt a susținut că modelul actor ar trebui să ofere garanții pentru furnizarea unui serviciu. Deși în modelul lui Dijkstra nu poate exista un interval de timp nelimitat între execuția operațiilor secvențiale pe un computer, un program care rulează în paralel, care și-a început activitatea într-o stare strict definită, nu poate fi întrerupt decât într-un număr limitat de stări [18]. ] . Prin urmare, modelul Dijkstra nu poate oferi garanții pentru furnizarea unui serviciu. Dijkstra a susținut că este imposibil să se implementeze nondeterminismul nelimitat.
Hewitt a argumentat altfel: nu există o limită a timpului petrecut cu munca secțiunii de calcule, numită arbitru pentru soluționarea conflictelor. Arbitrii se ocupă de soluționarea unor astfel de situații. Ceasul computerului funcționează asincron cu intrările externe: intrare de la tastatură, acces la disc, intrare în rețea și așa mai departe. Deci poate dura o perioadă nelimitată de timp pentru a primi un mesaj trimis către un computer, iar în acel timp computerul poate trece printr-un număr nelimitat de stări.
Non-determinismul nelimitat este o trăsătură caracteristică a modelului actoric, care utilizează modelul matematic Klinger bazat pe teoria regiunilor [2] . Nu există o stare globală în modelul actorului.
Mesajele din modelul actorului nu sunt neapărat tamponate. Aceasta este diferența sa puternică față de abordările anterioare ale modelului de calcul simultan. Lipsa tamponării a provocat multe neînțelegeri în timpul dezvoltării modelului de actor și este încă un subiect de controversă până în prezent. Unii cercetători susțin că mesajele sunt tamponate în „aer” sau „mediu”. De asemenea, mesajele din modelul actor sunt pur și simplu trimise (de exemplu, pachete în IP ). Nu există nicio cerință pentru o strângere de mână sincronă cu destinatarul.
O evoluție firească a modelului de actor a fost capacitatea de a transmite adrese în mesaje. Influențat de rețelele cu comutare de pachete, Hewitt a propus să dezvolte un nou model de calcul concurent în care legătura să nu aibă deloc câmpuri obligatorii, toate acestea putând fi goale. Desigur, dacă expeditorul mesajului dorește ca destinatarul să aibă acces la adrese pe care nu le are deja, adresa trebuie trimisă în mesaj.
În timpul calculului, poate fi necesar să se trimită un mesaj unui destinatar de la care urmează să fie primit ulterior un răspuns. Modul de a face acest lucru este să trimiteți un mesaj care să conțină adresa altui actor, numit CV (uneori numit și continuare sau stivă de apeluri ). Destinatarul poate crea apoi un mesaj de răspuns care să fie trimis la reluare .
Crearea de actori plus includerea adreselor participanților în mesaje înseamnă că modelul actorului are o topologie potențial variabilă în relația lor unul cu celălalt, similar obiectelor din limbajul Simula care au, de asemenea, o topologie variabilă în relația lor între ele.
Spre deosebire de abordarea anterioară bazată pe combinarea proceselor secvențiale, modelul actorului a fost conceput ca un model simultan în esența sa. După cum este scris în teoria modelelor actorilor, secvența din aceasta este un caz special care decurge din calcule simultane.
Hewitt a fost împotriva includerii cerințelor conform cărora mesajele trebuie să sosească în ordinea în care au fost trimise modelului actorului. Dacă se dorește comandarea mesajelor primite, aceasta poate fi modelată cu o coadă de actori care oferă această funcționalitate. Astfel de cozi de actori ar ordona mesajele primite astfel încât acestea să fie primite în ordine FIFO . În general, dacă un actor X trimite un mesaj M1 unui actor Y și apoi același actor X trimite un alt mesaj M2 către Y , atunci nu există nicio cerință ca M1 să ajungă la Y înainte de M2 .
În acest sens, modelul actor reflectă sistemul de comutare de pachete, ceea ce nu garantează că pachetele vor fi primite în ordinea în care au fost trimise. Lipsa garanțiilor privind ordinea de livrare a mesajelor permite sistemului de comutare de pachete să tamponeze pachetele, să folosească mai multe căi pentru a trimite pachete, să retrimită pachetele deteriorate și să utilizeze alte tehnici de optimizare.
De exemplu, actorii pot folosi o conductă de procesare a mesajelor. Aceasta înseamnă că în procesul de procesare a mesajului M1 , actorul poate varia comportamentul care va fi utilizat pentru a procesa următorul mesaj. În special, aceasta înseamnă că poate începe procesarea încă un mesaj M2 înainte ca procesarea M1 să fie finalizată . Doar pentru că unui actor i se acordă dreptul de a utiliza o conductă de procesare a mesajelor nu înseamnă că trebuie să utilizeze acea conductă. Dacă un mesaj va fi transmis sau nu, este o chestiune de compromis tehnic. Cum poate un observator extern să știe că procesarea mesajului unui actor a trecut prin conductă? Nu există nicio ambiguitate cu privire la utilizarea de către un actor a capacității de pipeline în acest sens. Doar dacă, într-o anumită implementare, implementarea optimizării pipeline este făcută incorect, poate apărea altceva decât comportamentul așteptat.
O altă caracteristică importantă a modelului de actor este localitatea: atunci când procesează un mesaj, un actor poate trimite mesaje numai către adresele pe care le-a primit din mesaj, către adresele pe care le avea deja înainte de a primi mesajul și către adresele pe care le-a creat în timpul procesării mesajului. mesaj.
Localitatea înseamnă, de asemenea, că nu pot avea loc mai multe modificări de adresă în același timp. În acest sens, modelul actor diferă de alte modele de concurență, cum ar fi rețelele Petri , în care implementările pot fi eliminate simultan din mai multe poziții și plasate la adrese diferite.
Ideea de a alcătui sisteme de actori în entități mai mari este un aspect important al modularității, care a fost dezvoltat în doctoratul lui Gool Ag .
Principala inovație a modelului de actor a fost introducerea conceptului de comportament, definit ca o funcție matematică care exprimă acțiunile unui actor atunci când procesează mesaje, inclusiv definirea unui nou comportament pentru procesarea următorului mesaj primit. Comportamentul asigură funcționarea modelului matematic de paralelism.
Comportamentul eliberează, de asemenea, modelul actor de detaliile de implementare, așa cum face, de exemplu, în Smalltalk-72, markerul interpretorului de fir. Cu toate acestea, este important să înțelegem că implementarea eficientă a sistemelor descrise de modelul actor necesită o optimizare avansată.
Alte sisteme de concurență (cum ar fi calculul proceselor ) pot fi modelate în modelul actor folosind protocolul de comitere în două faze [19] .
În modelul actorului, există o teoremă de reprezentare computațională pentru sistemele închise, în sensul că acestea nu primesc mesaje din exterior. În notația matematică, un sistem închis, notat cu S , este construit ca cea mai bună aproximare pentru comportamentul inițial, numit ⊥ S , folosind o funcție de comportament S de progresie aproximată construită pentru S după cum urmează (conform publicației lui Hewitt din 2008):
Notăm S ≡ ⊔ i∈ω progresia S i (⊥ S )Astfel, S poate fi caracterizat matematic în ceea ce privește toate comportamentele sale posibile (inclusiv luând în considerare nondeterminismul nerestricționat). Deși Denote S nu este o implementare a lui S , poate fi folosit pentru a demonstra următoarea generalizare a tezei Church-Turing [20] : dacă un actor primitiv al unui sistem închis de actori este eficient, atunci posibilele sale rezultate sunt enumerabile recursiv. Demonstrarea rezultă direct din teorema reprezentării computaționale.
Dezvoltarea modelului actorului are o legătură interesantă cu logica matematică. Una dintre motivațiile cheie pentru dezvoltarea sa a fost nevoia de a gestiona aspectele apărute în timpul dezvoltării limbajului de programare Planner . Odată ce modelul actorului a fost formulat inițial, a devenit important să se determine puterea modelului în raport cu teza lui Robert Kowalski că „calculele pot fi grupate prin inferențe”. Teza lui Kowalski s-a dovedit a fi falsă pentru calcule simultane în modelul actorului. Acest rezultat este încă discutabil și contrazice unele idei anterioare, deoarece teza lui Kowalski este valabilă pentru calcule secvențiale și chiar pentru unele tipuri de calcule paralele, de exemplu, pentru calculele lambda.
Cu toate acestea, s-au făcut încercări de a extinde programarea logică la calculul concurent. Cu toate acestea, Hewitt și Aga într-o lucrare din 1999 susțin că sistemul rezultat nu este deductiv în următorul sens: pașii de calcul ai sistemelor de programare logică paralelă nu urmează în mod deductiv din pașii anteriori.
Migrația în modelul de actor este capacitatea unui actor de a-și schimba locația. De exemplu, Aki Yonezawa, în disertația sa, a modelat un serviciu poștal în care actorii clienți ar putea intra, schimba locația în timp ce rulează și ieși. Un actor care ar putea migra a fost modelat ca un actor cu o locație specifică care se schimbă atunci când actorul migrează. Cu toate acestea, fiabilitatea acestei simulări este controversată și face obiectul cercetării.
Actorii pot fi asigurați în unul dintre următoarele moduri:
Un punct subtil în modelul actorului este capacitatea de a sintetiza adresa unui actor. În unele cazuri, sistemul de securitate poate interzice sinteza adreselor. Deoarece adresa unui actor este doar un șir de biți, este evident posibil să o sintetizezi, deși dacă șirul de biți este suficient de lung, este destul de dificil sau chiar imposibil să găsești adresa actorului. SOAP folosește adresa URL în care se află actorul ca adresă punct final . Deoarece URL -ul este un șir de caractere, este evident posibil să-l sintetizezi, deși dacă se aplică criptarea, este aproape imposibil să ridici șirul.
Sinteza adresei actorilor este de obicei modelată cu o mapare. Ideea este de a folosi sistemul de actori pentru a mapa la adresele reale ale actorilor. De exemplu, structura de memorie a unui computer poate fi modelată ca un sistem de actori care oferă o mapare. În cazul adreselor SOAP , aceasta este modelarea DNS și maparea URL .
Prima lucrare publicată a lui Robin Milner despre concurență [21] s-a remarcat prin faptul că nu se bazează pe o compoziție secvențială a proceselor, diferită de modelul actorului, deoarece se baza pe un număr fix de procese, un număr fix de legături în topologia de rând folosită pentru sincronizați legătura. Modelul original Cooperating Serial Processes (CSP) publicat de Anthony Hoare [22] diferă de modelul actorului deoarece se bazează pe compoziția paralelă a unui număr fix de procese secvențiale legate într-o topologie fixă și care comunică utilizând transmiterea sincronă a mesajelor pe baza procesului. nume. Versiunile ulterioare ale CSP s-au îndepărtat de la comunicarea bazată pe nume de proces, adoptând principiul comunicării anonime prin conducte. Această abordare este folosită și în lucrările lui Milner privind calculul sistemelor comunicante și pi-calcul .
Ambele modele timpurii ale lui Milner și Hoare au un nondeterminism limitat. Modelele teoretice moderne ale sistemelor care interacționează [23] oferă în mod direct nondeterminism nelimitat.
La patruzeci de ani de la publicarea Legii lui Moore, creșterea continuă a performanței cipului se datorează metodelor de paralelism masiv local și global. Paralelismul local este utilizat în cipurile noi pentru microprocesoarele multi-core pe 64 de biți, în modulele cu mai multe cipuri și în sistemele de comunicații de înaltă performanță. Concurența globală este în prezent activată în noul hardware de comutare de pachete în bandă largă cu fir și fără fir. Capacitatea de stocare datorită paralelismului local și global crește exponențial.
Modelul are ca scop rezolvarea următoarelor probleme ale construcției de sisteme de calcul:
Multe dintre ideile introduse în modelele de actori sunt acum folosite și în sistemele multi-agent din aceleași motive [24] . Diferența cheie este că agentul sistemului (în majoritatea definițiilor) impune restricții suplimentare actorilor, solicitându-le de obicei să folosească angajamente și obiective.
Modelul actor este folosit și în clienții de cloud computing [25] .
Primele limbaje de programare cu suport pentru actori includ Act 1, 2 și 3 [26] [27] , Acttalk [28] , Ani [29] , Cantor [30] , Rosette [31]
Limbaje mai recente orientate pe modelul actorilor: Actor-Based Concurrent Language (ABCL), ActorScript, AmbientTalk [32] , Axum [33] . Limbajele de programare de uz general care folosesc conceptul de actor includ E , Elixir [34] , Erlang , Io , SALSA [35] , Scala [36] [37] .
Bibliotecile și structurile de tabel cu actori au fost dezvoltate pentru a oferi un stil de programare asemănător actorului în limbaje care nu au actori încorporați.
| Biblioteci și structuri de masă cu actori | |||
|---|---|---|---|
| Nume | Data ultimei emisii | Licență | Limbaje de programare |
| ActiveJava | 2008 | ? | Java |
| Actor | 31-05-2013 | MIT | Java |
| Actor-CPP | 2012-03-10 [38] | GPL 2.0 | C++ |
| Cadrul actorului | 13-11-2013 | Apache 2.0 | .NET |
| ActorKit | 2011-09-13 [39] | BSD | Obiectiv-C |
| Akka | 23-04-2015 | Apache 2.0 | Java și Scala |
| Akka.NET | 18-01-2016 | Apache 2.0 | .NET |
| C++ Actor Framework (CAF) | 25-11-2015 [40] | Boost Software License 1.0 și BSD 3-Clause | C++11 |
| Celuloid | 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 |
| Java funcțional | 2016-02-15 [44] | BSD | Java |
| GPars | 2014-05-09 [45] | Apache 2.0 | Macabru |
| jetlang | 30-05-2013 [46] | NewBSD | Java |
| Korus | 04-02-2010 | GPL 3 | Java |
| [ 47 ] | 2011-10-13 [48] | MIT | Java |
| Cadrul LabVIEW Actor | 2012-03-01 [49] | ? | LabVIEW |
| libprocess | 19-06-2013 | Apache 2.0 | C++ |
| NAct | 28-02-2012 | LGPL 3.0 | .NET |
| OOSMOS | 2016-02-17 [50] | GPL 2.0 și comercial | C, C++ |
| Orbită | 2016-02-16 [51] | NewBSD | Java |
| Orleans | 2019-06-04 [52] | MIT | .NET |
| Panini | 22-05-2014 | MPL 1.1 | Limbajul de programare propriu |
| Peernetic | 29-06-2007 | LGPL 3.0 | Java |
| PostSharp | 24-09-2014 | Comercial / Freemium | .NET |
| Pulsar | 24.11.2016 [53] | NewBSD | Piton |
| Pulsar | 2016-02-18 [54] | LGPL / Eclipse | Clojure |
| Pykka | 2022-05-28 [55] | Apache 2.0 | Piton |
| React.Net | ? | MIT | .NET |
| Retlang | 2011-05-18 [56] | NewBSD | .NET |
| rotor | 23-05-2022 | MIT | C++17 |
| S4 | 2012-07-31 [57] | Apache 2.0 | Java |
| SObjectizer | 2016-02-11 | NewBSD | C++11 |
| Schema de termite | 21-05-2009 | LGPL | Sistem |
| Theron | 2014-01-18 [58] | M.I.T. [59] | C++ |
| dramatic | 2019-09-11 [60] | Lansare publică GoDaddy [61] | Piton |
| QP | 29-09-2015 [62] | GPL 2.0 și comercial | C și C++ |
| Quasar | 2016-01-18 [63] | LGPL / Eclipse | Java |