Dnia pamiętnego Mon, 01 Jul 2013 00:26:42 +0200, Michoo wyjmując peta
oznajmił:

> On 28.06.2013 22:12, A.L. wrote:
>> On Fri, 28 Jun 2013 15:36:11 +0200, Michoo<m...@v...pl> wrote:
>
>>>> P.S. Zadam to samo zadanko co kiedys: procesy a, b, c, d, e, f
>>>>
>>>> Wzajemne wykluczanie: (a,c), (c,f), (a,b), (b,e), (b,d), (c,d), (e,f)
>>>>
>>>> Zaprojeltowac rozwiazanie bez deadlocku i starvation free
>>>
>>> Ale już Ci na nie odpowiadałem:
>>> - tworzysz 6 muteksów (A-F)
>>> - sporządzasz dla każdego procesu listę z którymi się wyklucza
>>> - 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().

Algorytm bombarduje szynę atomikami, ale jest poprawny.

Do zagłodzenia może dojść.

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

>>> [*] 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 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ę. O ile czegoś na szybko nie pomyliłem, wychodzi
graf pierwszeństwa, który można potraktować w sposób uproszczony,
byle spraweidliwy.

>> 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. Część
ma, czasami nawet patent jak dzielone shared_ptr-y.

> Kwestie zagłodzenia w takim wypadku trzeba rozwiązywać osobno już
> zależnie od tego co rozumiemy przez "zagłodzenie"[*] i jakie są schematy
> współpracy między wątkami.

Wydaje mi się już pisałeś, na czym może polegać zagłodzenie w
prostym przypadku, w bardziej skomplikowanych konfiguracjach
jedne grupy wątków mogą głodzić inne.

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.

> Być może statyczny przydział, być może wstrzymywanie procesów które
> wybijają się poza zakładany histogram - za mało danych aby odpowiedzieć.

Być może FIFO procesów i ten bliżej wyjścia ma pierwszeństwo. Kombinuję,
ale ja jakoś nie widzę w tym problemie poważnego problemu.

> [*] Czy mamy ograniczenia typu "minimum 1 wywołanie na k jednostek
> czasu", czy raczej "od a1 do a2 % czasu wykonania w k jednostkach", czy
> też kombinację z ewentualnymi dodatkowymi warunkami. Ogólnie wchodzimy
> opuszczamy już tutaj problem synchronizacji a wchodzimy w sferę
> szeregowania zadań.

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

--
Edek