PB173 - Ovladače jádra - Linux
IV. Chyby souběhu
Jiri Slabý
ITI, Fakulta informatiky
8. 10. 2013
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013      1 /18
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í
int *addr;
int a = load(addr); a = a + 1; store(a, addr);
Ukázkový kód
J. Slabý (ITI, Fl)
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;	
/*>"!<*/	store(a, addr);	-
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013      3/ 18
Řešení chyb souběhu
• Atomickou operací ve stylu ioad_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
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013      4/ 18
Část I
Atomické operace, bitmapy
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013      5/ 18
Atomické operace
a linux/atomic .h, Documentation/atoiiiic_ops .txt
a atomic_t a = ATDMIC_INIT(5)
a 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;
atomic.t a;
int a = load(addr); a = a + 1; store(a, addr);
atomicJnc(&a);
/* nebo atomic.add(1, &a); */
Řešení pomocí atomických operací
• atomic64_t (drahý na 32-bitu)
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013      6/ 18
Úkol
Práce s atomickými typy
O Definice jednoho atomic_t V module_init
O 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
Q Přečíst hodnotu a vrátit jako návratovou Pozn.: tento kód nemažte, budeme s ním nadále pracovat
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013      7/ 18
Atomické bitové operace
• Stačí-li 1 bit namísto int
• linux/bitops .h, Documentation/atoiiiic_ops .txt
• 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_DP, kde DP £ {and,or,xor,andnot, complement}
• bitmap_empty, bitmap_f ull, .. .
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013      8/ 18
Úkol
Práce s bitmapami
O Definice bitového pole o 100 bitech O Výmaz pole (bitmap_zero) O Nastavení 2., 63. a 76. bitu
O Výpis longu (°/„lx) S 63. bitem (bitmapa[BIT_W0RD(63)]) O Výpis celé bitmapy (bitmap_scnprintf) O Výpis longů obsahující „1" bity (for_each_set_bit) O Výpis pozice 1. nastaveného bitu (f ind_f irst_bit)
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013      9/ 18
Část II
Zámky
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013 10/18
Zámky
Vytvoření kritické sekce * Spinlocky
• Čekání ve smyčce (požírá strojový čas)
• Rychlé, nesmí se uvnitř spát (čekat)
a Mutexy
• Spící, fronta čekatelů
• Pomalejší než spinlock (viz tělo__mutex_lock_common)
« Semafory
• Podobné mutexům
• Počítadlo (jsou rekurzivní)
0 Dnes se používají výjimečně
POZOR
Zámky lze držet jen v jádře (po dobu vykonávání syscallu)
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013 11/18
Zámky v jádře - spinlocky
• Čekání ve smyčce
• linux/spinlock.h, Documentation/spinlocks.txt
• DEFINE_SPINLDCK(lock), spinlock_t lock
• spin_lock, spin_unlock
« Podobné pthread spinlockům
int *addr;
DEFINE-SPINLOCK(addrJock); int *addr;
int a = load(addr); =4> a = a + 1; store(a, addr);
spinJock(&addr_lock); int a = load(addr); a = a + 1; store(a, addr); spin.unlock(&addr.lock);
Řešení pomocí spinlocků
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013 12/18
Úkol
Práce se spinlocky
• Úkol s atomickými operacemi přepište
• atomic_t změňte na obyčejný int
• A celý kód obalte spinlockem
• Vyzkoušejte
J. Slabý (ITI, Fl)
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); =4> a = a + 1; store(a, addr);
mutexJock(&addrJock); int a = load(addr); a = a + 1; store(a, addr); mutex_unlock(&addrJock);
Řešení pomocí mutexů
Zámky v jádře - ostatní
Semafory
• 1inux/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
J. Slaby (ITI, Fl)
Úkol
Atomické čtení/zápis bufferu o velikosti 128 bytů
• Globální buffer 128 B
• 2 znaková (mise) zařízení
• 1 implementuje .read
• 1 implementuje .write
• 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)
• Č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)
• Vyzkoušejte
Pozn. 1: práce s offp v pb173/04 Pozn. 2: odevzdat s domácím
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013 16/18
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 a Obvyklé typy chyb: ABBA, AA
• Obvyklé chyby: lock + if + return (POZOR)
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013 17/18
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í
» 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
J. Slabý (ITI, Fl)
PB173/02
8. 10. 2013 18/18