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

> On 02.07.2013 19:56, Edek wrote:
>> Dnia pamiętnego Tue, 02 Jul 2013 18:16:18 +0200, Michoo wyjmując peta
>> oznajmił:
>
>>> - w przypadku odczytu INIT_DONE pomijamy cały blok - inicjalizacja
>>> została już wykonana
>>
>> Tak, ale nie miała miejsce synchronizacja.
>
> Jaka synchronizacja?

No żeby udowodnić widzialność danych musisz udowodnić odpowiedni
'ordering' pomiędzy wątkami.

>>> Pisane na szybko więc co przeoczyłem?
>>
>> Model pamięci C++11?
>
> pthreads z nie_pojebaną_architekturą (tm)

ARM i Itanium się kwalifikują jako poyebane? IMHO tak.

>> 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.
>
> Gwarancja jest oidp silniejsza - jeżeli wątek kończy release to zmiany
> są "commited" w pamięci.

Nie bardzo. Gwarancje dotyczą widoczności pomiędzy wątkami, nie
ma Jednego Prawdziwego Stanu Pamięci. Nie znam finalnego standartu, ale
takie były proposale.

>> Jeżeli
>> nie ma przejścia przez mutex obu wątków mamy race, czyli wątek B
>> czyta potencjalnie śmieci.
>
> Czyta albo stary stan, albo nowy stan[*] a nie śmieci - dlatego m.i. się
> używa sig_atomic_t - pierwotne rozwiązanie też to zakłada.

A dlaczego wszystkie pola ustawiane przez func miałyby używać
sig_atomic_t? Nie doczytałeś, nie chodzi o zmienne
użyte w tym algorytmie, ale dowolne inicjalizowane przez func
a używane po przejściu tego algorytmu. Czyli w tym algorytmie ich
nie ma, są powodem istnienia once().

Naprawdę wszystkie Twoje obiekty w polach statycznych w C++ używają
wszędzie sig_atomic_t? Ja tam wolę float czy int i parę innych.

> [*] W praktyce nawet na NUMA jest utrzymywana spójność cache więc od
> momentu zapisu z cache do pamięci wszystkie odczyty będą miały nowy stan.

Na Intelach tak, sam mówiłem, że na Intelach i tak będzie ok. C++
ma działać na innych architekturach też. W tym takich, które powstaną
za 10 lat, najlepiej bez losowych fackapów. Jak tak słuchałem
Ludzi Który Wiedzą Co Mówią, ARM, Itanium, Alphy są inne niż x86 ;)
Bardzo Inne (tm).

>> Zapis dotyczy zmiennych użytych tutaj i wszystkich
>> zapisów w func(), które po przejściu algorytmu muszą być widoczne.
>
> Masz barierę na lock() w linii 07 zaraz po wywołaniu func() a dopiero
> potem modyfikację stanu zmiennej w 08.
>
>>
>> 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)
>
> lock() synchronizuje pamięć

Nie no proszę cię. Jak się synchronizuje dostęp do danych w dwóch
wątkach to trzeba w obu użyć synchronizacji. Albo atomics, które
też mają semantykę 'ordering in memory model', też w obu.

Czy ty mnie nie prowokujesz?

>> 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
>
> No właśnie nie może, bo to oznacza, że masz architekturę na której
> zmiany wykonane po barierze są widoczne przed zmianami wykonanymi przed
> barierą.

Inny punkt widzenia jest taki, że drugi wątek może czytać w innej
kolejności, skoro nie ma pomiędzy tymi punktami synchronizacji.

I nie, Intel tego nie zabrania, bo kompilator może inaczej
szeregować operacje, jeżeli tak mu wygodnie podczas optymalizacji.
Sprzęt przed kompilatorem Cię nie uchroni.

>> Powyższa sekwencja może jest mało prawdopodobna, ale mamy
>> data race.
>
> Jeżeli chcesz się trzymać litery standardu C++11 to sam odczyt w linii
> 01 oryginalnego rozwiązania to jest data race, więc całe dalsze
> wykonanie to UB.

Co najwyżej może podlegać word-tearing, ale używają typu,
który ustawiany jest cały (czyli atomicznie, ale z najsłabszym
ordering czyli żadnym).

Sam fakt że może widzieć starą wartość algorytm uwzględnia i to nie
jest UB. Z wątkami tak jest, albo jeden może coś zrobić wcześniej a
drugi później albo odwrotnie i czy atomik już jest ustawiony
czy jeszcze nie nie jest żadnym UB.

Swoją szosą UB stosuje się do reguły "as-if program działa w jednym
wątku".

>> Dlatego ten algorytm jest genialny, kolejne
>> przejścia są bez synchronizacji.
>
> Powiedziałbym, że jest "normalny" - działa w obrębie pewnych założeń.
> Tyle, że rozwiązuje problem, którego imo nie ma przez nałożenie
> ograniczenia na liczbę once a przy tym nie eliminując problemu z UB.

Ok, algorytm nie jest może wiekopomny, ale jak widać dowodzenie
jego poprawności nie jest takie trywialne.

--
Edek