Encontré esta pregunta en un libro de texto que estoy leyendo. La solución se da debajo también. Tengo problemas para entender cómo el mínimo podría ser 2. ¿Por qué un subproceso no puede leer 0, todos los demás subprocesos se ejecutan y escribe 1? Y ya sea 1 o 2, ¿el último hilo que escribe debe completar su propio bucle?
int n = 0; int main(int argc, char **argv) { for (i = 0; i < 5; i++) { int tmp = n; tmp = tmp + 1; n = tmp; } return 0; }Si un solo subproceso ejecuta esta aplicación, esperaría que el resultado final fuera 5. ¿Qué sucede si 5 subprocesos ejecutan el mismo ciclo en paralelo? ¿Cuáles son los valores más grande y más pequeño que n podría tener? El mayor debe ser evidente: 25, con 5 incrementos de 5 hilos. Sin embargo, razonar sobre el valor más pequeño posible es más difícil. Pista: n puede ser menor que 5, pero depende de ti averiguar por qué.
Solución:
Con cinco subprocesos ejecutando este ciclo de cinco iteraciones y sin protección contra accesos simultáneos, el valor más bajo que puede alcanzar n es dos. Comprender cómo llegar a este resultado es más fácil cuando se trabaja hacia atrás desde el resultado final. Para que la salida final sea dos, un subproceso debe haber leído un valor de uno de n, lo incrementó y luego escribió dos. Eso significa que otro subproceso escribió uno, lo que implica que inicialmente también leyó cero (que también es el valor inicial de n). Esto explica el comportamiento de dos de los cinco subprocesos. Sin embargo, para que se produzca este comportamiento, se deben haber sobrescrito los resultados de los otros tres subprocesos. Dos ejecuciones válidas podrían lograr esto. 1) los tres subprocesos comenzaron y completaron la ejecución entre el primer subproceso leyendo cero y escribiendo uno, o 2) los tres subprocesos comenzaron y completando la ejecución entre el subproceso final leyendo uno y escribiendo dos. Ambos ordenamientos de ejecución son válidos.
Suponiendo que cada subproceso tiene una i local (es decir, cada subproceso se ejecutará durante 5 iteraciones, pase lo que pase), intentemos obtener 1 como resultado. Esto significaría que el último subproceso en escribir un valor tendría que leer 0 para n en su quinta iteración. La única forma en que esto podría suceder es si ningún subproceso ha escrito aún en n al comienzo de la quinta iteración de ese subproceso, pero para que ese subproceso esté en su quinta iteración, ese subproceso debe haber escrito en n , por lo tanto, no es posible.
Por lo tanto, el resultado más pequeño posible es 2, que puede ocurrir, por ejemplo, de la siguiente manera: el último subproceso en escribir n ha completado 4 iteraciones, luego otro subproceso escribe 1, el último subproceso lee el 1 al comienzo de su quinta iteración, todos los demás los subprocesos completan todas sus iteraciones antes del último subproceso, y finalmente el último subproceso completa su quinta iteración escribiendo el 2.
Descargo de responsabilidad: estoy respondiendo a la pregunta conceptual sobre subprocesos múltiples: como han señalado otros, la falta de atomicidad podría conducir a un comportamiento indefinido y resultados arbitrarios si el código C presentado se usara tal cual. Basado en el caso de número más grande "evidente" de la pregunta, supongo que el autor del libro de texto no se da cuenta de esto o está usando un pseudocódigo similar a C para ilustrar el concepto. Si es lo primero, entonces la respuesta correcta sería que el libro está equivocado, pero creo que la respuesta en el segundo caso también es educativa.
Solo una idea para agregar: Sumar, restar, etc. en C usando el operador + es más que solo 1 operación. Abajo, en el nivel de ensamblaje, la operación + se compone de varias instrucciones. Si varios subprocesos accedieran a una variable y hubiera una mala intercalación de estas instrucciones, el resultado final podría ser un resultado horriblemente incorrecto -> esta es otra razón por la que necesitamos cosas como mutexes, semáforos y variables de condición.
El mayor debe ser evidente: 25, con 5 incrementos de 5 hilos.
Total y completamente equivocado. Lo que sea que haya dicho esto, nunca debería ser escuchado (al menos sobre cosas que involucran subprocesos), punto.
int tmp = n; tmp = tmp + 1; n = tmp; Imagine una CPU que no tuviera una operación de incremento, pero que tuviera una operación eficiente de "sumar 10" y una operación eficiente de "restar nueve". En tal CPU, tmp = tmp + 1; podría optimizarse a tmp += 10; tmp -= 9; . El compilador también podría optimizar tmp por completo operando en n .
Entonces este código podría convertirse en el equivalente de:
n += 10; n -= 9; Ahora imagine que esto sucede: los cinco hilos suman 10, por lo que n ahora es 50. El primer hilo lee el 50, los otros cuatro hilos restan 9. El primer hilo resta 9 de los 50, lee y escribe 41. Entonces, cuando todo está hecho , n es 41.
Entonces, lo que se afirma que es evidente por sí mismo es completamente falso. Quien haya escrito eso no entiende el enhebrado en C.
si cada subproceso escribe un 1, entonces el valor final no puede ser mágicamente otra cosa
También total y completamente falso. Considere una CPU que escribe un 1 escribiendo primero un 0 y luego incrementando el valor. Si esto sucede en dos núcleos, el resultado final podría ser 2. Este libro de texto fue escrito por alguien que fundamentalmente no entiende los subprocesos y el comportamiento indefinido.
(Supongo que este libro de texto no se limita a un contexto especial en el que lo que dice es cierto. Por ejemplo, podría estar usando código "similar a C" como una forma de lenguaje ensamblador independiente de la plataforma y podría estar haciendo suposiciones sobre plataformas en las que los enteros alineados tienen garantías específicas. Pero si eso es así, lo que está enseñando no se traduce en código C en absoluto y solo se aplicaría a las personas que escriben código ensamblador en CPU cuyas reglas coinciden con las suposiciones del libro de texto).