list :: empty () wielowątkowe zachowanie?

9

Mam listę, z której chcę, aby różne wątki pobierały elementy. Aby uniknąć zablokowania muteksu strzegącego listy, gdy jest pusta, sprawdzam empty()przed zablokowaniem.

W porządku, jeśli wezwanie do list::empty()jest nieprawidłowe w 100% przypadków. Chcę tylko uniknąć awarii lub zakłóceń jednoczesnych list::push()i list::pop()połączeń.

Czy mogę bezpiecznie założyć, że VC ++ i Gnu GCC tylko czasami się empty()mylą i nic gorszego?

if(list.empty() == false){ // unprotected by mutex, okay if incorrect sometimes
    mutex.lock();
    if(list.empty() == false){ // check again while locked to be certain
         element = list.back();
         list.pop_back();
    }
    mutex.unlock();
}
c++ multithreading optimization race-condition stdlist Anne Quinn
źródło
1
Nie możesz tego założyć. Można użyć współbieżne pojemnik jak VC concurrent_queue
Panagiotis Kanavos
2
@Fureeish To powinna być odpowiedź. Dodałbym, że std::list::sizegwarantuje stałą złożoność czasu, co w zasadzie oznacza, że ​​rozmiar (liczba węzłów) musi być przechowywany w osobnej zmiennej; nazwijmy to size_. std::list::emptywtedy prawdopodobnie zwróci coś jako size_ == 0, a jednoczesne odczytywanie i zapisywanie size_spowoduje wyścig danych, a zatem UB.
Daniel Langr,
@DanielLangr Jak mierzy się „stały czas”? Czy jest to pojedyncze wywołanie funkcji czy pełny program?
ciekawy,
1
@curiousguy: DanielLangr odpowiedział na twoje pytanie „niezależnie od liczby węzłów listy”, to jest dokładna definicja O (1), co oznacza, że ​​każde wywołanie jest wykonywane w mniej niż pewnym stałym czasie, niezależnie od liczby elementów. en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions Inna opcja (do C ++ 11) będzie liniowa = O (n), co oznacza, że ​​rozmiar musiałby liczyć elementy (lista połączona), co byłoby jeszcze gorsze dla współbieżność (bardziej oczywisty wyścig danych niż nieatomowy odczyt / zapis licznika).
firda
1
@curiousguy: Biorąc swój przykład z dV, złożoność czasu jest taka sama - ograniczenia matematyczne. Wszystkie te rzeczy są albo rekurencyjnie zdefiniowane, albo w formie „Istnieje C takie, że f (N) <C dla każdego N” - to jest definicja O (1) (dla danego / każdego HW istnieje stała C taka że algo kończy się w czasie krótszym niż C na dowolnym wejściu). Amortyzowana oznacza średnio , co oznacza, że ​​przetworzenie niektórych danych wejściowych może potrwać dłużej (np. Konieczne ponowne przekodowanie / ponowna alokacja), ale nadal jest ona średnio stała (przy założeniu wszystkich możliwych danych wejściowych).
firda

Odpowiedzi:

10

W porządku, jeśli wezwanie do list::empty()jest nieprawidłowe w 100% przypadków.

Nie, nie jest dobrze. Jeśli sprawdzisz, czy lista jest pusta poza jakimś mechanizmem synchronizacji (blokowanie muteksu), oznacza to, że masz wyścig danych. Wyścig danych oznacza, że ​​masz niezdefiniowane zachowanie. Niezdefiniowane zachowanie oznacza, że ​​nie możemy dłużej myśleć o programie, a wszelkie otrzymywane dane wyjściowe są „poprawne”.

Jeśli cenisz swoje zdrowie psychiczne, weźmiesz hit wydajności i zablokujesz muteks przed sprawdzeniem. To powiedziawszy, lista może nie być dla ciebie odpowiednim pojemnikiem. Jeśli możesz nam powiedzieć dokładnie, co robisz z tym, możemy zaproponować lepszy pojemnik.

NathanOliver
źródło
Osobista perspektywa, połączenie list::empty()to czynność czytania, która nie ma nic wspólnego zrace-condition
Ngọc Khánh Nguyễn
3
@ NgọcKhánhNguyễn Jeśli dodają elementy do listy, to zdecydowanie powoduje wyścig danych, gdy piszesz i czytasz rozmiar w tym samym czasie.
NathanOliver,
6
@ NgọcKhánhNguyễn To nieprawda. Warunkiem wyścigu jest read-writelub write-write. Jeśli nie wierz mi, daj sekcji STANDARDOWE na wyścigach danych odczytu
NathanOliver
1
@ NgọcKhánhNguyễn: Ponieważ ani zapis, ani odczyt nie są gwarantowane, że są atomowe, dlatego mogą być wykonywane jednocześnie, dlatego odczyt może spowodować coś zupełnie niepoprawnego (nazywany odczytem podartym). Wyobraź sobie, że zapisujesz zmianę 0x00FF na 0x0100 w małym 8-bitowym MCU endian, zaczynając od przepisania niskiego 0xFF na 0x00, a odczyt osiąga teraz dokładnie to zero, odczytywanie obu bajtów (zapis wątku spowolniony lub zawieszony), zapis jest kontynuowany przez aktualizację wysokiego bajtu na 0x01, ale wątek odczytu już otrzymał niepoprawną wartość (ani 0x00FF, ani 0x0100, ale nieoczekiwany 0x0000).
firda
1
@ NgọcKhánhNguyễn Może to dotyczyć niektórych architektur, ale maszyna wirtualna C ++ nie oferuje takiej gwarancji. Nawet jeśli twój sprzęt tak zrobił, kompilator byłby w stanie zoptymalizować kod w taki sposób, że nigdy nie zobaczyłbyś zmiany, ponieważ bez synchronizacji wątków może założyć, że działa tylko jeden wątek i odpowiednio go zoptymalizować.
NathanOliver,
6

Istnieje odczyt i zapis (najprawdopodobniej do sizeczłonka std::list, jeśli założymy, że tak się nazywa), które nie są zsynchronizowane ze sobą w odczynniku . Wyobraź sobie, że jeden wątek wywołuje empty()(w twoim zewnętrznym if()), podczas gdy drugi wątek wszedł w wewnętrzny if()i wykonuje się pop_back(). Czytasz wtedy zmienną, która prawdopodobnie jest modyfikowana. To jest niezdefiniowane zachowanie.

Fureeish
źródło
2

Jako przykład tego, jak coś może pójść nie tak:

Wystarczająco inteligentny kompilator może zobaczyć, że mutex.lock()nie może zmienić list.empty()wartości zwracanej, a tym samym ifcałkowicie pomija kontrolę wewnętrzną , ostatecznie prowadząc do pop_backlisty na liście, której ostatni element został usunięty po pierwszej if.

Dlaczego to może zrobić? Synchronizacja nie jest możliwa list.empty(), więc gdyby została zmieniona jednocześnie, stanowiłoby to wyścig danych. Standard mówi, że programy nie będą miały wyścigów danych, więc kompilator weźmie to za pewnik (w przeciwnym razie może nie przeprowadzić prawie żadnych optymalizacji). Dlatego może przyjąć perspektywę jednowątkową na niezsynchronizowanym list.empty()i stwierdzić, że musi pozostać stała.

To tylko jedna z wielu optymalizacji (lub zachowań sprzętowych), które mogą uszkodzić Twój kod.

Max Langhof
źródło
Obecne kompilatory nawet nie chcą optymalizować a.load()+a.load()...
ciekawy
1
@curiousguy Jak by to zoptymalizować? Żądasz pełnej spójności sekwencyjnej, więc dostaniesz to ...
Max Langhof,
@MaxLanghof Nie uważasz, że optymalizacja a.load()*2jest oczywista? a.load(rel)+b.load(rel)-a.load(rel)Zresztą nawet nie jest zoptymalizowany. Nic nie jest. Dlaczego oczekujesz, że blokady (które zasadniczo mają spójność sekwencji) będą bardziej zoptymalizowane?
ciekawy,
@curiousguy Ponieważ porządkowanie w pamięci dostępu nieatomowego (tutaj przed i po śluzie) i atomów jest zupełnie inne? Nie oczekuję, że blokada zostanie zoptymalizowana „bardziej”, spodziewam się, że niezsynchronizowane dostępy zostaną zoptymalizowane bardziej niż sekwencyjnie spójne. Obecność zamka jest nieistotna z mojego punktu widzenia. I nie, kompilator nie jest dozwolone w celu optymalizacji a.load() + a.load()do 2 * a.load(). Jeśli chcesz dowiedzieć się więcej, zadaj pytanie na ten temat.
Max Langhof,
@ MaxLanghof Nie mam pojęcia, co nawet próbujesz powiedzieć. Zamki są zasadniczo sekwencyjnie spójne. Dlaczego implementacja miałaby próbować optymalizować niektóre prymitywy wątków (blokady), a nie inne (atomiki)? Czy spodziewasz się, że dostęp nieatomowy zostanie zoptymalizowany pod kątem zastosowań atomowych?
ciekawy