PB173 - Ovladače jádra - Linux IV. Jiří Slabý ITI, Fakulta Informatiky 11. 10. 2011 J. Slabý (ITI) PB173/01 11. 10. 2011 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) PB173/01 11. 10. 2011 2/18 Příklad chyby souběhu int a = load (addr) ; a = a + 1 ; store(a, addr) Vlákno A Vlákno B int a = load (addr) ; a = a + 1 ; Vlákno A Vlákno B int a = load (addr) ; a = a + 1; int a = load (addr) ; a = a + 1 ; store (a, addr) ; Vlákno A Vlákno B int a = load (addr) ; a = a + 1; store (a, addr) ; int a = load (addr) ; a = a + 1 ; store (a, addr) ; J. Slabý (ITI) PB173/01 11. 10. 2011 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) PB173/01 11. 10. 2011 4/18 Část I Atomické operace, bitmapy J. Slabý (ITI) PB173/01 11. 10. 2011 5/18 Atomické operace • asm/atomic. h, Documentation/atomic_ops . txt a atomic.t a = ATOMIC_INIT (5) • Pojme 32 bitů se znaménkem (int) (historicky jen 24) • atomicread, atomicset • atomic_add, atomicinc, atomic.sub, atomic.dec, atomic_*_return a další (LXR) int *addr; atomic.t a; int a = load (addr) ; =4> a = a + 1; store (a, addr) ; atomic.inc(&a) ; /* nebo atomic.add (1 , &a) ; */ Řešení pomocí atomických operací a atomic64_t (drahý na 32-bitu) J. Slabý (ITI) PB173/01 11. 10. 2011 6/18 Práce s atomickými typy O Definice jednoho atomic_t V module_in O Nastavit hodnotu na -3 (nejlépe staticky) O Atomicky: přičíst 1 a přečíst hodnotu O Přečtenou hodnotu vypsat do logu 0 Přičíst 3 0 Odečíst 1 O Přečíst hodnotu a vrátit jako návratovou Atomické bitové operace • Stačí-li 1 bit namísto int a linux/bitops.h, Documentation/atomic_ops . txt • unsigned long a = 0, popř. 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 a bitmap_zero, bitmap.f ill, bitmap_copy • bitmap_OP, kde OP £ {and, or, xor, andnot, complement} • bitmap_empty, bitmap.full, . . . J. Slabý (ITI) PB173/01 11. 10. 2011 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 (%ix) s 63. bitem (pole [bit_word (63) ] z LXR) 0 Výpis celého pole (bitmap_scnprintf) Q Výpis longů obsahující 1 bity (f or_each_set_bit z LXR) O Výpis pozice 1. nastaveného bitu (f ind_f irst_bit) J. Slabý (ITI) PB173/01 11. 10. 2011 9/18 Část II Zámky J. Slabý (ITI) PB173/01 11. 10. 2011 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) • Mutexy • Spící, fronta čekatelů • Pomalejší než spinlock (viz __mutex_lock_common) « Semafory • Podobné mutexům • Počítadlo (jsou rekurzivní) • Dnes se používají výjimečně • Monitory (java) ... Zámky lze držet jen v jádře (po dobu vykonávání syscallu) J. Slabý (ITI) PB173/01 11. 10. 2011 11/18 Zámky v jádře - spinlocky • linux/spinlock.h, Documentation/spinlocks.txt • DEFINE.SPINLOCK(lock),spinlock.t lock • spin_lock, spin_unlock • Podobné pthread spinlockům int *addr; int a = load (addr) a = a + 1; store (a, addr) ; DEFINE.SPINLOCK( addr.lock) int *addr; spin.lock(&addr.lock ) ; int a = load (addr) ; a = a + 1 ; store (a, addr) ; spin.unlock(&addr.lock ) ; Řešení pomocí spinlocků J. Slabý (ITI) PB173/01 11. 10. 2011 12/18 Spinlocky a přerušení Vlákno Přerušení spin.lock(&addr.lock ) ; spin Jock(&addr_lock) ; spin.unlock(&addr.lock ) ; // " deadlock spin _unlock(&addrJock) ; _irq* varianty • Zákaz přerušení, poté spinlock Vlákno Přerušení spin.lock.irq(&addr.lock) ; // interrupt cannot trigger spi n.u nlock.irq (&addr.lock ) ; spin.lock(&addr.lock ) ; spin.unlock(&addr.lock ) ; J. Slabý (ITI) PB173/01 11. 10. 2011 13/18 Zámky v jádře - mutexy Mutexy • linux/mutex.h • DEFINEJMUTEX(name) • mutex.lock, mutex.unlock • Přerušitelné varianty • Signál přeruší čekání • Tyto funkce vracejí hodnotu ne/mám zámek • Podobné pthread mutexům int *addr; DEFINE.MUTEX( addr.lock) ; int *addr; int a = load (addr) ; =4> a = a + 1 ; store (a, addr) ; mutex.lock(&addr.lock) ; int a = load (addr) ; a = a + 1 ; store (a, addr) ; mutex-unlock(&addrJock) ; Řešení pomocí mutexů J. Slabý (ITI) PB173/01 11. 10. 2011 14/18 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) • NEPOUŽÍVAT 9 V nových jádrech už ani není • Hrubozrnný zámek • Pochází z dob počátku Linuxu • lock.kernel, unlock_kernel J. Slabý (ITI) PB173/01 11.10.2011 15/ 18 Úkol Atomické čtení/zápis bufferu o velikosti 128 bytů • Globální buffer • 2 znaková (i mise) zařízení • 1 implementuje . read • 1 implementuje .write • Zápis o Umožněn max. po 5 znacích (.write vrací max. 5) • Spí 10 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 soffpv pb173/04 Pozn. 2: odevzdat s domácím J. Slabý (ITI) PB173/01 11. 10. 2011 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 « Obvyklé typy chyb: ABBA, AA • Obvyklé chyby: lock + if + return •L 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) PB173/01 11. 10. 2011 18/18