Barreras

1. Qué es una barrera

Una barrera (barrier) es un punto de sincronización donde todos los hilos deben llegar antes de que cualquiera pueda continuar. Es como una puerta que no se abre hasta que todos los invitados han llegado. Cuando el último hilo llega, la barrera se abre y todos los hilos continúan.

Las barreras son útiles cuando un programa se divide en fases: todos los hilos deben completar la fase 1 antes de que cualquiera comience la fase 2. Por ejemplo, en un algoritmo paralelo, todos los hilos calculan sus resultados parciales (fase 1) antes de combinarlos (fase 2).

La barrera garantiza que no hay hilos adelantados: ningún hilo puede empezar la fase 2 hasta que todos hayan terminado la fase 1.

2. Cómo funciona

Una barrera funciona así:

1. Un hilo llega a la barrera. Se bloquea y espera a los demás. llegar
2. Los demás hilos llegan uno a uno. Cada uno se bloquea y espera. esperar
3. El último hilo llega. La barrera se abre. abrir
4. Todos los hilos se desbloquean y continúan con la siguiente fase. continuar

La barrera tiene un contador interno que cuenta cuántos hilos han llegado. Cuando el contador alcanza el número total de hilos, la barrera se abre.

La barrera es reutilizable: después de que se abre, se reinicia automáticamente para la siguiente fase. No hay que recrearla.

3. pthread_barrier

POSIX proporciona barreras a través de pthread_barrier_t y las funciones pthread_barrier_init, pthread_barrier_wait y pthread_barrier_destroy.

La barrera se inicializa con el número de hilos que deben llegar antes de que se abra:

#include <pthread.h>

pthread_barrier_t barrier;
pthread_barrier_init(&barrier, NULL, 4);  /* 4 hilos deben llegar */

/* En cada hilo: */
void *trabajo(void *arg) {
    hacer_fase_1();
    pthread_barrier_wait(&barrier);  /* esperar a los demás */
    hacer_fase_2();
    return NULL;
}

pthread_barrier_destroy(&barrier);

pthread_barrier_wait retorna PTHREAD_BARRIER_SERIAL_THREAD para el último hilo en llegar (el que abre la barrera) y 0 para los demás. Esto permite que el último hilo haga trabajo adicional (por ejemplo, combinar resultados).

4. La API de barreras

La barrera se puede reutilizar: después de que se abre, se reinicia automáticamente para la siguiente fase. No hay que destruirla y recrearla.

5. Un ejemplo desarrollado

Un ejemplo de sincronización por fases con barrera:

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

#define NUM_HILOS 4

pthread_barrier_t barrier;

void *trabajo(void *arg) {
    int id = *(int *)arg;

    /* Fase 1: cada hilo hace su trabajo. */
    printf("Hilo %d: fase 1\n", id);
    sleep(1 + id % 2);  /* simular trabajo de duración variable */

    /* Esperar a que todos terminen la fase 1. */
    int ret = pthread_barrier_wait(&barrier);
    if (ret == PTHREAD_BARRIER_SERIAL_THREAD) {
        printf("Hilo %d: soy el último, abro la barrera.\n", id);
    }

    /* Fase 2: todos continúan juntos. */
    printf("Hilo %d: fase 2\n", id);
    return NULL;
}

int main(void) {
    pthread_t hilos[NUM_HILOS];
    int ids[NUM_HILOS];

    pthread_barrier_init(&barrier, NULL, NUM_HILOS);

    for (int i = 0; i < NUM_HILOS; i++) {
        ids[i] = i;
        pthread_create(&hilos[i], NULL, trabajo, &ids[i]);
    }
    for (int i = 0; i < NUM_HILOS; i++) {
        pthread_join(hilos[i], NULL);
    }

    pthread_barrier_destroy(&barrier);
    return 0;
}

La salida garantiza que todos los «fase 1» se imprimen antes de cualquier «fase 2». El último hilo en llegar imprime un mensaje adicional.

6. Cómo se implementa con semáforos

Una barrera se puede implementar con semáforos. La idea es:

1. Contador de llegadas: cada hilo incrementa un contador al llegar. contar
2. Espera: si no es el último, el hilo espera en un semáforo. esperar
3. Apertura: el último hilo despierta a todos los que esperan. abrir

typedef struct {
    int count;          /* número de hilos que deben llegar */
    int arrived;        /* número de hilos que han llegado */
    sem_t mutex;        /* protege arrived */
    sem_t barrier;      /* semáforo para bloquear */
} barrier_t;

void barrier_init(barrier_t *b, int count) {
    b->count = count;
    b->arrived = 0;
    sem_init(&b->mutex, 0, 1);
    sem_init(&b->barrier, 0, 0);
}

void barrier_wait(barrier_t *b) {
    sem_wait(&b->mutex);
    b->arrived++;
    if (b->arrived == b->count) {
        /* Último en llegar: abrir la barrera. */
        for (int i = 0; i < b->count - 1; i++) {
            sem_post(&b->barrier);
        }
        b->arrived = 0;  /* reiniciar para la próxima fase */
    }
    sem_post(&b->mutex);
    if (b->arrived != 0) {  /* no es el último */
        sem_wait(&b->barrier);
    }
}

void barrier_destroy(barrier_t *b) {
    sem_destroy(&b->mutex);
    sem_destroy(&b->barrier);
}

Esta implementación tiene un problema: si un hilo llega a la barrera de la siguiente fase antes de que todos hayan salido de la anterior, puede haber una carrera. La solución es usar dos semáforos o un contador de fase.

7. Sincronización por fases

La sincronización por fases es el uso principal de las barreras. Un programa se divide en fases, y todos los hilos deben completar una fase antes de que cualquiera comience la siguiente.

Ejemplos de sincronización por fases:

• Algoritmos paralelos: todos los hilos calculan resultados parciales (fase 1) antes de combinarlos (fase 2).
• Simulaciones: todos los hilos actualizan el estado (fase 1) antes de calcular el siguiente paso (fase 2).
• Procesamiento de datos: todos los hilos procesan su parte (fase 1) antes de escribir los resultados (fase 2).

8. Ejemplo de sincronización por fases

Un ejemplo de sincronización por fases: calcular la suma de un array en paralelo:

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

#define NUM_HILOS 4
#define N 1000000

int array[N];
int parciales[NUM_HILOS];
pthread_barrier_t barrier;

void *sumar(void *arg) {
    int id = *(int *)arg;
    int inicio = id * (N / NUM_HILOS);
    int fin = (id + 1) * (N / NUM_HILOS);

    /* Fase 1: calcular la suma parcial. */
    int suma = 0;
    for (int i = inicio; i < fin; i++) {
        suma += array[i];
    }
    parciales[id] = suma;

    /* Barrera: esperar a que todos terminen la fase 1. */
    pthread_barrier_wait(&barrier);

    /* Fase 2: el hilo 0 combina los resultados. */
    if (id == 0) {
        int total = 0;
        for (int i = 0; i < NUM_HILOS; i++) {
            total += parciales[i];
        }
        printf("Suma total: %d\n", total);
    }
    return NULL;
}

int main(void) {
    /* Inicializar el array. */
    for (int i = 0; i < N; i++) array[i] = 1;

    pthread_barrier_init(&barrier, NULL, NUM_HILOS);

    pthread_t hilos[NUM_HILOS];
    int ids[NUM_HILOS];
    for (int i = 0; i < NUM_HILOS; i++) {
        ids[i] = i;
        pthread_create(&hilos[i], NULL, sumar, &ids[i]);
    }
    for (int i = 0; i < NUM_HILOS; i++) {
        pthread_join(hilos[i], NULL);
    }

    pthread_barrier_destroy(&barrier);
    return 0;
}

La barrera garantiza que todos los hilos han calculado sus sumas parciales antes de que el hilo 0 las combine. Sin la barrera, el hilo 0 podría leer parciales[i] antes de que el hilo i lo haya calculado.

9. Propiedades

10. Simulador interactivo

Este simulador muestra cómo una barrera sincroniza varios hilos en fases:

11. Resumen

• Una barrera es un punto de sincronización donde todos los hilos deben llegar antes de continuar.
• Se implementa con pthread_barrier_t en POSIX.
• La barrera se inicializa con el número de hilos que deben llegar.
• pthread_barrier_wait bloquea hasta que todos lleguen.
• El último en llegar recibe PTHREAD_BARRIER_SERIAL_THREAD.
• La barrera es reutilizable para múltiples fases.
• Se puede implementar con semáforos.
• Es útil para sincronización por fases en algoritmos paralelos.

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Implementa el programa de suma paralela con barrera.
2. Implementa la barrera con semáforos y verifica que funciona.
3. Usa PTHREAD_BARRIER_SERIAL_THREAD para que el último hilo combine los resultados.
4. Implementa una sincronización por 3 fases con la misma barrera.
5. Investiga cómo se implementa la barrera en el núcleo de Linux.
6. Explica por qué la implementación con semáforos tiene un problema de carrera.