8. tétel - Párhuzamos tervezési minták II.

Mutassa be a Master/Worker tervezési mintát! Ismertesse a tulajdonságait, az általános felépítését, valamint tipikus használati eseteit! Mutassa be a Fork/Join tervezési mintát!

Master/Worker

A Master/Worker minta azokban az esetekben használható hatékonyan, amikor a terheléselosztás nehezen valósítható meg a szálak között és ezért nem célszerű előre műveletvégzőket rendelni adott feladatokhoz.

Akkor is megoldást nyújthat, ha a logika intenzív része nem számlálós ciklusba rendezett, mérete nem ismert előre, és nem is becsülhető meg.

Tehát akkor jó, amikor:

  • nagy mennyiségű, nem összefüggő adatunk van
  • jó terheléseloszlás mellett szeretnénk elvégezni a feladatokat

Általános felépítése

flowchart TB
    MI[Master Inicializál] --> WI & W2 & W3 & W4
    subgraph W1[W1: worker életciklus]
    WI[Inicializálás] --> WF[Feladat kérése a Mastertől] --> WV[Feladat végrehajtása] --> COND{Van még megoldatlan feladat?}
    COND -->|Van| WF
    COND -->|Nincs| WL[Leállás]
    end
    subgraph W2
    end
    subgraph W3
    end
    subgraph W4
    end
    WL & W2 & W3 & W4 --> MB[Master begyűjti az eredményeket] --> ML[Master leáll]

  1. Master inicializál

    • Betölti a problémát
    • deklarálja a részproblémák tárolására alkalmas szerkezetet,
    • betölti a részfeladatokat,
    • majd indítja a Worker elemeket.

  2. Worker életciklus

    a) Inicializálás
    b) Feladat kérése a Mastertől
    c) Végrehajtás
    d) Ha van még megoldatlan feladat, akkor ugrás a b) pontra
    e) Kilépés

  3. Master begyűjti és összegzi az eredményeket

  4. Leállítás

Tulajdonságok

  • A feladatokat tartalmazó adatszerkezet (bag of tasks) jellemzően egy szálbiztos sor
  • A feladatok nincsenek statikusan hozzárendelve a műveletvégzőkhöz
  • A terheléselosztás automatikus (egy szál új feladatot kap, ha végzett az előzővel)
  • Jól skálázható: ha a feladatok száma jóval nagyobb a műveletvégzők számánál, a párhuzamos gyorsítás közel lineáris
  • A Master a feladatok legyártása után Workerré válhat
  • Átalakítások:
    • Work stealing: a workereknek saját munkasora van, és lophatnak egymáséról ha kifogytak
    • Hibatolerálás megoldható, ha ugyanazt a feladatot több workernek is kiosztjuk
  • Hátrány:
    • kihívás lehet a befejezés detektálása
      • pl. ha a Master már a gyártás közben indítja a workereket, szükség lehet egy logikai változóra is, a sor ürességének ténye nem elég
      • poison pill: speciális feladat, ami azt jelzi, hogy nincs már feladat, és leállhat a worker
    • ha a szálaknak a műveletvégzés során kommunikálni kell egymással, vagy a feladatok között függés van, akkor ez a minta nem alkalmazható.

Fork/Join

Abban az esetben használjuk a Fork/Join mintát, ha a részproblémák létrehozása dinamikus, a bemeneti paraméter függvénye. Ekkor nem ismert előre a részfeladatok száma.

Tipikus használati esete az „oszd meg és uralkodj” elvű problémák, amikor a feladatot addig bontjuk részproblémákra, amíg el nem érünk az alapesetig, majd visszafelé felépítjük a megoldást.

A minta neve a szálak elágazáskori létrejöttéről (fork), és később a szinkronizációkor való visszacsatlakozásról (join) kapta.

Az implementációkor a fő problémát a szálak létrehozásából, menedzsmentjéből és megszüntetéséből adódó overhead okozza, amellyet kétféle leképezéssel oldhatunk meg.

A direkt leképezés során a szálak és a részprobléma létrehozása egyszerre történik. A forráskódban, ahol szükséges, létrejön a szál, a szülő szál pedig blokkol, amíg a gyermek nem végzett a feladatával. Tehát a program egy szállal indul, amelyről egyre több szál ágazik le, és várakozik ezek befejeződésére. A gyermek szálakból további szálak ágazhatnak le.

Az indirekt leképezés az előbb kialakuló jelentős overheadet hívatott csökkenteni. A direkt lekézesés során a szálak létrehozása a teljes végrehajtást lassítja, illetve ronthatja a hatékonyságot. Szálak létrehozása és megszüntetése helyett használható az úgynevezett thread pool, amikor a program indításakor újrahasznosítható szálak jönnek létre, feladatuk befejeztével pedig visszakerülnek a poolba. Ezzel a szerkezettel a feladatokhoz nem kapcsolódnak dedikált szálak, tehát csökken a létrehozásból, ütemezésből és megszüntetésből adódó overhead.

A minta szorosan kapcsolódik a Loop Parallelism és a Master/Worker mintához is.