🚀 go-pugleaf

> Czy kolejka std::queue jest bezpieczna wątkowo?

Tak, jak wszystko. Czyli jeden wątek używa jednej kolejki, a drugi innej. :-)

> 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?

To jest ta łatwiejsza połowa problemu. Druga połowa to czekanie na wolne miejsce lub na dostępne dane.

Ogólnie:

https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem

-- 
Maciej Sobczak * http://www.inspirel.com

On Sunday, May 1, 2016 at 10:35:58 AM UTC+2, Borneq wrote:
> Czy kolejka std::queue jest bezpieczna wątkowo?
> 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?

http://doc.qt.io/qt-4.8/qt-threads-semaphores-example.html
Pozdrawiam

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.

// 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).

> 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/

Pozdrawiam,

Matt

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