Semafory-a-monitory.md

# 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í](Preruseni-a-vyjimky). 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](Kriticka-sekce-a-zamky) a [vlákna](Vlakna). Uváznutí se tu jen předvádí, rozebrané je [jinde](Uvaznuti). ## 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í](Systemova-volani). 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. ```c// špatněpthread_mutex_lock(&m);if (pocet == 0)    pthread_cond_wait(&cv, &m);   // po probuzení může být pocet pořád 0vezmi_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](Prepinani-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. ```csem_t prazdna, plna;             // prazdna = N, plna = 0pthread_mutex_t mutex; // producent                     // konzumentsem_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í](Uvaznuti). ### Č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í. ```cpthread_barrier_init(&b, NULL, 8);   // osm vláken, jedno na jádropthread_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í](Uvaznuti) a [plánování](Planovani-procesu). 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](Meziprocesova-komunikace). 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 ```bashipcs -s                                # pole semaforů System V a jejich vlastníkls -l /dev/shm/sem.*                   # pojmenované POSIX semafory, jeden soubor na semaforstrace -f -e trace=futex ./program     # -f i pro vlákna; na futexu stojí mutex i condvargdb -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](Nastroje-a-diagnostika) 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](Kriticka-sekce-a-zamky)** - souběh a atomicita- **[Uváznutí](Uvaznuti)** - čtyři podmínky, detekce a inverze priorit- **[Meziprocesová komunikace](Meziprocesova-komunikace)** - synchronizace mezi procesy- **[Vlákna](Vlakna)** - co sdílejí, a proto co je nutné chránit- **[Nástroje a diagnostika](Nastroje-a-diagnostika)** - čím se dívat na běžící proces