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á):

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í.