2

Answer to this question is wrong as it has chance to deadlock. Condition Variable - Wait/Notify Race Condition

I found no solution to solving race condition or dead lock issue.

Imagine we have two threads. now goal is as follows.

first condition:
Thread 1 Waits
Thread 2 Notifies

second condition:
Thread 2 Notifies
Thread 1 Should not wait and continue normal execution.

How can this be implemented correctly without having a queue for notifies? because I want this part of code to run as fast as possible and use a Boolean value instead of adding item into queue. Also there are only 2 threads, so use of queue seems overkill for me.

pseudo code when there is race condition:

Thread 1:
lock(x);
if(!signaled)
{
    unlock(x); // ********
    // still small gap, how to avoid?
    cv.wait(); // forget spurious wakeup for sake of simplicity 
    signaled = false;
}
else // ********
    unlock(x);

Thread 2:
lock(x);
signaled = true;
cv.notify();
unlock(x);

now if you remove two lines commented with ******** race condition will be solved and chance of deadlock will be introduced where Thread1 waits while owning the lock and Thread2 is stuck at locking x.

M.kazem Akhgary
  • 18,645
  • 8
  • 57
  • 118
  • You might want to look into using the [`std::atomic`](http://en.cppreference.com/w/cpp/atomic/atomic) mechanism to handle this case. – tadman Jul 27 '17 at 20:57
  • 2
    Your assumptions are incorrect. `conditional_variable::wait` **atomically** enters wait mode and releases the lock. – SergeyA Jul 27 '17 at 20:58
  • even if `conditional_variable::wait` releases the lock, I'm pretty sure it does that **before** waiting, so the gap is still there internally @SergeyA – M.kazem Akhgary Jul 27 '17 at 21:03
  • 1
    @M.kazemAkhgary, no, you are wrong. There is no gap, it is guaranteed by implementation. This is what it exists for – SergeyA Jul 27 '17 at 21:06

1 Answers1

3

The source of your confusion is your misunderstanding of conditional variables. The inherent feature of them is that lock release and entering into wait mode is done atomically, i.e. nothing happens in between.

So no modification to the variable can be happening before variables enters into wait mode, because lock will not be released. This is basic guarantee of any conforming conditional_variable implementation, for example, here is the extract from the reference page for std::conditional_variable:

http://en.cppreference.com/w/cpp/thread/condition_variable/wait

Atomically releases lock, blocks the current executing thread, and adds it to the list of threads waiting on *this. The thread will be unblocked when notify_all() or notify_one() is executed. It may also be unblocked spuriously. When unblocked, regardless of the reason, lock is reacquired and wait exits. If this function exits via exception, lock is also reacquired. (until C++14)

SergeyA
  • 61,605
  • 5
  • 78
  • 137
  • ok, forget my previous comment, if two operations are done atomically then problem is solved. can you give reference to your statement? – M.kazem Akhgary Jul 27 '17 at 21:06
  • 1
    I would be in whatever API you are using. Provided you are using C++, it would be in documentation for `conditional_variable::wait`. Will put in the answer. – SergeyA Jul 27 '17 at 21:07