Granularidad y costo de los bloqueos

1. Qué es la granularidad

La granularidad de un bloqueo se refiere a cuánto código protege un solo mutex. Un bloqueo de granularidad gruesa (coarse-grained) protege una gran sección de código o una estructura de datos completa. Un bloqueo de granularidad fina (fine-grained) protege una pequeña sección o un elemento individual.

La granularidad es una decisión de diseño que afecta al rendimiento y a la complejidad del código. No hay una respuesta única: depende de la carga de trabajo, del patrón de acceso y de los requisitos del sistema.

2. Granularidad gruesa (coarse-grained)

En la granularidad gruesa, un solo mutex protege toda la estructura de datos o todo el código que accede a ella:

/* Un solo mutex para toda la lista. */
typedef struct {
    nodo_t *lista;
    pthread_mutex_t mutex;
} lista_t;

void insertar(lista_t *l, int valor) {
    pthread_mutex_lock(&l->mutex);
    /* Toda la operación de inserción está protegida. */
    nodo_t *nuevo = malloc(sizeof(nodo_t));
    nuevo->valor = valor;
    nuevo->siguiente = l->lista;
    l->lista = nuevo;
    pthread_mutex_unlock(&l->mutex);
}

int buscar(lista_t *l, int valor) {
    pthread_mutex_lock(&l->mutex);
    /* Toda la búsqueda está protegida. */
    nodo_t *actual = l->lista;
    while (actual) {
        if (actual->valor == valor) {
            pthread_mutex_unlock(&l->mutex);
            return 1;
        }
        actual = actual->siguiente;
    }
    pthread_mutex_unlock(&l->mutex);
    return 0;
}

Ventajas:

• Simplicidad: un solo mutex, fácil de razonar.
• Sin deadlock: con un solo lock no hay ciclos de espera.
• Fácil de verificar: con ThreadSanitizer es fácil detectar errores.

Desventajas:

• Baja concurrencia: todos los accesos se serializan.
• Alta contención: todos los hilos compiten por el mismo lock.
• Pobre escalabilidad: añadir más hilos no mejora el rendimiento.

3. Granularidad fina (fine-grained)

En la granularidad fina, cada elemento o grupo de elementos tiene su propio mutex:

/* Un mutex por nodo. */
typedef struct nodo {
    int valor;
    struct nodo *siguiente;
    pthread_mutex_t mutex;
} nodo_t;

typedef struct {
    nodo_t *lista;
    pthread_mutex_t lista_mutex;  /* protege la cabeza de la lista */
} lista_t;

void insertar(lista_t *l, int valor) {
    nodo_t *nuevo = malloc(sizeof(nodo_t));
    nuevo->valor = valor;
    pthread_mutex_init(&nuevo->mutex, NULL);

    /* Solo bloquear la cabeza de la lista. */
    pthread_mutex_lock(&l->lista_mutex);
    nuevo->siguiente = l->lista;
    l->lista = nuevo;
    pthread_mutex_unlock(&l->lista_mutex);
}

int buscar(lista_t *l, int valor) {
    pthread_mutex_lock(&l->lista_mutex);
    nodo_t *actual = l->lista;
    pthread_mutex_unlock(&l->lista_mutex);

    /* Buscar sin lock (puede ser inseguro si se inserta concurrentemente). */
    while (actual) {
        if (actual->valor == valor) return 1;
        actual = actual->siguiente;
    }
    return 0;
}

Ventajas:

• Alta concurrencia: los hilos pueden acceder a distintos elementos simultáneamente.
• Baja contención: los hilos rara vez compiten por el mismo lock.
• Mejor escalabilidad: añadir más hilos mejora el rendimiento.

Desventajas:

• Complejidad: más mutexes, más código, más posibilidad de errores.
• Riesgo de deadlock: si se adquieren múltiples locks, puede haber ciclos de espera.
• Overhead: más mutexes consumen más memoria y tiempo de inicialización.
• Difícil de verificar: ThreadSanitizer puede no detectar todos los errores.

4. Comparación

5. La contención

La contención (contention) es el grado en que los hilos compiten por el mismo lock. Con alta contención, los hilos pasan más tiempo esperando el lock que haciendo trabajo útil.

La contención se mide como la fracción de tiempo que un hilo pasa esperando el lock vs. ejecutando la sección crítica. Si un hilo pasa el 80 % del tiempo esperando, la contención es alta.

La contención afecta al rendimiento de varias formas:

• Menos trabajo útil: los hilos que esperan no avanzan.
• Más cambios de contexto: los hilos se bloquean y desbloquean.
• Más tráfico en el bus: los hilos compiten por el lock (especialmente con spinlocks).
• Menor escalabilidad: añadir más hilos no mejora el rendimiento.

La solución a la alta contención no es un lock mejor, sino reducir la contención: usar más locks, reducir la sección crítica, o rediseñar el programa.

6. La ley de Amdahl en la práctica

En el tema 1 viste la ley de Amdahl: la aceleración está limitada por la parte serie del programa. La sincronización es una fuente de serialización: cada lock convierte código paralelo en serie.

Si una sección crítica protegida por un lock representa una fracción f del tiempo de ejecución, y el lock se adquiere con frecuencia, la aceleración máxima es:

Aceleración máxima = 1 / f (si la sección crítica es completamente serie).

Por ejemplo, si el 10 % del tiempo se pasa en la sección crítica (adquiriendo y liberando el lock), la aceleración máxima es 10×, sin importar cuántos núcleos haya.

La granularidad fina reduce f (la fracción serie) al acortar la sección crítica y reducir la contención. Pero añade overhead (más locks, más código).

7. Un ejemplo desarrollado

Un programa que mantiene un array de contadores. Varios hilos incrementan contadores aleatorios. Se compara la granularidad gruesa (un lock para todo el array) con la fina (un lock por contador):

#define _POSIX_C_SOURCE 200809L
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NUM_CONTADORES 1000
#define INCREMENTOS 100000

/* Granularidad gruesa: un lock para todo. */
typedef struct {
    int contadores[NUM_CONTADORES];
    pthread_mutex_t mutex;
} array_grueso_t;

/* Granularidad fina: un lock por contador. */
typedef struct {
    int valor;
    pthread_mutex_t mutex;
} contador_fino_t;

typedef struct {
    contador_fino_t contadores[NUM_CONTADORES];
} array_fino_t;

/* Función de incremento con granularidad gruesa. */
void incrementar_grueso(array_grueso_t *a, int idx) {
    pthread_mutex_lock(&a->mutex);
    a->contadores[idx]++;
    pthread_mutex_unlock(&a->mutex);
}

/* Función de incremento con granularidad fina. */
void incrementar_fino(array_fino_t *a, int idx) {
    pthread_mutex_lock(&a->contadores[idx].mutex);
    a->contadores[idx].valor++;
    pthread_mutex_unlock(&a->contadores[idx].mutex);
}

Con granularidad gruesa, todos los incrementos se serializan: un solo hilo a la vez puede incrementar cualquier contador. Con granularidad fina, los hilos pueden incrementar contadores distintos simultáneamente.

La diferencia de rendimiento es significativa: con 4 hilos y 1000 contadores, la granularidad fina puede ser 4 veces más rápida que la gruesa (si los hilos acceden a contadores distintos).

7. El trade-off

La elección de granularidad es un trade-off entre:

La regla práctica es: empezar con granularidad gruesa y refinar solo donde la contención sea un problema. Premature optimization es la raíz de todos los males.

8. Medir el costo

Para medir el costo de la contención, se puede usar un benchmark que mida el tiempo de ejecución con distintos números de hilos y distintas granularidades:

$ gcc -std=c17 -Wall -Wextra -O2 -pthread -o contadores contadores.c
$ for n in 1 2 4 8; do echo -n "$n hilos: "; ./contadores $n; done
1 hilos: 0.05 s
2 hilos: 0.08 s (grueso) / 0.03 s (fino)
4 hilos: 0.15 s (grueso) / 0.02 s (fino)
8 hilos: 0.30 s (grueso) / 0.015 s (fino)

Con granularidad gruesa, el tiempo aumenta con el número de hilos (contención). Con granularidad fina, el tiempo disminuye (paralelismo).

9. Simulador interactivo

Este simulador compara la granularidad gruesa con la fina para un array de contadores:

10. Resumen

• La granularidad de un bloqueo es cuánto código protege un solo mutex.
• Granularidad gruesa: un lock para todo. Simple pero serializa.
• Granularidad fina: un lock por elemento. Paralelo pero complejo.
• La contención es el grado en que los hilos compiten por el mismo lock.
• La ley de Amdahl limita la aceleración: la sincronización es serialización.
• La práctica recomendada es empezar grueso y refinar donde la contención sea un problema.
• La solución a la alta contención es reducir la contención, no un lock mejor.

11. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Implementa el programa de contadores con granularidad gruesa y fina.
2. Mide el rendimiento con 1, 2, 4 y 8 hilos para ambas granularidades.
3. Calcula la contención para cada caso.
4. Explica por qué la granularidad fina puede ser más lenta con pocos hilos.
5. Diseña un esquema de granularidad intermedia (grupos de contadores).
6. Investiga cómo se implementa la granularidad fina en bases de datos (row-level locking).