critical, locks y el problema de los filósofos

💡 En simple

• critical es un solo baño con llave para todo el edificio: aunque quieras otro baño, haces la misma fila.
• critical con nombre son baños distintos, cada uno con su llave.
• Un lock es una llave que tú creas, guardas en una variable y puedes tener muchas (por ejemplo, una por casillero). Tú decides cuándo la tomas y cuándo la sueltas.

El riesgo de tener muchas llaves: que cada persona tenga una y espere la del otro para siempre. Eso es un deadlock (interbloqueo), y es lo que pasa con los filósofos.

Repaso: critical

teoria/ejemplo02_suma_prod_critical.cpp

#pragma omp parallel num_threads(4) default(shared)
{
    int psum = 0, pprod = 1;            // privadas: declaradas dentro
    #pragma omp for schedule(static)
    for (int i = 0; i < ARR_SIZE; i++) {
        psum += a[i];
        pprod *= a[i];
    }
    #pragma omp critical
    sum += psum;                        // una vez por hilo
    #pragma omp critical
    prod *= pprod;
}

Salida real (a[i] = 1, 2²⁰ elementos): sum: 1048576, prod: 1, en ≈ 0.0005 s.

Las dos regiones critical sin nombre usan el mismo candado: mientras un hilo suma en sum, nadie puede multiplicar en prod, aunque son variables distintas. Con nombres, son candados independientes:

U4.4 — secciones críticas con nombre

#pragma omp critical (section1)
{ for (int j = 0; j < BIG_NUMBER; j++) sum += psum; }

#pragma omp critical (section2)
{ for (int j = 0; j < BIG_NUMBER; j++) prod *= pprod; }   // puede correr a la vez que section1

Locks en OpenMP

Un lock es un objeto omp_lock_t que solo un hilo puede tener a la vez. Tiene 4 operaciones:

Función	Qué hace
omp_init_lock(&l)	Crea el lock (libre). Antes de usarlo.
omp_set_lock(&l)	Espera hasta que el lock esté libre y lo toma.
omp_unset_lock(&l)	Lo libera.
omp_destroy_lock(&l)	Lo elimina (lo contrario de init).

Ventaja frente a critical: el lock es una variable, así que puedes tener un arreglo de locks y elegir cuál tomar en tiempo de ejecución (lock[key]). Un critical con nombre se fija al escribir el código.

critical vs atomic vs lock, medido

Los tres programas de teoria/ hacen lo mismo: 8 hilos, cada uno suma 1 a x 100 000 veces. Resultado esperado: 800 000.

teoria/ejemplo03_lock.cpp

omp_lock_t writelock;
omp_init_lock(&writelock);
#pragma omp parallel shared(x)
{
    for (int i = 0; i < 100000; i++) {
        omp_set_lock(&writelock);
        x = x + 1;
        omp_unset_lock(&writelock);
    }
}
omp_destroy_lock(&writelock);

Ejecutado 3 veces cada uno (g++ -O2 -fopenmp, 8 hilos):

Versión	x	Tiempo (3 corridas)
#pragma omp atomic	800 000 ✓	0.019 · 0.020 · 0.013 s
#pragma omp critical	800 000 ✓	0.066 · 0.056 · 0.079 s
omp_set_lock / omp_unset_lock	800 000 ✓	0.057 · 0.120 · 0.119 s

Los tres son correctos. atomic es el más rápido (≈ 4× menos que critical) porque usa una instrucción atómica del procesador. critical y lock hacen lo mismo por dentro (un candado), y el lock explícito además paga la llamada a función.

Regla práctica

Para una variable y una operación simple: atomic. Para un bloque: critical. Para muchas posiciones independientes (cada una con su candado): arreglo de locks. Y si puedes acumular en privado y combinar al final: reduction, que le gana a todos.

Histograma: el caso donde los locks brillan

U4.4 — histograma con carrera

#pragma omp parallel for private(key)
for (int i = 0; i < INP_SIZE; i++) {
    key = inp[i];
    hist[key]++;          // dos hilos con el mismo key ⇒ se pierde un incremento
}

La lámina propone dos arreglos:

1. critical alrededor de hist[key]++. Funciona, pero no es eficiente: hay 2²⁰ bins y un solo candado. Dos hilos que van a bins distintos igual hacen fila.
2. Un lock por bin (omp_lock_t lock[HIST_SIZE]): solo chocan los hilos que van al mismo bin.

¿Se podría usar critical con nombre? No para esto: el nombre se escribe en el código, no puede depender de key. Tendrías que escribir 2²⁰ regiones distintas.

Histograma en paralelo: ¿cuánto bloquear?

Cada hilo procesa 6 datos y suma 1 en hist[key]. Compara cuántos pasos tarda cada versión y si el total da 24.

sin proteccióncriticallock por binlocal + fusión

hilos = 4bins = 6🎲 Otros datos

#pragma omp parallel for private(key)
for (i = 0; i < N; i++) {
    key = inp[i];
    hist[key]++;                 // carrera
}

⏮︎◀︎▶︎ Play▶︎⏭︎

0.5×1×2×4×

paso de tiempo 0/6

hilo 0 —hilo 1 —hilo 2 —hilo 3 —

pasos de tiempo6ideal: 6

suma del histograma0/24

actualizaciones perdidas0

Error en la lámina 21

En el código de la lámina, los locks se indexan con i (la posición del dato) en vez de key (el bin):

omp_set_lock(&(lock[i]));     // ✗ i va hasta INP_SIZE = 2^26, pero hay HIST_SIZE = 2^20 locks
hist[key]++;
omp_unset_lock(&(lock[i]));

Tiene dos problemas: se sale del arreglo de locks (i llega a 2²⁶) y no protege nada, porque dos hilos con el mismo key toman locks distintos. Lo correcto es lock[key]. (Observación propia.)

Los filósofos comensales

N filósofos en una mesa redonda con N tenedores, uno entre cada par. Para comer, cada uno necesita los dos tenedores que tiene al lado. Algoritmo de la lámina:

1. piensa hasta que el tenedor izquierdo esté libre, y lo toma;
2. piensa hasta que el derecho esté libre, y lo toma;
3. come;
4. suelta el izquierdo y el derecho; repite.

teoria/ejemplo04_filosofos.cpp

const int N = 5;
omp_lock_t forks[N];
...
#pragma omp parallel num_threads(N) private(id, left, right)
{
    id = omp_get_thread_num();
    left = id;
    right = (id + 1) % N;
    for (int i = 0; i < 30; ++i) {
        think(id);
        omp_set_lock(&forks[left]);      // primero el izquierdo
        omp_set_lock(&forks[right]);     // luego el derecho
        eat(id);
        omp_unset_lock(&forks[left]);
        omp_unset_lock(&forks[right]);
    }
}

La lámina pregunta: “Hay un problema de concurrencia en el código, ¿cómo lo solucionaría?”

Los filósofos y los locks

Cada tenedor es un omp_lock_t y cada filósofo, un hilo. Con el turno rotativo todos toman su tenedor izquierdo a la vez: es el peor caso posible.

izquierdo primero (clase)menor número primero

turno rotativoal azar

filósofos = 5

omp_set_lock(&forks[left]);    // primero el izquierdo
omp_set_lock(&forks[right]);   // luego el derecho

⏮︎◀︎▶︎ Play▶︎⏭︎

0.5×1×2×4×

paso 0/10

Todos piensan.

F0 comió0/2

F1 comió0/2

F2 comió0/2

F3 comió0/2

F4 comió0/2

El problema: deadlock

Si los 5 toman su tenedor izquierdo a la vez, cada uno espera el derecho, que tiene su vecino. Nadie suelta nada: el programa se cuelga.

Lo ejecutamos 200 veces (con un límite de 2 s por corrida):

Versión	Corridas colgadas
código de clase (con cout en think y eat)	4 / 200
mismo código sin los cout	144 / 200
con la solución de abajo	0 / 200

Los cout hacen que los hilos se desfasen, y eso esconde el error casi siempre. Es lo típico de los errores de concurrencia: el programa “funciona” al probarlo y falla en otro momento.

Cómo leerlo: a la izquierda, cada filósofo F_i tiene su tenedor izquierdo (línea gruesa) y espera el derecho (flecha roja), que tiene el vecino: las flechas forman un círculo y nadie avanza. A la derecha, con el orden global F4 pide primero el tenedor 0, que tiene F0; espera sin tener ninguno, el tenedor 4 queda libre y F3 (verde) toma los dos y come. El círculo ya no se puede cerrar.

La solución: orden global de los locks

Para que haya deadlock tiene que existir una espera circular (F0 espera a F1, que espera a F2… que espera a F0). Se rompe si todos toman los tenedores en el mismo orden global: primero el de menor número.

int a = std::min(left, right), b = std::max(left, right);
omp_set_lock(&forks[a]);
omp_set_lock(&forks[b]);
eat(id);
omp_unset_lock(&forks[a]);
omp_unset_lock(&forks[b]);

Para F0…F3 no cambia nada (izquierdo < derecho). Solo F4 cambia: pide el tenedor 0 antes que el 4. Si F0 ya tiene el 0, F4 espera sin tener ninguno, así que F3 puede tomar el 4 y comer: el círculo no se cierra.

Otras soluciones válidas: que un filósofo tome primero el derecho, o dejar sentarse a lo más N − 1 a la vez.

Ejercicio

En el histograma con un lock por bin, ¿qué pasa con el rendimiento si todos los datos caen en el mismo bin?

Ver solución

Todos los hilos piden el mismo lock en cada iteración, así que hacen fila igual que con critical: el bucle queda secuencial, y además paga el costo de omp_set_lock/omp_unset_lock. Los locks por bin solo ayudan cuando los datos se reparten entre muchos bins. Si hay pocos bins o los datos están muy concentrados, conviene un histograma local por hilo y fusionar al final (ver el simulacro de la PC4).

Errores típicos

• Olvidar omp_init_lock antes de usar el lock (u omp_destroy_lock al final).
• Liberar un lock desde un hilo que no lo tomó: comportamiento no definido.
• Tomar dos locks en distinto orden en hilos distintos: es exactamente el deadlock de los filósofos.
• Tomar dos veces el mismo omp_lock_t en el mismo hilo (por ejemplo, en una función recursiva): se bloquea a sí mismo. Para eso existe omp_nest_lock_t.

Práctica extra

Un deadlock necesita cuatro condiciones a la vez (Coffman): exclusión mutua, retener y esperar, no expropiación y espera circular. ¿Cuál rompe cada solución: (a) orden global de los locks, (b) sentar a lo más N − 1 filósofos?

Ver solución

Las dos rompen la espera circular.

• (a) Si todos piden en orden creciente, una cadena de esperas siempre va hacia números mayores y no puede volver al inicio.
• (b) Con N − 1 filósofos y N tenedores, por el principio del palomar al menos uno consigue los dos tenedores, come y libera: el círculo nunca se completa.

Autoevaluación

0/6 correctas · 0 respondidas Reiniciar

1. ¿Qué hace omp_set_lock(&l) si otro hilo ya tiene l?

a) falla y sigueb) espera hasta que lo liberen y luego lo tomac) lo liberad) lanza una excepción

2. Dos #pragma omp critical sin nombre en partes distintas del código…

a) usan candados independientesb) comparten el mismo candadoc) son inválidosd) se convierten en atomic

3. ¿Por qué un arreglo de locks es mejor que critical para el histograma?

a) porque es más cortob) porque solo esperan los hilos que van al mismo binc) porque no necesita initd) porque evita el deadlock

4. En el código de los filósofos de clase, el deadlock ocurre cuando…

a) un filósofo come dos vecesb) todos toman el tenedor izquierdo a la vez y esperan el derechoc) N es pard) se usa omp_unset_lock

5. Tomar siempre primero el tenedor de menor número evita el deadlock porque…

a) hace los locks más rápidosb) rompe la espera circularc) reduce el número de hilosd) usa atomic

6. Con 8 hilos y 10⁵ incrementos cada uno, la versión más rápida medida fue…

a) lockb) criticalc) atomicd) las tres igual

Fuente ·U4.4 Paralelismo compartido-OMP.pdf (láminas 12–21) · semana_10/teoria/ejemplo02_suma_prod_critical.cpp · semana_10/teoria/ejemplo03_atomic.cpp · semana_10/teoria/ejemplo03_critical.cpp · semana_10/teoria/ejemplo03_lock.cpp · semana_10/teoria/ejemplo04_filosofos.cpp