5. Előadás - Aszinkron végrehajtási modellek

A korábbiakban láthattuk, hogy

több szál kezelése esetében tipikusan nem lesz determinisztikus a programok végrehajtása.
Versenyhelyzetek (race condition) alakulhatnak ki, amelyek megoldásához szinkronizációs módszereket használhatunk.
A lock-ok használata deadlock-hoz vezethet.
Nehezen reprodukálható hibák keletkezhetnek.
A szoftver megbízhatósága igen fontos szempont, ami így nehezen garantálható.

Processzek közötti kommunikáció, CSP

CSP - Communicating Sequential Processes
Matematikai modell, Folyamat algebra
A folyamat itt általános (implementációtól független) fogalom.
Nem használ osztott memóriát.

Csatorna

A folyamatok közötti kommunikáció oldható meg a segítségével.
Nevesített csatornák vannak, amelyre fel lehet iratkozni, lehet rajta üzeneteket közzétenni. (Publish-Subscribe model)
Megvalósítható egy-több és több-egy kapcsolat is.
A kommunikáció résztvevői nem tudnak egymásról. (Nincs a folyamatoknak egyedi címe, dedikált címzett.)

Egy-több kapcsolat:

Több-egy kapcsolat:

Csatornák használata Go-ban

package main

import "fmt"

func main() {

    c := make(chan string)

    go func() {
        c <- "value"
    }()

    result := <-c
    fmt.Println(result)
}

Bufferelt csatorna:

package main

import "fmt"

func main() {

    c := make(chan string, 3)

    c <- "first"
    c <- "second"
    c <- "third"

    fmt.Println(<-c)
    fmt.Println(<-c)
    fmt.Println(<-c)
}

Szinkronizáció csatornák segítségével:

package main

import (
    "fmt"
    "time"
)

func worker1(done chan bool) {
    fmt.Print("Worker 1 ...")
    done <- true
}

func worker2(done chan bool) {
    fmt.Print("Worker 2 ...")
    done <- true
}

func main() {

    done := make(chan bool)

    go worker1(done)
    go worker2(done)

    <-done
    <-done
}

forrás:

Aktor modell

Az aktorok jellemzői

Az aktorra úgy tekinthetünk, hogy az perzisztens módon létezik.
Van belső állapota, amely el van szigetelve a külvilágtól.

Az aktorok műveletei

Létre tud hozni egy új aktort.
Üzenetet tud küldeni egy másik aktornak.
Üzenetet tud fogadni egy másik aktortól.

Az üzenet feldolgozása során megváltozhat az aktor belső állapota, abban mellékhatásokat fejthet ki.

Az üzenetküldés sajátosságai

Minden aktornak van egy egyedi címe.
Minden folyamat egyszerre csak egy üzenetet kézbesít.
A modellben nincs kitüntetett szerepe az időnek. Az aktor csak azzal foglalkozik, hogy hogyan dolgozza fel a beérkező üzeneteket, azok hatására milyen üzeneteket küldjön.
Az üzenetek kézbesítésére vonatkozóan nincs időkorlát, időtúllépés.
Az üzenetek kézbesítési sorrendjére nincsen garancia.
Az aktorok címeit a létrehozásukkor, vagy a kapott üzenetekből lehet megtudni.
Az elküldött üzenetek immutable adatnak tekinthetők.

Postaládák

Mailbox, Message Queue
Minden aktor számára a modell biztosít egy postaládát.
Ez tulajdonképpen egy üzenetsornak tekinthető (queue, FIFO).

Supervision

Az aktorok más aktorokat felügyelhetnek.
A supervisor aktor tudja ellenőrízni, hogy a felügyelt aktor helyesen működik-e. Szükség esetén újra tudja indítani.
Az aktorok ilyen módon fa struktúrába szervezhetők.

A modell előnyei

Egyszerűen skálázható
Hibatűrő, jól kezeli a hibákat (fault tolerant)
Nem kezel megosztott állapotokat.

A modell hátrányai

A modell nem garantálja azt, hogy ne tudjanak kialakulni deadlock-ok.
Az aktorokhoz tartozó mailbox-ok mérete véges, azok túlcsordulhatnak.
Sok implementációtól függő elemet tartalmaz.

Az MPI szabvány

MPI: Message Passing Interface
Egy kommunikációs protokoll párhuzamos gépek számára.
Alapvetően C, C++ és Fortran programokhoz, de már más nyelvekhez is elérhető.
HPC: High Performance Computing

Főverziók

MPI-1.1, 1992
MPI-2.0, 1997
MPI-3.0, 2012
MPI-4.0, 2021

Kommunikáció a processzek között

Az MPI-vel a processzeket csoportokba szervezhetjük.
Ezek között a kommunikációt egy Communicator végzi.
Segíti a pont-pont kommunikációt és a több processz közötti kommunikációt is.
Blokkoló és nem blokkoló üzenetátadást is alkalmaz.

Adattípusai

MPI_BYTE
MPI_SHORT
MPI_INT
MPI_LONG
MPI_FLOAT
MPI_DOUBLE

Megvannak ezek UNSIGNED változatai is.

Saját (összetett) típusok definiálására is lehetőséget ad.

Open MPI

Az MPI egy nyílt forráskódú implementációja.
Nem csak egy függvénykönyvtár. Az Open MPI-vel készített programok futtatásához külön eszközök szükségesek.

A program fordítása:

gcc hello.c -o hello -l mpi

A program futtatása:

mpirun hello

Parancssori argumentumként megadhatjuk a processzek számát:

mpirun -np 2 master_slave

A C függvénykönyvtár használata

MPI inicializálása:

MPI_Init(&argc, &argv);

Az inicializálást minden, a kommunikációban résztvevő processznek el kell végeznie.
A paraméterek a main függvényben megadott parancssori argumentumok tipikusan.

A kommunikációs közegből való kilépést explicit módon jelezni kell:

MPI_Finalize();

Minden processzhez tartozik egy rang (rank):

int rank;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);

Ennek a funkciója gyakorlatilag megegyezik a PID és TID szerepével.

A kommunikációban résztvevő processzek számának lekérdezése:

int n_tasks;
MPI_Comm_size(MPI_COMM_WORLD, &n_tasks);

Pont-pont kommunikációval, blokkoló üzenetet küldeni az MPI_Send függvénnyel lehet:

MPI_Send(
    void* data,
    int count,
    MPI_Datatype datatype,
    int destination,
    int tag,
    MPI_Comm communicator
);

Üzenetet fogadni az MPI_Recv függvénnyel lehet:

MPI_Recv(
    void* data,
    int count,
    MPI_Datatype datatype,
    int source,
    int tag,
    MPI_Comm communicator,
    MPI_Status* status
);

Broadcast üzenetet küldeni az MPI_Bcast függvénnyel lehet:

MPI_Bcast(
    void* data,
    int count,
    MPI_Datatype datatype,
    int root,
    MPI_Comm communicator
);

A redukció jellegű műveletekhez használhatjuk az MPI_Reduce függvényt:

MPI_Reduce(
    void* send_data,
    void* recv_data,
    int count,
    MPI_Datatype datatype,
    MPI_Op op,
    int root,
    MPI_Comm communicator
);

A redukciós operátor (op) lehet például:

MPI_SUM
MPI_PROD
MPI_MIN
MPI_MAX

forrás:

https://mpitutorial.com

Kérdések

CSP

A CSP modell esetében hogyan kommunikálnak egymással a folyamatok?
Milyen előnyei és hátrányai vannak a CSP modellnek?

Aktor modell

Milyen műveletei vannak az aktoroknak?
Egy aktor honnan tudhatja egy másik aktor címét?
Milyen előnyei és hátrányai vannak az aktor modellnek?

MPI szabvány

Milyen problémát old meg az MPI szabvány?
Miért definiál saját típusokat a függvénykönyvtára?
Milyen kommunikációs módokat támogat az MPI szabvány?

Feladatok

Szálbiztos tárolók implementálása

Implementálja a (dinamikus) tömb (Array), a láncolt lista (List), a sor (Queue) és a verem (Stack) adatstruktúrákat (először szálkezelés nélkül)!
Készítsen olyan példát, amely megmutatja, hogy több szál használata esetén nem garantált a helyes működés!
Készítse el a struktúrák szálbiztos implementációját!
Definiáljon függvényt a listában való kereséshez!
Vizsgálja meg ennek az időbonyolultságát mérések segítségével! (Készítsen hozzá táblázatot és grafikont!)
Definiáljon egy olyan függvényt, amely paraméterként várja a listához tartozó struktúrát, a keresett elemet, továbbá két függvényt, amelyből az első az elem megtalálásakor hívódik meg, a második pedig akkor, hogy ha a lista nem tartalmazza a keresett elemet!

Promise implementálása

Definiáljon egy Promise struktúrát és hozzá tartozó függvényeket, amelyekkel a következő műveletek oldhatók meg!

A struktúra tárolja egy számítás eredményét.
A has_value függvénnyel lehessen lekérdezni, hogy van-e már eredmnény.
A get_value függvénnyel lehessen lekérdezni a számítás eredményét. Adjon vissza NULL értéket, hogy ha még nem áll rendelkezésre az eredmény!
Oldja meg a hibakezelést (például egy get_error függvénnyel)!
Minden függvényhez készítsen használati esetet (mint példát)!

5. Előadás - Aszinkron végrehajtási modellek

Processzek közötti kommunikáció, CSP

Csatornák használata Go-ban

Aktor modell

Az aktorok jellemzői

Az aktorok műveletei

Az üzenetküldés sajátosságai

Postaládák

Supervision

A modell előnyei

A modell hátrányai

Az MPI szabvány

Kommunikáció a processzek között

Open MPI

A C függvénykönyvtár használata

Kérdések

CSP

Aktor modell

MPI szabvány

Feladatok

Szálbiztos tárolók implementálása

Promise implementálása

Publish-Subscribe modell implementálása