What is wrong with multi-thread implementation?

3

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

What did I do wrong?

STARTING THE 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);
    }
}
    
asked by anonymous 09.04.2016 / 21:03

2 answers

4

The problem not was to wait for the threads to finish. The code does this perfectly, albeit in an unoptimized way, as follows:

  • Tests the first Thread and waits if it does not execute
  • If it is not the last thread, execute step 1 for the next thread ('i + 1)
  • Improving the result display

    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 did not have to be recursive.

    In addition, the second if is redundant. It is guaranteed that threads will end.

    So the snippet 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();
    }
    

    Correcting the problem

    Well, let's get down to the problem then. It is in only 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 one operator that is necessarily atomic.

    In fact, even operations that are atomic as unit increments ( var++ ) can generate problems when threads running on different processors use an old value of the variable found in the local cache, which is out of date relative to 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. A simple 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, in addition to 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 increment this way:

    resultado.addAndGet(valor);
    

    Finally, print like this:

    System.out.println(resultado.get());
    
        
    11.04.2016 / 02:54
    0

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

    Follow the code below:

       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();
                }
            }
    
    }
    
        
    10.04.2016 / 16:33