What’s wrong with multi-thread implementation?

Question

The implementation below is merely a test class to test competition in Java. Multiple Threads are created that execute a method that adds up, then a return is displayed showing the sum result. According to the values already implemented in the code below, the correct result is 100, but it oscillates between 90 and 100 since for some implementation error, the parallel process prevents to always return the correct value, displaying the result without waiting for all Threads to finish executing the sum.

What I did wrong?

BEGINNING OF CLASS

import java.util.ArrayList;
import java.util.List;

public class ExercicioFinal {

    private final static List<Soma> listaSoma = new ArrayList<Soma>(0);
    private static final int LIMITE = 10;

    public static void main(final String[] args) throws InterruptedException {
        for (int i = 0; i < LIMITE; i++) {
            listaSoma.add(new Soma(10));
        }

        for (final Soma soma : listaSoma) {
            new Thread(soma).start();
        }

        exibirResultado(0);
    }

    private static void exibirResultado(final int i) throws InterruptedException {
        final Soma s = listaSoma.get(i);
        synchronized (s) {
            if (!s.foiExecutado()) {
                s.wait();
            }

            if ((i + 1) < listaSoma.size()) {
                exibirResultado(i + 1);
            } else {
                if (s.foiExecutado()) {
                    Soma.exibe();
                } else {
                    exibirResultado(i);
                }
            }
        }
    }
}

class Soma implements Runnable {
    private static int resultado;
    private final int valor;
    private boolean executou = false;

    public Soma(final int valor) {
        this.valor = valor;
    }

    @Override
    public void run() {
        synchronized (this) {
            try {
                Thread.sleep(1);
            } catch (final InterruptedException e) {
                e.printStackTrace();
            }
            resultado += valor;
            executou = true;
            this.notify();
        }
    }

    public boolean foiExecutado() {
        return executou;
    }

    public static void exibe() {
        System.out.println(resultado);
    }
}

Answer 1

The problem nay was to wait for the threads to finish. The code does this perfectly, although not optimally, as follows:

1. Test the first Thread and wait if it hasn’t run
2. If it is not the last thread, execute step 1 to the next thread (`i + 1)

Improving the display of the result

The code that implements the above algorithm is this:

final Soma s = listaSoma.get(i);
synchronized (s) {
    if (!s.foiExecutado()) {
        s.wait();
    }

    if ((i + 1) < listaSoma.size()) {
        exibirResultado(i + 1);
    } else {
        if (s.foiExecutado()) {
            Soma.exibe();
        } else {
            exibirResultado(i);
        }
    }
}

The algorithm could be a loop, it didn’t need to be recursive.

Moreover, the second if is redundant. It is guaranteed that threads will finish.

Therefore, the excerpt could be rewritten like this:

private static void exibirResultado() throws InterruptedException {
    for (final Soma s : listaSoma) {
        synchronized (s) {
            if (!s.foiExecutado()) {
                s.wait();
            }
        }
    }
    Soma.exibe();
}

Fixing the problem

Well, let’s get to the problem then. It’s in just one line of code:

resultado += valor;

That’s right. The problem is that the above operation is not atomic!

This concept is very important: it is not because an operation has only one line or an operator that it necessarily is atomic.

In fact, even operations that are atomic as unit increments (var++) can cause problems when threads running on different processors use an old value of the variable found in the local cache, which is lagged from the cache of other processors. Here comes the use of volatile, but it’s not the problem in this case, so I’ll stop here. :)

The solution in this case is that the variable update needs to be synchronized between threads. An easy way to do this is like this:

synchronized (Soma.class) {
    resultado += valor;
}

The above block ensures that only one instance of Soma can access the variable at a time, and at the end of the block the other threads will have the correct value of the variable.

Another possibility is to use a variable of type AtomicInteger. Example:

private static AtomicInteger resultado = new AtomicInteger();

Then increase so:

resultado.addAndGet(valor);

Finally, print like this:

System.out.println(resultado.get());

Answer 2

What was missing was to check if all the threads had finished, their execution, I was just checking if the thread had been executed, but not if all of them were executed. I used the approach of counting the total Threads executed with a static int variable, so that if it is equal to the List size (.size()) then it displays the sum result, otherwise it calls the method back in the same index and stays in loop until Thread finishes its execution. Done!

Follows code:

   import java.util.ArrayList;
    import java.util.List;

    public class ExercicioFinal {private static final int LIMITE_ITERACAO = 10;

    public static void main(final String[] args) throws InterruptedException {

    final List<Somador> somaList = new ArrayList<Somador>(0);<br>
    for (int i = 0; i < LIMITE_ITERACAO; i++) {
    somaList.add(new Somador(10));
            }

            for (final Somador somador : somaList) {
                new Thread(somador).start();
            }

            exibirResultado(0, somaList);
        }

        private static void exibirResultado(final int index, final List<Somador> somaList) throws InterruptedException {
            final Somador somador = somaList.get(index);
            synchronized (somador) {
                if (!somador.executou()) {
                    somador.wait();
                }
                if (((index + 1) == somaList.size()) && (Somador.executados() == somaList.size())) {
                    Somador.exibir();
                } else if ((index + 1) < somaList.size()) {
                    exibirResultado(index + 1, somaList);
                } else {
                    exibirResultado(index, somaList);
                }
            }
        }
    }

    class Somador implements Runnable {<br>
    private static int contador;<br>
    private boolean executou;<br>
    private final int valor;<br>
    private static int executados;<br>

        public Somador(final int valor) {
            this.valor = valor;
        }

        public boolean executou() {
            return this.executou;
        }

        public static int executados() {
            return executados;
        }

        public static void exibir() {
            System.out.println(contador);
        }

        @Override
        public void run() {
            synchronized (this) {
                contador += valor;
                executados++;
                this.executou = true;
                this.notify();
            }
        }

}