java - Pregunta de entrevista de condición de carrera: rango mínimo y máximo de un entero

multithreading race-condition

Question

Recientemente me hicieron esta pregunta en una entrevista.

Dado el siguiente código, ¿cuál será el valor mínimo y máximo posible del número entero estático num ?

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

public class ThreadTest {
    private static int num = 0;

    public static void foo() {
        for (int i = 0; i < 5; i++) {
            num++;
        }
    }

    public static void main(String[] args) throws Exception{
        List<Thread> threads = new ArrayList<Thread>();
        for (int i = 0; i < 5; i++) {
            Thread thread = new Thread(new Task());
            threads.add(thread);
            thread.start();
        }
        for (int i = 0; i < 5; i++) {
            threads.get(i).join();
        }
        // What will be the range of num ???
        System.out.println(ThreadTest.num);
    }
}

class Task implements Runnable {
    @Override
    public void run() {
        ThreadTest.foo();
    }

}

Les dije que el valor máximo sería 25 (en caso de que no haya condición de carrera), y el mínimo sería 5 (en caso de una condición de carrera entre todos los hilos en cada iteración).
Pero el entrevistador dijo que el valor mínimo puede ir incluso por debajo de 5.
¿Cómo es eso posible?

Answer 1

Afirmo que el valor mínimo posible es 2.

La clave para esto es la no atomicidad de num++ , es decir, es una lectura y una escritura, que pueden tener otras operaciones en el medio.

Llame a los hilos T1..T5:

• T1 lee 0, T2 lee 0;
• T1 escribe 1, y luego lee y escribe 3 veces.
• Entonces T2 escribe 1;
• Entonces T1 lee 1;
• Entonces T2-5 hace todo su trabajo
• Entonces, finalmente, T1 escribe 2.

(Nota: el resultado 2 no depende del número de subprocesos o del número de iteraciones, siempre que haya al menos 2 de cada uno).

Pero la respuesta honesta a esto es: realmente no importa. Hay una carrera de datos, como se define en JLS 17.4.5 :

Cuando un programa contiene dos accesos en conflicto (§17.4.1) que no están ordenados por una relación anterior, se dice que contiene una carrera de datos .

(Hay una ausencia de relaciones antes de pasar entre las acciones en los hilos)

Por lo tanto, no puede confiar útilmente en lo que sea que haga. Es simplemente un código incorrecto.

(Además, sé que la respuesta a esto no se debe a un código multiproceso de depuración de batalla ganado con esfuerzo, o a una lectura técnica profunda: lo sé porque he leído esta respuesta antes en otro lado. Es un truco de salón, nada más, y por eso pregunto al el valor mínimo no es una muy buena pregunta de entrevista).

Answer 2

Bueno, mi respuesta sería Max 25 y Min 0, ya que todas sus operaciones son incrementales, y lo inicializó como 0 ... Creo que el int estático no volátil se arroja allí para que entres en estos pensamientos sobre la raza condiciones, pero ¿hay algo allí que DISMINUYA el número en cualquier situación?

Editar: Por lo que vale, esta sería una distracción típica que pueden esperar que puedas superar en el mundo real, justificando ese "truco", ¡hay muchas pistas falsas!

Answer 3

Sus hilos están actualizando una variable que no es volátil, lo que significa que no garantiza que cada hilo vea el valor actualizado de num . Consideremos el siguiente flujo de ejecución de subprocesos:

Thread 1: 0->1->2 (2 iteration left)
Thread 2: 0->1->2->3 (1 iteration left)
Thread 3: 0->1->2->3 (1 iteration left)
Thread 4: 0->1->2->3 (1 iteration left)
Thread 5: 0->1->2->3 (1 iteration left)

En este punto, el subproceso 1 vacía el valor 2 de num a la memoria y el subproceso 2,3,4,5 decide volver a leer el num de la memoria (por cualquier motivo). Ahora:

Thread 1: 2->3->4 (completed 2 iteration)
Thread 2: 2->3 (completed 1 iteration)
Thread 3: 2->3 (completed 1 iteration)
Thread 4: 2->3 (completed 1 iteration)
Thread 5: 2->3 (completed 1 iteration)

El subproceso 1 vacía el valor 4 en la memoria y después de eso Theard 2,3,4 ... el valor en la memoria muestra que el valor actual del número será 3 lugar de 5