Reescribimos el algoritmo secuencial para que ``funcione'' con dos procesos:
Initially: p is set to positive number
q is set to positive number
a: set r to 0
P0 P1
b: loop loop
c: if q equal 0 exit if q equal 0 exit
d: set r to r+p set r to r+p
e: set q to q-1 set q to q-1
f: endloop endloop
g: ...
El algoritmo es indeterminístico en el sentido que no se sabe de antemano en qué orden se van a ejecutar las instrucciones, o más preciso, cómo se van a intercalar las instrucciones de ambos procesos.
El indeterminismo puede provocar situaciones que deriven en errores transitorios, es decir, el fallo ocurre solamente si las instrucciones se ejecutan en un orden específico.
Ejemplo: (mostrado en pizara)
Un programa concurrente es correcto si el resultado observado (y esperado) no depende del orden (dentro de todos los posibles órdenes) en el cual se ejecute las instrucciones.
Para comprobar si un programa concurrente es incorrecto basta con encontrar una intercalación de instrucciones que nos lleva en un fallo.
Para comprobar si un programa concurrente es correcto hay que comprobar que no se produce ningún fallo en ninguna de las intercalaciones posibles.
El número de posibles intercalaciones de los procesos en un programa concurrente crece exponencialmente con el número de unidades que maneja el planificador. Por eso es prácticamente imposible comprobar con la mera enumeración si un programa concurrente es correcto bajo todas las ejecuciones posibles.
En la argumentación hasta ahora fue muy importante que las instrucciones se ejecutaran de forma atómica, es decir, sin interrupción ninguna.
Por ejemplo, se observa una gran diferencia si el procesador trabaja directamente en memoria o si trabaja con registros:
P1: inc N
P2: inc N
P2: inc N
P1: inc N
Se observa: las dos intercalaciones posibles producen el resultado correcto.
P1: load R1,N
P2: load R2,N
P1: inc R1
P2: inc R2
P1: store R1,N
P2: store R2,N
Es decir, existe una intercalación que produce un resultado falso.
Eso implica directamente: no se puede convertir un programa multi-hilo en un programa distribuido sin analizar el concepto de memoria compartida detenidamente.
Ejemplo de Java: accesos a variables con más de 4 byte no son atómicos.