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 [2026/05/25 13:03] (current) – jpelc
Line 5: Line 5:
     - **Hardwarová podpora pro paralelní výpočty** – (super)skalární architektury, pipelining, spekulativní vyhodnocování, vektorové instrukce, vlákna, procesy, GPGPU. Hierarchie cache pamětí.     - **Hardwarová podpora pro paralelní výpočty** – (super)skalární architektury, pipelining, spekulativní vyhodnocování, vektorové instrukce, vlákna, procesy, GPGPU. Hierarchie cache pamětí.
     - **Komplikace v paralelním programování** – souběh (race condition), uváznutí (deadlock), iluze sdílení (false sharing).     - **Komplikace v paralelním programování** – souběh (race condition), uváznutí (deadlock), iluze sdílení (false sharing).
-    - **Podpora paralelního programování v C a C++** – pthreads, thread, jthread, atomic, mutex, lock_guard.+    - **Podpora paralelního programování v C a CPP** – pthreads, thread, jthread, atomic, mutex, lock_guard.
     - **Podpora paralelního programování v OpenMP** – sériově-paralelní model uspořádání vláken (fork-join), paralelizovatelná úloha (task region), různé implementace specifikace. Direktivy: parallel, for, section, task, barrier, critical, atomic.     - **Podpora paralelního programování v OpenMP** – sériově-paralelní model uspořádání vláken (fork-join), paralelizovatelná úloha (task region), různé implementace specifikace. Direktivy: parallel, for, section, task, barrier, critical, atomic.
     - **Techniky dekompozice programu** – statické a paralelní rozdělení práce. Threadpool a fronta úkolů. Balancování a závislosti (dependencies).     - **Techniky dekompozice programu** – statické a paralelní rozdělení práce. Threadpool a fronta úkolů. Balancování a závislosti (dependencies).
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 104: Line 103:
  
 === Programovací modely === === Programovací modely ===
-  * **CUDA C/C++** – pro NVIDIA+  * **CUDA C/CPP** – pro NVIDIA
   * **OpenCL** – otevřený standard   * **OpenCL** – otevřený standard
-  * **SYCL** – moderní C++ model+  * **SYCL** – moderní CPP model
   * **OpenMP target** – direktivy pro GPU   * **OpenMP target** – direktivy pro GPU
  
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 CPP ===== 
- 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 CPP. 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 (CPP11) ==== 
-* Od C++11 je k dispozici standardní knihovna pro vlákna – `std::thread`. +  * Od CPP11 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 CPP idiomy** (např. RAII, STL, lambdy).
  
-==== std::jthread (C++20) ==== +==== std::jthread (CPP20) ==== 
-* Od C++20 přibyla nová třída `std::jthread`, která automaticky spravuje vlákno. +  * Od CPP20 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.
  
 ==== 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 CPP 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 280: Line 267:
 </code> </code>
  
-*Moderní C++* doporučuje použít `std::lock_guard`, který mutex **automaticky zamkne a odemkne** – tím se předejde chybám (např. zapomenutí `unlock()` při výjimce):+*Moderní CPP* doporučuje použít ''std::lock_guard'', který mutex **automaticky zamkne a odemkne** – tím se předejde chybám (např. zapomenutí ''unlock()'' při výjimce):
  
 <code cpp> <code cpp>
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 CPP 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 C++ se používá `std::atomic<T>` – kde `T` může být např. `int`, `bool`, pointer apod. +V praxi jsou tedy ''std::atomic'' velmi efektivní pro jednoduché sdílené proměnné – například čítače:
- +
-  * 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:+
  
 <code cpp> <code cpp>
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 =====
-OpenMP je velmi populární knihovna pro paralelizaci v jazycích C, C++ a Fortran. Umožňuje snadno spouštět více vláken pomocí direktiv vkládaných přímo do zdrojového kódu. V této kapitole se podíváme na to, jak funguje základní model *fork-join*, jak se v OpenMP definují úlohy (tasky), a jaké máme k dispozici prostředky pro synchronizaci. Ukážeme si i různé varianty implementací OpenMP a přehled direktiv, které programátorům umožňují jemné řízení paralelismu.+OpenMP je velmi populární knihovna pro paralelizaci v jazycích C, CPP a Fortran. Umožňuje snadno spouštět více vláken pomocí direktiv vkládaných přímo do zdrojového kódu. V této kapitole se podíváme na to, jak funguje základní model *fork-join*, jak se v OpenMP definují úlohy (tasky), a jaké máme k dispozici prostředky pro synchronizaci. Ukážeme si i různé varianty implementací OpenMP a přehled direktiv, které programátorům umožňují jemné řízení paralelismu.
  
 ==== 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:
-  * `#pragma omp barrier` – ruční synchronizační bod. +  * ''#pragma omp barrier'' – ruční synchronizační bod. 
-  * `single`, `master` – sekci vykoná pouze jedno vlákno. +  * ''single'', ''master'' – sekci vykoná pouze jedno vlákno. 
-  * `ordered` – zachování pořadí iterací ve smyčce. +  * ''ordered'' – zachování pořadí iterací ve smyčce. 
-  * `critical`, `atomic` – zajištění sériového přístupu ke sdíleným proměnným. +  * ''critical'', ''atomic'' – zajištění sériového přístupu ke sdíleným proměnným. 
-  * `nowait` – zabrání implicitní bariéře na konci paralelního bloku. +  * ''nowait'' – zabrání implicitní bariéře na konci paralelního bloku. 
-  * `OMP_NESTED=TRUE` nebo `omp_set_max_active_levels()` – aktivuje vnořenou paralelizaci. +  * ''OMP_NESTED=TRUE'' nebo ''omp_set_max_active_levels()'' – aktivuje vnořenou paralelizaci. 
-  * `task`, `taskgroup`, `depend(...)` – jemné řízení závislostí mezi úlohami (viz níže).+  * ''task'', ''taskgroup'', ''depend(...)'' – jemné řízení závislostí mezi úlohami (viz níže).
  
 ==== 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. +  * **Intel oneAPI (icx/icpx + iomp5)** – ''-qopenmp'', verze 5.2, velmi výkonný runtime, podpora GPU. 
-  * **Intel oneAPI (icx/icpx + iomp5)** – `-qopenmp`, verze 5.2, velmi výkonný runtime, podpora GPU. +  * **IBM XL (LLVM-based)** – ''-qsmp=omp'', verze 5.1, optimalizace pro POWER.
-  * **IBM XL (LLVM-based)** – `-qsmp=omp`, verze 5.1, optimalizace pro POWER.+
   * **AMD AOCC 4.x** – laděno pro AMD Zen, Clang + libomp.   * **AMD AOCC 4.x** – laděno pro AMD Zen, Clang + libomp.
   * **Cray/ROCm** – zaměřeno na GPU/offload (OpenMP target).   * **Cray/ROCm** – zaměřeno na GPU/offload (OpenMP target).
  
 ==== 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 468: Line 443:
 </code> </code>
    
-Tento příklad ukazuje vytvoření tasku se závislostí `depend(out: sum)`, paralelní redukci vnitřní smyčky, a následný task, který čeká na výsledek (`depend(in: sum)`).+Tento příklad ukazuje vytvoření tasku se závislostí ''depend(out: sum)'', paralelní redukci vnitřní smyčky, a následný task, který čeká na výsledek (''depend(in: sum)'').
  
  
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 =====
-Abychom lépe pochopili různé způsoby paralelizace, ukážeme si je na konkrétních příkladech z oblasti řazení, lineární algebry a strojového učení. Uvidíme, jak lze algoritmy jako quick sort nebo násobení matic přirozeně rozdělit do paralelních částí a jaké techniky přitom použít – např. tasky, `collapse`, blokové zpracování či závislosti.+Abychom lépe pochopili různé způsoby paralelizace, ukážeme si je na konkrétních příkladech z oblasti řazení, lineární algebry a strojového učení. Uvidíme, jak lze algoritmy jako quick sort nebo násobení matic přirozeně rozdělit do paralelních částí a jaké techniky přitom použít – např. tasky, ''collapse'', blokové zpracování či závislosti.
  
 ==== Řazení ==== ==== Řazení ====
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:

Navigation

Playground

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