Operační systémy pro mobilní zařízení (OSMZ)
Týden IV. (1.3.-5.3.2021)
V implementační úloze zadané minulý týden se vyskytuje použití semaforu. Ten je jednou z IPC metod (Inter-Process Communication) kterými se budeme detailněji zabývat. Meziprocesová komunikace je sadou technik pro výměnu dat mezi dvěma nebo více procesy případně vlákny. V našich implementačních úkolech se zaměřujeme jen na mezivláknovou komunikaci nicméně tyto mechanismy jsou obecné a aplikovatelné i mezi procesy. V prezentaci najdete výčet nejpoužívanějších metod. Tabulka v zásadě kopíruje tu, kterou naleznete s odkazy na Wikipedii.
Protože budete používat v implementace semafor, pojďme si ho popsat podrobněji. Semafor je jednoduchý synchronizační prostředek, v podstatě jen počítadlo určené k přidělování (počítání) zdrojů. Proto s ním lze dělat tyto věci: Zjistit aktuální hodnoty semaforu (v Androidu availablePermits()) Je-li vnitřní hodnota semaforu kladná, proces/vlákno může zdroj využít. Dekrementuje přitom hodnotu semaforu o 1 (případně jinou předanou hodnotu) metodou acquire()) Je-li vnitřní hodnota semaforu 0, nebo by pod tuto hodnotu klesla použitím metody acquire s argumentem, je vlákno uspán až do doby, kdy jsou zdroje uvolněny a semafor nabude kladné hodnoty. Uvolňování zdrojů se realizuje metodou release(). Pokud chcete ověřit zda-li daný zdroj je k dispozici v požadovaném počtu a nechcete vyvolat zablokování, můžete použít metodu tryAcquire() která v případě úspěchu odebere odpovídající počet permits, vrátí true a chová se stejně jako acquire(), ale v okamžiku, kdy je nedostatek zdrojů, tak se oproti acquire() nezablokuje a jen vrátí návratovou hodnotu false.
Pokud bychom se podívali na implementaci semaforu přímo v Linuxovém jádře, zjistíme, že je opravdu velmi jednoduchý a i v současné podobě dobře čitelný.
kernel/locking/semaphore.c
Samotná struktura semaforu v sobě má kromě kromě zámku realizované spinlockem a počítadlem ještě seznam čekajících, aby se zamezilo možnosti, že si ho nějaký proces "přivlastní" (velmi zjednodušeně řečeno).
include/linux/semaphore.h
Samotné atomické funkce semaforů by nefungovaly bez odpovídající podpory ze strany hardwaru. U architektury x86 bychom našli v implementaci spinlock
/include/asm-generic/qrwlock.h a /arch/x86/include/asm/cmpxchg.h
použití instrukce instrukce CMPXCHG, která v případě Intelu odpovídá abstraktní instrukci TST (test and set lock) zmíněnou v prezentacích.
Pro demonstraci synchronizačních problémů a jejich řešení skrz IPC mecha\nismy se používají tyto klasické problémy (nemusíte znát detailně, jen dokázat shrnout o jaký typ problému se jedná):
- Problém večeřících filozofů
- Problém producenta a spotřebitele
- Problém čtenářů a zapisovatelů
- Problém spícího holiče
- Problém kuřáků cigaret
Součástí Android SDK (ukázky projektů) jsou i řešení většiny těchto problémů.
PREZENTACE
LITERATURA
Andrew S. Tanenbaum - Moderní operační systémy. 4. vydání:
- Kapitola 2.3 Mezi-procesní komunikace (str. 119 – 146)
- Kapitola 2.5 Klasické IPC problémy (str. 167 – 169)
- Kapitola 6.7 Různé problémy (str. 458 – 463)
BONUS MATERIÁLY
Problém s plánovačem a IPC ve vozítku Pathfinderu na Marsu a málem jeho ztráty.
Problém souběhu u radiologického přístroje Therac-25 s několika desítkami postižených pacientů
OTÁZKY
Po přečtení výše uvedených textů byste měli být schopni odpovědět na další otázky z okruhů ke zkoušce, konkrétně:
- Vysvětlete pojem meziprocesová komunikace (IPC) a uveďte několik příkladů IPC metod.
- Vysvětlete pojem souběh (race condition), kdy nastává a jakým způsobem mu lze předcházet.
- Vysvětlete pojem semafor, operace, příklad použití.