Pr-1st-1.1-m05-Slajd11

Zakleszczenie w podstawowym modelu k spośród r

W podstawowym modelu k spośród r, z pasywnym procesem $P_i$ skojarzony jest zbiór warunkujący ${{𝒟}}_i$, liczba naturalna $k_i$, $1\le k_i\le |{{𝒟}}_i|$, oraz liczba naturalna $r_i=|{{𝒟}}_i|$. W modelu tym proces $P_i$ staje się aktywny wówczas, gdy uzyska wiadomości od co najmniej $k_i$ różnych procesów ze zbioru warunkującego ${{𝒟}}_i$.

$deadlock({ℬ})\equiv$

$({ℬ}\subseteq {𝒫})\wedge ({ℬ}\ne \mathrm{\varnothing })\wedge$

$\mathrm{\forall }{P}_i::P_i\in {ℬ}(passiv{e}_i\wedge$

$(\mathrm{\exists }{{ℬ}}_i::{{ℬ}}_i\subseteq {{𝒟}}_i\cap {ℬ}::$

$(|{{𝒟}}_i\setminus {{ℬ}}_i|<k_i\wedge$

$(\mathrm{\forall }{P}_j::P_j\in {{ℬ}}_i::(\mathrm{\neg }in\text{-}transi{t}_i[j]\wedge \mathrm{\neg }availabl{e}_i[j]))))$

Definicja powyższa oznacza, że dla każdego procesu $P_i$ można znaleźć zbiór procesów ${{ℬ}}_i$, od których nie jest możliwe otrzymanie wiadomości ${{ℬ}}_i\subseteq {ℬ}$ i jednocześnie $(\mathrm{\forall }{P}_j::P_j\in {{ℬ}}_i::(\mathrm{\neg }in\text{-}transi{t}_i[j]\wedge \mathrm{\neg }availabl{e}_i[j]))$ Tak więc, $P_i$ potencjalnie otrzyma co najwyżej $|{{𝒟}}_i\setminus {{ℬ}}_i|$ wiadomości, co jednak nie wystarcza do uaktywnienia, gdyż $|{{𝒟}}_i\setminus {{ℬ}}_i|<k_i$.

<< Poprzedni slajd | Spis treści | Następny slajd >>