Questions tagged [lock-free]

An umbrella term for methods and algorithms to synchronize multithreaded environments or other forms of distributed system without using locks.

0
votes
1answer
14 views

Lock free non-allocating collection

I am looking for a collection data structure that is: thread safe lock free non-allocating (amortized or pre-allocated is fine) non-intrusive not using exotic intrinsics Element order does not ...
1
vote
0answers
21 views

Why wait-free multi-producer queue in Boost atomic example is wait-free

I have a question about the wait-free multi-producer queue in boost atomic example. I think the 'push' is only lock-free rather than wait-free, because there is a 'compare_exchange_weak loop', then ...
2
votes
1answer
74 views

Lock-free ping-pong in C11

I'm very new to concurrency in C and trying to do some basic staff to understand how it works. I wanted to write a conforming implementation of lock-free ping-pong, i.e. one thread prints ping, ...
1
vote
0answers
50 views

atomic_thread_fence requirement in a sequence lock

I'm writing a simple sequence lock and after reading through the c++ docs on atomics and atomic_thread_fence, it feels like I should need a fence. However, Ive written it without a fence and I have ...
1
vote
0answers
94 views

Creating a lock-free memory pool using C++11 features [migrated]

I have created a thread-safe and lock-free memory pool program using C++11 features. A couple of notable features: g_memStack is a stack that contains the memory unit; we can allocate memory from it. ...
0
votes
1answer
31 views

Can a boost::lockfree::queue be checked for full?

I am using a boost::lockfree::queue Foo(128). Before Popping the queue I can check the queue for empty status by Foo.empty() function. I was wondering if I can check similarly for its status at full ...
1
vote
0answers
35 views

MPMC Queue crashing when inserting dummy node

I am trying to create a lock-free Multi-Producer and Multi-Consumer Queue, however it keeps crashing sometimes when trying to pop out the dummy node. When I was first writing this queue algorithm, I ...
-2
votes
1answer
28 views

Can two boost lockfree queues cause deadlock

My overall design is to have multiple producer threads (>2) to generate results into two atomic<bool> processing_done=false; // when all producers finished // will set to true boost::...
1
vote
1answer
43 views

Is boost::lockfree::queue (in multithreaded program) lockable?

I am working on a program where, 2+ (gstreamer) boost:: threads and same number of boost:: threads of a dummy application are simultaneously using a queue. Now this queue is used for synchronization ...
1
vote
2answers
45 views

Lock-free container with flipping buffers

For one of my projects, which has to support concurrent reads and writes, I need a container that is able to buffer items till a consumer has taken each currently buffered item at once. As producers ...
4
votes
1answer
102 views

At which level does one unit test lock-free code?

Can LLVM, QEMU, GDB, Bochs, OpenStack or the like be used to unit test lock-free concurrent code on an open-source platform? Has anyone achieved this? If you answer by recommending software, I don't ...
2
votes
0answers
41 views

For testing, can one force broken lock-free code to fail? [duplicate]

[I now see that my question is a duplicate. I will vote to close it.] Can one reliably test lock-free code in C++? Is there a known technique? Can one compose a proper unit test? In lock-free-...
-2
votes
1answer
99 views

Lock free single producer/single consumer circular buffer - Can CPU speculation break the memory barrier logic?

I have been looking at a lock free single producer/single consumer circular buffer when I thought about speculative execution and its effect on the simple code. With this implementation, there is ...
3
votes
2answers
158 views

Lock free single producer/single consumer circular buffer

I have been looking at a lock free single producer/single consumer circular buffer on this website when I couldn't figure out why a specific memory barrier was needed. I have carefully read a hundread ...
2
votes
4answers
161 views

Fast and Lock Free Single Writer, Multiple Reader

I've got a single writer which has to increment a variable at a fairly high frequence and also one or more readers who access this variable on a lower frequency. The write is triggered by an external ...
3
votes
1answer
86 views

Is this lock-free dlist insertion is safe?

I need to implement a lock-free insertion of a sub-list in the head of a doubly-linked list. This list has a dummy head, so each thread tries to insert its part right after the head node. This design ...
2
votes
0answers
73 views

Boost lock-free queue is triggering clang's thread sanitizer

I created a lock-free object pool using boost's lock-free queue, version 1.68. While it seems to be working fine, I keep getting these warnings from clang's thread sanitizer in the function pop(). ...
2
votes
3answers
618 views

Regarding shared_ptr reference count block

I had 2 questions regarding the std::shared_ptr control block: (1) Regarding size: How can I programatically find the exact size of the control block for a std::shared_ptr? (2) Regarding logic: ...
0
votes
0answers
62 views

LockFree Queue with Gcc builtins

I am working on developing a single write/reader lock_free queue that is placed on a shared memory which is going to be opened by two different Linux processes. Both processes open the shm with ...
0
votes
1answer
140 views

C++ semaphore (semi *lockfree*), where do I get one?

edit: this is not a duplicate of any question that allows mutex locking in post(). Please read carefully, I need a lockfree post()! Don't mark this duplicate if you don't have a real answer. A ...
0
votes
0answers
126 views

lock free stack: what is the correct use of memory order?

The below class describes a lock free stack of uint32_t sequential values (full code here). For instance, LockFreeIndexStack stack(5); declares a stack containing the numbers {0, 1, 2, 3, 4}. This ...
8
votes
3answers
161 views

Does volatile prevent introduced reads or writes?

In C#, volatile keyword ensures that reads and writes have acquire and release semantics, respectively. However, does it say anything about introduced reads or writes? For instance: volatile Thing ...
2
votes
1answer
38 views

Moving values between lockfree lists

Background I am trying to design and implement lock-free hashmap using chaining method in C++. Each hash table cell is supposed to contain lockfree list. To enable resizing, my data structure is ...
2
votes
2answers
60 views

Parallel lock-free ascending id generation

I have a map which should associate Strings with an id. There must not be gaps between ids and they must be unique Integers from 0 to N. Request always comes with two Strings of which one, both or ...
4
votes
1answer
104 views

Why are CAS not considered equivalent to busy-waiting loops?

Reading a bit about lock free programming in the past few days I came accross the util.java.Random class creating it's bits using the following routine: protected int next(int bits) { long ...
1
vote
1answer
59 views

Can I monitor boost::lockfree::spsc_queue from a third thread?

I have one thread producing data onto a boost::lockfree::spsc_queue, and one thread consuming data. Can I have a third thread monitoring the queue using read_available or write_available? I am not ...
4
votes
4answers
306 views

Copy-free thread-safe Ring Buffer for Big Arrays

For signal processing on big arrays (10^7 elements), I use different threads connected with ring buffers. Sadly, too much time is just needed for copying the data to and out of the buffer. The current ...
7
votes
1answer
207 views

Order-preserving memcpy in C++

I'm developing a multicore, multithreaded software library in which I want to offer update-order preserving lock-free shared memory objects that might span multiple cache lines. Specifically, ...
1
vote
2answers
381 views

Multiple Producer Multiple Consumer Lockfree Non Blocking Ring Buffer With Variable Length Write

I want to pass variable-length messages from multiple producers to multiple consumers, with low latency queue on multi-socket Xeon E5 systems. (400 bytes with a latency of 300 ns would be nice, for ...
2
votes
1answer
323 views

Ring buffer for a wait-free producer and a blocking consumer

I have a producer thread that produces objects at a rate that might (temporarily) be too fast for the consumer thread to consume. Therefore, I'd like a FIFO that buffers the remaining work. Once the ...
2
votes
0answers
114 views

Why is atomic_thread_fence(memory_order_seq_cst) needed in a lock-free queue that already uses seq_cst CAS?

A lock-free queue, only one thread execute push and pop, others execute steal. However, I can't understand why steal() needs std::atomic_thread_fence(std::memory_order_seq_cst). In my opinion, steal(...
1
vote
1answer
32 views

Lock-free Tree Node Assignment in Preallocated Vector of Nodes

I'm currently trying to multithread the creation of a tree where the class which holds the tree preallocates a std::vector of Nodes in a chunk of a particular size (conceptually the size is arbitrary)....
3
votes
1answer
37 views

Can I determine the result of a data race without reading the value?

I'm trying to better understand lock-free programming: Suppose we have two threads in a data race: // Thread 1 x = 1 // Thread 2 x = 2 Is there a lock-free way a third thread can know the result ...
7
votes
1answer
482 views

Are lock-free atomics address-free in practice?

Boost.Interprocess is a wonderful library that simplifies the usage of shared memory amongst different processes. It provides mutexes, condition variables, and semaphores, which allow for ...
3
votes
2answers
131 views

C Lock-Free Queue Memory Management

To improve my C skills, I implemented a thread-safe and lock-free queue. The algorithm is from chapter 10.5 of the book "The Art of Multiprocessor Programming" by Maurice Herlihy and Nir Shavit which ...
2
votes
0answers
72 views

Is this lock-free structure that guards usage of a single resource in Rust correct?

I'm trying to make a structure that can marshal the use of a resource by multiple threads. I believe I have found a correct implementation, but I am still learning about memory orderings and such, so ...
1
vote
2answers
159 views

memory ordering in boost example of lock-free ring buffer

When I read boost atomics about an example wait-free ring buffer implementation: https://www.boost.org/doc/libs/1_66_0/doc/html/atomic/usage_examples.html#boost_atomic.usage_examples....
4
votes
1answer
144 views

Is it safe to use rcu_dereference() inside local_bh_disable()/local_bh_enable()?

The local_bh_disable-function changes per-cpu (in case of x86 and recent kernels) __preempt_count or current_thread_info()->preempt_count otherwise. Anyway that gives us a grace period, so we can ...
0
votes
0answers
25 views

Does it make sense to have a lock-free algorithm that uses a lock?

I heard this is possible, but I cannot think of an example where this makes sense. Please give an example. Also, if a lock - free algorithm is using a lock, how do we prove that it is actually lock ...
0
votes
0answers
43 views

LockFreeStack benchmark (oversubscription state)

I've implemented lock-free Stack, based on 'Concurrency in action' book example. I wanted to benchmark it and compare it to other lock-free stacks, i.e from boost::lockfree. I used google benchmark ...
3
votes
1answer
152 views

C++: How can lock-free data structures be implemented in C++ if std::atomic_flag is the only lock-free atomic type?

Typical way of implementing lock-free data structures is using atomic CAS operations, such as std::compare_exchange_strong or std::compare_exchange_weak. The example of this technique's usage can be ...
9
votes
1answer
129 views

Lock-Free way to Signal between Asyncs

I am looking for a lock-free way to signal between two Asyncs in F#. I have two tail-recursive async functions, and I want one to yield until signaled by the other before proceeding to the next ...
4
votes
1answer
133 views

Spurious underflow in C++ lock-free queue implementation

I'm trying to implement a lock-free queue that uses a linear circular buffer to store data. In contrast to a general-purpose lock-free queue I have the following relaxing conditions: I know the worst-...
5
votes
2answers
676 views

Genuinely test std::atomic is lock-free or not

Since std::atomic::is_lock_free() may not genuinely reflect the reality [ref], I'm considering writing a genuine runtime test instead. However, when I got down to it, I found that it's not a trivial ...
1
vote
2answers
82 views

Portable event checker with condition and lock-free notification

I need to let a realtime (audio) thread signal another background thread when an event happens. The background "checker" thread will then perform some expensive operation. Therefore my restrictions ...
5
votes
1answer
208 views

is_lock_free() returned false after upgrading to MacPorts gcc 7.3

Previously, with Apple LLVM 9.1.0, is_lock_free() on 128-bit structures have returned true. To have complete std::optional support, I then upgraded to MacPorts gcc 7.3. During my first try to compile, ...
2
votes
1answer
158 views

Valgrind: Conditional jump or move depends on uninitialised value(s) when using atomic::compare_exchange_weak

I have an assignment to implement a very basic lock-free sorted vector (with only insert and indexing), and I have everything working properly, however, valgrind is saying that I have a conditional ...
1
vote
1answer
151 views

Thread-local acquire/release synchronization

In general, load-acquire/store-release synchronization is one of the most common forms of memory-ordering based synchronization in the C++11 memory model. It's basically how a mutex provides memory ...
3
votes
2answers
86 views

C++ deleting object, does it lock?

Using C++, when I create a new object, then 'new' keyword do some locks (since it does some memory allocation, etc). So, I cannot use it directly in a lock-free software. However, does the 'delete' ...
2
votes
0answers
68 views

How to test for memory order problems in lock-free/atomics based code on x86/64?

Whilst trying out text book examples of using memory order tags with atomics I realized that even with std::memory_order_relaxed, examples like the one bellow work the same as if stronger memory order ...