Stack Overflow
Stack Overflow

Questions tagged [wait-free]

A method is wait-free if it guarantees that every call finishes its execution in a finite number of steps (i. e. even if one thread is stuck on execution, other threads don't wait while it completes).

17 questions
27
votes
5 answers

Lock-free and wait-free thread-safe lazy initialization

To perform lock-free and wait-free lazy initialization I do the following: private AtomicReference instance = new AtomicReference<>(null); public Foo getInstance() { Foo foo = instance.get(); if (foo == null) { foo = new Foo(); …
Alex Salauyou
  • 14,185
  • 5
  • 45
  • 67
8
votes
2 answers

Anything in std::atomic is wait-free?

If T is a C++ fundamental type, and if std::atomic::is_lock_free() returns true, then is there anything in std::atomic that is wait-free (not just lock-free)? Like, load, store, fetch_add, fetch_sub, compare_exchange_weak, and…
Koosha
  • 1,492
  • 7
  • 19
6
votes
1 answer

implementing a Fast .NET Lock-Free Inter-Process using SharedMemory MMF

I am new to multitasking and IPC and I am trying to construct an approach for fast inter process comunication using shared memory( at first I was researching the IPC term, having in mind wcf sockets and named pipes only to eventually discover about…
RalfL
  • 109
  • 4
4
votes
2 answers

Are X86 atomic RMW instructions wait free

On x86, atomic RMW instructions like lock add dword [rdi], 1 are implemented using cache locking on modern CPUs. So a cache line is locked for duration of the instruction. This is done by getting the line EXCLUSIVE/MODIFIED state when value is read…
pveentjer
  • 10,545
  • 3
  • 23
  • 40
3
votes
2 answers

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 FIFO is full, the producer shall simply retire or…
purefanatic
  • 933
  • 2
  • 8
  • 23
3
votes
2 answers

What exactly is the meaning of "wait-free" in boost::lockfree?

I am reading the docs for spsc_queue and even after reading a bit elsewhere I am not completely convinced about the meaning of "wait-free". What exactly do they mean here bool push(T const & t); Pushes object t to the ringbuffer. Note: Thread-safe…
463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
2
votes
1 answer

Improving lock-free linear allocation to be wait-free

Given the following simple lock-free linear allocation algorithm I made: bool allocate(size_type size, size_type& offset) { size_type pos; size_type new_pos; pos = m_pos.load(std::memory_order_acquire); do { new_pos…
plasmacel
  • 8,183
  • 7
  • 53
  • 101
2
votes
2 answers

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.example_ringbuffer I am wondering if the memory_order_acquire is…
Yunzhou Wu
  • 71
  • 4
1
vote
0 answers

Examples for lock-free but not wait-free algorithms?

According to Examples/Illustration of Wait-free And Lock-free Algorithms: all wait-free programs are lock-free, this is obvisous by the definition of lock-free and wait-free. But I can't think of an algorihtm that is lock-free but not wait-free,…
konchy
  • 573
  • 5
  • 16
1
vote
1 answer

Does boost atomic reference counting example contain a bug?

I'm referring to this example. The authors use memory_order_release to decrement the counter. And they even state in the discussion section that using memory_order_acq_rel instead would be excessive. But wouldn't the following scenario in theory…
Leonid
  • 1,127
  • 2
  • 15
  • 29
1
vote
1 answer

Wait-free put, get data-structure

I am considering concurrent multi-producer multi-consumer data structure that has two methods: success = try_put(elem) and success = try_get(&elem). I assume that this data structure has a fixed amount of preallocated memory and in case it is full…
user8044236
1
vote
0 answers

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 there may be a particular thread in the loop for…
Derek Zhang
  • 101
  • 1
  • 7
1
vote
0 answers

Is the following object wait-free?

Here is the full question: Is the following property equivalent to saying that object x is wait-free? For every infinite history H of x, every thread that takes an infinite number of steps in H completes an infinite number of method calls. So I…
sparrow2
  • 147
  • 1
  • 11
0
votes
1 answer

Need help porting a wait free trie from C to Rust

For some HPC computing I need to port a wait free trie (but you can think of it as a tree) from C to Rust. The trie is 99% read 1% write, and is used both in parallel-concurrent scenarios , and concurrent only scenarios (single thread with multiple…
Mascarpone
  • 2,516
  • 4
  • 25
  • 46
0
votes
1 answer

Can the hardware fetch&add instruction guarantee wait-free execution?

So, if multiple processes execute FAA, is there any guarantee that this FAA instruction will be executed in a wait-free manner? What if processes that finish executing this instruction do not stop there but repeatedly try to execute it?
agood
  • 50
  • 1
  • 7
1
2