Linda (koordinační jazyk) - Linda (coordination language)

v počítačová věda, Linda je model koordinace a komunikace mezi několika paralelními procesy fungujícími na objektech uložených a získávaných ze sdílené, virtuální, asociativní paměti.^[1] Byl vyvinut společností Sudhir Ahuja na AT&T Bell Laboratories ve spolupráci s David Gelernter a Nicholas Carriero na univerzita Yale v roce 1986.^[1]^[2]

Modelka

Tento model je implementován jako „koordinační jazyk“, ve kterém je do sekvenčního jazyka, jako je C, přidáno několik primitiv pracujících na seřazené posloupnosti typovaných datových objektů „n-tice“ a logicky globální asociativní paměť, nazvaný a tuplespace, ve kterém procesy ukládají a načítají n-tice.

Původní model Linda vyžaduje čtyři operace, které jednotliví pracovníci provádějí na n-tice a n-tice:

v atomicky čte a odstraňuje n-tici z n-tice
rd nedestruktivně čte tuplespace
ven vytvoří n-tici a zapíše ji do tuplespace (n-tice může být duplikována v tuplespace)
eval vytváří nové procesy pro vyhodnocení n-tic, zápis výsledku do tuplespace

Linda-kalkul

Linda-kalkul je formalizace výše uvedeného modelu s tím rozdílem, že v následujícím ${ displaystyle mathrm {vnější}}$ zahrnuje oba ven a eval operace. Prezentace kalkulu je založena na Cridlig et al.^[3]

Syntax

Vybereme konkrétní zastoupení n-tic. Předpokládáme, že máme sadu n-tic ${ displaystyle t in { mathcal {T}}}$ a je nám dovoleno vytvořit a použít substituční funkci ${ displaystyle sigma}$ na n-tice nahrazující proměnné výrazy, které dávají n-tici. Například máme n-tici ${ displaystyle t = ({ mathit {ahoj}}, x)}$ , poté použijte střídání ${ displaystyle sigma = {{ mathit {svět}} / x }}$ na ${ displaystyle t}$ výnosy ${ displaystyle ({ mathit {ahoj}}, { mathit {svět}})}$

Procesy Linda-kalkulu jsou definovány následující gramatikou.

${ displaystyle P, Q :: = t ; | ; mathrm {outeval} (P) .Q ; | ; mathrm {rd} (t) .P ; | ; mathrm {in} (t) .P ; | ; P + Q ; | ; mathbf {rec} XP ; | ; X}$

Syntaxe zahrnuje následující operace Lindy, nedeterministický výběr a rekurzi. Funkce substituce je rozšířena na procesy rekurzivně.

Sémantika

Prostor n-tice je reprezentován jako a multiset procesů. Píšeme ${ displaystyle M , | , P}$ pro ${ displaystyle M cup {P }}$ kde ${ displaystyle M}$ je multiset, ${ displaystyle {P }}$ singleton multiset a ${ displaystyle cup}$ je operace multiset unie. Sémantika je pak definována jako a redukční vztah v multisetu ${ displaystyle M rightarrow M '}$ jak následuje.

${ displaystyle { begin {array} {lrcll} { text {(outeval)}} & M , | , mathrm {outeval} (P) .Q & rightarrow & M , | , P , | , Q & { text {(čtení)}} & M , | , mathrm {rd} (t). P , | , t '& rightarrow & M , | , P sigma , | , t '& { text {pokud existuje}} sigma { text {takový, že}} t sigma = t' { text {(vstup)}} & M , | , mathrm { in} (t) .P , | , t '& rightarrow & M , | , P sigma & { text {pokud existuje}} sigma { text {takový, že}} t sigma = t ' { text {(levá volba)}} & M , | , P + Q & rightarrow & M , | , P & { text {(správná volba)}} & M , | , P + Q & rightarrow & M , | , Q & { text {(rekurze)}} & M , | , mathbf {rec} X.P & rightarrow & M , | , P { mathbf { rec} XP / X } a end {pole}}}$

Všimněte si, že (vstup) spotřebovává n-tici ${ displaystyle t '}$ z prostoru n-tice, zatímco (čtení) ji pouze čte. Výsledná provozní sémantika je synchronní.

Hodnocení

Ve srovnání s jinými modely s paralelním zpracováním je Linda více ortogonální při zacházení s koordinací procesů jako s oddělenou aktivitou od výpočtu, a obecněji je možné subsumovat různé úrovně souběžnosti - jednoprocesorový, vícevláknový víceprocesorový nebo síťový - pod jeden model. Jeho ortogonalita umožňuje procesům výpočetním v různých jazycích a platformách spolupracovat pomocí stejných primitiv. Jeho obecnost umožňuje distribuci vícevláknového systému Linda na více počítačů beze změny.

Vzhledem k tomu, že modely pro předávání zpráv vyžadují těsně spojené procesy, které si navzájem posílají zprávy v nějaké sekvenci nebo protokolu, procesy Linda jsou odděleny od ostatních procesů a komunikují pouze prostřednictvím tuplespace; proces nemusí mít žádnou představu o jiných procesech kromě druhů n-tic spotřebovaných nebo vyrobených (datová vazba).

Vědci navrhli více primitiv na podporu různých typů komunikace a koordinace mezi (otevřenými distribuovanými) počítačovými systémy a řešení konkrétních problémů vyplývajících z různých použití modelu.^{[Citace je zapotřebí ]} Vědci také experimentovali s různými způsoby implementace virtuální sdílené paměti pro tento model.^{[Citace je zapotřebí ]} Mnoho z těchto vědců navrhlo větší úpravy původního modelu Linda a vyvinulo rodinu systémů známých jako Systémy podobné Lindě a implementováno jako ortogonální technologie (na rozdíl od původní verze). Příkladem toho je jazyk Ulehčit navrhl Steven Ericsson-Zenith.

Implementace

Linda byla původně implementována v C a Fortran, ale od té doby byl implementován v mnoha programovacích jazycích, včetně:

C: C-Linda, TCP-Linda, LinuxTuples
C ++: CppLinda, Boreas
C#: pProstory
Erlang: Erlinda
Jít: pProstory
Jáva: Prostory Java, jRESP, TSpaces, LightTS, LIMETKA, pProstory
JavaScript: pProstory
Lisp
Lua: LuaTS Lua Lanes
Prolog: SICStus Prolog Linda
Krajta: PyLinda
Rubín: Rindo
Rychlý: pProstory

Mezi nejvýznamnější implementace Lindy patří:

C-Linda nebo TCP-Linda - nejstarší komerční a rozšířená implementace virtuální sdílené paměti pro superpočítače a klastrované systémy od společnosti Scientific Computing Associates, kterou založil Martin Schultz.
Prostory Java - implementace tuplespace založená na Javě, která pomohla popularizovat distribuované výpočty.
TSpaces - platforma tuplespace založená na Javě od IBM.^{[nepřiměřená váha? – diskutovat]}

Kritiky

Kritika Lindy z multiprocesorové komunity se obvykle zaměřuje na sníženou rychlost operací v systémech Linda ve srovnání s Rozhraní pro předávání zpráv (MPI) systémy.^{[Citace je zapotřebí ]} I když to nebylo neopodstatněné, byla tato tvrzení do značné míry vyvrácena kvůli důležité třídě problémů.^[4] Podrobnou kritiku modelu Linda lze najít také v knize Stevena Ericssona-Zenitha Procesní modely interakce.^[5]

název

Linda je pojmenována po Linda Lovelace, herečka v pornografickém filmu Hluboké hrdlo, slovní hříčka Ada je poctou Ada Lovelace.^[6]

Publikace

Gelernter, David; Carriero, Nicholas (1992). "Koordinační jazyky a jejich význam". Komunikace ACM. 35 (2): 97–107. doi:10.1145/129630.129635. S2CID 7748555.
Carriero, Nicholas; Gelernter, David; Mattson, Timothy; Sherman, Andrew (1994). „Alternativa Linda k systémům předávání zpráv“. Parallel Computing. 20 (4): 633–655. doi:10.1016/0167-8191(94)90032-9.
Wellsi, Georgi. „Koordinační jazyky: s Lindou zpět do budoucnosti“ (PDF). Rhodosská univerzita. Archivovány od originál (PDF) dne 19. 12. 2009.
Sluga, Thomas Arkadius. "Moderní C ++ implementace koordinačního jazyka LINDA". University of Hannover. Chybějící nebo prázdný | url = (Pomoc)

Viz také

Reference

^ ^A ^b Ahuja, Sudhir (AT&T Bell Laboratories); Carriero, Nicholas; Gelernter, David (srpen 1986), „Linda a přátelé“, Počítač, IEEE, 19b (8): 26–34, doi:10,1109 / mc.1986.1663305, S2CID 5155678
^ Carriero, Nicholas; Gelernter, David (01.01.1985). "S / Net's Linda Kernel (Extended Abstract)". Sborník z desátého sympózia ACM o zásadách operačních systémů. SOSP '85. New York, NY, USA: ACM: 160–. doi:10.1145/323647.323643. ISBN 978-0897911740. S2CID 6922183.
^ Cridlig, Régis; Goubault, Eric (1993). "Sémantika a analýza lindských jazyků". Lecture Notes in Computer Science, vol 724. Springer, Berlín, Heidelberg. doi:10.1007/3-540-57264-3_30. ISBN 978-3-540-57264-0.
^ Carriero; et al. (1. dubna 1994). „Linda Alternativa k systémům předávání zpráv“. Parallel Computing. 2 (4): 633–655. doi:10.1016/0167-8191(94)90032-9.
^ Ericsson-Zenith (1992). Procesní modely interakce. Pařížská univerzita.
^ Markoff, John (19. ledna 1992). „Románek Davida Gelerntera s Lindou“. The New York Times.

externí odkazy

Koordinační jazyk - Malá diskuse o rozdílech mezi přístupem Lindy a přístupem Lindy Programování založené na toku
Linda pro C ++
Linda pro C.
Erlinda (pro Erlang)
PyLinda (pro Python)
Rinda (pro Ruby)
Linda v mobilním prostředí (LIME) (pro nesC)

[:0-1] A ^b Ahuja, Sudhir (AT&T Bell Laboratories); Carriero, Nicholas; Gelernter, David (srpen 1986), „Linda a přátelé“, Počítač, IEEE, 19b (8): 26–34, doi:10,1109 / mc.1986.1663305, S2CID 5155678

[2] Carriero, Nicholas; Gelernter, David (01.01.1985). "S / Net's Linda Kernel (Extended Abstract)". Sborník z desátého sympózia ACM o zásadách operačních systémů. SOSP '85. New York, NY, USA: ACM: 160–. doi:10.1145/323647.323643. ISBN 978-0897911740. S2CID 6922183.

[3] Cridlig, Régis; Goubault, Eric (1993). "Sémantika a analýza lindských jazyků". Lecture Notes in Computer Science, vol 724. Springer, Berlín, Heidelberg. doi:10.1007/3-540-57264-3_30. ISBN 978-3-540-57264-0.

[4] Carriero; et al. (1. dubna 1994). „Linda Alternativa k systémům předávání zpráv“. Parallel Computing. 2 (4): 633–655. doi:10.1016/0167-8191(94)90032-9.

[process-5] Ericsson-Zenith (1992). Procesní modely interakce. Pařížská univerzita.

[deeep-throat-6] Markoff, John (19. ledna 1992). „Románek Davida Gelerntera s Lindou“. The New York Times.

[1]

[2]

[3]

[4]

[5]

[6]