ノンブロッキングアルゴリズムの利点-パフォーマンスだけでなく、それほど多くない

シリーズの最後の投稿が、ハードコアすぎることが判明した以前の3つの記事とは異なり、ハブラの大衆に言語学的な関心をもたらすだけではないことを願っています。

一連のノンブロッキングアルゴリズムに関するChenのコメンテーターの1人は、これらのより複雑なアルゴリズムがクリティカルセクションなどの単純なブロッキングプリミティブを大幅に上回ることができる条件を疑問に思いました。

彼は、パフォーマンスを測定することにより、単純なアルゴリズムから複雑なアルゴリズムへの移行を正当化することは絶対に正しいです。単純なアルゴリズムがそのタスクを十分に実行する場合、良いものから良いものを探すものは何もありません。

ただし、非ブロッキング同期の利点は、通常のブロッキングのプリミティブと比較してパフォーマンスが向上することに限定されません。（この投稿の後半では、完全に非ブロッキングの同期に移行することなく、これらの明白な利点を得る方法を説明します。）

トリッキーなノンブロッキングアルゴリズムではなく、シングルトンの初期化を保護するために、通常のクリティカルセクションを使用することにしました。

 CRITICAL_SECTION g_csSingletonX;
 X * g_px = NULL;

 X * GetSingletonX（）
 {
 EnterCriticalSection（＆g_csSingletonX）;
 if（g_px == NULL）
 {
 g_px = new（nothrow）X（）;
 }
 LeaveCriticalSection（＆g_csSingletonX）;
 return g_px;
 }

X()コンストラクターがロック自体を使用すると問題が発生します。そのため、デッドロックが発生しないように、プログラムはロックの階層を定義し、ロックを厳密にその順序でキャプチャする必要があります。（さらに、コンストラクターコードがユーザーによって作成されておらず、その中のロックの順序に影響を与えることができない場合、この段階で敗北を認める必要があります。）

ロックの階層の構築中に、一部のロックは常に同じ順序でキャプチャできるとは限らないため、それらを組み合わせる必要があることが判明する場合があります。同期はますます厳しくなっています。たとえば、 g_csSingletonXをクラスXのすべてのメソッドのロックと同様に、すべてのシングルトンコンストラクターのロックと組み合わせる必要があることがg_csSingletonXする場合があります。

 CRITICAL_SECTION g_csCommon;

 X * GetSingletonX（）
 {
 EnterCriticalSection（＆g_csCommon）;
 if（g_px == NULL）
 {
 g_px = new（nothrow）X（）;
 }
 LeaveCriticalSection（＆g_csCommon）;
 return g_px;
 }

 Y * GetSingletonY（）
 {
 EnterCriticalSection（＆g_csCommon）;
 if（g_py == NULL）
 {
 g_py = new（nothrow）Y（）;
 }
 LeaveCriticalSection（＆g_csCommon）;
 return g_py;
 }

 void X :: DoSomething（）
 {
 EnterCriticalSection（＆g_csCommon）;
 ..何か..
 LeaveCriticalSection（＆g_csCommon）;
 }

うん！小さく目立たないクリティカルセクションから、多くのスレッドが常に競合しているグローバルブロックが取得されました。

ノンブロッキングアルゴリズムの大きな利点は、ロックがないためデッドロックが発生しないことです。階層はもう必要ありません。（不安定なキャッシュの例のように、非ブロッキング操作から「非ブロッキングロック」を構築している場合を除きます）。ノンブロッキングのもう1つの優れた機能は、ロックがないため、ロックをキャプチャするスレッドがクラッシュしたときに「所有者なし」状態のままにならないことです。 WAIT_ABANDONED場合に正しい操作を続行する方法をWAIT_ABANDONED必要はありません。保護されたデータは常に正しいままであり、正しい状態の1つから次の状態にアトミックに渡されます。

いずれかのコンポーネントでエラーが発生した場合、コンピューターを再起動するだけで作業状態に戻ることができる製品に出会ったことがありますか？ノンブロッキングを使用すると、このように動作しないプログラムを簡単に作成できます。

明らかに従来のブロッキングプリミティブを好む場合でも、最終的にそれらを使用することは非常に便利です！ -次に、非ブロッキングアルゴリズムを詳しく調べる必要があります。次のコードで考えてみましょう：

 CRITICAL_SECTION g_cs;
ゴリラデータg_data;

 void PokeGorilla（倍の強度）
 {
 EnterCriticalSection（＆g_cs）;
 DeformGorilla（強度、およびg_data）;
網状（＆g_data.spline）;
 int stress = CalculateTension（＆g_data.spline）;
 if（stress <25）g_data.mood = RELAXED;
 else if（stress <50）g_data.mood = ANNOYED;
それ以外の場合g_data.mood = ANGRY;
 DeleteObject（g_data.hbmGorilla）;
 g_data.hbmGorilla = RenderGorilla（＆g_data）;
 LeaveCriticalSection（＆g_cs）;
 }

-議論の余地のある場所がいくつかあります。まず、ロックの階層は尊重されますか？たとえば、 Reticulate()関数には、幾何学的操作を保護するロックが必要な場合があります。階層に従って、このロックはg_cs前にg_csする必要があることがg_csするg_csます。

g_csをg_cs競合するスレッドが多数ある場合、 PokeGorilla()がロックを保持する時間を短縮する必要があります。 RenderGorilla()は、おそらく複雑で遅い操作です。（あなたは、リアルな毛皮を描くのがどれほど難しいか知っています。）その後、 RenderGorilla()呼び出し中に、 g_csロックg_csます。

両方の問題の可能な解決策は、非ブロッキング同期への移行です。しかし、それはとても難しいです！（ほぼリアルな毛皮と同じくらい難しい。）ノンブロッキングの利点の80％を得るために、作業の20％しか費やせないでしょうか？

void PokeGorilla(double intensity)
{
//
EnterCriticalSection(&g_cs);
GORILLADATA data = g_data;
LeaveCriticalSection(&g_cs);

//
DeformGorilla(intensity, &data);
Reticulate(&data.spline);
int stress = CalculateTension(&data.spline);
if (stress < 25) data.mood = RELAXED;
else if (stress < 50) data.mood = ANNOYED;
else data.mood = ANGRY;
data.hbmGorilla = RenderGorilla(&data);

//
EnterCriticalSection(&g_cs);
HBITMAP hbmToDelete = g_data.hbmGorilla;
g_data = data;
LeaveCriticalSection(&g_cs);
DeleteObject(hbmToDelete);
}

「do、write」モデルに従って、ゴリラの状態をローカル変数にコピーし、このローカル変数に対してすべてのアクションを実行します。「レチキュレーション」中にロックが解除されるため、ロックの階層に問題はありません。また、ゴリラの描画中にロックも解除されるため、残りのスレッドのアイドル状態が少なくなります。ゴリラの状態が処理されると、再びロックを取得し、変更を記録します。

この場合、ゴリラを最後に突っ込んだ方が勝ちました。実行される状態レコードは、ロックが解除されている間、処理中に行われたすべての変更を上書きします。変更が互いに独立している場合、この動作は許容されます。しかし、ゴリラの感情的な緊張は、突くたびに蓄積すると仮定します。前回のポークの処理中にゴリラが突かれたかどうかを識別する必要があります。突っ込んだ場合は、最終結果の新しいデータを考慮してください。

次に、バージョンカウンターを使用して、「do、write、（try try）」モデルに戻ります。

LONG g_lCounter;

void PokeGorilla(double intensity)
{
BOOL fSuccess;

do {
//
EnterCriticalSection(&g_cs);
GORILLADATA data = g_data;
LONG lCounter = g_lCounter;
LeaveCriticalSection(&g_cs);

//
DeformGorilla(intensity, &data);
Reticulate(&data.spline);
int stress = CalculateTension(&data.spline);
if (stress < 25) data.mood = RELAXED;
else if (stress < 50) data.mood = ANNOYED;
else data.mood = ANGRY;
data.hbmGorilla = RenderGorilla(&data);

//
EnterCriticalSection(&g_cs);
HBITMAP hbmToDelete;
if (lCounter == g_lCounter)
{
hbmToDelete = g_data.hbmGorilla;
g_data = data;
g_lCounter++;
fSuccess = TRUE;
} else {
hbmToDelete = data.hbmGorilla;
fSuccess = FALSE;
}
LeaveCriticalSection(&g_cs);
DeleteObject(hbmToDelete);
} while (!fSuccess);
}

通常のゴリラデータに加えて、バージョン番号を保存し、各ポークごとにバージョン番号を増やします。実際、この番号をGORILLADATA構造GORILLADATAに保存する方が良いでしょう。（いいえ、ゴリラを突かない方が良いでしょう！）ノンブロッキングアルゴリズムでは、 InterlockedCompareExchangeRelease操作でバージョン番号の値を確認します。しかし、 GORILLADATA構造GORILLADATAアトミックに更新GORILLADATAないため、クリティカルセクションを使用してチェックし、同時に更新します。それにもかかわらず、モデルは以前と同じままです。ゴリラが背中の後ろに突っ込んだ場合、得られたすべての結果を捨てて、新しい方法で計算を開始して、両方のポケを最終結果に反映させる必要があります。

ノンブロッキングアルゴリズムの利点-パフォーマンスだけでなく、それほど多くない

More articles: