IB109 Návrh a implementace paralelních systémů
POSIX Threads - pokračování Win32 Threads
Jiří Barnat
Správa vláken
• Vytváření, oddělování a spojování vláken.
o Funkce na nastavenia zjištění stavu vlákna.
Vzájemná vyloučení (mutexes)
o Vytváření, ničení, zamykania odemykání mutexů.
o Funkce na nastavenia zjištění atributů spojených s mutexy.
Podmínkové/podmíněné proměnné (conditional variable)
o Slouží pro komunikaci/synchronizaci vláken.
o Funkce na vytváření, ničení, "čekání na" a "signalizování při" specifické hodnotě podmínkové proměnné.
• Funkce na nastavenia zjištění atributů proměnných.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 2/44
Podmínkové proměnné v POSIX Threads
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 3/44
Podmínkové proměnné — Motivace
Motivace I
9 Často na jednu kritickou sekci čeká vícero vláken.
• Aktivní čekání - permanentní zátěž CPU.
• Uspávání s timeoutem - netriviální režie, omezená frekvence dotazování se na možnost vstupu do kritické sekce.
Motivace II
• Vlákno realizuje ucelenou, logicky oddělenou funkcionalitu.
• Ta není třeba po celou dobu běhu aplikace.
• Programátorem řízená dočasná deaktivace vlákna.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 4/44
Podmínkové proměnné
Obecné řešení
9 Uspání vlákna, pokud vlákno má/musí čekat.
o Vzbuzení vlákna v okamžiku, kdy je možné pokračovat.
Realizace v POSIX Threads
• Mechanismus označovaný jako Podmínkové proměnné.
• Podmínková proměnná vyžaduje použití mutexu.
o Po získání mutexu se vlákno může dočasně vzdát tohoto mutexu a uspat se (v rámci dané podmínkové proměnné).
o Probuzení musí být explicitně signalizováno jiným vláknem.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 5/44
Podmínkové proměnné
int pthread_cond_init (
ptrhead_cond_t *cond, pthread_cond_condattr_t *attr)
• Inicializuje podmínkovou proměnnou.
• Má-li attr hodnotu NULL, použije se výchozí chování.
int pthread_cond_destroy ( ptrhead_cond_t *cond)
• Zničí nepoužívanou podmínkovou proměnnou a související datové struktury.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 6/44
Podmínkové proměnné
int pthread_cond_wait (
ptrhead_cond_t *cond, pthread_mutex_t *mutex_lock)
• Uvolní mutex mutex_lock a zablokuje vlákno ve spojení s podmínkovou proměnou cond.
• Po návratu vlákno opět vlastní mutex mutex_lock.
• Před použitím musí být mutex.lock inicializován a zamčen volajícím vláknem.
int pthread_cond_signal (
ptrhead_cond_t *cond)
o Signalizuje probuzení jednoho z vláken, uspaných nad podmínkovou proměnou cond.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 7/44
Podmínkové proměnné
int pthread_cond_broadcast ( ptrhead_cond_t *cond)
• Signalizuje probuzení všem vláknům čekajících nad podmínkovou proměnnou cond.
int pthread_cond_timedwait ( ptrhead_cond_t *cond, pthread_mutex_t *mutex_lock, const struct timespec *abstime)
• Vlákno buď vzbuzeno signálem, nebo vzbuzeno po uplynutí času specifikovaném v abstime.
9 Při vzbuzení z důvodu uplynutí času, vrací chybu ETIMEDOUT, a neimplikuje znovu získání mutex_lock.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 8/44
Podmínkové proměnné - typické použití
12 pthread_cond_t is.empty;
13 pthread_mutex_t mutex;
432 pthread_mutex_lock(&mutex);
433 while ( size > 0 )
434 pthread_cond_wait (&is_empty, femutex)
• • •
456 pthread_mutex_unlock(&mutex); 715     [pthread_mutex_lock(&mutex);]
• • •
721 size=0;
722 pthread_cond_signal(&is_empty);
723 [pthread_mutex_unlock(&mutex) ;]
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
Další funkce v POSIX Threads
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 10/44
Globální, přesto vláknu specifické proměnné
Problém
• Vzhledem k požadavkům vytváření reentrantních a thread-safe funkcí se programátorům zakazuje používat globální data.
o Případné použití globálních proměnných musí být bezstavové a prováděno v kritické sekci.
o Klade omezení na programátory. Řešení
• Thread specific data (TSD)
• Globální proměnné, které mohou mít pro každé vlákno jinou hodnotu.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 11/44
Implementace TSD
Standardní řešení
• Pole indexované jednoznačným identifikátorem vlákna, o Vlákna musí mít rozumně velké identifikátory.
• Snadný přístup k datům patřící jiným vláknům - potenciální riziko nekorektního kódu.
Řešení POSIX standardu
• Identifikátor (klíč) a asociovaná hodnota.
9 Identifikátor je globální, asociovaná hodnota lokální proměnná. Klíč - pthread_key_t.
• Asociovaná hodnota - univerzální ukazatel, tj. void *.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 12/44
int pthread_key_create ( ptrhead_key_t *key, void (*destructor)(void*))
• Vytvorí nový klíč (jedná se o globální proměnnou).
• Hodnota asociovaného ukazatele je nastavena na NULL pro všechna vlákna.
o Parametr destructor - funkce, která bude nad asociovanou hodnotou vlákna volána v okamžiku ukončení vlákna, pokud bude asociovaná hodnota nenulový ukazatel.
• Parametr destructor je nepovinný, lze nahradit NULL.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
Zničení klíče a asociovaných ukazatelů
• int pthread_key_delete (ptrhead_key_t key)
• Nevolá žádné destructor funkce.
9 Programátor je zodpovědný za dealokaci objektů před zničením klíče.
Funkce na získání a nastavení hodnoty asociovaného ukazatele
• void * pthread_getspecif ic (ptrhead_key_t key)
• int pthread.set specif ic (
ptrhead_key_t key, const void *value)
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
ptrheacLt pthreacLself ()
• Vrací unikátní systémový identifikátor vlákna
int pthreacLequal (pthreacLt threadl, pthread_t thread2)
• Vrací nenula při identitě vláken threadl a thread2
pthread_once_t once.control = PTHREAD_ONCE_INIT; int pthread_once(pthread_once_t *once_control, void (*init_routine) (void));
9 První volání této funkce z jakéhokoliv vlákna způsobí provedení kódu init_routine. Další volání nemají žádný efekt.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 15/44
Další funkce v POSIX Threads
Plánování (scheduling) vláken
• Není definováno, většinou je výchozí politika dostačující.
• POSIX Threads poskytují funkce na definici vlastní politiky a priorit vláken.
9 Není požadována implementace této části API. Správa priorit mutexů.
Sdílení podmínkových proměnných mezi procesy. Vlákna a obsluha POSIX signálů. Read-Write zámky.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 16/44
Typické konstrukce
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 17/44
Čtenáři a písaři - WRRM Mapa
Specifikace problému
• Vlákna aplikace často čtou hodnotu, která je relativně méně často modifikována. (Write-Rarely-Read-Many)
• Je žádoucí, aby čtení hodnoty mohlo probíhat souběžně.
Možné problémy
• Souběžný přístup dvou vláken-písařů, může vyústit
v nekonzistentní data nebo mít nežádoucí vedlejší efekt, například memory leak.
Souběžný přístup vlákna-písaře v okamžiku čtení hodnoty jiným vláknem-čtenářem může vyústit v čtení neplatných, nekonzistentních dat.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 18/44
Řešení s použitím POSIX Threads
■v
<* Ctení a modifikace dat bude probíhat v kritické sekci.
• Přístup do kritické sekce bude řízen pomocí funkcí pthreacL*.
Další požadavky
• Vlákno-čtenář může vstoupit do kritické sekce, pokud v ní není nebo na ní nečeká žádné vlákno-písař.
• Vlákno-čtenář může vstoupit do kritické sekce, pokud v ní jsou jiná vlákna-čtenáři.
9 Přístupy vláken-písařů jsou serializovány a mají přednost před přístupy vláken-čtenářů.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 19/44
Čtenáři a písaři - Implementace
Jednoduché řešení
• Použít jeden pthread_mutex_t pro kritickou sekci, o Vylučuje souběžný přístup vláken-čtenářů.
Lepší řešení
9 Implementujeme nový typ zámku - rwlock_t o Funkce pracující s novým zámkem
9 rwlock_rlock(rwlock_t *1) - vstup vlákna-čtenáře
• rwlock_wlock(rwlock_t *1) - vstup vlákna-písaře
• rwlock_unlock(rwlock_t *1) - opuštění libovolným vláknem
• Funkce rwlock implementovány s využitím podmínkových proměnných z POSIX Thread API.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 20/44
Čtenáři a písaři - Implementace
rlock
unl
rlock
sleep
rlock
KS
unlock
rlock
unlock
sleep
wlock
KS
sleep
wlock
KS
unlock
IB109 Návrh a implementace paralelních systémů
POSIX Threads - pokračování, Win32 Threads
str. 21/44
Čtenáři a písaři - Implementace
1 typedef struct {
2 int readers;
3 int writer;
4 pthread_cond_t readers_proceed;
5 pthread_cond_t writer_proceed;
6 int pending.writers;
7 pthread_mutex_t lock;
8 } rwlock_t;
9
10 void rwlock_init (rwlock_t *1) {
11 l->readers = l->writer = l->pending_wr iters = 0;
12 pthread_mutex_init (&(l->lock) ,NULL) ;
13 pthread_cond_init (&(l->readers_proceed) ,NULL);
14 pthread_cond_init (&(l->writer_proceed) ,NULL) ;
15 }
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 22/44
Čtenáři a písaři - Implementace
16
17 void rwlock_rlock (rwlock_t *1) {
18 pthreadjnutex_lock(&(l->lock));
19 while (l->pending_writers>0 || (l->writer>0)) {
20 pthread_cond_wait (&(l->readers_proceed), &(l->lock));
21 }
22 l->readers++;
23 pthreadjnutex_unlock(&(l->lock));
24 }
25
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 23/44
Čtenáři a písaři - Implementace
26
27 void rwlock_wlock (rwlock_t *1) {
28 pthreadjnutex_lock(&(l->lock));
29 while (l->writer>0 || (l->readers>0)) {
30 l->pending_writers++;
31 pthread_cond_wait (&(l->writer_proceed), &(l->lock));
32 l->pending_writers —;
33 }
34 l->writer++;
35 pthreadjnutex_unlock(&(l->lock));
36 }
37
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 24/44
Čtenáři a písaři - Implementace
38
39 void rwlock_unlock (rwlock_t *1) {
40 pthreadjnutex_lock(&(l->lock));
41 if (l->writer>0)
42 l->writer=0;
43 else if (l->readers>0)
44 l->readers—;
45 pthreadjnutex_unlock(&(l->lock));
46 if ( l->readers == 0 && l->pending_writers >0)
47 pthread_cond_signal( &(l->writer_proceed) );
48 else if (l->readers>0)
49 pthread_cond_broadcast ( &(l->readers_proceed) )
50 }
51
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 25/44
Čtenáři a písaři - Příklady použití
Počítání minima
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
rwlock_rlock(&rw_lock); if (myjmin < globaljnin) {
rwlock_unlock(&rw_lock);
rwlock_wlock(&rw_lock);
if (my_min < global_min) global_min = my_min;
}
}
rwlock_unlock(&rw_lock);
{
o Hašovací tabulky
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 26/44
Bariéry
Specifikace problému
« Synchronizační primitivům
• Vláknu je dovoleno pokračovat po bariéře až když ostatní vlákna dosáhly bariéry.
9 Naivní implementace přes mutexy vyžaduje aktivní čekání (nemusí být vždy efektivní).
Lepší řešení
• Implementace bariéry s použitím podmínkové proměnné a počítadla.
o Každé vlákno, které dosáhlo bariéry zvýší počítadlo.
• Pokud není dosaženo počtu vláken, podmíněné čekání.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 27/44
Bariéry - Implementace
1 typedef struct {
2 pthread_mutex_t count_lock;
3 pthread_cond_t ok_to_proceed;
4 int count;
5 } barrier.t;
6
7 void barrier_in.it (barrier_t *b) {
8 b->count = 0;
9 pthread_mutex_init (&(b->count_lock), NULL);
10 pthread_cond_init (&(b->ok_to_proceed), NULL);
11 }
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 28/44
Bariéry - Implementace
12 void barrier (barrier_t *b, int nr.threads) {
13 pthread_mutex_lock(&(b->count_lock));
14 b->count ++;
15 if (b->count == nr_threads) {
16 b->count = 0;
17 pthread_cond_broadcast (& (b->ok_to_proceed));
18 }
19 else
20 while (pthread_cond_wait (&(b->ok_to_proceed),
21 &(b->count_lock)) !=0);
22 pthread_mutex_unlock(&(b->count_lock)) ;
23 }
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 29/44
Bariéry - Efektivita implementace
Problém
9 Po dosažení bariéry všemi vlákny, je mutex count_lock postupně zamčen pro všechny vlákna
o Dolní odhad na dobu běhu bariéry je tedy O(n), kde n je počet vláken participujících na bariéře
Možné řešení
o Implementace bariéry metodou binárního půlení
• Teoretický dolní odhad na bariéru je 0(n/p + log p), kde p je počet procesorů
C" v y viceni
• Implementujte bariéru využívající binárního půlení
• Měřte dopad počtu participujících vláken na dobu trvání lineární a logaritmické bariéry na vámi zvoleném paralelním systému
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 30/44
Chyby, krom nezamykaného prístupu ke globální proměnné
Typické chyby - situace 1
• Vlákno VI vytváří vlákno V2 e V2 požaduje data od VI
o VI plní data až po vytvoření V2 o V2 použije neinicializovaná data
Typické chyby - situace 2
• Vlákno VI vytváří vlákno V2
• VI předá V2 pointer na lokální data VI
• V2 přistupuje k datům asynchronně
a V2 použije data, která už neexistují (VI skončilo)
Typické chyby - situace 3
• VI má vyšší prioritu než V2, čtou stejná data
9 Není garantováno, že VI přistupuje k datům před V2
• Pokud V2 má destruktivní čtení, VI použije neplatné data
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads str. 31/44
Ladění programů s POSIX vlákny
Valgrind
• Simulace běhu programu.
• Analýza jednoho běhu programu.
Nástroje valgrindu
• Memcheck - detekce nekonzistentního použití paměti.
• Callgrind - jednoduchý profiler.
• kcachegrind - vizualizace.
• Helgrind - detekce nezamykaných přístupů ke sdíleným proměnným v POSIX Thread programech.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 32/44
Rozšíření POSIX Threads - nepovinná dle standardu
Barriéry
o pthread_barrier_t
• pthread_barrierattr_t
• _init(...),-destroy(...), _wait(...)
Read-Write zámky
• pthread_rwlock_t
o pthread_rwlockattr_t
• _init(...), -destroy(...)
• _rdlock(...), _wrlock(...),.unlock(...)
• _tryrdlock(...) , _trywrlock(...)
• _timedrdlock(...), _timedwrlock(...)
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 33/44
Další způsoby synchronizace
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 34/44
Synchronizace procesů
Problém - jak synchronizovat procesy
o Mutexy z POSIX Threads dle standardu slouží pouze pro synchronizaci vláken v rámci procesu.
9 Pro realizaci kritických sekcí v různých procesech je třeba jiných synchronizačních primitiv.
• Podpora ze strany operačního systému. Semafory
Čítače používané ke kontrole přístupů ke sdíleným zdrojům. 9 POSIX semafory (v rámci procesu) 9 System V semafory (mezi procesy)
• Lze využít i pro synchronizaci vláken.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 35/44
Semafory
Semafor
• Celočíselný nezáporný čítač jehož hodnota indikuje "obsazenost" sdíleného zdroje.
• Nula - zdroj je využíván a není k dispozici. Nenula - zdroj není využíván, je k dispozici.
• sem_init() - inicializuje čítač zadanou výchozí hodnotou
• sem_wait() - sníží čítač, pokud může, a skončí, jinak blokuje
• sem_post() - zvýší čítač o 1, případně vzbudí čekající vlákno
Semafory vs. mutexy
• Mutex smí odemknout pouze to vlákno, kterého jej zamklo.
• Semafor může být spravován / manipulován různými vlákny.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 36/44
y
Monitor
• Synchronizační primitivům vyššího programovacího jazyka.
• Označení kódu, který může být souběžně prováděn nejvýše jedním vláknem.
• JAVA - klíčové slovo synchronized
Semafory, mutexy a monitory
o Se semafory a mutexy je explicitně manipulováno programátorem.
• Vzájemné vyloučení realizované monitorem je implicitní, tj. explicitní zamykání skrze explicitní primitiva doplní překladač.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 37/44
Vlákna v MS Windows
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 38/44
Vlákna v MS Windows
Vyšší programovací jazyk
• C++11
• JAVA
• ...
POSIX Thread pro Windows
• Existuje knihovna poskytující POSIX Thread interface.
Nativní rozhraní MS Windows
o Přímá systémová volání (součást jádra OS).
• Pouze rámcově podobná funkcionalita jako POSIX Threads.
• Na rozdíl od POSIX Threads nemá nepovinné části (tudíž neexistují různé implementace téhož).
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 39/44
Windows vs. POSIX Threads - Funkce
Windows	POSIX Threads
Pouze jeden typ HANDLE	Každý objekt má svůj vlastní typ (např. pthreacLt, pthread.jnutex_t, . . .)
Jedna funkce pro jednu činnost, (např. WaitForSingleObject)	Různé funkce pro manipulaci s různými objekty a jejich atributy.
Typově jednodušší rozhraní (bez typové kontroly), čitelnost závislá na jménech proměnných.	Typová kontrola parametrů funkcí, lepší čitelnost kódu.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 40/44
Win32 vs. POSIX Threads - Synchronizace
Windows	POSIX Threads
Události (Events) Semafory Mutexy Kritické sekce	Mutexy Podmínkové proměnné Semafory
Signalizace pomocí událostí.	Signalizace v rámci podmínkových proměnných.
Jakmile   je   událost signalizována, zůstává v tomto stavu tak  dlouho,  dokud ji někdo voláním   odpovídající funkce nepřepne do nesignalizovaného stavu.	Signál     zachycen čekajícím vláknem, pokud takové není, je signál zahozen.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 41/44
Win32 vs. POSIX Threads - Základní mapování
Windows	POSIX Threads
CreateThread	pthread_create pthread_attr_*
ThreadExit	pthread_exit
WaitForSingleObj ect	pthread_join pthread_attr_setdetachstate pthread_detach
SetPriorityClass SetThreadClass	Pouze nepřímo mapovatelné. setpriority sched_set scheduler sched_setparam pthread-setschedparam
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 42/44
Win32 vs. Linux/UNIX - Mapování synchronizace
Windows	Linux threads	Linux processes
M u t ex	PThread Mutex	System V semafor
Kritická sekce	PThread Mutex	
Semafor	PThread podm. proměnné POSIX semafor	System V semafor
Událost	PThread podm. proměnné POSIX semafor	System V semafor
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 43/44
Win32 vs. UNIX - Pozorování
Pozice vláken ve MS Windows
9 Silnější postavení než vlákna v Linuxu.
• Synchronizační prostředky fungují i mezi procesy.
• Vlákna ve vlákně (Processes-Threads-Fibers)
• User-mode scheduling (UMS) - kooperativní plánování.
Výhody jednoho typu
• Jednou funkcí lze čekat na nekonkrétní vlákno.
• Jednou funkcí lze čekat na vlákno a na mutex.
IB109 Návrh a implementace paralelních systémů: POSIX Threads - pokračování, Win32 Threads
str. 44/44