Zagrożenia w programowaniu współbieżnym: lock convoy oraz stampede

O zakleszczeniu czy zagłodzeniu, każdy programista słyszał, nawet nie mając styczności z programowaniem wielowątkowym. Opisany w poprzednim poście przykład livelock jest bardziej wyrafinowanym problemem.

Dzisiaj z kolei o kilku innych błędach popełnianych w środowisku wielowątkowym.

Lock Convoy  – występuje, gdy mamy za dużo wątków próbujących założyć blokadę. Załóżmy, że napisaliśmy następującą funkcję:

private void DoAsync()
{
    lock(_sync)
    {
        // jakis kod
        Thread.Sleep(1000);
    }
    // jakis kod 
}

Wykonanie jej zajmie oczywiście więcej niż jedna sekunda. Co gorsze, mamy tam sekcję krytyczną, która zawsze będzie wykonywana sekwencyjnie. Jeśli nowe wątki będą wywoływać DoAsync z wyższą częstotliwością niż może nastąpić zwolnienie blokady, wtedy do czynienia będziemy mieli z lock convoy. Lock convoy to po prostu akumulacja wątków, które blokują zasoby, ale nie mogą wykonać kodu, ponieważ uzyskanie dostępu do sekcji krytycznej jest niemożliwe.

Lock Convoy może zrujnować całkowicie system. Jeśli występuje, po jakimś czasie po prostu zabraknie zasobów. Dlatego ważne jest monitorowanie (np. za pomocą performance counters) liczby wątków tworzonych w danym systemie.

Inną ciekawostką jest, że kiedyś systemy Windows, planowały wykonywanie wątków, w takiej samej kolejności jakie one chciały wejść w sekcję krytyczną. Jeśli zatem T1 wykonuje sekcję krytyczną, a T2 oraz T3 kolejno chciały do niej wejść, wtedy OS gwarantował, że T2 najpierw uzyska dostęp, a potem dopiero T3. Jaki to ma związek z Lock Convoy? Proszę zauważyć, że pomiędzy zwolnieniem locka a przyznaniem go uśpionemu wątkowi, wykonanych musi być wiele cyklów procesora. Z tego względu, jeśli mamy opisaną powyżej sytuację (T1 wychodzi z sekcji krytycznej a T2,T3 są uśpione), dużo lepiej nadać dostęp wątkowi, który jest już wykonywany. Załóżmy, że T4 nie wymaga zmiany kontekstu i chce akurat wejść do sekcji krytycznej trzymanej przez T1 – dużo szybciej będzie mu nadać dostęp niż zmieniać kontekst dla T2. Jaka jest wada jednak takiego rozwiązania? Oczywiście może dojść do zagłodzenia T2 i T3.

Kolejnym zagrożeniem to stampede, występującym również, gdy korzystamy np. z metody Monitor.PulseAll. Przykład:

class ConditionPatternSample
{
   private readonly Object _lock = new Object();
   private Boolean _condition = false;

   public void Thread1()
   {
       Monitor.Enter(_lock);

       while (!_condition)
       {
           Monitor.Wait(_lock);
       }
       _condition = false;
       Monitor.Exit(_lock);
   }

   public void Thread2()
   {
       Monitor.Enter(_lock);

       _condition = true;

       Monitor.PulseAll(_lock);

       Monitor.Exit(_lock);
   }
}

Powyższy kod, prezentuje sprawdzanie flagi w środowisku wielowątkowym. Używamy tutaj PulseAll, który wybudza wszystkie wątki. Jaki jest tego skutek? Jeśli mamy 100 wątków czekających w metodzie Thread1, zostaną one wszystkie wybudzone. A co potem? Jak widać, są one w sekcji krytycznej i znów 99 będzie musiało zostać uśpionych. Skutek tego jest dość katastrofalny – mnóstwo zmian kontekstu, która jest bardzo kosztowna.

Klasa Monitor ma dwie kolejki, wątków gotowych do uzyskania blokady oraz czekających na Pulse. W momencie, gdy wykonujemy metodę Monitor.Enter, przeniesiony on jest do kolejki “ready”. W przypadku wykonania Monitor.Wait jest on przeniesiony do “waiting queue”. Z kolei Pulse przenosi tylko pierwszy wątek z waiting queue  z powrotem do ready queue. PulseAll  za to przeniesie wszystkie wątki, nie tylko ten pierwszy. Różnica jest taka, że wątki mogą uzyskać dostęp do sekcji, wyłącznie gdy są w ready queue.

Ktoś może słusznie zadać pytanie. Po co wywoływać PulseAll, skoro zarówno Pulse jak i PulseAll muszą być umieszczone pomiędzy Monitor.Enter a Monitor.Exit? W końcu zawsze tylko jeden wątek będzie mógł wykonywać daną operację. Czy nie będzie to w praktyce to samo? Pulse budzi jeden wątek i jest on wykonywany. PulseAll budzi wszystkie, ale tylko jeden naturalnie będzie wykonany. Nie lepiej nie używać po prostu PulseAll i tym sposobem unikać zawsze stapmede? Wszystko zależy od konkretnego scenariusza. Jeśli wszystkie wątki sprawdzają ten sam warunek (jak wyżej), nie ma sensu korzystać z PulseAll, ponieważ kod może zostać wykonany przez jakikolwiek wątek. Inna sprawa, gdy każdy wątek czeka na inny warunek. Wtedy jeśli będziemy budzić wątek po wątku, wykonamy masę niepotrzebnych zmian kontekstu. Wybudzimy np. T1, który sprawdzi warunek i znów uśpi się. PulseAll z kolei wybudzi wszystkie i każdy z nich sprawdzi czy spełnia dany warunek. PulseAll gwarantuje nam, że wszystkie wątki sprawdzą czy spełniają dany warunek. Gdybyśmy wywołali Pulse jeden wątek sprawdziłby warunek i w przypadku jego niespełnienia zostałby przeniesiony znów do waiting queue, co spowoduje, że wątki, które mogłyby coś wykonać, nie zostaną odpalone.

Podsumowując: PulseAll może prowadzić do stampedee. Czasami po prostu jest to wymagane, aby poprawnie zaimplementować algorytm  – przykład sprawdzania różnych warunków w środowisku równoległym. Monitor.Pulse z kolei może pogorszyć lock convoy. Wyobraźmy sobie, że budzimy wątek, on sprawdza warunek i znów musimy go uśpić – będziemy potrzebować więcej zmian kontekstu. Problem z Monitor.Pulse i  lock convoy to tam sama sytuacja jak z opisanym na początku szeregowaniem wątku – czasami lepiej dać dostęp do sekcji krytycznej wątkowi, który nie potrzebuje zmiany kontekstu i jest gotowy uzyskać dostęp od razu.

Leave a Reply

Your email address will not be published.