Concurrencia y sincronización — ejercicios tipo examen con condiciones de carrera, semáforos paso a paso y la leche de siempre (y un Peterson que no te deja entrar)

Respuesta: Los tres procesos son concurrentes aunque nunca se ejecuten dos instrucciones suyas en el mismo instante

Concurrencia es la existencia simultánea de varios procesos en ejecución. No implica ejecución simultánea: con un núcleo, los procesos se intercalan.

• V — El paralelismo es un caso particular de la concurrencia.
• F — Si dos procesos son concurrentes, se están ejecutando en dos procesadores distintos.
• V — Para que haya paralelismo hacen falta varios procesadores (o núcleos).
• F — La computación distribuida es concurrencia en un único procesador muy rápido.

Todo paralelismo es concurrencia, pero no al revés. Paralelismo = ejecución simultánea en varios procesadores; si esos procesadores están en distintas máquinas unidas por una red, hablamos de computación distribuida.

Cuando varios procesos existen a la vez hablamos de concurrencia. Si además se ejecutan a la vez en varios procesadores, es paralelismo. Y si esos procesadores están repartidos por una red, la computación es distribuida.

De más general a más concreto: concurrencia → paralelismo → computación distribuida (paralelismo en red).

Respuesta: Llamando a una API de hilos, como pthreads · Con objetos concurrentes que ofrece el lenguaje · Con sentencias concurrentes del propio lenguaje

Tres maneras: una API (pthreads), objetos concurrentes (Java, C++) y sentencias concurrentes (Ada, Go…).

Respuesta: Para describir de forma natural actividades del mundo real que ocurren a la vez · Para marcar trozos de código que pueden ir en paralelo y aprovechar varios procesadores · Para escribir con más facilidad ciertos algoritmos

Expresar mejor el mundo real, aprovechar varios procesadores y simplificar algunos algoritmos. El precio: resultados que pueden depender del intercalado.

Respuesta: Porque el resultado depende de cómo se intercalen las instrucciones de los hilos, y ese intercalado cambia de una ejecución a otra

Un programa concurrente tiene que funcionar con todos los intercalados posibles; probarlo diez veces y que salga bien no demuestra nada.

Respuesta: Condición de carrera

Es una condición de carrera: dos hilos «corren» hacia el mismo dato y gana quien escribe el último.

Respuesta: 11

H1: 10 → 11. H2 también leyó 10 antes de que H1 escribiera: 10 → 11. El segundo escribe pisa el 11 con otro 11. Se pierde una actualización.

Orden correcto:

1. Cargar el valor de contador desde la memoria a un registro
2. Sumar 1 al registro
3. Guardar el registro en la posición de memoria de contador

Leer (lw), sumar (addi) y escribir (sw). Si el planificador expulsa al hilo entre el primer y el último paso, otro hilo puede leer un valor viejo.

Respuesta: El trozo de código de un proceso o hilo donde accede a datos que comparte con otros

Sección crítica: segmento de código donde se accede a datos compartidos. Requisito básico: exclusión mutua, nunca más de un proceso o hilo dentro.

Respuesta: Exclusión mutua · Progreso · Espera limitada

Exclusión mutua (uno dentro como mucho), progreso (si está libre, se decide pronto y solo entre los que quieren entrar) y espera limitada (nadie se cuela delante de ti sin límite).

• Exclusión mutua → Nunca hay más de un hilo dentro de la sección crítica
• Progreso → Si nadie está dentro y alguien quiere entrar, la decisión la toman solo los interesados y en un tiempo finito
• Espera limitada → Hay un máximo de veces que otros pueden entrar antes que un hilo que ya lo ha pedido

La exclusión mutua protege el dato; el progreso y la espera limitada evitan que alguien se quede esperando para siempre.

• V — Mientras un proceso está en su sección crítica, ningún otro proceso del sistema puede avanzar en esa CPU.
• F — Funciona igual de bien en un multiprocesador.
• F — Garantiza la espera limitada.
• V — Impide que el temporizador expulse al proceso mientras toca el dato compartido.

Sin interrupciones no hay expulsión, así que en un solo procesador hay exclusión mutua. Pero congela toda la concurrencia, no sirve con varios procesadores (cada uno tiene sus interrupciones) y no garantiza espera limitada.

• Instrucción atómica → Se ejecuta entera sin que nada la interrumpa
• Test-and-set → Pone la variable a verdadero y devuelve el valor que tenía antes
• Compare-and-swap → Si la variable vale lo esperado, le pone un valor nuevo y devuelve verdadero
• LOCK BTS → Versión de x86: la CPU se queda el bus mientras hace el test-and-set

Las tres son ayudas del hardware: leen y modifican una celda de memoria en un solo paso indivisible. IBM ya tenía en los años 60 un SWAP atómico; MIPS y ARM usan la pareja LL/SC.

Respuesta: La llamada devuelve true, ocupado sigue a true y el hilo da otra vuelta esperando

test-and-set devuelve el valor antiguo. Si era true, alguien está dentro y el bucle sigue girando (espera activa). Solo entra quien recibe false.

Respuesta: Se despierta uno de los dos bloqueados y el semáforo sigue valiendo 0

signal despierta a un proceso si hay alguno esperando; solo si la cola está vacía suma 1. Por eso el valor no sube cuando alguien estaba dormido.

Respuesta: Que los dos miren, vean que no hay nota y compren los dos, porque el cambio de contexto llega antes de dejar la nota

Mirar la nota y dejarla son dos pasos separados. Si los dos miran antes de que ninguno la deje, compran los dos: la «solución» funciona casi siempre y falla en el peor momento.

Respuesta: Que los dos dejen su nota, cada uno vea la del otro y ninguno compre

La exclusión mutua queda resuelta, pero si los dos dejan la nota a la vez, los dos se echan atrás y la nevera sigue vacía.

• V — Garantiza exclusión mutua entre los dos procesos.
• V — Obliga a que los procesos entren alternándose, quieran o no.
• F — Cumple el requisito de progreso.
• V — Mientras espera, el proceso consume CPU dando vueltas al bucle.

Si al proceso 2 le toca el turno pero no quiere entrar, el 1 no puede volver a entrar aunque la sección esté libre: alternancia estricta, falla el progreso.

Respuesta: Cumple exclusión mutua, progreso y espera limitada · Usa dos variables «quiero entrar» y una variable turno, todas compartidas · Un procesador o compilador moderno que reordene lecturas y escrituras puede romperlo

Peterson combina la nota con nombre (quiere1, quiere2) con la variable turno. Es correcto en teoría, pero solo para dos procesos, con espera activa y sensible a la reordenación de instrucciones.

Respuesta: El hilo 1

El hilo 2 espera mientras quiere1 && turno == 1, y las dos cosas son ciertas. El hilo 1 espera mientras quiere2 && turno == 2, y turno vale 1: entra. El último que escribe turno es el que cede.

Respuesta: Tiene dos estados, libre y adquirido, y empieza libre · Si un hilo hace lock() y el mutex ya está adquirido, ese hilo se bloquea hasta conseguirlo · Al hacer unlock(), si hay hilos esperando, uno de ellos lo adquiere y se desbloquea

mutex = mutual exclusion. lock() adquiere (o bloquea), unlock() libera (y despierta a uno). Las dos operaciones son atómicas.

Respuesta: Siempre van asociadas a un mutex · wait() bloquea al hilo y, mientras duerme, libera el mutex · Si nadie espera, signal() no hace nada · broadcast() despierta a todos los hilos de la cola

Una variable condición es una cola de hilos que esperan una condición dentro de una sección crítica. Al despertar, el hilo vuelve a adquirir el mutex antes de seguir.

• Estilo Hoare → Q sigue enseguida y P se queda sin el mutex hasta que Q termine
• Estilo Mesa → Q pasa a listo, pero espera a que P suelte el mutex
• broadcast → Se despiertan todos los que esperan y compiten por el mutex
• Desbloqueo FIFO → Se despierta el que lleva más tiempo esperando

El estilo Mesa es el más usado hoy. Cuando hay varios esperando, la elección puede ser FIFO, por prioridades o al azar; broadcast los despierta a todos.

Respuesta: Porque con el estilo Mesa, cuando el hilo vuelve a tener el mutex la condición puede haber cambiado otra vez, y hay que comprobarla de nuevo

Entre el signal y el momento en que el hilo despierto recupera el mutex, otro hilo puede entrar y volver a llenar (o vaciar) el búfer. El while vuelve a mirar.

Los semáforos los propuso Dijkstra en 1965. De los monitores de Hoare (1972) salen el mutex y las variables condición. Los canales y los buzones no necesitan memoria compartida.

Con memoria compartida: semáforos, regiones críticas condicionales y monitores. Sin memoria compartida: canales, buzones y promesas y futuros.

Respuesta: Cuando cola == N

Productor: espera si está lleno (cola == N). Consumidor: espera si está vacío (cola == 0).

Respuesta: 4 · 5 · 3

Si los dos leen 4 antes de que ninguno escriba, gana el último que escribe: 5 o 3. Solo el orden «uno entero y luego el otro» da el 4 correcto.

• V — Pueden leer varios lectores a la vez.
• F — Un escritor puede escribir mientras hay lectores dentro, si no tocan la misma fila.
• V — Si se da prioridad a los lectores, un escritor puede esperar indefinidamente.
• F — Si se da prioridad a los escritores, desaparece todo riesgo de inanición.

Varios lectores o un solo escritor, nunca mezclados. Prioridad a los lectores → inanición de escritores; prioridad a los escritores → inanición de lectores.

Respuesta: Que los pares cojan primero un palillo y los impares el otro · Dejar que como mucho cuatro filósofos intenten coger palillos a la vez · Coger los dos palillos en una sola operación atómica

Si los cinco cogen el palillo izquierdo a la vez, cada uno espera el que tiene el vecino: interbloqueo. Las tres soluciones de los apuntes rompen ese círculo.

Los dos hilos leen 200 antes de que nadie escriba. El hilo 1 escribe 230, pero el hilo 2 escribe después su 120 encima: los 30 añadidos se pierden. Lo correcto era 200 + 30 − 80 = 150 y sale 120.

m baja a 0 cuando entra A, y B y C se ponen en cola. Cuando A hace signal, m NO sube: el permiso pasa directamente a B (el primero de la cola). Lo mismo con B → C. Solo el último signal, sin nadie esperando, devuelve m a 1.

Un semáforo contador cuenta impresoras libres. A y B se llevan las dos (2 → 0); C y después D se bloquean. Cada signal con alguien esperando le pasa la impresora sin tocar el valor; al final, sin nadie esperando, vuelve a subir a 1 y a 2.

Turno 3: no quedan huecos y D se bloquea. Turno 4: R saca un trozo y su signal(huecos) despierta a D, así que huecos sigue a 0. Turno 6: el búfer está vacío y R se bloquea. Turno 7: D mete su trozo sin esperar (ya tenía el permiso) y su signal(llenos) despierta a R, así que llenos sigue a 0.

El hilo 2 encuentra quiere1 = false y entra directamente. El hilo 1 levanta la mano, cede (turno = 2) y espera, porque el hilo 2 quiere y es su turno. En cuanto el hilo 2 pone quiere2 = false, la condición del hilo 1 deja de cumplirse y entra.

Respuesta modelo:

Una condición de carrera ocurre cuando dos o más hilos acceden a un dato compartido, al menos uno lo modifica y el resultado depende del orden en que se intercalen sus instrucciones.

Ejemplo: contador vale 7 y dos hilos hacen contador = contador + 1. En la CPU son tres pasos: leer a un registro, sumar y escribir. Si el hilo 1 lee 7 y le quitan la CPU antes de escribir, el hilo 2 también lee 7; los dos calculan 8 y los dos escriben 8. Se pierde una suma: debería valer 9.

Se evita convirtiendo el acceso al dato en una sección crítica con exclusión mutua: por ejemplo, rodeando la suma con mutex.lock() y mutex.unlock(), o con una instrucción atómica. Así, el segundo hilo no puede leer hasta que el primero haya escrito.

Lo importante es el porqué: el hilo trabaja con una copia en su registro y escribe un valor calculado a partir de un dato que ya está viejo.

Respuesta modelo:

1. Exclusión mutua: nunca puede haber más de un proceso o hilo ejecutando su sección crítica.

2. Progreso: si nadie está en la sección crítica y hay procesos que quieren entrar, solo esos procesos participan en la decisión y esta se toma en un tiempo finito.

3. Espera limitada: existe un límite al número de veces que otros procesos pueden entrar antes que uno que ya ha pedido entrar.

Inhibir las interrupciones consigue exclusión mutua en un único procesador, porque sin interrupciones nadie expulsa al proceso. Pero no es buena solución general: suspende toda la concurrencia del sistema (perjudica a los que no quieren entrar), no sirve en multiprocesadores (cada CPU tiene sus interrupciones y otra puede entrar) y no garantiza espera limitada.

Un examen suele pedir el nombre exacto de los requisitos: exclusión mutua, progreso y espera limitada.

Respuesta modelo:

Un mutex sirve para tener acceso exclusivo a un recurso. Tiene dos estados (libre y adquirido) y dos operaciones atómicas: lock() lo adquiere o bloquea al proceso si ya estaba adquirido; unlock() lo libera y, si hay procesos esperando, uno de ellos lo adquiere.

Una variable condición sirve para esperar a que se cumpla una condición dentro de una sección crítica. Siempre va asociada a un mutex y gestiona una cola de procesos. Operaciones: wait() bloquea al proceso y libera el mutex mientras duerme (al despertar debe volver a adquirirlo); signal() despierta a uno de la cola (si no hay nadie, no hace nada); broadcast() despierta a todos.

Tras un signal de P con Q esperando: en el estilo Hoare, Q se reanuda inmediatamente y P pierde el mutex; en el estilo Mesa, Q se desbloquea pero espera a que P libere el mutex. Mesa es el más usado, y por eso la condición se comprueba con while y no con if.

La pista para no mezclarlas: el mutex responde a «¿puedo entrar?»; la variable condición, a «¿ya se cumple lo que espero?».

Respuesta modelo:

Productores y consumidores comparten una cola FIFO de N posiciones. El productor no debe meter si el búfer está lleno (cola == N) y el consumidor no debe sacar si está vacío (cola == 0). Además, cola++ y cola– tocan un dato compartido: sin protección, un intercalado puede dejar un valor incorrecto.

Productor: mutex.lock(); while (cola == N) cprod.wait(); buffer[in] = cosa; in = (in + 1) % N; cola++; ccons.signal(); mutex.unlock();

Consumidor: mutex.lock(); while (cola == 0) ccons.wait(); cosa = buffer[out]; out = (out + 1) % N; cola--; cprod.signal(); mutex.unlock(); consumir(cosa);

El mutex garantiza que solo uno toca buffer, in, out y cola. Cada uno espera en su variable condición y avisa al otro con signal después de cambiar el estado. Se usa while porque, con el estilo Mesa, al despertar hay que volver a comprobar la condición.

consumir(cosa) va después de unlock(): no toca datos compartidos y, si estuviera dentro, haría esperar al productor sin motivo.