The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b36pdv [2025/06/04 21:06] – zapleka3statnice:bakalar:b4b36pdv [2025/06/04 22:52] (current) – [Logické hodiny a kauzalita] zapleka3
Line 18: Line 18:
     - **Vzájemné vyloučení procesů v DS** – algoritmy pro vyloučení procesů a jejich vlastnosti.     - **Vzájemné vyloučení procesů v DS** – algoritmy pro vyloučení procesů a jejich vlastnosti.
     - **Volba lídra v DS** – algoritmy pro volbu lídra a jejich vlastnosti.     - **Volba lídra v DS** – algoritmy pro volbu lídra a jejich vlastnosti.
 +
 +===== Paralelní systémy/výpočty =====
  
 ===== 1. Hardwarová podpora pro paralelní výpočty ===== ===== 1. Hardwarová podpora pro paralelní výpočty =====
Line 78: Line 80:
  
 ==== GPGPU ==== ==== GPGPU ====
-* **General-Purpose computing on Graphics Processing Units** (GPGPU) využívá původně grafické karty pro obecné výpočty. +  * **General-Purpose computing on Graphics Processing Units** (GPGPU) využívá původně grafické karty pro obecné výpočty. 
- +  * GPU obsahují tisíce jednoduchých jader sdružených do **streaming multiprocessorů (SM)**.   
-* GPU obsahují tisíce jednoduchých jader sdružených do **streaming multiprocessorů (SM)**.   +    * Ty spouštějí stovky až tisíce vláken najednou ve skupinách (warp – 32 vláken běžících lock-step).
-  Ty spouštějí stovky až tisíce vláken najednou ve skupinách (warp – 32 vláken běžících lock-step).+
  
 === Architektura a omezení === === Architektura a omezení ===
- 
   * **Výpočetní hierarchie:** GPC → SM → block → warp → thread   * **Výpočetní hierarchie:** GPC → SM → block → warp → thread
   * **Sdílené prostředky:**   * **Sdílené prostředky:**
Line 90: Line 90:
     * max 64 warpů / SM (až 2048 vláken)     * max 64 warpů / SM (až 2048 vláken)
     * ~255 registrů na vlákno – méně registrů = vyšší obsazenost     * ~255 registrů na vlákno – méně registrů = vyšší obsazenost
- 
   * **Paměťová hierarchie:**   * **Paměťová hierarchie:**
     * L1/shared: ~33 cyklů     * L1/shared: ~33 cyklů
Line 128: Line 127:
  
 ==== Vlákna a procesy ==== ==== Vlákna a procesy ====
-* **Proces** je samostatná jednotka běhu programu, má vlastní adresní prostor (paměť), popisovače souborů atd. +  * **Proces** je samostatná jednotka běhu programu, má vlastní adresní prostor (paměť), popisovače souborů atd. 
-  * Spuštění nového procesu je relativně nákladné. +    * Spuštění nového procesu je relativně nákladné. 
-  * Vhodné pro více zcela oddělených výpočetních úloh (např. mikroservisy, více programů najednou). +    * Vhodné pro více zcela oddělených výpočetních úloh (např. mikroservisy, více programů najednou). 
- +  * **Vlákno (thread)** je lehčí jednotka běhu uvnitř procesu. 
-* **Vlákno (thread)** je lehčí jednotka běhu uvnitř procesu. +    * Sdílí paměť a další prostředky s ostatními vlákny procesu. 
-  * Sdílí paměť a další prostředky s ostatními vlákny procesu. +    * Přepínání mezi vlákny je levnější než mezi procesy. 
-  * Přepínání mezi vlákny je levnější než mezi procesy. +    * Vhodné pro paralelizaci uvnitř jedné aplikace – více úloh najednou (např. UI, I/O, výpočty). 
-  * Vhodné pro paralelizaci uvnitř jedné aplikace – více úloh najednou (např. UI, I/O, výpočty). +    * Pozor na **synchronizaci a souběhy (race conditions)** – nutnost použití zámků, mutexů apod.
-  * Pozor na **synchronizaci a souběhy (race conditions)** – nutnost použití zámků, mutexů apod.+
  
 ==== Hierarchie cache pamětí ==== ==== Hierarchie cache pamětí ====
 Moderní CPU mají vícestupňovou **hierarchii cache**, která zajišťuje rychlý přístup k často používaným datům: Moderní CPU mají vícestupňovou **hierarchii cache**, která zajišťuje rychlý přístup k často používaným datům:
- 
   * **L1 cache** – nejmenší (např. 32 KB), ale nejrychlejší (~4 cykly), zvlášť pro instrukce a data.   * **L1 cache** – nejmenší (např. 32 KB), ale nejrychlejší (~4 cykly), zvlášť pro instrukce a data.
   * **L2 cache** – větší (např. 256 KB), pomalejší (~12 cyklů), většinou sdílena mezi jádry.   * **L2 cache** – větší (např. 256 KB), pomalejší (~12 cyklů), většinou sdílena mezi jádry.
Line 148: Line 145:
  
 Efektivní využití cache (např. přístup po řádcích, nikoliv po sloupcích v 2D poli) může mít zásadní vliv na výkon. Efektivní využití cache (např. přístup po řádcích, nikoliv po sloupcích v 2D poli) může mít zásadní vliv na výkon.
- 
- 
  
 ===== 2. Komplikace v paralelním programování ===== ===== 2. Komplikace v paralelním programování =====
Line 155: Line 150:
  
 ==== Race Condition (souběh) ==== ==== Race Condition (souběh) ====
-* **Souběh (race condition)** nastává, když dvě nebo více vláken přistupuje ke **stejným datům** a **alespoň jedno z nich je mění**, přičemž jejich pořadí není řízené (např. zámky, mutexy). +  * **Souběh (race condition)** nastává, když dvě nebo více vláken přistupuje ke **stejným datům** a **alespoň jedno z nich je mění**, přičemž jejich pořadí není řízené (např. zámky, mutexy). 
- +  * To znamená, že výsledek programu **závisí na načasování** – někdy to „vyjde dobře“, jindy ne. 
-* To znamená, že výsledek programu **závisí na načasování** – někdy to „vyjde dobře“, jindy ne. +  * Typickým příkladem je inkrementace sdílené proměnné – pokud není chráněná zámkem, může být výsledek menší, než kolik se očekává.
-* Typickým příkladem je inkrementace sdílené proměnné – pokud není chráněná zámkem, může být výsledek menší, než kolik se očekává.+
  
 Například: Například:
Line 168: Line 162:
 </code> </code>
  
-* Řešení: +  * Řešení: 
-  * Použít **synchronizační primitiva** – mutexy, atomické operace, semafory apod. +    * Použít **synchronizační primitiva** – mutexy, atomické operace, semafory apod. 
-  * Nebo použít **thread-local** kopie a sloučit je až nakonec.+    * Nebo použít **thread-local** kopie a sloučit je až nakonec.
  
 ==== Deadlock (uváznutí) ==== ==== Deadlock (uváznutí) ====
-* **Uváznutí (deadlock)** nastává, když dvě nebo více vláken čeká na zdroj, který drží to druhé – a žádné se nepohne dál. +  * **Uváznutí (deadlock)** nastává, když dvě nebo více vláken čeká na zdroj, který drží to druhé – a žádné se nepohne dál. 
- +  * Jednoduše řečeno: vlákno A čeká na zámek, který drží vlákno B, a vlákno B čeká na zámek, který drží vlákno A.
-* Jednoduše řečeno: vlákno A čeká na zámek, který drží vlákno B, a vlákno B čeká na zámek, který drží vlákno A.+
  
 Například: Například:
Line 189: Line 182:
 </code> </code>
  
-* Aby deadlock mohl nastat, musí být splněny tyto 4 podmínky (tzv. Coffmanovy podmínky): +  * Aby deadlock mohl nastat, musí být splněny tyto 4 podmínky (tzv. Coffmanovy podmínky): 
-  * **Vzájemné vyloučení** – zdroje nejsou sdílené (jen jedno vlákno je může mít). +    * **Vzájemné vyloučení** – zdroje nejsou sdílené (jen jedno vlákno je může mít). 
-  * **Zadržení a čekání** – vlákno drží jeden zámek a čeká na další. +    * **Zadržení a čekání** – vlákno drží jeden zámek a čeká na další. 
-  * **Neodnímatelnost** – zdroj (zámek) nemůže být násilně odebrán. +    * **Neodnímatelnost** – zdroj (zámek) nemůže být násilně odebrán. 
-  * **Cyklické čekání** – existuje cyklus závislostí mezi vlákny. +    * **Cyklické čekání** – existuje cyklus závislostí mezi vlákny. 
- +  * Prevence: 
-* Prevence: +    * Dodržovat **pevné pořadí zamykání zdrojů**. 
-  * Dodržovat **pevné pořadí zamykání zdrojů**. +    * Používat **timeouty** u zámků. 
-  * Používat **timeouty** u zámků. +    * Využít algoritmy pro **deadlock detection** a recovery.
-  * Využít algoritmy pro **deadlock detection** a recovery.+
  
 ==== False Sharing ==== ==== False Sharing ====
 Nastává, když dvě vlákna přistupují k **různým** proměnným, které se ale nachází ve **stejné cache line**. Nastává, když dvě vlákna přistupují k **různým** proměnným, které se ale nachází ve **stejné cache line**.
- +  * Když jedno vlákno zapíše do své proměnné, CPU invaliduje celou cache line – i když druhé vlákno pracuje na jiné proměnné ve stejné linii. 
-* Když jedno vlákno zapíše do své proměnné, CPU invaliduje celou cache line – i když druhé vlákno pracuje na jiné proměnné ve stejné linii. +  * Pokud se to děje často, dochází k **velkému zpomalení**, protože cache se neustále synchronizuje mezi jádry. 
-* Pokud se to děje často, dochází k **velkému zpomalení**, protože cache se neustále synchronizuje mezi jádry. +  * Řešení: 
- +    * **Zarovnat proměnné** tak, aby každá byla na vlastní cache line (např. pomocí `alignas(64)`). 
-* Řešení: +    * Přidat „padding“ mezi proměnné, které používají různá vlákna.
-  * **Zarovnat proměnné** tak, aby každá byla na vlastní cache line (např. pomocí `alignas(64)`). +
-  * Přidat „padding“ mezi proměnné, které používají různá vlákna.+
  
 ==== True Sharing (není komplikace) ==== ==== True Sharing (není komplikace) ====
 Nastává, když dvě vlákna přistupují ke **stejné** proměnné. Nastává, když dvě vlákna přistupují ke **stejné** proměnné.
- +  * Narozdíl od false sharing je to **žádoucí chování**, pokud víme, co děláme – ale musí být správně synchronizované. 
-* Narozdíl od false sharing je to **žádoucí chování**, pokud víme, co děláme – ale musí být správně synchronizované. +  * Typicky jde o sdílené čítače, fronty, stavové proměnné atd.
-* Typicky jde o sdílené čítače, fronty, stavové proměnné atd. +
  
    
 ===== 3. Podpora paralelního programování v C a C++ ===== ===== 3. Podpora paralelního programování v C a C++ =====
- Existuje více úrovní podpory – od nízkoúrovňových knihoven jako `pthreads` v C, až po elegantní moderní rozhraní ve stylu `std::thread`, `std::jthread`, `std::mutex` nebo `std::atomic` v C++. Pokud chceme psát vícevláknové programy efektivně a bezpečně, je důležité pochopit, kdy a jak jednotlivé nástroje použít – a čím se liší.+Existuje více úrovní podpory – od nízkoúrovňových knihoven jako `pthreads` v C, až po elegantní moderní rozhraní ve stylu `std::thread`, `std::jthread`, `std::mutex` nebo `std::atomic` v C++. Pokud chceme psát vícevláknové programy efektivně a bezpečně, je důležité pochopit, kdy a jak jednotlivé nástroje použít – a čím se liší.
  
 ==== POSIX vlákna (pthreads) ==== ==== POSIX vlákna (pthreads) ====
-* `pthreads` (POSIX Threads) je **standardní rozhraní v jazyku C** pro práci s vlákny. +  * `pthreads` (POSIX Threads) je **standardní rozhraní v jazyku C** pro práci s vlákny. 
-* Poskytuje funkce pro: +  * Poskytuje funkce pro: 
-  * **vytváření vláken**: `pthread_create()` +    * **vytváření vláken**: `pthread_create()` 
-  * **synchronizaci vláken**: +    * **synchronizaci vláken**: 
-    * **mutexy**: `pthread_mutex_lock()`, `pthread_mutex_unlock()` +      * **mutexy**: `pthread_mutex_lock()`, `pthread_mutex_unlock()` 
-    * **podmínkové proměnné**: `pthread_cond_wait()`, `pthread_cond_signal()` +      * **podmínkové proměnné**: `pthread_cond_wait()`, `pthread_cond_signal()` 
-    * **semafory**: `sem_init()`, `sem_wait()`, `sem_post()`+      * **semafory**: `sem_init()`, `sem_wait()`, `sem_post()`
  
 Je to výkonný, ale nízkoúrovňový nástroj – programátor musí vše spravovat ručně. Hodí se pro systémy, kde je důležitá kontrola nad výkonem a kompatibilita se standardem POSIX. Je to výkonný, ale nízkoúrovňový nástroj – programátor musí vše spravovat ručně. Hodí se pro systémy, kde je důležitá kontrola nad výkonem a kompatibilita se standardem POSIX.
  
 ==== std::thread (C++11) ==== ==== std::thread (C++11) ====
-* Od C++11 je k dispozici standardní knihovna pro vlákna – `std::thread`. +  * Od C++11 je k dispozici standardní knihovna pro vlákna – `std::thread`. 
-* Umožňuje jednoduché vytvoření a správu vláken pomocí objektově orientovaného rozhraní. +  * Umožňuje jednoduché vytvoření a správu vláken pomocí objektově orientovaného rozhraní. 
-  * Vlákno spustíme předáním funkce (nebo lambdy) do konstruktoru. +    * Vlákno spustíme předáním funkce (nebo lambdy) do konstruktoru. 
-  * Synchronizace se řeší pomocí `std::mutex`, `std::condition_variable` a dalších primitiv.+    * Synchronizace se řeší pomocí `std::mutex`, `std::condition_variable` a dalších primitiv.
  
 Výhodou oproti `pthreads` je **vyšší přehlednost, typová bezpečnost a integrace s C++ idiomy** (např. RAII, STL, lambdy). Výhodou oproti `pthreads` je **vyšší přehlednost, typová bezpečnost a integrace s C++ idiomy** (např. RAII, STL, lambdy).
  
 ==== std::jthread (C++20) ==== ==== std::jthread (C++20) ====
-* Od C++20 přibyla nová třída `std::jthread`, která automaticky spravuje vlákno. +  * Od C++20 přibyla nová třída `std::jthread`, která automaticky spravuje vlákno. 
-  * Při zničení objektu se vlákno **automaticky ukončí** (`join()` nebo `detach()`). +    * Při zničení objektu se vlákno **automaticky ukončí** (`join()` nebo `detach()`). 
-  * Má vestavěnou podporu pro **zrušení vlákna** pomocí `stop_token`. +    * Má vestavěnou podporu pro **zrušení vlákna** pomocí `stop_token`. 
-  * Výborně se hodí pro práci s **RAII přístupem** a bezpečnější práci s vláknem.+    * Výborně se hodí pro práci s **RAII přístupem** a bezpečnější práci s vláknem.
  
 To znamená, že se snižuje riziko zapomenutého `join()` a tím i potencionálních chyb. To znamená, že se snižuje riziko zapomenutého `join()` a tím i potencionálních chyb.
Line 250: Line 238:
 ==== Mutex a Lock Guard ==== ==== Mutex a Lock Guard ====
 **Mutex** (*mutual exclusion*) je synchronizační nástroj, který **zajišťuje, že jen jedno vlákno přistupuje k určité části kódu najednou** – typicky tzv. *kritické sekci*. **Mutex** (*mutual exclusion*) je synchronizační nástroj, který **zajišťuje, že jen jedno vlákno přistupuje k určité části kódu najednou** – typicky tzv. *kritické sekci*.
- +  * V C++ se používá `std::mutex` a jeho varianty: 
-* V C++ se používá `std::mutex` a jeho varianty: +    * `std::recursive_mutex`, `std::timed_mutex`, …
-  * `std::recursive_mutex`, `std::timed_mutex`, …+
  
 Ukázka (ruční zamykání/odemykání): Ukázka (ruční zamykání/odemykání):
Line 308: Line 295:
 ==== Atomic ==== ==== Atomic ====
 **Atomic** proměnné umožňují provádět operace, které jsou **nedělitelné (atomické)** – tím pádem **bezpečné vůči souběhu**, aniž by bylo potřeba používat mutex. **Atomic** proměnné umožňují provádět operace, které jsou **nedělitelné (atomické)** – tím pádem **bezpečné vůči souběhu**, aniž by bylo potřeba používat mutex.
- +  * V C++ se používá `std::atomic<T>` – kde `T` může být např. `int`, `bool`, pointer apod. 
-* V C++ se používá `std::atomic<T>` – kde `T` může být např. `int`, `bool`, pointer apod. +    * V pozadí to využívá **atomické instrukce CPU** (pokud jsou dostupné), takže jsou **rychlejší než mutexy**. 
- +    * Pokud HW atomické instrukce neumí, fallback je přes mutex.
-  * V pozadí to využívá **atomické instrukce CPU** (pokud jsou dostupné), takže jsou **rychlejší než mutexy**. +
-  * Pokud HW atomické instrukce neumí, fallback je přes mutex.+
  
 V praxi jsou tedy `std::atomic` velmi efektivní pro jednoduché sdílené proměnné – například čítače: V praxi jsou tedy `std::atomic` velmi efektivní pro jednoduché sdílené proměnné – například čítače:
Line 342: Line 327:
 </code> </code>
  
-* Jinými slovy – `std::atomic` je ideální, pokud chceš **rychlou synchronizaci bez složitých zámků**, ale nepotřebuješ složitou logiku jako čekání, notifikace, podmínky apod. +  * Jinými slovy – `std::atomic` je ideální, pokud chceš **rychlou synchronizaci bez složitých zámků**, ale nepotřebuješ složitou logiku jako čekání, notifikace, podmínky apod.
  
 ===== 4. Podpora paralelního programování v OpenMP ===== ===== 4. Podpora paralelního programování v OpenMP =====
Line 350: Line 334:
 ==== Sériově-paralelní model uspořádání vláken (fork-join) ==== ==== Sériově-paralelní model uspořádání vláken (fork-join) ====
 Fork-join model je základní exekuční schéma OpenMP. Program začíná jedním *master* vláknem, které po vstupu do direktivy **`parallel`** vytvoří tým dalších vláken (*fork*). Všechna vlákna spolupracují v daném paralelním regionu a na jeho konci se implicitní bariérou zase spojí do jediného vlákna (*join*). Fork-join model je základní exekuční schéma OpenMP. Program začíná jedním *master* vláknem, které po vstupu do direktivy **`parallel`** vytvoří tým dalších vláken (*fork*). Všechna vlákna spolupracují v daném paralelním regionu a na jeho konci se implicitní bariérou zase spojí do jediného vlákna (*join*).
- +  * Výhody: 
-* Výhody: +    * jednoduchá správa vláken 
-  * jednoduchá správa vláken +    * sdílená paměť 
-  * sdílená paměť +    * předvídatelné chování a synchronizace
-  * předvídatelné chování a synchronizace+
  
 Ukázkový kód: Ukázkový kód:
Line 372: Line 355:
 </code> </code>
  
-* Poznámka: OpenMP vytváří **vlákna**, nikoliv procesy – všechna sdílí paměť. Vlákna jsou obvykle implementována pomocí POSIX/pthreads.+  * Poznámka: OpenMP vytváří **vlákna**, nikoliv procesy – všechna sdílí paměť. Vlákna jsou obvykle implementována pomocí POSIX/pthreads.
  
 Další možnosti a doplňky modelu: Další možnosti a doplňky modelu:
Line 385: Line 368:
 ==== Paralelizovatelná úloha (task region) ==== ==== Paralelizovatelná úloha (task region) ====
 Pomocí direktivy `task` lze definovat úlohy, které mohou být nezávisle spouštěny paralelně. Oproti `parallel for`, které rozděluje smyčku, `task` umožňuje paralelizovat **libovolné části kódu**, včetně rekurze a nepravidelné struktury výpočtu. Pomocí direktivy `task` lze definovat úlohy, které mohou být nezávisle spouštěny paralelně. Oproti `parallel for`, které rozděluje smyčku, `task` umožňuje paralelizovat **libovolné části kódu**, včetně rekurze a nepravidelné struktury výpočtu.
- +  * Tasky lze organizovat do `taskgroup`. 
-* Tasky lze organizovat do `taskgroup`. +  * Pomocí `depend(in|out|inout: var)` lze řídit pořadí a závislosti. 
-* Pomocí `depend(in|out|inout: var)` lze řídit pořadí a závislosti. +  * `detach`, `priority` – umožňují pokročilou kontrolu provádění.
-* `detach`, `priority` – umožňují pokročilou kontrolu provádění.+
  
 Příklad: Příklad:
Line 404: Line 386:
 OpenMP je pouze specifikace – jednotlivé kompilátory ji implementují v různé míře. OpenMP je pouze specifikace – jednotlivé kompilátory ji implementují v různé míře.
  
-*Přehled nejznámějších implementací (stav 2025):* +Přehled nejznámějších implementací (stav 2025):*
   * **GCC 14+ (libgomp)** – `-fopenmp`, verze 5.2 (téměř úplná), open-source klasika.   * **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.   * **Clang 18+ (libomp)** – `-fopenmp`, verze 5.2 (většina), funguje i na Windows.
Line 414: Line 395:
  
 ==== Přehled hlavních direktiv OpenMP ==== ==== Přehled hlavních direktiv OpenMP ====
-* **`#pragma omp parallel`**  +**`#pragma omp parallel`**  
   * Vytvoří tým vláken.   * Vytvoří tým vláken.
   * Podporuje: `num_threads`, `if`, `default`, `shared`, `private`, …   * Podporuje: `num_threads`, `if`, `default`, `shared`, `private`, …
- +**`for` / `do`**  
-* **`for` / `do`**  +
   * Paralelizace smyčky.   * Paralelizace smyčky.
   * Možnosti: `schedule(static|dynamic|guided)`, `collapse(n)`, `reduction`, `nowait`.   * Možnosti: `schedule(static|dynamic|guided)`, `collapse(n)`, `reduction`, `nowait`.
- +**`sections` / `section`**  
-* **`sections` / `section`**  +
   * Spustí nezávislé bloky kódu paralelně (např. různé funkce najednou).   * Spustí nezávislé bloky kódu paralelně (např. různé funkce najednou).
- +**`task`**  
-* **`task`**  +
   * Vytvoří úlohu; možnost specifikace závislostí přes `depend(...)`.   * Vytvoří úlohu; možnost specifikace závislostí přes `depend(...)`.
   * Další klauzule: `priority`, `detach`.   * Další klauzule: `priority`, `detach`.
- +**`barrier`**  
-* **`barrier`**  +
   * Explicitní synchronizační bod – všechna vlákna musí dojít na toto místo.   * Explicitní synchronizační bod – všechna vlákna musí dojít na toto místo.
- +**`critical [(name)]`**  
-* **`critical [(name)]`**  +
   * Zamezí více vláknům vstup do stejné sekce kódu najednou.   * Zamezí více vláknům vstup do stejné sekce kódu najednou.
   * Jméno odděluje různé nezávislé sekce.   * Jméno odděluje různé nezávislé sekce.
- +**`atomic`**  
-* **`atomic`**  +
   * Odlehčená synchronizace pro jednoduché operace s proměnnou (inkrementace, zápis, čtení…).   * Odlehčená synchronizace pro jednoduché operace s proměnnou (inkrementace, zápis, čtení…).
  
Line 475: Line 450:
  
 ==== Statické × dynamické rozdělení práce ==== ==== 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. +  * **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. +    * Např. pomocí `schedule(static[, chunk])` v OpenMP. 
-  * Výhodou je **nízký overhead** (prakticky žádná synchronizace). +    * 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í. +    * 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é. 
-* **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])`. 
-  * Používá se `schedule(dynamic[, chunk])`. +    * Výhodou je lepší **vyvážení zátěže**. 
-  * Výhodou je lepší **vyvážení zátěže**. +    * Nevýhodou je **vyšší režie kvůli synchronizaci**. 
-  * 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. 
-* **Guided plánování** – kompromis mezi statickým a dynamickým: +    * Vhodné pro případy, kdy práce trvá různě dlouho a časem ubývá. 
-  * `schedule(guided[, chunk])` začíná velkými bloky a postupně zmenšuje chunk velikost. +  * Další možnosti: 
-  * Vhodné pro případy, kdy práce trvá různě dlouho a časem ubývá. +    * `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.
-* 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) ==== ==== 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**. +  * 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. +    * 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. 
-* 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ěž**. 
-* **Work-stealing**: pokud vlákno nemá co dělat, zkusí si **„ukrást“ úkol** z cizí fronty. +    * Push/pop na vlastní frontě jsou většinou **lock-free**; zámky se používají jen při krádeži.
-  * 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 ==== ==== Balancování zátěže ====
 Vyrovnané rozdělení práce je klíčem k výkonu paralelního programu. Vyrovnané rozdělení práce je klíčem k výkonu paralelního programu.
- +  * U **smyček**: 
-* U **smyček**: +    * Volba správného `schedule(...)` plánu. 
-  * Volba správného `schedule(...)` plánu. +    * Velikost `chunku` ovlivňuje granularitu přidělené práce. 
-  * 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. 
-  * `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. 
-* U **tasků**: +    * Pomocí `priority(expr)` lze zvýhodnit důležité úkoly. 
-  * Work-stealing pomáhá s dynamickým plánováním. +    * Heuristiky runtime mohou **omezit vznik malých tasků** (např. jejich inline-ing) → lepší škálování.
-  * 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) ==== ==== 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(...)`. 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í: 
-* Typy závislostí: +    * `depend(in: X)` – task **potřebuje** data `X`. 
-  * `depend(in: X)` – task **potřebuje** data `X`. +    * `depend(out: X)` – task **produkuje** data `X`. 
-  * `depend(out: X)` – task **produkuje** data `X`. +    * `depend(inout: X)` – task `X` čte i zapisuje. 
-  * `depend(inout: X)` – task `X` čte i zapisuje. +    * Další pokročilé typy: `mutexinoutset`, `depobj` – pro specializované scénáře.
-  * Další pokročilé typy: `mutexinoutset`, `depobj` – pro specializované scénáře.+
  
 Ukázkový kód: Ukázkový kód:
Line 537: Line 504:
 </code> </code>
  
-* OpenMP runtime si z těchto závislostí **sestaví DAG (acyklický graf)**. +  * 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.+  * 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). 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 ===== ===== 6. Techniky dekompozice programu na příkladech =====
Line 551: Line 516:
  
 === Quick sort === === Quick sort ===
-* **Proč „rozděl a panuj“?**   +  * **Proč „rozděl a panuj“?**   
-  * *Divide*: vybereme pivot a jedním průchodem rozdělíme pole na část < pivot a část ≥ pivot.   +    * *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ů*).   +    * *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í. +    * *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.
-* Paralelizace: po operaci `partition` spustíme levé větvení jako `omp task`, pravé běží ve vlákně dál.+
  
 <code cpp> <code cpp>
Line 579: Line 543:
  
 === Merge sort === === Merge sort ===
-* **Proč „rozděl a panuj“?**   +  * **Proč „rozděl a panuj“?**   
-  * *Divide*: rekurzivní dělení pole na půlky.   +    * *Divide*: rekurzivní dělení pole na půlky.   
-  * *Conquer*: každou půlku řadíme paralelně.   +    * *Conquer*: každou půlku řadíme paralelně.   
-  * *Combine*: dvě seřazené části spojíme lineárním `merge`. +    * *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`.
-* Paralelizace: obě rekurze běží jako tasky, po jejich dokončení proběhne `inplace_merge`.+
  
 <code cpp> <code cpp>
Line 609: Line 572:
  
 === Paralelní násobení matice × vektor (SpMV/Dense MV) === === 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$.   +  * **Princip:** každý prvek $y_i$ je skalární součin řádku $A_i$ a vektoru $x$.   
-  * *Divide*: rozdělíme po řádcích.   +    * *Divide*: rozdělíme po řádcích.   
-  * *Conquer*: každý řádek počítá vlákno nezávisle.   +    * *Conquer*: každý řádek počítá vlákno nezávisle.   
-  * *Combine*: nepotřebujeme – každý výstupní `y[i]` je unikátní. +    * *Combine*: nepotřebujeme – každý výstupní `y[i]` je unikátní. 
- +  * U husté matice: nejlepší přístup po řádcích (row-major).   
-* U husté matice: nejlepší přístup po řádcích (row-major).   +  * U řídké: paralelizace přes nenulové řádky (např. CSR formát).
-* U řídké: paralelizace přes nenulové řádky (např. CSR formát).+
  
 <code cpp> <code cpp>
Line 632: Line 594:
  
 === Paralelní násobení dvou matic === === Paralelní násobení dvou matic ===
-* **Naivní přístup**: každý prvek $c_{ij}$ samostatně – špatná cache-lokalita. +  * **Naivní přístup**: každý prvek $c_{ij}$ samostatně – špatná cache-lokalita. 
- +  
-* **Blokové (tiling) násobení**: +  * **Blokové (tiling) násobení**: 
-  * *Divide*: rozdělíme výstupní matici $C$ na bloky $B_{pq}$. +    * *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)`. +    * *Conquer*: každý blok počítá vlákno/task – např. pomocí `collapse(2)`. 
-  * *Combine*: není třeba – bloky jsou oddělené.+    * *Combine*: není třeba – bloky jsou oddělené.
  
 <code cpp> <code cpp>
Line 647: Line 609:
 </code> </code>
  
-* Pro vysoký výkon: používat BLAS knihovny (OpenBLAS, MKL…) se SIMD a tilingem.+  * 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) === === Paralelní řešení systému lineárních rovnic (Gaussova eliminace) ===
-* **Gaussova eliminace (LU)**: v kroku $k$ odstraňujeme hodnoty pod pivotem $A_{kk}$. +  * **Gaussova eliminace (LU)**: v kroku $k$ odstraňujeme hodnoty pod pivotem $A_{kk}$. 
-  * Paralelizujeme řádky $i = k+1..n-1$. +    * Paralelizujeme řádky $i = k+1..n-1$. 
-  * Nutná synchronizace mezi kroky – `taskwait` nebo sekvenční závislosti.+    * Nutná synchronizace mezi kroky – `taskwait` nebo sekvenční závislosti.
  
 <code cpp> <code cpp>
Line 667: Line 629:
 </code> </code>
  
-* **Iterativní metody (Jacobi, CG, GMRES)**: +  * **Iterativní metody (Jacobi, CG, GMRES)**: 
-  * Lépe paralelizovatelné než Gauss – hlavně `matvec`, vektorové operace, redukce. +    * Lépe paralelizovatelné než Gauss – hlavně `matvec`, vektorové operace, redukce. 
-  * OpenMP poskytuje `reduction(+:)` a `atomic` pro synchronizaci.+    * OpenMP poskytuje `reduction(+:)` a `atomic` pro synchronizaci.
  
-* **Off-load na GPU (OpenMP 5.x)**: +  * **Off-load na GPU (OpenMP 5.x)**: 
-  * Pomocí `target teams distribute parallel for` lze výpočet přenést na GPU. +    * 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í.+    * 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.+===== Distribuované výpočty/systémy ====
  
-Kadý proces má své lokální hodiny, které nemusí ukazovat přesný čas (synchronizace je možná pouze s určitou přesností).+===== 1. Úvod do distribuovaných systémů (DS) ===== 
 +Distribuované systémy (DS) jsou o tom, jak spolupracují **nezávislé výpočetní jednotky**, které spolu **nesdílejí paměť ani hodiny**, ale komunikují pomocí zpráv. Jsou všude kolem nás – od cloudových služeb po blockchain nebo velké paralelní výpočty. Tato kapitola představuje základní charakteristiky DS, problematiku času a přehled typických typů selhání, se kterými musí každý návrh systému počítat.
  
-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.+*Distribuovaný systém je*: 
 +  * soustava **autonomních procesů** spojených sítí, 
 +  * komunikace probíhá **pouze zprávami** (message passing), 
 +  * **žádná sdílená paměť**, **žádné globální hodiny**, 
 +  * procesy mohou **selhávat nezávisle**, 
 +  * každý proces má **lokální hodiny**, které mohou běžet různou rychlostí. 
 + 
 +Kvůli těmto vlastnostem je velmi těžké se v systému spolehlivě orientovat v čase – nemůžeme dát pevný limit na doručení zprávy nebo délku výpočtu. 
 + 
 +==== Asynchronní × Synchronní DS ==== 
 +Tyto modely popisují „jaký svět“ předpokládáme při návrhu distribuovaného algoritmu – tedy **jaké vlastnosti sítí, hodin a chování procesů** budeme brát jako dané.
  
-==== 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 === === Synchronní model ===
-  * **Známe horní hranice** +  * Známe **horní hranice** pro: 
-    * maximální zpoždění zprávy +    * zpoždění zpráv, 
-    * maximální čas mezi dvěma kroky procesu +    * rychlost výpočtu, 
-    * maximální drift lokálních hodin +    * odchylku mezi hodinami. 
-  * Algoritmy můžeme psách v **fázích/kolech** a spolehlivě používat timeouty +  * Můžeme navrhovat algoritmy ve **fázích (kolech)** a spolehlivě používat timeouty. 
-  * V praxi čistě synchroní sétě skoro neexistují+  * Takto předvídatelné sítě se v praxi téměř **nevyskytují** – je to spíš teoretický model. 
 === Asynchronní model === === Asynchronní model ===
-  * **Žádné limity** – zpráva může bloudit libovolně dlouho, proces může +  * **Žádné záruky** – zpráva může zůstat „viset“ libovolně dlouho, proces se může libovolně zdržet, hodiny se mohou rozjet. 
-    běžet tak pomalu, jak chce, hodiny se mohou rozejít. +  * Timeouty **nejsou spolehlivé** – nelze říct, jestli se proces „jen zpozdil“ nebo opravdu „spadl“. 
-  * Timeout tedy **nemůže spolehlivě rozlišit** „zpomalení“ od „pádu“. +  * Například slavný důkaz **FLP** ukazuje, že **v asynchronním modelu není možný deterministický konsensus**, pokud může padnout byť jen jeden proces.
-  * 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í“.  +
-  +
  
 +=== Částečně synchronní model ===
 +  * Realistický kompromis:
 +    * Systém se může nějakou dobu chovat asynchronně, **ale nakonec se „ustálí“** a začne dodržovat limity.
 +  * Většina reálných protokolů (např. **Raft**, **PBFT**) počítá právě s tímto modelem.
 +  * Výhoda: **odolnost vůči výpadkům i výkyvům**, ale **zaručená dohoda** nakonec proběhne.
  
-  - Selhání procesu +==== Typy selhání v distribuovaných systémech ==== 
-    * crash / fail-stop - proces přestane vykonávatz algoritmus +V DS musíme počítat s tím, že **něco selže** – a často i nepozorovaně. Rozlišujeme:
-    * 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: +  * **Selhání procesu**: 
-Spolehlivé doručování, žádná duplikace, žádné vytváření, garantované pořadí doručování+    * *crash / fail-stop* – proces přestane fungovat (nic už neposílá). 
 +    * *byzantské (libovolné) selhání* – proces dál funguje, ale **chybně** (např. posílá nesmysly, nebo se chová škodlivě). 
 +  * **Selhání kanálu**: 
 +    * *ztráta zprávy* – zpráva se ztratí v síti. 
 +    * *partitioning* – síť se rozdělí na **oddělené oblasti**, které spolu **nemohou komunikovat**. 
 +  * **Selhání časování**: 
 +    * odezva procesu nebo zprávy překročí **očekávané časové limity** – může jít o zpoždění i výpadek.
  
-===== Detekce selhání v DS ===== +==== Předpoklady na komunikační kanál ==== 
-**detektory selhání a jejich vlastnosti**+Distribuované algoritmy často **předpokládají vlastnosti komunikační vrstvy** – obvykle se uvažuje tzv. „ideální, ale pomalá“ síť:
  
-**úplnost** - každé selhání je časem detekováno alespoň jedním bezvadným procesem+  * **spolehlivé doručení** – žádné ztráty zpráv, 
 +  * **žádné duplikace** – zprávy se nedoručují víckrát, 
 +  * **žádné falešné zprávy** – proces nemůže dostat zprávu, kterou nikdo neposlal, 
 +  * **zachování pořadí** – zprávy mezi dvěma procesy dorazí ve stejném pořadí, v jakém byly odeslány.
  
-**přesnost** - nedochází k mylné detekci+Tato vlastnosti se často **simulují vyšší vrstvou (např. TCP)**, ale ne vždy – a je třeba s tím počítat při návrhu protokolu.
  
-nelze dosáhnout obou vlastností současně, je vyžadována  100% úplnost a $\lt$ 100% přesnost.+===== 2. Detekce selhání v DS ===== 
 +V distribuovaných systémech je běžné, že některé procesy selžou – a aby systém mohl dál správně fungovat, ostatní uzly se to musí nějak **včas a spolehlivě dozvědět**. K tomu slouží tzv. **detektory selhání**, které monitorují ostatní uzly (např. pomocí heartbeat zpráv) a označují ty, které nereagují, jako havarované.
  
 +Jenže v distribuovaném prostředí nemáme jistotu, jestli uzel selhal, nebo je jen dočasně pomalý (např. síťová prodleva) – a proto je detekce selhání **zásadně nejistá**. Tato kapitola rozebírá vlastnosti detektorů selhání, různé typy heartbeat protokolů a praktický algoritmus SWIM.
  
 +==== Vlastnosti detektorů selhání ====
 +  * **Úplnost (completeness)**  
 +    * Každé skutečné selhání je **časem detekováno** alespoň jedním bezchybným uzlem.
 +  * **Přesnost (accuracy)**  
 +    * Detektor **nemá falešné poplachy** – neoznačí proces za havarovaný, pokud ve skutečnosti běží.
  
-Frekvence selhání roste lineárně s počtem procesů ve skupině (selhání jsou běžná)+Nelze zaručit obě vlastnosti zároveň (dle FLP výsledku) – proto většina systémů **upřednostňuje úplnost**, i když občas dojde k mylné detekci.  
  
-Dva podprotokoly - detekce selhání a šíření informace o selhání+Jinými slovy: **lepší je omylem někoho považovat za mrtvého, než si nevšimnout, že skutečně spadl**.
  
-Průběh detekce: +  * Frekvence selhání v praxi roste **lineárně s počtem uzlů** – tj. v systému se stovkami uzlů je běžné, že některé z nich selžou v každém okamžiku.
-  - 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í:+==== Průběh detekce ==== 
 +  - Proces $p_j$ selže. 
 +  - Jiný proces $p_k$ jeho selhání **zjistí** (např. nepřišel heartbeat). 
 +  - Proces $p_k$ **šíří informaci** o selhání $p_j$ dalším uzlům – podle typu protokolu. 
 + 
 +==== Typy detekčních protokolů ====
  
 === Centralizovaný heartbeat === === Centralizovaný heartbeat ===
-Heartbeat jsou odesílány periodicky, každých $\mathcal{T}$ jednotek času jednomu vybranému procesu $p_j$+  * Každý uzel **periodicky posílá heartbeat** jednomu vybranému procesu $p_j$ každých $\mathcal{T}$ jednotek času. 
 +  * $p_j$ si udržuje čítač a čas posledního přijetí od každého uzlu. 
 +  * Pokud nedorazí heartbeat během $\tau$ → $p_i$ je považován za selhaný.
  
-Heartbeat má pořadové číslo, to odeslání heartbeatu je inkrementován lokální čítač pro každý proces+**Vlastnosti:** 
 +  * Jednoduchá implementace. 
 +  * **Nezjistí selhání $p_j$ samotného** – není nikdo, kdo by ho hlídal. 
 +  * $p_j$ může být **přetížen**, pokud systém obsahuje hodně uzlů.
  
-Pokud není heartbeat od $p_i$ přijat v $p_j$ v časovém limitu $\tau$, je $p_i$ označen jako havarovaný+=== Kruhový heartbeat === 
 +  * Každý proces periodicky posílá heartbeat **sousedovi** v kruhu. 
 +  * Lze použít **jednosměrný** nebo **obousměrný** kruh.
  
-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.+**Vlastnosti:** 
 +  * Není žádný centrální bod → lepší škálování. 
 +  * **Není úplný**, pokud selže jeden (v jednosměrném) nebo dva (v obousměrném) uzly. 
 +  * Nutno **udržovat kruhovou topologii** – složitější údržba.
  
 +=== All-to-all heartbeat ===
 +Každý uzel **periodicky odesílá heartbeat všem ostatním**.
  
-=== Kruhový heartbeat === +**Vlastnosti:** 
-Heartbeats jsou odesílány periodicky sousedům každého procesu (jednostranně nebo oboustranně).+  * **Vysoká úplnost** – každý je hlídán všemi. 
 +  * Rovnoměrná zátěž mezi uzly. 
 +  * **Nízká přesnost** – síťové zpoždění může vést k falešnému označení za mrtvého. 
 +  * **Velké zatížení sítě** – škáluje špatně pro stovky uzlů.
  
-  * není centrální uzel +=== SWIM protokol ===   
-  * není úplné při selhání více procesů (stačí jeden u jednosměrného, 2 u obousměrného) +**Scalable Weakly-consistent Infection-style Membership**
-  * je třeba udržovat kruhovou hierarchii+
  
-=== All to all heartbeat === +Moderní přístup k detekci, který **škáluje a je adaptivní**.
-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 === +Každý proces $p_i$ periodicky: 
-**Scalable weakly consistent infection-style proces group membership protocol**+  - Posílá `ping` náhodnému uzlu $p_j$ a čeká na `ack`. 
 +  - Pokud žádná odpověď nepřijde, požádá $\mathcal{K}$ jiných uzlů, aby se zeptaly místo něj (`ping_req`). 
 +  - Tyto uzly pingnou $p_j$, a pokud odpověď dostanou, pošlou ji zpět $p_i` jako `ping_ack`. 
 +  - Pokud nikdo z $\mathcal{K}$ nedostane odpověď → $p_j$ je označen za mrtvého.
  
-  * proces $p_i$ periodicky odesílá zprávu $\texttt{ping}$ náhodně vybranému uzlu $p_j$ a čeká na odpověď $\texttt{ack}$ +**Vlastnosti:** 
-  * pokud ji nedostance, odešle zprávu $\texttt{ping\_req}$ $\mathcal{K}$ náhodně vybraným uzlům +  * **Přesnost** lze nastavit volbou $\mathcal{K}$ – roste s $\mathcal{K}$, chybovost klesá exponenciálně. 
-  * tyto uzly se zeptají $p_j$ pomocí zprávy $\texttt{ping}$ a pokud dostanou odpověď, odešlou ji $p_i$ jako $\texttt{ping\_ack}$ +  * **Úplnost** je zaručena. 
-  * pokud ani jeden z $\mathcal{K}$ uzlů nedostane odpověď, označí $p_i$ $p_j$ jako havarovaný+  * **Průměrný čas detekce**: 
 +  * $\frac{e}{e - 1} \mathcal{T}$ 
 +    * průměrná délka detekčního cyklu v SWIM protokolu 
 +  * Dobře funguje i ve velkých systémech (1000+ uzlů).
  
-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}$+===== 3. Čas a kauzalita v DS ===== 
 +V běžném programu máme přesné hodiny, které říkají, kdy se co stalo. V distribuovaném systému ale žádné „společné“ hodiny nemáme – každý uzel má své vlastní a běží jinak rychle. Proto je v DS mnohem důležitější **pořadí a závislosti událostí** než konkrétní čas. V této kapitole si vysvětlíme, jak fungují fyzické a logické hodiny, co znamená synchronizace a jak se sleduje kauzalita mezi událostmi.
  
-===== Čas a kauzalita v DS ===== +==== Problémy s časem v DS ==== 
-**uspořádání událostí v DS, fyzické hodiny a jejich synchronizace, logické hodiny a jejich synchronizace**+  * **Clock slew** – rozdíl ve skutečném čase mezi dvěma procesy. 
 +  * **Clock drift** – rozdíl v rychlosti běhu hodin (jeden proces má hodiny „rychlejší“ nebo „pomalejší“ než druhý). 
 +  * To znamená, že hodiny **nelze úplně sladit**, jen přiblížit.
  
-clock slew - rozdíl v času hodin dvou procesů, mají li dvoje hodiny nenulovou mimoběžnost, jsou nesynchronizované+==== Synchronizace hodin ==== 
 +Synchronizace může být:
  
-clock drift - rozdíl v rychlosti hodin dvou procesů+=== Externí synchronizace === 
 +  * Každý proces $p_i$ má své hodiny $\mathcal{C}_i$ udržované v rozmezí $\delta$ od nějakého **externího referenčního času** $\mathcal{S}$. 
 +    * Např. atomové hodiny, UTC, NTP servery. 
 +    * $|\mathcal{C}_i - \mathcal{S}| \leq \delta$ 
 +      * Každý uzel se snaží držet v intervalu $\delta$ od globálního času 
 +  * Typický příklad: **NTP (Network Time Protocol)**.
  
-synchronizace +=== Interní synchronizace === 
-  * externí +  * Zajišťuje, že hodiny **každého páru procesů** se liší nanejvýš o $\delta$. 
-    * č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$) +    * Formálně: $|\mathcal{C}_i - \mathcal{C}_j| \leq \delta$ 
-    * externí hodiny mohou být napojeny na UTC nebo atomové hodiny +      * Rozdíl mezi hodinami dvou uzlů je nejvýše $\delta$ 
-    * například NTP +  * Není vázaná na žádný „reálný čas“, ale zajistí, že uzly se navzájem „drží při sobě“. 
-  * interní +  * Např. **Berkeley algorithm**.
-    * 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)+==== Praktické algoritmy pro synchronizaci ====
  
-Cristianův algoritmus +=== Cristianův algoritmus === 
-$$ \mathcal{C}_i \coloneq t + \frac{\mathcal{T}_\text{RT}-l_{\text{min}+l'_{min}}}{2}$$ +  * Klient se zeptá serveru: *„Kolik je hodin?“* 
-chyba je omezena, tj maximálně $\frac{\mathcal{T}_\text{RT} - l_{\text{min}} - l'_{\text{min}}}{2}$+  * Server odpoví, a klient si upraví svůj čas podle:
  
-lokální čas lze posunou libovolně dopředu, ale ne dozadu, je možné zvýšit nebo snížit rychlost hodin+$\mathcal{C}_i := t + \frac{\mathcal{T}_{RT} - l_{\text{min}} - l'_{\text{min}}}{2}$ 
 +  * RTT mínus odhadnutá minimální latence tam i zpět, děleno dvěma
  
-NTP +Očekávaná **chyba synchronizace** je: $\leq \frac{\mathcal{T}_{RT} - l_{\text{min}} - l'_{\text{min}}}{2}$
-  * 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+Lokální čas lze zvyšovat okamžitě, ale **nelze ho vracet zpět** – místo toho se mění rychlost přibývání.
  
-kauzální vztah - první událost může ovlivnit druhou+=== NTP === 
 +  * Servery tvoří **stromovou hierarchii** (stratum 0, 1, 2, …). 
 +  * Uzly synchronizují čas s rodiči i některými sousedy. 
 +  * Latence se odhaduje pomocí offsetu:
  
-Relace stalo se před +$o = \frac{(t_1^{r} - t_2^{r} + t_2^{s} - t_1^{s})}{2}$ 
-  - 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}$ +  * vypočtený odhad ofsetu mezi hodinami klienta a serveru
-  - 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 +==== Logické hodiny a kauzalita ==== 
-  * relace stalo se před zavádí částečné uspořádání událostí, potenciální kauzální závislosti +Logické hodiny nejsou o „skutečném čase“, ale o **pořadí událostí**. Nepotřebují žádnou synchronizaci – pouze konzistentní značkování událostí podle „co mohlo ovlivnit co“.
-  * $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+=== Kauzální vztah – relace „stalo se před“ (→) === 
 +Událost $\mathcal{A}$ **mohla ovlivnit** událost $\mathcal{B}$, pokud:
  
-Synchronizace logických hodin +  * $\mathcal{A} \rightarrow \mathcal{B}$ – pokud obě nastaly ve stejném procesu a $\mathcal{A}$ byla dřív, 
-  - po každé události která se odehraje v $p_i$ se hodiny $\mathcal{C}_i$ inkrementují o 1 +  * nebo $\mathcal{A}$ je odeslání zprávy a $\mathcal{B}$ je její přijetí, 
-  - každé zprávě $m$ odeslané procesem $p_i$ je přiřazená časová značka $ts(m) = \mathcal{C}_i$ +  * nebo (tranzitivně): $\mathcal{A} \rightarrow \mathcal{B} \rightarrow \mathcal{C}$ ⇒ $\mathcal{A} \rightarrow \mathcal{C}$
-  - 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! +=== Kauzální nezávislost === 
-  * Platí: jestliže $e_1 \rightarrow e_2$, pak $\mathcal{C}(e_1) \lt \mathcal{C}(e_2)$ +  * Události $e_1$, $e_2$ jsou **současné** (nezávislé), pokud:  $$ e_1 \parallel e_2 $$ 
-  * Neplatí: jestliže $\mathcal{C}(e_1) \lt \mathcal{C}(e_2)$, pak $e_1 → e_2$+  * Jinými slovy: žádná z nich nemohla ovlivnit druhou.
  
-Vektorové hodiny - každý proces si udržuje vektor celočíselných hodin ostatních procesů+=== Lamportovy logické hodiny === 
 +Každý proces si udržuje **číselnou hodnotu svých hodin**: 
 +  * Při každé lokální události: $\mathcal{C}_i := \mathcal{C}_i + 1$ 
 +  * Při odeslání zprávy $m$:  zpráva dostane časovou značku $ts(m) := \mathcal{C}_i$ 
 +  * Při přijetí zprávy $m$ procesem $p_j$:  $$ \mathcal{C}_j := \max(\mathcal{C}_j, ts(m)) + 1 $$
  
-===== Globální stav v DS a jeho výpočet ===== +Důležité:   
-**řez distribuovaného výpočtu, algoritmus pro distribuovaný globální snapshot, stabilní vlastnosti DS**+  * Jestliže $e_1 \rightarrow e_2$, pak $\mathcal{C}(e_1) < \mathcal{C}(e_2)$ 
 +  * Ale: $\mathcal{C}(e_1) < \mathcal{C}(e_2)$ **neznamená**, že $e_1 \rightarrow e_2$
  
-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+⇒ Lamportovy hodiny **respektují kauzalitu**, ale **neumí ji zpětně ověřit**.
  
-globální snapshot je záznam globálního stavu+=== Vektorové hodiny === 
 +Abychom **přesně zachytili kauzalitu**, každý proces si udržuje **vektor hodin**, kde každý prvek reprezentuje „jaký čas vím o ostatních“:
  
-například +  * Vektor $V_i$ proces $p_i$ má délku $n$ (počet procesů). 
-  * garbage collection +  * Při každé lokální události: $V_i[i] += 1$ 
-  * deadlock detection +  * Při odeslání zprávy se posílá kopie $V_i$ 
-  * detekce ukončení výpočtu +  * Při přijetí zprávy $m$ se provede prvek po prvku: $$ V_i[j] := \max(V_i[j], V_m[j]) \quad \text{pro všechna } j $$  a poté $V_i[i] += 1$
-  * checkpointing+
  
-Řez - časová hranice v každém procesu a v každém komunikačním kanále +Událost $e_1$ předchází $e_2$ **ve vektorovém čase**, pokud: $$ V(e_1)[k] \leq V(e_2)[k] \ \forall k \text{ a alespoň jedna nerovnost je ostrá} $$
-  * 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í: +To už umí odhalit **kauzální závislost i nezávislost**. 
-$$ 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)+ 
 +===== 4. Globální stav v DS a jeho výpočet ===== 
 +V distribuovaném systému neexistuje globální hodina ani centrální pohled na „okamžitý stav celého systému“. Přesto někdy potřebujeme **získat konzistentní snímek stavu** všech procesů a kanálů – třeba pro detekci uváznutí, garbage collection nebo checkpointing. Tato kapitola vysvětluje, co znamená **řez distribuovaného výpočtu**, jak funguje **Chandy-Lamportův algoritmus** pro získání globálního snapshotu a co jsou **stabilní vlastnosti** systému. 
 + 
 +==== Co je globální stav a snapshot ==== 
 + 
 +**Globální stav** je: 
 +  * množina **lokálních stavů všech procesů** + 
 +  * stav **všech komunikačních kanálů**   
 +  * … ve stejném (logickém) okamžiku 
 + 
 +**Globální snapshot** je **záznam** takového stavu, který může být analyzován mimo běžící systém (např. logicky, offline). 
 + 
 +Použití: 
 +  * **garbage collection** – rozhodnutí, že objekt už není dosažitelný 
 +  * **detekce deadlocku** 
 +  * **ukončení výpočtu** 
 +  * **checkpointing** – ukládání stavu pro případ obnovení 
 + 
 +==== Řez distribuovaného výpočtu ==== 
 + 
 +**Řez (cut)** definuje: 
 +  * **časový okamžik** v každém procesu a 
 +  * **hranicí** mezi tím, co se „už stalo“, a tím, co „teprve nastane“ 
 + 
 +Události, které nastanou **před řezem**, do něj patří; zbytek je mimo. 
 + 
 +=== Konzistentní řez === 
 +Řez $\mathcal{Ř}$ je **konzistentní**, pokud: $$ f \in \mathcal{Ř} \land e \rightarrow f \implies e \in \mathcal{Ř} $$   
 + 
 +Jinými slovy: **jestliže obsahuje důsledek, musí obsahovat i příčinu**.   
 +  * Nelze, aby byl v řezu příjem zprávy, ale ne její odeslání. 
 + 
 +Konzistentní řez je tedy **logický okamžik**, který by mohl být zpozorován „zvenčí“.
  
-konzistentní řez = logický okamžik 
  
 {{statnice:bakalar:rezy.png?500}} {{statnice:bakalar:rezy.png?500}}
Line 868: Line 899:
 {{statnice:bakalar:rezy2.png?500}} {{statnice:bakalar:rezy2.png?500}}
  
-Chamdy-Lamport algoritmus pro distribuovaný globální snapshot +==== Algoritmus pro distribuovaný snapshot (Chandy-Lamport) ==== 
-  - (Vytváření snapshotu je distribuované.) +Chandy-Lamport algoritmus umožňuje **distribuovaným procesům získat konzistentní snapshot**, aniž by existovalo globální hodiny. 
-  - Speciální zpráva: ZNAČKA ▪ + 
-  - Jeden (libovolný) z procesů iniciuje vytvoření snapshotů. +**Základní princip:** 
-  - Procesy reagují na příjem zprávy ZNAČKA ▪ +  * Procesy si **lokálně zaznamenají** svůj stav. 
-  - výsledkem je konzistentní řez+  * Stav kanálů mezi nimi se zjistí pomocí **speciální zprávy**: `ZNAČKA ▪`. 
 +  * Algoritmus je **asynchronní** a **neblokující** – každý proces koná na základě přijatých značek. 
 + 
 +**Průběh:** 
 +  - Jeden proces iniciuje snapshot – uloží si stav a pošle `ZNAČKA ▪` všem sousedům. 
 +  - Když jiný proces obdrží `ZNAČKA ▪` poprvé: 
 +      * uloží svůj stav, 
 +      * pošle `ZNAČKA ▪` dál, 
 +      * vše, co do té doby přišlo na kanálu, **patří do snapshotu**. 
 +  - Pokud přijde `ZNAČKA ▪` na kanál, u kterého už máme stav procesu, ale ne kanálu → zprávy mezi tím patří do snapshotu. 
 +Výsledkem je **konzistentní globální snapshot**.
  
 {{statnice:bakalar:03_globalni_snapshot_2023.pdf|ilustrace algoritmu slide 15-21}} {{statnice:bakalar:03_globalni_snapshot_2023.pdf|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 +==== Stabilní vlastnosti ====
-  * 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//+**Stabilní vlastnost** je taková, že když začne platit, **zůstává platná navždy**. 
 +  * Příklady: 
 +    * výpočet skončil 
 +    * došlo k uváznutí 
 +    * objekt je sirotek (už nikdy nebude dosažen)
  
-Chandy-Lamport snapshotů algoritmus lze použít pro detekci stabilních globálních vlastností: +**Nestabilní vlastnost**: 
-  * Je daná stabilní vlastnost V splněna v globálním snapshotu zachyceným snapshot algoritmem? +  * např. „žádný proces neselhal“ – může přestat platit. 
-    - 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.+=== Kontrola stabilní vlastnosti pomocí snapshotu === 
 +Chandy-Lamport algoritmus lze využít pro **detekci stabilních vlastností**: 
 + 
 +Chceme vědět, jestli nějaká stabilní vlastnost $\mathcal{V}$ v systému **nastala**. 
 +  * Pokud **platí v globálním snapshotu**, pak: 
 +    * Platila už i ve skutečném systému v okamžiku **ukončení** snapshotu. 
 +  * Pokud **neplatí v snapshotu**, pak: 
 +    * Nemohla platit ani **v okamžiku zahájení** snapshotu. 
 + 
 +Snapshot tedy vytváří **spolehlivý časový úsek**, během kterého můžeme ověřit trvalost vybraných vlastností.
  
 ===== Vzájemné vyloučení procesů v DS ===== ===== Vzájemné vyloučení procesů v DS =====
 **algoritmy pro vyloučení procesů a jejich vlastnosti** **algoritmy pro vyloučení procesů a jejich vlastnosti**
 +
 +V distribuovaných systémech nemáme sdílenou paměť ani centrální plánovač. Pokud chceme zajistit, že do tzv. **kritické sekce** vstupuje vždy jen jeden proces, potřebujeme speciální algoritmy pro **vzájemné vyloučení**. Tato kapitola popisuje základní problém, požadavky na jeho řešení a několik klíčových algoritmů včetně jejich výhod a nevýhod.
  
 ==== Problém vzájemného vyloučení ==== ==== Problém vzájemného vyloučení ====
-<markdown> +  * Kritická sekce je část programu, do které smí vstoupit v daný okamžik právě jeden proces – např. pro aktualizaci sdíleného stavu. 
-- *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 +  * V distribuovaném prostředí je nutné **synchronizovat přístup přes zprávy**. 
-- Definujeme funkce *enter()* a *exit()* pro vstup a výstup do kritické sekce +  * Algoritmus poskytuje dvě základní operace: 
-- 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 +    * `enter()` – požádá o vstup do kritické sekce 
-</markdown>+    * `exit()` – opustí kritickou sekci 
 ==== Požadavky na algoritmus pro vyloučení procesů ==== ==== Požadavky na algoritmus pro vyloučení procesů ====
-<markdown>+  * **Bezpečnost**: nikdy není více než jeden proces v kritické sekci současně. 
 +  * **Živost**: každý požadavek na vstup do kritické sekce je časem uspokojen. 
 +  * **Uspořádání (volitelné)**: pokud jeden požadavek kauzálně předchází jinému, měl by být obsloužen dříve. 
 +  * Předpoklady: 
 +    * procesy neselhávají 
 +    * komunikace je spolehlivá (FIFO, bez ztrát, bez duplicit) 
 +    * systém je **asynchronní** s konečnou latencí
  
-- *Bezpečnost* - Nejvýše jeden proces v kritické sekci +==== Analýza výkonnosti algoritmů ==== 
-- *Živost* - Každý požadavek na vstup kritické sekce je časem uspokojen +  * **Komunikační zátěž** – kolik zpráv je potřeba pro každý vstup/výstup do KS 
-- *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 +  * **Zpoždění klienta** – čas od požadavku po vstup, pokud nikdo jiný nečeká 
-- 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í +  * **Synchronizační zpoždění** – čas mezi výstupem jednoho procesu a vstupem dalšího
-</markdown> +
- +
-==== Analýza výkonnosti algoritmů pro vzájemné vyloučení ==== +
-<markdown> +
- +
-- *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 +
-</markdown>+
  
 ==== Centralizovaný algoritmus ==== ==== Centralizovaný algoritmus ====
-<markdown>+  * Jeden proces slouží jako **koordinátor** a spravuje **token**. 
 +  * Proces žádá koordinátora o token; po jeho získání vstoupí do kritické sekce. 
 +  * Po výstupu token vrací. 
 +  * Token je předáván podle fronty požadavků.
  
-- Je zvolen jeden koordinátor +**Vlastnosti:** 
-- Ten spravuje speciální token, který držiteli umožní vstup do KS a frontu požadavků na vstup do KS +  * Bezpečnost i živost zaručena. 
-- Před vstupem do KS je poslán požadavek na token koordinátorovi, po přijetí tokenu algoritmus vstupuje do kritické sekce +  * Komunikační zátěž: 2 zprávy (žádost + token) pro vstup, 1 pro výstup. 
-- Po výstupu je token vrácen koordinátorovi +  * Zpoždění klienta: 2 latence. 
-- 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 +  * Synchronizační zpoždění: 2 latence. 
-- Ve chvíli kdy koordinátor obdrží token tak zkontroluje frontu zda tam není žádný požadavek a případně jej obslouží +  * Nevýhoda: **koordinátor je single point of failure**.
-- 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 +
-</markdown>+
  
 ==== Kruhový algoritmus ==== ==== Kruhový algoritmus ====
-<markdown>+  * Procesy jsou uspořádány v logickém kruhu. 
 +  * Jeden **token** obíhá dokola. 
 +  * Proces vstupuje do kritické sekce až po přijetí tokenu. 
 +  * Pokud token nepotřebuje, rovnou ho předá dál.
  
-- N procesů v kruhu +**Vlastnosti:** 
-- Proces může poslat zprávu následníkovi +  * Komunikační zátěž: až $N$ zpráv při čekání na token. 
-- Mezi procesy koluje jeden token +  * Zpoždění klienta: 0 až $N$ latencí. 
-- Před vstupem proces čeká dokud neobdrží token +  * Synchronizační zpoždění: 1 až $N-1$ latencí. 
-- Po vstupu proces pošle token následníkovi +  * Výhoda: žádný centrální uzel. 
-- Pokud proces obdrží token a nečeká na vstup, tak jej hned předá dále +  * Nevýhoda: token může „zabloudit“ nebo se ztratit.
-- 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í +
-</markdown>+
  
 ==== Ricart-Agrawalův algoritmus ==== ==== Ricart-Agrawalův algoritmus ====
-<markdown> +  * Nepoužívá token – pracuje pomocí **multicastu a logických hodin**. 
-- Nepoužívá token, ale kauzalitu a multicast +  * Každý proces si udržuje: 
-- Nižší synchronizační zpoždění než kruhový algoritmus a nepoužívá centrální proces +    * stav (*RELEASED*, *WANTED*, *HELD*) 
-- 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) +    * frontu odložených žádostí 
-1. identifikátor kritické sekce, kterou zamyká, +  * Pro vstup do kritické sekce: 
-1. stav: *RELEASED*, *HELD* nebo *WANTED*, a +    * proces pošle `REQUEST` všem, zaznamená čas 
-1. frontu odložených požadavků.+    * čeká na odpovědi `OK` od všech 
 +  * Ostatní procesy odpoví podle kauzálního (Lamportova) času
  
-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`+<code cpp> 
 +// schéma odpovědi na REQUEST(K) 
 +if (stav == HELD || (stav == WANTED && (můj_čas < jejich_čas || (můj_čas == jejich_čas && můj_id < jejich_id)))) { 
 +    odlož požadavek; 
 +} else { 
 +    pošli OK; 
 +} 
 +</code>
  
-1. 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*. +  * Po ukončení práce v kritické sekci proces: 
-1. 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*. +    * přepne stav na RELEASED 
-1. Pokud procesu `P[j]` přijde zpráva `REQUEST(K)` od procesu `P[i]` s časem `T[i]`, tak  +    * pošle OK na všechny odložené požadavky
- - 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]`. +
-1. 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 +**Vlastnosti:** 
-- Je zachováno pořadí, požadavky s nižší lamportovou značkou mají přednost +  * Komunikační zátěž: 
-- Komunikační zátěž – $2(N-1)$ při vstupu, až $(N-1)$ při výstupu +    * $2(N-1)$ zpráv při vstupu (REQUEST + OK) 
-- Zpoždění klienta – **2** latence +    * až $(N-1)$ zpráv při výstupu (zpracování fronty) 
-- Synchronizační zpoždění – 1 latence +  * Zpoždění klienta: 2 latence 
-</markdown>+  * Synchronizační zpoždění: 1 latence 
 +  * Výhoda: **zcela decentralizovaný**, deterministický 
 +  * Nevýhoda: **vysoký počet zpráv**
  
 ===== Volba lídra v DS ===== ===== Volba lídra v DS =====
 **algoritmy pro volbu lídra a jejich vlastnosti** **algoritmy pro volbu lídra a jejich vlastnosti**
-<markdown> + 
-- Cílem je, aby se všechny procesy shodly na jednom „koordinátorovi“ (lídrovi).   +V distribuovaném systému často potřebujeme zvolit jeden proces, který bude působit jako koordinátor – například pro synchronizaci, správu zámků nebo organizaci úkolů. Jelikož uzly mohou selhávat, musí volba probíhat robustně a bez centrální autority. 
-- 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). +Cílem algoritmu pro **volbu lídra** je zajistit, aby: 
-</markdown>+  * všechny živé procesy se **shodly na jednom lídrovi**, 
 +  * nezáleželo na tom, kdo volbu zahájil, 
 +  * více paralelních voleb nakonec **konvergovalo k jedné**. 
 + 
 +Předpokládáme: 
 +  * spolehlivé doručování zpráv (žádné ztráty ani duplicity), 
 +  * možnost selhání procesů (typicky crash), 
 +  * procesy mají unikátní ID (číselné) a dokážou je mezi sebou porovnat.
  
 ==== Kruhový algoritmus (Ring) ==== ==== Kruhový algoritmus (Ring) ====
-<markdown> +  * Procesy jsou logicky uspořádány do kruhu (např. podle ID). Každý zná svého následníka a umí ho kontaktovat. 
-- Procesy tvoří logický kruh uspořádaný podle ID. Každý zná svého **následníka** a umí zjistit, zda soused žije.   +  * Při podezření na pád lídra (např. po timeoutu) proces $P_i$ zahájí volby: 
-- **Start**: proces $P_i$ detekuje pád lídra a pošle zprávu `ELECTION(i)` svému následníkovi.   +    * pošle `ELECTION(i)` svému následníkovi. 
-- **Přijetí `ELECTION(j)`** u $P_i$   +    * pokud příjemce dostane `ELECTION(j)`: 
-  - pokud $j > i$: předá zprávu dál beze změny;   +      * pokud $j > i$, předá dál beze změny, 
-  - pokud $j < i$: nahradí $j$ svým ID a pošle `ELECTION(i)`;   +      * pokud $j < i$, nahradí vlastním ID a pošle dál, 
-  - pokud $j = i$: zpráva oběhla kruh ⇒ $P_i$ má nejvyšší ID ⇒ je vítěz. +      * pokud $j = i$, zpráva oběhla kruh ⇒ $P_i$ má nejvyšší ID ⇒ 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. +  * Nový lídr pak vyšle `ELECTED(i)` kolem kruhu → všichni si uloží nového lídra. 
-- **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í. + 
-</markdown>+**Vlastnosti:** 
 +  * Komunikační složitost: $\mathcal{O}(n)$ 
 +  * Funguje správně i při více paralelních volbách 
 +  * Zvítězí proces s nejvyšším ID 
 +  * Nevyžaduje globální znalost všech procesů
  
 ==== Algoritmus Bully ==== ==== Algoritmus Bully ====
-<markdown> +  * Procesy jsou propojeny do **úplné sítě** – každý zná každého. 
-- **Assumpce**: úplná síť (každý zná všechny), procesy se dají porovnat dle ID; detekce pádu je „rychlá“ (time-outs).   +  * Pokud $P_i$ zjistí, že koordinátor mlčí (timeout), zahájí volby: 
-- **Kroky (z pohledu procesu $P_i$)**   +  - Pošle `ELECTION` všem **procesům s vyšším ID** 
-  1. $P_i$ zjistí, že koordinátor neodpovídá.   +  - Pokud žádný neodpoví → $P_i$ se **prohlásí lídrem** 
-  2. Pošle `ELECTION` *všem* procesům s **vyšším** ID.   +  - Pošle `COORDINATOR(i)` všem **nižším ID** 
-  3. Pokud **nikdo** neodpoví během timeoutu → $P_i$ se prohlásí koordinátorem, odešle `COORDINATOR(i)` všem procesům s nižším ID a volba končí.   +  - Pokud někdo odpoví `OK` → $P_i$ čeká na `COORDINATOR(k)` od silnějšího 
-  4. Pokud přijde **alespoň jedno** `OK` od vyššího ID → $P_i$ čeká na zprávu `COORDINATOR(k)`; pokud po čase nedorazí, restartuje volby.   +  - Pokud neobdrží oznámení včas, znovu zahájí volby 
-  5. Po přijetí `COORDINATOR(k)` si každý proces uloží $k$ jako nového lídra.+ 
 +**Zprávy:** 
 +  * `ELECTION` – „ozvi se, pokud žiješ a jsi silnější“ 
 +  * `OK` – potvrzení, že někdo silnější žije 
 +  * `COORDINATOR(k)` – oznámení o novém lídrovi
  
-- **Typy zpráv**   +**Vlastnosti:** 
-  - `ELECTION` – „vyhlašuji volby, reaguj, pokud žiješ a máš vyšší ID“.   +  * Zaručuje, že vítězí **nejvyšší živé ID** 
-  - `OK` – potvrzení, že vyšší proces existuje; potlačí menší ID.   +  * Horší složitost: $\mathcal{O}(n^2)$ zpráv v nejhorším případě 
-  - `COORDINATOR(k)` – oznámení výsledku všem.  +  * Rychlejší než kruh, pokud je vyšší ID blízko 
 +  * Vyžaduje spolehlivou detekci pádů (není odolný vůči partitioning)
  
-- **Vlastnosti**   
-  - Garantuje, že zvítězí **nejvyšší živé ID** (“bully” přetlačí ostatní).   
-  - Nejhorší případ $\mathcal{O}(n^2)$ zpráv (kaskáda voleb, když padá více procesů).   
-  - Rychlejší konvergence než kruh, pokud selže jen koordinátor a vyšší ID je blízko.   
-  - Netoleruje síťové rozdělení (“split brain”) – vyžaduje spolehlivé detekce crashů. 
-</markdown> 
  

Trace: • b0b36dbs

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b36pdv (generated for current page)