Lock Free Bounded Stack C ++ 11 atomics
I was thinking about using a very simple bounded (pre-allocated) stack to keep track of my thread IDs in the correct LIFO order. So I was wondering if my implementation is thread safe:
// we use maximum 8 workers
size_t idle_ids_stack[8];
// position current write happening at
std::atomic_uint_fast8_t idle_pos(0);
// this function is called by each thread when it is about to sleep
void register_idle(size_t thread_id)
{
std::atomic_thread_fence(std::memory_order_release);
idle_ids_stack[idle_pos.fetch_add(1, std::memory_order_relaxed)] = thread_id;
}
// this function can be called from anywhere at anytime
void wakeup_one()
{
uint_fast8_t old_pos(idle_pos.load(std::memory_order_relaxed));
std::atomic_thread_fence(std::memory_order_acquire);
size_t id;
do
{
if(old_pos == 0) return; // no idle threads in stack; exit;
id = idle_ids_stack[old_pos-1];
}
while (!idle_pos.compare_exchange_weak(old_pos, old_pos-1, std::memory_order_acquire, std::memory_order_relaxed));
// wakeup single thread
signal_thread(id);
}
source to share
I am not an expert on blocking programming, but I am pretty sure your code is NOT thread safe.
-
Consider first
register_idle()
:What can happen here is that Thread1 is incrementing
idle_pos
, but before it stores its id, another thread callswakeup_once
and uses the deprecated id (in the worst case, not even a valid one, since the array is not initialized yet). Also I see no reason to fetch memory ... -
In
wakeup_one()
you have a similar problem (called ABA problem ):- You download current
idle_pos
and according toid
. - Another thread calls and terminates
wakeup_one
(idle_pos is decremented). - Another thread calls
register_idle
, which again increases idle_pos to the same value as before. - Now the first thread resumes, thinks it
idle_pos
doesn't change and signals the wrong thread
- You download current
I may be wrong, but I believe that it is generally not possible to create fully blocking stacks based on an array, because you need to do two things in one atomic operation: change the index variable and store or load the value in the array.
Aside from these logic errors, I highly recommend not using offline memory fences (they make the code less readable and may even be more expensive). Also, I would just start manually specifying the memory orders after I made sure the program is correct with the default settings.
source to share