Souběh, kritické sekce

Při psaní kódu našeho modulu dskel jsme zatím víceméně opomíjeli fakt, že kód ovladače může a také většinou je vykonáván více programy současně - říkáme, že kód je vykonáván na kontextu více programů.

Tehdy může dojít k situaci, kdy výsledek paralelního běhu více programů je závislý na pořadí přístupu programů ke sdíleným datům. Této situaci říkáme souběh (race conditions). Může k ní dojít nejen na strojích s více procesory (SMP systémy), ale i na jednoprocesorovém stroji, který má jen jedno fyzické jádro.

Jak je to možné? Uvědomme si, že většina moderních operačních systémů umožňuje běh více uživatelských programů současně. Buď má počítač skutečně více procesorů nebo je paralelní běh několika programů realizován přepínáním programů tak, aby každý z nich měl na chvíli k dispozici procesor, zatímco ostatní čekají

Toto přepínání, kdy spuštěné programy na chvíli vlastní procesor nebo čekají, až jej dostanou k dispozici, se nazývá multitasking. V tomto textu budeme vždy mluvit o tzv. preemtivním multitaskingu, v němž je zajištěno, že procesor má každý program k dispozici jen na přesně definovaný krátký okamžik, cca několik milisekund.. Každý takový uživatelský program pak samozřejmě může přistupovat i na náš modul a vykonávat tak jeho kód současně (počítač s více CPU) nebo pseudosoučasně (počítač s jedním CPU) s ostatními programy.

Vedle toho je přirozeným zdrojem souběhu také hardwarové a softwarové přerušení. Přerušení totiž skutečně na krátkou chvíli přeruší normální běh programu, protože místo programu, který běžel, je vykonáván kód obsluhy přerušení. A v rámci obsluhy přerušení může samozřejmě být i proveden kód, který přistupuje k nějakým sdíleným datům (globální proměnná, apod.).

Je tedy zřejmé, že problémům se souběhem se nevyhneme i v případě relativně jednoduchých ovladačů, protože i ty, byť neobsluhují přerušení, mohou být používány více uživatelskými programy současně.

Jádrem všech problémů se souběhem samozřejmě nejsou funkce, ale data, která jsou sdílena, tj. je možné k nim přistupovat z kontextu více programů. Jde o globální proměnné, ať už proměnné primitivního typu nebo proměnné typu složitějších struktur. Snadno se pak stane, že kód vykonávaný na kontextu programu A danou globální proměnou vyčítá, zatímco kód běžící na kontextu programu B její hodnotu mění. Jakou hodnotu vyčte kód vykonávaný programem A? Původní nebo novou? Nebo staronovou (část staré, část nové)?

Problémům se sdílením dat se dá předejít použitím tzv. kritické sekce. Kritická sekce je ohraničená část kódu, kterou může v daný moment vykonávat zaručeně jen jeden program. Toho docilujeme použitím synchronizačních primitiv - mechanismů, které ostatní programy donutí počkat, dokud jiný program nedokončí vykonávání kódu v kritické sekci. Tyto primitiva chrání přístup do kritické sekce. Základní synchronizační nástroje si stručně představíme.

Každý kód, který přistupuje ke sdíleným datům by tedy měl být upraven tak, aby se stal kritickou sekcí, tzn. aby k datům bylo možné přistupovat vzájemně výlučně s ostatními programy. Říkáme pak, že k datům přistupujeme v kritické sekci.

Pro úplnost dodávám, že použití kritických sekcí a s tím spojené používání synchronizačních mechanismů snižuje výkon a je zdrojem řady chyb, které se velmi obtížně ladí. Dobrý návrh ovladače se proto nejprve snaží počet sdílených proměnných omezit na opravdu nezbytné minimum.

Atomické proměnné

Nejlepší kritickou sekcí je žádná kritická sekce. Ano, skutečně, existují synchronizační mechanismy, které zaručí vzájemně výlučný přístup ke sdíleným datům, ale přitom není vyžadováno použití kritické sekce. Jedním z nich jsou i atomické proměnné. Jsou to speciální proměnné, u nichž je zajištěno, že přístup k nim bude výlučný. Lze je s výhodou použít tam, kde bychom jinak museli přístup k proměnné primitivního typu (int, bool apod.) chránit pomocí kritické sekce.

Všechny atomické proměnné jsou v linuxovém jádře typu atomic_t, který má šířku 32bitů (dříve jen 24bit). Při jejich používání musíme do svého zdrojového kódu vložit hlavičkový soubor <asm/atomic.h>. Inicializaci atomické proměnné zařídí makro ATOMIC_INIT(var). Ukázka:

atomic_t done = ATOMIC_INIT(0);

Na atomické proměnné nemůže přestupovat pomocí běžných operátorů jako je přiřazení apod. Musíme používat definovanou množinu operací. Uvedeme jen ty nejpoužívanější. Jejich kompletní množina je dostupná v souboru <asm/atomic.h>.

// prirazeni hodnoty v dobe kompilace
atomic_t var = ATOMIC_INIT(value);

// prirazeni hodnoty ’value’ do promenne ’v’
void atomic_set(atomic_t * v, int value);

// vycteni hodnoty z atomicke promenne ’v’
int atomic_read(atomic_t * v);

// zvyseni a snizeni hodnoty promenne ’v’ o jednicku
void atomic_inc(atomic_t * v);
void atomic_dec(atomic_t * v);

// pricteni hodnoty ’i’ k hodnote promenne ’v’
void atomic_add(int i, atomic_t * v);
void atomic_sub(int i, atomic_t * v);

Výhoda použití atomických proměnných je v tom, že mají velmi malou režii. Na řadě architektur jsou totiž pro operace s atomickými proměnnými vyhrazeny přímo speciální instrukce.

Spinlocky

Spinlocky patří mezi synchronizační mechanismy, které se používají pro kontrolu přístupu ke kritické sekci. Princip jejich činnosti je jednoduchý. První proces, který vstoupí do kritické sekce chráněné spinlockem, zamkne spinlock a pokračuje ve vykonávání kódu uvnitř kritické sekce. Ostatní procesy při pokusu vstoupit do kritické sekce zjistí, že spinlock je zamčený, a začnou ve smyčce testovat stav spinlocku tak dlouho, dokud není odemčen. To znamená do doby než první proces opustí kritickou sekci a spinlock odemkne. Pak si spinlock může zamknout zase jiný proces.

Čekání na odemčení spinlocku (na vstup do kritické sekce) je tedy z principu aktivní. Což znamená, že čekající procesy zatěžují CPU, ale zase na druhou stranu tyto procesy nemohou být během tohoto čekání uspány. Tato vlastnost spinlocku určuje oblast jeho použití:

Obsluha přerušení, protože zde není možné se vzdát procesoru a jít spát.
Uživatelské funkce volané při obsluze časovačů. Časovače jsou totiž v jádře implementované s použitím softwarového přerušení, takže platí to samé co pro klasické přerušení.
Obecně krátké kritické sekce. Spinlock má totiž malou režii, takže pro velmi krátké sekce je výhodnější než jiné synchronizační mechanismy.

Kód v kritické sekci chráněné spinlockem musí splňovat několik kriterií:

musí být co nejkratší,
nesmí obsahovat funkce, které mohou způsobit uspání procesu (funkce pro přenos dat mezi prostorem jádra a uživatelským prostorem, funkce pro alokaci paměti atd.)
a musí být nepřerušitelný, tj. atomický - během jeho vykonávání nesmí nastat přerušení, v jehož obsluze by se vstupovalo do stejné kritické sekce, tj. na stejná sdílená data.

O takovém kódu říkáme, že je atomický, resp. že je vykonáván v atomickém kontextu. Např. kód obsluhy přerušení a kód uživatelských funkcí volaných v obsluze časovačů musí být atomický.

Spinlock se deklaruje jako proměnná typu spinlock_t a je třeba jej před prvním použitím inicializovat pomocí funkce spin_lock_init() nebo případně v čase kompilace i použitím makra DEFINE_SPINLOCK(lock). Nicméně použití uvedené funkce je preferovanější. Při používání spinlocku si musíme do zdrojového souboru vložit soubor <linux/spinlock.h>.

Prototypy:

// inicializace spinlocku
void spin_lock_init(spinlock_t * lock);

// zamceni a odemceni spinlocku
void spin_lock(spinlock_t * lock);
void spin_unlock(spinlock_t * lock);

Příklad použití:

1// inicializace
2spinlock_t mylock;
3spin_lock_init(&mylock);
4
5// kriticka sekce
6spin_lock(&mylock);
7
8/* ... chraneny kod ... */
9
10spin_unlock(&mylock);

Je důležité si pamatovat, že vícenásobné zamčení spinlocku stejným procesem skončí zablokováním procesu.

Uvedené funkce pro zamykání a odemykání spinlocku postačují v případě, že se na sdílená data nepřistupuje z obsluhy přerušení nebo z uživatelské funkce volané v obsluze časovače. Proč? Protože funkce spin_lock() a spin_unlock() nevypínají přerušení (ani hardwarové ani softwarové). Kvůli tomu kód v kritické sekci přestává být atomický - jeho vykonávání může být přerušeno obsluhou přerušení, která se pokouší vstoupit do kritické sekce, tj. zamknout spinlock, který je už ale zamčen uživatelským programem. Dojde tak k zatuhnutí systému, protože nelze dokončit obsluhu přerušení. Zároveň uživatelský program není s to opustit kritickou sekci, jelikož jeho běh je přerušen obsluhou přerušení.

Proto v situaci, kdy se na sdílená data přistupuje i z obsluhy přerušení anebo i v obsluze časovače, je nutné použít tyto funkce:

// vypne a pak zase zapne obsluhu vsech preruseni (hw i sw)
// a ulozi stav masky preruseni
void spin_lock_irqsave(spinlock_t * lock, unsigned long flags);
void spin_unlock_irqsave(spinlock_t * lock, unsigned long flags);

// vypne a pak zase zapne obsluhu vsech preruseni (hw i sw)
void spin_lock_irq(spinlock_t * lock);
void spin_unlock_irq(spinlock_t * lock);

// vypne a pak zase zapne obsluhu sw preruseni (hw jsou stale povolena)
void spin_lock_bh(spinlock_t * lock);
void spin_unlock_bh(spinlock_t * lock);

Funkce spin_lock_bh() a spin_unlock_bh() použijeme v případě, kdy se na sdílená data přistupuje na kontextu uživatelského procesu a zároveň v obsluze časovače nebo když spolu data sdílí více časovačů. Ostatní funkce využijeme v případě, kdy se ke sdíleným datům přistupuje i z obsluhy hardwarového přerušení.

Tyto rozšířené funkce musíme používat jak v kódu volaném na kontextu uživatelského programu tak i v obsluze časovače či přerušení. Bylo by vážnou chybou použít funkci spin_lock() v kódu volaném uživatelským programem a funkci spin_lock_bh() v obslužné funkci časovače.

Poslední zajímavou funkcí je funkce spin_trylock(), která vrátí 0, pokud je spinlock již zamčen jiným procesem nebo 1, pokud je odemčen. V tomto případě jej zároveň zamkne. Toto chování je výhodné v situaci, kdy chceme místo čekání na odemčení spinlocku dělat něco jiného.

Mutexy

Mutexy jsou dalším synchronizačním primitivem, který umí ochránit kritickou sekci. Podobně jako spinlocky mají jen dva stavy - zamčeno/odemčeno. Na rozdíl od spinlocků jsou však čekající procesy uspány a tak nespotřebovávají čas procesoru. K jejich probuzení dojde až v okamžiku odemčení mutexu, kdy jeden z nich má právo znovu zamknout mutex a vstoupit do kritické sekce. Ostatní jsou znovu uspány. Výběr kandidáta na vstup do kritické sekce je řešen tak, aby se do ní dostaly všechny čekající procesy v rozumně krátkém čase.

Kvůli uspávání čekajících procesů se mutexy nehodí pro ochranu kritických sekcí, ke kterým se přistupuje z obsluhy přerušení nebo časovačů.

Podobně jako u spinlocků, není možné mutex zamknout tímtéž procesem více jak jednou. Jinak dojde k zablokování procesu.

Mutex se deklaruje jako proměnná typu mutex. K jeho inicializaci se používá funkce mutex_init(), která je stejně jako funkce pro zamykání a odemykání mutexu deklarovaná v hlavičkovém souboru <linux/mutex.h>.

Prototypy:

// inicializace mutexu
void mutex_init(struct mutex * mt);

// zamceni a odemceni mutexu
void mutex_lock(struct mutex * mt);
void mutex_unlock(struct mutex * mt);

Příklad použití:

1// inicializace
2struct mutex mymux;
3mutex_init(&mymux);
4
5// kriticka sekce
6mutex_lock(&mymux);
7
8/* ... chraneny kod ... */
9
10mutex_unlock(&mymux);

I mutex je možné zamknout neblokujícím způsobem pomocí funkce mutex_trylock(), která mutex zamkne a vrátí 1, případně vrátí 0, pokud byl už mutex zamčen jiným procesem.

Protože je čekání na odemčení mutexu nepřerušitelné (a to ani signálem), tak je k dispozici také funkce mutex_lock_interruptible(), která, pokud čeká na odemčení mutexu, může být přerušena signálem. Tehdy vrátí chybu -EINTR, kterou je nejlépe hned předat volající funkci a ukončit tak systémové volání. Jestliže se podaří mutex zamknout, funkce vrátí 0.

Příklad:

1res = mutex_lock_interruptible(&mymux);
2if ( res == 0 )
3{
4      /* ... chraneny kod ... */
5
6      mutex_unlock(&mymux);
7}
8
9return res;

Používání přerušitelných funkcí je preferované z toho důvodu, že je pak možné přerušit běh uživatelského procesu stiskem kláves Ctrl+C, i když program čeká na odemčení mutexu.

Semafory

Jsou jedním z nejstarších synchronizačních primitiv. Podobně jako v případě mutexů způsobí čekání na zamčeném semaforu uspání čekajícího procesu. Proto ani semafory nemohou být použity v kódu obsluhy přerušení či časovače.

Na rozdíl od mutexů a spinlocků není semafor dvoustavový. Je realizován jako čítač, který je vždy s každým zamčením semaforu snížen o jedničku. Jakmile jeho hodnota klesne na nulu, je proces, který toto způsobil, uspán a čeká, až nějaký jiný proces vystoupí z kritické sekce a zvedne tak hodnotu semaforu na kladnou nenulovou hodnotu. Semafor tímto způsobem zajišťuje, že v kritické sekci nebude více procesů, než je povoleno.

Počet procesů, které mohou vstoupit do kritické sekce, je dán počáteční hodnotou, resp. počtem odemčení semaforu. Může být nastaven např. na jedničku, pak se semafor chová jako mutex. Nebo na nulu, pak je semafor od začátku zamčen.

Níže uvádíme typ semaphore a prototypy funkcí včetně příkladu jejich použití. Samozřejmě je potřeba do zdrojového kódu vložit hlavičkový soubor <linux/semaphore.h>:

// inicializace semaforu
void sema_init(struct semaphore *sem, int val);

// zamceni a odemceni semaforu
void down(struct semaphore *sem);
void up(struct semaphore *sem);

// prerusitelne zamceni semaforu
int down_interruptible(struct semaphore *sem);

Příklad použití:

1// inicializace 
2struct semaphore mysem;
3sema_init(&mysem, 2);
4
5// kriticka sekce - neprerusitelne cekani
6down(&mysem);
7
8/* ... chraneny kod ... */
9
10up(&mysem);
11
12// kriticka sekce - prerusitelne cekani
13// => preferovany zpusob pouziti
14res = down_interruptible(&mysem);
15if ( res == 0 )
16{
17     /* ... chraneny kod ... */
18
19     up(&mysem);
20}
21
22return res;

I v případě semaforu je k dispozici přerušitelná funkce pro zamčení semaforu down_interruptible(), kterou se doporučuje používat místo nepřerušitelné funkce down().

A samozřejmě je k dispozici i neblokující zamykací funkce down_trylock(), která netypicky vrací 1, když je semafor již zamčen, a 0, když byl semafor odemčen a podařilo se jej zamknout.