5

Windows32ビットの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

リストヘッダーメンバーへのアクセスを同期しません。これは少なくとも2つのレベルで悪いです：

  • リストヘッダーへの値の割り当ては、思ったほどアトミックではない場合があります。これは、非同期の読み取り操作が破損した値を取得する可能性があることを意味します。

  • これに関するもう1つのより可能性の高い問題は、ボックスに複数のコアがある場合、それらのすべてがプロセッサキャッシュに値の独自のコピーを持つ可能性があることです。それらに値を同期させるには、メモリバリアが必要です

于 2009-12-11T16:42:00.087 に答える
1

最も明白なエラーは、あなたが付けた名前です。リンクリストとして実装したにもかかわらず、実装したのはスタックです。

于 2009-12-11T16:49:26.630 に答える
1

head -> A -> Bリスト（実際にはスタック）にAとBの2つのアイテムがあり、が2の場合、次の一連のイベントで何が起こるかを考えてみてくださいcount。

  1. スレッド1はpop()呼び出しを開始しますが、直前にプリエンプトされます _InterlockedCompareExchange64()
  2. スレッド2は、スタックからAとBの両方のアイテムを削除してから、2つの新しいアイテムをスタックに戻します。一番上のアイテムは、たまたまAと同じアドレスに割り当てられているので、たとえば、がありますhead -> A -> D。countが2に戻って いることに注意してください
  3. スレッド1が再開し、CAS（ ）を正常に _InterlockedCompareExchange64()実行します。ここheadで、割り当てが解除された（不良）Bを指し、Dが失われた（不良）。

これは古典的なABA問題です。アイテム数ではなく世代番号として2番目の単語を使用する必要があります。つまり、これをデクリメントしないでください。 実験的なboost::lockfreeライブラリ について現在進行中

のメーリングリストの議論があります。Herb Sutterのロックフリーキュー も見てください。これは、ダミーノードがプロデューサーとコンシューマーがお互いを踏まないようにする別のアプローチです。

于 2009-12-11T17:43:23.900 に答える