-
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
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- 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
Najnowsze wątki
- 2025-01-13 Kraków => UX Designer <=
- 2025-01-13 Katowice => Key Account Manager (ERP) <=
- 2025-01-13 Mińsk Mazowiecki => Spedytor Międzynarodowy <=
- 2025-01-12 USB3.x->HDMI/DP ze sterownikami w win11
- 2025-01-12 Jak na naszych oczach odradza się cenzura :-)
- 2025-01-11 Koszty prowadzenia firmy za granicą
- 2025-01-11 19 migrantów
- 2025-01-11 300km/h
- 2025-01-11 Kongres USA uchwalił "Prawo babci Pawlakowej" na MTK [Lex Gradma Pawlak]
- 2025-01-11 Riga => Specjalista ds. public relations <=
- 2025-01-11 Przestępca wyborczy Musk nadciąga nad Tuskistan?
- 2025-01-11 Białystok => Delphi Programmer <=
- 2025-01-09 Jaka nawigacja z asystentem zmiany pasa ruchu?
- 2025-01-10 Coś dusi.
- 2025-01-09 akumulator napięcie 12.0v