Livelock: przykład

Deadlock jest zdecydowanie najbardziej znanym problemem występującym w świecie wielowątkowym. Nieco gorzej znanym jest livelock. Pisałem już kiedyś o nim tutaj.

Nie pokazałem jednak przykładu i wielu osobom ciężko wyobrazić sobie livelock w praktyce. Występuje on jednak bardzo często i nie jest to coś, co powinno być rozważane wyłącznie teoretycznie. Bardzo często, najbardziej zoptymalizowane algorytmy cierpią właśnie na livelock.

Jak pisałem już kiedyś, livelock najłatwiej wyjaśnić na przykładzie dwóch osób na korytarzu, które próbują się minąć. Bardzo często wybierają ten sam kierunek ucieczki, co kończy się blokadą. W przeciwieństwie do deadlock, zmieniają oni jednak swój “stan”. Deadlock to coś statycznego, gdzie stan wątków pozostaje taki sam. W Livelock zmienia on się, jednak wciąż uniemożliwia wykonanie całego kodu. Inną wspólną cechą przykładu z dwoma osobami na korytarzu i livelock jest fakt, że kiedyś one się w końcu miną. Livelock bardzo często ma charakter tymczasowy – po jakimś czasie wątki tak zmienią swój stan, że możliwe będzie ich wykonanie. Oczywiście w przypadkach pesymistycznych nigdy to nie będzie miało miejsca, ale w przeciwieństwie do deadlock, jest to jak najbardziej możliwe.

Pora na przykład… Jak wspomniałem, livelock głównie ma miejsce gdy staramy się pisać optymalny kod, bez użycia czasochłonnych blokad. Wyobraźmy sobie, że chcemy zaimplementować funkcję zwiększającą liczbę o jeden:

internal class Program
{
   private static int Value = 0;
   private const int N = 1000;

   private static  void Main(string[] args)
   {
       Task t1 = Task.Factory.StartNew(()=>Increment(N));
       Task t2 = Task.Factory.StartNew(() => Increment(N));
       Task t3 = Task.Factory.StartNew(() => Increment(N));
       Task t4 = Task.Factory.StartNew(() => Increment(N));
       Task t5 = Task.Factory.StartNew(() => Increment(N));
       Task t6 = Task.Factory.StartNew(() => Increment(N));

       Task.WaitAll(t1, t2, t3, t4,t5,t6);

       Console.WriteLine(Value);
   }

   private static void Increment(int n)
   {
       for (int i = 0; i < n;i++)
       {
           Increment();
           Thread.Sleep(1);
       }
   }
   private static void Increment()
   {
       int original = Value;

       while (Interlocked.CompareExchange(ref Value, original + 1, original) != original)
       {

           original = Value;
       }
   }
}

Wiem, że można użyć Interlocked.Increment ale nie o to w przykładzie chodzi. Jakiś czas temu temu, również pokazywałem jak zaimplementować stos, bez użycia blokad:

public class LockFreeStack<T>
{
    private volatile Node m_head;

    private class Node { public Node Next; public T Value; }

    public void Push(T item)
    {
        var spin = new SpinWait();
        Node node = new Node { Value = item }, head;
        while (true)
        {
            head = m_head;
            node.Next = head;
            if (Interlocked.CompareExchange(ref m_head, node, head) == head) break;
            spin.SpinOnce();
        }
    }
    public bool TryPop(out T result)
    {
        result = default(T);
        var spin = new SpinWait();

        Node head;
        while (true)
        {
            head = m_head;
            if (head == null) return false;
            if (Interlocked.CompareExchange(ref m_head, head.Next, head) == head)
            {
                result = head.Value;
                return true;
            }
            spin.SpinOnce();
        }
    }
}

Jeśli ktoś nie rozumie konstrukcji z CompareExchange to proszę wrócić do wspomnianych wpisów i przenalizować jeszcze raz kod. W skrócie jest to synchronizacja optymistyczna – liczymy na to, że żaden inny wątek w międzyczasie nie zmodyfikował nam stanu. Jeśli to zrobił, musimy zaczynać od nowa – stąd pętla while. Przyjrzyjmy się inkrementacji:

private static void Increment()
{
  int original = Value;

  while (Interlocked.CompareExchange(ref Value, original + 1, original) != original)
  {

      original = Value;
  }
}

Może się zdarzyć, że wątek T1 nigdy nie zdoła zwiększyć liczby, ponieważ zawsze pozostałe wątki będą go ubiegały i stąd T1 będzie musiał zaczynać od nowa. Mam na myśli sytuację, w której T1 ustawia original=Value, ale potem CompareExchange wykrywa, że zmienna została zmieniona i pętla zaczyna się od nowa. W praktyce nie zachodzi to zbyt często i stąd, statycznie algorytmy bez użycia locków są dużo szybsze.

Leave a Reply

Your email address will not be published.