Semafory a monitory

Semafory, monitory a klasické úlohy

Semafor a mutex se v návodech pravidelně popisují jako dvě jména pro jednu věc: obojí čeká, obojí pouští dovnitř po jednom. Ta věta je nesprávná.

Mutex má vlastníka. Odemkne ho ten, kdo ho zamkl, a nikdo jiný. pthread_mutex_unlock na cizím zámku má nedefinované chování a u typu PTHREAD_MUTEX_ERRORCHECK vrátí EPERM.

Semafor vlastníka nemá. Zvýšit ho může kdokoliv, i vlákno, které nikdy nečekalo. Vypadá to akademicky, dokud nedojdeš k tomu, kde to rozhoduje: sem_post je async-signal-safe a v jádře se up() smí volat z obsluhy přerušení. Mutex tam nemá co dělat - obsluha přerušení nemá vlákno, kterému by zámek patřil.

Stránka je o semaforech, monitorech a úlohách, na kterých se synchronizace učí, a o tom, co z nich zbude pro reálný kód. Předpokládá kritickou sekci a zámky a vlákna. Uváznutí se tu jen předvádí, rozebrané je jinde.

Semafor je počítadlo, ne zámek

Tohle je nejdůležitější věc na celé stránce: semafor není zámek. Je to počítadlo dostupných kusů něčeho.

Deset volných slotů ve vyrovnávací paměti, čtyři volná spojení v poolu. Kdo kus chce, odečte si ho a případně počká. Kdo kus vyrobí, přičte ho.

Když ho inicializuješ na jedničku a obalíš jím kritickou sekci, dostaneš mutex bez kontroly vlastnictví - tedy horší mutex. Zbytek stránky je rozvedení téhle věty.

P a V, čili co vymyslel Dijkstra

Semafor zavedl Edsger Dijkstra v roce 1965 a dal mu dvě operace: P (dnes wait nebo down) počítadlo snižuje, V (dnes signal nebo up) ho zvyšuje. V POSIXu jsou to sem_wait a sem_post. Písmena jsou holandská: P od prolaag, slepence z „probeer te verlagen" (zkus snížit), V od verhogen (zvýšit).

P sníží počítadlo o jedna; kdyby tím kleslo pod nulu, vlákno se místo toho uspí. V počítadlo zvýší a jednoho z čekajících probudí. Kterého, není definované.

Atomicita znamená, že mezi test a změnu počítadla se nikdo nevejde. Nemůže nastat, že dvě vlákna uvidí hodnotu 1 a obě projdou. Do jádra se jde, teprve když se musí spát - jinak by každé sem_wait stálo systémové volání.

Semafor inicializovaný na jedničku je binární, na N obecný čili počítající, kde N je počet kusů zdroje.

Tři věci, které se pletou

	Mutex	Binární semafor	Počítající semafor
Má vlastníka	ano	ne	ne
K čemu je	vzájemné vyloučení	signalizace mezi vlákny	počítání volných kusů
Smí uvolnit jiné vlákno	ne	ano	ano
Umí dědit prioritu	ano	ne	ne
Typické použití	ochrana struktury	probuzení z obsluhy signálu	pool spojení, limit souběžnosti

Z prvního řádku plyne všechno ostatní: vlastnictví říká systému, koho upřednostnit a kdo chyboval.

Monitor: zamykání, které dělá překladač

Monitor je kritická sekce zabalená do datového typu. Data jsou uvnitř, přístup jde jen přes metody a zamykání obstará překladač nebo běhové prostředí, ne ty. Navrhli ho Brinch Hansen a Hoare na začátku sedmdesátých let, protože ruční P a V se neuhlídá.

Vyloučení samo nestačí. Konzument, který uvnitř monitoru najde prázdnou frontu, musí umět počkat a přitom zámek pustit. Na to je podmínková proměnná: wait atomicky uvolní zámek a uspí volajícího, signal probudí jednoho čekajícího. V Javě je tohle celé v jazyce (synchronized, wait, notifyAll), v C to skládáš z pthread_mutex_t a pthread_cond_t, v Pythonu je to threading.Condition.

while, nikdy if

Nejčastější reálná chyba na celé stránce.

// špatně
pthread_mutex_lock(&m);
if (pocet == 0)
    pthread_cond_wait(&cv, &m);   // po probuzení může být pocet pořád 0
vezmi_polozku();
pthread_mutex_unlock(&m);

// správně
pthread_mutex_lock(&m);
while (pocet == 0)                // podmínku ověř znovu po každém probuzení
    pthread_cond_wait(&cv, &m);
vezmi_polozku();
pthread_mutex_unlock(&m);

Důvody jsou dva. Falešná probuzení: POSIX výslovně dovoluje, aby se pthread_cond_wait vrátil, aniž kdokoliv volal signal. A hlavně Mesa sémantika: probuzené vlákno se jen zařadí do fronty na zámek, takže mezi signal a jeho pokračováním stihne projít někdo třetí a položku sebrat. Hoarova sémantika s okamžitým předáním řízení se prakticky neimplementuje, protože by si vynutila přepnutí kontextu.

Napsané v if to bude fungovat měsíce a pak jednou přečteš prázdný slot.

Klasické úlohy a co na nich doopravdy je

Producent a konzument

Jedno vlákno vyrábí položky, druhé je zpracovává, mezi nimi kruhová vyrovnávací paměť o N slotech. Potřebuješ počítadlo volných slotů, počítadlo plných a vyloučení nad ukazateli do bufferu.

sem_t prazdna, plna;             // prazdna = N, plna = 0
pthread_mutex_t mutex;

// producent                     // konzument
sem_wait(&prazdna);              sem_wait(&plna);
pthread_mutex_lock(&mutex);      pthread_mutex_lock(&mutex);
buf[in] = p; in = (in+1) % N;    p = buf[out]; out = (out+1) % N;
pthread_mutex_unlock(&mutex);    pthread_mutex_unlock(&mutex);
sem_post(&plna);                 sem_post(&prazdna);

Klasické zadání používá i na mutex binární semafor. V reálném kódu tam patří pthread_mutex_t: vyloučení vlastníka má, počítání kusů ne.

Teď prohoď u producenta první dva řádky. Zamkne mutex, zjistí, že buffer je plný, a usne se zámkem v ruce. Konzument potřebuje ten samý mutex, aby mohl odebrat položku a slot uvolnit. Nikdo se nehne - učebnicové uváznutí.

Čtenáři a písaři

Sdílenou strukturu smí číst libovolný počet vláken najednou, zapisovat smí jen jedno a nikdo u toho nesmí číst.

Přednost čtenářů pustí dovnitř nového čtenáře, kdykoliv už uvnitř nějaký je. Při stálém přísunu čtenářů se písař ke slovu nedostane nikdy. Přednost písařů zastaví příchozí čtenáře, jakmile někdo čeká na zápis; vyhladovět pak můžou čtenáři, ale jen když se zapisuje pořád.

Potkáš to u zámku nad konfigurací, kterou čte osm vláken a přepisuje se při reloadu, a u cache. Nepiš vlastní semafory, ber pthread_rwlock_t. V glibc je výchozí čtenářská přednost, písaře upřednostní atribut PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP.

Večeřící filozofové

Pět filozofů u kulatého stolu, mezi každými dvěma jedna vidlička, k jídlu jsou potřeba obě. Každý vezme nejdřív levou, pak pravou.

Když je vezmou všichni současně, drží každý jednu a čeká na druhou. Učebnicově dobré je to proto, že kód každého filozofa je zjevně správný a chyba je až v kruhu.

• Omez počet u stolu na čtyři. Semafor inicializovaný na 4; při čtyřech vždycky někdo dojí.
• Jeden filozof bere v opačném pořadí. Kruh se rozpojí, zmizí jednotný směr čekání.
• Ber obě vidličky atomicky. Pod jedním zámkem se ověří obě a buď se vezmou, nebo nic.

Do reálného kódu ber druhé řešení zobecněné na globální pořadí zámků. Očísluj zámky, třeba adresou struktury, a ber je vždycky vzestupně. Cyklické čekání tím zmizí v celém programu.

Bariéra

Bariéra je opačný problém: nechceš pouštět po jednom, chceš, aby se sešli všichni. N vláken zavolá pthread_barrier_wait a nikdo nepokračuje, dokud nedorazí poslední.

pthread_barrier_init(&b, NULL, 8);   // osm vláken, jedno na jádro
pthread_barrier_wait(&b);            // poslední příchozí pustí všechny naráz

Hodí se na výpočet po krocích, kde další krok smí začít, až dopočítají všechna jádra.

Proč semafor neumí dědit prioritu

Semafor nemá vlastníka, takže systém neví, čí prioritu má při čekání zvednout. Mutex to ví, a proto umí dědění priority: čeká-li vysokoprioritní vlákno na zámek držený nízkoprioritním, to nízkoprioritní na tu dobu prioritu dostane. Podrobnosti jsou u uváznutí a plánování.

V červenci 1997 se Mars Pathfinder začal na Marsu sám resetovat. Nízkoprioritní úloha sběru meteodat držela mutex nad sdílenou sběrnicí, středně prioritní komunikační úloha ji vytlačila z procesoru a vysokoprioritní správce sběrnice marně čekal na ten zámek. Hlídací časovač usoudil, že správce nedoběhl, a restartoval systém - opakovaně a se ztrátou dat.

Dědění priority ve VxWorksu bylo k dispozici, jen vypnuté; tým JPL ho zapnul na dálku. Poučení: každá úloha zvlášť byla napsaná správně a na Zemi se to nikdy nestalo.

Co používat dnes

V C ber pthread_mutex_t plus pthread_cond_t. To je monitor a pokryje většinu situací uvnitř procesu.

Semafor si nech na počítání zdrojů. Pool spojení, limit souběžných úloh, sloty ve frontě.

Ve vysokoúrovňových jazycích ber, co je v knihovně. Fronta z queue v Pythonu nebo BlockingQueue v Javě řeší producenta a konzumenta odladěně.

Mezi procesy ber pojmenované POSIX semafory. sem_open("/muj_sem", O_CREAT, 0600, 1) vytvoří semafor viditelný podle jména napříč procesy - most k meziprocesové komunikaci. Objeví se jako soubor /dev/shm/sem.muj_sem a přežije konec procesu, dokud ho někdo nesmaže přes sem_unlink.

Co se dnes už nedělá: semafory System V přes semget a semop. Mají nepříjemné rozhraní a zůstávají v jádře i po pádu programu. V návodech přežívají proto, že jsou starší než POSIXové. Linux od jádra 2.6.16 (rok 2006) většinu vnitřních semaforů nahradil typem struct mutex.

Diagnostika

ipcs -s                                # pole semaforů System V a jejich vlastník
ls -l /dev/shm/sem.*                   # pojmenované POSIX semafory, jeden soubor na semafor
strace -f -e trace=futex ./program     # -f i pro vlákna; na futexu stojí mutex i condvar
gdb -p $(pidof program)                # a uvnitř: thread apply all bt

Na zaseknutém programu pusť jako první thread apply all bt. Ukáže zásobník každého vlákna; když jich pět visí ve pthread_cond_wait, máš seznam podezřelých. Ostatní nástroje až potom.

Příznak	Kde je problém
Zasekne se po hodinách, procesor na nule	uváznutí; podívej se, kdo na čem visí
Zasekne se hned s plným bufferem	prohozené sem_wait a pthread_mutex_lock
Konzument občas přečte prázdný slot	pthread_cond_wait v if místo while
signal se ztratil, nikdo se neprobudil	podmínková proměnná si nic nepamatuje
Písaři se nedostanou ke slovu	čtenářská přednost v pthread_rwlock_t
Semafor přežil pád procesu zamčený	ipcrm -s ID nebo sem_unlink

Čtvrtý řádek je pointa celé stránky. sem_post na semaforu, na kterém nikdo nečeká, počítadlo zvýší a to zvýšení tam zůstane - kdo přijde za hodinu, projde bez čekání. pthread_cond_signal na podmínkové proměnné, na které nikdo nečeká, neudělá nic a zmizí beze stopy. Proto se u ní stav mění pod zámkem a testuje ve smyčce.

Co si odnést

Semafor je počítadlo kusů, ne zámek. Použitý jako zámek je to mutex bez vlastnictví.

Vlastnictví je ta funkční odlišnost. Plyne z něj dědění priority i to, že mutex nepatří do obsluhy přerušení.

wait u podmínkové proměnné patří do while. Falešná probuzení a Mesa sémantika, ne opatrnost.

Semafor si zvýšení pamatuje, podmínková proměnná ne. Ztracený signal je reálná kategorie chyby.

Nejdřív semafor, až pak mutex. Prohozené pořadí položí producenta s konzumentem okamžitě.

Filozofové jsou o globálním pořadí zámků. Ber je vždycky ve stejném směru a cyklus nevznikne.

Kam dál

• Kritická sekce a zámky - souběh a atomicita
• Uváznutí - čtyři podmínky, detekce a inverze priorit
• Meziprocesová komunikace - synchronizace mezi procesy
• Vlákna - co sdílejí, a proto co je nutné chránit
• Nástroje a diagnostika - čím se dívat na běžící proces