🚀 go-pugleaf

On Monday, May 2, 2016 at 2:49:05 PM UTC+2, Matt D. wrote:
> On 5/1/2016 10:35 AM, Borneq wrote:
> > Czy kolejka std::queue jest bezpieczna wątkowo?
> 
> Nie zabezpieczona -- nie do zapisu:
> http://stackoverflow.com/questions/21302142/is-stdqueue-thread-safe-with-producer-and-multiple-consumers
> http://stackoverflow.com/questions/1164023/is-there-a-production-ready-lock-free-queue-or-hash-implementation-in-c
> 
> W starszych zrodlach mozesz znalezc porady, aby problem "rozwiazac" 
> zabezpieczajac dany kontener, n.p., mutexem.
> Dzisiaj jednak nie radze siegac do zabezpieczania calych kontenerow 
> mutexami -- to zabije wydajnosc i skalowalnosc (przy wzrastajacej ilosci 
> cores wydajnosc moze zaczac spadac, zamiast rosnac). Moze byc lepiej 
> uzyc lock-free -- patrz nizej.

To wszystko racja, jednak nie przesadzajmy też w drugą ze stron. Ja
używam wielokrotnie kolejek w programach, jakbym wykonywał na nich
100 razy więcej operacji niż wykonuję, to program by nie zwolnił.
Wniosek z tego taki, że najprostsze rozwiązanie, czyli właśnie 
zabezpieczenie mutexem, będzie najlepsze. Implementacja struktur
lock-less, wait-less jest bardzo trudna i jeśli można, to trzeba
używać starych dobrych rozwiązań. Cytat z materiałów które załączyłeś:

[
Fortunately, you can force certain ordering guarantees all the way down to the CPU level using memory barriers. Unfortunately, they are extremely tricky to use properly. In fact, a major problem with lock-free code is that it's prone to bugs that can only be reproduced by specific non-deterministic interleavings of thread operations. This means a lock-free algorithm with a bug may work 95% of the time and only fail the other 5%. Or it may work all of the time on a developer's CPU, but fail occasionally on another CPU.
]


> 
> // Inny przyklad jak, IMHO, tego lepiej nie robic -- 
> https://software.intel.com/en-us/articles/single-producer-single-consumer-queue 
> -- `volatile` to tutaj za malo / nie daje zadnych gwarancji 
> wielowatkowych; memory barrier to tutaj za duzo -- czesto wystarczy para 
> jednostronnych transakcji atomicznych (acquire-release).
Bym powiedział dosadniej, volatile to nie tylko za mało, ale to wręcz nic, a
w dodatku różne kompilatory różnie się z tym obchodziły i być może nadal
różnie obchodzą.


> 
> > Jak napisać pod Linuxem dwie klasy, z których jedna w wątku (lub
> > głównym) będzie zapisywała do kolejki a druga w wątku odczytywała?
> 
> Jesli chcesz jeden producent i jeden konsument, to szukasz 
> single-producer, single-consumer (SPSC) lock-free queue (ringbuffer).
> 
> Jesli wiecej niz jeden, to multi-, n.p., MPMC -- ale nie uzywaj jesli 
> nie potrzebujesz, dla prostszego wariantu SPSC mozna zagwarantowac 
> wait-free, znacznie silniejsza gwarancja od lock-free.
> Terminologia: 
> http://www.boost.org/doc/libs/master/doc/html/lockfree.html#lockfree.introduction___motivation.introduction__amp__terminology
> 
> Tutaj jest porzadny przyklad:
> https://github.com/cameron314/readerwriterqueue
> opis: http://moodycamel.com/blog/2013/a-fast-lock-free-queue-for-c++
> 
> Zobacz tez:
> http://kukuruku.co/hub/cpp/lock-free-data-structures-exploring-queues
> 
> Boost.Lockfree -- boost::lockfree::spsc_queue
> http://boost.org/libs/lockfree
> 
> CDS: Concurrent Data Structures library
> https://github.com/khizmax/libcds
> W szczegolnosci:
> http://libcds.sourceforge.net/doc/cds-api/namespacecds_1_1container.html
> 
> Ogolne wprowadzenie do programowania lock-free:
> http://preshing.com/20120612/an-introduction-to-lock-free-programming/
> 

W sumie trochę podziwiam autorów, za takie implementacje :)

Pozdrawiam