5

我在 Windows 32 位上用 C++ 编写了一个低锁列表。与使用关键部分相比，我得到了很大的改进，但我希望有人能理智地检查我所做的事情是否正确，并且我所做的事情没有任何错误：

#ifndef __LOW_LOCK_STACK_H_
#define __LOW_LOCK_STACK_H_

template< class T > class LowLockStack
{
protected:
    struct Entry
    {
        Entry*  pNext;
        T*              pData;
    };
    union Header
    {
        __int64         m_XChg;
        struct
        {
                Entry*  m_pNext;
                __int16 m_Depth;
                __int16 m_Counter;
        };
    };

    Header      m_Header;
public:
    LowLockStack()
    {
        m_Header.m_pNext        = NULL;
        m_Header.m_Depth        = 0;
        m_Header.m_Counter  = 0;
    }

    ~LowLockStack()
    {
    }

    void PushEntry( T* pData )
    {
        Entry* pEntry   = new Entry;
        pEntry->pData   = pData;

        Header header;
        Header xchg;
        do
        {
            xchg.m_XChg   = m_Header.m_XChg;

            header.m_pNext  = pEntry;
            header.m_Depth  = xchg.m_Depth + 1;
            header.m_Counter = xchg.m_Counter + 1;
            pEntry->pNext  = xchg.m_pNext;
        } while( _InterlockedCompareExchange64( &m_Header.m_XChg, header.m_XChg, xchg.m_XChg ) != xchg.m_XChg );
    }

    T* PopEntry()
    {
        Entry* pEntry   = NULL;
        Header header;
        Header xchg;
        do
        {
            xchg.m_XChg    = m_Header.m_XChg;

            pEntry                  = xchg.m_pNext;
            if ( pEntry == NULL )
            {
                 return NULL;
            }

            header.m_pNext  = pEntry->pNext;
            header.m_Depth  = xchg.m_Depth - 1;

        } while( _InterlockedCompareExchange64( &m_Header.m_XChg, header.m_XChg, xchg.m_XChg ) != xchg.m_XChg );

        T* pRet = pEntry->pData;
        delete pEntry;

        return pRet;
    }

    __int32 GetDepth()
    {
        return m_Header.m_Depth;
    }
};

#endif

如果没有错误（我怀疑；））然后将其视为参考实现：D

编辑：考虑到一些批评，我已经更新了代码。

4

4 回答 4

4

正如您所发现的，无锁编程很难做到正确。

Windows 已经支持无锁单链表， http: //msdn.microsoft.com/en-us/library/ms684121 (VS.85).aspx ，你应该尝试使用它而不是自己动手。

于 2009-12-11T16:46:39.803 回答
2

您不同步对列表标题成员的访问。这至少在两个层面上很糟糕：

  • 将值分配给列表标题可能不像您想象的那么原子。这意味着未同步的读取操作可能会获得损坏的值。

  • 另一个更可能的问题是，如果您的盒子有多个内核，那么每个内核都可以在处理器缓存中拥有自己的值副本。要使它们同步值，您需要一个内存屏障

于 2009-12-11T16:42:00.087 回答
1

最明显的错误是你给它的名字。不管您是否将其实现为链表，您实现的是一个堆栈。

于 2009-12-11T16:49:26.630 回答
1

考虑当列表（实际上是堆栈）中有两个项目 A 和 B 时，在以下事件序列中会发生什么，如head -> A -> B2 count：

  1. 线程 1 开始pop()调用，但在此之前被抢占 _InterlockedCompareExchange64()
  2. 线程 2 从堆栈中删除两个项目，A 和 B，然后将两个新项目放回堆栈，并且顶部项目恰好分配在与 A 相同的地址，所以我们有，说head -> A -> D。请注意，count返回到 2
  3. 线程 1 恢复并成功执行 CAS ( _InterlockedCompareExchange64())。现在head指向 B，它被释放（坏）并且 D 丢失（坏）。

这是一个经典的ABA问题。您应该使用第二个单词作为代号而不是项目计数，即永远不要减少它。 现在有一个关于实验性boost::lockfree库

的邮件列表讨论。 还可以看看Herb Sutter 的无锁队列——这是一种不同的方法，其中一个虚拟节点可以防止生产者和消费者相互踩踏。

于 2009-12-11T17:43:23.900 回答