out|inout: A)` umožní jemnější DAG nad stávajícím fork-join skeletonem.
Ukázkový kód (C):
```c
#include <omp.h>
#include <stdio.h>
int main(void) { #pragma omp parallel
{
int id = omp_get_thread_num();
int n = omp_get_num_threads();
printf("Hello from thread %d of %d\n", id, n);
} /* <-- implicit join & barrier */
return 0;
}
````
</markdown>
Poznámka: Fork-join v OpenMP vytváří vlákna, nikoli samostatné procesy. Implementace obvykle stojí na POSIX/pthreads; celý tým sdílí stejnou adresní prostor a paměť. (Procesy se používají jen ve speciálních hybridních modelech např. MPI+OpenMP.)
===== Různé implementace OpenMP specifikace =====
Běžně používané kompilátory a knihovny OpenMP (stav jaro 2025):
| Implementace | Kompilátor / knihovna | Úroveň podpory | Poznámky |
| GCC 14+ (libgomp) | -fopenmp | 5.2 (téměř úplná) | Dlouhodobá open-source volba. |
| LLVM/Clang 18+ (libomp) | -fopenmp | 5.2 (většina) | Dobrá diagnostika, funguje i na Windows. |
| Intel oneAPI (icx/icpx + iomp5) | -qopenmp | 5.2 | Vysoce optimalizovaný runtime, podporuje offload na GPU. |
| IBM XL / LLVM-based | -qsmp=omp | 5.1 | Optimalizace pro POWER. |
| AMD AOCC 4.x | Clang + libomp | 5.1 | Laděno pro Zen architekturu. |
| Cray/AMD ROCm (OpenMP Offload) | Clang | 5.2 | Zaměřeno na akcelerátory a HPC. |
==== Přehled hlavních direktiv OpenMP ====
parallel – vytvoří tým vláken; podporuje klauzule if, num_threads, default, shared, private, …
for / do – paralelizuje smyčku; plánování (schedule(static|dynamic|guided)), collapse(n), reduction, nowait.
sections / section – spustí nezávislé bloky kódu souběžně.
task – vytvoří paralelizovatelnou úlohu, volitelně s depend, priority, detach.
barrier – explicitní synchronizační bod všech vláken týmu.
critical [ (name) ] – sekce, do které může současně vstoupit jen jedno vlákno; pojmenování odděluje nezávislé kritické sekce.
atomic – nejlehčí synchronizace pro jednoduché operace na sdílené proměnné (update, read, write, …).
==== Příklad zapojení všeho dohromady ====
Ukázka kombinuje `parallel`, `for`, tasky a závislosti:
#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áme na všechny tasky
return 0;
}
===== Techniky dekompozice programu =====
statické a dynamické rozdělení práce. Thread-pool a fronta úkolů. Balancování a závislosti (dependencies).
Statické × dynamické rozdělení práce
Statické rozdělení (schedule(static[,chunk])) přiřadí iterace/vlákna předem, minimální overhead, ale hrozí nevyváženost u nepravidelné práce.
Dynamické rozdělení (schedule(dynamic[,chunk])) přiděluje iterace za běhu podle aktuálního vytížení; víc synchronizace, ale lepší vyrovnání.
Guided (schedule(guided[,chunk])) začíná velkými bloky a postupně zmenšuje, kompromis mezi overheadem a vyvážením.
Další volby: runtime (čte z OMP_SCHEDULE), auto (nechá výběr na runtime).
Thread-pool a fronta úkolů (work-stealing)
První paralelní region vytvoří persistentní tým vláken – thread-pool – který se recykluje pro všechny další regiony.
Každé vlákno udržuje lokální deque s tasky; když jeho fronta zeje prázdnotou, ukradne (steals) úkol z cizí → vyrovnání zátěže bez centrální zámky.
Fronty se většinou zamykají jen při krádeži, takže běžné push/pop jsou lock-free a škálují.
Balancování zátěže
Smyčky: volba plánu (static, dynamic, guided), velikost chunku, případně collapse(n) pro součtové smyčky.
Tasky: work-stealing, priority(expr), hromadné throttling limity a heuristiky kompilátoru (např. inline-ing malých tasků přes if(too_small)).
Závislosti (dependencies)
Tasks mohou deklarovat závislosti pomocí
depend –
in,
out,
inout,
mutexinoutset,
depobj.
#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();
Runtime tvoří orientovaný acyklický graf; když jsou všechny závislosti splněné, task se stane „ready“ a fronty si ho mohou volně rozebrat.
===== Techniky dekompozice programu na příkladech =====
==== Řazení ====
quick sort a merge sort
=== Quick sort ===
=== Merge sort ===
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ý výstupní prvek $y_i$ je skalární součin $i$-tého řádku matice $A$ a vektoru $x$.
Divide: rozdělíme práci po řádcích (každý řádek je nezávislý).
Conquer: vlákna počítají dot-product paralelně.
Combine: žádná synchronizace není potřeba, každý řádek zapisuje vlastní $y_i$.
-
Ukázkový kód: paralelizace přes omp parallel for; žádná redukce není nutná, protože každé vlákno píše do unikátního prvku y[i].
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í prvek-po-prvku ($c_{ij}$) škáluje, ale má špatnou cache-lokalitu (každé vlákno prochází celou druhou matici).
Blokové (tiling) rozdělení:
Divide výslednou matici $C$ na bloky $B_{pq}$ o velikosti např. 64 × 64.
Conquer — každý blok počítá jedno vlákno nebo task (
collapse(2) či ruční tasking).
#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);
Combine není potřeba – bloky zapisují do oddělených částí $C$.
Work-stealing runtime OpenMP při dynamickém rozvrhu zajistí, že vlákna s prázdnou frontou převezmou volné bloky → lepší vyvážení.
Prakticky: pro výkon se používají knihovny pro matematické výpočty BLAS (OpenBLAS, MKL, libflame) s vysoce optimalizovaným blokováním a SIMD.
=== Paralelní řešení systému lineárních rovnic (Gaussova eliminace) ===
Gauss / LU: pro každý krok $k$ lze paralelně provést eliminaci řádků $k+1..n-1$.
Závisí na pivotu $A_{kk}$, takže v kroku $k$ musí být ukončené všechny změny z kroku $k-1$.
#pragma omp parallel for na vnější smyčce řádků, nowait nelze kvůli závislostem.
Ukázkový kód (bez otočných pivotů):
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 (CG, GMRES, Jacobi) se paralelizují ještě lépe: operují hlavně s mat-vec a vektorovými redukcemi, kde OpenMP poskytuje hotové reduction(+:) a atomic.
GPU / accelerator off-load: v OpenMP 5.x pomocí target teams distribute parallel for →
jádro se provede na GPU, host kontroluje synchronizaci.
===== Ú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 ====
