2

http://www.boyet.com/articles/LockfreeQueue.htmlに基づく比較とスワップを使用して、C でロック フリー キューを実装しました。

うまく機能していますが、このキューを実装したロックフリーのスキップリストに統合しようとしています。スキップ リストをプライオリティ キューとして使用しており、プライオリティの競合が発生した場合に複数の値を格納するために、各ノード内のロック フリー キューを使用したいと考えています。ただし、優先順位の競合を検出したときにスキップ リストでノードを管理する方法により、キューが空でない場合にのみ、アイテムをキューに追加できる必要があります。

キューのロックフリーの性質により、この操作を実際に実行する方法がわかりません。

基本的に、アトミックな enqueue_if_not_empty 操作をどのように記述すればよいでしょうか?

4

2 に答える 2

0

Enqueue-If-Not-Emptyは比較的簡単に見えますが、制限があります。他のスレッドがキューから以前のすべてのアイテムを同時に削除する可能性があるため、テールでの挿入が行われた後、新しいアイテムがたまたまキューの最初。アトミックコンペアアンドスワップ操作はさまざまなフィールドで実行されるため（アドバンスtail.Nextをデキューしながら変更をエンキューするhead）、より強力な保証には、この関数だけでなく、少なくともDequeue()同様に追加の複雑さが必要になります。

通常の方法に対する次の変更Enqueue()で十分です
。1）関数の開始時に、head.Nextnullであるかどうかを確認し、nullの場合は、キューが空になるとすぐに戻ります。2）挿入が成功する前に最初に空でないキューが空になった場合にキューイングの試行を停止する必要がある場合に備えて、ループ条件に
追加します。head.Next!=nullこれは、上記で説明した状況を防ぐことはできませんが（空のチェックとノードの挿入の間に時間枠があるため）、発生する可能性は低くなります。
3）関数の最後で、新しいノードが正常にキューに入れられた場合にのみ、テールを進めてみてください（Enqueue-If-Emptyの回答で行ったように）。

于 2011-05-04T08:48:42.713 に答える
0

編集:気づいたように、私はまったく反対のセマンティクスで関数を書きました-空のキューにのみエンキューします。それを反映するために名前を修正し、誰かが興味を持った場合に備えてそのままにしておくことにしました. したがって、これは質問に対する正しい答えではありませんが、別の理由が見つからない限り、反対票を投じないでください:)

EnqueueIfEmpty()以下は、参照された論文のキュー実装に追加する試みです。動作するか、コンパイルできるかは確認していません。基本的な考え方は、head の next が現在 null である場合 (空のキューに必要な条件)、headの直後に (tail ではなく) 新しいノードを挿入することです。頭が尾と等しいことを確認する追加のチェックを残しましたが、これは削除できる可能性があります。

public bool EnqueueIfEmpty(T item) {
  // Return immediately if the queue is not empty.
  // Possibly the first condition is redundant.
  if (head!=tail || head.Next!=null)
      return false;

  SingleLinkNode<T> oldHead = null;

  // create and initialize the new node
  SingleLinkNode<T> node = new SingleLinkNode<T>();
  node.Item = item;

  // loop until we have managed to update the tail's Next link 
  // to point to our new node
  bool Succeeded = false;
  while (head==tail && !Succeeded) {

    // save the current value of the head
    oldHead = head;         

    // providing that the tail still equals to head...
    if (tail == oldHead) {

      // ...and its Next field is null...
      if (oldhead.Next == null) {

        // ...try inserting new node right after the head.
        // Do not insert at the tail, because that might succeed
        // with a non-empty queue as well.
        Succeeded = SyncMethods.CAS<SingleLinkNode<T>>(ref head.Next, null, node);
      }

      // if the head's Next field was non-null, another thread is
      // in the middle of enqueuing a new node, so the queue becomes non-empty
      else {
        return false;
      }
    }
  }

  if (Succeeded) {
    // try and update the tail field to point to our node; don't
    // worry if we can't, another thread will update it for us on
    // the next call to Enqueue()
    SyncMethods.CAS<SingleLinkNode<T>>(ref tail, oldHead, node);
  }
  return Succeeded;
}
于 2011-05-03T20:50:30.410 に答える