1/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Vláknové programování část I Lukáš Hejmánek, Petr Holub {xhejtman,hopet}@ics.muni.cz Laboratoř pokročilých síťových technologií PV192 2012–02–21 2/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací “For the past thirty years, computer performance has been driven by Moore’s Law; from now in, it will be drivern by Amdahl’s Law. Writing code that effectively exploits multiple processors can be very challenging. . . ” –Doron Rajwan, Research Scientist, Intel Corp. 3/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Amdahlův zákon zrychlení ≤ 1 F + 1−F N kde F je podíl sériově vykonávané práce a N je počet procesorů 4/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Amdahlův zákon zrychlení ≤ 1 F + 1−F N kde F je podíl sériově vykonávané práce a N je počet procesorů 5/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací 80 jader na čipu Intel na IDF 2006 předvedl prototyp procesoru s 80 jádry. Výkon ≈ 1 TFLOPS Zdroje: http://www.news.com/Intel-shows-off-80-core-processor/2100-1006_3-6158181.html 6/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Úvod do programování ve vláknech • Programování v C s využitím Pthreads • Programování v Javě • Výlet do jiných jazyků: Ada • Demonstrováno na praktických příkladech 7/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Úvod do programování ve vláknech • Programovaní v C s využitím Pthreads 1. Procesy, vlákna, přepínání kontextu, knihovna pthreads, vznik a ukončení vláken, základy ladění aplikací 2. Základy synchronizace: zámky, semafory, podmíněné proměnné, RCU struktury 3. Pokročilé synchronizace: bariéry, rw zámky, pojmenované semafory, futexy 4. Afinita,Atributy vláken, režimy startu vlákna, priority, ukončování vláken, thread-specific data 5. OpenMP 6. Práce s pamětí 7. GUI, OpenGL, Futures a TPE v C++ 8/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Úvod do programování ve vláknech • Programování v Javě 1. Vlákna v jazyce Java, vytváření a ukončování. Viditelnost operací. Monitory a synchronizace. Signalizace a pozastavení. 2. Paralelní datové struktury. Atomické typy. Ladění paralelních programů: uváznutí a jeho diagnostika, hladovění. Testování paralelních programů. 3. Explicitní zamykání – RW zámky, vlastní typy zámků. Executory, thread pools, futures. 4. Paměťový model Javy. Paralelismus a GUI. 9/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Úvod do programování ve vláknech • Výlet do jiných jazyků: Ada 1. Úvod k jazyku Ada: základní rysy jazyka, syntaxe, datové typy. 2. Podpora paralelismu v jazyce Ada: úlohy, chráněné objekty, monitory, podpora systémů v reálném čase. 10/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Literatura • Andrews, Gregory R. Foundations of multithreaded, parallel, and distributed programming. Addison-Wesley 2000. • Ben-Ari M., Principles of Concurrent and Distributed Programming. 2nd Ed. Addison-Wesley, 2006 • Goetz B., Peierls T., Bloch J., Bowbeer J., Holmes D., Lea D. Java Concurrency in Practice. Addison Wesley Professional, 2006 • Butenhof D. R., Programming with POSIX(R) Threads. Addison-Wesley Professional, 1997 • Burns A., Wellings A. Concurrency in Ada. 2nd Ed. Cambridge University Press, 1998 nebo Burns A., Wellings A. Concurrent and Real-Time Programming in Ada. Cambridge University Press, 2007 11/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Přehled přednášky Procesy a vlákna Procesy Vlákna Knihovna Pthreads Základy ladění aplikací 12/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Procesy • Proces • Instance programu, která je sekvenčně prováděna. • Je to entita pro alokace zdrojů (procesor, paměť, atd) • Procesy tvoří stromovou hierarchii–vztah rodič potomek Sex is not really common among processes—each process has just one parent. 13/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Procesy • Typy procesů • Levný proces (Light Weight Process–LWP) • Levné procesy mezi sebou sdílí adresní prostor • Minimum privátních zdrojů • Drahý proces (Heavy Weight Process–HWP) • Drahé procesy jsou mezi sebou zcela izolované • Prakticky všechny zdroje jsou privátní 14/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Procesy • Popisovač procesu • Obsahuje informace o • Signálech • Přidělené paměti • Otevřených souborech • Aktuálním adresáři • HW kontext (obsah registrů, zásobník, . . . ) – TSS • Terminálu • Prioritě • Stav • . . . 15/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Procesy • Vytvoření procesu • Proces vzniká rozštěpením rodiče • Po startu je potomek stejný jako rodič • Stejný obsah paměti (Copy on Write) • Vykonává stejný kód 16/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Procesy • Běh procesu • Vykonávání kódu programu • Dva režimy běhu • User space–kód samotného programu • Kernel space–kód jádra • Stav procesu • Running • Interruptible • Uninterruptible (Nezpracovává signály) • Stopped • Traced • Konkurence vs. paralelismus • Konkurence–vykonávání stejného nebo různého kódu více procesy, nemusí probíhat ve stejný čas • Paralelismus–konkurence probíhající ve stejný čas 17/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Procesy • Přepínání kontextu • Zásadní mechanismus multitaskingu • Mechanismus uložení a obnovení stavu CPU • Rozlišujeme přepnutí kontextu • Registrové (obsluha přerušení) • Vláknové (přepnutí na jiné vláko téhož procesu) • Procesové (přepnutí na jiný proces) 18/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Procesy • Kroky při přepínání kontextu • Uložení stavu CPU, obvykle do TSS • Všechny běžné registry, deskriptory segmentu, příznaky • Stav a registry FPU • Obnova adresního prostoru • Načtení nového stavu CPU 19/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Procesy • Softwarové vs. hardwarové přepínání kontextu • Kontext lze uložit a obnovit v softwaru (kopírování stavu) • Některé procesory podporují přepnutí kontextu v HW (architektura x86 od Intel 80386 a dál) • Linux od verze jádra 2.4 používá softwarové přepnutí kontextu • Softwarové i hardwarové přepnutí kontextu je velmi drahá operace! 20/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Procesy • Komunikace mezi procesy • Soubory • Signály (signal(7)) • Sockets (socket(2)) • Fronty zpráv (mq_overview(7)) • Trubky (pipes), pojmenované vs. nepojmenované (pipe(2)) • Semafory (sem_overview(7)) • Sdílená paměť, paměťově mapované soubory (shm_overview(7), mmap(2)) • Message passing (MPI knihovny) 21/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Vlákna • Proč vlákna? • Paralelismus • Výkon • Odezva • Komunikace 22/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Vlákna • Vlákno • Podmnožina procesu • Vlákno nemá vlastní adresní prostor • Typicky sdílí stav ostatními vlákny daného procesu • Shared-memory model: • Komunikace mezi vlákny je možná stejně jako u procesů a navíc i přes jejich sdílenou paměť • Oproti procesu jsou běžně sdílené globální a statické proměnné 23/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Vlákna • Vlákna stejného procesu sdílí • Kód programu • „Většinu“ dat • Novější koncepce vláken podporuje nesdílenou paměť–thread local storage (TLS) • Otevřené soubory (file descriptors) • Signály a obsluhu signálů • Současný pracovní adresář • Identifikaci uživatele a skupiny • Process ID (PID) • Pojmenované semafory, fronty zpráv a další nástroje IPC 24/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Vlákna • Každé vlákno má unikátní • Thread ID (identifikace vlákna) • Obsah registrů procesoru, ukazatel vrcholu zásobníku • Zásobník pro lokální proměnné a návratové adresy • Masku signálů • Prioritu • Hodnotu proměnné errno (dle POSIX.1c) 25/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Vlákna • Implementace vláken v operačním systému je různá • proces a vlákno není rozlišeno (vlákno je tedy procesem – Linux bez NPTL) • proces a vlákno jsou rozlišeny (vlákno se liší od procesu – Windows, Linux s NPTL) • vlákna v uživatelském prostoru (vlákna si řídí sám proces – Java Green Threads (obsolete), Erlang) 26/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Vlákna • Mapování vláken na plánovací entity v jádře • mapování vláken 1:1 • současné produkční implementace • Linux, Windows, FreeBSD s libthr • mapování vláken N:M + teoreticky nejefektivnější − příliš složité, problémy s invertováním priorit, atd. • FreeBSD s Kernel Scheduler Entitites, experimenty i v Linuxu • mapování vláken N:1 • zastaralý přístup, user-space threading • FreeBSD s libc_r 27/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Vlákna • Některé systémy mají „levné“ přepínání vláken a „drahé“ přepínání procesů (Windows NT, OS/2). • Některé systémy příliš nerozlišují v přepnutí vlákna nebo procesu. • Proč uvažujeme vlákna místo procesů? • Rychlejší přepnutí běžících vláken než běžících procesů. • Snadné sdílení paměti a dalších zdrojů mezi běžícími vlákny (někdy ovšem nevýhoda). 28/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Knihovna Pthreads • POSIX Threads (Pthreads) je POSIX standard pro vlákna • Vlákna v systémech na bázi jádra Linux • Linux threads – neúplná implementace POSIX Threads • Vlákno bylo obsluhováno stejně jako proces, mělo i vlastní PID (process ID). • Není nutná speciální podpora jádra, problémy s výkonem, pokud se vlákno samo nevzdá procesoru (yield()). • Nahrazena NPTL – Native POSIX threads library • Výrazně vyšší výkonnost • Vlákno je samo o sobě jednotkou plánování, tj. procesový plánovač plánuje i vlákna obvykle úplně stejně. • NPTL potřebuje speciální podporu jádra pro synchronizaci. • Pthreads knihovna má implementaci pro řadu systémů: Linux, *BSD, Windows, MacOS, . . . 29/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Knihovna Pthreads • Vytváření vláken a procesů v Linuxu • Vlákno vzniká systémovým voláním clone(2) • Proces vzniká systémovým voláním fork(2) (případně vfork) • Nejčastější použití fork(2) je pro spuštění nového programu • Po fork(2) dojde k rozštěpení rodiče, duplikaci adresního prostoru, atd. • Následně je pomocí execl(3) zrušen obsah paměti a puštěn nový program • Jednodušší volání system(3), nelze ale použít vždy • Procesy se obvykle vytváří přímo voláním fork(2), vlákna pomocí knihovny pthreads. 30/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Knihovna Pthreads • Vytvoření procesu 1 #include 2 3 void 4 run(char *name) 5 { 6 pid_t child; 7 8 if((child=fork())==0) { 9 /* child */ 10 execlp(name, NULL); 11 return; 12 } 13 if(child < 0) { 14 perror("fork error"); 15 } 16 /* parent */ 17 return; 18 } 31/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Vytváření vláken pomocí Pthreads • Rukojeť vlákna pthread_t, používá se pro pro takřka všechna volání týkající se vytváření a manipulace s vlákny. • int pthread_create(pthread_t *thread, pthread_attr_t *attr, void *(*start_routine)(void*), void* arg); 32/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací • Vytvoření vlákna v C 1 #include 2 3 void * 4 runner(void *foo) 5 { 6 return NULL; 7 } 8 9 int 10 main(void) 11 { 12 pthread_t t; 13 14 pthread_create(&t, NULL, runner, NULL); 15 return 0; 16 } 33/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací • Nefunkční příklad pro C++ 1 #include 2 3 // not void* 4 void 5 runner(void *foo) 6 { 7 return; 8 } 9 10 int 11 main(void) 12 { 13 pthread_t t; 14 15 pthread_create(&t, NULL, runner, NULL); 16 return 0; 17 } 34/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Ukončování vláken • Možnosti ukončení vlákna samotným vláknem: • Návrat z hlavní funkce startu vlákna (třetí argument funkce pthread_create). • Explicitní zavolání funkce pthread_exit(void *value_ptr). • Možnosti ukončení vlákna jiným vláknem: • „Zabití“ vlákna pthread_kill(pthread_t thread, int sig). • Zasláním signálu cancel pthread_cancel(pthread_t thread) • Nedoporučovaná možnost, není jisté, kde přesně se vlákno ukončí. • Ukončení vlákna ukončením celého procesu • Zavoláním exit(3) • Posláním signálu SIGKILL, SIGTERM, . . . 35/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací • Co s návratovou hodnotou ukončeného vlákna? • Pro zjištění návratové hodnoty int pthread_join(pthread_t thread, void **value). 36/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací 1 #include 2 #include 3 #include 4 5 void * 6 runner(void *foo) 7 { 8 sleep(10); 9 pthread_exit(NULL); 10 } 11 12 int 13 main(void) 14 { 15 pthread_t t; 16 17 pthread_create(&t, NULL, runner, NULL); 18 19 pthread_kill(t, SIGKILL); 20 return 0; 21 } 37/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Reentrantní funkce • Vícenásobný běh programu má určitá úskalí. • Kód funkcí musí počítat s tím, že může být prováděn několikrát najednou. • Problematické jsou globální proměnné a statické lokální proměnné. 38/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací 1 char buffer_2[200]; 2 3 char * 4 foo1(char * a) 5 { 6 static char buffer_1[200]; 7 8 snprintf(buffer_1, 200, "Text: %s\n", a); 9 10 return buffer_1; 11 } 12 13 char * 14 foo2(char *a) 15 { 16 snprintf(buffer_2, 200, "Text: %s\n", a); 17 18 return buffer_2; 19 } 39/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací • Reentrantní funkce – funkce schopná násobného běhu. • Příklad funkce foo(char *) – implementace alokuje dynamický kus paměti. • Makro __REENTRANT – je-li definováno, říkáme překladači a hlavičkovým souborům, že funkce mohou být vykonávány násobně. • Knihovní funkce: • Thread safe – lze používat z více vláken • Not thread safe – nelze používat z více vláken • Některé funkce nemohou být thread safe z podstaty věci – strtok(3) • POSIX.1c rozšiřuje množinu funkcí o thread safe varianty, např. strtok_r(3) 40/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Kompilace • Dvě možnosti kompilace: • gcc -o foo foo.c -lpthread -D__REENTRANT • gcc -o foo foo.c -pthread -D__REENTRANT • Nezapomínáme na to, že záleží na pořadí knihoven a objektových souborů na příkazové řádce. 41/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Ladění aplikací • Ladící výpisy • Debugger 42/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Ladící výpisy • Pozor na mixování výpisů jednotlivých vláken do sebe. • Jeden print je obvykle atomický. • getpid() vrací pro vlákna stejnou hodnotu. • pthread_self() vrací identifikaci vlákna (pthread_t – lze vypsat jako integer). • Ladící výpisy způsobují určitou synchronizaci! 43/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Debugger • Použití gdb: • info threads – vypíše základní informace o běžících vláknech. • thread ID – přepnutí se na konkrétní vlákno. • Debugger způsobuje velkou synchronizaci! 44/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Ladění aplikací 1 (gdb) info threads 2 2 Thread 0x40da4950 (LWP 12809) 0x00007f9f852c7b99 in 3 pthread_cond_wait@@GLIBC_2.3.2 () from /lib/libpthread.so.0 4 * 1 Thread 0x7f9f856de6e0 (LWP 12806) 0x00007f9f84ff8b81 in nanosleep () 5 from /lib/libc.so.6 6 (gdb) thread 2 7 [Switching to thread 2 (Thread 0x40da4950 (LWP 12809))]#0 0x00007f9f852c7b99 8 in pthread_cond_wait@@GLIBC_2.3.2 () from /lib/libpthread.so.0 9 (gdb) where 10 #0 0x00007f9f852c7b99 in pthread_cond_wait@@GLIBC_2.3.2 () 11 from /lib/libpthread.so.0 12 #1 0x0000000000400907 in worker (arg=0x0) at conditions.c:13 13 #2 0x00007f9f852c33f7 in start_thread () from /lib/libpthread.so.0 14 #3 0x00007f9f85032b2d in clone () from /lib/libc.so.6 15 #4 0x0000000000000000 in ?? () 16 (gdb) 45/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Ladění aplikací • valgrind – ladící nástroj • helgrind – režim valgrindu • Použití: valgrind -tool=helgrind aplikace • Detekuje • Chybné použití knihovny pthreads • Nekonzistentní použití zámků • Některé nezamknuté přístupy ke sdíleným datům (data races) 46/46 Vláknové programování Procesy a vlákna Knihovna Pthreads Základy ladění aplikací Ladění aplikací 1 ==20556== Possible data race during read of size 4 at 0x601040 by thread #3 2 ==20556== at 0x400630: foo (critsec1.c:10) 3 ==20556== This conflicts with a previous write of size 4 by thread #1 4 ==20556== at 0x4006D9: main (critsec1.c:24) 5 ==20556== 6 ==20556== Possible data race during write of size 4 at 0x601040 by thread #3 7 ==20556== at 0x40064C: foo (critsec1.c:12) 8 ==20556== This conflicts with a previous write of size 4 by thread #1 9 ==20556== at 0x4006D9: main (critsec1.c:24) 10 ==20556== 11 ==20556== Possible data race during read of size 4 at 0x601040 by thread #2 12 ==20556== at 0x400643: foo (critsec1.c:12) 13 ==20556== This conflicts with a previous write of size 4 by thread #4 14 ==20556== at 0x40064C: foo (critsec1.c:12)