-
Data: 2013-07-01 01:47:19
Temat: Re: pytanie z mutexów
Od: Edek <e...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 01.07.13 02:31 A.L.
- 01.07.13 11:32 Michoo
- 01.07.13 12:05 Michoo
- 01.07.13 13:02 Edek
- 01.07.13 13:54 Edek
- 01.07.13 14:14 Edek
- 01.07.13 15:10 Edek
- 01.07.13 15:53 A.L.
- 01.07.13 18:24 Michoo
- 01.07.13 18:30 Michoo
- 01.07.13 18:36 Michoo
- 01.07.13 19:08 Edek
- 01.07.13 21:47 Edek
- 01.07.13 22:01 Edek
- 02.07.13 18:16 Michoo
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-06-27 Re: Prywatny parking? Pierwsze 10 minut bezplatnie
- 2024-06-27 A co mnie to koooorwa obchodzi?
- 2024-06-28 nawigacja satelitarna
- 2024-06-28 SmartLife/Tuya i osuszanie -- mordowanie z zimną krwią...
- 2024-06-27 położyłem kafelki
- 2024-06-28 Łódź => International Freight Forwarder <=
- 2024-06-28 Łódź => Spedytor Międzynarodowy <=
- 2024-06-28 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-06-28 Sopot => Team Leader E-Commerce for Foreign Markets <=
- 2024-06-28 Warszawa => Senior React Native Developer <=
- 2024-06-28 Warszawa => Frontend Developer (React) <=
- 2024-06-28 Warszawa => Software .Net Developer <=
- 2024-06-28 Warszawa => Frontend Developer (React) <=
- 2024-06-28 Warszawa => Programista Full Stack .Net <=
- 2024-06-28 Warszawa => Frontend Developer (React) <=