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.

Leave a Reply

Your email address will not be published.