これは、SMPシステムの割り込みハンドラーで実行する必要があるため、ロックフリーである必要があります。鍵が取れません。
いくつかの値を保持する連続した配列があります。この配列の一部のエントリは「フリー」であり、占有されていません。これらのエントリのリストを作成して、すばやく割り当てることができるようにします。ただし、任意のエントリを割り当てる必要がある場合があります。
したがって、次のことが適切な方法であることがわかります。連続する配列は、値だけでなく、左右のポインターも保持するため、両端キューが作成されます。有効な左/右ポインタを持つのは空き値のみです。dequeへの単なるインデックスアクセスであるため、任意のノードにすばやくアクセスできます。
さて、その核心に：比較的効率的で、任意のノードの削除をサポートできる優れたロックフリーの両端キューアルゴリズムはありますか？
連続した配列は、値だけでなく左右のポインターも保持するため、deque が作成されます。
[をちょきちょきと切る]
さて、肝心なところ: 比較的効率的で、任意のノードの削除をサポートできる、優れたロックフリー deque アルゴリズムはありますか?
任意の要素を削除できる両端キューは、実際には二重にリンクされたリストです。あなたがあきらめた唯一のことは、任意の要素を挿入する機能であり、削除するのは難しい部分です.削除できる場合は、確実に追加できます.
ロックフリーの双方向リンク リストは存在しますが、ガベージ コレクションが必要です。
これはどう; フリーリストがあります。これは利用可能なノードを表します。ノードは実際には配列であるため、それらにインデックスを付けることができます。任意のノードを使用する必要がある場合は、配列にインデックスを付けてから、その要素のフラグを CAS しますが、フリーリストに残します (フリーリストの先頭にないため、もちろんそうする必要があります)。将来的にポップするようになり、すでに使用されている要素をポップしていることに気付いた場合は、空いている要素が見つかるまでポップし続けます。
ガベージ コレクション システムでは、項目のメモリが物理的にいつ解放されるかを気にせず、項目を追加することができない場合、個別にリンクされたリストで項目のロックフリーの論理的削除をサポートすることが可能です。削除中のアイテムの直後。各アイテムに削除済みフラグを付け、各アイテムにアクセスするときに次のノードが削除されているかどうかをチェックするリスト走査ルーチンを用意します。ある場合は、compare と swap を使用して、現在のノードの「次の」ポインタをその周りに振ります。削除されていたノードの「次の」ポインタが変更される可能性がありますが、その次のノードをスキップするだけであることに注意してください。次のポインターを振ると、リストからリンク解除されたばかりのノードが再リンクされる可能性があります (例: A->B-> C->D は、B と C が同時に削除された場合、A->B->D (B のポインターをスイング) になり、次に A->C->D (A のポインターを B の 'next' のラッチされた値にスイング) になる可能性があります。ポインター)。ただし、ノード C に「削除済み」のフラグが付けられ続けている場合でも、次にリストが繰り返されるときに A のポインターが D に移動するため、問題は発生しません。
2 つの注意点: -1- ガベージ コレクションを行わないシステムでは、いつノードを解放できるかを知るのが難しい場合があります。ノードを解放してからポインタをそこに戻すと、未定義の動作が発生する可能性があります。-2- 削除したノードの直後にノードを追加すると、ポインタが揺れて新しいノードが切断される場合があります。ノードが常にキューの最後に追加される場合、ダミー ノードでキューを終了することにより、この後者の問題を回避できます。ダミー ノードは、その後に別のノードが存在するまで削除できません。