PB173 - Ovladače jádra - Linux
IV. Chyby souběhu
Jiri Slabý
Fakulta informatiky Masarykova univerzita
7. 10. 2014
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014 1/19
Obsah cvičení
O Chyby souběhu
Q Atomické operace, bitmapy
Q Zámky • Spinlocky a Mutexy
Jiri Slabý (Fakulta informatiky, MU) PB173/02 7.10.2014     2/ 19
Chyby souběhu, zámky
LDD3 kap. 5 (zastaralá)
Co je chyba souběhu
• Chyba závislá na načasování/prokládání operací
Ukázkový kód ^	
int *addr;	
int a = load(addr);	
a = a + 1;	
store(a, addr);	
	
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014      3/ 19
Příklad chyby souběhu
int a = load(addr); a = a + 1; store(a, addr);
Uvažujme *addr == 0
*addr	Vlákno A	Vlákno B
0	int a = load(addr);	<waiting>
0	a = a + 1;	
0	<schedule>	
*addr	Vlákno A	Vlákno B
0	int a = load(addr);	int a = load(addr);
0	a = a + 1;	a = a + 1;
1	<waiting>	store(a, addr);
*addr	Vlákno A	Vlákno B
0	int a = load(addr);	<exited>
0	a = a + 1;	
/*>1 <*/	store(a, addr);	
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014      4/ 19
Řešení chyb souběhu
a Atomickou operací ve stylu load_inc_store
• Nutná podpora CPU
• Ne na všechno jsou operace (vesměs jen +, -, load, store)
• Kritickou sekcí
• Kus kódu vykonávaný max. jedním procesem
• Zámky
• Read-copy-update (RCU)
• Podrobnosti v LDD
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014      5/ 19
Sekce 2
Atomické operace, bitmapy
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014      6/ 19
Atomické operace
• linux/atomic.h, Documentation/atomic_ops.txt
• atomic_t a = AT0MIC_INIT(5)
• Pojme 32 bitů se znaménkem (int) (historicky jen 24)
• atomic_read, atomic_set
• atomic_add, atomic_inc, atomic_sub, atomic_dec, atomic_*_return a další (LXR)
int *addr;
atomicj a;
int a = load(addr); =4> a = a + 1; store(a, addr);
atomic_inc(&a);
/* nebo atomic_add(1, &a); */
• atomic64_t (drahý na 32-bitu)
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014      7/ 19
Úkol
Práce s atomickými typy O Definice jednoho atomic_t V module_init 0 Nastavit hodnotu na -3 (nejlépe staticky) O Atomicky jednou operací „přičíst 1 a přečíst hodnotu" O Přečtenou hodnotu vypsat do logu O Přičíst 3 O Odečíst 1
O Přečíst hodnotu a vrátit jako návratovou Pozn.: tento kód nemažte, budeme s ním nadále pracovat
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014      8/ 19
Atomické bitové operace
• Stačí-li 1 bit namísto int
• linux/bitops.h, Documentation/atomic_ops.txt a DECLARE_BITMAP(a, 1000)
• set_bit, clear_bit, test_bit
• test_and_set_bit, test_and_clear_bit
Bitmapy lze použít i NEATOMICKY (např. v kritických sekcích)
• linux/bitmap.h
• __set_bit,__clear_bit
• bitmap_zero, bitmap_fill, bitmap_copy
• bitmap_0P, kde OP £ {and,or,xor,andriot,coniplenierit}
• bitmap_empty, bitmap_f ull, ...
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014      9/ 19
Úkol
Práce s bitmapami O Definice bitového pole o 100 bitech 0 Výmaz pole (bitmap_zero) 0 Nastavení 2., 63. a 76. bitu (počítáno od nuly) O Výpis longu (7„lx) S 63. bitem (bitmapa[BIT_W0RD(63)]) 0 Výpis celé bitmapy (bitmap_scnprintf) 0 Výpis longů obsahující „1" bity (f or_each_set_bit) 0 Výpis pozice 1. nastaveného bitu (f ind_f irst_bit)
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014 10/19
Sekce 3
Zámky
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014 11/19
Zámky
Vytvoření kritické sekce
• Spinlocky
• Čekání ve smyčce (požírá strojový čas)
• Rychlé, nesmí se uvnitř spát (čekat)
• Mutexy
• Spící, fronta čekatelů
• Pomalejší než spinlock (viz tělo__mutex_lock_common)
• Semafory
• Podobné mutexům
• Počítadlo (jsou rekurzivní)
» Dnes se používají výjimečně
POZOR
Zámky lze držet jen v jádře (po dobu vykonávání syscallu)
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014 12/19
Zámky v jádře - spinlocky
• Čekání ve smyčce
• linux/spinlock.h, Documentation/spinlocks.txt a DEFINE_SPINLOCK(lock), spinlock_t lock
• spin_lock, spin_unlock
• Podobné pthread spinlockům
int *addr;
D E Fl N E_SP IN LOC K(add rjock); int *addr;
int a = load(addr); a = a + 1; store(a, addr);
spin_lock(&addr_lock); int a = load(addr); a = a + 1; store(a, addr); spin_unlock(&addr_lock);
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014 13/19
Úkol
Práce se spinlocky
O Úkol s atomickými operacemi přepište O atomic_t změňte na obyčejný int 0 A celý kód obalte spinlockem O Vyzkoušejte
Jiri Slabý (Fakulta informatiky, MU)
Zámky v jádře - mutexy
Mutexy
• Spící, fronta čekatelů
• linux/mutex.h
• DEFINE_MUTEX(name)
• mutex_lock, mutex_unlock
• Podobné pthread mutexům
int *addr;
DEFINE_MUTEX(addr_lock); int *addr;
int a = load(addr); a = a + 1; store(a, addr);
mutex_lock(&addr_lock); int a = load(addr); a = a + 1; store(a, addr); mutex_unlock(&addr_lock);
Jiri Slabý (Fakulta intormatiky, MU)
PB173/02
7.10.2014 15/19
Zámky v jádře - ostatní
Semafory
• linux/semaphore.h
« Víceméně nepoužívat
• Pozor: DECLARE_MUTEX(lock)
• down, up
Big Kernel Lock (BKL)
• Historický
• Hrubozrnný
• Pochází z dob počátku Linuxu
• lock kernel, unlock kernel
Jiri Slabý (Fakulta informatiky, MU)
Úkol
Atomické čtení/zápis bufferu o velikosti 128 bytů
O Globální buffer 128 B Q 2 znaková (mise) zařízení
• 1 implementuje .read
• 1 implementuje .write
Q Zápis
• Umožněn max. po 5 znacích (.write vrací max. 5)
• Spí 20 ms po každém zápisu znaku do bufferu (msleep z
linux/delay.h)
O Čtení
• Vrátí naráz celých 128 B (je-li count dostatečně velký) Musí vidět změny pouze po 5 znacích (až na poslední pětici)
O Vyzkoušejte
Pozn. 1: práce s offp v pb173/04 Pozn. 2: odevzdat s domácím
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014 17/19
Deadlock
• 4 podmínky uváznutí
« Jádro spoléhá na programátora, že k němu nikdy nedojde « LockDep
• Dynamický mechanismus hledání chyb v zámcích
« Obvyklé typy chyb: ABBA, AA
• Obvyklé chyby: lock + if + return (POZOR)
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014 18/19
Další problémy zámků
• Zpomalují kritický kód
• Řešení: odstranit zámky
• Např. kruhovými buffery
• Nevhodná granularita
• Jeden zámek na všechno vs. jeden zámek na jednu činnost
• Např. BKL, nebo naopak zámky každého registru
• Zahlcení
a Příliš mnoho procesů čeká na zámek
• Lze řešit přechodem na COW, RCU, RW zámky, ...
• Např. všechny procesy čekají na taskiist_iock
Jiri Slabý (Fakulta informatiky, MU)
PB173/02
7.10.2014 19/19