Jak wykonać synchronizację wątków bez użycia mutex, semorphore, spinLock i futex?

Question

To jest pytanie do wywiadu, przeprowadzono wywiad.

Jak wykonać synchronizację nici bez użycia mutex, semorphore, spinLock i futex?

Biorąc pod uwagę 5 wątków, jak sprawić, by 4 z nich czekało na sygnał z lewej nici w tym samym punkcie? oznacza to, że gdy wszystkie wątki (1,2,3,4) wykonują w punkcie w funkcji wątku, zatrzymują się i oczekują na sygnał z wątku 5 wysyłającego sygnał, w przeciwnym razie nie będą kontynuowali.

Mój pomysł:

Wykorzystanie globalnej zmiennej bool jako flaga, jeśli gwint 5 nie ustawia go prawda, wszystkie inne wątki czekać na jednym punkcie, a także ustawić ich zmienna flag prawda. Po tym, jak wątek 5 znajdzie wszystkie zmienne flag wątku są prawdziwe, ustawi ono flagę var true.

To jest zajęty-czekać.

Jakieś lepsze pomysły?

Dzięki

the pseudo code: 
bool globalflag = false; 
bool a[10] = {false} ; 
int main() 
{ 
    for (int i = 0 ; i < 10; i++) 
    pthread_create(threadfunc, i) ; 

     while(1) 
     { 
     bool b = true; 
     for (int i = 0 ; i < 10 ; i++) 
     { 
       b = a[i] & b ; 
     } 
     if (b) break; 
    } 
    } 
    void threadfunc(i) 
    { 
    a[i] = true; 
    while(!globalflag); 
    } 

Answer 1

rozpocznie z pustym połączonej listy wątków oczekujących. Głowa powinna być ustawiona na 0.

Użyj CAS, porównaj i zamień, aby wstawić wątek na czele listy kelnerów. Jeśli głowica = -1, nie wstawiaj ani nie czekaj. Możesz bezpiecznie używać CAS do wstawiania elementów na czele listy połączonej, jeśli robisz to dobrze.

Po wstawieniu oczekujący wątek powinien poczekać na SIGUSR1. Aby to zrobić, użyj sigwait().

W trybie gotowości wątek sygnalizacyjny używa CAS do ustawienia listy oczekiwania na wartość -1. Zapobiega to dodawaniu kolejnych wątków do listy oczekujących. Następnie wątek sygnalizacyjny iteruje wątki na liście oczekujących i wywoła wątek pthread_kill (&, SIGUSR1), aby obudzić każdy oczekujący wątek.

Jeśli SIGUSR1 zostanie wysłany przed wywołaniem sigwait, sigwait natychmiast powróci. W związku z tym nie będzie wyścigu między dodaniem wątku do listy oczekujących a wywołaniem sigwait.

EDYTOWANIE:

Dlaczego CAS jest szybszy niż muteks? Odpowiedź Laymena (jestem laikiem). Jest szybszy dla niektórych rzeczy w niektórych sytuacjach, ponieważ ma niższy narzut, gdy nie ma ŻADNEJ rasy. Jeśli więc zmniejszysz swój równoczesny problem do momentu zmiany 8-16-32-64-128 bitów sąsiedniej pamięci, a wyścig nie zdarzy się bardzo często, CAS wygrywa. CAS jest w zasadzie nieco bardziej fantazyjnym/drogim instruktorem mov, gdzie i tak zamierzałeś zrobić regularne "mov". Jest to "wymiana zamka" lub coś w tym stylu.

Z drugiej strony muteks to cała masa dodatkowych rzeczy, które zabrudzają inne linie pamięci podręcznej i używają więcej barier pamięci, itp. Chociaż CAS działa jak bariera pamięci na x86, x64 itp. Wtedy oczywiście musisz odblokować muteks, który jest prawdopodobnie o tyle samo dodatkowych rzeczy.

Oto jak dodać element do połączonej listy przy użyciu CAS:

while (1) 
{ 
    pOldHead = pHead; <-- snapshot of the world. Start of the race. 
    pItem->pNext = pHead; 
    if (CAS(&pHead, pOldHead, pItem)) <-- end of the race if phead still is pOldHead 
    break; // success 
} 

Jak często myślisz Twój kod będzie mieć wiele wątków w tej linii CAS dokładnie w tym samym czasie? W rzeczywistości .... niezbyt często. Przeprowadziliśmy testy, które zapętlały się dodając miliony elementów z wieloma wątkami w tym samym czasie i zdarza się to mniej niż 1% czasu. W prawdziwym programie może się to nigdy nie zdarzyć.

Oczywiście, jeśli jest wyścig, musisz wrócić i ponownie wykonać pętlę, ale w przypadku listy z linkami, co to kosztuje?

Wadą jest to, że nie można wykonywać bardzo skomplikowanych czynności na tej liście połączonej, jeśli zamierzasz użyć tej metody do dodawania pozycji do głowy. Spróbuj wprowadzić listę podwójnie połączoną. Co za ból.

EDIT:

W powyższym kodzie używam makro CAS. Jeśli używasz Linuksa, CAS = makro używając __sync_bool_compare_and_swap. Zobacz gcc atomic builtins. Jeśli używasz Windows, CAS = makro używając czegoś podobnego InterlockedCompareExchange. Oto co funkcja inline w oknach może wyglądać następująco:

inline bool CAS(volatile WORD* p, const WORD nOld, const WORD nNew) { 
    return InterlockedCompareExchange16((short*)p, nNew, nOld) == nOld; 
} 
inline bool CAS(volatile DWORD* p, const DWORD nOld, const DWORD nNew) { 
    return InterlockedCompareExchange((long*)p, nNew, nOld) == nOld; 
} 
inline bool CAS(volatile QWORD* p, const QWORD nOld, const QWORD nNew) { 
    return InterlockedCompareExchange64((LONGLONG*)p, nNew, nOld) == nOld; 
} 
inline bool CAS(void*volatile* p, const void* pOld, const void* pNew) { 
    return InterlockedCompareExchangePointer(p, (PVOID)pNew, (PVOID)pOld) == pOld; 
} 

Answer 2

1. Wybierz sygnał do użycia, powiedzmy SIGUSR1.
2. Użyj pthread_sigmask, aby zablokować SIGUSR1.
3. Utwórz wątki (dziedziczą maskę sygnału, dlatego 1 należy wykonać jako pierwszą!)
4. Wątki 1-4 wywołują sigwait, blokując do czasu otrzymania SIGUSR1.
5. Wątek 5 wywołuje kill() lub pthread_kill 4 razy z SIGUSR1. Ponieważ POSIX określa, że ​​sygnały będą dostarczane do wątku, który nie blokuje sygnału, zostanie dostarczony do jednego z wątków oczekujących w sigwait(). Nie ma zatem potrzeby śledzenia, które wątki już odebrały sygnał, a które nie, z powiązaną synchronizacją.

Answer 3

Można to zrobić za pomocą SSE3 za MONITOR i MWAIT instrukcje dostępne przez _mm_mwait i _mm_monitor intrinsics, Intel ma artykuł o nim here. (istnieje również patent na używanie monitora pamięci - oczekiwanie na rywalizację o blokady here, które mogą być interesujące).

Answer 4

Myślę, że patrząc Peterson's algorithm lub Dekker's algorithm

one synchronizowane wątki tylko w oparciu o pamięci współdzielonej