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

Jakbym miał to zrealizować i powyższe rozwiązanie byłoby
niewystarczające zrobił bym to za pomocą monitora z porównaniem maski
aktualnie działających procesów z wymaganą maską jako warunkiem.

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.

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

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

--
Pozdrawiam
Michoo