6

次回の並行システム試験の準備として、教科書「マルチプロセッサプログラミングの芸術」からいくつかの質問に答えようとしています。1つの質問は私を悩ませています：

演習129： LockFreeStackオブジェクトのプッシュとポップの両方に同じ共有BackOffオブジェクトを使用することは意味がありますか？EliminationBackOffStackで、空間と時間のバックオフを他にどのように構成できますか？

この質問は私を悩ませます。最初に頭に浮かぶのは、バックオフオブジェクトが行うのはプロセスを待機させることだけなので、意味がないということです。共有してみませんか？質問の2番目の部分は完全に私を避けており、どんな助けでも大歓迎です。

LockFreeStackのコード：

public class LockFreeStack<T> {

    AtomicReference<Node> top = new AtomicReference<Node>(null);

    static final int MIN_DELAY = ...;
    static final int MAX_DELAY = ...;
    Backoff backoff = new Backoff(MIN_DELAY, MAX_DELAY);

    protected boolean tryPush(Node node) {
        Node oldTop = top.get();
        node.next = oldTop;
        return(top.compareAndSet(oldTop, node));
    }

    public void push(T value) {
        Node node = new Node(value);
        while (true) {
            if (tryPush(node)) {
                return;
            } else {
                backoff.backoff();
            }
        }
    }
4

3 に答える 3

1

BackOff同期の観点から最初の質問に近づくと、プッシュとポップの両方で同じオブジェクトを許可することは理にかなっていると思います。このクラスの実装に関係なく。この理由は、スタックがある場合、スタックへのアイテムの削除と追加の間、一貫した状態を維持する必要があるためです。BackOffただし、読み取りが問題のデータソースをロックすることはないため、複数のオブジェクトがそれを見ることができるよりも、ピーク（最初の要素またはスタックの最上位を見る）のみを行っていた場合。2番目の質問では、そのクラスのコードを投稿する必要があります。

于 2010-11-03T22:14:21.417 に答える
1

私のとりとめのないことが役立つかどうかはわかりませんが、とにかく「投稿」ボタンを押します。

答えは の実装に依存しbackoff()ます。ここでの目標は同期を回避することなので、ローカル ストレージはありませんThreadLocal。バックオフ アルゴリズムがランダマイザーを使用する場合は、再入可能である必要もあります。との間で共有できる可能性が最も高いので、共有したいですか。プッシュとポップは両方とも参照を変更しようとしているので、バックオフが連続するスレッドに大幅に異なる番号を与えるとよいでしょう。プッシュまたはポップに関する競合はありますか? いずれかの方法でより積極的に後退する必要がありますか? これが一般的なスタックである場合、わかりません。poppushtop

バックオフをどのように「再構築」できるかという点についても、よくわかりません。成功したプッシュまたはポップを、バックオフ時間を短縮する機会として利用できますか? によって割り当てられたシーケンスのランダムなバックオフ待機と素数の違いはどうThreadLocalですか?

于 2010-11-03T22:05:21.413 に答える
0

この状況でバックオフを使用するのは過剰です。

実際のアプリケーションは、スタックにプッシュしたりスタックから外したりするよりも、ノードの処理に多くの時間を費やす必要があります。比較によるスタック操作は非常に短いはずです。したがって、2 つのスレッドが同時にスタックにアクセスする可能性はほとんどありません。ただし、時々発生するため、どちらが正しいかをコーディングする必要があります。 

public void push(T value) { 
   Node node = new Node(value); 
   while (!tryPush(node)) 
       backoff.backoff(); 
 }

私見：短くすることができます

public void push(T value) { 
   Node node = new Node(value); 
   while (!tryPush(node));
}
于 2010-11-04T19:10:27.590 に答える