Dnia pamiętnego Tue, 02 Jul 2013 18:16:18 +0200, Michoo wyjmując peta
oznajmił:

> On 01.07.2013 19:08, Edek wrote:
>> Dnia pamiętnego Mon, 01 Jul 2013 18:24:17 +0200, Michoo wyjmując peta
>> oznajmił:

>>> Co do samego algorytmu - potrzebne są trzy stany:
>>> przed_inicjalizacją, w_trakcie, po_inicjalizacji, nie da się tego zrobić
>>> na JEDNEJ fladze binarnej, można by użyć dwóch(i wprowadzić odpowiednie
>>> poprawki), ale po co?
>>
>> Nie, jest potrzebna monotonicznie rosnąca liczba, nie trzy stany. Mi
>> to zajęło z pół godziny żeby dojść dlaczego: spróbuj zastąpić
>> monotonicznie rosnącą stanami i albo udowodnij poprawność
>> albo udowodnij że jest problem.
>
> #define START_VALUE 2
> #define BEING_INITIALIZED 1
> #define INIT_DONE 0
>
> /* PRECONDITION:
> *once == START_VALUE
> */
>
> void fast_pthread_once( fast_pthread_once_t *once, void (*func)(void) )
> {
> /*01*/ if ( *once != INIT_DONE ) {
> /*02*/ check( pthread_mutex_lock(&mu) == 0 );
> /*03*/ if ( *once == START_VALUE ) {
> /*04*/ *once = BEING_INITIALIZED;
> /*05*/ check( pthread_mutex_unlock(&mu) == 0 );
> /*06*/ (*func)();
> /*07*/ check( pthread_mutex_lock(&mu) == 0 );
> /*08*/ *once = INIT_DONE;
> /*09*/ check( pthread_cond_broadcast(&cv) == 0 );
> /*10*/ } else {
> /*11*/ while ( *once != INIT_DONE ) {
> /*12*/ check( pthread_cond_wait(&cv, &mu) == 0 );
> /*13*/ }
> /*14*/ }
> /*15*/ check (pthread_mutex_unlock(&mu) == 0);
> /*16*/ }
> }
>
> Wszystkie zapisy i odczyty (poza linią 01) są chronione muteksem. Tak więc:
> A) w lini 01 może zostać albo odczytana wartość początkowa, wartość z
> linii 04 lub 08
> - w przypadku odczytu INIT_DONE pomijamy cały blok - inicjalizacja
> została już wykonana

Tak, ale nie miała miejsce synchronizacja.

> - w przypadku odczytu innej wartości rozpoczynamy blok synchronizowany B
>
> B) w linii 03 może zostać albo odczytana wartość początkowa, wartość z
> linii 04 lub 08
> - w przypadku wartości innej niż START_VALUE oczekujemy w liniach 11,12
> na zakończenie inicjalizacji [*] (deadlock przy wywołaniu rekurencyjnym)
> - w przypadku wartości START_VALUE zmieniamy ją na BEING_INITIALIZED i
> kończymy blok synchronizowany - od tego momentu żaden wątek w 01 ani 03
> nie odczyta wartości START_VALUE
> - Po zakończeniu inicjalizacji zapisujemy *once = INIT_DONE i wybudzamy
> wątki czekające w linii 12 - od tego momentu nie zostanie odczytana inna
> wartość niż INIT_DONE
>
> Czekające wątki po kolei kończą oczekiwanie 12->11->15.
>
> [*] Jeżeli wartość zmieniła się na INIT_DONE po odczycie w linii 01 ale
> przed otrzymaniem muteksu to nie czekamy w linii 12 tylko kończymy na 15.
>
> Pisane na szybko więc co przeoczyłem?

Model pamięci C++11?

>> Ja potrafię to drugie.
>>
> Poproszę.

Model Pamięci ma taką cechę że zapis w wątku A jest widoczny w wątku B
gdy nastąpi uszeregowanie poprzez release w A i acquire w B. Lock() to
aquire, unlock() to release, albo można w ogóle każdą operację na
mutexie traktować 'stricter' jako sequence point - czyli jeżeli oba
wątki przejdą op na mutex to zapis w A może być odczytany w B. Jeżeli
nie ma przejścia przez mutex obu wątków mamy race, czyli wątek B
czyta potencjalnie śmieci. Zapis dotyczy zmiennych użytych tutaj i wszystkich
zapisów w func(), które po przejściu algorytmu muszą być widoczne.

func to głównie konstruktory, przejście całego algorytmu oznacza,
że obiekty są już zainicjalizowane (przez wywołanie func).

Uff, definicje z głowy ;). Wątek A i wątek B i numery linii,
możliwa sekwencja:

A linie 1 do 5 (w 2 i 5 jest mutex)
A 6: konstruktor (po to jest ten algorytm) może zapisać pola
A 7: mutex (acquire)
A 8: once = INIT_DONE

B 1: (once == INIT_DONE) == true (co nie musi być prawdą, ale może)
B 17: wątek używa wartości z A 6, które nie muszą być poprawne,
bo wątek B nie przeszedł przez żaden mutex. Może odczytać
śmieci, czyli mamy race

Powyższa sekwencja może jest mało prawdopodobna, ale mamy
data race.

Na Intelach jeżeli dobrze kojarzę to się nie ma prawa zdarzyć,
bo Intel ma taki model pamięci że jeżeli zapis do once jest widoczny
to poprzednie zapisy z func też, były wcześniej. Pisząc asma x86 można
na tym polegać, ale w bibliotece taki algorytm w C na innej platformie
nagle ma niewidoczne efekty konstruktorów. Przynajmniej wg. modelu
pamięci C11 i C++11.

W oryginalnym algorytmie zawsze będzie odpowiedni 'ordering' przez
synchronizację, bo ta zmienna thread-local jest zmieniana tylko
przy zankniętym mutex, więc pierwszy if bez przejścia przez mutex
nigdy nie będzie false. Dlatego ten algorytm jest genialny, kolejne
przejścia są bez synchronizacji.

Pozdrawiam
--
Edek