Zakleszczenia są bardzo trudnym tematem, ale w następnych wpisach, postaram się podać kilka najczęściej stosowanych technik unikania ich. Tematyka została na tyle przebadana, że istnieją pewne uniwersalne sposoby, które można wykorzystać we własnych algorytmach współbieżnych.

Zacznijmy od zdefiniowania sytuacji, które konieczne są aby zaistniał deadlock:

1. Wzajemnie wykluczanie – oczywiście, aby była mowa o deadlock, musimy mieć jakieś blokady czy inny sposób definiowania sekcji krytycznej.
2. Synchronizacja powinna odbywać się na zasadzie czekania. Mechanizmy takie jak lock, czekają aż zasób zostanie zwolniony i w tym czasie blokują one dany wątek.
3. Brak wywłaszczania – jeśli, którykolwiek wątek mógłby wywłaszczyć inny wątek, wtedy zakleszczenie również byłoby niemożliwe.
4. Cykliczne wywołania – to jest bardzo ważna obserwacja. Zakleszczenie występuje tylko wtedy, gdy wątek A chce uzyskać dostęp do L1 i L2 a wątek B do L2, L1 (Circular wait).

Powyższe warunki nazywa się warunkami Coffman’a. Zrozumienie tego jest kluczowe, jeśli chcemy pisać algorytmy wolne od zakleszczeń. Dzisiaj skupimy się na ostatnim warunku. Wyjaśnimy to na przykładzie problemu\algorytmu bankiera. W skrócie mamy funkcję, która transferuje pieniądze z konta A do B. Funkcja oczywiście może być wywoływana w sposób  współbieżny. Sygnatura wygląda następująco:

void Transfer(Account accountA,Account account B, double amount);

Pobierając pieniądze z danego konta, musimy zablokować do niego dostęp, aby ktoś inny nie modyfikował w tym samym czasie ilości środków pieniężnych na tym koncie. Zakładamy ponadto, że nie możemy wykonywać operacji osobno tj. najpierw na koncie A a potem na koncie B – obie operacje muszą zostać wykonane w tej samej sesji. Pierwsza implementacja mogłaby wyglądać następująco:

private void Transfer(Account accountA, Account accountB, double amount)
{
  lock (accountA)
  {
      lock (accountB)
      {
          if (accountA.Balance < amount)
              throw new Exception("Insufficient funds.");

          accountA.Balance -= amount;
          accountB.Balance += amount;
      }
  }
}

Powyższy kod jest klasycznym przykładem deadlock’a – jeśli wątek T1 przelewa pieniądze z A do B, a wątek T2 z B do A to duże prawdopodobieństwo, że skończy to się zakleszczeniem.

Na podstawie warunku nr 4 wiemy, że zakleszczenie istnieje wyłącznie wtedy, gdy mamy cykl. Musimy zatem uzyskać dostęp jednocześnie do dwóch zasobów naraz. Niestety poniższa konstrukcja nie jest wspierana przez C#:

lock (accountA,accountB)
{
     if (accountA.Balance < amount)
         throw new Exception("Insufficient funds.");

     accountA.Balance -= amount;
     accountB.Balance += amount;
}

Możemy to zaimplementować samemu, ale jest z tym trochę roboty i nie zawsze warto. Lepiej zaobserwować inną, pochodną zależność – blokując zasoby ZAWSZE w tej samej kolejności, pozbędziemy się cykli!

Załóżmy, że GetHashCode() zwraca jakieś ID w postaci klucza:

private void Transfer(Account accountA, Account accountB, double amount)
{
  if (accountA.GetHashCode() > accountB.GetHashCode())
  {
      lock (accountA)
      {
          lock (accountB)
          {
              // logika
          }
      }
  }
  else
  {
      lock (accountB)
      {
          lock (accountA)
          {
              // logika
          }
      }
  }
}

Powyższy kod to oczywiście wyłącznie ilustracja. Proszę jednak zauważyć, jak łatwo czasami można pozbyć się zakleszczenia przez prostą obserwację – wystarczy blokować zasoby zawsze w tym samym porządku.

Rozwiązanie można nawet wykorzystać na więcej niż dwa locki – wystarczy przekazać tablicę obiektów i ją posortować, a następnie w pętli blokować po kolei dostęp do przekazanych zasobów.