-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!.POSTED!not-for-mail
From: Edek <e...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: pytanie z mutexów
Date: Mon, 1 Jul 2013 17:08:37 +0000 (UTC)
Organization: ATMAN - ATM S.A.
Lines: 92
Message-ID: <kqsd2l$fgq$5@node2.news.atman.pl>
References: <5...@g...com>
<51c56394$0$28103$c3e8da3$91613603@news.astraweb.com>
<f...@4...com>
<kq70gf$ngh$1@mx1.internetia.pl>
<3...@4...com>
<kq7g4r$a05$1@mx1.internetia.pl>
<f...@4...com>
<kqi854$v85$1@mx1.internetia.pl>
<u...@4...com>
<kqk43i$sfo$1@mx1.internetia.pl>
<a...@4...com>
<kqqbud$j5h$1@mx1.internetia.pl> <kqqg26$pa6$8@node2.news.atman.pl>
<kqrkrs$ka6$1@mx1.internetia.pl> <kqrnjk$fgq$1@node2.news.atman.pl>
<kqsb2s$t1t$1@mx1.internetia.pl>
NNTP-Posting-Host: 87-205-33-79.adsl.inetia.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-Trace: node2.news.atman.pl 1372698517 15898 87.205.33.79 (1 Jul 2013 17:08:37 GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Mon, 1 Jul 2013 17:08:37 +0000 (UTC)
User-Agent: Pan/0.139 (Sexual Chocolate; GIT bf56508 git://git.gnome.org/pan2)
Xref: news-archive.icm.edu.pl pl.comp.programming:203935
[ ukryj nagłówki ]Część teraz...
Dnia pamiętnego Mon, 01 Jul 2013 18:24:17 +0200, Michoo wyjmując peta
oznajmił:
> On 01.07.2013 13:02, Edek wrote:
>> Dnia pamiętnego Mon, 01 Jul 2013 12:05:05 +0200, Michoo wyjmując peta
>> oznajmił:
>> Część ludzi twierdzi, że algorytm działa po "drobnej zmianie",
>> gdy _fast_pthread_once_per_thread_epoch jest nie monotonicznie
>> rosnąca ale flagą - a łatwo udowodnić, że wtedy całość się rozsypie.
> Tak, implementacja w której polega się na monotoniczności się sypie gdy
> jej nie ma, kto twierdzi inaczej?
Znajdzie się, między innymi na listach llvma.
> Co do samego algorytmu - potrzebne są trzy stany:
> przed_inicjalizacją, w_trakcie, po_inicjalizacji, nie da się tego zrobić
> na JEDNEJ fladze binarnej, można by użyć dwóch(i wprowadzić odpowiednie
> poprawki), ale po co?
Nie, jest potrzebna monotonicznie rosnąca liczba, nie trzy stany. Mi
to zajęło z pół godziny żeby dojść dlaczego: spróbuj zastąpić
monotonicznie rosnącą stanami i albo udowodnij poprawność
albo udowodnij że jest problem. Ja potrafię to drugie.
>> Każda zmiana wymaga dowodu od początku.
>
> Nieprawda. Każda zmiana wymaga dowodu od miejsca gdzie zostaje wprowadzona.
Widzę dwie opcje: albo udowadnia się, że zmiana nie narusza pozostałych
twierdzeń, albo robi się dowód od początku. Czasami łatwiej jest
zacząć od zera.
>> Zazwyczaj w takich sytuacjach używa się:
>> a = try_get()
>> if (a == null) {
>> zwolnij_wszystkie_locki
>> a = get();
>> od początku ustawiamy się w kolejce do locków
>> }
>
> try_get to nie jest rozwiązanie lock_free[*].
Spróbuj zapomnieć na chwilę o sprzęcie. try_get nie jest lock-free?
A co robi kolejka lock-free, gdy nie ma w niej żadnego elementu?
Są dwie opcje: przy get() robi spina aż się pojawi element,
try_get() zwraca null. Dokładnie tak jak w blokującej kolejce,
kwestia nazewnictwa metod co najwyżej.
> lock free oznacza, że nie występuje sytuacja w której wykonanie jednego
> wątku jest blokowane przez inny - wątki pracują cały czas (aktywne
> oczekiwanie) a w każdej rundzie dokładnie jednemu się powodzi.
Try_get blokującej nie jest lock-free, ale efekt jest taki sam:
albo żaden nic nie dostanie jak kolejka jest pusta, albo jeden
z nich na raz pobierze element.
> [*] "Pod spodem" jest bo w ogóle futex jest implementowany na pierwszym
> poziomie jako atomowa flaga, ale semantycznie jest to klasyczny mutex.
Wiem, ale łatwiej jest operować na dostarczanej abstrakcji, albo
przynajmniej nie mieszać sprzętu do logiki poprawności.
>> Dlatego, że try_get zamyka jeden lock jako ostatni, na krótko,
>> bez wait(),
>
> Ale wcześniejsze zamki masz z wait, to gdzie tu lock-free?
Nie ma znaczenia czy jest lock-free czy nie. Mówiłem o przykładzie
komunikacji pomiędzy wątkami, które już są uwikłane we własny
algorytm i trzeba dodać komunikację nie naruszając samego
algorytmu. Mieszasz sprzęt do logiki.
I o co ci chodzi z tym lock-free? Wiele rzeczy działa
tak samo czy są lock-free czy nie, tylko szybciej.
>> a jeżeli ma być wait() to już trzeba wszystko zwolnić
>> bo wait() zalicza się w myśleniu o deadlockach do locków.
>
> lock() zawiera w środku niejawne wait() - to nie jest wg mnie
> rozwiązanie lock-free.
Nie, lock() nie zawiera wait(). Wait() zwalnia lock, lock()
go zamyka. Jasne że nie jest lock-free, ale nie w tym rzecz,
lock() ma inną semantykę niż wait(). Szczegóły implementacyjne
nic tu nie zmieniają, liczy się efekt.
--
Edek
Następne wpisy z tego wątku
- 01.07.13 21:47 Edek
- 01.07.13 22:01 Edek
- 02.07.13 18:16 Michoo
- 02.07.13 19:56 Edek
- 02.07.13 21:18 Michoo
- 02.07.13 23:06 Edek
- 03.07.13 02:29 Michoo
- 03.07.13 04:08 Edek
- 09.07.13 14:42 firr
- 10.07.13 15:41 firr
Najnowsze wątki z tej grupy
- Alg. kompresji LZW
- 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??
Najnowsze wątki
- 2025-02-17 Kraków => MS Dynamics 365BC/NAV Developer <=
- 2025-02-17 Chrzanów => Programista NodeJS <=
- 2025-02-17 Warszawa => Node.js / Fullstack Developer <=
- 2025-02-17 Białystok => System Architect (Java background) <=
- 2025-02-17 Białystok => Solution Architect (Java background) <=
- 2025-02-17 Gliwice => Team Lead / Tribe Lead FrontEnd <=
- 2025-02-17 Gdańsk => PHP Developer <=
- 2025-02-17 Warszawa => Senior ASP.NET Developer <=
- 2025-02-17 Gliwice => Business Development Manager - Network and Network Security
- 2025-02-17 Mińsk Mazowiecki => Area Sales Manager OZE <=
- 2025-02-17 Odśnieżanie samochodu
- 2025-02-17 Katowice => Regionalny Kierownik Sprzedaży (OZE) <=
- 2025-02-17 Dęblin => JavaScript / Node / Fullstack Developer <=
- 2025-02-17 Pompiarze...
- 2025-02-16 PV teraz