Dnia pamiętnego Mon, 01 Jul 2013 12:05:05 +0200, Michoo wyjmując peta
oznajmił:

> On 01.07.2013 01:47, Edek wrote:

>> mając do zamknięcia n,m,l,... zamyka się n, a potem try_lockiem
>> pozostałe. Jeżeli któryś się nie zamknie, bo zajęty, zwalnia się już
>> zamknięte i ten który był zajęty jest pierwszy do kolejnej rundy -
>> przez co proces czeka na tym locku aż się zwolni, bo pierwszy jest lock().
>
> W takiej sytuacji możesz mieć live-lock - wystarczą już dwa procesy
> "wymieniające się" dwoma blokadami.

Praktycznie ten algorytm w implementacji boost-a ma jeszcze kilka
yieldów.

>> 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. Konsekwencje
live-locka w tym konkretnym przypadku są praktycznie wyłącznie teoretyczne.

>>>>> Każdy proces wchodząc do sekcji krytycznej pobiera potrzebne mu blokady
>>>>> w kolejności A-F. Rozwiązuje to problem wzajemnego wykluczania([*]).
>>>>> Problem zagłodzenia nie wystąpi na pewno gdy muteksy budzą w kolejności
>>>>> FIFO, przy braku tej gwarancji do zagłodzenia może dojść[**] więc
>>>>> najlepiej chyba ją zapewnić przez kombinację mutex+lista+condition
>>>>> variable (dopóki !pierwszy na liście).
>>
>> Nope. Trzeba jeszcze dopisać się do list dzielonych z pozostałymi
>> procesami, inaczej one też mogą zagłodzić/być zagłodzone, np.
>> mapa list z maską jako kluczem...
>
> 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.

>>>>> [*] Czyim imieniem nazywamy ten algorytm - nie pamiętam. Jest to daleka
>>>>> wariacja Lamporta.
>>>>> [**] Choćby a i b "wymieniające się" muteksem A mogą zagłodzić c.
>>
>> ... a wtedy a i b dopiszą się do kolejki z c i c będzie pierwsze.
>
> Nie rozumiem.

W tej pracy linkowanej przez A.L. w referencjach jest edge-based solution,
wspomniana jest we wstępie. Jeszcze nie czytałem, a sam mogłem coś pokręcić
(biorąc pod uwagę fakt że moje 10 minut < publikacja - nic dziwnego ;) ).

>> Nie przemyślałem tylko jak to zaimplementować, bo trzeba jeszcze chronić
>> same kolejki o ile nie ma kolejek lock-free z peek() i mieć jakąś
>> politykę reagowania na a przed b na jednej liście a b przed a na drugiej
>> - random() dałby radę.
>
> Używasz parę blokad:
> lock(Xa);
> dodaj_na_koniec_kolejki(procId,a);
> unlock(Xa);
>
> do{
> cond_wait(Ya);
> }while(head(a)!=procId);
> do_stuff();
> lock(Xa);
> usun_zpoczatku_kolejki(a);
> unlock(Xa);
> unlock(Ya);

Nie zrozumiałem. Gdzie jest lock(Ya)? Co robi do_stuff()? I gdzie to pasuje
do całości?

>> 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. Przykład:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2
008/n2660.htm#AppendixSource

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.

Każda zmiana wymaga dowodu od początku.

>> Schematy współpracy: skoro się wykluczają mogą w ramach wykluczenia
>> przekazywać dane. Albo mogą mieć kolejki, które są liśćmi w drzewie
>> kolejności locków, więc są pomijalne dla poprawności.
>
> Mogą. Właśnie od "mogą" zależy bardzo dużo jeżeli chodzi o wątki. Jeżeli
> masz problem producenci-konsumenci to daje się go rozwiązać lock-free.

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
}

To nie wymaga ani zmiany głównego algorytumu ani kolejek lock-free.
Dlatego, że try_get zamyka jeden lock jako ostatni, na krótko,
bez wait(), a jeżeli ma być wait() to już trzeba wszystko zwolnić
bo wait() zalicza się w myśleniu o deadlockach do locków.

--
Edek