4
\$\begingroup\$

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:

// 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);
}

Please see latest changes: Gist

\$\endgroup\$
4
\$\begingroup\$

Problem 1

Consider that register_idle() is equivalent to this slightly rewritten version:

// 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);
    uint8_t pos = idle_pos.fetch_add(1, std::memory_order_relaxed);

    // What happens when this thread stops right here?

    idle_ids_stack[pos] = thread_id;
}

If the thread stops after incrementing idle_pos, but before writing the actual thread id to the stack, you will be in trouble when another thread tries to wake up the thread at the top of stack. It will try to read a thread id from the stack that has not yet been written.

Problem 2

(Credit @MikeMB for correcting me on my previous answer)

You have a problem in wakeup_one() as well. Suppose idle_pos is 2 and idle_ids_stack[1] is 5. Now consider the following sequence of events:

  1. Thread 1 runs wakeup_one() and executes id = idle_ids_stack[old_pos-1], so at this point, id is 5. But now thread 1 sleeps for a little while.
  2. Thread 2 runs wakeup_one(), grabs the same id (5), and returns it, setting idle_pos to 1 in the process.
  3. Thread 3 runs register_idle(), puts its id (3) into idle_ids_stack[1] and increments idle_pos back to 2.
  4. Now thread 1 resumes, and compare-exchanges idle_pos from 2 to 1 successfully. But it returns id as 5 (a duplicate thread id), instead of 3 (the proper one).
\$\endgroup\$
  • \$\begingroup\$ Regarding problem2: compare_exchange_weak does update the first argument with the current value of the atomic variable. In this case, old_pos IS set to the value of idle_pos in every iteration. However, that still leaves Problem 1 and the ABA problem (see my answer at SO - is there a way to merge those questions?). \$\endgroup\$ – MikeMB Jun 18 '15 at 22:13
  • \$\begingroup\$ regarding 2: yes it will be updated thanx to compare_exchange. still the first problem remains... looks like there is no easy solution. i have to consider using Node based approach with tags or hazard pointers \$\endgroup\$ – inspirit Jun 18 '15 at 22:13
  • \$\begingroup\$ @MikeMB Oops sorry, I will correct this. \$\endgroup\$ – JS1 Jun 18 '15 at 22:19
  • \$\begingroup\$ @inspirit Why not just use a lock/mutex? \$\endgroup\$ – JS1 Jun 19 '15 at 4:00
  • \$\begingroup\$ @JS1 yes thats what i did already of course. now i was trying to optimize some of the parts including thread lifecycle management. \$\endgroup\$ – inspirit Jun 19 '15 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.