2

こんにちは、ロックレスリストを書き込もうとしています。追加部分が機能していると思いますが、リストからオブジェクトを抽出するコードがうまく機能しません:(

リストは通常​​のリストではありません..私はインターフェースIWorkItemを持っています

interface IWorkItem
{
    DateTime ExecuteTime { get; }
    bool Cancelled { get; }
    void Execute(DateTime now);
}

そして、私はこれを追加できるリストを持っています:P そして理想は私が Get(); を実行したときです。リストでは、IWorkItem が見つかるまでループする必要があります。

If (item.ExecuteTime < DateTime.Now)

リストから削除して返します..デュアルコアCPUで多くのスレッドを使用してテストを実行しましたが、これまでのところ追加が失敗したことはないようですが、Get関数はいくつかの作業項目を失い、何が悪いのかわかりません.. ...

psこれが機能するようになったら、誰でも自由にコードを使用できます:)まあ、あなたはどうでもいいですが、バグが発生したときのポイントはわかりません:P

コードはhttp://www.easy-share.com/1903474734/LinkedList.zipにあります。実行しようとすると、リスト...

編集: ロックレス リストが動作しています。lock(obj) ステートメントを使用するよりも高速でしたが、Interlocked を使用するロック オブジェクトがあり、ロックレス リストよりもパフォーマンスが優れていました。ここで結果をアップロードするのがうまくいかない場合でも、同じ結果が得られます..

4

4 に答える 4

5

問題はあなたのアルゴリズムです: この一連のイベントを考えてみましょう:

スレッド 1 が を呼び出しlist.Add(workItem1)、完全に完了します。

ステータスは次のとおりです。

first=workItem1, workItem1.next = null

次に、スレッド 1 が呼び出さlist.Add(workItem2)れ、2 番目の直前のスポットReplace("//lets try" というコメントがある場所) に到達します。

ステータスは次のとおりです。

first=workItem1, workItem1.next = null, nextItem=workItem1

この時点で、スレッド 2 が引き継ぎ、 を呼び出しますlist.Get()。の executionTime が現在であると仮定workItem1すると、呼び出しは成功し、 が返されますworkItem1。

このステータスの後:

first = null, workItem1.next = null

（そして他のスレッドでnextItemは、まだworkItem1です）。

ここで、最初のスレッドに戻り、Add()設定によって完了しますworkItem1.next:=workItem2。

ここで呼び出すとlist.Get()、正常に完了したnullにもかかわらず、が返されます。Add()

おそらく、ピアレビューされた実際のロックフリー リンク リスト アルゴリズムを調べる必要があります。標準的なのはJohn Valoisのこれだと思います。ここに C++ の実装があります。ロックフリー優先度キューに関するこの記事も役に立つかもしれません。

于 2009-02-02T09:43:43.553 に答える
1

それで、ロックレスにする必要があると確信していますか？作業負荷によっては、ノンブロッキング ソリューションの方が遅くなる場合があります。詳細については、このMSDN の記事を参照してください。また、ロックレス データ構造が正しいことを証明することは、非常に困難な場合があります。

于 2009-01-24T16:36:54.160 に答える
1

データベースの世界からこの例を反映して、データ構造にタイムスタンププロトコルを問題なく使用できます。

同時実行

ただし、各アイテムには読み取りと書き込みの両方のタイムスタンプが必要であることを明確にし、アルゴリズムのルールに明確に従うようにしてください。

ただし、リンクされたリストでこれを実装するには、さらにいくつかの問題があると思います。データベースの例は、必要な配列インデックスがわかっているベクトルには問題ありません。ただし、リンクされたリストでは、ポインターをたどる必要がある場合があり、検索中にリストの構造が変わる可能性があります。ある種のニュアンスでそれを解決できると思います（または、「新しい」リストをそのままトラバースしたい場合は何もしません）が、問題が発生します。リストをロックするよりも状況を悪化させるロールバック状態を導入することなく、問題を解決してみてください!

于 2009-02-01T21:10:39.110 に答える
0

私はこのテーマの専門家ではありませんが、私が見る限り、IWorkItem の実装で ExecutionTime フィールドを揮発性にするか (もちろん、すでにそうなっている可能性があります)、メモリバリアを挿入する必要があります。 ExecutionTime またはそれを読み取る前に設定します。

于 2009-01-24T16:25:31.983 に答える