3.10. TÉCNICAS DE PROGRAMACIÓN.

  1. Implementación de semáforos.
  2. Implementación de bloqueos de lectores/escritores.
  3. Implementación de barreras.
  4. Implementación de monitores.

Aunque los paquetes de hilos sólo suelen implementar mútex y variables de condición como estructuras básicas para sincronización de hilos, se pueden implementar otras estructuras más complicadas en nuestros programas.

En este apartado vamos a mostrar como implementar distintas técnicas de programación para algunas situaciones habituales en la programación con hilos. Se emplean las primitivas de gestión de mútex y variables de condición que define el estándar POSIX 1003.1c, y que se pueden consultar en un capítulo posterior, como base para definir otras primitivas más potentes.

Implementación de semáforos.

En este caso vamos a mostrar como implementar semáforos contadores empleando un mútex y una variable de condición. Vamos a implementar la estructura de un semáforo, con las operaciones P (WAIT) y V (SIGNAL) definidas por Dijkstra, junto con las operaciones de inicialización y destrucción del semáforo. El semáforo tendrá siempre un valor >=0, de forma que si es 0, cualquier operación V sobre el semáforo suspenderá el hilo que realiza la operación, hasta que el semáforo adquiera un valor superior.

Definimos la estructura de datos de un semáforo sem_t compuesta por :

/* Estructura de datos del semáforo */
typedef struct {
    pthread_mutex_t lock;  /* Acceso exclusivo a la estructura */
    pthread_cond_t  no_cero;        /* Condición de semáforo no cero */
    unsigned int    contador; /* Valor del semáforo */
    unsigned int    en_espera;/* No. de hilos en espera */
} sem_t;

/* Inicializa la estructura del semáforo con el valor indicado */
int sem_init(sem_t *s, unsigned int valor) {
    /* Inicializa el mútex y la variable de condición asociadas */
    pthread_mutex_init(&s->lock, NULL);
    pthread_cond_init (&s->no_cero, NULL);
    s->contador = valor;
    s->en_espera = 0;
    return (0);
}

/* Destruye un semáforo que ya no es necesario */
int sem_destroy(sem_t *s) {
    pthread_mutex_destroy(&s->lock);        /* Destruye el mútex */
    pthread_cond_destroy(&s->no_cero);     /* Destruye la var.cond.*/
    return (0);
}

/* Operación P o WAIT de Dijkstra sobre el semáforo */
int sem_wait(sem_t *s) {
    pthread_mutex_lock(&s->lock);  /* Acceso exclusivo a datos sem.*/
    while (s->contador == 0) {    /* Esperar hasta que semáforo>0 */
        s->en_espera++;                        /* contar al hilo en espera */
        pthread_cond_wait(&s->no_cero, &s->lock); /* Espera condic. */
        s->en_espera --;               /* Descontar al hilo en espera */
    }
    s->contador--;         /* Decrementa el valor del semáforo */
    pthread_mutex_unlock(&s->lock);        /* Libera el mútex */
    return (0);
}

/* Operación V o SIGNAL de Dijkstra sobre el semáforo */
int sem_signal(sem_t *s) {
    pthread_mutex_lock(&s->lock);  /* Acceso exclusivo a datos sem.*/
    if (s->en_espera)                      /* Si existen hilos en espera */
        pthread_cond_signal(&s->no_cero);      /* Se despierta un hilo */
    s->contador++;                 /* Se incrementa el semáforo */
    pthread_mutex_unlock(&s->lock);        /* Libera el mútex */
    return (0);
}


Implementación de bloqueos de lectores/escritores.

El problema de los lectores/escritores es un problema clásico de la programación concurrente. Se debe permitir el acceso simultáneo de múltiples lectores a una estructura de datos crítica, pero sólo se debe permitir el acceso a un escritor al mismo tiempo, y de forma exclusiva.

En algunos paquetes de hilos, como UI Threads se incorporan primitivas para la gestión de este problema. A continuación vamos a definir primitivas similares. Vamos a definir una estructura de datos que podemos asociar con un bloque de datos al que deseamos acceder para lectura y en ocasiones para escritura. Definimos la estructura de datos bloqueo de lectores/escritores rwlock_t compuesta por :

/* Estructura de datos del bloqueo de lectores/escritores */
typedef struct {
        pthread_mutex_t lock;      /* Acceso estructura de datos      */
        pthread_cond_t  lectura;   /* Condición lectura permitida     */
        pthread_cond_t  escritura; /* Condición escritura permitida   */
        int             estado;    /* -1:escritor,0:libre,>0:lectores */
        int             en_espera; /* No. de escritores en espera     */
} rwlock_t;

/* Inicializa una estructura de bloqueo de lectores/escritores */
int rwlock_init(rwlock_t *rw) {
        / * Inicializa el mútex y variables de condición asociados */
        pthread_mutex_init(&rw->lock, NULL);
        pthread_cond_init(&rw->lectura, NULL);
        pthread_cond_init(&rw->escritura, NULL);
        rw->estado    = 0;
        rw->en_espera = 0;
        return (0);
}


/* Destruye la estructura de bloqueo de lectores/escritores */
int rwlock_destroy(rwlock_t *rw) {
        pthread_mutex_destroy(&rw->lock );       /* Destruye el mútex y */
        pthread_cond_destroy(&rw->lectura ); /* var. de condición */
        pthread_cond_destroy(&rw->escritura);/* asociados */
        return (0);
}


/* Adquiere un bloqueo de lector */
int rw_rdlock(rwlock_t *rw) {
        pthread_mutex_lock(&rw->lock);  /* Acceso exclusivo */
        /* Mientras se esté escribiendo o haya escritores en espera,
           se suspende hasta que haya permiso de lectura */
        while ( (rw->estado < 0) && rw->en_espera )
                pthread_cond_wait(&rw->lectura, &rw->lock);
        rw->estado++;
        pthread_mutex_unlock(&rw->lock);        /* Libera el mútex */
        return (0);
}


/* Adquiere un bloqueo de escritor */
int rw_wrlock(rwlock_t *rw) {
        pthread_mutex_lock(&rw->lock);  /* Acceso exclusivo */
        rw->en_espera++;       /* Incrementa el no. de lectores en espera */
        /* Mientras se está leyendo o escribiendo, 
           se suspende a la espera del permiso de escritura */
        while (rw->estado)
                pthread_cond_wait(&rw->escritura, &rw->lock);
        rw->estado = -1; /* Establece el estado de escritura */
        rw->en_espera--; /* Decrementa el no. de escritores en espera */
        pthread_mutex_unlock(&rw->lock);        /* Libera el mútex */
        return (0);
}


/* Libera un bloqueo de lectores/escritores */
int rw_unlock(rwlock_t *rw) {
        pthread_mutex_lock(&rw->lock);  /* Acceso exclusivo */
        if (rw->estado == -1 ) { /* Si era un bloqueo de escritura */
           rw->estado = 0;  /* libera el bloqueo */
           if (rw->en_espera) /* Si existen escritores en espera */
                pthread_cond_signal(&rw->escritura); /* despierta uno*/
           else /* Sino despierta a todos los lectores */
                pthread_cond_broadcast(&rw->lectura);/* */
        } else {      /* Si era un bloqueo de lectura */
           rw->estado--;   /* libera el bloqueo de lectura */
           /* Si no hay más lectores, despierta un escritor */
           if (rw->estado == 0)
                  pthread_cond_signal(&rw->escritura);
        }
        pthread_mutex_unlock(&rw->lock);        /* Libera el mútex */
        return (0);
}


Antes de emplear este tipo de bloqueo debemos garantizar que hemos inicializado la estructura. Además al finalizar su utilización se debe destruir. Cada vez que intentemos una operación sobre los datos bloqueamos primero la variable asociada de lectores/escritores empleando el bloqueo apropiado (lectura o escritura), realizamos la operación, y después liberamos la variable asociada. La forma normal de emplear las primitivas es recubrir cada tipo de acceso (lectura o escritura) con el bloqueo correspondiente y el desbloqueo final :

LECTOR :                                        ESCRITOR :
rw_rdlock(&rw);                         rw_wrlock(&rw);
 Acceso para lectura                     Acceso para escritura
rw_unlock(&rw)                          rw_unlock(&rw);



Implementación de barreras.

Una barrera es un punto de sincronización entre varios hilos. Esta técnica permite que varios hilos se sincronicen en un determinado punto de su ejecución, de forma que ninguno de ellos puede avanzar en su ejecución hasta que todos hayan alcanzado el punto establecido por la barrera. Con esta técnica se pueden implementar algoritmos SIMD en sistemas MIMD de una forma sencilla.

Figura 3-13 Funcionamiento de una barrera.

En la implementación que se realiza, empleamos el tipo semáforo sem_t definido con anterioridad. Definimos la estructura de datos de una barrera barrier_t compuesta por :

Cada nodo de la lista de hilos en espera del tipo waitlist_t consta de :

/* Estructura de la lista de hilos en espera */
typedef struct _list {
        sem_t           sem;      /* Semáforo de espera asociado */
        struct _list    *next;     /* Siguiente hilo de la lista */
} waitlist_t;

/* Estructura que define el tipo Barrera */
typedef struct _barrier {
        pthread_mutex_t lock;           /* Acceso exclusivo             */
        unsigned int    maxcont;   /* No. de hilos a sincronizar   */
        unsigned int    en_ejecución; /* No. de hilos en ejecución    */
        waitlist_t      *head;       /* Cabeza de lista de hilos en espera */
} barrier_t;

/* Inicializa una variable barrera */
int barrier_init(barrier_t *b, int num_hilos) {
        if ( contador < 1 )     /* Si el no. de hilos a sincronizar */
                return (-1);    /* no es válido devuelve error */
        b->maxcont      = num_hilos;
        b->en_ejecucion = num_hilos;
        b->head         = NULL;
        pthread_mutex_init(&b->lock, NULL);
        return( 0 );
}

/* Se bloquea en una barrera hasta que lleguen todos los hilos, para después continuar la ejecución */
int barrier_wait(barrier_t *b ) {
        pthread_mutex_lock(&b->lock);           /* Acceso exclusivo */
        /* Si es el último hilo en alcanzar la barrera */
        if (b->en_ejecucion == 1) {
                if (b->maxcont != 1) { /* Si no es el único hilo */
                   waitlist_t *h;
                   /* Despierta todos los hilos a la espera
                      de la sincronización con la barrera */
                   for (h = b->head; h != NULL; h = h->next)
                        sem_signal(&h->sem );
                        /* Limpia la barrera, para otra sincronización */
                   b->head         = NULL;
                   b->en_ejecucion = b->maxcont;
                }
                pthread_mutex_unlock(&b->lock); /* Libera el mútex */
        } else { /* Si no es el último hilo en alcanzar la barrera */
                waitlist_t wl;
                sem_init(&wl.sem, 0);   /* Inicializa semáforo temporal */
                b->en_ejecución--;      /* Un hilo menos en ejecución   */
                wl.next = b->head;      /* Inserta en la cabeza de la   */
                b->head = &wl;          /* lista de hilos en espera     */
                pthread_mutex_unlock(&b->lock);/* Libera el mutex */
                sem_wait(&wl.sem );     /* Espera la sincronización     */
                sem_destroy(&wl.sem);   /* Destruye el semáforo temporal*/
        }
        return (0);
}

/* Destruye una variable barrera */
int barrier_destroy(barrier_t *b) {
        b->maxcont      = 0;
        b->en_ejecucion = 0;
        return( pthread_mutex_destroy( &b->lock) );
}


Antes de emplear este tipo de técnica debemos garantizar que hemos inicializado la variable de la barrera. Además al finalizar su utilización se debe destruir. Cada vez que necesitemos un punto de sincronización conjunta, empleamos la primitiva de espera por la barrera en el lugar adecuado en cada uno de los hilos que deseamos sincronizar. La forma normal en la que aparece la primitiva en relación con la ejecución de los distintos hilos a sincronizar es :

t  Hilo1                         Hilo2                           Hilo3
1  .......                       .......                 .......
2  .......                       barrier_wait(&b);       .......
3  barrier_wait(&b);             (suspendido)            .......
4  (suspendido)                                          barrier_wait(&b);
5  Continua                      Continua                Despierta al resto
6  .......                       .......                 .......



Implementación de monitores.

Los monitores son una técnica muy útil en programación concurrente. Consiste en agrupar un conjunto de procedimientos o funciones junto con una serie de datos críticos compartidos que son manipulados por dichos procedimientos, de forma que en un momento dado sólo puede estar ejecutándose un único procedimiento del monitor. Esto garantiza el acceso exclusivo.

A la hora de crear un monitor debemos tener en cuenta los siguientes aspectos :

/* Estructura de los datos compartidos del monitor */
typedef struct _monitor_t {
        pthread_mutex_t         lock;    /* Acceso exclusivo al monitor */
        datos_t                 datos; /* El resto de datos del usuario */
} monitor_t

void monitor_init(monitor_t *m, ... ) {
        pthread_mutex_init(&m->lock, NULL);
        ... Inicialización de los datos de usuario : m->datos ...
}

void monitor_destroy(monitor_t *m, ... ) {
        pthread_mutex_destroy(&m->lock);
        ... Destrucción de los datos de usuario : m->datos ...
}

void monitor_func(monitor_t *m) {
        pthread_mutex_lock(&m->lock);
        ... Código de la función concreta del monitor ...
        pthread_mutex_unlock(&m->lock);
}