Detekcja zakleszczeń: algorytm wait-for graph

W ostatnich dwóch wpisach przyjrzeliśmy się bliżej przyczynom powstawania zakleszczeń. Powinno być jasne już, że zakleszczenie to nie jest problem pojawiający się nagle, w nieoczekiwany sposób. Całkiem łatwo można wykryć to, już na etapie pisania kodu – bardzo często wystarczy statyczna analiza kodu. Dzisiaj kolejna technika, która mam nadzieję, pomoże jeszcze bardziej zrozumieć podstawy powstania deadlock’ow.

Zajmiemy się grafem, umożliwiającym znalezienie blokad, powodujących zakleszczenie systemu. Bazy danych mają takie algorytmy zaimplementowane aby zakończyć automatycznie transakcje powodujące problem. Ktoś może zapytać się, po co taka wiedza programiście piszącemu aplikacje biznesowe a nie narzędzia programistyczne?

Bardzo często, nawet w aplikacjach biznesowych, pisze się platformy wykonujące jakąś logikę – np. systemy finansowe gdzie różne algorytmy odgrywają rolę “robotów”. W innych dziedzinach również zdarza się, że dana platforma musi wykonywać jakiś kod użytkownika.

Myślę jednak, że większość programistów nie spotkała się mimo wszystko z takimi scenariuszami. Główną przyczyną, dlaczego warto zrozumieć ten algorytm to po prostu uświadomienie sobie, że za pomocą zrzutu pamięci, sami możemy wyznaczyć czy deadlock wystąpił w systemie. Wystarczy kartka papieru i z łatwością możemy sobie wszystko rozpisać. Polecam tym wszystkim taki trening, którzy wciąż nie są pewni, czy deadlock jest możliwy w ich systemie.

Na Wikipedii można znaleźć matematyczny opis algorytmu. Dowiemy się, że wspomniany graf wygląda następująco:

Wait-for graph example.png

Oznacza to, że wątek Pi nie może założyć blokady, ponieważ czeka na Pj. Innymi słowy, Pj trzyma aktualnie blokadę, którą chce uzyskać Pi. Jeśli rozrysujemy sobie graf i okaże się, że ma on cykl, wtedy mamy do czynienia z zakleszczeniem. Jeśli nie ma żadnego cyklu, to nie ma konfliktu i po jakimś czasie wszystkie wątki otrzymają żądane blokady.

Załóżmy, że mamy klasyczny przypadek zakleszczenia – dwa konta bankowe, jeden wątek próbuje przetransferować dane z konta A do konta B, a drugi z kolei z B do A. Na dodatek nakładamy dwie osobne blokady,  LA dla konta A, a dla konta B, LB. Kod:

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;
          accountA.Balance += amount;
      }
  }
}

Jeśli T1 założy blokadę LA, a T2 blokadę LB, to otrzymamy następujący graf:

image

Jak widać, graf zawiera cykle i w taki sposób, matematycznie można stwierdzić, że algorytm powoduje zakleszczenie.

Spróbujmy zaimplementować uproszczoną wersję algorytmu. Załóżmy, że przed założeniem blokady, chcemy sprawdzić czy nie spowoduje ona zakleszczenia. Wiąże się to z koniecznością śledzenia pewnych informacji, a mianowicie będziemy mieli kolekcje przechowujące właścicieli blokad oraz wątki czekające na dane blokady:

private static readonly Dictionary<object, Thread> LocksTaken = new Dictionary<object, Thread>();

private static readonly Dictionary<Thread, object> WaitingFor=new Dictionary<Thread, object>();

Obie kolekcje to słowniki. Pierwszy zawiera informacje o tym, jaki wątek trzyma daną blokadę. Kluczem jest blokada, a wartością właściciel (czyli wątek).

Z drugiego słownika dowiemy się, jakie wątki czekają na daną blokadę. Czyli jeśli wątek T1 czeka na blokadę L1 to wtedy będziemy mieli w kolekcji parę <T1,L1>.  Powyższe kolekcje sami musimy wypełniać danym i dlatego należy rozszerzyć klasę Monitor – ale to nie w tym poście.

Mając kolekcję, możemy zacząć pisać naszą metodę:

internal class Program
{
   private static readonly Dictionary<object, Thread> LocksTaken = new Dictionary<object, Thread>();
   private static readonly Dictionary<Thread, object> WaitingFor = new Dictionary<Thread, object>();

   private static void TryToEnter(object target)
   {
      Thread owner;
      if (!LocksTaken.TryGetValue(visitedNodes.Last.Value.Item2, out owner))
          return; // na pewno nie spowoduje zakleszczenia

        // dlasza czesc logiki
   }
}

Powyższy kod to najłatwiejszy scenariusz. Sprawdzamy, czy blokada jest trzymana przez jakiś wątek. Jeśli nie, to oczywiście możemy uzyskać do niej dostęp i nie spowoduje to zakleszczenia. Załóżmy jednak, że taka blokada jest już trzymana przez inny wątek. W takiej sytuacji musimy rozwijać dalej graf:

private static void TryToEnter(object target)
{
  var visitedNodes = new LinkedList<Tuple<Thread, object>>();

  visitedNodes.AddLast(new Tuple<Thread, object>(Thread.CurrentThread, target));

  while (true)
  {
      Thread owner;
      if (!LocksTaken.TryGetValue(visitedNodes.Last.Value.Item2, out owner))
          break;

      if (visitedNodes.Any(node => node.Item1 == owner))
          throw new DeadlockException();

      object waitingForLock;
      if (!WaitingFor.TryGetValue(owner, out waitingForLock))
          break;

      visitedNodes.AddLast(new Tuple<Thread, object>(owner, waitingForLock));

  }
}

Po kolei… VisitedNodes to lista zawierająca już odwiedzone węzły wait-for-graph. To dzięki niej, zorientujemy się, że mamy cykl i dalsze przeszukiwanie grafu nie ma sensu ponieważ nigdy nie zakończy się (deadlock).

Dalej mamy pętle, w której przechodzimy przez graf. Kolejna linia (znana z poprzedniego kodu), sprawdza czy dana blokada jest przez kogoś wzięta. Jeśli nie, to nie ma na pewno deadlock’a. W przeciwnym wypadku bierzemy wątek, który trzyma daną blokadę. Po tym będziemy wiedzieli, że wątek T1 chce uzyskać dostęp do L1, który jest trzymany przez T2.

W kolejnej linii sprawdzamy, na jakie blokady T2 czeka. Jeśli na żadne to kwestia czasu i wszystkie blokady zostaną nadane. W przeciwnym wypadku, będziemy wiedzieć, że: T1 chce uzyskać dostęp do blokady L1, która jest trzymana przez T2, który z kolei czeka blokadę L2. W formie grafu będzie to wyglądać następująco:

image

 

Następnie dodajemy do visitedNodes węzeł w formie T2,L2.

Rozpoczynamy iterację numer 2. Jeśli L2 nie jest trzymamy przez żaden wątek, to nie mamy cyklu i możemy przerwać dalsze poszukiwania. W przeciwnym wypadku, wykonujemy analogiczne kroki. Za pomocą słownika dowiadujemy się, kto trzyma L2:

image

A następnie na jaką blokadę czeka T3. Wyobraźmy sobie, że T3 czeka na L1, wtedy otrzymamy cykl i co za tym idzie – zakleszczenie:

image

Łatwo zauważyć, że nie ma wyjścia z takiego grafu. Mamy zapętlenie i nie ma szans, że taki algorytm zakończy się.

Proszę zauważyć, że powyższa implementacja nie generuje całego grafu a jedynie potrzebny podgraf – dlatego nazwałem to uproszczeniem pełnego algorytmu.

Leave a Reply

Your email address will not be published.