Saltar al contenido principal

Práctica 1.2: Auditoría de seguridad y vivacidad

Fecha límite de entrega: 13 de octubre de 2026 a las 15:00
Lenguaje de trabajo: C (POSIX Threads pthread.h)
Código de inicio: 📥 game_of_life_base.zip

1. Objetivos de la práctica​

  1. Adoptar el rol de auditor de software concurrente: Diagnosticar, clasificar e identificar fallos en programas multihilo preexistentes sin disponer de pistas previas sobre sus defectos.
  2. Utilizar herramientas de diagnóstico:
    • ThreadSanitizer (TSan) y Helgrind (Valgrind): Detectar violaciones de seguridad (Safety) como condiciones de carrera (Data Races).
    • top / htop: Diagnosticar violaciones de vivacidad (Liveness) analizando el consumo de CPU y el estado de los procesos.
  3. Implementar una solución robusta: Construir una versión limpia e inmune a fallos (game_of_life_solucion.c) aplicando doble buffer, carga de plantillas externas y sincronización correcta mediante cerrojos y variables de condición/barreras.

2. Introducción al Juego de la Vida​

El Juego de la Vida es un autómata celular diseñado por John Conway en 1970 sobre una rejilla bidimensional de células. Cada celda puede estar viva (█) o muerta ( ).

=== Juego de la Vida - Generación 14 ===
┌──────────────────────────────────────────────────────────────────────┐
│                                                                      │
│       ██                                                             │
│         ██                                                           │
│       ████                                                           │
│                                                                      │
│                                    ████                              │
│                                    █   █                             │
│                                    █                                 │
│                                   ██                                 │
│                                                                      │
└──────────────────────────────────────────────────────────────────────┘

Reglas de evolución de generación:​

En cada paso de tiempo, el estado de una celda (y,x)(y, x) en la siguiente generación depende del número de sus 8 celdas vecinas contiguas en el instante actual (dimensión 70×1570 \times 15):

  1. Supervivencia: Una celda viva con 2 o 3 vecinas vivas permanece viva.
  2. Fallecimiento: Una celda viva con menos de 2 vecinas vivas muere por despoblación, o con más de 3 vecinas vivas muere por sobrepoblación.
  3. Nacimiento: Una celda muerta con exactamente 3 vecinas vivas pasa a estar viva.

3. Código base de la práctica​

Descarga el paquete comprimido de partida:
📥 game_of_life_base.zip

El paquete contiene 3 variantes del programa escritas en C con hilos POSIX (pthread), cada una con un defecto de concurrencia diferente, además del directorio de plantillas de prueba:

  • game_of_life_v1.c
  • game_of_life_v2.c
  • game_of_life_v3.c
  • templates/ (template1.txt, template2.txt, template3.txt)
  • Makefile

Ejecución con plantillas:​

Los programas permiten indicar opcionalmente el fichero de plantilla a cargar y el número de hilos de trabajo:

# Ejecución por defecto (template1.txt con 4 hilos):
./game_of_life_v1

# Cargar una plantilla concreta (ej. template2.txt) con 4 hilos:
./game_of_life_v1 templates/template2.txt 4

4. Herramientas de diagnóstico y mecanismos de sincronización​

A. Herramientas de análisis dinámico de memoria: ThreadSanitizer y Helgrind​

  • ThreadSanitizer (TSan): Es una herramienta de instrumentación en tiempo de ejecución de LLVM/GCC diseñada para detectar accesos a memoria no coordinados (Data Races). Compila los programas añadiendo el flag -fsanitize=thread: 
    gcc -O1 -g -fsanitize=thread game_of_life_v1.c -o game_of_life_v1 -lpthread
  • Helgrind (Valgrind): Es una herramienta de depuración basada en emulación que analiza la sincronización de hilos POSIX sin necesidad de recompilar el binario con banderas especiales: 
    valgrind --tool=helgrind ./game_of_life_v1

B. Herramientas de monitoreo de procesos (top / htop)​

top y htop permiten inspeccionar en tiempo real el consumo de CPU y el estado de los hilos del sistema operativo:

  • Uso de CPU: Observa si el proceso consume cerca del 0% de CPU o el 100% / 400% de CPU.
  • Estado del proceso (S / R): Indica si los hilos están dormidos/bloqueados por el SO (S - Sleeping) o si están ejecutando instrucciones continuamente (R - Running).

C. Introducción a la sincronización: cerrojos (mutex) y barreras​

Dado que en las sesiones de teoría aún no se han estudiado en detalle las primitivas de sincronización, a continuación se introducen conceptualmente los dos mecanismos fundamentales que necesitarás para auditar e implementar programas concurrentes en C con POSIX Threads (pthread.h).

1. Cerrojos de exclusión mutua (pthread_mutex_t)​

¿Qué problema resuelven?​

Cuando dos o más hilos intentan acceder y modificar la misma variable o estructura de datos compartida en memoria de forma simultánea, se produce una condición de carrera (Data Race). El resultado final se vuelve impredecible y arbitrario según qué hilo sea ligeramente más rápido.

El concepto:​

Un mutex (MUTual EXclusion) es un mecanismo que actúa como la única llave de entrada a un bloque de código sensible (denominado sección crítica):

  • Solo existe una llave asociada a cada mutex.
  • Para entrar a modificar el recurso compartido, un hilo debe adquirir la llave (pthread_mutex_lock).
  • Si un hilo intenta adquirir la llave mientras otro hilo la posee, el sistema operativo bloquea y duerme al hilo solicitante hasta que la llave sea liberada (pthread_mutex_unlock).
Sintaxis en C (pthread.h):​
  • Declaración e inicialización estática: 
    pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
  • Entrada y salida de la sección crítica: 
    pthread_mutex_lock(&mutex);   // Bloquea el hilo si el cerrojo está ocupado
    /* --- Sección crítica: lectura/escritura segura de variables compartidas --- */
    pthread_mutex_unlock(&mutex); // Libera el cerrojo para el resto de hilos

2. Barreras de sincronización (pthread_barrier_t)​

¿Qué problema resuelven?​

En los algoritmos distribuidos por fases o por turnos (como la simulación del Juego de la Vida), el cálculo de la generación t+1t+1 depende de que todos los hilos hayan terminado de calcular la generación tt. Si un hilo rápido comenzara a calcular la generación t+1t+1 mientras un hilo lento aún no ha finalizado la generación tt, se leerían y sobrescribirían datos erróneos.

El concepto:​

Una barrera es un punto de encuentro colectivo para un grupo de NN hilos:

  • Imagina un grupo de excursionistas realizando una ruta de senderismo: ningún excursionista arranca la siguiente etapa hasta que todos los miembros del grupo hayan llegado al punto de control.
  • Cada hilo al finalizar su tarea parcial en la fase actual invoca un punto de espera (pthread_barrier_wait) y queda bloqueado.
  • En el instante exacto en que llega el último hilo de los NN requeridos, la barrera se desbloquea simultáneamente para todos y los NN hilos prosiguen con la siguiente etapa.
Sintaxis en C (pthread.h):​
  • Inicialización: Se indica el número total NN de hilos que se deben esperar: 
    pthread_barrier_t barrier;
    pthread_barrier_init(&barrier, NULL, num_threads);
  • Punto de espera: 
    pthread_barrier_wait(&barrier); // Bloquea al hilo hasta que coincidan los N hilos
  • Destrucción: Libera los recursos de la barrera al finalizar el programa: 
    pthread_barrier_destroy(&barrier);

5. Ejercicios​

Ejercicio 1: Auditoría de las variantes (v1, v2 y v3)​

Deberás auditar cada una de las tres variantes (game_of_life_v1.c, game_of_life_v2.c y game_of_life_v3.c) combinando compilación estándar, análisis con ThreadSanitizer/Helgrind y monitoreo de procesos con top/htop.

Cuestiones a responder en la memoria:​

  1. Identificación de fallos:
    • Asigna a cada archivo (v1, v2 y v3) el fallo específico que padece: condición de carrera (Data Race), interbloqueo pasivo (Deadlock) o interbloqueo activo / espera ocupada (Livelock / Spin-Wait) y explica cómo has conseguido llegar a esa conclusión.
  2. Análisis de seguridad (Safety):
    • Para la variante que sufre una Data Race, adjunta el informe emitido por ThreadSanitizer o Helgrind e indica las líneas exactas del código fuente involucradas en la lectura y escritura conflictivas.
    • Explica por qué escribir directamente in-place sobre la matriz compartida durante la iteración corrompe la semántica del algoritmo.
  3. Análisis de vivacidad (Liveness):
    • Para la variante que sufre un Deadlock, indica el % de CPU registrado en top/htop y explica qué secuencia en la adquisición de cerrojos (mutex) provoca el bloqueo.
    • Para la variante que sufre un Livelock / Spin-Wait, indica el % de CPU registrado en top/htop y explica por qué el proceso consume recursos de reloj de la CPU sin lograr progresar de generación.
    • Resume la diferencia fundamental a nivel de estado en el planificador del SO entre un Deadlock (pasivo) y un Livelock (activo).

Ejercicio 2: Implementación de la solución robusta (game_of_life_solucion.c)​

Implementa en game_of_life_solucion.c una versión libre de fallos de seguridad y vivacidad.

Requisitos de la solución:​

  1. Doble buffer: Mantén dos matrices independientes en memoria: curr_grid[HEIGHT][WIDTH] (para lectura del estado en tiempo tt) y next_grid[HEIGHT][WIDTH] (para escritura limpia del estado en tiempo t+1t+1). Al terminar cada paso de generación, intercambia los punteros de ambas matrices.
  2. Sincronización con barrera o cerrojo+condición: Implementa un mecanismo de barrera de hilos para asegurar que:
    • Ningún hilo intercambia los buffers hasta que todos hayan terminado de escribir la generación t+1t+1.
    • Ningún hilo empieza la generación t+2t+2 hasta que el Hilo 0 haya intercambiado los buffers y limpiado la pantalla.
  3. Carga de plantillas: Incorporar el lector de plantillas load_template() para permitir probar patrones desde ficheros .txt.
  4. Refresco limpio de pantalla: Limpia la pantalla en cada generación utilizando secuencias de escape ANSI (\033[H\033[J), enmarcando la rejilla con borde ASCII/Unicode y añadiendo un retardo de refresco adecuado (usleep(100000)) para permitir una visualización fluida de la simulación a 10 FPS.
  5. Ausencia total de fallos:
    • La compilación con -fsanitize=thread o el análisis con Helgrind no debe emitir ninguna advertencia de Data Race.
    • La simulación debe ejecutarse de forma fluida a 10 FPS sin congelaciones de CPU al 0% ni consumos del 100%.

6. Criterios de evaluación y entrega​

La entrega se realizará en la plataforma pracdlsi en un archivo comprimido denominado p1_2.tgz.

El archivo comprimido debe incluir:

  1. auditoria.pdf (o auditoria.md): Informe documentado respondiendo a todas las cuestiones del Ejercicio 1, identificando qué error corresponde a v1, v2 y v3, adjuntando trazas de TSan/Helgrind y registros de top/htop.
  2. game_of_life_solucion.c: Código fuente en C completamente corregido.
  3. Makefile: Fichero para compilar el proyecto corregido de forma automatizada.