3

次のツリーを検討してください。

木

私がやろうとしているのは、ツリー ウェーブ アルゴリズムをエミュレートすることです。これにより、ノードが直接接続されたネイバーの 1 つを除くすべてからトークンを受信した場合、そのサイレント ネイバーにトークンが送信されます (リーフ ノードの場合は常に true)。ノードがサイレント ネイバーからトークンを受信すると、決定が下されます。ノードは常に 7 であり、ツリー構造は同じであるため、各ノードの隣接ノード (直接接続されたノード) を常に把握しています。

ツリー アルゴリズムの擬似コード:

ツリーアルゴリズム

次のオブジェクトがあります。

public final class Node implements Runnable {

    private final int name;

    // Indicating token receiving from neighbours
    private Map<Node, Boolean> neigh = new 
            HashMap<Node, Boolean>();

    public Node(int name) {
        this.name = name;
    }

    public int getName() {
        return name;
    }

    public void addNeigh(Node node) {
        neigh.put(node, false);
    }

    private int flag() {
        Collection<Boolean> c = neigh.values();
        int count = 0;
        for (Boolean bool : c) {
            if (!bool) {
                count++;
            }
        }
        return count;
    }

    private Node getSilentNeigh() {
        for (Entry<Node, Boolean> entry : neigh.entrySet()) {
            if (false == entry.getValue()) {
                return entry.getKey();
            }
        }
        return null;
    }

    public void sendToken(Node from, String token) {

        Node n;
        if ((n = getSilentNeigh()) != null && flag() == 1) {
            if (from.equals(n)) {
                System.out.println(name + " decides!");
            }
        }

        neigh.put(from, true);
    }

    @Override
    public boolean equals(Object obj) {

        if (this == obj) {
            return true;
        }

        if (!(obj instanceof Node)) {
            return false;
        }

        final Node n = (Node) obj;
        return name == n.name;
    }

    @Override
    public int hashCode() {
        int hc = 17;
        return 37 * hc + name;
    }

    @Override
    public void run() {
        while(flag() > 1);

        Node n = getSilentNeigh();

        System.out.println(name + " sends token to " + n.getName());

        n.sendToken(this, "token");
    }

    @Override
    public String toString() {
        return "Node " + name;
    }
}

run() メソッド内には while(condition) があり、これは実際には待機 (ネイバーからトークンを受信する) を意味し、ノードがトークンを受信しなかったネイバーが 1 つしかない場合は、そのノードにトークンを送信します。

これは、ノードを作成する方法と、相互に関連付ける方法です。

        // Number of nodes
        int numberOfNodes = 7;

        // Array of nodes
        Node[] nodes = new Node[numberOfNodes]; 

        for (int i = 0; i < nodes.length; i++) {
            // Creating node
            nodes[i] = new Node(i);
        }

        nodes[0].addNeigh(nodes[1]);
        nodes[0].addNeigh(nodes[2]);
        nodes[1].addNeigh(nodes[0]);
        nodes[1].addNeigh(nodes[3]);
        nodes[1].addNeigh(nodes[4]);
        nodes[2].addNeigh(nodes[0]);
        nodes[2].addNeigh(nodes[5]);
        nodes[2].addNeigh(nodes[6]);    
        nodes[3].addNeigh(nodes[1]);
        nodes[4].addNeigh(nodes[1]);
        nodes[5].addNeigh(nodes[2]);
        nodes[6].addNeigh(nodes[2]);

私がしていることは、実行するノードの順序をランダムに選択することです:

        // List holding random node numbers
        List numbers = new ArrayList<Integer>();

        int chosen = 0;
        while (chosen < numberOfNodes) {
            int processNum = randInt(0, (numberOfNodes - 1));
            if (!numbers.contains(Integer.valueOf(processNum))) {
                 numbers.add(new Integer(processNum));
                 chosen++;
            }
        }

たとえば、ノードは任意の順序である可能性があります。

0, 5, 3, 4, 6, 2, 1
5, 3, 0, 2, 1, 6, 4
3, 1, 0, 2, 4, 6, 5

そして、私はスレッドを開始します:

for (Integer number : numbers) {
    Thread thread = new Thread(nodes[number]);
    thread.start();
}

期待される結果が得られる場合があります (2 つを決定する必要があります)。

Nodes selected: 0, 4, 5, 2, 6, 3, 1
5 sends token to 2
4 sends token to 1
6 sends token to 2
3 sends token to 1
1 sends token to 0
0 sends token to 2
2 decides!
2 sends token to 0
0 decides!

しかし、通常、エラーが発生し、決定するのは1つだけです:

Nodes selected: 5, 3, 4, 6, 0, 2, 1
3 sends token to 1
5 sends token to 2
4 sends token to 1
6 sends token to 2
2 sends token to 0
0 sends token to 1
1 decides!
Exception in thread "Thread-6" java.lang.NullPointerException
    at uk.ac.ncl.csc8103.wave.Node.run(Node.java:86)
    at java.lang.Thread.run(Thread.java:745)

はい、これは割り当てのためです。私はこの人たちと本当に親しいです..しかし、私はこの問題に直面しています。

4

2 に答える 2

1 
Inside the run() method there is a while(condition) that actually means.. wait (receiving tokens from neighbours)

これはあなたのコードでは真実ではありません

  while(flag() > 1);

Node に Node が 1 つしかない場合 ( 4 /5 / 6 ) - これらの場合、flag() は 1 を返し、while ループを終了し、イニシエーターがメッセージの送信を開始する前であっても、前進してリクエストを送信します。

アップデート

ご存じのように、このコードには 4 つのイニシエーター (3,4,5,6) があり、while ループから抜け出すことを除いて..

これを取る

選択されたノード: 5、3、4、6、0、2、1 3 トークンを 1 に送信 5 トークンを 2 に送信 4 トークンを 1 に送信 6 トークンを 2 に送信 2 トークンを 0 に送信 0 トークンを 1 に送信 1 決定!

これは純粋に競合状態であり、以前に開始されたイニシエーター (5) が既に到達している場合、または他のイニシエーターの (3) ネイバー (1) にメッセージを送信します。Initator(3) が開始して SlientNeigh を取得しようとすると、 Null (slient neigh はありません) になります。したがって、n.sendToken で Null ポインター例外が発生します。

アルゴリズムの参照 : 同期する必要はありません (各ノードが近隣ノードからメッセージを 1 つだけ受信するという規則はありません)。

参照3つの単純なプロパティから

  – In each computation there is one initiator, which starts the algorithm by sending out exactly one message

–– A process, upon receipt of a message, either sends out one message or decides


–– The algorithm terminates in the initiator and when this happens, each process has sent a message at least once
于 2014-10-24T20:50:01.647 に答える
1

さて、あなたのrunメソッド呼び出しNode n = getSilentNeigh();この呼び出しは null を返す可能性があり、null でnないことを確認せずに変数を使用します。

@Override
public void run() {
    while(flag() > 1);
    Node n = getSilentNeigh(); // this call can return null
    System.out.println(name + " sends token to " + n.getName()); // you are probably getting 
                                                                 // NullPointerException here
    n.sendToken(this, "token");
}
于 2014-10-24T18:59:07.687 に答える