On 01.07.2013 01:47, Edek wrote:
>>>> - sortujesz te listy w kolejności a-f
>
> Nawet nie trzeba sortować. Try_lock załatwia problem dealocku, tak:
>
> 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.

> Do zagłodzenia może dojść.

Jest jeszcze gorzej - nie ma warunku postępu.

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

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

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

>
>>> Niezupelnie o to chodzi, bo wejscie w proces a powinno blokowac
>>> procesy b i c ale nie powinno blokowac procesow d, e, f
>>
>> Nie znam (a przynajmniej nie przypominam sobie) innego "standardowego"
>> algorytmu rozwiązującego ten problem w sposób przejrzysty a jednocześnie
>> optymalny pod względem wydajnościowym.
>
> 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.

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

> Tak jakby z zagłodzeniem było kiedykolwiek inaczej. Problem polega
> na tym, że problem jest jeden i algorytm jest jeden, ale musi
> spełniać oba warunki: działać, czyli być bez race'ów i deadlocków, i ma
> nie zagłodzić.

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.

--
Pozdrawiam
Michoo