Что не так с этим алгоритмом выполнения в Java?
Рассмотрим следующее дерево:
То, что я пытаюсь сделать, это эмулировать древовидный алгоритм, чтобы, если узел получил токен от всех, кроме одного из его напрямую подключенных соседей, он отправляет токен этому тихому соседу (всегда верно для конечного узла). И если узел получает токен от тихого соседа, решение принимается. Узлы всегда 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() есть время (условие), которое на самом деле означает.. ожидание (получение токенов от соседей), и когда есть только один сосед, узел не получил токен, чтобы отправить ему токен.
Вот как я создаю узлы и как я ассоциирую друг друга:
// 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!
Но обычно я получаю ошибку, и только один решает:
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)
И да, это для Задания, и я очень близок к этому, ребята... но я сталкиваюсь с этой проблемой.
2 ответа
Ну твой run вызовы методов Node n = getSilentNeigh(); Этот вызов может вернуть ноль, и вы используете 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");
}
Inside the run() method there is a while(condition) that actually means.. wait (receiving tokens from neighbours)
Это не так в соответствии с вашим кодом
while(flag() > 1);
если узел имеет только один узел ( 4 /5 / 6) - для них флаг () вернет 1 и завершится в то время как цикл, а затем будет двигаться вперед и отправлять запрос даже до того, как инициаторы начнут отправлять сообщение
ОБНОВИТЬ
Как вы знаете, для этого кода есть 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) уже достиг / отправляет сообщение соседу ( 1) другого инициатора (3). в то время как Инициатор (3) попытается запустить и получить SlientNeigh, он получит Null (без скользкого ржа). таким образом вы получаете исключение нулевого указателя в n.sendToken.
Ссылка на алгоритм: Вам не нужно sycn (у нас нет правила, что каждый узел должен получать только одно сообщение от соседа).
Из ссылки три простых свойства
– 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