Kilka ciekawostek z przeładowywania metod, część I

Przeładowania metod to podstawy języka. Niestety, nieumiejętnie stosowane, mogą przystworzyć problemów nawet zaawansowanym programistom. Z tego względu, uważam, że należy po prostu unikać tych przeładować, które są zbyt trudne w zrozumieniu – powodują niepotrzebne zamieszanie.

Zacznijmy od klasycznego przykładu, który jest zrozumiały dla każdego:

private static void Main(string[] args)
{
      Display("Hello World");
      Display(5);
}

private static void Display(string text)
{
  Console.WriteLine("string");
}

private static void Display(int number)
{
  Console.WriteLine("int");
}

Nie ma tutaj żadnej zagadki – pierwsze wywołanie wykona funkcje z parametrem string a drugie z int. Nieco mniej zrozumiałą konstrukcją może być:

private static void Main(string[] args)
{
      Display(5);
}
private static void Display(double arg)
{
  Console.WriteLine("double");
}
private static void Display(Int16 arg)
{
  Console.WriteLine("int16");
}
private static void Display(int arg)
{
  Console.WriteLine("int");
}
private static void Display(float arg)
{
  Console.WriteLine("float");
}

Która funkcja zostanie wywołana? Teoretycznie każda z nich spełnia wymagania ponieważ 5 może być skonwertowane zarówno do int16 jak i int, float, double czy long. C# zawsze będzie starał się dobrać najlepsze dopasowanie. Mamy tutaj do czynienia z całkowitą liczbą, stąd int16,int,long są lepszymi kandydatami niż zmiennoprzecinkowe (skomplikowane) zmienne typu double czy float.

I tutaj mała pułapka… Może wydawać się, że int16 jest lepszy niż int ponieważ zajmuje mniej pamięci, a żeby pomieścić cyfrę 5, 16 bitów w zupełności wystarcza. Deklarując jednak każdą zmienne, możemy określić jej typ za pomocą specyfikatorów, a mianowicie (źródło, stackoverflow):

var d = 1.0d; // double
var f = 1.0f; // float
var m = 1.0m; // decimal
var i = 1; // int
var ui = 1U; // uint
var ul = 1UL; // ulong
var l = 1L; // long

Stąd wynika, że jak przekażemy liczbę całkowitą, bez specyfikatora, zostanie użyty typ Int32. Powinno być już jasne, która metoda zostanie wykonana, gdy wywołamy:

Display(5.00);

Będzie to oczywiście wersja z Double – aby wywołać float musielibyśmy napisać 5.00f.

A co jeśli mamy następujący kod?

internal class Program
{
   private static void Main(string[] args)
   {
           Display(5.00);
   }

   private static void Display(float arg)
   {
       Console.WriteLine("float");
   }
}

Wywoła to błąd kompilacji – 5.00 to double a nie float – nie ma tutaj niejawnej konwersji. Natomiast, niejawna konwersja ma miejsce z typu mniej dokładnego do bardziej, tzn.:

internal class Program
{
   private static void Main(string[] args)
   {
           Display(5.00f);
   }

   private static void Display(double arg)
   {
       Console.WriteLine("double");
   }
}

Widać, że jest trochę tutaj niespodzianek. To jednak dopiero początek. C# naprawdę potrafi zaskoczyć,  jeśli chodzi o wywoływanie metod. Powyższe pułapki są mimo wszystko logiczne i wiadomo, czego można spodziewać się.

Rozważmy następujący przykład:

internal class Program
{
   private static void Main(string[] args)
   {
       Child child = new Child();
       child.Display((int) 5);
   }
}

internal class Parent
{
   public void Display(int arg)
   {
       Console.WriteLine("int");
   }

}

internal class Child : Parent
{
   public void Display(double arg)
   {
       Console.WriteLine("double");
   }
}

Child dziedziczy po Parent. Nie mamy tutaj do czynienia z method hiding, ponieważ sygnatury metod są różne od siebie. Jest to wciąż klasyczny przykład przeładowywania metod. Normalnie, Display z Integer zostałby wywołany, ponieważ jest to lepsze dopasowanie. C# jednak w przypadku dziedziczenia, zawsze weźmie najpierw pod uwagę metodę znajdującą się bliżej w hierarchii klas. Operujemy na Child, dlatego najpierw będzie C# próbował znaleźć dopasowanie w Child, a dopiero potem w Parent. Z tego względu Display(double) wygrywa i zostanie wykona.

Jest to poważna pułapka i osobiście unikam takiego kodu. Wystarczy, że zmienimy wskaźniki na:


private static void Main(string[] args)
{
  Parent child = new Child();
  child.Display((int) 5);
}

I w takim przypadku, wersja z Int zostanie wywołania a nie z double, jak powyżej.

Kolejną pułapką są wirtualne metody i ich przeciążenia:

internal class Program
{
   private static void Main(string[] args)
   {
       Child child = new Child();
       child.Display((int) 5);
   }
}

internal class Parent
{
   public virtual void Display(int arg)
   {
       Console.WriteLine("int");
   }
}

internal class Child : Parent
{
   public override void Display(int arg)
   {
       Console.WriteLine("override int");
   }
   
   public void Display(double arg)
   {
       Console.WriteLine("double");
   }
}

Korzystamy ze wskaźnika Child, zatem najpierw próbujemy znaleźć dopasowanie w Child. Mamy przeciążoną metodę Display(int) i logiczna odpowiedź brzmiałaby, że “override int” zostanie wywołany. Twórcy C# jednak, zdecydowali się ignorować przeciążenia i w pierwszej kolejności zostaną rozpatrzone wszystkie inne metody w Child – w tym przypadku będzie to Display(double)!

W przyszłym poście, kolejne dziwne przeładowania wykorzystujące dziedziczenie – to właśnie one powodują największe problemy i powinny być unikane.

decimal vs double, część II (wydajność)

W poprzednim w poście, przedstawiłem różnice między decimal a double. Powinno być już jasne, kiedy jaki typ stosować. Jeszcze raz chcę tylko podkreślić, że wybór między decimal a double to coś więcej niż między int16 a int32. Wybranie double w nieprawidłowych scenariuszach może przynieść bardzo trudne w znalezieniu błędy. Wybranie z kolei Int32 zamiast Int16 raczej nie przyniesie ubocznych efektów.

Dziś z kolei o wydajności… Typ double jest szeroko znany i z tego względu wspierany przez hardware. Operacje na nim są DUŻO szybsze niż na decimal. Zobaczmy następujący przykład:

internal class Program
{
   private static void Main(string[] args)
   {
       const int n = int.MaxValue;

       Stopwatch stopwatch = Stopwatch.StartNew();

       double doubleType = 0;
       for (int i = 0; i < n; i++)
       {
           doubleType ++;
       }

       Console.WriteLine(stopwatch.ElapsedMilliseconds);

       stopwatch = Stopwatch.StartNew();

       float floatType = 0;
       for (int i = 0; i < n; i++)
       {
           floatType ++;
       }

       Console.WriteLine(stopwatch.ElapsedMilliseconds);

       stopwatch = Stopwatch.StartNew();

       decimal decimalType = 0;
       for (int i = 0; i < n; i++)
       {
           decimalType ++;
       }

       Console.WriteLine(stopwatch.ElapsedMilliseconds);
   }
}

Wynik:

image

Jak widać, różnica jest ogromna, mająca realny wpływ na aplikacje – oczywiście zależy to od typu oprogramowania. Mowa o systemach, które wykonują różne obliczenia 24h na dobę.

Double i Float z kolei mają taką samą wydajność. Dla procesorów 64 bitowych nie ma bowiem to znaczenia – dla starej architektury, float jest szybszy niż double. Jeśli piszemy aplikację na PC, wtedy polecam korzystać zawsze z double – nie ma sensu używać float, który ma taką samą wydajność a dużo mniejszą precyzję.

decimal vs double, część I

W kilku wpisach chciałbym przedstawić różnicę między tymi dwoma typami. Osoby piszące aplikacje finansowe z pewnością znają te różnice bo to właśnie w tych typach aplikacji, double powodował bardzo poważne błędy.

Przed przeczytaniem wpisu, niezbędne będzie przypomnienie sobie następujących informacji:

1. Przeliczanie systemu binarnego, szczególnie części dziesiętnej.
2. Liczby zmiennoprzecinkowe.

Nie będę tego opisywał na blogu, ponieważ są to zagadnienia wyjaśniane już wiele razy – ale pisząc aplikacje wysokopoziomowe niestety łatwo zapomnieć o podstawach informatyki.

Typ double jest najpopularniejszy wśród programistów, ale bardzo często nie ma to uzasadnienia. Zacznijmy od napisania takiego programu:

float a = 0.1f;
double b = a;

Console.WriteLine(a);
Console.WriteLine(b);

Na ekranie zobaczymy:

image

Dlaczego? W końcu mamy taką samą liczbę i double ma większą dokładność niż float, stąd może wydawać się dziwne, że druga linia nie reprezentuje dokładnie liczby 0.1.

Inna sprawa, to przecież próbujemy wyświetlić prostą liczbę 0.1, 1/10. Niestety w rzeczywistości 0.1 nie ma dokładnej reprezentacji binarnej.

Zróbmy podobny eksperyment ale z 0.5 Na ekranie wyświetli się:

image

Jak widać, z 0.5 nie ma takiego już problemu. Spróbujmy zamienić 0.5 ma system binarny:

0.5 * 2 = 1 stąd w systemie binarnym 0.5 to po prostu 0.1. Nie ma żadnego problemu, aby przechować taką wartość w formie mantysy i wykładnika.

A co w przypadku 0.1?

0.1 * 2 = 0.2,  0.0

0.2 * 2 = 0.4,  0.00

0.4 * 2 = 0.8, 0.000

0.8 * 2 = 1.6, 0.0001

0.6 * 2 = 1.2, 0.00011

0.2 * 2 = 0.4, 0.000110 // i zaczynamy od nowa…

Problem w tym, że dziesiętnej liczby 0.1(1/10), nie da zamienić się na dokładną binarną reprezentację – powyższy przykład pokazuje, że liczba ma nieskończoną reprezentacje tak jak w systemie dziesiętnym ma 1/3 (0.333333…).

Przechowując 0.1 w double albo float, tak naprawdę nie przechowujemy dokładnej wartości, a wartość którą udało przechować się w pamięci.

Dlaczego zatem double wygląda mniej dokładniej niż float? Tak naprawdę, obie liczby zawierają dokładnie tą samą wartość a wszystko jest związane ze sposobem formatowania i wyświetlania na ekranie. Możemy użyć modyfikatora G7, aby wyświetlić liczby z tą samą precyzją. Innymi słowy, 0.1 w float będzie miał reprezentację typu 0.00011000011 a po konwersji do double, część mantysy będzie wyzerowana (to już zależy od kompilatora). Nie wiadomo tak naprawdę co z pozostałymi bitami stanie się, dlatego należy unikać mieszania float z double.

Na ekranie widzimy inne wyniki, ponieważ metoda ToString zdaje sobie sprawę, że float ma dokładność do 7 cyfr, a double do 16 – stąd wie, jak zaokrąglić liczbę. Normalnie, gdybyśmy użyli double b = 0.1, liczba 0.1 inaczej byłaby przechowania niż po rzutowaniu z float – więcej miejsc po przecinku moglibyśmy przechować w pamięci.

Wniosek z powyższych rozważań jest następujący – jeśli chcesz przechowywać wartości, które występują w systemie dziesiętnym, nie używaj double. Double zawsze używa reprezentacji binarnej o podstawie 2:  mantysa * 2^wykładnik.

Decimal jest również liczbą zmiennoprzecinkową. Tak samo jak float czy double, przechowuje w pamięci mantysę i wykładnik. Podstawa jest jednak zawsze równa 10 – stąd można dokładnie przechować 0.1 w pamięci.

Ma to olbrzymie znaczenie dla aplikacji finansowych, gdzie operuje się na wartościach dziesiętnych – pieniądzach. Wyobraźmy sobie następujący kod:

static void Main(string[] args)
{
  double doubleResult = 0;
  decimal decimalResult = 0;
  const int n = 100000*10000;

  for (int i = 0; i < n; i++)
  {
      doubleResult += 0.1;
      decimalResult += 0.1m;
  }

  Console.WriteLine(doubleResult);
  Console.WriteLine(decimalResult);
}

image

Jak widać, ze względu na fakt, że double nie przechowuje dokładnie 0.1 a jedynie wartość przybliżoną, błędy narastają, powodując na końcu poważną różnice. W aplikacjach, gdzie wykonujemy wiele obliczeń (np. konta bankowe itp.) jest to nieakceptowalne.

Zmienne double\float mają jednak pewne zalety. Przede wszystkim są dużo szybsze (ale o tym w przyszłym poście), ponieważ wspierane są przez sprzęt (CPU).

Double\float przechowują DUŻO większe liczby:

Console.WriteLine(float.MaxValue);
Console.WriteLine(double.MaxValue);
Console.WriteLine(decimal.MaxValue);

image

Zaglądając do MSDN dowiemy się również o następujących technicznych parametrach powyższych typów:

Typ Zasięg Precyzja Wielkość
float

-3.4 × 10^38 to +3.4 × 10^38

7 cyfr 32 bity
double ±5.0 × 10^324 to ±1.7 × 10^308 15-16 64
decimal (-7.9 x 10^28 to 7.9 x 10^28) / (10^(0 to 28)) 28-29 128

Decimal ma dużo mniejszy zasięg ale za to potrafi przechować liczby z wyższą dokładnością. Wyjątkiem są jednak bardzo małe liczby:

double a =  0.000000000000000000000000000001;
decimal b = 0.000000000000000000000000000001m;
Console.WriteLine(a);
Console.WriteLine(b);

image

Innymi słowy, float\double należy używać dla bardzo dużych albo bardzo małych liczb.

Proszę zauważyć, że w większości przypadków nie potrzebujemy tak wysokiej dokładności jaką daje nam decimal. W przypadku aplikacji przemysłowych, wszelkie sensory już dostarczają tak wysoką niedokładność, że nie ma to znaczenia. Ponadto, one w końcu operują na wartościach binarnych. Decimal warto używać, gdy liczby pochodzą od człowieka (który operuje systemem dziesiętnym) oraz gdy wykonujemy na nich operacje matematyczne. W przyszłym wpisie pokażę, różnicę w wydajności ponieważ jest ona znacząca.

Istnieje jeszcze jedna drobna różnica. float\double mają pojęcia takie jak NaN, PositiveInfinity oraz NegativeInfinity. Natomiast w przypadku decimal, wyrzucany jest wyjątek, gdy będziemy próbować dzielić przez zero.

Code Review: Tworzenie wątków za pomocą Task.Factory.StartNew i ContinueWith

Załóżmy, że nie możemy korzystać z await\async i gdzieś w kodzie mamy następujące wywołania:

public MainWindow()
{
  InitializeComponent();
  Task.Factory.StartNew(LoadData).ContinueWith(UpdateUserInterface, TaskScheduler.FromCurrentSynchronizationContext());
}
private static void UpdateUserInterface(Task obj)
{
  Console.WriteLine("Interfejs zaktualizowany.");
  Task task = Task.Factory.StartNew(AnotherTimeConsumingOperation);
}

private static void AnotherTimeConsumingOperation()
{
  // ???
}

private static void LoadData()
{
  Thread.Sleep(5000);
}

Chcemy wykonać operacje za pomocą Task’ow. LoadData to operacja czasochłonna i wykonujemy ją w wątku z puli. Następnie chcemy zaktualizować interfejs użytkownika więc wywołujemy UpdateUserInterface na wątku głównym UI. Na końcu chcemy wykonać kolejną operację więc standardowo wywołujemy StartNew:

Task.Factory.StartNew(AnotherTimeConsumingOperation);

Niestety, jeśli zajrzyjmy do debuggera, okaże się, że ta metoda jest wykonywana na wątku UI!

image

Dlaczego? W końcu spodziewalibyśmy się, że zostanie ściągnięty wątek z puli, ponieważ nie użyliśmy żadnej flagi mówiącej o synchronizacji (tak jak w poprzednim przykładzie).

Zajrzyjmy do Reflector’a:

[MethodImpl(MethodImplOptions.NoInlining), __DynamicallyInvokable]
public unsafe Task StartNew(Action action)
{
    StackCrawlMark mark;
    Task task;
    mark = 1;
    task = Task.InternalCurrent;
    return Task.InternalStartNew(task, action, null, this.m_defaultCancellationToken, this.GetDefaultScheduler(task), this.m_defaultCreationOptions, 0, &mark);
}

 

Widać, że jest używana metoda GetDefaultScheduler do uzyskania scheduler’a:

private TaskScheduler GetDefaultScheduler(Task currTask)
{
    if (this.m_defaultScheduler == null)
    {
        goto Label_000F;
    }
    return this.m_defaultScheduler;
Label_000F:
    if (currTask == null)
    {
        goto Label_0024;
    }
    if ((currTask.CreationOptions & 0x10) != null)
    {
        goto Label_0024;
    }
    return currTask.ExecutingTaskScheduler;
Label_0024:
    return TaskScheduler.Default;
}
  private TaskScheduler GetDefaultScheduler(Task currTask)
{
    if (this.m_defaultScheduler == null)
    {
        goto Label_000F;
    }
    return this.m_defaultScheduler;
Label_000F:
    if (currTask == null)
    {
        goto Label_0024;
    }
    if ((currTask.CreationOptions & 0x10) != null)
    {
        goto Label_0024;
    }
    return currTask.ExecutingTaskScheduler;
Label_0024:
    return TaskScheduler.Default;
}

 

Łatwo sprawdzić, że defaultscheduler będzie NULL więc pierwszy IF nie zostanie wykonany.

Okazuje się, że w naszym przypadku zostanie użyty aktualny scheduler, którym po wywołaniu UpdateUserInterface będzie SynchronizationContextScheduler. Zatem wszystkie wątki od czasu gdzie przekazaliśmy jako scheduler TaskScheduler.FromCurrentSynchronizationContext() będą wykonywane domyślnie na wątku UI.

Rozwiązanie to oczywiście przekazywanie zawsze schedulera jawnie:

Task.Factory.StartNew(AnotherTimeConsumingOperation,new CancellationToken(),TaskCreationOptions.None,TaskScheduler.Default)

Innymi słowy, jeśli nie przekażemy schedulera jawnie to jest używany TaskScheduler.Current a nie TaskScheduler.Default. Z tego względu, zawsze należy jawnie przekazywać taki parametr ponieważ łatwo popełnić błąd. Myślę, że nie jest to dla większości programistów zbyt intuicyjne. Szczególnie, gdy nie mamy jednego łańcucha wywołań a tworzymy wątki w różnym miejscach.

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.

Unikanie zakleszczeń, część II

W poprzednim poście pokazałem, jak w łatwy sposób można uniknąć deadlock’ów, zauważając jedną, prostą zależność. W drugiej i trzeciej części przyjrzyjmy się temu dokładniej i w sposób  bardziej formalny.

Uściślając technikę z poprzedniego postu, uzyskamy tzw. lock leveling.

Zasada jest dosyć prosta – każdemu obiektowi w systemie nadajemy pewną liczbę, poziom. Następnie wątek może blokować wyłącznie obiekty o niższym poziomie. W ten sposób unikniemy cykli a co za tym idzie, zakleszczeń. Poziomy bowiem wyznaczają z góry określoną kolejność z jaką można posługiwać się podczas synchronizacji.

Brzmi prosto, ale w praktyce jest to bardzo trudne. Szczególnie gdy nie chcemy mieć dwóch obiektów o tym samym poziomie. Jeśli pozwolilibyśmy na dostęp do obiektów o tym samym poziomie, bardzo łatwo mogłoby to się skończyć zakleszczeniem. Załóżmy, że wątek T1 chce zablokować obiekty A i B, które mają ten sam poziom. Mógłby zatem najpierw zablokować A potem B. W tym samym czasie, wątek T2 mógłby zablokować najpierw B a potem próbować uzyskać dostęp do A – klasyczne zakleszczenie.

Nadając blokadom poziomy, warto pomyśleć o architekturze. Naturalne jest, że warstwa biznesowa będzie miała obiekty synchronizujące o wyższym poziomie niż warstwa dostępu do danych, ponieważ nigdy DAL nie będzie wywoływał logiki biznesowej. Jeśli DAL miałby wyższy poziom niż BL, wtedy warstwa biznesowa, nie mogłaby założyć  blokad na dwóch warstwach.

Dobrą wiadomością z kolei jest fakt, że korzystając z powyższej techniki, można deadlock’i wykrywać już na etapie kompilacji! W końcu załóżmy, że C# wspierałby tą technikę, wtedy moglibyśmy napisać:

lock(_Sync1,level:10)
{
   ...
   lock(_Sync2,level:20) // konstrukcja nielegalna!
   {
   
   }

}

Powyższy kod jest nielegalny – próbujemy uzyskać dostęp do obiektu o wyższym poziomie. Możliwe jest to do wykrycia na poziomie kompilacji\analizy kodu.

Spróbujmy teraz napisać klasę, która będzie wykonywać powyższe zadania. Oczywiście nie będzie to kod produkcyjny ale jedynie zarys jak to powinno działać.

Najbardziej prymitywna wersja mogłaby wyglądać następująco:

internal sealed class LevelLock
{
   private readonly int _level;
   private readonly object _sync = new object();
   [ThreadStatic] private static LinkedList<LevelLock> _locks;

   public LevelLock(int level)
   {
       _level = level;
   }

   public int Level
   {
       get { return _level; }
   }

   public void Enter()
   {
       DetectDeadlock();
       Monitor.Enter(_sync);
   }

   public void Exit()
   {
       _locks.Remove(this);
       Monitor.Exit(_sync);
   }

   private void DetectDeadlock()
   {
       if (_locks == null)
           _locks = new LinkedList<LevelLock>();
       else if(_locks.Count>0)
       {
           LevelLock lastLock = _locks.Last.Value;
           if (_level >= lastLock.Level)
               throw new DeadlockException();
       }
       _locks.AddLast(this);
   }
}

Warto zwrócić uwagę na atrybut ThreadStatic o którym pisałem tutaj. Chcemy sprawdzać poziomy wyłącznie odbywające się w tym samym wątku. Jeśli wątek T1 tworzy locki o poziomach 10,5 to nie stoi nic na przeszkodzie, że T2 stworzy sobie 12,6,3. Chcemy tylko zagwarantować, że każdy z wątków tworzy wątki w jednakowej kolejności (w sposób malejący).

Poniższy kod wyrzuci wyjątek (deadlock):

var lock1 = new LevelLock(10);
var lock2 = new LevelLock(20);

lock1.Enter();
lock2.Enter();

Następujące konstrukcje są z kolei dozwolone:

var lock1 = new LevelLock(10);
var lock2 = new LevelLock(20);

lock2.Enter();
lock1.Enter();

var lock1 = new LevelLock(10);
var lock2 = new LevelLock(20);

lock1.Enter();
lock1.Exit();
lock2.Enter();
lock2.Exit();

Jak wspomniałem, lock leveling można wykonać na etapie kompilacji, poprzez analizę kodu. Z tego względu, bardzo często pomija się to w wersji release, aby nie obciążać niepotrzebnie aplikacji:

[Conditional("DEBUG")]
private void DetectDeadlock()
{
  if (_locks == null)
      _locks = new LinkedList<LevelLock>();
  else if(_locks.Count>0)
  {
      LevelLock lastLock = _locks.Last.Value;
      if (_level >= lastLock.Level)
          throw new DeadlockException();
  }
  _locks.AddLast(this);
}

Kod  oczywiście pozostawia wiele do życzenia. Warto rozważyć, czy należy sprawdzać poziomy między różnymi bibliotekami. Rzadko ma miejsce deadlock z wykorzystaniem kompletnie różnych bibliotek (np. System.Drawing z naszym DLL). Znacząco ułatwiłoby to nadawanie poziomów. Inna wada to fakt, że powyższy kod nie wspiera blokad rekursyjnych tzn. gdy ten sam wątek wywołuje Enter dwa razy to za drugim razem wykonanie powinno zostać po prostu zignorowane. Lock tak się właśnie zachowuje i dlatego poniższy kod nie powoduje zakleszczenia:

object sync=new object();
lock (sync)
{
    lock (sync)
    {
        
    }
}

Ponadto, nie mamy tutaj obsługi błędów czy timeout’a. Innym problemem jest brak CER.

Unikanie deadlock’ow–sortowanie blokad

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.

Debugowanie aplikacji wielowątkowych: opcja Show Threads in Source

Dziś kolejna wskazówka dotycząca debugowania. W poprzednim poście pokazałem Parralel Stacks, umożliwiający wizualizację wątków. Jest to niezastąpione, jeśli nie wiemy w którym miejscu lub który wątek powoduje problem. Dzisiaj kolejna opcja, “Show Threads in Source”. Najpierw stwórzmy jakieś wątki np.:

internal class Program
{
   private static readonly object Sync = new object();

   private static void Main(string[] args)
   {
       for (int i = 0; i < 50; i++)
       {
           Task.Factory.StartNew(() =>
           {
               lock (Sync)
               {
                   Thread.Sleep(5000000);
               }
           });
       }
       Console.ReadLine();
   }

}

Opcja Show Threads in Source pokaże nam, jakie inne wątki są wykonywane w danym obszarze kodu. Dlaczego jest to takie ważne? Chodzi oczywiście o deadlock’i czy zmienianie w tym samie czasie tej samej zmiennej. Po uruchomieniu powyższej aplikacji, po kilku sekundach klikamy break-in, aby uruchomić debugger. Następnie otwieramy okno Threads:

image

Kliknijmy na wątku, któremu udało się wejść do sekcji krytycznej:

image 

Na tym etapie nic specjalnego nie dzieje się. Wiemy tylko, że jeden wątek będzie blokował pozostałe, ponieważ zdefiniowaliśmy sekcję krytyczną. Czasami sprawa nie wygląda tak prosto i nie wiemy, jakie inne wątki aktualnie wykonują dany kod – zwykle mamy scheduler’y i bardziej skomplikowaną infrastrukturę.

Opcję Show Threads in Source możemy wybrać z Toolbar’a albo z menu:

image

Pojawią się dodatkowe ikonki, po lewej stronie kodu źródłowego:

image

Pokazują one, że jakieś wątki wykonują ten kod. W powyższym przypadku mamy dwie ikony. Jedna jest na lock, co się zgadza ponieważ 49 wątków czeka na wejście do sekcji krytycznej oraz jeden wątek jest na Console.ReadLine – co również ma sens ponieważ Main Thread właśnie będzie czekał na input od użytkownika.

Najeżdżając kursorem na ikonkę, dostaniemy interaktywną listę wykonywanych tam wątków:

image

Bardzo przydatna funkcja, szczególnie w przypadku analizowania blokad.

Debugowanie i wyświetlanie informacji w oknie output.

Zauważyłem, że czasami programiści używają Debug.WriteLine, aby wyświetlić jakieś informacje w oknie output:

 Debug.WriteLine("Jakies informacje.");

image

Nie ma w tym nic złego, ale czasami dodawana jest powyższa linia tylko tymczasowo, aby ułatwić sobie debugowanie (szczególnie aplikacji wielowątkowej). Visual Studio pozwala osiągnąć ten sam efekt, za pomocą zwykłego breakpoint’a. Wystarczy najpierw ustawić breakpoint (naciskamy F9), a potem kliknąć na nim i wybrać When Hit:

image

Zostanie otworzone nowe okno, w którym możemy ustawić jaka wiadomość ma zostać wyświetlona:

image

Oprócz samej wiadomości, możemy również wyświetlić zdefiniowane zmienne jak nazwa funkcji czy identyfikator wątku. Mamy  również dostęp do naszych własnych zmiennych za pomocą {}. Jeśli została zadeklarowana zmienna o nazwie text to w celu jej wyświetlenia wpisujemy {text}.

Jeżeli zatem potrzebujemy wyświetlić jakiś tekst tymczasowo, lepiej skorzystać z breakpoint’ów niż Debug.WriteLine. Warto również zaznaczyć, że breakpoint’y możemy wyeksportować do pliku i wysłać np. innemu programiście.

Debugowanie kodu zewnętrznych bibliotek, część II

Kilka dni temu opisywałem jak w VS 2008 debugować kod .NET Framework i obiecywałem sprostowanie do wersji 2012. Z tego co udało mi się dowiedzieć, temat nie jest zbyt jasny ale wygląda na to, że:

1. W niektórych wersjach VS2010 działało to ale potem znów zostało popsute.
2. W VS2012 funkcja nie działa. Jeśli komuś udało się to uruchomić pod VS 2012, proszę o komentarz pod wpisem.

Link do Microsoft Connect, opisujący bug:

http://connect.microsoft.com/VisualStudio/feedback/details/697947/net-framework-4-reference-sources-fail-since-out-of-date

Dyskusja na Stackoverflow:

http://stackoverflow.com/questions/8139269/how-do-you-enable-enable-net-framework-source-stepping

Z tego względu, w dzisiejszym wpisie, pokażę alternatywne rozwiązanie, z wykorzystaniem .NET Reflector Pro (wersja zintegrowana z VS).

Najpierw oczywiście pobieramy wersje trial i odznaczamy opcje VS z poprzedniego wpisu:
1. Enable Source Server Support
2. Enable .NET Framework Source Code Stepping

Chcemy polegać na Reflector a nie na VS, więc musimy zablokować Source Server i Code Stepping. Następnie z menu głównego wybieramy .NET Reflector->Generate PDBs…:

image

Pojawi się okno, gdzie możemy zaznaczyć biblioteki, które chcemy debugować. Oczywiście z wykorzystaniem reflector’a, nie musimy ograniczać się wyłącznie do kodu .NET Framework, ale możliwe jest debugowanie jakiekolwiek biblioteki zewnętrznej:

image

W poście, chcę zdebugować po prostu DateTime.Parse, dlatego zaznaczam z listy mscorlib. Następnie Reflector wygeneruje PDB dla danej biblioteki:

image

Pozostało nam teraz tylko uruchomić debugger i nacisnąć F11 na linii DateTime.Parse:

image

Osobiście, wielokrotnie miałem problemy z bibliotekami dostarczonymi przez firmy trzecie i nie wiedziałem dlaczego one nie zachowują się, jak tego oczekuję. Korzystając z powyższych kroków, łatwo odkryć, co nie tak robimy z daną biblioteką.