Concurrencia y paralelismo no son sinónimos: la concurrencia es la composición y gestión de múltiples tareas que progresan en periodos solapados (posible en un solo núcleo mediante intercalado), mientras que el paralelismo es la ejecución física simultánea en varias unidades de procesamiento. La taxonomía de Flynn clasifica las arquitecturas según los flujos de instrucciones y datos en SISD, SIMD, MISD y MIMD. Entre las arquitecturas distribuidas, el modelo cliente-servidor centraliza el servicio, mientras que en P2P los nodos comparten roles equivalentes; la comunicación entre procesos se organiza por memoria compartida o por paso de mensajes.
El rendimiento paralelo se cuantifica con la Ley de Amdahl: S(N) = 1 / ((1 − P) + P/N), con P la fracción paralelizable y N los procesadores. Cuando N→∞ el techo es S_max = 1/(1−P) (con P=0.90 el límite es 10×; con P=0.95 es 20×). La Ley de Gustafson (aceleración escalada), S(N) = (1−P) + P·N, aplica cuando el problema crece con N. Se define la aceleración S = T₁/T_N y la eficiencia E = S/N, con 0 < E ≤ 1 (E=1 es la aceleración lineal ideal). MapReduce es un modelo de procesamiento paralelo por fases map y reduce.
En coordinación y sincronización conviene recordar:
El teorema CAP establece que, ante una partición de red, un sistema solo garantiza dos de tres propiedades: Consistencia, Disponibilidad y Tolerancia a particiones. Para la tolerancia a fallos y replicación, los consensos por mayoría (Paxos, Raft) exigen un quórum de ⌊N/2⌋+1 y con N = 2f+1 toleran f caídas; tolerar f fallas bizantinas exige N ≥ 3f+1. El resultado de imposibilidad FLP prueba que en un sistema asíncrono no existe consenso determinista con terminación garantizada ni con una sola falla por caída. El Two-Phase Commit (2PC) coordina preparación (prepare) y decisión (commit/abort), pero es bloqueante si el coordinador falla. La Ley de Little, L = λ·W, modela un sistema en estado estable.
1. La Ley de Amdahl calcula la aceleración (speedup) máxima que un programa puede alcanzar al ejecutarse en N procesadores, cuando una fracción P del código es paralelizable y el resto es estrictamente secuencial. ¿Cuál de las siguientes expresiones corresponde a la Ley de Amdahl?
La Ley de Amdahl es S(N)=1/((1−P)+P/N): la fracción secuencial (1−P) no se acelera y solo la fracción P se divide entre N; la opción (1−P)+P·N corresponde en realidad a la Ley de Gustafson. (Amdahl, G. M. (1967), 'Validity of the single processor approach to achieving large scale computing capabilities', AFIPS Conference Proceedings, vol. 30.)
2. Un programa tiene una fracción paralelizable P = 0.80 (el 80% del código se puede paralelizar) y se ejecuta en N = 4 procesadores idénticos. Aplicando la Ley de Amdahl, ¿cuál es la aceleración S(4) que se obtiene?
Sustituyendo en S(N)=1/((1−P)+P/N): S(4)=1/(0.20+0.80/4)=1/0.40=2.5×; 3.4× resulta de aplicar por error la fórmula de Gustafson, y 4.0× supondría aceleración lineal ideal ignorando la fracción secuencial. (Amdahl (1967); Hennessy & Patterson, 'Computer Architecture: A Quantitative Approach', ley de Amdahl.)
3. Un equipo de desarrollo tiene un programa con una fracción paralelizable P = 0.95 (95% del código). De acuerdo con la Ley de Amdahl, si agregan procesadores de manera indefinida (N → ∞), ¿cuál es la aceleración máxima teórica que podrían alcanzar, sin importar cuántos procesadores agreguen?
Cuando N→∞, S_max=1/(1−P); con P=0.95, S_max=1/0.05=20×. El valor 10× corresponde al límite para P=0.90, no para P=0.95, y 1.05× resulta de invertir la razón (calcular 1/P en lugar de 1/(1−P)). (Amdahl (1967); Hennessy & Patterson, 'Computer Architecture: A Quantitative Approach', ley de Amdahl.)
4. La Ley de Gustafson (aceleración escalada) fue propuesta como alternativa a la Ley de Amdahl para los casos en los que el tamaño del problema crece junto con el número de procesadores, en lugar de mantenerse fijo. ¿Cuál expresión corresponde a esta ley, donde P es la fracción paralelizable y N el número de procesadores?
La Ley de Gustafson es S(N)=(1−P)+P·N, apropiada cuando el problema crece con N; la primera alternativa corresponde a la Ley de Amdahl y la última intercambia el papel de P y (1−P). (Gustafson, J. L. (1988), 'Reevaluating Amdahl's Law', Communications of the ACM 31(5).)
5. Una empresa de simulación climática ejecuta el mismo modelo con una malla de tamaño fijo en un clúster y desea estimar la aceleración al aumentar el número de procesadores sin modificar el volumen de datos procesado. Un segundo equipo, en cambio, aumenta el número de procesadores para simular mallas cada vez más finas, de modo que el trabajo por procesador permanece constante. ¿Qué modelo de aceleración es el adecuado para el segundo equipo?
La Ley de Gustafson modela la aceleración escalada cuando el tamaño del problema crece con N (segundo equipo); la Ley de Amdahl asume un problema de tamaño fijo, adecuado para el primer equipo. (Gustafson (1988), 'Reevaluating Amdahl's Law', CACM 31(5).)
6. Un programa secuencial tarda T₁ = 100 segundos en ejecutarse. Al paralelizarlo y ejecutarlo en 8 procesadores, el tiempo baja a T₈ = 40 segundos. ¿Cuáles son la aceleración S y la eficiencia E obtenidas?
S=T1/T_N=100/40=2.5 y E=S/N=2.5/8=0.3125; invertir el cociente o no dividir entre N al calcular la eficiencia son errores comunes que llevan a los otros resultados. (Grama, Gupta, Karypis, Kumar, 'Introduction to Parallel Computing', 2ª ed., Addison-Wesley.)
7. La taxonomía de Flynn clasifica las arquitecturas de cómputo según el número de flujos de instrucciones y de datos que pueden procesarse simultáneamente. ¿Cuáles son las cuatro categorías que la componen?
Flynn (1972) define cuatro categorías según flujos de instrucción y de datos: SISD, SIMD, MISD y MIMD; MPMD, SPMD y NUMA son términos de programación paralela o de arquitectura de memoria, no categorías de Flynn. (Flynn, M. J. (1972), 'Some Computer Organizations and Their Effectiveness', IEEE Transactions on Computers C-21(9).)
8. Una tarjeta gráfica (GPU) ejecuta la misma instrucción de manera simultánea sobre cientos de núcleos, cada uno operando sobre un elemento distinto de un arreglo de datos (por ejemplo, al aplicar el mismo filtro a cada píxel de una imagen). Según la taxonomía de Flynn, ¿en qué categoría se clasifica esta arquitectura?
Al aplicar la misma instrucción a múltiples elementos de datos en paralelo, la arquitectura corresponde a SIMD; MIMD requeriría instrucciones distintas por núcleo, y MISD/SISD no describen ese procesamiento simultáneo. (Flynn (1972), IEEE Transactions on Computers C-21(9).)
9. Un sistema operativo ejecuta tres procesos en una computadora con un solo núcleo, intercalando rápidamente su ejecución mediante cambios de contexto, de modo que ningún proceso corre físicamente al mismo tiempo que otro mientras avanzan en periodos que se traslapan. ¿Qué concepto describe correctamente esta situación?
La concurrencia es la gestión de tareas que progresan en periodos traslapados, incluso en un solo núcleo mediante intercalado; el paralelismo requiere ejecución física simultánea en múltiples unidades, lo cual no ocurre aquí. (Herlihy & Shavit, 'The Art of Multiprocessor Programming'; Tanenbaum & Van Steen, 'Distributed Systems: Principles and Paradigms'.)
10. A un servidor de una aplicación distribuida llegan en promedio λ = 5 solicitudes por segundo, y cada solicitud permanece en el sistema (espera más procesamiento) un promedio de W = 2 segundos. Suponiendo estado estable, según la Ley de Little, ¿cuál es el número promedio de solicitudes L presentes en el sistema en un instante dado?
La Ley de Little establece L=λ·W=5×2=10 solicitudes en promedio; sumar λ y W en lugar de multiplicarlos, o invertir el cociente, son errores frecuentes que producen los otros resultados. (Little, J. D. C. (1961), 'A Proof for the Queuing Formula L = λW', Operations Research 9(3).)
11. El teorema CAP describe una limitación fundamental de los sistemas de bases de datos distribuidas ante la ocurrencia de una partición de red. ¿Qué establece este teorema?
El teorema CAP (Gilbert & Lynch, 2002) establece que, ante una partición de red, un sistema distribuido solo puede satisfacer dos de las tres propiedades consistencia, disponibilidad y tolerancia a particiones; la durabilidad no forma parte de esas tres propiedades. (Gilbert & Lynch (2002), 'Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services', ACM SIGACT News 33(2); conjetura de Brewer (2000).)
12. Durante una partición de red que separa dos centros de datos de un sistema distribuido, un equipo de ingeniería decide que las réplicas de cada lado sigan aceptando lecturas y escrituras para no interrumpir el servicio, aun a riesgo de que ambos lados devuelvan valores distintos para el mismo dato hasta que la partición se resuelva. De acuerdo con el teorema CAP, ¿qué propiedad está priorizando este equipo sobre la consistencia?
Al seguir respondiendo en ambos lados de la partición a costa de la consistencia, el equipo prioriza la disponibilidad (sistema AP); la tolerancia a particiones ya está presente por la naturaleza del escenario y no es la propiedad priorizada en esta decisión. (Gilbert & Lynch (2002); Brewer (2000).)
13. El teorema CAP define tres propiedades que un sistema distribuido no puede garantizar simultáneamente ante una partición de red. ¿Cuál de las siguientes propiedades NO forma parte de las tres que considera el teorema CAP?
Las tres propiedades del teorema CAP son consistencia, disponibilidad y tolerancia a particiones; la durabilidad es una propiedad de las transacciones ACID, no una de las consideradas por el teorema CAP. (Gilbert & Lynch (2002), ACM SIGACT News 33(2).)
14. En un sistema distribuido donde algunos nodos pueden presentar fallas bizantinas (comportamiento arbitrario o malicioso, incluyendo el envío de información falsa o contradictoria a distintos nodos), se desea que el sistema alcance consenso correcto tolerando hasta f nodos con este tipo de falla. ¿Cuál es el número mínimo total de nodos N que se requiere?
Lamport, Shostak y Pease (1982) demostraron que el consenso tolerando f fallas bizantinas requiere al menos N=3f+1 nodos; N=2f+1 corresponde al umbral para fallas por caída (crash), no a fallas bizantinas. (Lamport, Shostak, Pease (1982), 'The Byzantine Generals Problem', ACM TOPLAS 4(3).)
15. Un sistema de cómputo distribuido debe seguir alcanzando consenso correcto aun si hasta f = 3 de sus nodos presentan fallas bizantinas simultáneamente. ¿Cuál es el número mínimo total de nodos N que debe tener el sistema?
Con N≥3f+1 y f=3, se requieren al menos N=3(3)+1=10 nodos; N=9 olvida sumar el +1, y N=7 corresponde erróneamente a la fórmula de tolerancia a fallas por caída (2f+1), no a fallas bizantinas. (Lamport, Shostak, Pease (1982), ACM TOPLAS 4(3).)
16. Un grupo de investigadores diseña un algoritmo determinista de consenso para un sistema completamente asíncrono (sin cotas conocidas de tiempo para los mensajes ni para el procesamiento), en el cual basta con que un solo proceso pueda fallar por caída. De acuerdo con el resultado de imposibilidad FLP, ¿qué puede afirmarse sobre este algoritmo?
El resultado FLP (Fischer, Lynch y Paterson, 1985) demuestra que ningún algoritmo determinista de consenso garantiza terminación en un sistema totalmente asíncrono si puede fallar por caída aunque sea un solo proceso, sin importar rondas adicionales o la paridad del número de procesos. (Fischer, Lynch, Paterson (1985), 'Impossibility of Distributed Consensus with One Faulty Process', Journal of the ACM 32(2).)
17. Lamport definió la relación 'sucede-antes' (happened-before, →) junto con un esquema de relojes lógicos para ordenar eventos en un sistema distribuido sin relojes físicos sincronizados. Si el evento a sucede-antes del evento b (a → b), ¿qué relación deben cumplir sus relojes lógicos C(a) y C(b)?
El esquema de relojes lógicos de Lamport (1978) garantiza que si a → b entonces C(a) < C(b); esta condición no exige una diferencia mínima específica entre los valores, por lo que C(a) ≤ C(b) − 2 no es la relación correcta. (Lamport, L. (1978), 'Time, Clocks, and the Ordering of Events in a Distributed System', Communications of the ACM 21(7).)
18. En un sistema distribuido con relojes lógicos de Lamport, dos eventos a y b ocurren en procesos distintos, no existe ningún intercambio de mensajes entre ellos ni una cadena causal que los conecte, y sus relojes lógicos resultan C(a) = 5 y C(b) = 7. ¿Qué puede concluirse correctamente sobre la relación entre a y b?
El recíproco de la relación de Lamport no siempre se cumple: un valor de reloj menor no implica precedencia causal cuando no hay cadena de mensajes que conecte los eventos, por lo que a y b son concurrentes, sin que esto signifique que ocurrieron al mismo tiempo físico. (Lamport (1978), Communications of the ACM 21(7).)
19. Un clúster que ejecuta un algoritmo de consenso basado en mayoría (como Paxos o Raft) está formado por N = 7 nodos. ¿Cuántos nodos como mínimo se necesitan para formar un quórum, y cuántas fallas por caída (crash) puede tolerar el sistema y seguir progresando?
El quórum es ⌊N/2⌋+1=⌊7/2⌋+1=4 nodos; con N=2f+1=7 se obtiene f=3 fallas tolerables. Un quórum de 3 sería minoría, y tolerar 4 fallas dejaría solo 3 nodos operando, insuficientes para el quórum. (Lamport (1998), 'The Part-Time Parliament' (Paxos), ACM TOCS 16(2); Ongaro & Ousterhout (2014), 'In Search of an Understandable Consensus Algorithm' (Raft), USENIX ATC.)
20. Dijkstra definió el semáforo como una variable entera manipulada únicamente mediante dos operaciones atómicas para coordinar procesos concurrentes. ¿Cuáles son estas dos operaciones y qué hace cada una?
Dijkstra (1968) definió P (wait) como la operación que decrementa el semáforo y bloquea al proceso si el valor queda negativo, y V (signal) como la que lo incrementa y despierta a un proceso en espera; las demás opciones invierten el efecto de cada operación. (Dijkstra, E. W. (1968), 'Cooperating Sequential Processes'; Silberschatz, 'Operating System Concepts'.)
21. Varios procesos concurrentes necesitan acceder de manera exclusiva a una sección crítica que actualiza un mismo archivo compartido, de modo que solo un proceso pueda estar dentro de la sección crítica a la vez. Un desarrollador propone usar un semáforo cuyo valor solo puede tomar 0 o 1, inicializado en 1. ¿Qué tipo de semáforo es este y qué garantiza?
Un semáforo con valores restringidos a {0,1} es un semáforo binario y, al inicializarse en 1, implementa exclusión mutua; un semáforo contador admite valores mayores y se usa para limitar el acceso a varios recursos simultáneos, no exclusión mutua estricta. (Dijkstra (1968); Silberschatz, 'Operating System Concepts'.)
22. El protocolo de confirmación en dos fases (Two-Phase Commit, 2PC) coordina una transacción distribuida entre varios nodos participantes a través de un nodo coordinador. ¿Cuáles son las dos fases que lo componen?
El 2PC consta de una fase de votación/preparación (prepare) y una fase de decisión (commit o abort); la fase de propuesta/aceptación por mayoría corresponde a algoritmos de consenso como Paxos, no al 2PC. (Gray, J. (1978), 'Notes on Data Base Operating Systems'; Coulouris, Dollimore, Kindberg, 'Distributed Systems: Concepts and Design'.)
23. En una transacción distribuida coordinada mediante el protocolo de confirmación en dos fases (2PC), todos los nodos participantes ya votaron a favor de confirmar (commit) y quedaron a la espera de la decisión final, pero el nodo coordinador falla antes de enviarles esa decisión y no hay forma de contactar a otro coordinador. ¿Qué ocurre con los nodos participantes en esta situación?
El 2PC es un protocolo bloqueante: si el coordinador falla después de que los participantes votaron a favor, estos no pueden decidir unilateralmente confirmar ni abortar sin riesgo de contradecir la decisión real, por lo que quedan bloqueados hasta que el coordinador se recupere. (Gray (1978); Coulouris, Dollimore, Kindberg, 'Distributed Systems: Concepts and Design'.)
24. El algoritmo de Peterson resuelve el problema de la exclusión mutua para dos procesos que comparten memoria, sin requerir instrucciones especiales de hardware. ¿Qué variables compartidas utiliza este algoritmo?
Peterson (1981) resolvió la exclusión mutua para dos procesos usando dos variables compartidas: un arreglo flag[2], que indica el interés de cada proceso en entrar a la sección crítica, y la variable turn, que resuelve el orden en caso de conflicto. (Peterson, G. L. (1981), 'Myths About the Mutual Exclusion Problem', Information Processing Letters 12(3).)
25. En el algoritmo de Peterson para dos procesos, ambos procesos establecen su bandera flag[i] en verdadero casi al mismo tiempo, indicando que desean entrar a la sección crítica. ¿Qué papel desempeña la variable turn para garantizar que solo uno de los dos entre primero, evitando además que el proceso perdedor espere de manera indefinida?
En el algoritmo de Peterson, cada proceso asigna turn al otro proceso justo antes de esperar; así, si ambos compiten, el valor final de turn decide de manera determinista quién espera y quién avanza, cumpliendo progreso y espera acotada. (Peterson (1981), Information Processing Letters 12(3).)
26. Para que ocurra un interbloqueo (deadlock) entre procesos concurrentes deben cumplirse simultáneamente las cuatro condiciones necesarias identificadas por Coffman. ¿Cuál de las siguientes NO es una de esas cuatro condiciones necesarias?
Las cuatro condiciones de Coffman son exclusión mutua, retención y espera, no apropiación (no preemption) y espera circular; la apropiación forzosa en cualquier momento es lo contrario de la condición real (no apropiación) y por eso no es una condición necesaria del interbloqueo. (Coffman, Elphick, Shoshani (1971), 'System Deadlocks', ACM Computing Surveys 3(2); Silberschatz, 'Operating System Concepts'.)
27. La Ley de Amdahl modela la aceleración (speedup) que se obtiene al paralelizar un programa en el que una fracción P del código es paralelizable y el resto es estrictamente secuencial. ¿Cuál de las siguientes expresiones corresponde a la fórmula de la Ley de Amdahl para la aceleración S(N) con N procesadores?
La Ley de Amdahl define S(N) = 1/((1−P)+P/N); la opción (1−P)+P·N corresponde en realidad a la fórmula de aceleración escalada de Gustafson, no a la de Amdahl. (Amdahl, G. M. (1967), AFIPS Conference Proceedings, vol. 30.)
28. En un programa donde el 90% del código (P = 0.90) puede ejecutarse en paralelo y el 10% restante es estrictamente secuencial, ¿cuál es la aceleración máxima teórica que puede alcanzarse según la Ley de Amdahl, sin importar cuántos procesadores adicionales se agreguen?
Con P=0.90, el límite es S_max=1/(1−P)=1/0.10=10×; 20× corresponde al límite con P=0.95, un valor cercano pero distinto. (Amdahl (1967); Hennessy & Patterson, Computer Architecture: A Quantitative Approach, ley de Amdahl.)
29. ¿Cuál es la diferencia conceptual principal entre la Ley de Amdahl y la Ley de Gustafson al analizar la aceleración de un sistema paralelo?
Amdahl analiza un problema de tamaño fijo, mientras que Gustafson reevalúa la ley suponiendo que el tamaño del problema escala con el número de procesadores. (Gustafson, J. L. (1988), 'Reevaluating Amdahl's Law', Communications of the ACM 31(5).)
30. Un sistema paralelo tiene una fracción paralelizable P = 0.95 y se ejecuta con N = 20 procesadores, donde el tamaño del problema escala con el número de procesadores. Según la Ley de Gustafson, S(N) = (1 − P) + P·N, ¿cuál es la aceleración escalada resultante?
Con P=0.95 y N=20, S(N)=(1−P)+P·N=0.05+19=19.05×; 19× resulta de considerar solo el término P·N y omitir el sumando de la fracción secuencial (1−P). (Gustafson, J. L. (1988), Communications of the ACM 31(5).)
31. En cómputo paralelo, la eficiencia E de un sistema con N procesadores se define a partir de la aceleración S como E = S/N. ¿Qué rango de valores puede tomar típicamente E y qué significa que E = 1?
La eficiencia se define como E=S/N y cumple 0<E≤1, siendo E=1 la aceleración lineal ideal; valores mayores a 1 no corresponden a la definición estándar. (Grama, Gupta, Karypis, Kumar, Introduction to Parallel Computing, 2ª ed., Addison-Wesley.)
32. Un programa distribuido tarda T1 = 100 segundos al ejecutarse en un solo procesador y T8 = 20 segundos al ejecutarse en 8 procesadores. Con S = T1/T8 y E = S/N, ¿cuál es la eficiencia E del sistema con 8 procesadores?
S=T1/T8=100/20=5 y E=S/N=5/8=0.625 (62.5%); calcular T8/T1 en lugar de T1/T8 produce el resultado erróneo de 20%. (Grama, Gupta, Karypis, Kumar, Introduction to Parallel Computing, 2ª ed.)
33. La taxonomía de Flynn clasifica las arquitecturas de cómputo según sus flujos de instrucciones y de datos. ¿Cuáles son las cuatro categorías que define esta taxonomía?
Flynn clasifica las arquitecturas en SISD, SIMD, MISD y MIMD; SPMD y NUMA/UMA son términos de otros contextos del cómputo paralelo, no categorías de esta taxonomía. (Flynn, M. J. (1972), IEEE Transactions on Computers C-21(9).)
34. Una unidad de procesamiento gráfico (GPU) ejecuta una sola instrucción que se aplica simultáneamente sobre múltiples flujos de datos, por ejemplo sumar el mismo valor a cada elemento de un arreglo grande a la vez. Según la taxonomía de Flynn, ¿a qué categoría corresponde esta forma de procesamiento?
Un solo flujo de instrucciones aplicado a múltiples flujos de datos corresponde a SIMD, la categoría típica de las GPU y los procesadores vectoriales. (Flynn, M. J. (1972), IEEE Transactions on Computers C-21(9).)
35. Un servidor de solicitudes recibe en promedio λ = 50 solicitudes por segundo, y cada solicitud permanece en el sistema un tiempo promedio W = 0.2 segundos antes de ser atendida por completo. Según la Ley de Little (L = λ·W), ¿cuántas solicitudes hay en promedio dentro del sistema en un instante dado?
Por la Ley de Little, L=λ·W=50×0.2=10; dividir en lugar de multiplicar (50/0.2=250) invierte la relación entre las variables. (Little, J. D. C. (1961), Operations Research 9(3).)