Kritická sekce - Critical section

V souběžném programování mohou souběžné přístupy ke sdíleným prostředkům vést k neočekávanému nebo chybnému chování, takže části programu, kde je přístup ke sdílenému prostředku, je třeba chránit způsoby, které se vyhýbají souběžnému přístupu. Tato chráněná část je kritická část nebo kritická oblast. Nelze jej spustit více než jedním procesem najednou. Kritická část obvykle přistupuje ke sdílenému prostředku, jako je datová struktura , periferní zařízení nebo síťové připojení, které by v kontextu více souběžných přístupů nefungovalo správně.

Potřeba kritických sekcí

Různé kódy nebo procesy se mohou skládat ze stejné proměnné nebo jiných zdrojů, které je třeba číst nebo zapisovat, ale jejichž výsledky závisí na pořadí, ve kterém se akce vyskytnou. Například pokud má proměnná x číst proces A a proces B musí zapisovat do stejné proměnné x současně, může proces A získat starou nebo novou hodnotu x .

Proces A:

// Process A
.
.
b = x + 5;               // instruction executes at time = Tx
.

Proces B:

// Process B
.
.
x = 3 + z;               // instruction executes at time = Tx
.
Obr. 1: Vývojový graf znázorňující potřebu kritického řezu

V takových případech je důležitá kritická část. Ve výše uvedeném případě, pokud A potřebuje číst aktualizovanou hodnotu x , provádění procesu A a procesu B současně nemusí poskytnout požadované výsledky. Aby se tomu zabránilo, je proměnná x chráněna kritickou částí. Nejprve B získá přístup do sekce. Jakmile B dokončí zápis hodnoty, A získá přístup do kritické sekce a lze číst proměnnou x .

Pečlivým řízením toho, které proměnné jsou upraveny uvnitř a vně kritické sekce, je zabráněno souběžnému přístupu ke sdílené proměnné. Kritická část se obvykle používá, když program s více vlákny musí aktualizovat více souvisejících proměnných, aniž by samostatné vlákno provádělo konfliktní změny těchto dat. V související situaci lze kritickou část použít k zajištění, že ke sdílenému prostředku, například tiskárně, lze přistupovat pouze po jednom procesu najednou.

Implementace kritických úseků

Implementace kritických sekcí se u různých operačních systémů liší.

Obr. 2: Zámky a kritické sekce ve více vláknech

Kritická část obvykle skončí v konečném čase a vlákno, úkol nebo proces bude muset čekat na pevný čas, než jej zadá ( ohraničené čekání ). Aby bylo zajištěno výhradní použití kritických sekcí, je při vstupu a výstupu z programu vyžadován nějaký synchronizační mechanismus.

Kritická část je součástí programu, který vyžaduje vzájemné vyloučení přístupu.

Jak je znázorněno na obr. 2, v případě vzájemného vyloučení (Mutex) blokuje jedno vlákno kritickou sekci pomocí technik zamykání, když potřebuje přístup ke sdílenému prostředku, a ostatní vlákna musí počkat, až se dostanou do tahu. To zabrání konfliktům, když dva nebo více vláken sdílí stejný paměťový prostor a chtějí získat přístup ke společnému prostředku.

Obrázek 3: Pseudokód pro implementaci kritické sekce

Nejjednodušší metodou, jak zabránit jakékoli změně řízení procesoru uvnitř kritické sekce, je implementace semaforu. V uniprocesorových systémech to lze provést deaktivací přerušení při vstupu do kritické sekce, vyhýbáním se systémovým voláním, které mohou způsobit přepnutí kontextu, zatímco je v sekci, a obnovením přerušení do jejich předchozího stavu při ukončení. Jakýkoli podproces provádění vstupující do kterékoli kritické sekce kdekoli v systému bude s touto implementací bránit tomu, aby bylo jakémukoli jinému podprocesu, včetně přerušení, poskytnut čas zpracování na CPU - a tedy vstupu do kterékoli další kritické sekce nebo dokonce jakéhokoli kódu vůbec - dokud původní vlákno neopustí svou kritickou část.

Tento přístup hrubou silou lze vylepšit pomocí Semaforů . Chcete-li vstoupit do kritické sekce, musí vlákno získat semafor, který uvolní při opuštění sekce. Jiným vláknům je zabráněno ve vstupu do kritické sekce ve stejnou dobu jako původní vlákno, ale mohou získat kontrolu nad CPU a spustit další kód, včetně dalších kritických sekcí, které jsou chráněny různými semafory. Zamykání semaforu má také časový limit, aby se zabránilo zablokování, při kterém je zámek získán jediným procesem po neomezenou dobu, čímž se zastaví ostatní procesy, které potřebují použít sdílený prostředek chráněný kritickou částí.

Použití kritických sekcí

Kritické sekce na úrovni jádra

Kritické sekce obvykle zabraňují migraci vláken a procesů mezi procesory a předcházení procesům a vláknům přerušením a jinými procesy a vlákny.

Kritické sekce často umožňují vnoření. Vnořování umožňuje zadávat a opouštět více kritických sekcí za nízkou cenu.

Pokud plánovač přeruší aktuální proces nebo vlákno v kritické sekci, plánovač buď umožní probíhajícímu procesu nebo vláknu běžet až do dokončení kritické sekce, nebo naplánuje proces nebo vlákno na další úplné kvantum. Plánovač nebude migrovat proces nebo vlákno do jiného procesoru a nebude plánovat spuštění jiného procesu nebo vlákna, když je aktuální proces nebo vlákno v kritické části.

Podobně, pokud dojde k přerušení v kritické části, informace o přerušení se zaznamená pro budoucí zpracování a provedení se vrátí do procesu nebo vlákna v kritické části. Jakmile je kritická část opuštěna a v některých případech je naplánované kvantum dokončeno, bude provedeno nevyřízené přerušení. Koncept kvantového plánování se vztahuje na zásady „každý s každým “ a podobné plánovací politiky .

Protože kritické sekce se mohou spouštět pouze na procesoru, na kterém jsou zadány, je synchronizace vyžadována pouze v rámci provádějícího procesoru. To umožňuje vstup a výstup z kritických sekcí s téměř nulovými náklady. Není nutná synchronizace mezi procesory. Je nutná pouze synchronizace toku instrukcí. Většina procesorů poskytuje požadované množství synchronizace jednoduchým aktem přerušení aktuálního stavu provádění. To umožňuje, aby kritické sekce ve většině případů nebyly ničím jiným než počtem zadaných kritických sekcí na procesor.

Vylepšení výkonu zahrnují provádění nevyřízených přerušení na konci všech kritických sekcí a umožnění spuštění plánovače na konci všech kritických sekcí. Kromě toho mohou být čekající přerušení přenesena do jiných procesorů k provedení.

Kritické sekce by se neměly používat jako dlouhodobý uzamykací primitiv. Kritické sekce by měly být udržovány dostatečně krátké, aby je bylo možné zadávat, spouštět a opouštět bez jakýchkoli přerušení hardwaru a plánovače.

Kritické sekce na úrovni jádra jsou základem problému se zablokováním softwaru .

Kritické sekce v datových strukturách

V paralelním programování je kód rozdělen do vláken. Read-write konfliktní proměnné jsou rozděleny mezi závity a každé vlákno má jejich kopie. Datové struktury, jako jsou propojené seznamy , stromy , hash tabulky atd., Mají datové proměnné, které jsou propojeny a nelze je rozdělit mezi vlákna, a proto je implementace paralelismu velmi obtížná. Chcete-li zlepšit účinnost implementace datových struktur více operací, jako je vkládání, mazání, je třeba provádět paralelní vyhledávání. Při provádění těchto operací mohou nastat scénáře, kdy je stejný prvek prohledáván jedním vláknem a je mazán jiným. V takových případech může být výstup chybný . Vlákno, které prohledává prvek, může mít přístup, zatímco druhé vlákno ho může po této době smazat. Tyto scénáře způsobí problémy v běžícím programu poskytnutím nepravdivých dat. Aby se tomu zabránilo, jedna metoda spočívá v tom, že celá datová struktura může být udržována v kritické sekci, takže je zpracovávána pouze jedna operace najednou. Jinou metodou je uzamčení používaného uzlu v kritické sekci, aby ostatní operace nepoužívaly stejný uzel. Použití kritické sekce tedy zajišťuje, že kód poskytuje očekávané výstupy.

Kritické části počítačových sítí

Kritické části jsou také nutné v počítačových sítích. Když data dorazí do síťových zásuvek , nemusí dorazit v objednaném formátu. Řekněme, že program 'X' běžící na stroji potřebuje shromáždit data ze zásuvky, změnit jejich uspořádání a zkontrolovat, zda něco chybí. Zatímco tento program pracuje na datech, žádný jiný program by neměl přistupovat ke stejné zásuvce pro tato konkrétní data. Proto jsou data soketu chráněna kritickým oddílem, takže program 'X' je může používat výhradně.

Viz také

Reference

externí odkazy