C++17 atomics and condition_variable deadlock

Question

I have the following code, which deadlocks on the commented lines. Basically f1 and f2 run as individual threads in the program. f1 expects i to be 1 and decrements it, notifying the cv. f2 expects i to be 0 and increments it, notifying the cv. I assume the deadlock occurs if f2 increments i to 1, calls cv.notify(), then f1 reads a stale value of i (which is 0) because there is no memory synchronization between the mutex and i and then waits and never gets woken up. Then f2 also enters a sleep state and now both threads are waiting on a cv that will never be notified.

How can I write this code so that the deadlock does not occur? Basically what I want to be able to achieve is having some atomic state that gets updated by two threads. If the state is not correct in one of the threads, I do not want to spin; rather I want to use the cv functionality (or something similar) to wake the thread up when the value is correct.

I am using g++-7 to compile the code with O3 (although the deadlock occurs in both O0 and O3).

#include <atomic>
#include <condition_variable>
#include <iostream>
#include <mutex>
#include <thread>

std::atomic_size_t i{0};
std::mutex mut;
std::condition_variable cv;

void f1() {
  while (1) {
    {
      std::unique_lock<std::mutex> lk(mut);
      cv.wait(lk, []() { return i.load() > 0; }); // deadlocks
    }
    --i;
    cv.notify_one();
    std::cout << "i = " << i << std::endl; // Only to avoid optimization
  }
}

void f2() {
  while (1) {
    {
      std::unique_lock<std::mutex> lk(mut);
      cv.wait(lk, []() { return i.load() < 1; }); // deadlocks
    }
    ++i;
    cv.notify_one();
    std::cout << "i = " << i << std::endl; // Only to avoid optimization
  }
}

int main() {
  std::thread t1(f1);
  std::thread t2(f2);
  t1.join();
  t2.join();
  return 0;
}

EDIT: cout is only to avoid compiler optimization.

Answer 1

I think the problem is that the value of i could be altered and notify_one could be called in the interval after another thread evaluated return i.load() > 0; but before lambda call returns and cv resumes wait. This way the change of atomic variable won't be observed by another thread and there is no one to wake it up to check again. This could be solved by locking mutex when changing variable though doing so would defeat the purpose of atomic.

Answer 2

I think VTT's answer is correct, just want to show what can happen. First, the code can be rewritten into the following form:

void f1() {
   while (1) {
      {
         std::unique_lock<std::mutex> lk(mut);
         while (i == 0) cv.wait(lk);
      }
      --i;
      cv.notify_one();
   }
}

void f2() {
   while (1) {
      {
         std::unique_lock<std::mutex> lk(mut);
         while (i >= 1) cv.wait(lk);
      }
      ++i;
      cv.notify_one();
   }
}

Now, consider the following time line, i being 0 initially:

time step    f1:               f2:
=========    ================= ================
        1                      locks mut
        2                      while (i >= 1) F
        3                      unlocks mut
        4    locks mut
        5    while (i == 0) T                  
        6                      ++i;
        7                      cv.notify_one();
        8    cv.wait(lk);
        9    unlocks mut(lk) 
       10                      locks mut                   
       11                      while (i >= 1) T
       12                      cv.wait(lk);

Effectively, f1 waits at the moment when i is 1. Both threads are now waiting in a blocking state at once.

---

The solution would be to put modifications of i into locked sections. Then, i even does not need to be an atomic variable.