PB173 - Ovladače jádra - Linux
IV. Chyby souběhu
Jiri Slabý
Fakulta informatiky Masarykova univerzita
11. 10. 2016
Jiri Slabý (Fakulta informatiky, MU)
PB173/04
11. 10. 2016 1/19
Obsah cvičení
Q Chyby souběhu
Q Atomické operace, bitmapy
Q Zámky
• Spinlocky
• Mutexy
Jiri Slabý (Fakulta informatiky, MU) PB173/04 11.10.2016 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 1	
int *addr = &some_int;	
int a = load(addr);	
a = a + 1;	
store(a, addr);	
	J
Jiri Slabý (Fakulta informatiky, MU)
PB173/04
11. 10. 2016 3/19
Příklad chyby souběhu
int a = load(addr); a = a + 1; store(a, addr);
Uvažujme při startu *addr == o
*addr	Vlákno A	Vlákno B
0 0 0	int a = load(addr); a = a + 1; <schedule>	<waiting>
*addr	Vlákno A	Vlákno B
0 0 1	int a = load(addr); a = a + 1; <waiting>	int a = load(addr); a = a + 1; store(a, addr);
*addr	Vlákno A	Vlákno B
0 0 >1<	int a = load(addr); a = a + 1; store(a, addr);	<exited>
Jiri Slabý (Fakulta informatiky MU)
PB173/04
11. 10. 2016 4/19
Ř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) o 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/04
11.10.2016 5/19
Sekce 2
Atomické operace, bitmapy
Jiri Slabý (Fakulta informatiky, MU)
PB173/04
11. 10. 2016 6/19
Atomické operace
• linux/atomic.h, Documentation/atomic_ops.txt
• atomic.t a = AT0MIC_INIT(5)
9 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 = &some_int;
atomic_t a;
int a = load(addr); 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/04
11. 10. 2016 7/19
Úkol
Práce s atomickými typy
O Definujte jeden atomic_t V module_init
O Nastavte hodnotu na -3 (nejlépe staticky)
O Atomicky jednou operací proveďte „přičíst 1 a přečíst hodnotu"
O Přečtenou hodnotu vypište do logu
O Přičtěte 3
O Odečtěte 1
O Přečtěte hodnotu a vraťte jako návratovou z module.init Pozn.: tento kód nemažte, budeme s ním nadále pracovat
Jiri Slabý (Fakulta informatiky, MU)
PB173/04
11. 10. 2016 8/19
Atomické bitové operace
• Stačí-li 1 bit namísto celého čísla (např. int)
• linux/bitops.h, Documentation/atomic_ops.txt
• DECLARE_BITMAP(a, 1000)
o Pole a typu long o velikosti 1000/BITS_PER_L0NG
• set_bit, clear_bit, test_bit
9 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 G {and, or,xor, andnot, complement} bitmap.empty, bitmap_full, ...
Jiri Slabý (Fakulta informatiky, MU)
PB173/04
11. 10. 2016 9/19
Úkol
Práce s bitmapami
Definujte bitové pole o 100 bitech Q Vymažte obsah pole
• bitmap_zero
O Nastavte 2., 63. a 76. bitu (čísla považujte za indexy v C) O Vypište long (°/.ix) s 63. bitem
• bitmapa[BIT_W0RD(63)]
Q Vypište celou bitmapu jako řetězec
bitmap_scnprintf (do 4.0), °/0100pb (od 4.0)
O Vypište longy obsahující bity nastavené na 1
• for_each_set_bit
Q Vypište pozici 1. nastaveného bitu
• find first bit
Jiri Slabý (Fakulta informatiky MU)
PB173/04
11. 10. 2016 10/19
Sekce 3
Zámky
Jiri Slabý (Fakulta informatiky, MU)
PB173/04
11. 10. 2016 11/19
Zámky
Vytvoření kritické sekce
• Spinlocky
9 Čekání ve smyčce (požírá strojový čas)
o Rychlé, ale POZOR: 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í 1 syscallu)
Jiri Slabý (Fakulta informatiky, MU)
PB 173/04
11. 10. 2016 12/19
Spinlocky
• Cekání ve smyčce
• linux/spinlock.h, Documentation/spinlocks.txt
• DEFINE_SPINLOCK(lock)s, spinlock.t lockD
• spin_lock, spin_unlock
Podobné pthread spinlockům
int *addr = &some_int;
DEFINESPINLOCK(addrlock); int *addr = &some_int;
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/04
11. 10. 2016 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 O A celý kód obalte spinlockem Vyzkoušejte
Jiri Slabý (Fakulta informatiky MU)
PB173/04
11. 10. 2016 14/19
Mutexy
• Spící, fronta čekatelů
• linux/mutex.h
o DEFINE_MUTEX(lock)s, struct mutex lockp
• mutex_lock, mutex_unlock
Podobné pthread mutexům
int *addr = &some_int;
D E FIN E_M UTEX(addrJock); int *addr = &some_int;
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 informatiky MU)
PB173/04
11. 10. 2016 15/19
Zámky v jádře - ostatní
Semafory
• linux/semaphore.h
• Víceméně nepoužívat
DEFINE_SEMAPHORE(lock) o down, up
Big Kernel Lock (BKL)
• Historický
• Dnes už v jádře nenajdeme (commit 4ba8216cd9 v 2.6.39)
• Jen jeho relikty
• Hrubozrnný
• Pochází z dob počátku Linuxu
• lock_kernel, unlock_kernel
Jiri Slabý (Fakulta informatiky MU)
PB173/04
11. 10. 2016 16/19
Deadlock
o 4 podmínky uváznutí
o Jádro spoléhá na programátora, že k němu nikdy nedojde o 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/04
11. 10. 2016 17/19
Úkol
Atomické čtení/zápis bufferu o velikosti 128 bytů (součást domácího) O Globální buffer 128 B O 2 znaková (mise) zařízení
• 1 implementuje .read
1 implementuje .write
O 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 (get_user a 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í kousek)
O Vyzkoušejte Pozn.: inspirace v pb173/04
Jiri Slabý (Fakulta informatiky, MU)
PB 173/04
11. 10. 2016 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í
Příliš mnoho procesů čeká na zámek o 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/04
11. 10. 2016 19/19