- děje, která se dějí zároveň
- není podstatné jestli se dějí, ale zda mohou nastat
- události mohou být happends-before (stalo se před) partial order (první událost zapříčiní druhou)
- jsou concurrent jestli jsou neseřazené podle happens-before
- problém dekompozice - různé úkoly jsou převážně nezávislé
- externí concurrency - obsluhování vícera klientů zároveň
- výkonnostní a hw limitace - větší troughput na více jádrových pc
- hw je bezprostředně paralelní
- software je bezprostředně sekvenční
- něco se musí vzdát (hw to nebude)
- vlákno je sekvence instrukcí
- každá instrukce se stala před další neboli happens-before je totální pořadí na vlákně
- základní jednotka plánování (scheduling)
- základní jednotka recoource ownership - primárně paměť, ale také otevřené soubory, atd.
- může obsahovat jedno nebo více vláken
- procesy jsou izolovány od sebe - IPC vytváři mezery v izolaci
- standardní vstup i výstup
- proces A zapíše soubor
- později proces B čte ten soubor
- comunikace se děje v reálném čase
- mezi dvěmi běžícími vlákny / procesy
- automatická: uživatel nezasahuje
- bidirectional (obousměrná) komunikace je typická - analogová ke konverzaci
- unidirectional (jednosměrná) komunikace - posílání příkazu child procesu
- síťové služby jsou typický příklad - webový server a webový prohlížeč
- prohlížeč pošle požadavek webové stránce
- server odpoví psláním dat
- je možné komunikovat prostředím souborů
- vícero procesů může otevřít stejný soubor
- jeden proces může zapsat data a další tyto data zpracovat
- originální rogram pak vezme výsledky
- typicky když se používají programy jako modules
- například překladač -
cc file.c
- prvně spustí preprocesor:
cpp -o file.i file.c
- poté
cc1 -o file.o file.i
- a nakonec linker
ld file.o crt.o -lc
- souborové mezikroky mohou být schovány v
/tmp a smazány po skončení
- komunikace vytvářením souborům a linků
- typicky: a spool directory
- klient přidá soubory do adresáře ke zpracování
- server periodicky vezme soubory z adresáře
- použité např. pro tisknutí a email
- zařízení pro přesměrování bajtů ve streamu (rozdíl od zpráv)
- jeden proces zapisuje, druhý čte
- reader blokuje jestliže je roura prázdná
- writer blokuje jestliže je buffer roury plný
- roury jsou hojně používané v UNIXu
- pipelines jsou postaveny pomocí shellového operátor
|
- nejvíce využito pro zpracovávání dat ve fázích
- podobné, ale více schopné než roury
- zpřístupňuje serveru komunikovat s více klienty
- každé spojení (connection) se chová jako obousměrná roura
- může být lokální nebo připojená přes síť (abstrakce sítě)
- paměť je sdílená když ji více vláken přistupuje
- děje se přirozeně pro vlákna jendoho procesu
- primární smysl je komunikace mezi-vlákny
- mnoho procesů může mapovat stejnou fyzickou lokaci
- toto je tradiční přístup
- ttaké umožňuje mezi-procesovou komunikaci
- komunikace používá diskrétní zprávy (messages)
- může a nemusí nás zajímat pořadí doručení
- můžeme tolerovat massage loss
- často používané přes síť
- může být implementováno na základě socketů
- strukturovaný pohled sdílené paměti
- typicky více-vláknové programy
- např. jakákoliv globální proměnná
- ale také může žít v paměti z
mallocu
void *thread( int *x ) { *x = 7; }
int main()
{
pthread_t id;
int *x = malloc ( sizeof( int ) );
pthread_create( &id, NULL, thread, x );
}
- mějme sdílení counter (shared counter)
i
- a nasledující dvě vlákna
int i = 0;
void thread1() { i = i + 1; }
void thread2() { i = i - 1; }
- přístup do paměti není atomický
a₀ ← load i | b₀ ← load i
a₁ ← a₀ + 1 | b₁ ← b₀ - 1
store a₁ i | store b₁ i
- sekce kódu ,které nesmí být přerušena
- staement
x = x + 1 může být kritická sekce
- co je kritická sekce je domain-dependent
- příklad je bankovní transakce
- nebo vložení prvku do linked listu
- (anomálie) chování, které závisí na načasování
- typicky mezi více vlákny nebo procesy
- nečekané pořadí událostí
- vzpoměňme si, že pořadí není garantováno
- souborový systém je sdílený zdroj a kvůli tomu náchylný k race conditions
- např. dvě vlákna zkusí vytvořit stejný soubor
- co se stane už oba uspějí?
- if oba data zápíšou, výsledek bude garbage
- context: pouze jedno vlákno smí přistoupit ke zdroji naráz
- zajišťuje mutex - mutual exclusion device
- mutex má 2 operace:
lock a unlock
lock musí počkat než jiné vlákno unlocks daný mutex
- víc obecný než mutex
- povoluje vícero veměnitelných instancí daného zdroje
- mějme N identických tiskáren, poté nanejvýš N procesů může tisknout zároveň
- basically an atomic counter
- konstrukce programovacího jazyka (není poskytován OS)
- vnitřně používají standardní mutexy
- data monitoru jsou pouze přístupná jeho metodám
- pouze jedno vlákno může použít monitor zároveň
- co když monitor potřebuje na něco čekat?
- představme si ohraničenou frontu implementovánou jako monitor
- co když se zaplní?
- writer je suspended
- podmínkové proměnné mají
wait a signal operace
- spinlock je nejjednodušší forma mutexu
- metoda
lock opakovaně zkouší získat zámek
- toto znamená, že bere processor time - také známé jako busy waiting
- spinlocks contention na stejném CPU je velmi špatné
- ale může být velmi efektivní mezi CPUs
- tyto potřebují kooperaci od OS plánovače (scheduler)
- když
lock selže, vlákno je uspáno (sleeps)
- je přidáno do čekací (waiting queue) fronty v plánovači
unlocking mutexu probudí čekací vlákno- potřebuje system call → pomelé vůči spinlockům
- stejný způsob jako suspending mutex
- čekající vlákno jde do čekcí fronty
signal přesune vlákno zpět do běžící fronty- busy-wait verze je známá jako polling
- občas paralelní počítání pracuje ve fázích
- všechny vlákna musí ukončit fázi 1 předtím, než může nějaká fáze 2
- tato je docíleno bariérou
- blokuje všechny vlákna než poslední vlákno skončí
- čekající vlákna jsou normálně uspány
- mějme sdílenou databázi
- mnoho vláken může číst databázi zároveň
- ale jestliže jedno zapisuje, žádné jiné nesmí ani číst ani psát
- co když je zde vždy nějaký reader
- nejrychlejší zámek je žádný zámek
- RCU povoluje readers pracovat v průběhu aktualizací
- vytvoř kopii a aktualizuj kopii
- přesměruj nové readers na aktualizovanou kopii
- kdy je bezpečné to reclaim memory?
- hw má limitovaný počet instancí
- mnoho zařízení může dělat pouze jednu věc
- třeba tiskárny, DVD writers, tape drivers, …
- chceme používat zařízení efektivně → sharing
- zdroje mohou být acquired a released
- sdílení není limitováno na procesy na jednom pc
- tiskárny a skenery mohou být network-attached
- celá síť musí koordinovat přístup
- toto může zapříčinit multi-computer deadlocks
- zámky (mutexy) jsou taky froma zdrojů
- mutex může být acquired (locked) a released
- zmčený mutex patří danému vláknu
- zámky jsou zástupný (proxy (stand-in)) zdroje
- občas držené zdroje mohou být odebrány
- v tomto případě např. fyzická paměť
- procesy mohou být swapped na disk v případě potřeby
- preemtability může záviset na contextu
- možná stránkování není dostupné
- tyto zdroje nemohou být (jednoduše) odebrány
- tiskárna v půlce tisku, DVD vypalovač uprostřed zápisu
- non-preemtable zdroje mohou vést k deadlocks
- proces potřebuje výžádat přístup ke zdroji
- tomuto se říká aquisition
- může selhat
- když je přístup granted, může zařízení být použito
- po dokončení musí zařízení vrátit (release) -> zpřístupnění pro jiné procesy
- Co dělat, v případě, že chceme acquire a busy zdroj?
- pokud to nepotřebujeme, budeme muset čekat
- stejná jako čekání na mutex
- vlákne je přesunuto na čekací frontu
- dva zdroje A a B
- dvě vlákna (procesy) P a Q
- P acquires A, Q acquires B
- P zkouší acquire B, ale musí čekat na Q
- Q zkouší acquire A, ale musí čekat na P
- mutual exclusion
- hold and wait condition
- non-preemtability
- circular wait
Deadlock je možný pouze pokud jsou všechny 4 možné.
- ne všechny deadlocky jsou kvůli zdrojům
- představme si message-passing system
- proces A čeká pro zprávu
- proces B pošle zprávu do A a čeká na odpověď
- zpráva se ztratí v přenosu
- vzpomeňme, že i reader i writer mohou blokovat
- Co když vytvoříme rouru v obou směrech?
- proces A píše data a zkouší přečíst odpověď
- blokuje, protože opačná roura je prázdná
- proces B čte data ale čeká na víc –> deadlock
- deadlocks jsou belmi obtížné na debugování
- mohou také být velice vzácné
- může nám risk deadlocku připadat přípustné
- prostě restart všeho v případě hitnutí deadlocku - pštrosí algoritmus
- můžeme alespoň zkusit odhalit deadlock
- nejčasteji podle zkoušení podmínky circular wait
- vytvoříme graph vlastníků a čekajících
- jestli je v graphu cyklus → deadlock
- jestli cyklus obsahuje odjímatelné zdroje, odeber ho a zkus znovu
- jinak, může být možné udělat rollback
- toto potřebuje checkpointing mechanismus
- pokud vše selže, kill některé z procesů
- zařízení může být potřeba re-initialised
- můžeme deny acquisitions k předejitím deadlockům
- musíme vědět maximum zdrojů pro každý proces
- avoidance závisí na safe states
- nejhorší případ: všechny procesy se zeptají o maximální zdroje
- bezpečné znamená vyhýbání se deadlockům v nejhorším případě
- deadlock avoidance je typicky nepraktické
- jsou 4 podmínky aby nastal deadlock
- můžeme zamezit jednu podmínku → deadlock bude zamezen
- tento zabraňuje mutual exclusion vlastnost
- vícero programů může zapisovat do tiskárny
- data jsou sbírany spolling daemonem
- který posílá příkazt do tiskárny sekvenčně
- můžeme zkusit odstranit hold-and-wait
- můžeme povolit batch acquisition
- proces můsí o všechny zdroje požádat najednou
- toto je typicky nepraktické
- alternativně: release a re-acquire
- tento způsob eliminuje circular waits
- vytvoříme globální pořadí na zdroje
- proces může acquire zdroje pouze v daném pořadí
- musí release + re-acquire jestli je pořadí špatné
- je nemožné vyvořit cyklus
- v deadlocku není žádný progress
- ale není lepší, když procesy jdou “tam a zpět”
- například releasing a re-acquiring zdrojů
- nemají žádný užitečný progress
- navíc potřebují zdroje
- livelock je špatný tak jako deadlock
- vyhladovění se stane, když proces nemůže mít žádný progress
- zobecnění obou deadlock a livelock
- například nefér scheduling na busy systém
- také problém reader and writers