Join minta

A join minta egy konkurrens (párhuzamos, elosztott) programtervezési minta, aminek lényege, hogy a szálak üzenetátadással kommunikálnak. A zárolással szemben magas szintű programozási modell, ami kommunikációs szerkezetmodellt használ, hogy elvonatkoztasson a környezet bonyolultságától, és lehetővé tegye a skálázást. Az üzenetek elfogyasztását atominak tekinti, még akkor is, ha több csatornán érkeztek az üzenetek.

Ez a minta a join-kalkuluson alapul, és mintaillesztést használ. Konkrétan ezt azzal valósítja meg, hogy lehetővé teszi függvények join definícióját, és/vagy csatornákat, amelyek konkurrens hívásra illeszkednek, továbbá üzenetminták is definiálhatók. Konkurrens programtervezési minták mintája (metaminta), mivel egyszerűbbé és hatékonyabbá teszi ezeknek az entitásoknak a kommunikációt és a többszálú programozási paradigma használatát.

Leírása

A join-minta egy magasabb csővezeték, szinkronizációval és mintaillesztéssel. Angolul chordnak is nevezik. Valójában a fogalom összegezhető illesztéssel és csatlakozással néhány üzenetre, amelyek különböző üzenetsorokból származnak, majd egyetlen kezelővel egyszerre kezeli őket. Az első elvárt kommunikációs lépés jelezhető a when kulcsszóval, a felcsatlakozás és párosítás and kulcsszóval, és a különféle feladatok futtatása a do kulcsszóval. A join minta tipikus formája:

j.When(a1).And(a2). ... .And(an).Do(d)

A When(a1) első argumentuma lehet szinkron vagy aszinkron csatorna, de lehet csatornák tömbje is. Minden további argumentumnak aszinkron csatornának kell lennie.

Pontosabban, ha egy üzenet illeszkedik minták egy összekapcsolt sorozatára, akkor elindul a kezelője egy új szálban, ha aszinkron kontextusban van, különben az üzenetnek várnia kell addig, amíg nem illeszkedik egy minta az ő valamelyik mintájára. Ha több illeszkedés van, akkor nem specifikált, hogy melyik minta választódik ki. Egy eseménykezelővel szemben, ami egy időben egyszerre több alternatív esemény egyikét szolgálja ki, a join minta csatornák konjunkciójára vár, és verseng a végrehajtásért minden más megengedett mintával.

Folyamatdiagram a join minta végrehajtásáról; általános illesztés több üzenetre (wait a chord) és az erőforrások szinkronizálása (szabad vagy zárolva)

A join mintát pi-kalkulusbeli csatornák halmaza definiálja, ami két műveletet definiál, a küldést és a fogadást; emiatt két join kalkulusbeli névre van szükség, egy x csatornanévre és egy x függvénynévre, az érték megszerzéséhez (egy kérés). A join definíció jelentése x() egy hívása, ami visszadja azt az értéket, ami egy x<> csatornán érkezett. Továbbá ha több függvény fut párhuzamosan, kiváltódik a return folyamat, és együtt szinkronizálódik a többi folyamattal.

J ::= //join patterns
| x<y> //message send pattern
| x(y) //function call pattern
| J | JBIS //synchronization

A kliens perspektívájából a csatorna csak deklarál egy metódust, ugyanazzal a névvel és szignatúrával. A kliens üzenetet küld vagy kérést vált ki a metódus hívásával. A folytató metódusnak várnia kell, amíg kérés vagy üzenet érkezett minden csatornán a folytatás When mondatát követően. Ha a folytatás futni kezd, akkor a csatornahívások argumentumai kikerülnek a sorból (elfogyasztódnak), és atomian átadódnak a folytatás paramétereinek. }}

A join minta osztálydiagramja

A legtöbb esetben a szinkron hívások sorrendje nem garantált a jobb teljesítmény érdekében. Az üzeneteket egy másik szál is elfogyaszthatja, így a szálnak lehet, hogy tovább kell várnia egy újabb üzenetre.

Története

π-kalkulus - 1992

A π-kalkulus a folyamatkalkulusok családjába tartozik, aminek segítségével matematikai képletekkel írja le és elemzi a konkurrens számítások sorozatát elnevezett csatornák bevezetésével, így a folyamatok kommunikálhatnak csatornákon keresztül, így leírhatók olyan konkurrens számítások is, amelyek hálózatkonfigurációja dinamikusan, futásidőben változik.

Join kalkulus - 1993

A join minták először Fournet és Gonthier alapvető join kalkulusával jelentek meg, mint aszinkron folyamatalgebra, amit elosztott környezetben hatékony implementációhoz terveztek. A join kalkulus kifejezőképessége megegyezik a π-kalkuluséval. Arra fejlesztették ki, hogy formális megalapozást adjon az elosztott programozási nyelvekhez, így elkerüli a más folyamatkalkulusokban használt kommunikációs szerkezeteket, például a randevúkat.

Elosztott join kalkulus - 1996

A join kalkulus névátadó kalkulus, és egyben magnyelv a konkurrens és elosztott programozáshoz. Az elosztott join kalkulus a join kalkuluson alapul, de az elosztott számításokhoz kibővítve. Mobil ágenseket használ, ahol az ágensek nem egyszerűen programok, hanem futó folyamatok, a saját kommunikációs képességeikkel.

JoCaml, Funnel és Join Java - 2000

A JoCaml és a Funnel funkcionális programozási nyelvek, amelyek támogatják a join minták deklarálását. Közvetlenül valósítják meg a join kalkulust funkcionális programozási nyelvekben.

Egy másik kiterjesztés egy nem szabványos kiterjesztés, a Java, JoinJava, amit Itzstein és Kearney javasolt.

Polyphonic C# - 2002

Cardelli, Benton és Fournet javasolta a C# bővítését join mintával 2002-ben, ez a Polyphonic C#.

Cω - 2003

A Cω a join kalkulus objektumorientált adaptációja. Tartalmazta a Polyphonic C#-ot a Cω (Comega) 2004-es kiadásában.

Scala Joins - 2007

A Scala Joins egy programkönyvtár, ami lehetővé teszi a join minta alkalmazását a Scala nyelvben a kiterjeszthető mintaillesztés kontextusában, hogy a join mintát a létező aktor alapú keretrendszerbe integrálja.

JErlang - 2009

Az Erlang natívan támogatja a konkurrens, valós idejű és elosztott paradigmát. A folyamatok közötti konkurrenciát bonyolult volt megoldani, ezért egy új nyelvet alkottak, a JErlangot, ami a join kalkuluson alapul.

A klasszikus programozási irodalomban

Join mintával egyszerűen kódolhatók egymással kapcsolatban álló konkurrens problémák, mint aktorok és aktív objektumok.

• Gátak

class SymmetricBarrier {
public readonly Synchronous.Channel Arrive;
public SymmetricBarrier(int n) {
    // create j and init channels (elided)
    var pat = j.When(Arrive);
    for (int i = 1; i < n; i++) pat = pat.And(Arrive);
    pat.Do(() => { });
}
}

• Étkező filozófusok

var j = Join.Create();
Synchronous.Channel[] hungry;
Asynchronous.Channel[] chopstick;
j.Init(out hungry, n); j.Init(out chopstick, n);
for (int i = 0; i < n; i++) {
    var left = chopstick[i];
    var right = chopstick[(i+1) % n];
    j.When(hungry[i]).And(left).And(right).Do(() => {
    eat(); left(); right(); // replace chopsticks
    });
}

• Kölcsönös kizárás

class Lock {
public readonly Synchronous.Channel Acquire;
public readonly Asynchronous.Channel Release;
    public Lock() {
        // create j and init channels (elided)
        j.When(Acquire).And(Release).Do(() => { });
        Release(); // initially free
    }
}

• [[Termelő-fogyasztó minta]

class Buffer<T> {
public readonly Asynchronous.Channel<T> Put;
public readonly Synchronous<T>.Channel Get;
    public Buffer() {
        Join j = Join.Create(); // allocate a Join object
        j.Init(out Put);
        // bind its channels
        j.Init(out Get);
        j.When(Get).And(Put).Do // register chord
        (t => { return t; });
    }
}

• Író-olvasó zárolás

class ReaderWriterLock {
private readonly Asynchronous.Channel idle;
private readonly Asynchronous.Channel<int> shared;
public readonly Synchronous.Channel AcqR, AcqW,
RelR, RelW;
public ReaderWriterLock() {
    // create j and init channels (elided)
    j.When(AcqR).And(idle).Do(() => shared(1));
    j.When(AcqR).And(shared).Do(n => shared(n+1));
    j.When(RelR).And(shared).Do(n => {
    if (n == 1) idle(); else shared(n-1);
    });
    j.When(AcqW).And(idle).Do(() => { });
    j.When(RelW).Do(() => idle());
    idle(); // initially free
}
}

• Szemaforok

class Semaphore {
public readonly Synchronous.Channel Acquire;
public readonly Asynchronous.Channel Release;
    public Semaphore(int n) {
        // create j and init channels (elided)
        j.When(Acquire).And(Release).Do(() => { });
        for (; n > 0; n--) Release(); // initially n free
    }
}

Alapfogalmak

• Join kalkulus: A join minta első megvalósításai ezen alapulnak.
• Üzenetátadás: A join minta párhuzamossági okok miatt üzenetátadással működik.
• Csatorna: Csatornák szinkronizálják és adnak át üzeneteket a konkurrensen végrehajtott szálak között. Általában egy csatorna több join mintában is benne van, minden minta egy lehetséges folytatást definiál, ami lefuthat, ha a csatorna meghívódik.
• Szinkron: A join minta használhat szinkron csatornákat, amelyek eredményt adnak vissza. A szinkron minta folytatása a szinkron hívó szálában fut.
• Aszinkron: Az aszinkron csatornának nincs visszatérési értéke, de argumentumai lehetnek. Folytatása egy új szálban fut. A join minta teljesen aszinkron lehet, folytatását szubrutinban nyújtja, és When mondata csak aszinkron csatornákat tartalmaz.
• Szinkron és aszinkron: A szinkron és aszinkron bufferek kombinációja egy olyan modult eredményez, ami kétféle fogyasztót támogat.
• Ütemező: a join mintákat ütemezni kell, kell egy ütemező, ami ezt megoldja.
• Progamtervezési minták: a join minta konkurrens viselkedési programtervezési minta.
• Konkurrens programozás: Konkurrensen hajtódik végre.
• Mintaillesztés: a join minta illeszkedő feladatokkal működik.
• Párhuzamos programozás: párhuzamosan hajtódnak végre a feladatok.
• Elosztott programozás: a join mintával felosztott feladatokat különböző ágensek hajthatják végre különböző környezetekben.
• Tranzakcionális memória: alkalmas a join minta kommunikációjának megvalósítására.
• Átfedés: a join minta számára nem probléma a különböző join minták közötti átfedés, egy csatornára több join minta is hivatkozhat.

Alkalmazások

Mobil ágenesek

A mobil ágensek autonóm programágensek társas készségekkel, kommunikációs lehetőségekkel és mozgási lehetőségekkel. A program és adatai mozoghatnak különféle gépek között futás közben.

A mobil ágensek használhatók arra, hogy összekapcsolják a konkurrens és az elosztott programozást join kalkulussal. Ezért megalkották az elosztott join kalkulus fogalmát, ami helyekkel és primitívekkel bővíti a join kalkulust a mobilitás leírására. Így az ágenseknek van fogalmuk a lokációról, ami az ágens fizikai helyét jelenti. Az ágens atomi jelleggel mozoghat a különböző helyek között.

Egy ágens folyamata funkcionalitásainak halmazaként definiálható, amibe beletartozik az aszinkron üzenetátadás, és a vándorlás. A mozgás könnyebb reprezentációja érdekében a helyeket fába szervezik. Ezzel a hibázás is egyszerűbben modellezhető. Ha egy helyen összeomlik a program, akkor minden alatta levő helyen is összeomlik. Egy meghatározott helyű hiba bármely futási helyről megtalálható, ez segít kijavítani a hibát.

Így a join kalkulus egy elosztott nyelv magja. Operációs szemantikája egyszerűen implementálható egy elosztott rendszerben, ami a hiba lehetőségét is tartalmazza. Így a join kalkulus elsőrangú objektumokként kezeli a csatornákat és a helyeket. Egy hely ismeri más helyek nevét, ezért onnan oda lehet lépni. Ez biztos alapot teremt a statikus elemzésnek és a biztonságos mozgásnak. Teljes az elosztott helyek kifejezésében. Ha nincs hiba, akkor a végrehajtás független a helyektől. Ez az átláthatóság fontos a mobil ágensek tervezésében, és nagyon hasznos tulajdonságaik ellenőrzéséhez.

2007-ben kiadták az alap join kalkulus egy proaktív ágenseket kezelő kiegészítését. Az ágensek megfigyelhetik közös környezetüket. Ehhez a közös környezethez változók adhatók az ágensekkel, például egy névszolgáltató, ami segít megtalálni más ágenseket.

Szerkesztés, fordítás

A join nyelvek join kalkulusra, mint magnyelvre épülnek. Ezért a kalkulust aszinkron folyamatokkal elemzik, és a join minták modellt adnak az eredmény szinkronizálására.
Ehhez két fordító szükséges:

• Join fordító: a join nyelv számára készített fordító. Ezt csak a join kalkulus számára hozták létre.
• Jocaml fordító: Az Objectif Caml egy kiterjesztésének fordítója, ami a join kalkulust használja.

Ez a két fordító ugyanazon a rendszeren, egy automatán működik.

let A(n) | B() = P(n)
and A(n) | C() = Q(n)
;;

Ez egy üzenet fogyasztását reprezentálja, ami a kiegészített join modellbe érkezik. Minden állapot egy lehetőség a kód végrehajtására, és minden átmenet üzenet fogadása két állapot között. Ha minden üzenet meg van ragadva, akkor a fordító végrehajtja a join kód törzsét, a teljes join modellnek megfelelően.

Így a join kalkulusban az alapértékek nevek, mint például A, B vagy C. Így a két fordító kétféleképpen reprezentálja az eredményeket. A join fordító egy kétdimenziós vektort használ, az első a név, a második pedig a fogadott üzenetek listája. A Jocaml a neveket pointerként használja, ami a definícióra mutat. Ezek további nevek pointerét tartalmazzák állapot mezővel, és illeszkedő adatszerkezetet üzenetekkel. Az alapvető különbség az, hogy ha az őrző folyamat végrehajtódik, akkor először az üzenetben szereplő összes nevet ellenőrzi, hogy készen állnak-e a futásra, míg a második csak egy változót és hozzáférést a többihez ahhoz, hogy tudja, a modell teljes.

Jelenlegi kutatások szerint a fordítási séma kétlépéses: irányításból és továbbításból áll. Az irányító tervezése és korrektsége lénygében a mintaillesztés elméletén múlik, míg egy belső irányítási lépés beszúrása a kommunikációba természetes ötlet, ami intuitívan nem változtatja meg a folyamat működését. Megfigyelték, hogy nem érdemes ennek ellenőrzése érdekében felügyelő objektumokat futás idejű szinten beiktatni, mivel ez jelentősen bonyolultabbá teszi az üzenetsorok kezelését, mivel végig kellene őket szkennelni a mintaillesztés és az üzenet elfogyasztása előtt.