# 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 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](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.

```c
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í](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í.

```c
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í](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

```bash
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](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