W ostatnim poście pisałem o różnych mechanizmach opartych o Spin. Zachęcam do przejrzenia ostatnich wpisów ponieważ bez tego trudno będzie zrozumieć dzisiejszy post.
SpinWait jest strukturą, w której najważniejsza metoda to SpinOnce. SpinOnce przez pierwsze 10 wywołań wykonuje klasyczny Spin (patrz poprzednie posty) dzięki czemu nie musimy obawiać się koszty związanego z uśpieniem wątku, zmianą kontekstu itp. SpinOnce jest jednak na tyle inteligentny, że po 10 wywołaniach zmienia swoje zachowanie:
-
Po 10 wywołaniach SpinOnce zaczyna używać metody Thread.Yield (patrz ostatni wpis), która oddaje wątek z powrotem do CPU i umożliwia zaplanowanie nowego wątku, o wyższym lub takim samym priorytecie, wyłącznie na tym samym procesorze. Yield będzie wywoływany za każdym razem z wyjątkiem co piątego i dwudziestego wywołania SpinOnce.
-
Thread.Sleep ( 0 ) – podobnie jak Thread.Yield z tym, że wątek, może być wykonany na dowolnym rdzeniu (nie tylko na tym samym procesorze). Thread.Sleep ( 0 ) jest wywołany co piąty raz po 10 wywołaniu Spinonce.
-
Thread.Sleep ( 1 ) – oddanie wątku na rzez innego o dowolnym priorytecie, wykonywanym na dowolnym procesorze. Sleep(1) wywołany jest co dwudziesty raz po 10 wykonaniu SpinOnce.
A co dokładnie dzieje się przez 10 wywołaniem? SpinOnce wykonuje Thread.SpinWait( N ) przekazując jako parametr najpierw 4, potem 8 a kończąc przy ostatnim, 10 wykonaniu na 2048.
Tym sposobem można zaimplementować wolną od blokad strukturę danych (źródło MSDN):
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(); } } }
Przyjrzymy się metodzie Push. Push ma za zadanie dołączyć nowy element na początku listy jednokierunkowej. Musimy zatem ustawić wskaźnik Next na aktualny początek (head) listy a następnie nowy początek listy ustawić na nowy element. Wszystko jest wykonywane w pętli while. Jeśli operację Push wykonuje wyłącznie jeden wątek, całość skończy się po jednej iteracji. W przypadku gdy mamy kolizje i dwa wątki wykonały Push wtedy zostanie wykonanych więcej iteracji. Interlocked.CompareExchange ma za zadanie ustawić początek listy (m_head) na nowo dodany element node. Interlocked jest oczywiście operacją atomową więc porównanie m_head z head oraz w przypadku gdy są one równe, ustawienie m_head na node zostanie wykonane w jednej, atomowej operacji (bezpiecznej z punktu widzenia współbieżności). W przypadku gdy drugi wątek zmienił w międzyczasie m_head, wtedy CompareExchange zwróci false i SpinOnce zostanie wywołany . Po krótkim przeczekaniu, wszystkie operacje zaczynają się od nowa. W praktyce powyższy algorytm jest szybszy niż lock. W sytuacjach gdy tylko jeden wątek wywołuje Push wtedy oczywiście widać największą przewagę Push nad implementacji z lock.
Hej
Przepraszam za późny komentarz w temacie (dopiero się zapoznałem).
Super Post (wreszcie ktoś pisze o wielowątkowości).
Generalnie piszesz że za pomocą spinwait można zaimplementować wolną od blokad strukturę danych (stos w tym przypadku), co jest prawdą ale nie do końca gdyż spin wait nie jest nam zupełnie potrzebne do implementacji tego typu struktury :).
Moim zdaniem kod na MSDN jest troszkę błędny ponieważ spin wait w tym wypadku da potencjalnie średnio gorszą wydajność niż kod bez niego (sprawdzone lokalnie). W przypadku takich struktur danych jesteśmy zainteresowani nie tyle faktem że są one lock free ale najbardziej porządaną cechą przy projektowaniu i implementacji takich algorytmów będzie wait free (!) t.j I’m mniej spinów wykonamy tym lepiej dla nas, natomiast gdy CAS się nie powiedzie to zawsze znajdzie się inny wątek ustawiający stan wewnętrznej struktury na poprawny (efekt ten nie występuje w prezentowanej strukturze), więc powinno interesować nas jak najmniejsze przełączanie kontekstu w trakcie pętli.
W przypadku nieudanego CAS ideą jest to aby jak najszybciej zakończyć pętle, w której się znajdujemy z jak najmniejszą możliwą liczbą spinów (CAS misses count) bądź też jak najszybciej przełączyć kontekst w ramach tego samego procesora aby inny wątek jak najszybciej dostał kwant czasu i jak najszybciej wykonał pętlę (zazwyczaj po przynajmniej jednym spinie). Spin wait jednak działa inaczej t.j zużywa dodatkowe iteracje lokalnie a dopiero następnie stara się przełączyć kontekst na ten sam procesor a następnie wybiera bardziej kosztowne opcje. Opcja aktywnego czekania w tym wypadku kosztuje nas najwięcej przez co daje gorszą wydajność, ale jak zakładam przykład na MSDN jest po to aby pokazać fakt że po pewnym czasie aktywnego czekania spin oddaje kwant czasu innemu wątkowi :).
Lepszym rozwiązaniem wg mnie jest następujące (mam nadzieje że kod się poprawnie sformatuje):
public void Push(T item)
{
int failedCAS = 0;
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;
/*
* This is acceptable, also num of failed cas should be dynamic, my proposal is:
* 1. Set the thresholdCAS = 10.
* 2. Calculate the Avg FailedCAS.
* 3. failedCASLimit = thresholdCAS – AvgFailedCAS,
* 3a. if failedCASLimit = 2) Thread.Yield();
//Thread.Yield(); //this is also good but stupid as it can bring down performance.
//leaving nothing here is also acceptable as we will simply spin spin spin baby 😛
}
}
Na koniec dodam że algorytmy lock free nie są aż tak wydajne jak je malują i przegrywają zazwyczaj z prostym lockiem, ponieważ dla przypadków, w których lock jest bardzo krótki .NET zakłada lekką blokadę, która sama w sobie nie powoduje wpisów w tablicy synchronizacji a jest własnie implementacją spinlocka 🙂 więc nie powoduje kolejkowania wątków oczekujących. Kiedy czas blokady wydłuża się tworzony jest wpis w tabeli synchronizacyjnej i wątek jest usypiany. Aby algorytmy lock free wygrywały z tradycyjną implementacja należy je pisać wait free, ale to kompletnie inny temat, który już nie jest przedmiotem twojego artykułu :).