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