0

私はロックレスデータ構造にかなり慣れていないので、演習のために（機能することを望んでいます）制限付きロックレス両端キューを作成しました（サイズ変更はまだありません。基本ケースを機能させたいだけです）。私が正しい考えを持っているかどうか、および/またはこれをどのように改善できるかについて、彼らが何をしているのかを知っている人々から確認を得たいと思います.

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;

};
4

4 に答える 4

3

これを見ると、これは問題になると思います：

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

これが実際のマルチスレッド環境で使用される場合、設定時に衝突すると思いますm_tasks[m_bottom]。2 つのスレッドが同時にこれを実行しようとするとどうなるかを考えてみてください。どちらが実際に m_tasks[m_bottom] を設定したかはわかりません。

ロックフリー キューの合理的な議論であるこの記事をチェックしてください。

于 2009-12-02T19:18:06.700 に答える
2

m_bottomおよびメンバーを使用しm_topて配列にインデックスを付けるのは問題があります。InterlockedXxxx() の戻り値を使用して、安全なインデックスを取得できます。IsEmpty() を失う必要があります。マルチスレッドのシナリオでは決して正確ではありません。PopXxx の空のチェックと同じ問題。ミューテックスなしでそれを機能させる方法がわかりません。

于 2009-12-02T20:03:09.807 に答える
1

このようなほとんど不可能なことを行うための鍵は、InterlockedCompareExchangeを使用することです。（これはWin32が使用する名前ですが、マルチスレッド対応のプラットフォームには、InterlockedCompareExchangeに相当するものがあります）。

アイデアは、構造のコピーを作成することです（これは、アトミック読み取りを実行するのに十分小さくなければなりません（64、または移植性を処理できる場合は、x86で128ビット）。

提案された更新で別のコピーを作成し、ロジックを実行してコピーを更新してから、InterlockedCompareExchangeを使用して「実際の」構造を更新します。InterlockedCompareExchangeが行うことは、値が状態更新前に開始した値であることをアトミックに確認し、それがまだその値である場合は、新しい状態で値をアトミックに更新します。通常、これは無限ループに包まれており、他の誰かが途中で値を変更しなくなるまで試行を続けます。大まかにパターンは次のとおりです。

union State
{
    struct
    {
        short a;
        short b;
    };
    uint32_t volatile rawState;
} state;

void DoSomething()
{
    // Keep looping until nobody else changed it behind our back
    for (;;)
    {
        state origState;
        state newState;

        // It's important that you only read the state once per try
        origState.rawState = state.rawState;
        // This must copy origState, NOT read the state again
        newState.rawState = origState.rawState;

        // Now you can do something impossible to do atomically...
        // This example takes a lot of cycles, there is huge
        // opportunity for another thread to come in and change
        // it during this update
        if (newState.b == 3 || newState.b % 6 != 0)
        {
            newState.a++;
        }

        // Now we atomically update the state,
        // this ONLY changes state.rawState if it's still == origState.rawState
        // In either case, InterlockedCompareExchange returns what value it has now
        if (InterlockedCompareExchange(&state.rawState, newState.rawState,
                origState.rawState) == origState.rawState)
            return;
    }
}

（上記のコードが実際にコンパイルされない場合はご容赦ください-頭のてっぺんから書きました）

素晴らしい。これで、ロックレスアルゴリズムを簡単に作成できます。間違い！問題は、アトミックに更新できるデータの量が大幅に制限されていることです。

一部のロックレスアルゴリズムは、並行スレッドを「支援」する手法を使用します。たとえば、複数のスレッドから更新できるようにしたいリンクリストがある場合、他のスレッドは、「最初」と「最後」のポインターが競合している場合に更新を実行して、それらが「last」が指すノードで、ノードの「next」ポインタはnullではありません。この例では、「最後の」ポインターが間違っていることに気付いたときに、インターロックされた比較交換を使用して、現在のノードをまだ指している場合にのみ、最後のポインターを更新します。

（スピンロックのように）「スピン」またはループするトラップに陥らないでください。「他の」スレッドが何かを終了することを期待しているため、簡単にスピンすることには価値がありますが、そうでない場合もあります。「その他」のスレッドはコンテキストスイッチされており、実行されていない可能性があります。あなたはただCPU時間を食べて、条件が真になるまで回転することによって電気を燃やしている（おそらくラップトップのバッテリーを殺している）。スピンを開始した瞬間に、ロックレスコードをチャックして、ロックを使用して記述した方がよいでしょう。ロックは無制限の回転よりも優れています。

難しいものからばかげたものに移行するために、他のアーキテクチャに取り掛かることができる混乱を考えてみてください。x86/ x64では一般的にかなり寛容ですが、他の「弱く順序付けられた」アーキテクチャに入ると、何かが起こる領域に入ります。意味がありません-メモリの更新はプログラムの順序では発生しないため、他のスレッドが実行していることについての精神的な推論はすべてウィンドウの外に出ます。（x86 / x64にも「ライトコンバイン」と呼ばれるメモリタイプがあり、ビデオメモリの更新時によく使用されますが、フェンスが必要な任意のメモリバッファハードウェアに使用できます）これらのアーキテクチャでは、「メモリフェンス」操作を使用して保証する必要がありますフェンスの前のすべての読み取り/書き込み/両方が（他のコアによって）グローバルに表示されること。書き込みフェンスは、フェンスの前の書き込みが、フェンスの後の書き込みの前にグローバルに表示されることを保証します。読み取りフェンスは、フェンスの後の読み取りがフェンスの前で投機的に実行されないことを保証します。読み取り/書き込みフェンス（別名フルフェンスまたはメモリフェンス）は、両方の保証を行います。柵は非常に高価です。（「フェンス」の代わりに「バリア」という用語を使用する人もいます）

私の提案は、最初にロック/条件変数を使用して実装することです。それを完全に機能させるのに問題がある場合は、ロックレス実装を試みるのは絶望的です。そして、常に測定し、測定し、測定します。ロックを使用した実装のパフォーマンスは完全に良好であることがわかるでしょう。重要な顧客に対してデモを行っているときにのみ表示される、厄介なハングバグを伴う不安定なロックレス実装の不確実性はありません。おそらく、元の問題をより簡単に解決できるものに再定義することで問題を修正できます。おそらく、より大きなアイテム（またはアイテムのバッチ）がコレクションに入るように作業を再構築することで、全体へのプレッシャーを軽減できます。

ロックレス並行アルゴリズムを作成することは非常に困難です（他の場所で1000倍作成されているのを見たことがあると思います）。多くの場合、努力する価値もありません。

于 2011-09-15T08:18:35.950 に答える
0

アーロンが指摘した問題に対処するには、次のようにします。

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

同様に、ポップするには:

ITask* PopTop() {
  int pos = InterlockedIncrement(&m_top);
  if (pos == m_bottom) // This is still subject to a race condition.
      return NULL;
  return m_tasks[pos];
}

m_emptyと の両方をIsEmpty()設計から完全に削除します。IsEmpty によって返される結果は、競合状態の影響を受けます。つまり、その結果を見るまでに、結果が古くなっている可能性があります (つまり、返された結果を見るまでに、キューに関する内容が間違っている可能性があります)。同様に、m_emptyそれがなくてもすでに利用可能な情報の記録、つまり古いデータを生成するためのレシピを提供するだけです。を使用m_emptyしても正しく動作しないことは保証されませんが、バグの可能性が大幅に増加します.

コードの暫定的な性質によるものだと思いますが、現在、配列の境界に深刻な問題がいくつかあります。配列インデックスを強制的に循環させるために何もしていないため、17 番目のタスクをキューにプッシュしようとするとすぐに大きな問題が発生します。

編集：コメントに記載されている競合状態は非常に深刻であることを指摘しておく必要があります-そしてそれだけではありません。元のコードより多少改善されていますが、これを正しく動作するコードと間違えてはなりません。

ロックを使用しない正しいコードを書くことは、ロックを使用する正しいコードを書くことよりもかなり難しいと思います。ロックを使用するコードをしっかりと理解せずにロックを行った人を私は知りません。元のコードに基づいて、ロックを使用するキューのコードを記述して理解することから始める方がはるかに良いと思います.ロックフリーコードの試み。

于 2009-12-02T20:03:53.637 に答える