Primer algoritmo concurrente

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.

En este momento anotamos que para un algoritmo concurrente las siguientes propriedades son escenciales:

seguridad:

nunca pasa nada malo, es decir, una cierta condición se cumple siempre (``safety property'')

vivacidad:

a veces pasa algo bueno, es decir, al fin y al cabo pasa algo o en algún momento en el futuro se cumple una cierta condición (``liveness property'')

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: multiplicación

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 común detenidamente.