c++ - ロックフリー マルチスレッド プログラミングとは

Question

マルチスレッド用に独自の「ロックフリー」コンテナを設計したと言う人/記事/SO の投稿を見たことがあります。彼らがパフォーマンスに影響を与えるモジュラス トリック (つまり、各スレッドはモジュロに基づいてのみ挿入できる) を使用していないと仮定すると、データ構造をマルチスレッド化するだけでなく、ロックフリーにすることはできますか?

この質問は、C および C++ を対象としています。

Answer 1

ロックフリー プログラミングの鍵は、ハードウェア固有のアトミック操作を使用することです。

実際のところ、ロック自体でさえ、これらのアトミック操作を使用する必要があります!

しかし、ロックされたプログラミングとロックフリーのプログラミングの違いは、ロックフリーのプログラムは単一のスレッドによって完全に停止されることは決してないということです。対照的に、ロック プログラムで 1 つのスレッドがロックを取得した後、無期限に中断されると、プログラム全体がブロックされ、処理を進めることができなくなります。対照的に、ロックのないプログラムは、個々のスレッドが無期限に中断された場合でも進行できます。

簡単な例を次に示します。同時カウンターのインクリメント。両方とも「スレッドセーフ」である、つまり複数回同時に呼び出すことができる 2 つのバージョンを紹介します。最初のロックされたバージョン:

int counter = 0;
std::mutex counter_mutex;

void increment_with_lock()
{
    std::lock_guard<std::mutex> _(counter_mutex);
    ++counter;
}

ロックフリーバージョン:

std::atomic<int> counter(0);

void increment_lockfree()
{
    ++counter;
}

ここで、数百のスレッドすべてがincrement_*関数を同時に呼び出すと想像してください。ロックされたバージョンでは、ロックを保持しているスレッドがミューテックスのロックを解除するまで、スレッドは進行できません。対照的に、ロックフリー バージョンでは、すべてのスレッドが処理を進めることができます。スレッドが保留された場合、そのスレッドはその仕事の分担を果たせなくなりますが、他の誰もが自分の仕事を続けることができます。

一般に、ロックフリー プログラミングはスループットと平均レイテンシ スループットを予測可能なレイテンシと引き換えにすることに注意してください。つまり、ロックのないプログラムは通常、競合が多すぎない場合 (アトミック操作は遅く、システムの残りの部分の多くに影響を与えるため)、対応するロック プログラムよりも処理量が少なくなりますが、予期せぬ事態が発生しないことが保証されます。大きなレイテンシ。

Answer 2

ロックの場合、ロックを取得し、他の誰も干渉できないことを認識して作業を行い、ロックを解放するという考え方です。

「ロックフリー」の場合、別の場所で作業を行い、この作業をアトミックに「可視状態」にコミットしようとし、失敗した場合は再試行するという考え方です。

「ロックフリー」の問題は次のとおりです。

• 自明ではないものに対してロックフリーのアルゴリズムを設計するのは困難です。これは、「アトミック コミット」部分を実行する方法が非常に限られているためです (多くの場合、ポインターを別のポインターに置き換えるアトミックな「比較と交換」に依存しています)。
• 競合がある場合、破棄/再試行される作業を繰り返し実行しているため、ロックよりもパフォーマンスが低下します
• 正しくて「公平」なロックフリーのアルゴリズムを設計することは事実上不可能です。これは、(競合の下で) いくつかのタスクは幸運である可能性があり (そして繰り返し作業をコミットして進歩する)、いくつかは非常に不運である (そして失敗と再試行を繰り返す) 可能性があることを意味します。

これらの組み合わせは、競合が少ない比較的単純なものにのみ適していることを意味します。

研究者は、ロックのないリンク リスト (および FIFO/FILO キュー) やロックのないツリーなどを設計しました。これほど複雑なものはないと思います。これらがどのように機能するかについては、難しいため複雑です。最も健全なアプローチは、関心のあるデータ構造のタイプを特定し、Web を検索して、そのデータ構造のロックフリー アルゴリズムに関連する調査を行うことです。

また、「ブロックフリー」と呼ばれるものがあることにも注意してください。これは、常に作業をコミットでき、再試行する必要がないことを除いて、ロックフリーに似ています。ブロックフリー アルゴリズムを設計するのはさらに困難ですが、競合は問題にならないため、ロックフリーに関する他の 2 つの問題はなくなります。注：Kerrek SBの回答の「同時カウンター」の例は、まったくロックフリーではありませんが、実際にはブロックフリーです。

Answer 3

新しい C および C++ 標準 (C11 および C++11) ではスレッドが導入され、スレッドはアトミック データ型と操作を共有しました。アトミック操作は、2 つのスレッド間で競合が発生する操作を保証します。スレッドがそのような操作から戻ると、操作が完全に完了したことを確認できます。

このようなアトミック操作に対する一般的なプロセッサ サポートは、コンペア アンド スワップ (CAS) またはアトミック インクリメント用の最新のプロセッサに存在します。

アトミックであることに加えて、データ型は「ロックフリー」プロパティを持つことができます。これはおそらく「ステートレス」という造語であるはずです。このプロパティは、割り込みハンドラーによって中断されたり、別のスレッドの読み取りが途中で中断されたりした場合でも、そのような型に対する操作がオブジェクトを中間状態のままにしないことを意味するためです。更新の。

いくつかのアトミック型はロックフリーである場合もあれば (そうでない場合もあります)、そのプロパティをテストするためのマクロがあります。ロックフリーであることが保証されているタイプが常に 1 つあります。つまり、atomic_flagです。

Answer 4

「ロックフリー」の考え方は、実際にはロックを持たないということではなく、ほとんどの操作でロックを使用しないようにするいくつかの手法を使用して、ロックおよび/またはクリティカルセクションの数を最小限に抑えることです。

これは、オプティミスティック デザインまたはトランザクション メモリを使用して実現できます。この場合、すべての操作に対してデータをロックするのではなく、特定のポイント (トランザクション メモリでトランザクションを実行するとき、またはオプティミスティック デザインでロールバックする必要があるとき) でのみデータをロックします。

他の選択肢は、 CAS (Compare And Swap)などの一部のコマンドのアトミック実装に基づいており、実装が与えられた場合でもコンセンサス問題を解決することができます。参照に対してスワップを実行する (そして、共通データで作業しているスレッドがない) ことにより、CAS メカニズムにより、ロックのない楽観的な設計を簡単に実装できます (まだ誰もデータを変更していない場合に限り、新しいデータにスワップします。アトミックに行われます)。

ただし、これらの 1 つに基礎となるメカニズムを実装するには、いくつかのロックが使用される可能性が高くなりますが、これらの手法が正しく使用されている場合、データがロックされる時間は (想定) 最小限に抑えられます。