c++ - 公平队列丢失通知

Question

考虑以下代码

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

template <typename T>
class Tqueue 
{
public:

   Tqueue() : m_next_ticket(0),
              m_counter(0) {}

   void push(const T& e){
       std::unique_lock<std::mutex> lock(m_mutex);
       m_queue.push(e);
       lock.unlock();
       m_cond.notify_all();
    };

   T wait_and_pop() {
       std::unique_lock<std::mutex> lock(m_mutex);
       int ticket = m_next_ticket++;
       m_cond.wait(lock,[=]{return (!m_queue.empty())
                  && (ticket == m_counter);});
       m_counter++;
       T data = m_queue.front();
       m_queue.pop();
       return data;
   }

private:
   int m_next_ticket;
   int m_counter;
   std::queue<T> m_queue;
   std::mutex m_mutex;
   std::condition_variable m_cond;   
};

这应该是我想出的公平队列的模板。在这种情况下，公平意味着 wait_and_pop() 调用返回的顺序与不同线程调用它们的顺序相同。

例如:线程 1 在空队列上调用 wait_and_pop() 并阻塞。然后 Thread 2 在空队列上调用 wait_and_pop() 并阻塞。之后 Thread 3 使用 push() 推送两个事件。现在 Thread 1 应该在 Thread 2 之前返回。

使用以下代码，有时它会起作用。但大多数时候代码永远阻塞:

Tqueue<int> queue;

std::mutex mutex;

void test(int i) 
{
    auto bla = queue.wait_and_pop();
    std::cout << "Thread : "<<bla << std::endl;
}

const int SIZE = 200;

int main(int argc, char *argv[])
{
    std::vector<std::thread> threads;
    for(int i = 0; i < SIZE; ++i)
       threads.push_back(std::thread(test,i));
    for(int i = 0; i < SIZE; ++i)
        queue.push(i);
    for(int i = 0; i < SIZE; ++i)
       threads[i].join();
    return 0;
}

想法是为每个线程创建一个唯一的票证。使用条件变量，然后我们在 wait_and_pop() 函数中等待，直到插入一个新事件。在 push() 函数中，新事件被插入队列并通知所有等待线程。每个线程检查是否队列不再为空并且唯一票证等于当前柜台。如果是这样，特定线程离开条件循环，从队列中弹出当前事件并增加计数器。

我怀疑有些通知丢失了，但我无法理解为什么会这样。有什么想法可以解决这个问题或如何以正确的方式实现这个问题吗？

编辑我如下更改了队列中的代码。现在它似乎工作。重要的是，我通知，同时仍然持有锁(在 push() 和 wait_and_pop() 中)。此外，我将票证系统更改为线程 ID 队列，但这只是为了方便，它使源代码保持紧凑。但我不确定，如果我想在生产代码，因为我不明白为什么它现在可以工作，而且我不知道它是否适用于所有情况。也许有人可以对此发表评论？

template <typename T>
class Tqueue 
{
public:
   void push(const T& e){
       std::unique_lock<std::mutex> lock(m_mutex);
       m_queue.push(e);
       m_cond.notify_all();
   };

   T wait_and_pop() {
       std::unique_lock<std::mutex> lock(m_mutex);
       m_ids.push(std::this_thread::get_id());
       m_cond.wait(lock,[=]{return (!m_queue.empty())
                  && (m_ids.front() == std::this_thread::get_id());});
       T data = m_queue.front();
       m_queue.pop();
       m_ids.pop();
       m_cond.notify_all();
       return data;
   }

private:
   std::queue<T> m_queue;
   std::queue<std::thread::id> m_ids;
   std::mutex m_mutex;
   std::condition_variable m_cond;

 };

Answer 1

通知确实丢失了。有可能许多 push 生成更少数量的线程被唤醒，因为当 m_cond.notify_all(); 被执行时，它只是让等待线程 runnable，即准备运行。这些线程仍然需要等待并获取 m_cond.wait 中的锁。

也有可能是主线程在单个 等待线程最终可以执行之前继续多次获取互斥量。这导致通知饥饿。

为了使该机制发挥作用，您需要在条件受到影响时随时通知。您已经通知 m_queue.push(e);，这会影响第一个条件 !m_queue.empty()。您还需要在 wait_and_pop 结束时通知，以处理第二个条件 ticket == m_counter。

T wait_and_pop() {
   ....blah blah
   T data = m_queue.front();
   m_queue.pop();

   lock.unlock();
   m_cond.notify_all();
   return data;
}

注意:有可能在这里我的意思是“最终会有一个最终发生的线程调度”。我不是说“我不确定”。

进一步说明:condition_variable.notify_all() 只保证最终唤醒线程。它不保证 X 次调用会唤醒 X 次。此外，由于您的情况，减少了保证只通知一个线程，这是根本原因。

关于在wait_and_pop解锁前后通知
在 wait_and_pop 中释放锁之前或之后通知应该没有任何区别。我指定的修改应该与编辑中的修改一样。我一直在进行一些变化(线程数、等待 x 线程完成并再次推送)的测试，结果相同。