c++ - Win32 C++ 中的无锁双端队列

Question

我对无锁数据结构还很陌生，所以我写了一个练习(我希望它的功能是)一个有界无锁双端队列(还没有调整大小，只是想让基本情况起作用)。我只是想从知道自己在做什么的人那里得到一些确认，以确定我是否有正确的想法和/或我如何改进它。

class LocklessDeque
{
  public:

    LocklessDeque() : m_empty(false),
                      m_bottom(0),
                      m_top(0) {}


    ~LocklessDeque()
    {
      // Delete remaining tasks
      for( unsigned i = m_top; i < m_bottom; ++i )
        delete m_tasks[i];
    }


    void PushBottom(ITask* task)
    {
      m_tasks[m_bottom] = task;

      InterlockedIncrement(&m_bottom);
    }


    ITask* PopBottom()
    {
      if( m_bottom - m_top > 0 )
      {
        m_empty = false;

        InterlockedDecrement(&m_bottom);

        return m_tasks[m_bottom];
      }

      m_empty = true;

      return NULL;
    }


    ITask* PopTop()
    {
      if( m_bottom - m_top > 0 )
      {
        m_empty = false;

        InterlockedIncrement(&m_top);

        return m_tasks[m_top];
      }

      m_empty = true;

      return NULL;
    }


    bool IsEmpty() const
    {
      return m_empty;
    }

  private:

    ITask* m_tasks[16];

    bool m_empty;

    volatile unsigned m_bottom;
    volatile unsigned m_top;

};

Answer 1

看着这个我会认为这会是一个问题:

void PushBottom(ITask* task)
{
  m_tasks[m_bottom] = task;
  InterlockedIncrement(&m_bottom);
}

如果在实际的多线程环境中使用它，我认为您在设置 m_tasks[m_bottom] 时会发生冲突。想一想如果您有两个线程同时尝试执行此操作会发生什么 - 您无法确定哪个线程实际设置了 m_tasks[m_bottom]。

查看 this article这是对无锁队列的合理讨论。