synchronize 3 threads to print sequential output

Question

I was asked this question in an interview. I was pretty clueless. So I decided to learn some multithreading and hopefully find an answer to this question.

I need to use 3 threads to print the output: 01020304050607.....

1. Thread1: prints 0
2. Thread2: prints odd numbers
3. Thread3: prints even numbers

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

std::mutex m;
std::condition_variable cv1, cv2, cv3;

int count = 0;

void printzero(int end)
{
    while (count <= end)
    {
        std::unique_lock<std::mutex> lock(m);
        cv1.wait(lock);
        std::cout << 0 << " ";
        ++count;
        if (count % 2 == 1)
        {
            lock.unlock();
            cv2.notify_one();
        }
        else
        {
            lock.unlock();
            cv3.notify_one();
        }
    }
}

void printodd(int end)
{
    while (count <= end)
    {
        std::unique_lock<std::mutex> lock(m);
        cv2.wait(lock);
        if (count % 2 == 1)
        {
            std::cout << count << " ";
            ++count;
            lock.unlock();
            cv1.notify_one();
        }
    }
}

void printeven(int end)
{
    while (count <= end)
    {
        std::unique_lock<std::mutex> lock(m);
        cv3.wait(lock);
        if (count % 2 == 0)
        {
            std::cout << count << " ";
            ++count;
            lock.unlock();
            cv1.notify_one();
        }
    }
}

int main()
{
    int end = 10;

    std::thread t3(printzero, end);
    std::thread t1(printodd, end);
    std::thread t2(printeven, end);

    cv1.notify_one();

    t1.join();
    t2.join();
    t3.join();

    return 0;
}

My solution seems to be in a deadlock situation. I'm not even sure if the logic is correct. Please help

Answer 1

There are several issues with your code. Here is what you need to do in order to make it work:

1. Revise your while (count <= end) check. Reading count without synchronization is undefined behavior (UB).
2. Use a proper predicate with std::condition_variable::wait. Problems of your code without predicate:
   • If notify_one is called before wait then the notification is lost. In the worst case, main's call to notify_one is executed before the threads start running. As a result, all threads may wait indefinitely.
   • Spurious wakeups may disrupt your program flow. See also cppreference.com on std::condition variable.
3. Use std::flush (just to be sure).

I played around with your code quite a lot. Below you find a version where I applied my suggested fixes. In addition, I also experimented with some other ideas that came to my mind.

#include <cassert>

#include <condition_variable>
#include <functional>
#include <iostream>
#include <mutex>
#include <thread>
#include <vector>

// see the `std::mutex` for an example how to avoid global variables

std::condition_variable cv_zero{};
std::condition_variable cv_nonzero{};

bool done = false;
int next_digit = 1;
bool need_zero = true;

void print_zero(std::mutex& mt) {
  while(true) {// do not read shared state without holding a lock
    std::unique_lock<std::mutex> lk(mt);
    auto pred = [&] { return done || need_zero; };
    cv_zero.wait(lk, pred);
    if(done) break;

    std::cout << 0 << "\t"
              << -1 << "\t"// prove that it works
              << std::this_thread::get_id() << "\n"// prove that it works
              << std::flush;

    need_zero = false;

    lk.unlock();
    cv_nonzero.notify_all();// Let the other threads decide which one
                            // wants to proceed. This is probably less
                            // efficient, but preferred for
                            // simplicity.
  }
}

void print_nonzero(std::mutex& mt, int end, int n, int N) {
// Example for `n` and `N`: Launch `N == 2` threads with this
// function. Then the thread with `n == 1` prints all odd numbers, and
// the one with `n == 0` prints all even numbers.
  assert(N >= 1 && "number of 'nonzero' threads must be positive");
  assert(n >= 0 && n < N && "rank of this nonzero thread must be valid");

  while(true) {// do not read shared state without holding a lock
    std::unique_lock<std::mutex> lk(mt);
    auto pred = [&] { return done || (!need_zero && next_digit % N == n); };
    cv_nonzero.wait(lk, pred);
    if(done) break;

    std::cout << next_digit << "\t"
              << n << "\t"// prove that it works
              << std::this_thread::get_id() << "\n"// prove that it works
              << std::flush;

// Consider the edge case of `end == INT_MAX && next_digit == INT_MAX`.
// -> You need to check *before* incrementing in order to avoid UB.

    assert(next_digit <= end);
    if(next_digit == end) {
      done = true;
      cv_zero.notify_all();
      cv_nonzero.notify_all();
      break;
    }

    ++next_digit;
    need_zero = true;

    lk.unlock();
    cv_zero.notify_one();
  }
}

int main() {
  int end = 10;
  int N = 2;// number of threads for `print_nonzero`

  std::mutex mt{};// example how to pass by reference (avoiding globals)

  std::thread t_zero(print_zero, std::ref(mt));

// Create `N` `print_nonzero` threads with `n` in [0, `N`).
  std::vector<std::thread> ts_nonzero{};
  for(int n=0; n<N; ++n) {
// Note that it is important to pass `n` by value.
    ts_nonzero.emplace_back(print_nonzero, std::ref(mt), end, n, N);
  }

  t_zero.join();
  for(auto&& t : ts_nonzero) {
    t.join();
  }
}