Google での "lock free vector" の最初の結果は、Damian Dechev、Peter Pirkelbauer、および Bjarne Stroustrup が共同執筆した研究論文で、理論的なロックフリー ベクトルについて説明しています。これ、または他のロックフリーのベクトルは実装されていますか?
2 に答える
MS は ppl::concurrent_vector を提供し、Intel は tbb::concurrent_vector を提供します。Windows では、少なくとも ppl と tbb は C ランタイムの一部です。
ウィキペディアでベクトルとは何かを調べたところです。
完全にロックフリーのバージョンは少し問題があると思います(ほんの1、2分考えてください)。
検討; アレイを作成し、通常どおりにアクセスするなど。このために、ロックフリーは必要ありません。サイズを変更する必要があるときに問題が発生します。入ってこれを発見するスレッドはmallocする必要があります。これは本当にユニークな操作です。この時点で他のスレッドはブロック/スピンする必要があります。彼らが助けようとした場合、たとえば、malloc自体を実行した場合、mallocを発行するスレッドが多数ある可能性があります。実際には、実行しているスレッドの数は非常に少ないので問題ありません-その場合、mallocを実行しているスレッドの数があり、勝者が新しいメモリをアトミックにアクティブ化し、敗者がこれを見てから解放します( )彼らの記憶を。
次に、コピーを実行するために、スレッドが要素にアクセスするようになると、リスト内の割り当てられたすべての配列を追跡する必要があります。要素が見つかるまで、リストから最も古いものからアクセスします。必要な場合は、最新の配列にない場合は、移動してからアクセスします。
次に、スレッドが最後の要素を移動し、その配列を解放できることをスレッドが認識する方法も必要です。そのため、要素をカウントする必要があります。そのため、潜在的に無制限の割り当て要件のリスクがあります。さらに、データ構造(リストについては述べましたが、他のこともありますが、それほど良くはありませんが、プロリー)はアトミックである必要があります(スレッドが同時に配列を削除する可能性があるため)そして、アトミックロックフリーリストは、ごく最近まで、ロックフリーデータ構造の頂点であり、SMRを必要とし、実装が複雑でした。
(私は最近まで言います-誰かが最近ロックフリーの赤黒木を発明しました、全部、追加して削除してください!)
TBH、なぜ誰かがベクトルを使用するのかわかりません。平衡二分木やハッシュを使用しないのはなぜですか?