ロックレスアルゴリズム：不安定なキャッシュ

（ 「ロックフリー」の概念のロシア語の翻訳がまだ文学で確立されていないという事実は、そのような翻訳がそうであってはならないことを私にまったく納得させない。）

アプリケーションのパフォーマンスを分析した結果、プロセッサ時間のかなりの部分が何らかの計算関数に費やされており、さらに、この関数は同じパラメーターで繰り返し呼び出され、同じ計算を繰り返し実行していると仮定します。単純な最適化は、初期データと最後の計算の結果が保存される1つのレコードからのキャッシュを要求します。

 BOOL IsPrime（int n）
 {
  static int nLast = 1;
  static BOOL fLastIsPrime = FALSE;

  //パラメータ値が前回から変更されていない場合、
  //完成した結果を使用します
  if（n == nLast）fLastIsPrimeを返します。

  //新しい結果を計算して記憶します
  nLast = n;
  fLastIsPrime = slow_IsPrime（n）;
  return fLastIsPrime;
 }

もちろん、このコードはスレッドセーフです。1つのスレッドがslow_IsPrime()呼び出し内にある場合、 slow_IsPrime()呼び出した他のスレッドはfLastIsPrimeとfLastIsPrime値を互いに矛盾させます。

簡単な解決策は、コードをクリティカルセクションに含めることです。しかし、シンプルさはパフォーマンスを犠牲にします：たとえば、 nLast = 5、 fLastIsPrime = TRUEで、2つのスレッドが同時にIsPrime(5)呼び出す場合、それらを並べる必要はまったくありません。キャッシュされた値を同時に使用することを妨げるものはありません。

ロックなしでキャッシュを実装する方法を見てみましょう。最後の投稿の 2つのトリックを一度に使用します。データが変更されるたびにバージョン番号を更新することと、キャッシュエントリを同期するための「do、write、（despair）」モデルです。

 #define IsLocked（l）（（l）＆1）

 BOOL IsPrime（int n）
 {
  static int nLast = 1;
  static BOOL fLastIsPrime = FALSE;
  static LONG lCounter = 0;

  //キャッシュから値を取得しようとします
  LONG lCounterStart = InterlockedReadAcquire（＆lCounter、-1）;
  if（！IsLocked（lCounterStart）&& n == nLast）{
   BOOL fResult = fLastIsPrime;
   //誰も私たちの背後にあるキャッシュに触れませんでしたか？
   if（InterlockedReadRelease（＆lCounter、-1）== lCounterStart）
    return fResult;
  }

  //キャッシュからの読み取りに失敗したか、値が適合しませんでした：
  //通常の方法で計算します
  BOOL fIsPrime = slow_IsPrime（n）;

  //キャッシュに値を保存しようとします
  lCounterStart = lCounter;
  if（！IsLocked（lCounterStart）&&
      InterlockedCompareExchangeAcquire（＆lCounter、
               lCounterStart + 1、lCounterStart）== lCounterStart）{
   nLast = n;
   fLastIsPrime = fIsPrime;
   InterlockedCompareExchangeRelease（＆lCounter、
               lCounterStart + 2、lCounterStart + 1）;
  }
  return fIsPrime;
 }

lCounter最下位ビットは、記録中はキャッシュが「ロック」されることを意味します。残りのビットにはバージョン番号が格納されます。このような組織では、ロック解除とバージョン番号の更新を1つの簡単な操作に組み合わせることができます。

この関数は、キャッシュからの読み取りとキャッシュへの書き込みという2つの部分で構成されています。キャッシュから読み取る場合、最初にAcquire操作でlCounterを読み取り、読み取られたfLastIsPrimeとfLastIsPrimeがバージョン番号の前に書き込まれたことを確認しfLastIsPrime 。読み取った数で判断すると、キャッシュがブロックされていない場合は、パラメーターの最後の値とその結果を読み取ります。結果が適合する場合、それを採用します。ただし、最初に、キャッシュから読み取るときにバージョン番号が変更されていないことを確認する必要があります。変更されている場合は、読み取った値が互いに対応していない可能性があるため、「適切な」結果は実際には信頼できません。

どちらの場合でも、キャッシュされた結果が適合しなかった場合、または読み取りデータが信頼できないことが判明した場合、役に立たないことが判明したキャッシュに手を振って計算を完了します。

キャッシュに書き込むとき、キャッシュがロックされていないことを確認するだけでなく、同時に自分自身でブロックし、最下位ビットを設定します。（キャッシュがブロックされたことが判明した場合でも、怖くないわけではありません。計算結果を書き込まない限り、誰も気分を害することはありません。再計算を避けるために時間を節約することを目的としています。）キャッシュをブロックすることにより、データ、そして1回の操作でInterlockedCompareExchangeReleaseがロックを解除し、バージョン番号を増やします。ロックを解除する前にデータの変更がメモリに書き込まれるように、操作はReleaseである必要があります。

キャッシュの操作の成功はオプションであるという事実を利用します。読み取りと書き込みの両方で、キャッシュがブロックされている場合、理論的には、キャッシュの利点を放棄する方が良いです。自分でやります！」-キャッシュにアクセスする権利を確保するために。冗長な計算を犠牲にして、優先度の逆転などの問題を回避します（優先度の高いスレッドが、優先度の低いスレッドが占有しているロックの解放を待機している場合）。

結果のシステムは完全にロックレスではないことに注意することが重要です。ロックレスアルゴリズムを使用して、実際に効果的なロックを実装しました。書き込みキャッシュをブロックしているスレッドがスタックしている場合、他のすべてのスレッドは実行を続けますが、キャッシュを使用できなくなります。

TryEnterCriticalSectionを使用して、同様のシステムを実装できます。

 BOOL IsPrime（int n）
 {
  static int nLast = 1;
  static BOOL fLastIsPrime = FALSE;
  BOOL fHaveAnswer = FALSE;
  BOOL fIsPrime;

  //キャッシュから値を取得しようとします
  if（TryEnterCriticalSection（＆g_cs））{
   if（n == nLast）{
    fHaveAnswer = TRUE;
    fIsPrime = fLastIsPrime;
   }
   LeaveCriticalSection（＆g_cs）;
  }
  if（fHaveAnswer）fIsPrimeを返します。

  //クリティカルセクションがビジーであるか、値が適合しませんでした。
  //通常の方法で計算します
  fIsPrime = slow_IsPrime（n）;

  //キャッシュに値を保存しようとします
  if（TryEnterCriticalSection（＆g_cs））{
   nLast = n;
   fLastIsPrime = fIsPrime;
   LeaveCriticalSection（＆g_cs）;
  }
  return fIsPrime;
 }

キャッシュから読み取るスレッドは互いに干渉しないため、最初の方法の方が適しています。クリティカルセクションの同時読み取りは使用できません。

Windows 7以降では、スリムなリーダーライターロックを有効にすることもできます。

 BOOL IsPrime（int n）
 {
  static int nLast = 1;
  static BOOL fLastIsPrime = FALSE;
  BOOL fHaveAnswer = FALSE;
  BOOL fIsPrime;

  //キャッシュから値を取得しようとします
  if（TryAcquireSRWLockShared（＆g_lock））{
   if（n == nLast）{
    fHaveAnswer = TRUE;
    fIsPrime = fLastIsPrime;
   }
   ReleaseSRWLockShared（＆g_lock）;
  }
  if（fHaveAnswer）fIsPrimeを返します。

  //キャッシュが書き込み用にロックされているか、値が適合していません。
  //通常の方法で計算します
  fIsPrime = slow_IsPrime（n）;

  //キャッシュに値を保存しようとします
  if（TryAcquireSRWLockExclusive（＆g_lock））{
   nLast = n;
   fLastIsPrime = fIsPrime;
   LeaveSRWLockExclusive（＆g_lock）;
  }
  return fIsPrime;
 }

ただし、この実装でも、キャッシュから読み取るスレッドはキャッシュへの書き込みを妨げる可能性があります。一方、最初の「スピリットレス」実装では、同時録音の試行のみが競合につながります。 IsPrime()が1つの値（たとえば、13）で複数回呼び出され、次に別の値（たとえば、17）で何回も呼び出される場合IsPrime()の結果がキャッシュされているかどうかをチェックするスレッドのフローは、単一のスレッドをスキップしません17 の結果をキャッシュします！キャッシュの負荷が非常に高い場合（これが追加した理由です！）-スリムリーダー/ライターロックに基づく実装により、キャッシュがほとんど役に立たないことがわかります。

ロックレスアルゴリズム：不安定なキャッシュ

More articles: