3

最近、次のような java-concurrency インタビュー タスクが見つかりました。

プッシュとポップの 2 つのメソッドを使用して、シンプルなロックフリー スタックを作成します。

私は集中しました：

import java.util.concurrent.atomic.AtomicInteger;


public class Stack {
    private AtomicInteger count = new AtomicInteger(-1);
    private Object[] data = new Object[1000];

    public void push(Object o) {
        int c = count.incrementAndGet();
        data[c] = o;
    }

    public Object pop() {
        Object top;
        int c;
        while (true) {
            c = count.get();
            if (c == -1) return null;
            top = data[c];
            if (count.compareAndSet(c, c-1))
                return top;
        }
    }
}

予想されたアプローチに似ていますか？または、「ロックフリースタック」は別の意味ですか? Javaインタビューの初心者を助けてください。

4

4 に答える 4

10

Java のアトミック整数とアトミック関数の使用について考えて、確かに正しい方向に出発しました。つまり、明示的なロックはありません。

ただし、同時にアクセスする場合はまだ正しくありません。これを示すのは比較的簡単です。カウントを取得してから新しい要素をスタックに追加するまで (data[c] = o)、およびその間、pop() スレッドがやって来て、より高いカウントを取得し、ポップします...何ですか? たまたまスタック内のその場所のメモリにあるものは何でも、オブジェクト o はそうではありません (まだ挿入されていないため)。

そして、これがロックフリーの配列ベースのスタックの問題です。理論的には、その特定のセルのカウントとコンテンツという 2 つの調整が必要であり、両方をアトミックに同時に行うことはできません。ロックフリーの配列ベースのスタック アルゴリズムが存在することは知りません。

ただし、ロックフリーのリンクリストに基づくスタックアルゴリズムがあります。その場合、新しいノードを作成してコンテンツを割り当てることができ、アトミックに実行する操作は1つだけです。トップポインターを変更します。

この議論に興味があるなら、最高の文学作品は Shavit と Herlihy の「The Art of Multiprocessor Programming」であり、ロックフリーとロックベースの両方のさまざまなデータ構造について説明しています。「通常の」ロックフリー スタック アルゴリズムを詳細に説明している論文は今のところ見つかりませんが、Maged Michael は彼の SMR 論文の 8 ページ、ポイント 4.2 で言及しており、私自身も C99 の実装を行っています。

于 2011-04-10T21:54:08.577 に答える
-1 
public class MyConcurrentStack<T>
{
private AtomicReference<Node> head = new AtomicReference<Node>();
public MyConcurrentStack()
{

}

public void push(T t)
{
    Node<T> n = new Node<T>(t);
    Node<T> current;

    do
    {
        current = head.get();
        n.setNext(current);
    }while(!head.compareAndSet(current, n));
}

public T pop()
{
    Node<T> currentHead = null;
    Node<T> futureHead = null;
    do
    {
        currentHead = head.get();
        if(currentHead == null)
        {
            return null;
        }
        futureHead = currentHead.next;
    }while(!head.compareAndSet(currentHead, futureHead)); 

    return currentHead.data;
}

public T peek()
{
    Node<T> n = head.get();
    if(n==null)
    {
        return null;
    }
    else
    {
        return n.data;
    }
}

private static class Node<T>
{
       private final T data;
       private Node<T> next;

       private Node(T data)
       {
           this.data = data;
       }

       private void setNext(Node next)
       {
           this.next = next;
       }
}

public static void main(String[] args)
{
    MyConcurrentStack m = new MyConcurrentStack();
    m.push(12);
    m.push(13);
    m.push(15);

    System.out.println(m.pop());
    System.out.println(m.pop());
    System.out.println(m.pop());
    System.out.println(m.pop());
}
}

コードは自明です。説明が必要な人がいたら教えてください。スタックは、次の図のように形成されます。

  ...     ...      ...
 |   |-->|   | -->|   |
  ...     ...      ...

   ^
   |
current head
于 2013-03-28T23:54:24.533 に答える
-2

BlockingQueue Useメソッドput（）を使用して要素を挿入し、メソッドdrainTo（Collection c）を使用して要素を取得できます。次に、cの終わりから要素を読み取ります。

于 2011-04-10T21:01:15.000 に答える