Efficient C++ Bounded Thread-Safe FIFO Queue and LIFO Stack for real-time systems version 1.08

[rami18]

Hello..


Efficient C++ Bounded Thread-Safe FIFO Queue and LIFO Stack for
real-time systems version 1.08

Now the Thread-Safe LIFO Stack that is LIFO fair and starvation-free is
working correctly.

Author: Amine Moulay Ramdane

Description:

Efficient C++ Bounded Thread-Safe FIFO Queue and LIFO Stack for
real-time systems, they are efficient and they eliminate false-sharing
and the Thread-Safe FIFO Queue is FIFO fair and starvation-free, and
the Thread-Safe LIFO Stack is LIFO fair and starvation-free.


You can download it from:

https://sites.google.com/site/aminer68/efficient-c-bounded-thread-safe-fifo-queue-and-lifo-stack-for-real-time-systems


Thank you,
Amine Moulay Ramdane.

[Mr Flibble]

As usual the code you post here is egregious. You do realize that you
cacheline "padding" isn't padding at all because you aren't using unions
or C++11 alignment features so every time you put a scalar member
variable in-between the "pads" you offset subsequent "pads"? Also it is
beneficial to put multiple variables WITHIN the same cacheline which is
the opposite of what you are doing with your "padding"?

union { int i; char padding[CACHE_LINE_SIZE]; } i;
int this_one_is_aligned[56];

Try harder mate.

/Flibble

[rami18]

I don't think you are correct, because i am using the same cacheline
padding as here:

http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue


This guy called Dmitry Vyukov that wrote this is a an expert.

[Mr Flibble]

If what you are trying to do is eliminate false sharing then your code
is still incorrect as you are still needlessly offsetting subsequent
pads; you need to use a union or a C++11 aligned storage. This is what
you want:

template<typename T>
struct cache_line_storage {
alignas(CACHE_LINE_SIZE) T data;
char pad[CACHE_LINE_SIZE > sizeof(T)
? CACHE_LINE_SIZE - sizeof(T)
: 1];
};

/Flibble

[rami18]

What you are trying to do Fibble is optimizing the memory, my way
of doing as i have explained is working correctly for false-sharing,
your way is an optimization of memory, but it is good to optimize for
memory for very tight constrains on memory on real-time systems..

[Chris M. Thomasson]

Strange padding stuff aside, the code does not make sense to me. He is
using Pthread emulation, locks mutexs, and waits on semaphores. How can
this even be remotely starvation free unless the underlying primitives
provide those guarantees? Also, he has this sequential consistency
membar in there, that does not make sense.

He also has this strange:

while (count()>=size)
{sched_yield();}

WTF is that shit!

[Chris M. Thomasson]

Personally, I would want the head and tail to be aligned and padded on
different cache lines, but you funnel all through individual mutexes for
head and tail. This means that the mutex state for the head and tail
needs to be accounted for as well. Padding is one aspect, proper
alignment is another. Without both, well, you basically have nothing.
Take a look at:

http://en.cppreference.com/w/cpp/memory/c/aligned_alloc

http://en.cppreference.com/w/cpp/types/aligned_storage

http://en.cppreference.com/w/cpp/language/alignas

Also, how can you claim starvation-free when you use pthread mutexs and
semaphores? Then you throw in a C++11 seq_cst membar, and do a strange
spin wait using sched_yield, it seems to be waiting for a "full"
condition. What is that all about?

[rami18]

You are asking for me to do padding and alignement, but i don't
think you are correct, because why Dmitry Vyukov is using only
padding on the following:

http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue


This guy called Dmitry Vyukov that wrote this is a an expert.

>Also, how can you claim starvation-free when you use pthread mutexs and
> semaphores?

Because i think Mutex and Semaphore of pthread for VxWorks real-time
system and for QNX real-time system are real-time and starvation-free.

[Chris M. Thomasson]

His padding does not mean correct alignment. For instance, I want head
and tail to start on actual cache line boundaries. Dmitry's example code
does not do that. Keep in mind that its example code, not really meant
for production. Btw, I know Dmitry.

> This guy called Dmitry Vyukov that wrote this is a an expert.
>
> >Also, how can you claim starvation-free when you use pthread mutexs and
> > semaphores?
>
>
> Because i think Mutex and Semaphore of pthread for VxWorks real-time
> system and for QNX real-time system are real-time and starvation-free.

VxWorks has absolutely nothing to do with it. Afaict, you seem to have
copied binaries from a PThread emulation lib:

https://sourceware.org/pthreads-win32/index.html

You should mention the license it has in copying.lib? ;^/

[rami18]

I have just included the copying.lib file inside the zip.