On 02.07.2013 23:06, Edek wrote:
> 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.

No i memory barrier jest definiowane jako:
- wszystkie zapisy wykonane do tej pory zostają commitowane do pamięci
- wszystkie odczyty od tej pory czytają ostatnio zapisany stan

>
>>>> 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.

Imo nie. Nadal jak robisz barrierę to wszystkie zapisy są widoczne.

>
>>> 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.

Nawet w sytuacji gdy zapis jest "rozgłaszany" do odpowiedniego procesu
dopiero w momencie wywołania którejś z funkcji synchronizacyjnych masz
sytuację w której:
- nie możesz czytać obiektów przed func() bo nie zostały zainicjalizowane
- pierwszy odczyt powinien dostarczyć to co zostało commitnięte w
ostatniej synchronizacji
więc albo nie masz zsynchronizowanej wartości *once i wchodzisz do
muteksu, albo masz zsynchronizowaną wartość *once ale wtedy masz
zsynchronizowane też efekty func(). Wiem o write-reordering, ale barrier
to barrier.

Potraktuj to po prostu jako założenie(co napisałem) - tak jak autor
oryginalnego algorytmu założył, że zapisy są "ordered" tak ja zakładam,
że barrier znaczy barrier a nie niewiadomo-co.

>
>>> 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().

Jest barriera przed zapisem *once, które jest atomowe. barriera jest
ordered z operacją atomową, więc kolejność jest jasno zdefiniowana.

>
> 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.

Nie pisałem o intelach - one zazwyczaj jednak są SMP.


> 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).

Zaprezentowany algorytm jeżeli ma serializację odczytu to zgłosi wyjątek
w momencie zapisu - coś jak javowe ConcurrentModificationException -
pamięć została odczytana w sposób konfliktujący z zapisem.

>
>>> Zapis dotyczy zmiennych użytych tutaj i wszystkich
>>> zapisów w func(), które po przejściu algorytmu muszą być widoczne.
>>
>> Masz barrierę 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.

Z tego wynika, że mutex_lock robi synchronizację pamięci:
http://pubs.opengroup.org/onlinepubs/9699919799/base
defs/V1_chap04.html#tag_04_11

Drugi wątek ma prawo zrobić odczyt inicjalizowanych obiektów dopiero PO
zakończeniu once().

>
> Czy ty mnie nie prowokujesz?

Ależ oczywiście - wiem czego "unika" ta implementacja i uważam, że żadna
istniejąca teraz architektura ani żadna która zaistnieje w przyszłości
jeżeli daje gwarancję "serializowalności" to tym bardziej daje gwarancję
uszeregowania barrier. Po prostu uważam, że w sprytny sposób unikany
jest problem, który nie istnieje.

>
>>> 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 barrierze są widoczne przed zmianami wykonanymi przed
>> barrierą.
>
> Inny punkt widzenia jest taki, że drugi wątek może czytać w innej
> kolejności, skoro nie ma pomiędzy tymi punktami synchronizacji.

Nie wolno mu czytać danych, które są dopiero inicjalizowane w once() do
jego zakończenia - to by było UB. Skoro czyta nową wartość *once, które
było modyfikowane PO barrierze to w dowolnej sensownej implementacji (to
było założenie poprawności mojego algorytmu) dane zostaną commitnięte.

>
> I nie, Intel tego nie zabrania, bo kompilator może inaczej
> szeregować operacje, jeżeli tak mu wygodnie podczas optymalizacji.

Kompilator też zna coś takiego jak barriera - przenośna biblioteka
zgodna z pthreads powinna to używać w funkcjach synchronizujących.

>
>>> 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).

Nie. Użyty jest dostęp przez wskaźnik a nie jeden z konstruktów c++11.
Standard wyraźnie mówi, że:
- równoczesny dostęp i zapis są "confilicting"
- "confliccting" bez synchronizacji z obu stron to UB

>
> Sam fakt że może widzieć starą wartość algorytm uwzględnia i to nie
> jest UB.

Ale UB jest sam odczyt.

> 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.

No i w moim też tak jest - najpierw jest niejawna barriera a dopiero
potem atomic - jeżeli atomic jest widoczny to stan z przed barriery też.

>
> 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.

Jak czytałeś algorytmy stosowane w bazach danych to jest.
Poza tym algorytm opiera się na założeniu, że odczyt konfliktujący z
zapisem jest ok. A ty twierdzisz, że odczyt po barrierze nie gwarantuje
spójności danych przed barrierą jeżeli barriera nie była wołana w obu
wątkach. Czemu jedno założenie ma być lepsze od innego?

--
Pozdrawiam
Michoo