c++ - スケーラブルロックとは何ですか？

Question

スケーラブルロックとは何ですか？また、スケーラブルでないロックとはどのように異なりますか？私はこの用語をTBBrw-lockのコンテキストで最初に見ましたが、どちらを使用するかを決めることができませんでした。

さらに、ライターよりもリーダーを優先するrw-lockはありますか？

Answer 1

「スケーラブル ロック」または「非スケーラブル ロック」という用語の正式な定義はありません。これが意味することは、ロックの競合が多い場合でも、一部のロック アルゴリズム、テクニック、または実装が適切に機能し、そうでないものもあるということです。

アルゴリズムに問題がある場合もあります。たとえば、優先度継承の単純な実装では、ロックを解放するために O(n) 作業が必要になる場合があります。ここで、n は待機中のスレッドの数です。これは、待機中のスレッドごとに O(n^2) の作業が行われることを意味します。

ハードウェアに問題がある場合もあります。単純なスピンロック (たとえば、ロック キャッシュ ラインが共有され、取得機能がバックオフしない実装) は、単一のバス インターコネクトを使用する SMP ハードウェアでは拡張できません。 CPU 相互接続は、単一の競合点です。同時に同じロックを取得しようとしている n 個の CPU がある場合、ロックを取得するために O(n) バス トラフィックが発生する可能性があります。繰り返しますが、これは n 個の CPU すべてが満たされるのに O(n^2) 時間かかることを意味します。

一般に、次の 2 つの条件が満たされない限り、スケーラブルでないロックは避ける必要があります。

1. 争いは軽い。
2. クリティカル セクションは非常に短いです。

2つの条件が満たされていることを本当に知っておく必要があります。クリティカル セクションは、コードの行数に関しては短いかもしれませんが、経過時間は短くありません。疑わしい場合は、スケーラブルなロックを使用し、パフォーマンスの問題を引き起こすと測定されたものを後で修正します。

最後の質問ですが、読者に有利な市販の読み書きロックについては知りません。実際、pthreads を含め、ほとんどの API はポリシーを指定していません (厄介なことに)。

私の最初のコメントは、あなたはおそらくそれを望んでいないということです。競合が多い場合は、どちらかを優先するとスループットが低下します。競合が少ない場合は、違いはありません。完全に公平なポリシーで rw ロックを使用しないと考えることができる唯一の理由は、尊重しなければならないスレッドの優先度があるため、最も優先度の高いスレッドを優先したい場合です。

ただし、必要に応じて、いつでも自分でロールすることができます。必要なのは、いくつかのフラグ (「readers can go now」用と「a writer can go now」用)、フラグを保護する条件変数、条件変数を保護する単一のミューテックス、および方法を示すいくつかのカウンターだけです。多くの読者、ライターが待っています。必要なのはそれだけです。これを実装することは非常に有益です。