3

LRUキャッシュの場合、「シンプル、高速、実用的な非ブロッキングおよびブロッキング並行キューアルゴリズム」で説明されているものと同様のロックフリーキューのアルゴリズムが必要です。

ただし、LRUキューを維持するには、キュー内のノードを削除する可能性も必要になります（末尾のノードを除く）。

私の考えは、CAS操作でノードを削除済みとしてマークし、その後、キュー内から削除されたノードを削除する単一のクリーンアップスレッドを使用することです。

ロックフリーアルゴリズムの作成は、私が最初に予想したよりも複雑であることがわかりました。だから、私の質問は：
そのようなアルゴリズムはすでに利用可能ですか？

これは私が現在使用している構造です：

全般的

  • ノードの構造は次のとおりです。struct{e*entry、nextポインター、prevポインター、state uint32}
  • 新しいノードごとに複数のメモリが割り当てられるのを避けるために、ノードの配列が割り当てられます。
  • ノードへのポインターは、配列インデックス値と更新カウンターで構成され、単一のuint64に多重化されます。
  • ノード状態は、ノードが削除されたかどうかを示す上位ビットで構成されます。残りのビットは更新カウンターとして使用されます

エンキュー

  • 補助キューは未使用のノードのリストを保持し、「新しい」ノードは補助キューからデキューを介してフェッチされ、デフォルトに設定されます
  • node.prevは、新しいノードがエンキューされる前に現在のテールに設定されます

デキュー

  • head.next.prevは、ヘッドデキューの前にNIL値にCASされます。head.next.prevがCLEANUP（クリーンアップスレッドによって処理されている）に設定されている場合、デキューは許可されず、スレッドはCPUを解放し、最初からやり直します。
  • 削除されていない状態のノードのデキューが成功すると、状態はCASで削除され、ノードは補助キューに戻されます。失敗すると（または状態がすでに削除済みに設定されている場合）、デキューされたnode.prevはNILからCLEANUPに変更され、ノードがデキューされたことをクリーンアップスレッドに通知します。その後、削除されていないノードが正常にデキューされ、CASで削除されるまで、デキューは最初からやり直します。

消去

  • キュー内の削除をマークするために、状態はCASで削除され、成功するとクリーンアップキューに渡されます。失敗しても何も行われませんが、関数は戻ります。

クリーンアップスレッド

  • node.prevがCLEANUPの場合、Dequeueはそれをキューから削除しました。ノードは補助キューに戻されます。
  • node.prevがNILの場合、ノードはヘッドになるか、ヘッドになるか、またはデキューされようとしています。node == headの場合、クリーンアップスレッドはデキューを実行しようとします（状態が削除済みに変更されます）。失敗すると、クリーンアッププロセスが最初から始まります。
  • nodeが別のノードに設定されている場合、node.prevはCLEANUPにCASされます。これにより、head.next == nodeになるとすぐに、デキューが行われるのを防ぎます。成功すると、二重リンクリストを使用してキュー内の削除が行われます。失敗すると、クリーンアッププロセスが最初から始まります。

Node.prevは、次のことを伝えるために使用されます。

  • キューの前にあるノード
  • ノードがヘッドになりそうです/ヘッドです
  • ノードはクリーンアップスレッドによって処理されています
  • ノードはデキューされます
4

1 に答える 1

3

キュー内の要素の論理的な削除は実際には問題があります。そのため、このための論文は見つかりません。また、これは非常に一般的なデータ構造に追加された非常に特殊な機能であり、これが論文が見つからないもう1つの理由です。一般的なデータ構造の論文しか見つかりません。

問題のある問題は2つあります。まず、キューは通常、カーソルをサポートするようには設計されていません。次に、論理的に削除したい要素にアクセスしても安全かどうかを知ることです。たとえば、すでにデキューされ、割り当てが解除されている可能性がありますか？

引用するキューは、ポインターとカウンターのペアを使用してABAを解決します。これは、フリーリストの使用を意味します。このコンテキストでは、要素の割り当てが解除されていないことを常に確認できます。

カーソルに関しては、デキューで入力してから、キューを下ってエンキューポインタに進む必要があります。しかし、次の要素に移動する前に、表示している要素がデキューされた場合はどうなりますか？次に、キューから削除され、フリーリストにある要素の次のポインタをたどります。実際、一般に、ある要素から次の要素にカーソルが移動する間、キューには何でも起こり得ます。これには、完全なキューの削除や、さまざまな要素を使用した再作成が含まれます。

したがって、カーソルを明示的にサポートするリンクリストが必要です。

使用している言語について言及していませんか？

于 2012-09-11T12:39:41.267 に答える