Základy synchronizace oooooooo Vláknové programování část II Lukáš Hejmanek, Petr Holub {xhejtman,hopet}@ics.muni.cz Laboratoř pokročilých síťových technologií PV192 2008-04-29 □ -O Q^ O 1/4; Základy synchronizace oooooooo Přehled přednášky Základy synchronizace Zámky Mutexy Semafory Podmíněné proměnné RCU struktury « □ ► -0 0,0 Základy synchronizace •ooooooo Kritické sekce • Co je to kritická sekce? • Nereentrantní část kódu • Ne vždy je na první pohled zřejmé, co je a není reentrantní. □ -o Q, O- 3/4; Základy synchronizace o»oooooo Kritické sekce - ukázky • Obecně je kritickou sekcí každá část kódu, která načte data, zpracuje je a zapíše zpět. • Příklad: • Načti čítač ze souboru • Zvyš čítač o jedna • Zapiš současnou hodnotu čítače zpět do souboru □ -o Q, O- 4/4; Základy synchronizace o»oooooo struct queue { void *data; struct queue *next; } queue; struct queue *head; struct queue «tail; void add(void *data) I tail->next = malloc sizeof(struct queue)); tail->data = data; tail = tail->next; } □ -O Q^ O 5/4; Základy synchronizace o»oooooo #include #include #include volatile int x=0; void * foo(void *arg) { int i; while(x == 0); for(i = 0; i < 1000000; i++) asm("incl^%0" : : "m" printf("%d\n", x); return NULL; } (x)); int main(void) { pthread_t tl, t2, t3; pthread_create(Stl, NULL, pthread_create(St2, NULL, pthread_create(St3, NULL, x=l; pthread_j oin(t1, NULL); pthread_j oin(t 2, NULL); pthread_j oin(t 3, NULL); return 0; foo, foo, foo, NULL) NULL) NULL) zi -O Q* O 6/4; Základy synchronizace o»oooooo • Příklad výstupu programu: • 1136215 • 1355167 • 1997368 • Očekávaný výstup: • xxxxxxx • yyyyyyy • 3000001 • Uvedené špatné chovaní se nazýva race condition (soupeření v běhu). □ -o Q, O- 7/4; Základy synchronizace oo»ooooo Řešení kritických sekcí • Nejlépe změnou kódu na reentrantní verzi. • Ne vždy je to možné. • Pomocí synchronizace = zamezení současného běhu kritické sekce • Snížení výkonu - přicházíme o výhodu paralelního běhu aplikace • Synchronizační nástroje: • Mutexy (zámky) • Semafory • Podmíněné proměnné □ -o c^ o 8/4; Základy synchronizace ooo»oooo Zámky • Vzájemné vyloučení vláken • Well-known algoritmy Petersonův algoritmus Dekkerův algoritmus Lamportův algoritmus „pekařství' □ -o Q, O- 9/4; Základy synchronizace ooo»oooo Zámky flag[0] = 0; flag[l] = 0; turn; PO: flag[0] = 1; PI: flag[l] = 1; turn = 1; turn = 0; while (flag[l] == 1 && turn = = D while (flag[0] == 1 && turn l // busy wait l // busy // wait } // critical section } // critical // section // end of critical section // end of critical // section flag[0] = 0; flag[l] = 0; • Proč nefunguje: http://bartoszmilewski.wordpress.com/2008/11/ 05/who-ordered-memory-fences-on-an-x86/ □ -O c\ o 10/4; Základy synchronizace ooo»oooo Změny pořadí zápisů a čteni • Současné procesory mohou měnit pořadí zápisů a čtení • Čtení může prohozeno se starším zápisem int a,b; a = 5; if(b) { } Důsledek: init: x=0 Thread 1 Thread 2 x = 1 if ready == 1 ready = 1 R = x □ -r)<\(y Základy synchronizace ooo»oooo Změny pořadí zápisů a čteni • Současné procesory mohou měnit pořadí zápisů a čtení • Čtení může prohozeno se starším zápisem l int a,b; 2 3 a = 5; 4 if(b) { } • Důsledek: init: x=0 Thread 1 Thread 2 x = 1 if ready == 1 ready = 1 R = x • ready=l && x=0 □ -T) (\ O 12/4; Základy synchronizace ooo»oooo Změny pořadí zápisů a čteni • Současné procesory mohou měnit pořadí zápisů a čtení • Čtení může prohozeno se starším zápisem l int a,b; 2 3 a = 5; 4 if(b) { } • Důsledek: init: x=0 Thread 1 Thread 2 x = 1 if ready == 1 ready = 1 R = x • ready=l && x=0 init: x=0, y= =0 Thread 0 Thread 1 mov [x] , 1 mov [y] 1 mov rl, [y] mov r2, [x] □ -T) (\ O 13/4; Základy synchronizace ooo»oooo Změny pořadí zápisů a čteni • Současné procesory mohou měnit pořadí zápisů a čtení • Čtení může prohozeno se starším zápisem l int a,b; 2 3 a = 5; 4 if(b) { } • Důsledek: init: x=0 Thread 1 Thread 2 x = 1 if ready == 1 ready = 1 R = x • ready=l && x=0 init: x=0, y= =0 Thread 0 Thread 1 mov [x] , 1 mov [y] 1 mov rl, [y] mov r2, [x] • rl=0 && r2=0 □ -T) (\ O 14/4; Základy synchronizace ooo»oooo Speciální instrukce CPU • Atomické operace • Bit test (testandsetQ) • Load lock/Store Conditional (LL/SC) • Compare and Swap (CAS) (x86 - cmpxchg) • __sync_bool_compare_and_swap() • __sync_value_compare_and_swap() • Atomicka aritmetika - specialita x86, x86_64 • Speciální instrukce lock formou prefixu • atomic_inc() { "lock xaddl %0, %1"} __sync_fetch_and_add(val, 1) • atomic_dec() { "lock xsubl %0, %1"} __sync_fetch_and_sub(val, 1) • xchg(int a, int b) { "xchgl %0, %1"} • Paměťové bariéry • rmb(), wmb() • __sync_synchronize () - plná paměťová bariéra □ -o°*o Základy synchronizace ooo»oooo Volati Iní typy • Nekonečná smyčka int x=0; void fool) while(x= =0); x = 10; } //continue f oo: movl x(%rip), %eax testl %eax, %eax je .L2 movl $10, x(%rip) ret .L2: .L4: jmp .L4 □ -T) (\ O 15/4; Základy synchronizace ooo»oooo Volati Iní typy • Funkční verze volat ile int x=0 void foot) while(x== =0); x = 10; } //continue f oo: .L2: movl x(%rip), %eax testl %eax, %eax je .L2 movl $10, x(%rip) ret □ -T) (\ O 17/4; Základy synchronizace ooo»oooo Volati Iní typy • Volatilní proměnná: volatile int x; nebo int volatile x; • Nevolatilní ukazatel na volatilní proměnnou: volatile int *x; • Volatilní ukazatel na nevolatilní proměnnou: int *volatile x; • Volatilní ukazatel na volatilní proměnnou: volatile int ♦volatile x; □ -O c\ o 18/4; Základy synchronizace ooo»oooo Zámek • Naivní algoritmus zámku volatile int val=0; void lock() { while(atomic_inc(val) =0) { //sleep } t void unlock() { val = 0; // wake up } □ -T) (\ O 19/4; Základy synchronizace ooo»oooo Zámek s podporou kernelu • Podpora kernelu o „volaní" my_sleep_while () • Pozastaví proces právě tehdy když je podmínka splněna • „volání" my_wake () • Vzbudí pozastavený proces(y) volatile int val=0, void lockt) { int c= while((c=atomic_ my_sleep } Lne(va _while 1))! (val =0) { ==(c+l)); void } unlock () { val = 0; my_wake (); □ ■0 0,0 20/4; Základy synchronizace oooo»ooo M utexy • Mechanismus zámků v knihovně Pthreads • Datový typ pthread_mutex_t. • Inicializace pthread_mutex_init (Inicializaci je vhodné provádět ještě před vytvořením vlákna). • Zamykání/odemykání • pthread_mutex_lock • pthread_mutex_unlock • Zrušení zámku pthread_mutex_destroy. □ -O c\ o 21/4; Základy synchronizace oooo»ooo ttinclude ttinclude ttinclude volatile int x= 3; pthread_mutex_t x_lock; void * foo(void *arg) l int i; while(x == 0); for (i = 0; i < 1000000; i++) { pthread_mutex_lock(&x_lock); X++; i pthread_mutex_unlock(&x_lock); t printf( '%d\n", x); return NULL; } □ -r)<\(y Základy synchronizace oooo»ooo int main { [void) pthread_t tl, t2, t3; pthread_mutex_init(&x_lock, NULL); pthread_create(Stl, NULL, foo, NULL); pthread_create(St2, NULL, foo, NULL); pthread_create(St3, NULL, foo, NULL); x=l; pthread_j oin(t1, NULL); pthread_j oin(t 2, NULL); pthread_join(t 3, NULL); pthread_mutex_destroy(&x_ -lock) ; } return 0; □ -T) (\ O 23/4; Základy synchronizace oooo»ooo • Výstup změněného programu: • 2424575 • 2552907 • 3000001 • Což je očekávaný výsledek □ -O cv o 24/4; Základy synchronizace oooo»ooo Zámky „bolí" • Mějme tři varianty předchozího příkladu: void foo(void *arg) { int i; while(x == 0); for(i = 0; i < 100000000; i++) X++; } void foo(void *arg) { int i; while(x == 0); for(i = 0; i < 100000000; i++) asm( "lockLjinclLj%0" : : } "m" (x)); void foo(void *arg) { int i while x == 0); for (i = 0; i < 100000000; i++) { pthread_mutex_lock(&x_lock); X++; } } pthread_mutex_unlock(&x_lock); □ -T) (\ O 25/4; Základy synchronizace oooo»ooo • Délky trvání jednotlivých variant (real time, 3 vlákna) • Bez zámku (nekorektní verze) 1.052sec • „Fast lock" pomocí assembleru 5.716sec • pthread mutex 66.414sec □ -O cv o 26/4; Základy synchronizace oooo»ooo Big kernel lock vs. Spin locking • Vlákna a procesy mohou mít velké množství zámků. • Koncepce Big kernel lock • Pro všechny kritické sekce máme jeden společný zámek • Název pochází z koncepce Linux kernelu verze 2.0 • Jednoduchá implementace • Může dojít k velkému omezení paralelismu • Koncepce Spin locking • Pro každou kritickou sekci zvláštní zámek • Název pochází z koncepce Linux kernelu verze 2.4 a dalších • Složitější implementace • Omezení paralelismu je většinou minimální • Velké nebezpečí vzniku skrytých race conditions. • Některé kritické sekce mohou spolu dohromady tvořit další kritickou sekci. □ -O c\ o 27/4; Základy synchronizace ooooo»oo Semafory Mutexy řeší vzájemné vyloučení v kritických sekcích. Semafory řeší synchronizaci úloh typu producent/konzument. Producent/konzument úloha: • Producent vyrábí • Konzument(i) spotrebováva • Problém synchronizace - konzument může spotřebovat nejvýše tolik, co producent vytvořil • Příklad: • Producent přidává objekty do fronty • Konzument odebírá objekty z fronty • Synchronizace: konzument může odebrat pouze, je-li fronta neprázdná, jinak má čekat. • Není vhodné čekat pomocí tzv. busy loop, tj. neustále zjišťovat stav front, vlákno zbytečně spotřebovává procesor. □ -O c\ o 28/4; Základy synchronizace ooooo»oo Synchronizace s použitím busy loop producer: while( } ) { přidej prvek do fronty; consumer: ) { /* busy loop */ while(fronta prázdna) nedělej nic; } odeber prvek z fronty □ ■0 0,0 29/4; Základy synchronizace ooooo»oo Semafor • Semafor je synchronizovaný čítač. • Producent čítač zvyšuje • Konzument čítač snižuje Čítač nelze snížit k záporné hodnotě • Pokus o snížení k záporné hodnotě zablokuje vlákno, dokud není čítač zvýšen. □ -o c\ o 30/4; Základy synchronizace ooooo»oo • Rukojeť semaforu sem_t. • Inicializace semaforu sem_init () (Inicializaci je vhodné provádět před vytvořením vláken). • Zvýšení hodnoty semaforu sem_post (). • Snížení hodnoty semaforu a případně čekání na zvýšení jeho hodnoty sem_wait(). • Zrušení semaforu sem_destroy (). □ -O cv o 31/4; Základy synchronizace ooooo»oo ttinclude ttinclude ttinclude ttinclude sem_t sem; int quit=0; void * producer(void *arg) l int i=0; while(!quit) { /* produce same data */ printf ("SendingLjdataLj%d\n" ,i++); sem_post(&sem) ; } } □ -T) (\ O 32/4; Základy synchronizace ooooo»oo void * consumer(void *arg) { int i=0; while(!quit) { /* wait for data */ sem_wait(&sem) ; printf ("DataLjreadyLj%d\n", /* consume data */ } i++); } int main { Void) pthread_t p, c; sem_init(&sem, 0, 0) ; pthread_create(&c, NULL, pthread_create(&p, NULL, consumer producer , NULL); , NULL); } sleep(1); quit = 1; pthread_join(c, NULL); pthread_join(p, NULL); sem_destroy(&sem) ; □ -T) (\ O 33/4; Základy synchronizace ooooo»oo Ukázka části výstupu programu Sending data 0 Sending data 1 Sending data 2 Sending data 3 Sending data 4 Sending data 5 Sending data 6 Sending data 7 Data ready 0 Data ready 1 Data ready 2 Data ready 3 Data ready 4 Data ready 5 Data ready 6 Data ready 7 Sending data 8 Sending data 9 Sending data 10 □ -T) (\ O 34/4; Základy synchronizace oooooo»o Podmíněné proměnné Synchronizace pomocí podmínek: • A: Čekej na splnění podmínky • B: Oznam splnění podmínky □ -o°*o Základy synchronizace oooooo»o Podmíněné proměnné • Základní rukojeť podmínky pthread_cond_t. • Inicializace podmínky pthread_cond_init (). • Cekání na podmínku pthread_cond_wait (). • Signalizace splnění podmínky • pthread_cond_signal () - probudí alespoň jednoho čekatele. • pthread_cond_broadcast () - probudí všechny čekatele. • Zrušení podmínky pthread_cond_destroy (). □ -O c\ o 36/4; Základy synchronizace oooooo»o ttinclude ttinclude ttinclude pthread_cond_t condition; pthread_mutex_t cond_lock; void * worker(void *arg) { pthread_mutex_lock(&cond_lock); printf("Waiting^for^conditionXn"); pthread_cond_wait(&condition, &cond_lock); printf("Condition^trueXn"); pthread_mutex_unlock(&cond_lock); return NULL; □ -r)<\(y Základy synchronizace oooooo»o int main(void) { pthread_t p; pthread_mutex_init(&cond_lock, pthread_cond_init(&condition, NULL); NULL); pthread_create(&p, NULL, worker, NULL); sleep(1); printf("Signaling^conditionXn"); pthread_mutex_lock(&cond_lock); pthread_cond_signal(&condition); pthread_mutex_unlock(&cond_lock) ; printf("Condition^doneXn"); pthread_join(p, NULL); pthread_cond_destroy(&condition) ; pthread_mutex_destroy(&cond_lock); return 0; □ -r)<\(y Základy synchronizace ooooooo» RCU struktury • Read-Copy-Update struktura • Zbytečné zamykat každý přístup • Zřejmě • Lze číst paralelně • Aktualizovat může jen jeden v době, kdy jiný nečte • Musíme zamykat pro čtení? • RCU struktury jsou hojně využívané v jádru Linuxu □ -o°*o Základy synchronizace ooooooo» RCU struktury • Využití RCU struktur • Aktualizace seznamů • Seznam lze paralelně číst • Seznam nelze paralelně aktualizovat • Princip RCU • Čtení seznamu „běžným" způsobem • Modifikace: • Zduplikování starého prvku seznamu (malloc() • Modifikace duplikátu • Záměna původního prvku s duplikátem • Co s původním prvkem? □ -o°*o Základy synchronizace ooooooo» RCU struktury API RCU struktur: • rcu_read_lock() • rcu_read_unlock() • synchronize_rcu() • rcu_assign_pointer() • rcu_dereference() • call_rcu() □