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