out|inout: var)` lze řídit pořadí a závislosti.
* `detach`, `priority` – umožňují pokročilou kontrolu provádění.
Příklad:
#pragma omp task depend(out: A) {
// vypočítáme A
}
#pragma omp task depend(in: A) {
// použijeme A
}
==== Různé implementace OpenMP specifikace ====
OpenMP je pouze specifikace – jednotlivé kompilátory ji implementují v různé míře.
*Přehled nejznámějších implementací (stav 2025):*
* GCC 14+ (libgomp) – `-fopenmp`, verze 5.2 (téměř úplná), open-source klasika.
* Clang 18+ (libomp) – `-fopenmp`, verze 5.2 (většina), funguje i na Windows.
* Intel oneAPI (icx/icpx + iomp5) – `-qopenmp`, verze 5.2, velmi výkonný runtime, podpora GPU.
* IBM XL (LLVM-based) – `-qsmp=omp`, verze 5.1, optimalizace pro POWER.
* AMD AOCC 4.x – laděno pro AMD Zen, Clang + libomp.
* Cray/ROCm – zaměřeno na GPU/offload (OpenMP target).
==== Přehled hlavních direktiv OpenMP ====
* `#pragma omp parallel`
* Vytvoří tým vláken.
* Podporuje: `num_threads`, `if`, `default`, `shared`, `private`, …
* `for` / `do`
* Paralelizace smyčky.
* Možnosti: `schedule(static|dynamic|guided)`, `collapse(n)`, `reduction`, `nowait`.
* `sections` / `section`
* Spustí nezávislé bloky kódu paralelně (např. různé funkce najednou).
* `task`
* Vytvoří úlohu; možnost specifikace závislostí přes `depend(…)`.
* Další klauzule: `priority`, `detach`.
* `barrier`
* Explicitní synchronizační bod – všechna vlákna musí dojít na toto místo.
* `critical [(name)]`
* Zamezí více vláknům vstup do stejné sekce kódu najednou.
* Jméno odděluje různé nezávislé sekce.
* `atomic`
* Odlehčená synchronizace pro jednoduché operace s proměnnou (inkrementace, zápis, čtení…).
==== Příklad zapojení všeho dohromady ====
#include <omp.h>
#include <stdio.h>
int main(void) {
#pragma omp parallel
#pragma omp single // jeden thread spouští tasky
{
#pragma omp task depend(out: sum)
{
int sum = 0;
#pragma omp parallel for reduction(+ : sum) nowait
for (int i = 0; i < 1e6; ++i)
sum += i;
printf("Sum done: %d\n", sum);
}
#pragma omp task depend(in: sum)
{
printf("Post-processing...\n");
}
} // implicit taskgroup – čeká se na všechny tasky
return 0;
}
Tento příklad ukazuje vytvoření tasku se závislostí `depend(out: sum)`, paralelní redukci vnitřní smyčky, a následný task, který čeká na výsledek (`depend(in: sum)`).
===== 5. Techniky dekompozice programu =====
Paralelní programy často potřebují být rozděleny na menší části – a to nejen podle funkcí, ale hlavně podle práce, kterou je třeba vykonat. Tato kapitola se věnuje technikám, jak takovou práci rozdělit mezi vlákna nebo úlohy (tasky), a jak přitom řešit problémy jako nevyvážená zátěž nebo závislosti mezi úlohami. Pochopení těchto principů ti pomůže psát efektivnější a škálovatelnější paralelní kód.
==== Statické × dynamické rozdělení práce ====
* Statické rozdělení – práce (např. iterace smyčky) se rozdělí předem mezi všechna vlákna.
* Např. pomocí `schedule(static[, chunk])` v OpenMP.
* Výhodou je nízký overhead (prakticky žádná synchronizace).
* Nevýhodou je, že u nepravidelných úloh může být některé vlákno přetížené, zatímco jiné skončí dříve a zahálí.
* Dynamické rozdělení – práce se přiděluje za běhu podle toho, které vlákno je volné.
* Používá se `schedule(dynamic[, chunk])`.
* Výhodou je lepší vyvážení zátěže.
* Nevýhodou je vyšší režie kvůli synchronizaci.
* Guided plánování – kompromis mezi statickým a dynamickým:
* `schedule(guided[, chunk])` začíná velkými bloky a postupně zmenšuje chunk velikost.
* Vhodné pro případy, kdy práce trvá různě dlouho a časem ubývá.
* Další možnosti:
* `schedule(runtime)` – výběr plánování je ponechán na hodnotě proměnné `OMP_SCHEDULE`.
* `schedule(auto)` – nechá výběr plánu na implementaci OpenMP.
==== Thread-pool a fronta úkolů (work-stealing) ====
* OpenMP (od verze 3.0) podporuje tasky, které jsou plánovány na vlákna z persistentního thread-poolu.
* Vlákna jsou vytvořena v prvním paralelním regionu a zůstávají aktivní i pro další úseky programu.
* Každé vlákno má vlastní lokální deque (obousměrnou frontu), do které si vkládá nové úkoly.
* Work-stealing: pokud vlákno nemá co dělat, zkusí si „ukrást“ úkol z cizí fronty.
* Tento přístup pomáhá automaticky vyvažovat zátěž.
* Push/pop na vlastní frontě jsou většinou lock-free; zámky se používají jen při krádeži.
==== Balancování zátěže ====
Vyrovnané rozdělení práce je klíčem k výkonu paralelního programu.
* U smyček:
* Volba správného `schedule(…)` plánu.
* Velikost `chunku` ovlivňuje granularitu přidělené práce.
* `collapse(n)` – slučuje více vnořených smyček do jedné, čímž zvyšuje počet iterací pro paralelizaci.
* U tasků:
* Work-stealing pomáhá s dynamickým plánováním.
* Pomocí `priority(expr)` lze zvýhodnit důležité úkoly.
* Heuristiky runtime mohou omezit vznik malých tasků (např. jejich inline-ing) → lepší škálování.
==== Závislosti (dependencies) ====
Tasky mohou mít mezi sebou závislosti, které určují pořadí provádění. V OpenMP se deklarují pomocí `depend(…)`.
* Typy závislostí:
* `depend(in: X)` – task potřebuje data `X`.
* `depend(out: X)` – task produkuje data `X`.
* `depend(inout: X)` – task `X` čte i zapisuje.
* Další pokročilé typy: `mutexinoutset`, `depobj` – pro specializované scénáře.
Ukázkový kód:
#pragma omp task depend(out:A)
build_A();
#pragma omp task depend(in:A) depend(out:B)
build_B();
#pragma omp task depend(in:B)
use_B();
* OpenMP runtime si z těchto závislostí sestaví DAG (acyklický graf).
* Jakmile jsou všechny vstupní závislosti splněny, task je označen jako „ready“ a zařadí se do fronty.
Tato metoda umožňuje velmi jemné řízení výpočtu a paralelizace i nepravidelných nebo stromových struktur (např. kompilátory, plánovače, grafy).
===== 6. Techniky dekompozice programu na příkladech =====
Abychom lépe pochopili různé způsoby paralelizace, ukážeme si je na konkrétních příkladech z oblasti řazení, lineární algebry a strojového učení. Uvidíme, jak lze algoritmy jako quick sort nebo násobení matic přirozeně rozdělit do paralelních částí a jaké techniky přitom použít – např. tasky, `collapse`, blokové zpracování či závislosti.
==== Řazení ====
quick sort a merge sort
=== Quick sort ===
* Proč „rozděl a panuj“?
* *Divide*: vybereme pivot a jedním průchodem rozdělíme pole na část < pivot a část ≥ pivot.
* *Conquer*: obě části rekurzivně řadíme – ideální místo pro vytvoření dvou paralelních úloh (*tasků*).
* *Combine*: není třeba – dělení samo zajistí správné pořadí.
* Paralelizace: po operaci `partition` spustíme levé větvení jako `omp task`, pravé běží ve vlákně dál.
void qs(std::vector<int>& vec, int from, int to) {
if (to - from <= base_size) {
std::sort(vec.begin() + from, vec.begin() + to);
return;
}
int pivot = vec[from];
int mid = partition(vec, from, to, pivot); // divide
if (mid - from > 1) { // conquer – left
#pragma omp task shared(vec) firstprivate(from, mid)
qs(vec, from, mid);
}
if (to - mid > 1) { // conquer – right
qs(vec, mid, to);
}
}
=== Merge sort ===
* Proč „rozděl a panuj“?
* *Divide*: rekurzivní dělení pole na půlky.
* *Conquer*: každou půlku řadíme paralelně.
* *Combine*: dvě seřazené části spojíme lineárním `merge`.
* Paralelizace: obě rekurze běží jako tasky, po jejich dokončení proběhne `inplace_merge`.
void ms(std::vector<int>& vec, int from, int to) {
if (to - from <= base_size) {
std::sort(vec.begin() + from, vec.begin() + to); // seriál-insert
return;
}
int mid = from + (to - from) / 2; // divide
#pragma omp task shared(vec) firstprivate(from, mid)
ms(vec, from, mid); // conquer – left
ms(vec, mid, to); // conquer – right
#pragma omp taskwait
std::inplace_merge(vec.begin() + from, // combine
vec.begin() + mid,
vec.begin() + to);
}
==== Numerická lineární algebra a strojové učení ====
násobení matice × vektor, násobení dvou matic, řešení systému lineárních rovnic
=== Paralelní násobení matice × vektor (SpMV/Dense MV) ===
* Princip: každý prvek $y_i$ je skalární součin řádku $A_i$ a vektoru $x$.
* *Divide*: rozdělíme po řádcích.
* *Conquer*: každý řádek počítá vlákno nezávisle.
* *Combine*: nepotřebujeme – každý výstupní `y[i]` je unikátní.
* U husté matice: nejlepší přístup po řádcích (row-major).
* U řídké: paralelizace přes nenulové řádky (např. CSR formát).
void matvec_dense(const std::vector<double>& A, // ROWS × COLS, row-major
const std::vector<double>& x,
std::vector<double>& y) {
#pragma omp parallel for
for (int i = 0; i < ROWS; ++i) {
double sum = 0.0;
for (int j = 0; j < COLS; ++j)
sum += A[i * COLS + j] * x[j]; // dot product
y[i] = sum;
}
}
=== Paralelní násobení dvou matic ===
* Naivní přístup: každý prvek $c_{ij}$ samostatně – špatná cache-lokalita.
* Blokové (tiling) násobení:
* *Divide*: rozdělíme výstupní matici $C$ na bloky $B_{pq}$.
* *Conquer*: každý blok počítá vlákno/task – např. pomocí `collapse(2)`.
* *Combine*: není třeba – bloky jsou oddělené.
#pragma omp parallel for collapse(2) schedule(dynamic)
for (int bi = 0; bi < N; bi += BS)
for (int bj = 0; bj < N; bj += BS)
for (int bk = 0; bk < N; bk += BS)
multiply_block(A, B, C, bi, bj, bk, BS);
* Pro vysoký výkon: používat BLAS knihovny (OpenBLAS, MKL…) se SIMD a tilingem.
=== Paralelní řešení systému lineárních rovnic (Gaussova eliminace) ===
* Gaussova eliminace (LU): v kroku $k$ odstraňujeme hodnoty pod pivotem $A_{kk}$.
* Paralelizujeme řádky $i = k+1..n-1$.
* Nutná synchronizace mezi kroky – `taskwait` nebo sekvenční závislosti.
void gauss_elim(std::vector<double>& A) { // ROWS × COLS, row-major
for (int k = 0; k < ROWS - 1; ++k) {
#pragma omp parallel for
for (int i = k + 1; i < ROWS; ++i) {
double c = -A[i * COLS + k] / A[k * COLS + k];
for (int j = k; j < COLS; ++j)
A[i * COLS + j] += c * A[k * COLS + j];
}
}
}
* Iterativní metody (Jacobi, CG, GMRES):
* Lépe paralelizovatelné než Gauss – hlavně `matvec`, vektorové operace, redukce.
* OpenMP poskytuje `reduction(+:)` a `atomic` pro synchronizaci.
* Off-load na GPU (OpenMP 5.x):
* Pomocí `target teams distribute parallel for` lze výpočet přenést na GPU.
* Host kontroluje synchronizaci, ale výpočet běží plně na zařízení.
===== Úvod do distribuovaných systémů (DS) ====
charakteristiky DS, čas a typy selhání v DS
DS je soubor nezávislých, autonomních výpočetních jednotek propojených komunikační sítí. Výpočetní jednotky mezi sebou komunikují formou posílání zpráv za účelem určité formy spolupráce.
Výpočetní jednotky nemají sdílenou paměť, nesdílejí globální hodiny a selhávají na sobě nezávisle.
Kadý proces má své lokální hodiny, které nemusí ukazovat přesný čas (synchronizace je možná pouze s určitou přesností).
Je obtížné uvažovat o čase nejen kvůli absenci globálních hodin ale obecně nelze dát limit na komunikaci a délku výpočtu.
==== Asynchronní x Synchronní DS ====
Popisují model světa ve kterém DS existuje. rozdělení synchroní a asynchroní popisuje množinu předpokladů, které budeme používat při psaní distribuovaného algoritmu.
=== Synchronní model ===
* Známe horní hranice
* maximální zpoždění zprávy
* maximální čas mezi dvěma kroky procesu
* maximální drift lokálních hodin
* Algoritmy můžeme psách v **fázích/kolech** a spolehlivě používat timeouty
* V praxi čistě synchroní sétě skoro neexistují
=== Asynchronní model ===
* Žádné limity – zpráva může bloudit libovolně dlouho, proces může
běžet tak pomalu, jak chce, hodiny se mohou rozejít.
* Timeout tedy **nemůže spolehlivě rozlišit** „zpomalení“ od „pádu“.
* V tomto modelu je např. prokázáno (FLP), že deterministický konsensus
s možností jediného pádu procesu **nelze** vyřešit.
=== Částečně synchronní model (real-world kompromis) ===
* Systém se může chovat asynchronně, ale po nejpozději neznámém čase stabilně do režimu, kdy už limity platí.
* Většina produkčních protokolů (Raft, PBFT …) předpokládá právě tenhle model – jsou robustní vůči výkyvům, ale nakonec se „chytí“.
- Selhání procesu
* crash / fail-stop - proces přestane vykonávatz algoritmus
* libovolné (byzantské) selhání - proces může pracovat déle a odpovídat na zprávy, ale vykonává chybný algoritmus
- Selhání kanálu
* ztráta zprávy - zpráva se ztratí a nedorazí do cílového procesu
* partitioning - procesy jsou rozdělené do disjunktních množin, komunikace v nich je možná, ale mezi nimi ne
- Selhání časování - doba odezvy procesu nebo přenosu zprávy vybočila z dohodnutého časového rozmezí
Předpoklady na komunikační kanál:
Spolehlivé doručování, žádná duplikace, žádné vytváření, garantované pořadí doručování
===== Detekce selhání v DS =====
detektory selhání a jejich vlastnosti
úplnost - každé selhání je časem detekováno alespoň jedním bezvadným procesem
přesnost - nedochází k mylné detekci
nelze dosáhnout obou vlastností současně, je vyžadována 100% úplnost a $\lt$ 100% přesnost.
Frekvence selhání roste lineárně s počtem procesů ve skupině (selhání jsou běžná)
Dva podprotokoly - detekce selhání a šíření informace o selhání
Průběh detekce:
- havárie procesu $p_j$
- detekce selhání procesu $p_j$ nějakým procesem $p_k$
- proces $p_k$ rozšiřuje informaci o selhání procesu $p_j$ do ostatních procesů
Základní protokoly pro detekci selhání:
=== Centralizovaný heartbeat ===
Heartbeat jsou odesílány periodicky, každých $\mathcal{T}$ jednotek času jednomu vybranému procesu $p_j$
Heartbeat má pořadové číslo, to odeslání heartbeatu je inkrementován lokální čítač pro každý proces
Pokud není heartbeat od $p_i$ přijat v $p_j$ v časovém limitu $\tau$, je $p_i$ označen jako havarovaný
Je úplný pro všechny uzly kromě $p_j$, selhání $p_j$ není detekováno a při velkém počtu uzlů může být $p_j$ přetížen.
=== Kruhový heartbeat ===
Heartbeats jsou odesílány periodicky sousedům každého procesu (jednostranně nebo oboustranně).
* není centrální uzel
* není úplné při selhání více procesů (stačí jeden u jednosměrného, 2 u obousměrného)
* je třeba udržovat kruhovou hierarchii
=== All to all heartbeat ===
každý proces periodicky odesílá heartbeat všem ostatním procesům
* rovnoměrná zátěž uzlů
* je úplný
* vysoké zatížení uzlů
* nízká přesnost (může dojít k označení více uzlů za havarované při zpoždění zprávy)
=== SWIM ===
Scalable weakly consistent infection-style proces group membership protocol
* proces $p_i$ periodicky odesílá zprávu $\texttt{ping}$ náhodně vybranému uzlu $p_j$ a čeká na odpověď $\texttt{ack}$
* pokud ji nedostance, odešle zprávu $\texttt{ping\_req}$ $\mathcal{K}$ náhodně vybraným uzlům
* tyto uzly se zeptají $p_j$ pomocí zprávy $\texttt{ping}$ a pokud dostanou odpověď, odešlou ji $p_i$ jako $\texttt{ping\_ack}$
* pokud ani jeden z $\mathcal{K}$ uzlů nedostane odpověď, označí $p_i$ $p_j$ jako havarovaný
přesnost lze nastavit volbou $\mathcal{K}$, klesá exponenciálně s rostoucím $\mathcal{K}$
úplnost je zaručena, průměrný čas detekce je $\frac{e}{e - 1}\mathcal{T}$
===== Čas a kauzalita v DS =====
uspořádání událostí v DS, fyzické hodiny a jejich synchronizace, logické hodiny a jejich synchronizace
clock slew - rozdíl v času hodin dvou procesů, mají li dvoje hodiny nenulovou mimoběžnost, jsou nesynchronizované
clock drift - rozdíl v rychlosti hodin dvou procesů
synchronizace
* externí
* čas $\mathcal{C}_i$ hodin každého procesu $p_i$ je udržován v rozmezí $\delta$ od času $\mathcal{S}$ externích referenčních hodin (tj. $|\mathcal{C}_i - \mathcal{S}| \leq \delta$)
* externí hodiny mohou být napojeny na UTC nebo atomové hodiny
* například NTP
* interní
* každý pár procesů $(p_i, p_j)$ má hodnoty času svých hodin v rozmezí $\delta$, v každém okamžiku (tj. $|\mathcal{C}_i - \mathcal{C}_j| \leq \delta$)
* například Berkeley algoritmus
Externí synchronizace typu Kolik je hodin? → odešle odpověď → nastaví čas, má chybu nastavení špatného času kvůli komunikační prodlevě (latenci)
Cristianův algoritmus
$$ \mathcal{C}_i \coloneq t + \frac{\mathcal{T}_\text{RT}-l_{\text{min}+l'_{min}}}{2}$$
chyba je omezena, tj maximálně $\frac{\mathcal{T}_\text{RT} - l_{\text{min}} - l'_{\text{min}}}{2}$
lokální čas lze posunou libovolně dopředu, ale ne dozadu, je možné zvýšit nebo snížit rychlost hodin
NTP
* servery uspořádány do hierarchie stromu, uzly synchronizují čas se svými rodiči a někdy s dalšími servery na stejné úrovni
* mezi zprávami se spočte offset, který se použije pro výpočet komunikační latence
* $o = \frac{(t_1^{r} - t_2^{r}+t_2^{s} - t_1^{s})}{2}$
Logické hodiny
nepoužívají přímo aktuální čas ale časovou značku
kauzální vztah - první událost může ovlivnit druhou
Relace stalo se před
- Jsou-li $\mathcal{A}$ a $\mathcal{B}$ události ve stejném procesu $p$ a pokud $\mathcal{A}$ nastala před $\mathcal{B}$, pak $\mathcal{A} \rightarrow \mathcal{B}$
- Je-li $\mathcal{A}$ odeslání zprávy a $\mathcal{B}$ je přijetí této zprávy, pak $\mathcal{A} \rightarrow \mathcal{B}$
- Je-li $\mathcal{A} \rightarrow \mathcal{B}$ a $\mathcal{B} \rightarrow \mathcal{C}$, pak $\mathcal{A} \rightarrow \mathcal{C}$ (tranzitivita)
Kauzální nezávislost
* relace stalo se před zavádí částečné uspořádání událostí, potenciální kauzální závislosti
* $e_1$ → $e_2$: potenciálně kauzálně závislé události ($e_2$ mohlo být ovlivněno $e_1$, ale nemuselo)
* $e_1$ || $e_2$: současné události (kauzální vztah určitě není)
Lamportovy logické hodiny - každý proces má své logické hodiny, které se aktualizují podle přijímání zpráv
Synchronizace logických hodin
- po každé události která se odehraje v $p_i$ se hodiny $\mathcal{C}_i$ inkrementují o 1
- každé zprávě $m$ odeslané procesem $p_i$ je přiřazená časová značka $ts(m) = \mathcal{C}_i$
- kdykoliv proces $p_j$ přijme zprávu $m$, tak:
- upraví své lokální hodiny $\mathcal{C}_j$ na $max\{\mathcal{C}_j, ts(m)\}$ a poté
- provede krok 1 předtím než předá $m$ aplikaci (<= přijetí zprávy je událost)
Lamportovy hodiny neimplikují kauzalitu!
* Platí: jestliže $e_1 \rightarrow e_2$, pak $\mathcal{C}(e_1) \lt \mathcal{C}(e_2)$
* Neplatí: jestliže $\mathcal{C}(e_1) \lt \mathcal{C}(e_2)$, pak $e_1 → e_2$
Vektorové hodiny - každý proces si udržuje vektor celočíselných hodin ostatních procesů
===== Globální stav v DS a jeho výpočet =====
řez distribuovaného výpočtu, algoritmus pro distribuovaný globální snapshot, stabilní vlastnosti DS
globální stav je množina lokálních stavů procesů v DS a stavu všech komunikačních kanálů v jednom okamžiku
globální snapshot je záznam globálního stavu
například
* garbage collection
* deadlock detection
* detekce ukončení výpočtu
* checkpointing
Řez - časová hranice v každém procesu a v každém komunikačním kanále
* události které nastanou před řezem jsou v řezu
* události které nastanou po něm jsoui mimo řez
Konzistentní řez - řez $\mathcal{Ř}$ je konzistentní pokud splňuje kauzalitu, tj. pokud pro každý pár událostí $e$, $f$ v systému platí:
$$ f \in \mathcal{Ř} \land e \rightarrow f \implies e \in \mathcal{Ř}$$
tj. pokud řez obsahuje nějakoiu událost, obsahuje i všechny, které ji předcházejí dle relace stalo se před (tj. nelze aby v řezu byl důsledek a nebyla tam příčina)
konzistentní řez = logický okamžik
Konzistentní globální snapshot odpovídá konzistentnímu řezu.
* Globální snapshot je konzistentní, pokud by mohl (ale nikoliv musel) být zpozorován externím pozorovatelem daného distribuovaného výpočtu.
* Nekonzistentní řez by nemohl nikdy být zpozorován externím pozorovatelem daného distribuovaného výpočtu.
Chamdy-Lamport algoritmus pro distribuovaný globální snapshot
- (Vytváření snapshotu je distribuované.)
- Speciální zpráva: ZNAČKA ▪
- Jeden (libovolný) z procesů iniciuje vytvoření snapshotů.
- Procesy reagují na příjem zprávy ZNAČKA ▪
- výsledkem je konzistentní řez
ilustrace algoritmu slide 15-21
stabilní vlastnost je taková vlastnost, že jakmile je ve výpočtu jednou splněna, zůtává splněna navždy
* například výpočet skončil, nastalo uváznutí, objekt je sirotek
nestabilní vlastnost je například ve výpočtu není žádný havarovaný proces
Chandy-Lamport snapshotů algoritmus lze použít pro detekci stabilních globálních vlastností:
* Je daná stabilní vlastnost V splněna v globálním snapshotu zachyceným snapshot algoritmem?
- ANO - Vlastnost $\mathcal{V}$ bude ve výpočtu splněna i ve fyzickém okamžiku doběhnutí snapshot algoritmu.
- NE - Vlastnost $\mathcal{V}$ nemohla být ve výpočtu splněna ani ve fyzickém okamžiku zahájení snapshot algoritmu.
===== Vzájemné vyloučení procesů v DS =====
algoritmy pro vyloučení procesů a jejich vlastnosti
==== Problém vzájemného vyloučení ====
Kritická sekce je část kódu u které potřebujeme zaručit, že ji v každém okamžiku vykonává maximálně jeden proces
Definujeme funkce enter() a exit() pro vstup a výstup do kritické sekce
Na úrovni operačního systému umíme problém řešit pomocí synchronizačních nástrojů, v distribuovaném systému potřebuje algoritmus
==== Požadavky na algoritmus pro vyloučení procesů ====
Bezpečnost - Nejvýše jeden proces v kritické sekci
Živost - Každý požadavek na vstup kritické sekce je časem uspokojen
Uspořádání (není nutné) - Předchází-li žádost jednoho procesu do kritické sekce kauzálně žádosti jiného procesu, tento proces by se měl do kritické sekce dostat dříve
Uvažujeme navíc, že procesy neselhávají a komunikační kanály jsou perfektní (FIFO, zprávy se neduplikují, nevznikají, neztrácejí) a uvažujeme asynchronní systém s konečnou latencí
==== Analýza výkonnosti algoritmů pro vzájemné vyloučení ====
Komunikační zátěž = počet zpráv poslaných při každém vstupu a výstupu do KS
Zpoždění klienta = zpoždění procesu při vstupu do KS za předpokladu, že jiné procesy na vstup nečekají
Synchronizační zpoždění = interval mezi vystoupením jednoho procesu z KS a vstoupením dalšího
==== Centralizovaný algoritmus ====
Je zvolen jeden koordinátor
Ten spravuje speciální token, který držiteli umožní vstup do KS a frontu požadavků na vstup do KS
Před vstupem do KS je poslán požadavek na token koordinátorovi, po přijetí tokenu algoritmus vstupuje do kritické sekce
Po výstupu je token vrácen koordinátorovi
Koordinátor po přijetí požadavku na token předá token pokud jej drží, pokud jej nedrží, tak tento požadavek přidá do fronty
Ve chvíli kdy koordinátor obdrží token tak zkontroluje frontu zda tam není žádný požadavek a případně jej obslouží
Bezpečnost je zaručena, a živost za našich předpokladů také
Komunikační zátěž - 2 zprávy vstup, 1 výstup
Zpoždění klienta - 2 latence
Synchronizační zpoždění - 2 latence
==== Kruhový algoritmus ====
N procesů v kruhu
Proces může poslat zprávu následníkovi
Mezi procesy koluje jeden token
Před vstupem proces čeká dokud neobdrží token
Po vstupu proces pošle token následníkovi
Pokud proces obdrží token a nečeká na vstup, tak jej hned předá dále
Komunikační zátěž - $N$ vstup, $1$ výstup
Zpoždění klienta - $0$ až $N$ zpráv
Synchronizační zpoždění - $1$ až $N-1$ komunikačních latencí
==== Ricart-Agrawalův algoritmus ====
Nepoužívá token, ale kauzalitu a multicast
Nižší synchronizační zpoždění než kruhový algoritmus a nepoužívá centrální proces
Každý proces si udržuje stav, který může nabývat 3 hodnot: WANTED, HELD, RELEASED (u všech procesů je inicializován na RELEASED)
identifikátor kritické sekce, kterou zamyká,
stav: RELEASED, HELD nebo WANTED, a
frontu odložených požadavků.
Na začátku je stav každého zámku každého procesu nastaven na RELEASED. V systému kolují pro každou kritickou sekci dva typy zpráv: REQUEST a OK
Pokud chce proces P[i] požádat o vstup do kritické sekce K, zaznamená čas T[i] kdy o zdroj žádá a pošle zprávu REQUEST(K) s tímto časem všem procesům, které do K přistupují. Nastaví stav svého zámku K na WANTED.
Zámek K procesu je ve stavu WANTED dokud neobdrží zprávu OK(K) od každého dalšího přistupujícího procesu. Poté se nastaví na HELD.
Pokud procesu
P[j] přijde zpráva
REQUEST(K) od procesu
P[i] s časem
T[i], tak
pokud je zámek K ve stavu HELD, pak zprávu REQUEST(K) zařadí mezi odložené požadavky a neodpoví
pokud je ve stavu WANTED a o vstup do kritické sekce žádal v čase T[j] < T[i], případně T[j] = T[i] a j < i, pak zprávu REQUEST(K) zařadí mezi odložené požadavky a neodpoví,
jinak pošle zprávu OK(K) procesu P[i].
Pokud proces P[i] dokončí práci v kritické sekci K, nastaví stav zámku K na RELEASED, odpoví na všechny zprávy ve frontě zámku a frontu vyprázdní.
V nejhorším případě je nutno čekat než všech $(N-1)$ pošle OK
Je zachováno pořadí, požadavky s nižší lamportovou značkou mají přednost
Komunikační zátěž – $2(N-1)$ při vstupu, až $(N-1)$ při výstupu
Zpoždění klienta – 2 latence
Synchronizační zpoždění – 1 latence
===== Volba lídra v DS =====
algoritmy pro volbu lídra a jejich vlastnosti
Cílem je, aby se všechny procesy shodly na jednom „koordinátorovi“ (lídrovi).
Předpokládáme možnost selhání (crash) procesů nebo spojení; zprávy se ale doručují spolehlivě.
Výsledek nesmí záviset na tom, kdo volbu odstartoval, a více souběžných voleb se musí slít do jedné (konvergence).
==== Kruhový algoritmus (Ring) ====
Procesy tvoří logický kruh uspořádaný podle ID. Každý zná svého následníka a umí zjistit, zda soused žije.
Start: proces $P_i$ detekuje pád lídra a pošle zprávu ELECTION(i) svému následníkovi.
Přijetí ELECTION(j) u $P_i$
pokud $j > i$: předá zprávu dál beze změny;
pokud $j < i$: nahradí $j$ svým ID a pošle ELECTION(i);
pokud $j = i$: zpráva oběhla kruh ⇒ $P_i$ má nejvyšší ID ⇒ je vítěz.
$P_i$ vyšle ELECTED(i) kolem kruhu; všichni si uloží, že koordinátor je $i$ a předají dál, dokud zpráva neoběhne kruh.
Komplexita: $\mathcal{O}(n)$ zpráv a čas, kde $n$ je počet živých procesů. Funguje i s více paralelními volbami, protože nejvyšší ID zvítězí.
==== Algoritmus Bully ====
