синхронизировать 3 потока для печати последовательного вывода

Question

Мне задали этот вопрос в интервью. Я был довольно невежественным. Поэтому я решил научиться многопоточности и, надеюсь, найти ответ на этот вопрос.

Мне нужно использовать 3 потока, чтобы напечатать вывод: 01020304050607 .....

1. Тема1: печать 0
2. Тема 2: печатает нечетные числа
3. Thread3: печатает четные числа

#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;
}

Мое решение, похоже, в тупиковой ситуации. Я даже не уверен, что логика верна. Пожалуйста, помогите

Answer 1

Есть несколько проблем с вашим кодом. Вот что вам нужно сделать, чтобы это заработало:

1. Пересмотрите свой while (count <= end) чек. Чтение count без синхронизации - неопределенное поведение (UB).
2. Используйте правильный предикат с std::condition_variable::wait. Проблемы вашего кода без предиката:
   • Если notify_one вызывается до wait, то уведомление теряется. В худшем случае вызов main на notify_one выполняется до начала работы потоков. В результате все потоки могут ждать бесконечно.
   • Ложные пробуждения могут нарушить ход вашей программы. См. Также cppreference.com на std::condition variable.
3. Используйте std::flush (просто чтобы быть уверенным).

Я довольно много играл с твоим кодом. Ниже вы найдете версию, где я применил предложенные мной исправления. Кроме того, я также экспериментировал с некоторыми другими идеями, которые приходили мне в голову.

#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();
  }
}