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.

Pigeontoed

—i and ++I should be inside the while. Otherwise conditions is never reached – Bone

You print values after they could've been altered by another thread. – Robinia

I'm guessing but I think a spurious wakeup may happen after one thread has changed the value but before it calls notify. So both threads can end up waiting on the variable without any possibility of notify being called again. Moving the increment/decrement into the lock seems to fix it. – Tovatovar

While moving it into the while is a solution, I'm wondering if it's possible to do without double synchronization (the atomic is already synchronizing i). – Pigeontoed

@Pigeontoed Make i not atomic, then you only need to rely on the mutex for synchronization. – Undue

Why C++17? Is there anything not available in C++11? – Envoi

I would recommend to rewrite cv.wait(lk, []() { return i.load() > 0; }); into while (i==0) cv.wait(lk); and similarly in f2 to make it more clear. – Envoi

I believe that on linux, the use of conditionnal variable and mutex is redundant, when a mutex is released, it automaticaly awakes one waiting threads. (TBC, if not, realy and if you target linux, just directly use futex) – Perdu

@Oliv, in linux, cv-s are comparable to signals, not mutexes, but cv-s require a mutex to work. I haven't worked with futexes immediately, but if it is not portable, then you're balancing portability with speed or smaller code. Wikipedia calls condition variable a higher-level locking abstraction of futex. – Veldaveleda

@Veldaveleda I can't find a wikipedia page where this is said, I would like to read this page evenif I know indeed that futex are used to implement condition variable as mutex. My opinion is that c++ mutex are a too high abstraction, of what is actualy a simple mechanism. For example, I see questions about implementing a lock that spin some time then lock a mutex, this is redundant too, this is how mutex are implemented with futex! The aim of multithreading is efficiency, but the synchronization primitive provided by the C++ standard can just lead to suboptimal constructs! So I will never use it – Perdu

en.wikipedia.org/wiki/Futex first paragraph. – Veldaveleda

@Perdu What do you mean? How do you program w/o CV on linux? – Decarburize

@Decarburize I don't remenber what I meant. But here clearly, on linux there is no need for a cv, neither a mutex. It could be done with a compare_and_exchange loop, the futex will be an optimization to avoid the spin lock. Actualy, coding using kernel primitive is much easier and less error prone. As you are curious, I advice you to code without glibc, direct raw assembly system calls, not even start up files. The kernel/user space interface is the right level of abstraction! Posix/glibc/pthread ... that's crap, just think about errno, – Perdu

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.

Robinia

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.

Envoi

The original notation in the question of OP solves the age old confusion of using the wait function without a predicate, so in that sense, it made things clearer that you now show what predicate you actually expect and that you're not just waiting on some signal that in order to work has to be in a while-loop. Also, optional time-outs are handled better (cv::wait_for()). – Veldaveleda

Also, in your scenarios, while (i == 0) and cv.wait(lk); are synced, so the thread can't be interrupted between them. – Veldaveleda

@Veldaveleda I updated the time line to include locking and unlocking of mutex. – Envoi

Yes, that works because ++i is not guarded. And the scenario easier shown in the while notation. – Veldaveleda

Answer 3

You call cv.notify_one(); when a thread does not own the mutex. It may cause notification is sent to empty. Imagine f2 starts before f1. f2 calls cv.notify_one(); but f1 is not in cv.wait yet.

Acquired mutex guarantees that f2 is either in std::unique_lock<std::mutex> lk(mut) or waits for notification.

#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::size_t ii;
    {
      std::unique_lock<std::mutex> lk(mut);
      cv.wait(lk, []() { return i.load() > 0; });
      ii = --i;
      cv.notify_one();
    }
    std::cout << "i = " << ii << std::endl;
  }
}

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

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

BTW std::atomic_size_t i could be std::size_t i.

Equi

I don't think you need to hold the mutex when notifying. Doesn't that run the risk of the notified thread waking up before the mutex has been unlocked? – Undue

@Undue According to this: "The notifying thread does not need to hold the lock on the same mutex as the one held by the waiting thread(s); in fact doing so is a pessimization, since the notified thread would immediately block again, waiting for the notifying thread to release the lock." – Jez

If you want change i to std::size_t, then the std::cout statements must be guarded because they access i. – Veldaveleda

@Veldaveleda Thank you. I updated the answer. It is a bad idea to guard std::cout, therefore I added local variables. – Equi

Answer 4

Since i is atomic, there is no need to guard its modification with the mutex.

The waits on the condition variable in f1 and f2 wait for ever unless a spurious wake-up occurs, because the condition variable was never notified. Since spurious wake-ups are not guaranteed, I suggest to check for the condition before waiting on the condition variable, and eventually notify the condition variable for the other thread.

There is another problem with your code. Both functions f1 and f2 will never end. So your main function will wait for ever joining its threads.

Housemaster

The std::wait() function does a while(! pred) wait_without_pred() internally (see answer of Daniel Langr) and not ending programs for demo purposes are normally closed with ctrl-c, the joins are needed to keep the program alive. – Veldaveleda