Questions tagged [lock-free]

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

Filter by
Sorted by
Tagged with
48
votes
5answers
15k views

Thread-Safe and Lock-Free - Queue Implementation

I was trying to create a lock-free queue implementation in Java, mainly for personal learning. The queue should be a general one, allowing any number of readers and/or writers concurrently. Would you ...
20
votes
3answers
2k views

C++ lock-free, MPMC Ring buffer in C++20

I have some performance critical inter-thread messaging code in C++. Multiple producers, one or more consumers. Profiling dozens of iterations of this messaging code over several years of development, ...
17
votes
2answers
2k views

O(1) lock free container

This is a lock-free Container class. By Container I mean it will hold objects for iteration at a later time. To achieve \$O(1)\$ ...
16
votes
2answers
4k views

Lock-free zero-copy triple buffer

In a producer-consumer scenario sometimes we have to deal with the producer being much faster than consumer. The data loss is unavoidable, and we are OK with it, as long as the consumer always has the ...
15
votes
3answers
2k views

Testing a lock-free job queue

I've created a lock-free job queue and with the tests I've written, which is also very fast. That makes me doubt my benchmark procedure, so I'm hoping the collective knowledge will shed some light on ...
15
votes
1answer
6k views

Lock-free multiple-consumer multiple-producer queue

The code below implements an intrusive lock-free queue that supports multiple concurrent producers and consumers. Some features: Producers and consumers work on separate ends of the queue most of ...
15
votes
2answers
1k views

Lock-free cache oblivious n-body algorithm

I'm currently looking at, from a rather high level, the parallelization of the gravity calculation in an N-body simulation for approximating a solution to the N-body problem. The simple form of the ...
12
votes
3answers
1k views

Lock-free thread-safe Fibonacci number generator

Here is my implementation of a lock-free thread-safe Fibonacci number generator. Is it correct? The idea is to use an immutable holder for previous and current numbers (since it's hard to change two ...
12
votes
1answer
5k views

Play some sine waves with SDL2

Runs smoothly, however valgrind is showing "possibly lost: 544 bytes in 2 blocks". This is my first time doing a lot of things here so I might be making multiple mistakes. Please let me know if ...
12
votes
1answer
16k views

Thread-safe lock-free counter

I was using such code: ...
11
votes
2answers
2k views

Implementation of a lock-free fixed-sized allocator

This question now has a follow-up: Implementation of a lock-free fixed-sized allocator - follow-up - with commented code I've tried implementing a lock-free fixed-size allocator while trying to ...
11
votes
1answer
3k views

Lock-free atomic shared pointer in C++14

I'm trying to write a lock-free implementation for atomic shared pointer. Basically, there are two class templates shared_ptr and ...
9
votes
3answers
3k views

C++ lock free, single producer, single consumer queue

Assumptions for use: push() will only ever be called by a single thread. pop() will only ever be called by a single thread. Requirements: push() needs to be as fast as possible. Requirements are ...
9
votes
3answers
2k views

Naive lock free work stealing queue

Recently, I read a article about work stealing queue Job System 2.0: Lock-Free Work Stealing – Part 3: Going lock-free, and this is my c++11 naive implementation based on my understand of c++11 ...
9
votes
2answers
1k views

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

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 ...
8
votes
1answer
440 views

Searching in a lock-free ordered single-linked list

The code below represents a lock-free ordered single-linked list, and is a modification of the algorithm proposed in this doc. How can I improve speed of searching (lookingup) in the list maintaining ...
8
votes
2answers
2k views

Lockless Queue Multiple-Reader Singler-Writer in C++

I wrote a lockless queue for sending small objects from a single thread to a random worker thread. Assumptions: x86/x86_64 compiled with GCC one thread may Write(), multiple threads may Read() ...
8
votes
1answer
2k views

Lock-free multi-producer multi-consumer queue

I'm looking for some feedback on my lock-free queue, based on Disruptor, mainly for any potential concurrency issues, such as where I need additional fences. It looks correct to me, and I can't seem ...
8
votes
1answer
805 views

Low-lock Multi-threading Implementation

I'm designing in my spare time a game engine (for fun, not so much for profit, haha). I wanted to design the 'core pipeline' as efficiently as possible. Having a quad-core CPU, I decided to take ...
7
votes
3answers
2k views

Lock-free SPMC queue

Here is my lock-free queue implementation for single producer with some preallocated memory. T is a simple type with no need for move operations. I don't use ...
7
votes
1answer
309 views

Lock-free triple buffer

I have a single producer and single consumer, and the producer never stops, but the consumer might not keep up. There's no need to consume every item, as long as we always access the most-recently ...
7
votes
1answer
656 views

Lock-free, multiple consumer, multiple producer queue

I'm implementing a lock-free, multiple consumer, multiple producer FIFO queue/pipe as an exercise in thinking about atomicity in operations. My main concern is correctness of operation, my second ...
7
votes
1answer
1k views

Snowflake Id implementation

For some time now I have maintained (and written) IdGen. It's inspired by Twitter's Snowflake project and it's intended use is to generate (roughly) incremental id's in a distributed scenario with ...
7
votes
1answer
2k views

Multiple-producer, single-consumer lock-free circular queue

I'm working on a firmware on a bare-metal ARM single core processor (Cortex M4), with no RTOS. I need to add a multiple-producer, single-consumer, lockless fixed-size circular (ring) buffer to the ...
7
votes
0answers
2k views

Yet another multi-producer single consumer queue in C++17

Here's an implementation of a multi-producer single consumer queue that I wanted to use with tasks such as logging from multiple points in a program to a single sink. The implementation is inspired ...
6
votes
4answers
2k views

Singleton SpinLock: Making Random Thread-Safe

Is this a valid and safe use of .NET's System.Threading.SpinLock? Why am I doing this? Random's public methods are not ...
6
votes
1answer
4k views

Lockless multi user, multi consumer FIFO queue using C++11

One of the features that is missing from C++11 are lockless queues. Therefore I have decided to write one myself. A few remarks: I know the code isn't technically lockless. However the lock is only ...
6
votes
1answer
756 views

Single producer single consumer wait-free object container

I have a fast producer thread and a slow consumer thread. The consumer processes as many objects as it can and simply ignores the rest in order to not slow down the producer. Therefore, I used a one-...
6
votes
1answer
1k views

C++11 lock free collection similar to std::forward_list - follow-up

This question has been superseded by C++11 lock free collection similar to std::forward_list - follow-up 2 Thread safe and lock free collections are very hard to write, so I'd appreciate any feedback,...
6
votes
1answer
2k views

Lock-free bounded stack in C++11

Here is a classical attempt to implement a lock-free stack (based on this article). I rewrote it in C++11 and also tried to add memory orders which I would like to confirm to be correct. ...
6
votes
0answers
210 views

Simple lock-free queue - multiple producers, single consumer

I have a simple lock-free queue, which supports multiple producers, but only one consumer. It is based on a constant-sized ring buffer and stores only pointers to a class and not actual instances. ...
5
votes
2answers
579 views

A simple lock-free queue for work stealing

I am currently reading the book C++ Concurrency in Action by Anthony Williams. In chapter 9, he implemented a lock-based work stealing queue and mentioned it is possible to implement a lock-free queue ...
5
votes
1answer
3k views

Single consumer and single producer lock-free circular buffer

I'm pretty new to multithreading. The code below is a simple implementation of a single consumer/single producer circular buffer that does not use any locking, that I wrote for fun. The question is,...
5
votes
2answers
3k views

Lock-free multiple producer single consumer message queue

For a while now I've been after a lock-free, simple and scalable implementation of a multiple producer, single consumer queue for delegates in C#. I think I finally have it. I've run basic tests on it ...
5
votes
3answers
595 views

Lock-free MultiConsumer/MultiProducer queue

I've written a simple lock-free multi-consumer/-producer FIFO queue. It's supposed to work like this: At any time many consumers may read from it At any time multiple producers can write to it, added ...
5
votes
2answers
4k views

Block a thread - spin-lock replacement

I have implemented several lock-free algorithms to maximise throughput but have always baulked when performing a spin-lock. I can usually convince myself that this is the only way but it still nags at ...
5
votes
1answer
977 views

Non blocking single producer/consumer queue with C++11 atomics

I've recently got interested in lockless programming, mainly lockless queues for job repartitions, so here I undertook a challenge of creating lockless queue for single producer and consumer. This is ...
5
votes
1answer
403 views

Lockless, blocking, non synchronized multiple producers and consumers ring buffer

My program is structured like this: there are M producer threads, each of which computes a section of an object O with index <...
5
votes
1answer
2k views

Lock-free queue with doubly linked list correctness

I need a lock-free queue which is implemented by doubly linked list. Is my code correct? Are there any errors? Are there any improvements to be made? linkedlist.h ...
5
votes
1answer
2k views

Lockfree ThreadPool implementation

How could this template class ThreadPool be improved? I use Boost queue to keep std::function's numbers from ...
5
votes
1answer
4k views

Lock-free ringbuffer with multiple readers in C++11

Basic Info I needed a lock-free ringbuffer with multiple readers (but one writer). However, I did not want the writer to check all readers every time in order to prevent an overrun. Thus, I decided ...
5
votes
1answer
482 views

lock-free job queue without size restriction (multiple read/write)

I've since come up with an improved version, which isn't technically lock-free, but might be as close as you can get (nearly) lock-free job queue of dynamic size (multiple read/write) code below is ...
5
votes
1answer
814 views

CountdownLatch Thread-Safety Check

I've written this class as an exercise for a synchronization construct to be used across multiple threads. The intent is to have worker threads Increment() it, do ...
5
votes
0answers
2k views

Disruptor pattern in a lock-free producer-consumer queue

I'm implementing a quick-and-dirty lock-free MPMC queue in C++, based on the v3 Disruptor algorithm. The implementation is pretty simple: Data to be shared between threads is stored in a ring buffer. ...
4
votes
2answers
4k views

C++ minimal threadsafe array based on std::deque

Here is a minimal example of a threadsafe array I want to build on for a timeseries application, with the following characteristics: Ever-growing, and the already contained elements remain constant (...
4
votes
2answers
4k views

Thread-safe lock free FIFO queue

A few years ago there was a need to add a FIFO queue between 2 threads into my project. At that time I've got some interesting idea how to do that without any atomics and locks. (There was a ...
4
votes
2answers
5k views

ArrayBlockingQueue: concurrent put and take

I have implemented an ArrayBlockingQueue (put and take) on the lines of LinkedBlockingQueue i.e using two locks so that my take ...
4
votes
1answer
145 views

Lock-free bounded stack atomics

I was thinking about using very basic bounded (preallocated) stack to keep track of my threads IDs in correct LIFO order. I was wondering if my implementation is thread safe: ...
4
votes
1answer
158 views

A concurrent lock-free Linked Queue implementation

Recently I've been learning about concurrency/parallelism and I decided to implement the Michael&Scott lock-free Linked queue (PDF) as practice. I'm not entirely sure how to test this data ...
4
votes
1answer
2k views

Lock-free FIFO queue implementation

...