On 01.07.2013 13:02, Edek wrote:
> Dnia pamiętnego Mon, 01 Jul 2013 12:05:05 +0200, Michoo wyjmując peta
> oznajmił:
>
>> On 01.07.2013 01:47, Edek wrote:
>
>>> Do zagłodzenia może dojść.
>>
>> Jest jeszcze gorzej - nie ma warunku postępu.
>
> To nie jest gorzej. Możliwy deadlock/starvation zawsze kiedyś się zdarzą,
> tego typu live-lock nawet jeżeli się zdarzy, to tymczasowo.

live-lock to starvation na dostępie do sekcji krytycznej.

Spotykałem kilkakrotnie z softem który przestawał działać po
przeniesieniu na dwa rdzenie i tak jak deadlock od razu widać bo "staje"
tak live-lock ma w praktyce ciekawsze objawy - np strasznie powolna
praca z obciążeniem dwóch rdzeniu (pozornie bez powodu, strace pokazuje
ciągłe try_lock) albo występujące raz na jakiś czas zacięcie. Ciężko to
nazwać "działaniem" gdy procesy 90% czasu walczą o dostęp do sekcji
krytycznej.

>>
>> Nie zrozumiałem. Skoro kolejką emulujemy listę oczekujących na muteksie
>> to oczywistym jest, że ona musi być współdzielona.
>
> Na którym mutexie miałaby być lista wszystkich sąsiadów?
> Nie da się
> podzielić grafu w ten sposób.

Nieistotne - cała ta dyskusja zaczęła się od "gdyby implementacja nie
zapewniała", znane mi zapewniają - można zobaczyć kod źródłowy choćby z
pthreads.

>
>>> Wiele algorytmów "wątkowych" nie ma ani standardu ani nazwy.
>>
>> Istnieją pewne "wzorce" czy "idiomy". Nie znałem takiego. Jak widać
>> wystarczyła drobna wariacja tego co przedstawiłem.
>
> W algorytmach wątkowych najczęściej nie ma czegoś takiego jak
> drobna wariacja. W zasadzie każda zmiana, nawet drobna, wymaga
> dowodu od początku.

Chyba nie przeczytałeś tego co pisałem ani pracy linkowanej przez A.L.

To jest drobna wariacja, bo udowadniasz najpierw to rozwiązanie
przedstawione przeze mnie a następnie dowodzisz jedynie, że po uzyskaniu
kompletu blokad pozostawienie jedynie blokady odpowiadającej
identyfikatorowi danego procesu nie narusza ograniczeń a zwiększa
stopień równoległości.

Dowód jest trywialny:

skoro:
1. rozwiązanie 1 zapewnia zarówno bezpieczeństwo jak i postęp (co
dowiedziono wcześniej)
2. procesy które bezpośrednio konfliktują zawierają się nawzajem na
swoich listach
3. wszystkie procesy konfliktujące ze sobą przed wejściem do sekcji
krytycznej muszą uzyskać _wszystkie_ muteksy z listy
4. muteksy pobierane są w kolejności, nie jest możliwe pobranie muteksu
i+1 przed pobraniem muteksu i

to:
- na podstawie 3. widzimy, że po wejściu do sekcji krytycznej posiadanie
przez proces Xi jedynie po jednym muteksie z list wszystkich procesów z
którymi konfliktuje nadal zapewnia bezpieczeństwo
- na podstawie 2. widzimy, że jeżeli proces Pi konfliktuje z procesem Pj
to proces Pj zawiera na swojej liście muteks Mi

Tak więc po wejściu do sekcji krytycznej jeżeli proces Pi zwolni
wszystkie muteksy poza Mi to bezpieczeństwo jest nadal zachowane.

Postęp jest zapewniany przez uszeregowanie (co dowiedzione jest w
dowodzie algorytmu podstawowego) - nie naruszamy go w żaden sposób.

Ponieważ zapewniony jest zarówno postęp jak i bezpieczeństwo to algorytm
jest poprawny.


>
> Część ludzi twierdzi, że algorytm działa po "drobnej zmianie",
> gdy _fast_pthread_once_per_thread_epoch jest nie monotonicznie
> rosnąca ale flagą - a łatwo udowodnić, że wtedy całość się rozsypie.
>

Tak, implementacja w której polega się na monotoniczności się sypie gdy
jej nie ma, kto twierdzi inaczej?

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?

> Każda zmiana wymaga dowodu od początku.

Nieprawda. Każda zmiana wymaga dowodu od miejsca gdzie zostaje wprowadzona.

>
> Zazwyczaj w takich sytuacjach używa się:
> a = try_get()
> if (a == null) {
> zwolnij_wszystkie_locki
> a = get();
> od początku ustawiamy się w kolejce do locków
> }

try_get to nie jest rozwiązanie lock_free[*].

lock free oznacza, że nie występuje sytuacja w której wykonanie jednego
wątku jest blokowane przez inny - wątki pracują cały czas (aktywne
oczekiwanie) a w każdej rundzie dokładnie jednemu się powodzi.


[*] "Pod spodem" jest bo w ogóle futex jest implementowany na pierwszym
poziomie jako atomowa flaga, ale semantycznie jest to klasyczny mutex.


> Dlatego, że try_get zamyka jeden lock jako ostatni, na krótko,
> bez wait(),

Ale wcześniejsze zamki masz z wait, to gdzie tu lock-free?

> a jeżeli ma być wait() to już trzeba wszystko zwolnić
> bo wait() zalicza się w myśleniu o deadlockach do locków.

lock() zawiera w środku niejawne wait() - to nie jest wg mnie
rozwiązanie lock-free.


--
Pozdrawiam
Michoo

do góry

On 01.07.2013 14:14, Edek wrote:
> Dużo odpowiedzi na jeden post wychodzi, ale trudno.
>
> Dnia pamiętnego Mon, 01 Jul 2013 12:05:05 +0200, Michoo wyjmując peta
> oznajmił:
>
>> Jeżeli
>> masz problem producenci-konsumenci to daje się go rozwiązać lock-free.
>
> Pod względem /poprawności/ kolejki lock-free niczym się nie różnią od
> blokujących kolejek.

Tak, jeżeli nie ma sekcji krytycznych to algorytm równoległy jest
poprawny. Tylko to jest niekonstruktywne.

> Istnieją tylko w celu /wydajności/, operacje na nich
> są zarówno bardzo częste jak i krótkotrwałe, więc nie warto tracić
> czasu na usypianie wątku i budzenie, lepszy jest spin w momencie
> kolizji.

Nie zgadzam się. Przez poleganie na operacjach atomowych a nie blokadach
powodują zupełnie inne projektowanie algorytmów i tak jak "widoczny
efekt" to większa wydajność tak pod spodem struktura programu jest
często zupełnie inna.

> lock
> do_single_memory_op
> unlock

Co więcej właśnie tak je realizuje sprzęt. Nawet może dałbym się
przekonać, że tak działający algorytm jest prawie_lock_free.

--
Pozdrawiam
Michoo

do góry

On 01.07.2013 13:54, Edek wrote:
> Dnia pamiętnego Mon, 01 Jul 2013 12:05:05 +0200, Michoo wyjmując peta
> oznajmił:

>>
>> 3 producentów na 2 procesorach plus konsument wymagający po 500
>> jednostek na cykl pracy. Optymalnie ze względu na przepustowość będzie
>> generowanie po 500 jednostek (opóźnienie 1000, ale brak strat na
>> przełączanie). Optymalnie ze względu na czas odpowiedzi będzie dążenie
>> do opóźnienia 750 - jeżeli konsument czeka dłużej to znaczy, ze jest
>> głodzony.
>
> Nie znałem takiej definicji.

Nazewnictwo się może różnić. Najogólniej można mówić o deadline.

> Jak się to sprawdza albo dowodzi? Naprawdę
> pytam bo nie wiem.

Słowa kluczowe: szeregowanie zadań, systemy rt.

Niektóre rzeczy są robione probabilistycznie inne w oparciu o silne
założenia - nie czuję się w mocy streścić kilku przedmiotów w poście na
grupach.

--
Pozdrawiam
Michoo

do góry

Część teraz...

Dnia pamiętnego Mon, 01 Jul 2013 18:24:17 +0200, Michoo wyjmując peta
oznajmił:

> On 01.07.2013 13:02, Edek wrote:
>> Dnia pamiętnego Mon, 01 Jul 2013 12:05:05 +0200, Michoo wyjmując peta
>> oznajmił:

>> Część ludzi twierdzi, że algorytm działa po "drobnej zmianie",
>> gdy _fast_pthread_once_per_thread_epoch jest nie monotonicznie
>> rosnąca ale flagą - a łatwo udowodnić, że wtedy całość się rozsypie.

> Tak, implementacja w której polega się na monotoniczności się sypie gdy
> jej nie ma, kto twierdzi inaczej?

Znajdzie się, między innymi na listach llvma.

> 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. Ja potrafię to drugie.

>> Każda zmiana wymaga dowodu od początku.
>
> Nieprawda. Każda zmiana wymaga dowodu od miejsca gdzie zostaje wprowadzona.

Widzę dwie opcje: albo udowadnia się, że zmiana nie narusza pozostałych
twierdzeń, albo robi się dowód od początku. Czasami łatwiej jest
zacząć od zera.

>> Zazwyczaj w takich sytuacjach używa się:
>> a = try_get()
>> if (a == null) {
>> zwolnij_wszystkie_locki
>> a = get();
>> od początku ustawiamy się w kolejce do locków
>> }
>
> try_get to nie jest rozwiązanie lock_free[*].

Spróbuj zapomnieć na chwilę o sprzęcie. try_get nie jest lock-free?
A co robi kolejka lock-free, gdy nie ma w niej żadnego elementu?
Są dwie opcje: przy get() robi spina aż się pojawi element,
try_get() zwraca null. Dokładnie tak jak w blokującej kolejce,
kwestia nazewnictwa metod co najwyżej.

> lock free oznacza, że nie występuje sytuacja w której wykonanie jednego
> wątku jest blokowane przez inny - wątki pracują cały czas (aktywne
> oczekiwanie) a w każdej rundzie dokładnie jednemu się powodzi.

Try_get blokującej nie jest lock-free, ale efekt jest taki sam:
albo żaden nic nie dostanie jak kolejka jest pusta, albo jeden
z nich na raz pobierze element.

> [*] "Pod spodem" jest bo w ogóle futex jest implementowany na pierwszym
> poziomie jako atomowa flaga, ale semantycznie jest to klasyczny mutex.

Wiem, ale łatwiej jest operować na dostarczanej abstrakcji, albo
przynajmniej nie mieszać sprzętu do logiki poprawności.

>> Dlatego, że try_get zamyka jeden lock jako ostatni, na krótko,
>> bez wait(),
>
> Ale wcześniejsze zamki masz z wait, to gdzie tu lock-free?

Nie ma znaczenia czy jest lock-free czy nie. Mówiłem o przykładzie
komunikacji pomiędzy wątkami, które już są uwikłane we własny
algorytm i trzeba dodać komunikację nie naruszając samego
algorytmu. Mieszasz sprzęt do logiki.

I o co ci chodzi z tym lock-free? Wiele rzeczy działa
tak samo czy są lock-free czy nie, tylko szybciej.

>> a jeżeli ma być wait() to już trzeba wszystko zwolnić
>> bo wait() zalicza się w myśleniu o deadlockach do locków.
>
> lock() zawiera w środku niejawne wait() - to nie jest wg mnie
> rozwiązanie lock-free.

Nie, lock() nie zawiera wait(). Wait() zwalnia lock, lock()
go zamyka. Jasne że nie jest lock-free, ale nie w tym rzecz,
lock() ma inną semantykę niż wait(). Szczegóły implementacyjne
nic tu nie zmieniają, liczy się efekt.

--
Edek

do góry

Dnia pamiętnego Mon, 01 Jul 2013 18:36:39 +0200, Michoo wyjmując peta
oznajmił:

> On 01.07.2013 13:54, Edek wrote:
>> Dnia pamiętnego Mon, 01 Jul 2013 12:05:05 +0200, Michoo wyjmując peta
>> oznajmił:

>> Jak się to sprawdza albo dowodzi? Naprawdę
>> pytam bo nie wiem.
>
> Słowa kluczowe: szeregowanie zadań, systemy rt.
>
> Niektóre rzeczy są robione probabilistycznie inne w oparciu o silne
> założenia - nie czuję się w mocy streścić kilku przedmiotów w poście na
> grupach.

Ok, ja większość z tych rzeczy znam, powiedziałbym że zgodnie ze
zdrowym rozsądkiem. Myślałem że istnieją może jakieś specyficzne
definicje dedykowane tylko do starvation.

--
Edek

do góry

Dnia pamiętnego Mon, 01 Jul 2013 18:24:17 +0200, Michoo wyjmując peta
oznajmił:
> On 01.07.2013 13:02, Edek wrote:
>> Dnia pamiętnego Mon, 01 Jul 2013 12:05:05 +0200, Michoo wyjmując peta
>> oznajmił:
>>> On 01.07.2013 01:47, Edek wrote:
>>
>>>> Do zagłodzenia może dojść.
>>>
>>> Jest jeszcze gorzej - nie ma warunku postępu.
>>
>> To nie jest gorzej. Możliwy deadlock/starvation zawsze kiedyś się zdarzą,
>> tego typu live-lock nawet jeżeli się zdarzy, to tymczasowo.
>
> live-lock to starvation na dostępie do sekcji krytycznej.

Mógłbyś nie używać określenia sekcja krytyczna mając na myśli mutual
exclusion w mojej obecności? Byłbym dozgonnie wdzięczny ;), bo
przy dwóch lockach ja nie bardzo wiem jak to podzielić:

lock(a) {
... sekcja krytyczna ...
lock (b) {
... sekcja nadkrytyczna?? ...
}
.... sekcja wciąż krytyczna ...
}

Live-lock to nic więcej jak wielokrotne próby wielu wątków,
z których żadnemu się nie udaje przez dłuższy czas. Ludzie sobie
z tym radzą nawet w transactional memory, gdzie tego typu
kolizje są znacznie częstsze bo struktury i transakcje dużo większe,
wymyślono odpowiednie "policies" pierwszeństwa.

> Spotykałem kilkakrotnie z softem który przestawał działać po
> przeniesieniu na dwa rdzenie i tak jak deadlock od razu widać bo "staje"
> tak live-lock ma w praktyce ciekawsze objawy - np strasznie powolna
> praca z obciążeniem dwóch rdzeniu (pozornie bez powodu, strace pokazuje
> ciągłe try_lock) albo występujące raz na jakiś czas zacięcie. Ciężko to
> nazwać "działaniem" gdy procesy 90% czasu walczą o dostęp do sekcji
> krytycznej.

Ja też różne rzeczy spotykałem i widziałem, ale ten konkretnie algorytm
jest jak najbardziej ok. To że widziałeś takie starvation to jeszcze nie
znaczy, że każdy algorytm który teoretycznie nie ma warunku postępu
probabilistycznie też nie ma. Zerknij do boosta - tam chwilowy livelock
jest obsługiwany podobnie jak wielokrotna kolizja w lock-free, mały
backoff a jak nie pomoże to yield.

--
Edek

do góry

On 01.07.2013 19:08, Edek wrote:
> Część teraz...
>
> 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
- 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?

> Ja potrafię to drugie.
>
Poproszę.

--
Pozdrawiam
Michoo

do góry

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

do góry

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?

>>
>> Pisane na szybko więc co przeoczyłem?
>
> Model pamięci C++11?

pthreads z nie_pojebaną_architekturą (tm)


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

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

[*] 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.

> 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ęć


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

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


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

--
Pozdrawiam
Michoo

do góry

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

do góry