Herecký model a procesní kalkul - Actor model and process calculi
tento článek byl nominován na kontrolu neutralita.Dubna 2017) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v počítačová věda, Herecký model a zpracovat kalkul jsou dva úzce související přístupy k modelování souběžný digitální výpočet. Vidět Historie herců a zpracování kalkulů.
Mezi těmito dvěma přístupy existuje mnoho podobností, ale také několik rozdílů (některé filozofické, jiné technické):
- Je jen jeden Herecký model (i když má řadu formálních systémů pro návrh, analýzu, ověřování, modelování, atd.); je jich mnoho zpracovat kalkul, vyvinutý pro uvažování o řadě různých druhů souběžných systémů na různých úrovních podrobností (včetně kalkulů, které zahrnují čas, stochastické přechody nebo konstrukce specifické pro oblasti aplikace, jako je bezpečnostní analýza).
- Herecký model byl inspirován zákony fyzika a závisí na nich pro své základní axiomy, tj. fyzikální zákony (vidět Teorie modelu herce ); procesní kameny byly původně inspirovány algebra (Milner 1993 ).
- Procesy v procesních kalkulích jsou anonymní a komunikují zasíláním zpráv buď prostřednictvím pojmenovaných kanály (synchronní nebo asynchronní) nebo prostřednictvím prostředí (který lze také použít k modelování komunikace podobné kanálu (Cardelli a Gordon 1998 )). Naproti tomu aktéři v hercově modelu mají identitu a komunikují zasíláním zpráv na poštovní adresy jiných aktérů (tento styl komunikace lze také použít k modelování komunikace podobné kanálu - viz níže).
Publikace o hercově modelu a procesních výpočtech obsahují značné množství křížových odkazů, poděkování a vzájemných citací (viz Historie herců a zpracování kalkulů ).
Jak kanály fungují
Nepřímá komunikace pomocí kanálů (např. Gilles Kahn a David MacQueen [1977]) je důležitým problémem pro komunikaci v paralelním a souběžném výpočtu ovlivňujícím sémantiku i výkon. Některé procesní výpočty se liší od modelu Actor v použití kanálů na rozdíl od přímé komunikace.
Synchronní kanály
Synchronní kanály mají tu vlastnost, že odesílatel vkládající zprávu do kanálu musí počkat, než příjemce přijme zprávu z kanálu, než může odesílatel pokračovat.
Jednoduché synchronní kanály
Synchronní kanál může být modelován hercem, který přijímá dát
a dostat
komunikace. Následuje chování herce pro jednoduchý synchronní kanál:
- Každý
dát
komunikace má zprávu a adresu, na kterou je zasláno potvrzení, když je zpráva přijata adostat
komunikace z kanálu v FIFO objednat. - Každý
dostat
komunikace má adresu, na kterou je přijatá zpráva odeslána.
Synchronní kanály v procesních kalkulích
Jednoduché synchronní kanály však nestačí pro procesní výpočty, jako je Komunikace postupných procesů (CSP) [Hoare 1978 a 1985], protože použití hlídaná volba (po Dijkstra) příkaz (nazvaný alternativní příkaz v CSP). V příkazu s hlídanou volbou lze provést více nabídek (tzv. Stráží) na více kanálech dát
a dostat
zprávy; pro každé provedení příkazu střežené volby však lze vybrat maximálně jednoho ze strážců. Protože lze vybrat pouze jednoho strážného, vyžaduje příkaz strážného výběru obecně něco jako dvoufázový protokol potvrzení nebo možná dokonce a třífázový protokol potvrzení -li oddechové časy jsou povoleni u stráží (jako v Occam 3 [1992]).
Zvažte následující program napsaný v CSP [Hoare 1978]:
[X :: Z! Stop () || Y :: stráž: boolean; stráž: = pravda; * [stráž → Z! go (); Z? Stráž] || Z :: n: integer; n: = 0; * [X? Stop () → Y! False; tisk! n; [] Y? Go () → n: = n + 1; Y! Pravda]]
Podle Clingera [1981] tento program ilustruje globální nedeterminismus, protože nedeterminismus vyplývá z neúplné specifikace načasování signálů mezi třemi procesy X
, Y
, a Z
. Opakovaný hlídaný příkaz v definici Z
má dvě alternativy:
- the
stop
zpráva je přijata odX
, v jakém případěY
je odeslána hodnota Nepravdivé atisk
je odeslána hodnotan
- A
jít
zpráva je přijata odY
, v jakém případěn
je zvýšen aY
je odeslána hodnota skutečný.
Li Z
kdy přijímá stop
Zpráva od X
, pak X
končí. Přijímání stop
příčiny Y
k odeslání Nepravdivé který při zadání jako hodnota jeho stráže způsobí Y
ukončit. Když obojí X
a Y
ukončili, Z
končí, protože již nemá živé procesy poskytující vstup.
Ve výše uvedeném programu existují synchronní kanály z X
na Z
, Y
na Z
, a Z
na Y
.
Analogie s problémem koordinace výboru
Podle Knabe [1992] to Chandy a Misra [1988] charakterizovali jako analogii problému koordinace výboru:
- Profesoři na univerzitě jsou přiděleni do různých výborů. Profesorka se občas rozhodne zúčastnit se schůze kteréhokoli z jejích výborů a počká, dokud to nebude možné. Schůze mohou začít, pouze pokud je plná účast. Úkolem je zajistit, že pokud všichni členové výboru čekají, alespoň jeden z nich se zúčastní nějaké schůze.
- Podstatou tohoto problému je, že dva nebo více výborů může sdílet profesora. Jakmile bude tato profesorka k dispozici, může si vybrat pouze jednu ze schůzek, zatímco ostatní nadále čekají.
Jednoduchý distribuovaný protokol
Tato část představuje jednoduchý distribuovaný protokol pro kanály v synchronních procesních výpočtech. Protokol má některé problémy, které jsou řešeny v následujících částech.
Chování příkazu hlídané volby je následující:
- Příkaz pošle zprávu každému ze svých strážců
připravit
. - Když přijme první odpověď od jednoho ze svých strážců, že je připraven, odešle zprávu tomuto strážci
připravit se na spáchání
a posílá zprávy všem ostatním strážnýmpřerušit
.- Když přijme zprávu od stráže, že je
připraven spáchat
, potom pošle strážce aspáchat
zpráva. Pokud však hází výjimku, nemůžepřipravit se na spáchání
, pak příkaz hlídané volby spustí celý proces znovu.
- Když přijme zprávu od stráže, že je
- Pokud všichni jeho strážci odpoví, že nemohou
připravit
, pak střežený příkaz nic nedělá.
Chování stráže je následující:
- Když zpráva pro
připravit
je přijat, pak strážný pošle apřipravit
zprávu každému z kanálů, se kterými nabízí komunikaci. Pokud má strážce boolean tak, že nemůžepřipravit
nebo pokud některý z kanálů odpoví, že nemůžepřipravit
, pak odešlepřerušit
zprávy na ostatní kanály a poté odpoví, že to nemůžepřipravit
.- Když zpráva pro
připravit se na spáchání
je přijat, pak strážný pošle apřipravit se na spáchání
zprávu na každý z kanálů. Pokud některý z kanálů odpoví, že nemůžepřipravit se na spáchání
, pak odešlepřerušit
zprávy na ostatní kanály a poté vyvolá výjimku, kterou nemůžepřipravit se na spáchání
. - Když zpráva pro
spáchat
je přijat, pak strážný pošlespáchat
zprávu na každý z kanálů. - Když zpráva pro
přerušit
je přijat, pak strážný pošlepřerušit
zprávu na každý z kanálů.
- Když zpráva pro
Chování kanálu je následující:
- Když
připravte se na umístění
přijata komunikace, pak odpovězte, že je připravena, pokud existujepřipravit se na to
komunikace probíhá, pokud avypovědět
komunikace byla přijata, v takovém případě udělejte výjimku, že nemůžepřipravte se na umístění
. - Když
připravte se na to
přijata komunikace, pak odpovězte, že je připravena, pokud existujepřipravte se na umístění
komunikace probíhá, pokud avypovědět
komunikace byla přijata, v takovém případě udělejte výjimku, že nemůžepřipravte se na to
.- Když
připravte se na zavázání
přijata komunikace, pak odpovězte, že je připravena, pokud existujepřipravte se na závazek
komunikace probíhá, pokud avypovědět
komunikace byla přijata, v takovém případě udělejte výjimku, že nemůžepřipravte se na zavázání
. - Když
připravte se na závazek
přijata komunikace, pak odpovězte, že je připravena, pokud existujepřipravte se na zavázání
komunikace probíhá, pokud avypovědět
komunikace byla přijata, v takovém případě udělejte výjimku, že nemůžepřipravte se na závazek
.- Když
odevzdat
je přijata komunikace, pak podle toho, který z následujících je přijat:- Když
spáchat dostat
komunikace je přijata, pak pokud ještě není provedena, proveďtedát
adostat
a vyčistit přípravky. - Když
přerušit dostat
přijata komunikace, pak zrušte přípravy
- Když
- Když
spáchat dostat
je přijata komunikace, pak podle toho, který z následujících je přijat:- Když
odevzdat
komunikace je přijata, pak pokud ještě není provedena, proveďtedostat
adát
a vyčistit přípravky. - Když
přerušit
přijata komunikace, pak zrušte přípravy.
- Když
- Když
přerušit
přijata komunikace, pak zrušte přípravy. - Když
zrušit dostat
přijata komunikace, pak zrušte přípravy.
- Když
- Když
Hladovění při získávání z více kanálů
Znovu zvažte program napsaný v CSP (popsán v Synchronní kanály v procesních kalkulích výše):
[X :: Z! Stop () || Y :: stráž: boolean; stráž: = pravda; * [stráž → Z! go (); Z? Stráž] || Z :: n: integer; n: = 0; * [X? Stop () → Y! False; tisk! n; [] Y? Go () → n: = n + 1; Y! Pravda]]
Jak zdůrazňuje Knabe [1992], problém s výše uvedeným protokolem (Jednoduchý distribuovaný protokol ) je tento proces Z
možná nikdy nepřijme stop
Zpráva od X
(jev zvaný hladovění ) a výše uvedený program tedy nemusí nikdy nic tisknout.
Naproti tomu zvažte jednoduchý systém herců, který se skládá z herců X, Y, Z, a tisk kde
- herec X je vytvořen s následujícím chováním:
- Pokud je zpráva
"Start"
přijato, poté odešlete Z zpráva"stop"
- Pokud je zpráva
- herec Y je vytvořen s následujícím chováním:
- Pokud je zpráva
"Start"
přijato, poté odešlete Z zpráva"jít"
- Pokud je zpráva skutečný přijato, poté odešlete Z zpráva
"jít"
- Pokud je zpráva Nepravdivé je přijat, pak nedělejte nic
- Pokud je zpráva
- herec Z je vytvořeno s následujícím chováním, které má počet
n
to je zpočátku 0:- Pokud je zpráva
"Start"
je přijat, pak nedělejte nic. - Pokud je zpráva
"stop"
přijato, poté odešlete Y zpráva Nepravdivé a poslat tisk počet zprávn
. - Pokud je zpráva
"jít"
přijato, poté odešlete Y zpráva skutečný a zpracovat další přijatou zprávu s počtemn
bytostn + 1
.
- Pokud je zpráva
Podle zákonů aktorské sémantiky se výše uvedený aktorský systém vždy zastaví, když budou herci X, Y, jsou Z jsou každému zaslány a "Start"
zpráva vedoucí k odeslání tisk číslo, které může být neomezeně velké.
Rozdíl mezi programem CSP a systémem Actor je v tom, že Actor Z nepřijímá zprávy pomocí příkazu chráněné volby z více kanálů. Místo toho zpracovává zprávy v pořadí příjezdu a podle zákonů pro herce systémy, stop
zpráva dorazí zaručeně.
Livelock při získávání z více kanálů
Zvažte následující program napsaný v CSP [Hoare 1978]:
[Bidder1 :: b: bid; * [Nabídky1? B → proces1! B; [] Nabídky2? B → proces1! B;] || Bidder2 :: b: nabídka; * [Nabídky1? B → proces2! B; [] Nabídky2? B → proces2! B;]]
Jak zdůrazňuje Knabe [1992], problém s výše uvedeným protokolem (Jednoduchý distribuovaný protokol ) je tento proces Uchazeč2
možná nikdy nepřijme nabídku od Nabídka1
nebo Nabídka2
(jev zvaný živý zámek ) a následně proces2
nemusí být nikdy nic zasláno. Při každém pokusu o přijetí zprávy Uchazeč2
je zmařeno, protože nabídka, kterou nabídl Nabídky1
nebo Nabídky2
je popadl pryč Uchazeč
protože se ukázalo, že Uchazeč
má mnohem rychlejší přístup než Uchazeč2
na Nabídky1
a Nabídky2
. Tudíž, Uchazeč
může přijmout nabídku, zpracovat ji a přijmout další nabídku dříve Uchazeč2
se může zavázat k přijetí nabídky.
Účinnost
Jak zdůrazňuje Knabe [1992], problém s výše uvedeným protokolem (Jednoduchý distribuovaný protokol ) je velký počet komunikací, které je třeba odeslat, aby bylo možné provést handshaking, aby bylo možné odeslat zprávu přes synchronní kanál. Ve skutečnosti, jak je uvedeno v předchozí části (Livelock ), počet komunikací může být neomezený.
Shrnutí problémů
Výše uvedené podsekce formulovaly následující tři problémy týkající se použití synchronních kanálů pro procesní výpočty:
- Hladovění. Použití synchronních kanálů může způsobit hladovění, když se proces pokusí získat zprávy z více kanálů pomocí příkazu chráněné volby.
- Livelock. Použití synchronních kanálů může způsobit, že se proces zachytí v živém zámku, když se pokusí získat zprávy z více kanálů v příkazu chráněného výběru.
- Účinnost. Použití synchronních kanálů může vyžadovat velké množství komunikací, aby bylo možné přijímat zprávy z více kanálů pomocí příkazu chráněné volby.
Je pozoruhodné, že ve všech výše uvedených případech vznikají problémy z použití příkazu hlídané volby k získávání zpráv z více kanálů.
Asynchronní kanály
Asynchronní kanály mají tu vlastnost, že odesílatel vkládající zprávu do kanálu nemusí čekat, až příjemce přijme zprávu z kanálu.
Jednoduché asynchronní kanály
Asynchronní kanál může modelovat herec, který přijímá dát
a dostat
komunikace. Následuje chování herce pro jednoduchý asynchronní kanál:
- Každý
dát
komunikace má zprávu a adresu, na kterou je okamžitě zasláno potvrzení (bez čekání na obdržení zprávy adostat
sdělení). - Každý
dostat
komunikace má adresu, na kterou je zaslaná zpráva odeslána.
Asynchronní kanály v procesních kalkulích
Programovací jazyk Join-calculus (publikovaný v roce 1996) implementoval lokální a distribuované souběžné výpočty. Zahrnovalo asynchronní kanály i druh synchronního kanálu, který se používá pro volání procedur. Agha's Aπ Actor calculus (Agha a Thati 2004 ) je založen na zadané verzi asynchronní π-počet.
Algebry
Použití algebraických technik bylo propagováno v procesních kalkulích. Následně bylo vyvinuto několik různých procesních kalkulů určených k poskytování algebraických úvah o aktorových systémech (Gaspari a Zavattaro 1997 ), (Gaspari a Zavattaro 1999 ), (Agha a Thati 2004 ).
Denotační sémantika
Will Clinger (navazující na práci Irene Greif [1975], Gordon Plotkin [1976], Henry Baker [1978], Michael Smyth [1978] a Francez, Hoare, Lehmann a de Roever [1979]) zveřejnili první uspokojivou matematiku denotační teorie Herecký model použitím teorie domény v jeho disertační práce v roce 1981. Jeho sémantika kontrastovala s neomezený nedeterminismus z Herecký model s omezeným nedeterminismem CSP [Hoare 1978] a souběžné procesy [Milne a Milner 1979] (viz denotační sémantika ). Roscoe [2005] vyvinul denotační sémantiku s neomezeným nedeterminismem pro následující verzi Communicating Sequential Processes Hoare [1985]. Poslední dobou Carl Hewitt [2006b] vyvinul pro herce denotační sémantiku založenou na časované diagramy.
Ugo Montanari a Carolyn Talcott [1998] přispěli k pokusu o smíření aktérů s procesními kalkulemi.
Reference
- Carl Hewitt, Peter Bishop a Richard Steiger. Formalismus univerzálního modulárního herce pro umělou inteligenci IJCAI 1973.
- Robin Milner. Procesy: Matematický model výpočetních agentů v Logic Colloquium 1973.
- Irene Greif a Carl Hewitt. Herecká sémantika PLANNERU-73 Záznam konference ze sympozia ACM o zásadách programovacích jazyků. Leden 1975.
- Irene Greif. Sémantika komunikace paralelních profesí Disertační práce MIT EECS. Srpna 1975.
- Gordon Plotkin. Konstrukce powerdomény SIAM Journal on Computing září 1976.
- Carl Hewitt a Henry Baker Herci a spojité funkce Pokračování pracovní konference IFIP o formálním popisu koncepcí programování. 1. - 5. srpna 1977.
- Gilles Kahn a David MacQueen. Koordinace a sítě paralelních procesů IFIP. 1977
- Aki Yonezawa Specifikace a ověřovací techniky pro paralelní programy založené na sémantice předávání zpráv Disertační práce MIT EECS. Prosince 1977.
- Michael Smyth. Mocné domény Journal of Computer and System Sciences. 1978.
- George Milne a Robin Milner. Souběžné procesy a jejich syntaxe JACM. Duben 1979.
- CAR Hoare. Komunikace postupných procesů CACM. Srpna 1978.
- Nissim Francez, AUTO. Hoare, Daniel Lehmann a Willem de Roever. Sémantika nedetermiismu, souběžnosti a komunikace Journal of Computer and System Sciences. Prosinec 1979.
- Mathew Hennessy a Robin Milner. O pozorování nedeterminismu a souběžnosti LNCS 85. 1980.
- Will Clinger. Základy herecké sémantiky Doktorská disertační práce z matematiky MIT. Červen 1981.
- Mathew Hennessy. Termínový model pro synchronní procesy Katedra počítačů Edinburgh University. CSR-77-81. 1981.
- J.A. Bergstra a J.W. Klop. Procesní algebra pro synchronní komunikaci Informace a kontrola. 1984.
- Luca Cardelli. Model implementace setkávací komunikace Seminář o souběžnosti. Přednášky z informatiky 197. Springer-Verlag. 1985
- Robert van Glabbeek. Omezený nedeterminismus a princip aproximace indukce v procesní algebře Sympózium o teoretických aspektech počítačových věd na STACS 1987.
- K. Mani Chandy a Jayadev Misra. Návrh paralelního programu: Nadace Addison-Wesley 1988.
- Robin Milner, Joachim Parrow a David Walker. Počet mobilních procesů Oddělení informatiky v Edinburghu. Hlášení ECS-LFCS-89-85 a ECS-LFCS-89-86. Červen 1989. Revidováno září 1990, respektive říjen 1990.
- Robin Milner. Polyadic pi-Calculus: Tutorial Edinburgh University. Zpráva LFCS ECS-LFCS-91-180. 1991.
- Kohei Honda a Mario Tokoro. Objektový počet pro asynchronní komunikaci ECOOP 91.
- José Meseguer. Logika podmíněného přepisování jako jednotný model souběžnosti in Selected papers of the Second Workshop on Concurrency and compositionality. 1992.
- Frederick Knabe. Distribuovaný protokol pro komunikaci založenou na kanálech s výběrem PARLE 1992.
- Geoff Barrett. Referenční příručka Occam 3 INMOS. 1992.
- Benjamin Pierce, Didier Rémy a David Turner. Typový programovací jazyk vyššího řádu založený na kalkulu pi Workshop o teorii typů a její aplikaci na počítačové systémy. Kjótská univerzita. Červenec 1993.
- Milner, Robin (Leden 1993), „Elements of interaction: Turing award lecture“, Komunikace ACM, CACM, 36: 78–89, doi:10.1145/151233.151240.
- R. Amadio a S. Prasad. Místa a selhání Konference o základech softwarové technologie a teoretické informatice. 1994.
- Cédric Fournet a Georges Gonthier. Reflexní chemický abstraktní stroj a spojovací kalkul POPL 1996.
- Cédric Fournet, Georges Gonthier, Jean-Jacques Lévy, Luc Maranget a Didier Rémy. Počet mobilních agentů CONCUR 1996.
- Tatsurou Sekiguchi a Akinori Yonezawa. Kalkul s mobilitou kódu FMOODS 1997.
- Gaspari, Mauro; Zavattaro, Gianluigi (květen 1997), Algebra aktérů (Technická zpráva), Boloňská univerzita
- Luca Cardelli a Andrew Gordon (1998), Maurice Nivat (ed.), „Mobile Ambients“, Základy softwarové vědy a výpočetní struktury, Přednášky z informatiky, Springer, 1378
- Ugo Montanari a Carolyn Talcott. Mohou herci a agenti Pi žít společně? Elektronické poznámky v teoretické informatice. 1998.
- Robin Milner. Komunikační a mobilní systémy: Pi-kalkul Cambridge University Press. 1999.
- M. Gaspari a G. Zavattaro (1999), „Algebra aktérů“, Formální metody pro systémy založené na otevřených objektech: 3–18, doi:10.1007/978-0-387-35562-7_2, ISBN 978-1-4757-5266-3
- Davide Sangiorgi a David Walker. Pi-kalkul: Teorie mobilních procesů Cambridge University Press. 2001.
- P. Thati, R. Ziaei a G. Agha. Teorie testování května pro asynchronní kameny s lokalitou a bez shody názvu Algebraická metodologie a softwarová technologie. Springer Verlag. Září 2002. LNCS 2422.
- Gul Agha a Prasanna Thati (2004), „Algebraická teorie herců a její aplikace na jednoduchý objektově založený jazyk“ (PDF), OO na FM (Dahl Festschrift) LNCS, Springer-Verlag, 2635, archivovány z originál (PDF) dne 2004-04-20, vyvoláno 2005-12-15
- J.C.M. Baeten, T. Basten a M.A. Reniers. Algebra komunikačních procesů Cambridge University Press. 2005.
- He Jifeng a C.A.R. Hoare. Propojení teorií souběžnosti Zpráva OSN UNU-IIST č. 328. University Institute of International Technology for Software Technology. Červenec 2005.
- Luca Aceto a Andrew D. Gordon (redaktoři). Algebraické výpočty procesů: Prvních dvacet pět let a dále Zpracovat algebru. Bertinoro, Forl`ı, Itálie, 1. – 5. Srpna 2005.
- Roscoe, A. W. (2005), Teorie a praxe souběžnosti, Prentice Hall, ISBN 978-0-13-674409-2
- Carl Hewitt (2006b) Co je to závazek? Fyzické, organizační a sociální COIN @ AAMAS. 2006.