Vzájemné vyloučení

Jednoduchá ukázka konfliktu, který vznikne pokud dva procesy současně upravují stejná data. Právě tomu má zabránit algoritmus „vzájemné vyloučení“.

Vzájemné vyloučení (anglicky mutual exclusion, nebo zkráceně mutex) je algoritmus používaný v programování jako synchronizační prostředek. Zabraňuje tomu, aby byly současně vykonávány dva (nebo více) kritické kódy nad stejným sdíleným prostředkem, jako například globální proměnné. Kritický kód je část kódu, ve které proces nebo vlákno přistupuje k veřejným prostředkům. Kritický kód není mechanismus ani algoritmus pro vzájemné vyloučení. Pokud jeden proces vstoupil do kritického kódu a nedokončil poslední instrukci (nevystoupil z kritického kódu), nemůže nad tímto prostředkem žádný jiný proces vstoupit do kritického kódu.

Stavy mutexu

Mutex může nabývat dvou stavů: volný a vlastněný. K tomu udržuje dva druhy informace. Prvním je identifikátor procesu, který mutex drží. Druhým je počet uzamknutí. Počet uzamknutí je vyjádřen číslem, které aktualizuje operace lock (získání mutexu) nebo unlock (uvolnění mutexu). Cílem je zabránění více procesům držet daný mutex. Při vícenásobném uzamknutí musí být i stejný počet odemknutí.

Získání mutexu

Případy, jak proces získá mutex:

• mutex je volný – proces se stává držitelem mutexu a počet uzamknutí je 1
• mutex je vlastněn aktuálním procesem – počet uzamknutí se zvýší o 1
• mutex je vlastněn neaktuálním procesem – proces se zablokuje a čeká na uvolnění mutexu

Uvolnění mutexu

Případy uvolnění mutexu procesem:

• mutex je volný – nedefinovaný stav, nemůže dojít k vyššímu počtu odemčení než bylo zamčení
• mutex je vlastněn aktuálním procesem – počet uzamknutí se sníží o 1, pokud je potom nulový, je uvolněn čekajícím procesům
• mutex je vlastněn neaktuálním procesem – nedefinovaný stav, neaktuální proces nemůže uvolňovat mutex, ten tak nebude uvolněn

Nevýhody

Nesprávné použití mutexu může vést ke zpomalení procesů, kdy většinu času jsou zablokovány ze vzájemného čekání, nebo v horším případě k uváznutí dvou a více procesů. Jako řešení potom musí být alespoň jeden proces ukončen.

Související články

• Synchronizační primitivum
• Kritická sekce
• Monitor (synchronizace)