Se considera instrucciones atómicas aquellas que está garantizado su correcto cumplimento independientemento de otras instrucciones posiblemente ejecutadas simultaneamente en el programa. A veces también nos referimos a instrucciones atómicas cuando el procesador es capaz de volver al estado producido justamente antes de haber empezado la ejecución de la instrucción en el caso de que se produzca una interrupción, es decir, el efecto de la instrucción es nulo.
Un algoritmo secuencial impone un orden total en el conjunto de las instrucciones que establece mientras un algoritmo concurrente solamente especifica un orden parcial.
Eso se puede visualizar con grafos: los nodos representan las instrucciones atómicas, las aristas indican si una instrucción debe seguir la otra.
Eso implica que la ejecución del programa es indeterminística. Ejecutar el mismo programa varias veces, aún con los mismos datos de entrada, puede resultar en secuencias de instrucciones diferentes, incluso puede ocurrir que es imposible detectar en que orden se ejecutan las instrucciones en un caso real.
Prácticas: implementa el ejemplo de la simple multiplicación en Java y observa el indeterminismo. ¿Cuáles de las instrucciones hay que ejecutar de forma atómica para que funcione bien la multiplicación?