Model herce je matematický model paralelního počítání , postavený na konceptu herce ( angl. herec "herec; jednající subjekt"), který je považován za univerzální primitiv paralelního provádění. Aktér v tomto modelu interaguje tak, že si vyměňuje zprávy s ostatními aktéry a každý v reakci na přijaté zprávy může činit místní rozhodnutí, vytvářet nové aktéry, posílat vlastní zprávy a určovat, jak reagovat na následné zprávy.
Vytvořeno jako teoretický základ pro řadu praktických implementací paralelních systémů .
Hlavní myšlenky a základ modelu byly stanoveny v roce 1973 publikací Hewitta, Bishopa a Steigera [1] . Proces tvorby modelu ovlivnily programovací jazyky Lisp , Simula a rané verze Smalltalku , stejně jako metody parametrické ochrany a přepínání paketů . Hlavní motivací pro vytvoření modelu byl úkol vybudovat distribuované výpočetní systémy založené na stovkách a tisících nezávislých počítačů vybavených vlastní lokální pamětí a komunikačním rozhraním [2] . S příchodem víceprocesorových systémů a vícejádrových architektur se zájem o model aktéra zvýšil i mimo kontext distribuovaných systémů.
V roce 1975 byla vyvinuta operační sémantika pro model aktéra [3] [4] . V roce 1977 byl vyvinut systém axiomatických zákonů pro modely herců [5] . V roce 1981 byla vytvořena denotační sémantika modelu (sémantika přechodů) [2] [6] , rozvinuta a v roce 1985 zobecněna [7] ; v důsledku těchto prací je teorie hereckých modelů uznávána jako rozvinutá a propracovaná.
V 90. letech 20. století byly vytvořeny formalismy, které plně neodpovídají modelu aktérů (neformalizují zaručené doručování zpráv), ale jsou prakticky zajímavé, zejména několik různých algeber aktorů [8] [9] a interpretace založené na lineární logice [10] .
Analogicky s filozofií objektově orientovaného programování , kde je každé primitivum považováno za objekt, model aktéra vyčleňuje koncept „herce“ jako univerzální entity. Aktér je výpočetní entita, která v reakci na přijatou zprávu může současně:
Nepředpokládá se, že existuje určitá posloupnost výše uvedených akcí a že je lze všechny provádět paralelně.
Oddělení odesílatele od zasílaných zpráv bylo zásadním úspěchem modelu aktéra: zajišťuje asynchronní komunikaci a řízení struktur ve formě předávání zpráv [11] .
Příjemci zpráv jsou identifikováni adresou, někdy označovanou jako „poštovní adresa“. Herec tak může komunikovat pouze s těmi herci, jejichž adresy má, může adresy vytahovat z přijatých zpráv nebo je předem znát, pokud je herec sám vytvořil.
Model se vyznačuje inherentní paralelností výpočtů uvnitř a mezi aktéry, dynamickým vytvářením aktérů, zahrnutím adres aktérů do zpráv a interakcí pouze prostřednictvím přímého asynchronního zasílání zpráv bez jakéhokoli omezení pořadí příchodu zpráv.
Model aktéra lze použít jako základ pro modelování, porozumění a uvažování na široké škále souběžných systémů , například:
Snad první paralelní programy byly obsluhy přerušení . Během provozu musí počítač zpravidla reagovat na vnější události, které se mohou vyskytnout v předem neznámém časovém okamžiku (asynchronně s ohledem na aktuálně prováděný program) - například přijímat informace zvenčí (znaky z klávesnice , pakety ze sítě a tak dále). Nejúčinnější zpracování takových událostí je realizováno pomocí tzv. přerušení. Když nastane událost, provádění aktuálního programu se „přeruší“ a spustí se obsluha přerušení , která provede akce nutné k reakci na událost (například přijímá příchozí informace a ukládá je do vyrovnávací paměti, odkud lze později přečíst), poté hlavní program pokračuje v práci tam, kde skončil .
Počátkem 60. let se přerušení začala používat k simulaci současného provádění několika programů na jednom procesoru [13] . Přítomnost paralelismu se sdílenou pamětí vedla k problému řízení souběžnosti. Zpočátku byl tento úkol koncipován jako jeden z mutexů na samostatném počítači. Edsger Dijkstra vyvinul semafory a později, v letech 1971 až 1973, byly Charlesem Hoareem a Perem Hansenem vyvinuty monitory [14] [15] [16] k vyřešení problému mutexu . Žádné z těchto řešení však nevytvořilo konstrukce v programovacích jazycích, které by zapouzdřovaly přístup ke sdíleným zdrojům. Zapouzdření později provedli Hewitt a Atkinson pomocí konstruktů serializátoru ([Hewitt, Atkinson 1977, 1979] a [Atkinson 1980]).
První modely počítání (např. Turingův stroj , Postův stroj , lambda počet atd.) byly založeny na matematice a využívaly konceptu globálního stavu k definování „výpočtového kroku“ (později byly tyto pojmy zobecněny v pracích McCarthyho a Dijkstra [17] [18] ). Každý výpočetní krok šel z jednoho globálního výpočetního stavu do dalšího. Přístup globálního stavu pokračuje v teorii automatů pro konečné automaty a zásobníkové stroje, včetně jejich nedeterministických verzí. Takové nedeterministické automaty mají vlastnost omezeného nedeterminismu. To znamená, že pokud stroj vždy stojí předtím, než přejde do počátečního stavu, pak existuje omezení počtu stavů, ve kterých může být.
Dijkstra dále rozvinul nedeterministický přístup globálního stavu. Dijkstrův model vyvolal polemiku o neomezeném nedeterminismu, což je vlastnost paralelního počítání , díky níž se latence při vyřizování požadavku může stát neomezeným v důsledku arbitrážní soutěže o sdílené zdroje, přičemž zároveň zaručuje, že požadavek bude nakonec splněn. servisováno. Hewitt tvrdil, že model aktéra by měl poskytovat záruky za poskytování služby. I když v Dijkstrově modelu nemůže být neomezené množství času mezi prováděním sekvenčních operací na počítači, paralelně běžící program, který zahájil svou práci v přesně definovaném stavu, může být přerušen pouze v omezeném počtu stavů [18 ] . Proto model Dijkstra nemůže poskytnout záruky za poskytování služby. Dijkstra tvrdil, že je nemožné implementovat neomezený nedeterminismus.
Hewitt argumentoval jinak: neexistuje žádný limit pro čas, který je vynaložen na práci sekce výpočtů, nazývané arbitr pro řešení konfliktů. Řešením takových situací se zabývají rozhodci. Hodiny počítače pracují asynchronně s externími vstupy: vstup z klávesnice, přístup na disk, síťový vstup atd. Přijetí zprávy odeslané do počítače tedy může trvat neomezeně dlouho a za tu dobu může počítač projít neomezeným počtem stavů.
Neomezený nedeterminismus je charakteristickým rysem modelu aktéra, který využívá Klingerův matematický model založený na teorii regionů [2] . V hereckém modelu neexistuje žádný globální stav.
Zprávy v modelu aktéra nemusí být nutně ukládány do vyrovnávací paměti. To je jeho ostrý rozdíl od předchozích přístupů k simultánnímu výpočetnímu modelu. Nedostatek vyrovnávací paměti způsobil mnoho nedorozumění během vývoje modelu herce a dodnes je předmětem sporů. Někteří výzkumníci tvrdí, že zprávy jsou uloženy ve „vzduchu“ nebo „prostředí“. Také se jednoduše odesílají zprávy v modelu aktéra (například pakety v IP ). Neexistuje žádný požadavek na synchronní podání ruky s příjemcem.
Přirozeným vývojem hereckého modelu byla schopnost předávat adresy ve zprávách. Pod vlivem sítí s přepojováním paketů navrhl Hewitt vyvinout nový souběžný výpočetní model, ve kterém by linka neměla vůbec žádná povinná pole a všechna by mohla být prázdná. Pokud si odesílatel zprávy přeje, aby měl příjemce přístup k adresám, které ještě nemá, musí být adresa odeslána ve zprávě.
Během výpočtu může být nutné odeslat zprávu příjemci, od kterého má být později obdržena odpověď. Způsob, jak toho dosáhnout, je odeslat zprávu obsahující adresu jiného aktéra, nazývanou resumé (někdy také nazývané pokračování nebo zásobník hovorů ). Příjemce pak může vytvořit zprávu s odpovědí, která bude odeslána jako životopis .
Vytvoření aktérů plus zahrnutí adres účastníků do zpráv znamená, že model aktéra má potenciálně proměnlivou topologii v jejich vzájemném vztahu, podobně jako objekty v jazyce Simula, které mají také proměnnou topologii ve svém vzájemném vztahu.
Na rozdíl od předchozího přístupu založeného na kombinování sekvenčních procesů byl herecký model ve své podstatě navržen jako simultánní. Jak je psáno v teorii hereckých modelů, sekvence v ní je speciální případ vznikající ze simultánních výpočtů.
Hewitt byl proti zahrnutí požadavků, že zprávy musí dorazit v pořadí, v jakém byly odeslány hereckému modelu. Pokud je požadováno seřadit příchozí zprávy, lze to modelovat pomocí fronty aktérů, která tuto funkcionalitu poskytuje. Takové fronty aktérů by seřadily příchozí zprávy tak, aby byly přijímány v pořadí FIFO . Obecně platí, že pokud aktér X pošle zprávu M1 aktéru Y a poté stejný aktér X pošle další zprávu M2 do Y , pak není žádný požadavek, aby M1 dorazil do Y před M2 .
V tomto ohledu model aktéra zrcadlí systém přepínání paketů, který nezaručuje, že pakety budou přijaty v pořadí, v jakém byly odeslány. Nedostatek záruk pořadí doručení zpráv umožňuje systému přepínání paketů ukládat pakety do vyrovnávací paměti, používat více cest k odesílání paketů, znovu odesílat poškozené pakety a používat další optimalizační techniky.
Herci mohou například použít kanál pro zpracování zpráv. To znamená, že v procesu zpracování zprávy M1 může aktér měnit chování, které bude použito pro zpracování další zprávy. Konkrétně to znamená, že může začít zpracovávat ještě jednu zprávu M2 před dokončením zpracování M1 . To, že je aktérovi uděleno právo používat kanál pro zpracování zpráv, neznamená, že musí tento kanál používat. Zda bude zpráva zpracována nebo ne, je věcí technického kompromisu. Jak může vnější pozorovatel vědět, že zpracování zprávy herce prošlo potrubím? V tomto ohledu neexistuje žádná nejednoznačnost ohledně využití schopnosti zřetězení ze strany aktéra. Pouze pokud je v konkrétní implementaci implementace zřetězené optimalizace provedena nesprávně, může dojít k něčemu jinému než očekávanému chování.
Další důležitou charakteristikou modelu aktéra je lokalita: při zpracování zprávy může aktér posílat zprávy pouze na adresy, které obdržel ze zprávy, na adresy, které měl již před přijetím zprávy, a na adresy, které vytvořil při zpracování zprávy. zpráva.
Lokalita také znamená, že nelze změnit více adres současně. V tomto ohledu se model aktéra liší od některých jiných souběžných modelů, jako jsou Petriho sítě , ve kterých mohou být implementace současně odstraněny z více pozic a umístěny na různé adresy.
Myšlenka skládání systémů aktérů do větších celků je důležitým aspektem modularity, který byl vyvinut v Gool Ag 's Ph.D.
Hlavní inovací modelu aktéra bylo zavedení konceptu chování, definovaného jako matematická funkce vyjadřující jednání aktéra při zpracování zpráv, včetně definice nového chování pro zpracování další příchozí zprávy. Chování zajišťuje fungování matematického modelu paralelismu.
Toto chování také osvobozuje model aktéra od implementačních detailů, jako to dělá například ve Smalltalku-72 značka interpretu vláken. Je však důležité pochopit, že efektivní implementace systémů popsaných modelem aktéra vyžaduje pokročilou optimalizaci.
Jiné systémy souběžnosti (jako je procesní počet ) lze modelovat v modelu aktéra pomocí dvoufázového potvrzovacího protokolu [19] .
V modelu aktéra existuje teorém výpočetní reprezentace pro uzavřené systémy v tom smyslu, že nepřijímají zprávy zvenčí. V matematické notaci je uzavřený systém, označený jako S , sestaven jako nejlepší aproximace pro počáteční chování, nazvaný ⊥ S , pomocí aproximující funkce chování S progrese sestavené pro S následovně (podle publikace Hewitt z roku 2008):
Označme S ≡ ⊔ i∈ω progresi S i (⊥ S )S lze tedy matematicky charakterizovat z hlediska všech možných způsobů chování (včetně zohlednění neomezeného nedeterminismu). Přestože Denote S není implementací S , lze jej použít k prokázání následujícího zobecnění Church-Turingovy teze [20] : je-li aktor primitiv uzavřeného systému aktérů efektivní, pak jsou jeho možné výstupy rekurzivně spočetné. Důkaz vyplývá přímo z věty o výpočetní reprezentaci.
Vývoj hereckého modelu má zajímavou souvislost s matematickou logikou. Jednou z klíčových motivací pro jeho vývoj byla potřeba řídit aspekty, které vznikly při vývoji programovacího jazyka Planner . Jakmile byl model herce původně formulován, stalo se důležité určit sílu modelu ve vztahu k tezi Roberta Kowalského , že „výpočty lze seskupit podle závěrů“. Kowalského teze se ukázala jako nepravdivá pro simultánní výpočty v modelu herce. Tento výsledek je stále diskutabilní a je v rozporu s některými předchozími myšlenkami, protože Kowalského teze platí pro sekvenční výpočty a dokonce i pro některé druhy paralelních výpočtů, například pro lambda výpočty.
Nicméně byly učiněny pokusy rozšířit logické programování na souběžné výpočty. Hewitt a Aga však v článku z roku 1999 tvrdí, že výsledný systém není deduktivní v následujícím smyslu: výpočetní kroky systémů paralelního logického programování nenásledují deduktivně z předchozích kroků.
Migrace v hereckém modelu je schopnost herce změnit své umístění. Například Aki Yonezawa ve své diplomové práci modeloval poštovní službu, do které mohli klientští herci vstupovat, měnit místo při běhu a vystupovat. Herec, který by mohl migrovat, byl modelován jako herec se specifickou polohou, která se mění, když herec migruje. Spolehlivost této simulace je však kontroverzní a je předmětem výzkumu.
Herci mohou být zajištěni jedním z následujících způsobů:
Jemným bodem v modelu herce je schopnost syntetizovat adresu herce. V některých případech může bezpečnostní systém zakázat syntézu adres. Vzhledem k tomu, že adresa aktéra je pouze bitový řetězec, je samozřejmě možné jej syntetizovat, ačkoli pokud je bitový řetězec dostatečně dlouhý, je poměrně obtížné nebo dokonce nemožné najít adresu aktéra. SOAP používá adresu URL , kde se nachází aktér , jako adresu koncového bodu . Vzhledem k tomu, že adresa URL je řetězec znaků, je samozřejmě možné ji syntetizovat, ačkoli pokud je použito šifrování, je téměř nemožné řetězec zachytit.
Syntéza adresy aktéra je obvykle modelována pomocí mapování. Cílem je použít herecký systém k mapování na skutečné adresy herců. Například paměťovou strukturu počítače lze modelovat jako systém aktérů, který poskytuje mapování. V případě SOAP adres se jedná o DNS modelování a mapování URL .
První publikovaná práce Robina Milnera o souběžnosti [21] byla pozoruhodná tím, že nebyla založena na sekvenčním složení procesu, což se lišilo od modelu aktéra, protože bylo založeno na pevném počtu procesů, pevném počtu odkazů v topologii řádků používané k synchronizovat odkaz. Původní model Cooperating Serial Processes (CSP) publikovaný Anthony Hoare [22] se liší od modelu aktéra, protože je založen na paralelním složení pevného počtu sekvenčních procesů spojených v pevné topologii a komunikujících pomocí synchronního předávání zpráv na základě procesu. jména. Pozdější verze CSP ustoupily od komunikace založené na názvech procesů a přijaly princip anonymní komunikace přes kanály. Tento přístup je také použit v Milnerově práci o kalkulu komunikujících systémů a pi-kalkulu .
Oba tyto rané modely Milnera a Hoarea mají omezený nedeterminismus. Moderní teoretické modely interagujících systémů [23] přímo umožňují neomezený nedeterminismus.
Čtyřicet let po zveřejnění Moorova zákona je pokračující nárůst výkonu čipu způsoben metodami lokálního a globálního masivního paralelismu. Lokální paralelismus se používá v nových čipech pro 64bitové vícejádrové mikroprocesory, ve vícečipových modulech a ve vysoce výkonných komunikačních systémech. Globální souběžnost je v současnosti umožněna v novém drátovém a bezdrátovém širokopásmovém hardwaru pro přepínání paketů. Kapacita úložiště díky lokálnímu i globálnímu paralelismu exponenciálně roste.
Model je zaměřen na řešení následujících problémů budování výpočetních systémů:
Mnoho myšlenek představených v modelech aktérů se nyní ze stejných důvodů používá také v multiagentních systémech [24] . Klíčový rozdíl je v tom, že agent systému (ve většině definic) ukládá aktérům další omezení, obvykle po nich vyžaduje, aby používali závazky a cíle.
Model aktéra se také používá v klientech cloud computingu [25] .
Mezi rané programovací jazyky s podporou herců patří Act 1, 2 a 3 [26] [27] , Acttalk [28] , Ani [29] , Cantor [30] , Rosette [31]
Novější jazyky orientované na model herce: Actor-Based Concurrent Language (ABCL), ActorScript, AmbientTalk [32] , Axum [33] . Mezi univerzální programovací jazyky, které využívají koncept herce, patří E , Elixir [34] , Erlang , Io , SALSA [35] , Scala [36] [37] .
Knihovny a struktury tabulek s herci byly vyvinuty tak, aby poskytovaly herecký styl programování v jazycích, které nemají vestavěné herce.
| Knihovny a stolní struktury s herci | |||
|---|---|---|---|
| název | Datum posledního vydání | Licence | Programovací jazyky |
| Aktivní Java | 2008 | ? | Jáva |
| Herec | 2013-05-31 | MIT | Jáva |
| Herec-CPP | 2012-03-10 [38] | GPL 2.0 | C++ |
| Actor Framework | 2013-11-13 | Apache 2.0 | .SÍŤ |
| ActorKit | 2011-09-13 [39] | BSD | Cíl-C |
| Akka | 2015-04-23 | Apache 2.0 | Java a Scala |
| Akka.NET | 2016-01-18 | Apache 2.0 | .SÍŤ |
| C++ Actor Framework (CAF) | 25. 11. 2015 [40] | Licence Boost Software 1.0 a BSD 3-klauzule | C++11 |
| Celuloid | 2016-01-19 [41] | MIT | rubín |
| 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 |
| Funkční Java | 2016-02-15 [44] | BSD | Jáva |
| GPars | 2014-05-09 [45] | Apache 2.0 | Báječný |
| jetlang | 2013-05-30 [46] | NewBSD | Jáva |
| Korus | 2010-02-04 | GPL 3 | Jáva |
| [ 47 ] | 2011-10-13 [48] | MIT | Jáva |
| LabVIEW Actor Framework | 2012-03-01 [49] | ? | LabVIEW |
| libprocess | 2013-06-19 | Apache 2.0 | C++ |
| NAct | 2012-02-28 | LGPL 3.0 | .SÍŤ |
| OOSMOS | 2016-02-17 [50] | GPL 2.0 a komerční | C, C++ |
| Obíhat | 2016-02-16 [51] | NewBSD | Jáva |
| Orleans | 2019-06-04 [52] | MIT | .SÍŤ |
| Panini | 2014-05-22 | MPL 1.1 | Vlastní programovací jazyk |
| Peernetický | 2007-06-29 | LGPL 3.0 | Jáva |
| PostSharp | 2014-09-24 | Komerční / Freemium | .SÍŤ |
| Pulsar | 24. 11. 2016 [53] | NewBSD | Krajta |
| Pulsar | 2016-02-18 [54] | LGPL / Eclipse | Clojure |
| Pykka | 2022-05-28 [55] | Apache 2.0 | Krajta |
| React.Net | ? | MIT | .SÍŤ |
| Retlang | 2011-05-18 [56] | NewBSD | .SÍŤ |
| rotor | 2022-05-23 | MIT | C++17 |
| S4 | 2012-07-31 [57] | Apache 2.0 | Jáva |
| SObjectizer | 2016-02-11 | NewBSD | C++11 |
| Schéma termitů | 2009-05-21 | LGPL | Systém |
| Theron | 2014-01-18 [58] | M.I.T. [59] | C++ |
| Thespian | 2019-09-11 [60] | Veřejné vydání GoDaddy [61] | Krajta |
| QP | 2015-09-29 [62] | GPL 2.0 a komerční | C a C++ |
| Quasar | 2016-01-18 [63] | LGPL / Eclipse | Jáva |