Jeśli zagwarantowane jest wzajemne wykluczenie, powiedzmy semaforami, program jest zakleszczony?

Question

Definiuję wzajemne wykluczenie i zakleszczenie odpowiednio poniżej: Warunek wykluczenia wzajemnego istnieje, jeśli w danym momencie każdy zasób udostępniony jest przypisany do dokładnie jednego procesu lub jest dostępny. Zestaw procesów jest zakleszczony, jeśli każdy proces w zestawie oczekuje na zdarzenie, które może spowodować tylko inny proces w zestawie.

Say, semafory binarne są używane, zapewniając, że tylko jeden z nich może wprowadzić swój obszar krytyczny w tym samym czasie. Ponieważ każdy proces obniża się tuż przed wejściem do krytycznego regionu, a zaraz po opuszczeniu go, gwarantuje się wzajemne wykluczenie.

Rozumiem, istnieją cztery warunki, które muszą wszyscy trzymają za nastąpić zakleszczenie, z których jeden jest warunek wzajemnego wykluczania (nie dwa procesy mogą być jednocześnie w swoich sekcjach krytycznych).

Ponieważ gwarantuje wzajemne wykluczenie, to program, w tym przypadku zakleszczenia wolna?

Pozdrawiam.

Answer 1

Niekoniecznie. Wyobraź sobie te dwa wątki:

Thread 1   Thread 2 
============  ============= 
Acquire A   Acquire B 
Acquire B   Acquire A 
Release B   Release A 
Release A   Release B 

Tu, wzajemne wykluczanie jest rzeczywiście zagwarantowane - w każdej chwili, semafory A i B są albo własnością jednego z wątków lub dostępny systemowy - ale impas jest nadal możliwe, jeśli wątek 1 i 2 każdy nabywa swoją pierwszą blokadę (A dla wątku 1, B dla wątku 2), ale wtedy będzie się martwić, czekając na zasób, który trzyma drugi.

Mam nadzieję, że to pomoże!