Clever Geek Handbook

ロックレスアルゴリズム：作成、書き込み、（再試行）モデル

前回実装したアトミック乗算は、より一般的なモデルの例であり、レイモンドは「do、write、（try try）」と呼びました。 



 for（;;）{
  //シェア変数の初期値を取得し、
  //変更する予定の
  oldValue = sharedVariable;

  ...他のパラメーターの初期値を取得...

  newValue = ...を使用して新しい値を計算します
                 oldValueと他のパラメーターのコピー...

  // Xxxの代わりに、Acquire、Release、または何もない場合があります
  if（InterlockedCompareExchangeXxx（
             ＆sharedVariable、
             newValue、oldValue）== oldValue）{
  休憩;  //記録に失敗しました
  }

  ... newValueを削除...

 } //再試行


新しい値を計算し、 InterlockedCompareExchange



呼び出して、値が変更されていない場合にのみ共有変数InterlockedCompareExchange



書き込みます。 変更されている場合は、別のストリームが合格しています。 この場合、次回から誰も「私たちをカット」しないことを期待して、最初から新しい方法で操作を実行しようとします。



「do、write、try again」モデルは、変数の値の更新を最初に開始するスレッドが最初に「レース」に勝つことを保証しないことを理解することが重要です。 「失敗」ストリームは、各試行で、より高速のライバルに何度も譲歩する可能性があります。 理論的には 、彼が開始した操作をまったく完了しない可能性があります （ただし、彼を追い越す各ストリームは自分で完了します）。 この機能は、通常待機キューを実装するロックとは対照的に、ロックレスアルゴリズムに典型的です。



翻訳者はあえて自分の類推を思いつきました。マクドナルドの興行所は城であり、その背後には待っている客の列があります。 チェックアウトに立っているクライアントがポケットにささいなことを詰め込んでいる場合、残りのクライアントとレジ係は予期せずに動き回っています。 システム全体がアイドル状態です。 一方、レストランのウェイターは城のない資源です。 各クライアントは彼に電話して昼食の代金を支払います。 しかし、別のクライアントはウェイターを途中で「振って」傍受できます。 彼が最終的にあなたのテーブルに着くまで、ウェイターが何回気を散らすかはわかりません。 しかし、一方で、彼があなたに合わないなら、今彼は誰かに仕えています。 一般に、システムはアイドル状態ではありません。





最後の投稿のInterlockedMultiply



関数は、ここで与えられたテンプレートにほぼそのまま対応しています。「別のパラメーター」は、関数パラメーターによって送信される乗数です。 「新しい意味」は作品です。 新しい値の記録が失敗した場合、他の誰かがそれを変更し、操作を再開します。



最後の投稿の静的変数の初期化も「do、write、（try again）」モデルに対応します。「try again」ステージのみが最適化されます。結果は、追い越しストリームによって共通変数に既に書き込まれた値と同じであることがわかります。 したがって、このステップは実行されない場合があります。 変数の初期化の場合、ReleaseバリアントではInterlockedCompareExchange



使用されます。これは、新しい値がメモリ内の他のデータと一緒にのみ有効で（ a



一緒にのみ）、それらの後にのみ書き込む必要があるためです。



モデルのもう1つの「最適化された」バージョンは、「do、write、（despair）」です。 ループもありません。新しい値の書き込みに失敗した場合、関数は失敗が致命的であると見なし、それ以上の試行を控えます。 これは、たとえばTryEnterCriticalSection



です。 InterlockedCompareExchangeAcquire



使用します。クリティカルセクション内から行われた変更は、セクションがビジーであることを記録する前にメモリに書き込まないでください。



共通変数が数値ではなくポインターである場合、同じポインターが新しいオブジェクトを指しているときに、前述の「ABAの問題」が発生しないように注意する必要があります。 静的オブジェクトの初期化に追加の困難は必要ありません。ポインターはNULLから何かにしか変更できず、非NULLになるとポインターは変更されなくなります。 ポインターを任意に変更できる場合、原則として、このポインターと「バージョン番号」は共通の変数に結合され、ポインターの変更ごとに増加します。



次の「do、write、（try again）」モデルの使用例では、バージョン番号は共通変数に保存されます。 まず、2つのヘルパー関数： 



 LONG InterlockedReadAcquire（__ LONG * pl、__ LONG lUnlikely）
 {
   return InterlockedCompareExchangeAcquire（pl、lUnlikely、lUnlikely）;
 }

 LONG InterlockedReadRelease（__ LONG * pl、__ LONG lUnlikely）
 {
   return InterlockedCompareExchangeRelease（pl、lUnlikely、lUnlikely）;
 }


LONG変数を直接読み取るのとは異なり、これらの関数は、メモリに書き込まれる順序に制限を課します。 InterlockedCompareExchange



操作の比較された値と新しい値は同じであるため、チェックされた値は操作のどの結果でも変更されません。 実行されるアクションはコードに似ています： 

 if（* pl == lUnlikely）* pl = lUnlikely;


lUnlikely



としてlUnlikely



レイモンドは、ほとんどの場合割り当てが実行されず、キャッシュブロックがダーティにならないように、ありそうもない値を選択することをお勧めします。 （すべてのプロセッサではなく、これによりメモリへの書き込みを防ぐことができますが、このトリックは不要ではありません。）



私たちの例： 



 LONG g_lColorChange;  //カラーバージョン番号

 ...
ケースWM_SYSCOLORCHANGE：
  InterlockedIncrement（＆g_lColorChange）;
  ...

 int CalculateSomethingAboutSystemColors（）
 {
  LONG lColorChangeStart;
  {
   lColorChangeStart = InterlockedReadAcquire（＆g_lColorChange、-1）;
   COLORREF clrWindow = GetSysColor（COLOR_WINDOW）;
   COLORREF clrHighlight = GetSysColor（COLOR_HIGHLIGHT）;
   ... GetSysColorを使用したその他の計算（...）
  } while（InterlockedReadRelease（
                        ＆g_lColorChange、-1）！= lColorChangeStart）;
  return iResult;
 }


古いバージョン番号の値を取得して、計算を開始します。 Acquire操作で取得するため、計算に使用するカラー値の前に、読み取られたバージョン番号がメモリに書き込まれます。

計算が完了すると、現在のバージョン番号と保存されているバージョン番号を比較します。 一致しない場合は、計算中に色が変更されているため、やり直す必要があります。

ABAの問題は、計算中に色が40億回変化した場合に発生する可能性があります。カウンターオーバーフローのため、これはわかりません。 実際には、これは起こりそうにないことは明らかです。


More articles:


All Articles