ブロッキング アルゴリズムとノンブロッキング アルゴリズム

ブロッキング、ノンブロッキング、ロックフリー、ウェイトフリー。これらの各用語は、並行環境で実行されたときのアルゴリズムの重要な特性を表しています。したがって、プログラムの実行時の動作について推論することは、多くの場合、アルゴリズムを適切なバケツに入れることを意味します。したがって、この投稿はバケットに関するものです。

アルゴリズムは、ブロックまたは非ブロックの 2 つのバケットのいずれかに分類されます。

まずブロッキングについて話しましょう。

ブロッキング

直感的には、アルゴリズムのブロッキングが何を意味するかは非常に明確です。しかし、同時実行性は直感に関するものではなく、正確な用語に関するものです。ブロッキングを定義する最も簡単な方法は、ノンブロッキングを使用して定義することです。

  • ノンブロッキング: スレッドの失敗または一時停止が別のスレッドの失敗または一時停止を引き起こすことができない場合、そのアルゴリズムはノンブロッキングと呼ばれます (実際の Java 同時実行)

この定義には、ロックについての言葉はありません。それは正しい。ノンブロッキングはより広い用語です。

プログラムをブロックするのはとても簡単です。典型的な使用例は、複数のミューテックスを使用し、それらを異なるシーケンスでロックすることです。良いタイミングで、デッドロックが発生しました。しかし、ブロッキング動作を生成する方法は他にもたくさんあります。

リソースを待たなければならないたびに、ブロックが可能です。

リソースへのアクセスを同期するためのいくつかの例を次に示します:

  • wait 付きの条件変数
  • 待つか手に入れるかの未来

スレッドの結合呼び出しでさえ、スレッドをブロックするために使用できます。

// deadlockWait.cpp

#include <iostream>
#include <mutex>
#include <string>
#include <thread>

std::mutex coutMutex;

int main(){

 std::thread t([]{
 std::cout << "Still waiting ..." << std::endl; // 2
 std::lock_guard<std::mutex> lockGuard(coutMutex); // 3
 std::cout << "child: " << std::this_thread::get_id() << std::endl;}
 );

 {

 std::lock_guard<std::mutex> lockGuard(coutMutex); // 1
 std::cout << "creator: " << std::this_thread::get_id() << std::endl;

 t.join(); // 5

 } // 4

}

プログラムの実行はすぐにブロックされます。

何が起こっている?作成者スレッドは (1) ミューテックスをロックします。ここで、子スレッドが実行されます (2)。式 (3) のミューテックスを取得するには、作成者スレッドが最初にロックを解除する必要があります。ただし、作成者スレッドは、lockGuard (1) が範囲外 (4) に入った場合にのみミューテックスのロックを解除します。子スレッドは最初にミューテックス coutMutex をロックする必要があるため、これは決して起こりません。

ノンブロッキング アルゴリズムを見てみましょう。

ノンブロッキング

ノンブロッキング アルゴリズムの主なカテゴリは、ロックフリーとウェイトフリーです。各ウェイトフリー アルゴリズムはロックフリーであり、各ロックフリーはノンブロッキングです。ノンブロッキングとロックフリーは同じではありません。オブストラクションフリーと呼ばれる追加の保証がありますが、あまり関連性がないため、この投稿では無視します.

ノンブロッキング アルゴリズムは通常、CAS 命令で実装されます。 CAS はコンペア アンド スワップの略です。 CAS は、C++ では compare_exchange_strong または compare_exchange_weak と呼ばれます。

この投稿では、強力なバージョンのみを参照します。詳細については、私の以前の投稿 The Atomic Boolean を参照してください。両方の操作の重要なアイデアは、atomicValue.compare_exchange_strong(expected, desired) の呼び出しがアトミックな方法で次のルールに従うことです。

  • atomicValue と expected のアトミック比較が true を返す場合、atomicValue は同じアトミック操作で必要に応じて設定されます。
  • 比較で false が返された場合、expected は atomicValue に設定されます。

それでは、ロックフリーとウェイトフリーを詳しく見てみましょう。

まずはロックフリー、ウエイトフリーの定義。両方の定義は非常に似ています。したがって、それらをまとめて定義することは非常に理にかなっています。

  • ロックフリー: システム全体の進行が保証されている場合、ノンブロッキング アルゴリズムはロックフリーです。
  • 待ち時間なし: スレッドごとの進行が保証されている場合、ノンブロッキング アルゴリズムはウェイトフリーです。

ロックフリー

// fetch_mult.cpp

#include <atomic>
#include <iostream>

template <typename T>
T fetch_mult(std::atomic<T>& shared, T mult){ // 1
 T oldValue = shared.load(); // 2
 while (!shared.compare_exchange_strong(oldValue, oldValue * mult)); // 3
 return oldValue;
}

int main(){
 std::atomic<int> myInt{5};
 std::cout << myInt << std::endl; 
 fetch_mult(myInt,5);
 std::cout << myInt << std::endl; 
}

アルゴリズム fetch_mult (1) は、mult が共有する std::atomic を乗算します。重要な観察は、古い値 T oldValue =shared Load の読み取り (2) と新しい値との比較 (3) の間に小さな時間枠があることです。したがって、別のスレッドがいつでも起動して oldValue を変更できます。スレッドのこのような不適切なインターリーブについて考えると、スレッドごとの進行が保証されないことがわかります。

したがって、このアルゴリズムはロックフリーですが、ウェイトフリーではありません。

これがプログラムの出力です。

ロックフリー アルゴリズムはシステム全体の進行を保証しますが、待機フリー アルゴリズムはスレッドごとの進行を保証します。

ウェイトフリー

最後の例のロックフリー アルゴリズムについて考えるとわかるでしょう。 compare_exchange_strong 呼び出しには同期が含まれます。最初に古い値を読み取り、初期条件が既に成立している場合は新しい値を更新します。初期条件が成立する場合、新しい値を公開します。そうでない場合は、呼び出しを while ループに入れてもう一度実行します。したがって、compare_exchange_strong はアトミック トランザクションのように動作します。

次のプログラムの重要な部分は同期する必要はありません。

// relaxed.cpp

#include <vector>
#include <iostream>
#include <thread>
#include <atomic>
 
std::atomic<int> cnt = {0};
 
void add(){ // 1
 for (int n = 0; n < 1000; ++n) {
 cnt.fetch_add(1, std::memory_order_relaxed); // 2
 }
}
 
int main()
{
 std::vector<std::thread> v;
 for (int n = 0; n < 10; ++n) {
 v.emplace_back(add);
 }
 for (auto& t : v) {
 t.join();
 }
 std::cout << "Final counter value is " << cnt << '\n';
}

関数 add (1) を詳しく見てみましょう。式 (2) には同期は含まれていません。値 1 がアトミック cnt に追加されるだけです。

そして、これがプログラムの出力です。常に 10000 を取得します。10 スレッドで値が 1000 回インクリメントされるためです。

簡単にするために、この投稿では、ブロッキングのサブセットとしての飢餓フリーや、ウェイトフリーのサブセットとして制限されたウェイトフリーなど、他のいくつかの保証を無視しました。詳細はブログ Concurrency Freaks で読むことができます。

次は?

次の投稿では、好奇心について書きます。これはいわゆる ABA 問題であり、CAS 命令の一種の誤検出ケースです。つまり、CAS 命令の古い値は同じように見えますが、その間に変更されました。