Lab3: Programando con Hilos

Objetivos

Escribir multiprogramas que intercambien información y se sincronicen utilizando POSIX Threads (pthreads), contemplando  los problemas típicos de la concurrencia como condiciones de carrera, abrazos mortales, inhanición, etc.

Introducción

En el Laboratorio anterior utilizamos las facilidades de concurrencia de gruesa granularidad de UNIX. Creabamos y esperábamos la finalización de procesos que se ejecutaban en espacios de memoria disjuntos, y donde sólo se compartían los descriptores de archivos.

Esta concurrencia hacía uso del concepto de proceso como unidad básica de ejecución, el cual brindaba la posibilidad de ejecutar una componente de un multiprograma en un espacio de memoria disjunto y a la vez protegido. Al no compartir memoria, los procesos efectuan su comunicación utilizando alguna de las estructuras que sí se comparten, por ejemplo el sistema de archivos, y vimos como a través de pipes podíamos comunicar y sincronizar procesos.

Un hilo o proceso liviano (ligthweight process - LWP) es otro de los posibles modelos de ejecución de un multiprograma que proveen los sistemas operativos en general y *NIX en particular, y brinda otra posibilidad para realizar multiprogramación.
Esta segunda opción existe para que el programador tenga la posibilidad de elegir una solución de compromiso entre 2 cualidades deseables protección y eficiencia .
Normalmente estos los hilos tienen vida dentro de los procesos, y podemos pensar en los procesos simples que utilizamos en el Lab2 como que sólo contienen un hilo de ejecución interno.

El problema reside en que un proceso maneja un estado relativamente grande, que involucra los registros del microprocesador, la pila de ejecución, el mapa de memoria, los descriptores de archivos y tabla de manejadores de señal, con lo cual el nacimiento, la vida (cambios de contexto) y la muerte de los procesos, son operaciones que consumen lo suficiente en cuanto a recursos de tiempo y espacio (memoria) como para que no sea viable la creación de decenas de miles de éstos procesos.
Los hilos en cambio, lo único que no comparten son los registros del microprocesador y el espacio de la pila, con lo cual las opearciones de creación, cambio de contexto y muerte, resultan mucho más económicas.

La comunicación entre las componentes del multiprograma es otro factor que diferencia los procesos de los hilos. Mientras que en los hilos es posible transferir información entre componentes simplemente escribiendo en el espacio de memoria compartido, los procesos tienen que efectuar un secuencia de llamadas al núcleo, para poder completar la transferencia de información: espacio_de_usuario1, kernel, espacio_de_usuario_2, incurriendo no sólo en sobrecarga por copia, sino también por cambios de niveles de protección .

El sistema operativo Linux, incorporta procesos livianos en un modelo conocido uno-a-uno utilizando clone, la generalización del syscall fork. A cada hilo se le asocia un proceso, donde se comparte la memoria y los descriptores de archivos.
Lamentablemente esta implementación de procesos livianos, pierde algunas de las características esperables ( LinuxThreads Frequently Asked Questions , Programación utilizando C threads , FAQ de comp.programming.threads ).

Como crear hilos

Veamos a través un ejemplo, como crear 2 hilos que impriman N veces "Hola Mundo" y  M veces"Mundo Hola" respectivamente por la salida estandar.
Necesitamos incluir la cabecera de la biblioteca pthreads , que forma parte de la glibc de Linux, que nos brinda acceso a todas las llamadas pthreads_* . Nosotros sólo utilizaremos en este ejemplo pthread_create y pthread_join, donde esta última tiene una semántica parecida al wait de los procesos. Observar la declaración y uso de arreglos constantes.

 
 
#include <stdio.h>
#include <pthread.h>

#define N 8
#define M 16

const char *mensaje[2] = {"Hola Mundo", "Mundo Hola"};
const int cantidad[2] = {N, M};

void imprime_mensaje(void *ptr) {
        int i;
        int id;

        id = *(int *) ptr;
        for(i=0; i<cantidad[id]; i++)
                printf("%s\n",mensaje[id]);
        return;
}


int main(int argc, char *argv[])
{
        pthread_t hilo0, hilo1;
        int id0=0, id1=1;

        pthread_create(&hilo0, NULL, (void *) &imprime_mensaje, (void *) &id0);
        pthread_create(&hilo1, NULL, (void *) &imprime_mensaje, (void *) &id1);

        pthread_join(hilo0, NULL);
        pthread_join(hilo1, NULL);

        return 0;
}

Para compilar este ejemplo debemos incluir la biblioteca pthread, de la siguiente manera:

 
[juan@hal juan]$ gcc -Wall -lpthread -o holaMundo holaMundo.c


Notamos que la llamada a pthread_create esta pasando una función como argumento y que se necesitan varios typecasts para poder compatibilizar los tipos actuales con los requeridos por la función (ver man pthread_create ).
Puede parecer extraño que definamos las variables id0 , id1 con dos constantes, pero esto también es necesario cuando tenemos que pasarle la dirección del argumento y no el valor en sí mismo.

Las funciones pthread_join, evitan que al terminar el main, acabe con la vida de sus hilos. La terminación del hilo se hace un simple return, que resulta equivalente a pthread_exit(NULL) .

Lamentablemente en máquinas con procesadores rápidos, no podemos observar ni el interleaving entre los mensajes, ni el no determinismo, esto se debe a que toma tan poco tiempo imprimir los N o M mensajes definidos, que el planificador casi no actua y el orden es puramente secuencial .
¿De qué nos sirve entonces un entorno de multiprogramación donde las planificaciones de procesos cortos resultan seriales? Realmente de poco, pues toda la problemática de interferencia entre componentes, regiones críticas, abrazos mortales se reducen a la nada. Sin embargo podemos simular interleavings más ricos , indicando explícitamente al planificador que queremos entregar el control a otro proceso (recordemos que en Linux, el planificador no distingue entre proceso e hilo), mediante la función sched_yield .
Estos sched_yield nos permitirán estar más confiados en que nuestros multiprogramas funcionarán de manera correcta independientemente del hardware o situación de carga concreta en donde se esté ejecutando.

Ejercicios

Memoria compartida entre hilos y las primeras interferencias

El ejemplo anterior sólo mostraba como crear hilos y que ambos leyeran desde la memoria compartida, pero al tener sólo accesos de lectura a la memoria, no es posible diferenciar entre memoria compartida y memoria disjunta con copias idénticas, como ocurría en el caso del fork.
El siguiente ejemplo implementa uno de los ejercicios del primer parcial donde se tenía un multiprograma con 2 componentes donde cada una de estas, de manera cíclica incrementaba y decrementaba una variable compartida.

P0:
do true ->
x:=x+1;
x:=x-1
od 
P1:
do true ->
x:=x+1;
x:=x-1
od

Es posible demostrar de manera mas o menos convincente que 0<=x<=2 si la atomicidad es línea a línea.
El siguiente programa es una implementación en pthreads de este multiprograma escrito en el Lenguaje de los Comandos Guardados de Dijkstra (LCGD).

 
 
#include <stdio.h>
#include <assert.h>
#include <pthread.h>

//compilacion condicional
#define __DEBUG

void *IncrDecr(void *);

//la variable global y compartida
int x=0;

int main(int argc, char *argv[]) {
        pthread_t t0id,t1id;

        pthread_create(&t0id, NULL, IncrDecr, NULL);
        pthread_create(&t1id, NULL, IncrDecr, NULL);
#ifdef __DEBUG
        printf("Hilos Creados\n");
        printf("Inicio de sonda de testeo\n");
#endif
        //sonda que comprueba el Invariante
        while(1) {
                assert(0<=x && x<=2); // Inv: 0<=x<=2
                printf("%2d", x);
        }
        //aqui nunca llega
}


//componente del multiprograma
void *IncrDecr(void *arg)
{
#ifdef __DEBUG
        printf("Hilo IncrDecr iniciado\n");
#endif
        for (;;) {
                x = x+1;
                x = x-1;
        }
}


Remarcamos 2 aspectos de este programa: la compilación condicional a través del uso de las directivas del preprocesador #define , #undef, #ifdef y #endif, y las variables globales.
La compilación condicional, nos permite en este caso generar 2 versiones diferentes de nuestro código una con información de debug y la otra sin ella, cambiando #define __DEBUG por #undef __DEBUG. Luego veremos como es posible obtener un mecanismo similar mejorando la legibilidad del código.
El uso de variables globales es una condición necesaria para el uso de memoria compartida entre los hilos, a menos que pasemos a las funciones que ejecutan los hilos referencias a espacios de memoria pedidos en el montículo o heap.

Si compilamos y ejecutamos nuestro ejemplo que podemos llamar programTopology, veremos que aunque la sonda muestra pocos cambios en x, esta siempre se mantiene en el rango [0,2]. La falta de cambios se debe nuevamente a la poca cantidad de interleavings que se producen, donde el efecto se nota más en procesadores rápidos y poco utilizados por el SO.

Para generar más interleavings podemos inundar de sched_yield() nuestro programa. Sin embargo nunca se producen los interleavings que muestran que x:=x+1 no es atómico, pues en este caso el invariante del multiprograma 0<=x<=2 ya no vale. Notar que jamás le declaramos al compilador C que esta instrucción fuese atómica, asi que puede ser compilada a una sola o a un conjunto (interrumpible) de intrucciones.

A fin de simular el caso del incremento no atómico suele ser necesario dividir explicitamente los incrementos y decrementos en 3 instrucciones.

Ejercicios

Sincronizando con Mutexes

La biblioteca de hilos en Linux incorpora Locks o Mutexes, para proteger regiones críticas del código, y las llamadas básicas son las siguientes: pthread_mutex_init, pthread_mutex_lock , pthread_mutex_unlock y pthread_mutex_destroy .
Notamos que tenemos llamadas para destruir el objeto Mutex a fin de liberar los recursos que este pueda consumir.

En este caso nuestro ejemplo sincroniza los accesos a un buffer compartido por parte de dos componentes, donde una establece un valor i en todo el buffer y la otra un valor j distinto. La idea es que queremos que se mantenga el invariante que todo hilo externo siempre vea el buffer con un contenido uniforme de valores, ya sea i o j.
Claramente si no protegemos con regiones críticas, es posible que a la mitad de una actualizacion, que no es atómica, se produzca un cambio de contexto, ya sea para inspeccionar los valores o para establecerlos en otro valor.

Lo que sigue es el programa setBuffer que implementa esta idea y protege a las secciones críticas utilizando Locks.

 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <pthread.h>

#define CAPACIDAD 16

void *set_buffer_to(void *);
void yield();

//las variables globales y compartidas
int buffer[CAPACIDAD];
pthread_mutex_t mutex;


int main(int argc, char *argv[]) {
        pthread_t hilo0,hilo1;
        int val[2]={4,8};
        int i;

        for(i=0; i<CAPACIDAD; i++)
                buffer[i] = 0;

        pthread_mutex_init(&mutex, NULL);
        pthread_create(&hilo0, NULL, set_buffer_to, (void *)&val[0]);
        pthread_create(&hilo1, NULL, set_buffer_to, (void *)&val[1]);
          //sonda que comprueba que el Inv siempre se cumpla
        while(1) {
                yield();
                pthread_mutex_lock(&mutex);     //Inicio SC
                //Inv: { \forall i : buffer[i]=buffer[0] }
                for (i=0; i<CAPACIDAD; i++) {
                        assert(buffer[i]==buffer[0]);
                        yield();
                }
                pthread_mutex_unlock(&mutex);   //Fin SC
        }
        //aqui nunca llega
}


//pone todo el buffer en un valor
void *set_buffer_to(void *arg) {
        int val, i;

        val = *(int *)arg;

        while(1) {
                yield();
                pthread_mutex_lock(&mutex);     //Inicio SC
                for (i=0; i<CAPACIDAD; i++) {
                        buffer[i] = val;
                        yield();
                }
                pthread_mutex_unlock(&mutex);   //Fin SC
                yield();
        }
}


//se entrega al planificador de manera no deterministica
void yield(void) {
        if (rand()%2)
                sched_yield();
}

Notar el uso de la función yield(), la cual agrega un poco de no-determinismo al sistema, entregando o no el hilo actual de ejecución con probabilidad ½. Luego veremos sistemas un poco más sofisticados, todos tendientes a producir interleavings siempre distintos en cada ejecución del código.

Ejercicios

Sincronizando con Semáforos

Utilizaremos los semáforos que brinda pthreads incluyendo su cabecera semaphore.h, a fin de implementar el problema del productor-consumidor sobre un buffer circular fifo.
Asi como en los mutexes, los semáforos pueden ser inicializados y destruidos con sem_init y sem_destroy, y sus operaciones básicas P y V están implementadas en las funciones sem_wait y sem_post respectivamente.
El código está hecho de forma tal que todas las variables compartidas que mantienen datos y sincronización están dentro de una estructura de datos denominada buffer síncrono . Esta forma de empaquetar estructuras de datos y su sincronización, es muy común, y los ejemplos más usuales son los monitores y las clases sincronizadas de Java.

Notar que el buffer circular es una implementación de una secuencia finita xs de N elementos, en un arreglo a de N+1 elementos y dos naturales pr y pw. La relación entre la secuencia y la representación está dada por los siguientes invariantes:
Dado este buffer síncrono, creamos 2 hilos, donde uno es el productor y inserta números naturales crecientes, mientras que el otro es el consumidor y los obtiene del buffer.
Una correcta ejecución de los 2 hilos debería mostrar para cada i, exactamente 1 valor encolado y 1 valor decolado, además los
valores decolados deberían estar en orden creciente (los encolados también lo están, pero por construcción del programa).
Algunas pruebas más débiles que estas (o sea que la validez es implicada) pueden ser contar la cantidad total de elementos producidos y consumidos, y divididos por tipo.

[juan@hal juan]$ ./prodCons | wc -l
   2048
[juan@hal juan]$ ./prodCons | tee 1 | grep ">" | wc -l ; grep "<" 1 | wc -l
   1024
   1024

Pero la mejor forma es mirar directamente la salida redirigida a un archivo, o bien generar un programa que compruebe estas propiedades a partir del archivo de salida. Mostramos a continuación una salida que contiene errores de sincronización.

[juan@hal juan]$ ./prodCons | head
>     0
<     0
>     1
<     1
>     0
<     2
>     0
<     3
>     0
<     4

El listado del programa se puede ver a continuación:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <pthread.h>
#include <semaphore.h>

#define NOTSHARED 0
#define N 16
#define NUM_ITEMS 1024

void *productor(void *);
void *consumidor(void *);
void yield();

//la estructura compartida
struct buffer_sync_s {
        int buffer[N+1];
        int pr,pw;
        pthread_mutex_t mutex;
        sem_t vacios;
        sem_t llenos;
} buffer_sync;


int main(int argc, char *argv[]) {
        pthread_t hilo_p, hilo_c

        //init de la estructura
        buffer_sync.pr = buffer_sync.pw = 0;
        pthread_mutex_init(&buffer_sync.mutex, NULL);
        sem_init(&buffer_sync.vacios, NOTSHARED, N);
        sem_init(&buffer_sync.llenos, NOTSHARED, 0);
        //creo los hilos
        pthread_create(&hilo_p, NULL, productor, NULL);
        pthread_create(&hilo_c, NULL, consumidor, NULL);
        //espero que terminen
        pthread_join(hilo_p, NULL);
        pthread_join(hilo_c, NULL);
        //destruyo la estructura
        sem_destroy(&buffer_sync.llenos);
        sem_destroy(&buffer_sync.vacios);
        pthread_mutex_destroy(&buffer_sync.mutex);

        return 0;
}

//se entrega al planificador de manera no deterministica
void yield(void) {
        if (rand()%2)
                sched_yield();
}
 //productor
void *productor(void *arg) {
        int i;
       
        for(i=0; i<NUM_ITEMS; i++) {
                yield();
                sem_wait(&buffer_sync.vacios);
                yield();
                pthread_mutex_lock(&buffer_sync.mutex);
                yield();
               
                //el buffer circular, encolar(i)
                buffer_sync.buffer[buffer_sync.pw] = i;
                yield();
                buffer_sync.pw = (buffer_sync.pw+1) % (N+1);
                yield();
                printf("< %5d\n",i);
                yield();
               
                pthread_mutex_unlock(&buffer_sync.mutex);
                yield();
                sem_post(&buffer_sync.llenos);
                yield();
        }
        pthread_exit(NULL);
}

//consumidor, totalmente simetrico
void *consumidor(void *arg) {
        int i;
        int a;
       
        for(i=0; i<NUM_ITEMS; i++) {
                yield();
                sem_wait(&buffer_sync.llenos);
                yield();
                pthread_mutex_lock(&buffer_sync.mutex);
                yield();
               
                //el buffer circular, decolar(i)
                a = buffer_sync.buffer[buffer_sync.pr];
                yield();
                buffer_sync.pr = (buffer_sync.pr+1) % (N+1);
                yield();
                printf("> %5d\n",a);
                yield();
               
                pthread_mutex_unlock(&buffer_sync.mutex);
                yield();
                sem_post(&buffer_sync.vacios);
                yield();
        }
        pthread_exit(NULL);
}

Ejercicios

Variables de Condición

Podemos pensar en los Semaforos y los Mutex (caso particular del anterior) como primitivas que esperan bajo ciertas condiciones (P(s) espera si s=0) y otras que señalizan la continuación ( V(s) ), sólo que las condiciones de espera son predicados específicos a fin de mantener el invariante 0<=s .
Las variables de condición son el tercer y último mecanismo de sincronización que veremos y nos permite permite esperar y señalizar por condiciones más generales que las impuestas por los semáforos.

Hay 2 primitivas básicas:
También se suele incorporar una transmisión masiva ( broadcast) de señalizaciones a fin de despertar a todos los procesos esperando por la variable de condición.

La primitiva de esperar es pthread_cond_wait y ademá s de tomar una variable de condición, toma un mutex. Esto es a fin de establecer exclusión mutua entre todos los hilos que pueden modificar los datos que componen la condición sobre la que se espera y se señaliza. El pseudocódigo de pthread_cond_wait se muestra a continuación:
pthread_cond_wait (cond, mutex)
begin
        pthread_mutex_unlock (mutex);
        block_on_cond (cond);
        pthread_mutex_lock (mutex);
end
Normalmente la secuencia de instrucciones de espera sería la siguente:
pthread_mutex_lock(mutex);

"se modifican los valores de las variables compartidas y se decide esperar"

pthread_cond_wait(cond, mutex);

"debido al mutex, estoy seguro que las condiciones sobre las variables compartidas
que produjeron la señalización se siguen cumpliendo"

pthread_mutex_unlock(mutex);
Si pthread_cond_wait, no liberara y readquiriera la exclusión mútua de manera atómica con las acciones de dormir y despertar, otros hilos podrían cambiar las condiciones sobre las variables compartidas que invaliden la condición que se asocia a cond . Exactamente esto es lo que se puntualiza en la página 269 respecto a la implementación de semáforos en "An Operating Systems Vade Mecum" de R.Finkel.


El ejemplo que se muestra a continuación se denomina sincronización de barrera y nos permite sincronizar fases de una computación que se realiza de forma paralela por un conjunto de hilos.

Supongamos que tenemos una máquina con 2 procesadores y necesitamos realizar un computo, pero para que este computo sea correcto, tenemos que poner a 0 un gran vector A de valores que están en memoria compartida. Podríamos decidir que sería bueno que existan 2 hilos de ejecución, donde uno ponga a 0 los lugares pares del vector y el otro los impares. Si tenemos en cuenta que es muy probable que cada hilo se ejecute en un procesador por separado, entonces esta etapa ocuparía la mitad del tiempo.
Lamentablemente no queremos que se comience a ejecutar el cálculo (segunda fase) hasta que se haya terminado con el proceso de reseto del vector (primera fase), y por supuesto no podemos confiar en que ambos hilos terminarán exactamente al mismo tiempo. Es por ello que introducimos una variable de condición llegaron y una de exclusión mútua mutex. La primera se asocia a la condición 2<=n, donde n representa la cantidad de componentes (en este caso a lo más 2) que finalizaron la primera etapa, mientras que mutex , asegura que los accesos a n sean en exclusión mutua para evitar condiciones de carrera, invalidaciones o interferencias sobre esta variable compartida.
El procedimiento es simple, cada componente pone a 0 sus elementos del vector y cuando termina incrementa n indicando que "una más llegó". Luego si n<2, entonces tenemos que esperar por la condición llegaron, y en cualquier caso que detectemos que 2<=n despertamos a todos los otros hilos que puedan estar esperando por la condición.

Veamos el código:
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define N 2
#define TAMANIO 1024
#define _Y yield()

void *trabajador(void *);
void yield();
void randomize()

//los datos compartidos
int vector[TAMANIO];
struct barrera_s {
        int n;
        pthread_mutex_t mutex;
        pthread_cond_t llegaron;
} barrera;


int main(int argc, char *argv[]) {
        pthread_t hilo_p, hilo_i;
        int par,impar;

        //cambio la semilla de los numeros aleatorios
        randomize();

        //init de los datos compartidos
        barrera.n = 0;
        pthread_mutex_init(&barrera.mutex, NULL);
        pthread_cond_init(&barrera.llegaron, NULL);
        //creo los hilos
        par=0; impar=1;
        pthread_create(&hilo_p, NULL, trabajador, (void *)&par);
        pthread_create(&hilo_i, NULL, trabajador, (void *)&impar);
        //espero que terminen
        pthread_join(hilo_p, NULL);
        pthread_join(hilo_i, NULL);
        //destruyo la estructura
        pthread_cond_destroy(&barrera.llegaron);
        pthread_mutex_destroy(&barrera.mutex);

        return 0;
}

 //trabajador
void *trabajador(void *arg) {
        int paridad
        int i;

        paridad = *(int *)arg; _Y;
        for(i=paridad; i<TAMANIO; i+=2) {
                vector[i] = i; _Y;
        }
        printf("Termino %d\n",paridad); _Y;

        pthread_mutex_lock(&barrera.mutex); _Y;
        barrera.n++; _Y;
        if (N<=barrera.n) { //todas las componentes llegaron
                pthread_cond_broadcast(&barrera.llegaron); _Y;
        } else {    //faltan de llegar
                pthread_cond_wait(&barrera.llegaron, &barrera.mutex); _Y;
        }
        pthread_mutex_unlock(&barrera.mutex); _Y;
       
        printf("Paso %d\n",paridad); _Y;
        return 0;
}

void yield(void) {
        if (rand()%2)
                sched_yield();
}

void randomize(void) {
        FILE *fd;
        unsigned int read;
        unsigned int buffer;
        fd = fopen("/dev/random","r");
        read = fread((void *)&buffer, sizeof(unsigned int), 1, fd);
        srand(buffer);
}

Notar que mejoramos la legibilidad del código definiendo la macro _Y. También aumentamos el no-determinismo en la planificación cambiando la semilla de producción de números aleatorios (man srand), mediante el dispositivo /dev/random, el cual esta produciendo constantemente valores al azar extraídos del entorno (interrupciones, contadores, memoria, etc.).

Ejercicios

Todos los códigos de los ejemplos

En el archivo  (Lab3Ejemplos.tar.gz ) incluye todos los códigos de ejemplo.

Tareas

Se deberán resolver tres problemas antropomorfos de sincronización:
Todos estos problemas tienen su correlato en problemas de sincronización de Sistemas Operativos y se puntualizarán oportunamente.

La Lavandería

"El lavadero de la esquina incorporó la computadora para mejorar la productividad y eficiencia de sus lavarropas. Para esto incluyó en su entrada una serie de terminales tontas donde cada persona que desea una máquina, introduce una moneda, y en caso de que existan máquinas libres, recibe el número de la maquina que le corresponde. Cuando termina de lavar, la persona se retira indicando en la terminal que ya liberó la máquina, para que pueda ser utilizado por otro cliente.

Del programador prolijo y estructurado, pero que poco sabe de concurrencia y sincronización, obtuvimos el siguiente tarball  LaLavanderia.tar.gz , cedido gentilmente.
La tarea es sencilla, se deberá modificar el código de forma tal que se solucionen dos problemas más o menos graves que desde hace ya un mes el programador no es capaz de resolver:
  1. Cuando no hay máquinas, las personas simplemente se van, cuando se les debería decir que esperen en los bancos.
  2. De vez en cuando el sistema asigna la misma máquina a dos personas distintas, causando confusión y malestar entre los clientes.

La versión "seria" de este problema se conoce como la Tabla Multihilo , y básicamente consiste en una tabla de objetos no tipados Tabla[0,tam), que soporta accesos concurrentes ( thread-safe ), con las siguientes operaciones:
y se utiliza para implementar tablas de procesos, hilos, páginas de memoria, archivos abiertos, etc.

Producción de Agua

Usted ha sido contratado por la Madre Naturaleza para ayudarla con la reacción química para formar agua. Ella tiene dificultades para generarla debido a problemas de sincronización. El truco consiste en tener 2 átomos de H y 1 átomo de O, todos al mismo tiempo. Los átomos son threads y puede haber varios O y otros tantos H. Cada átomo llama al procedimiento naturaleza_o_listo y naturaleza_h_listo , cuando cada uno esta listo para reaccionar. Se supone que eventualmente todo átomo estará listo para reaccionar.
Los procesos que ejecutan los átomos-hilos serían

void abstraccion_o(void) {
        //solo soy un O calmo
        naturaleza_o_listo(n);
}
 void abstraccion_h(void) {
        //solo soy un O calmo
        naturaleza_h_listo(n); _Y;
}

Los procedimientos naturaleza_o_listo y naturaleza_h_listo , deberían incrementar la cantidad de átomos listos para reaccionar de cada tipo en la naturaleza y cuando se junte la cantidad necesaria, uno de ellos debería llamar a la función naturaleza_hacer_agua , que simplemente imprime un mensaje y deja que estos átomos terminen, pues ya forman parte de una molécula y no son capaces de reaccionar de ahora en más.
Al finalizar se deberían tener todos las posibles moléculas de agua armadas y los átomos restantes esperando y listos para reaccionar.

Se deberán crear el tipo de dato abstracto naturaleza que será una abstracción de ella, donde además de llevarse la cuenta de la cantidad de átomos de H y O listos para reaccionar se incluyan las variables de sincronización que se consideren necesarias (locks, semáforos y variables de condición).

La versión "seria" del problema se conoce como encuentro entre procesos o rendezvous, y es algo parecido al problema de sincronización de fase o barrera visto en los ejemplos.

El Puente Colgante de una Vía

Ahora su contrato es con Caminos de la Nada, una subcontratista que provee los sistemas informáticos a una de las tantas empresas que concesionan caminos. A Caminos ... se le pidió que brinde un sistema para sincronizar el tráfico sobre un angosto y de liviano tránsito puente en un camino público. El tráfico sólo puede cruzar el puente en una sola dirección a la vez, y si hay más de 3 vehículos sobre el puente, este decididamente se cae.
En este sistema cada automóvil se representa con un hilo que ejecuta el proceso abstraccion_de_auto que se presenta a continuación.

void abstraccion_de_auto(direccion d) {

        puente_entrar(p,d);
        puente_cruzar(p,d);
        puente_salir(p,d);

}

La direccion puede ser Oeste-Este o Este-Oeste, e indica que dirección de paso tiene el vehículo.

El objetivo es crear un TAD sincronizado puente que en sus métodos puente_entrar y puente_salir , tenga la sincronización suficiente para que la expresión siguiente resulte invariante, donde los naturales oe y eo representan la cantidad de vehículos que están sobre el puente en cada una de las direcciones.

(oe=0 | eo=0) & oe<=3 & eo<=3

La versión seria de este problema se conoce como la exclusión mutua entre rojos y azules.
Para este problema se dividen los procesos entre rojos y azules, donde ambos quieren acceder a una sección crítica. Puede haber cuantos rojos y azules se quiera dentro de la SC, mientras no haya dos procesos de diferente color en ella. El invariante que se debe mantener es
azules!=0 => rojos=0
o equivalentemente
azules=0 | rojos=0
El problema del one-lane-bridge es similar sólo que pone restricciones respecto a la cantidad máxima de cada color que pueden estar en la SC.

Problemas como este o el de lectores-escritores (Finkel p.279) pueden ser resueltos de manera sistemática mediante la técnica del Semáforo Binario Dividido. La técnica es originalmente de Hoare y en 1979 Dijkstra escribió EWD703 , un tutorial sobre esta técnica.

Cómo atacar los problemas

Es prerequisito fundamental haber probado y comprendido los códigos de ejemplo de la sección de introducción. También resulta útil como precalentamiento la resolución de los ejercicios que allí se plantean.

La Lavandería

Casi toda la cáscara del problema está lista, solo se deberá incluir suficiente sincronización como para que no ocurran estos errores, pero no demasiada como para que el comportamiento sea puramente serial (pocos interleavings posibles).
Se pueden utilizar cualquiera de los 3 mecanismos de sincronización vistos en pthreads (locks, semáforos y variables de condición), pero siempre adentro del TAD Lavadero definido en lavadero.{c,h} .

Antes de comenzar a resolver los problemas sería bueno mejorar la producción de interleavings, utilizando los sched_yield como en los ejemplos anteriores, a fin de que estos problemas surjan, o si no en la mayoría de los casos se obtiene una ejecución serial.

Producción de Agua

En este problema no damos ningún esqueleto sin sincronizar del problema, pero se puede seguir la línea del problema anterior. Una posibilidad es crear un TAD naturaleza que inicialmente tenga 2 componentes, más todas las de sincronización que se pudieran agregar, junto a las funciones que operan sobre ese TAD.

struct naturaleza_s {
        nat h_listo,o_listo;
};

typedef struct naturaleza_s* naturaleza;

naturaleza naturaleza_crear(void);
void naturaleza_destruir(naturaleza n);
void naturaleza_o_listo(naturaleza n);
void naturaleza_h_listo(naturaleza n);
void naturaleza_hacer_agua(naturaleza n);
void naturaleza_a_cadena(naturaleza n, char* buffer);

Las funciones naturaleza_o_listo y naturaleza_h_listo simplemente incrementan los escalares en el TAD y deberían sincronizarse de manera que tan pronto como haya H2O, se llame a naturaleza_hacer_agua , que tiene como precondición
2<=n->h_listo & 1<=n->o_listo
para que luego de los decrementos que implican la formación del agua, los escalares sigan siendo de tipo Nat.
Claramente si la sincronización resulta correcta siempre se dará la precondición de naturaleza_hacer_agua.

El main es sencillo, una cantidad NUM_O de hilos que hacen abstracción_o y una cantidad NUM_H que hacen lo mismo pero para el hidrógeno.

Hay que imprimir todos los mensajes de debug necesarios dentro del TAD para que se pueda comprobar la corrección de una ejecución inspeccionando la salida y viendo como se suceden las creaciones, reacciones y esperas para la sincronización y luego la muerte de la representación en hilos de los átomos. Puede resular útil engordar la información de debug con la función pthread_self(), la cual devuelve el identificador único del proceso, a fin de identificar que proceso realiza cada acción.

El Puente Colgante de una Vía

Los tipos y las signaturas de los métodos del TAD inicial, sin sincronización podrían ser como sigue:

struct puente_s {
        nat oe,eo;
};

typedef struct puente_s* puente;

puente puente_crear(void);
void puente_destruir(puente p);
void puente_entrar(puente p, direccion d);
void puente_salir(puente p, direccion d);
void puente_cruzar(puente p, direccion d);
void puente_a_cadena(puente p, char *buffer);

Los cuales tienen el mismo patrón que los anteriores.
Las funciones puente_entrar y puente_salir incrementan y decrementan respectivamente p->oe o p->eo dependiendo de la dirección d dada. Esta dirección puede ser codificada con un nuevo tipo de datos enumerado como se muestra a continuación :

typedef enum {
        DIR_OE, DIR_EO
} direccion;

Es conveniente poner assert en todos los lugares donde el invariante pueda ser destruido. Por ejemplo para puente_entrar(p,DIR_EO) deberíamos poder aseverar que es válido p->oe==0 y también que p->eo<3 antes de proceder al incremento de la variable global p->eo.
Clarament cuando completemos el TAD con la sincronización necesaria, estos assert deberán ser siempre válidos.

Este problema tiene muchos aspectos respecto a la justicia de la política de sincronización, por ejemplo sería interesante poder indicar como se comporta su solución si tenemos un auto cruzando en DIR_EO, aparece otro por cruzar en la misma dirección, pero ya hay uno en DIR_OE esperando que el que está sobre el puente pase.

Qué se debe Entregar

Deberá crearse un informe que incluya cada uno de los problemas, indicando todo lo que se crea necesario, para que, a partir de la lectura del informe, una persona con conocimientos de Sistemas Operativos y Concurrencia entienda cuales eran los problemas y como se planteó la solución.
En el informe tambíen se deben copiar y pegar secuencias de ejecución correctas e incorrectas que se produzcan.
Que TAD, primitivas de sincronización, invariantes, modularización, etc, se utilizaron son ejemplos típicos de lo que debería consignarse en el informe.

En general se los códigos deberán ser sencillos, modulares, utilizar TAD y programación defensiva, proveer información de debugging condicional, entre otras cosas.

Toda la sincronización deberá estar dentro del TAD, asi como la información de debug, a fin de que el programa principal sea lo más sencillo posible. No se permite utilizar busy wait.

La Lavandería

Se pide que el código compile en 4 versiones, utilizando compilación condicional con dos definiciones NO_PROB_1 y NO_PROB_2 de manera tal que, cada definición controle la aparición del problema 1 (esperar) y el problema 2 (condiciones de carrera). Entonces si compilo con DEFINES=-DNO_PROB_1 -DNO_PROB_2 en el Makefile, el programa funciona a la perfección ante cualquier interleaving posible, mientras que si compilo con DEFINES= , produce los dos errores de concurrencia mencionados.

El informe deberá indicar cuales eran los problemas, y como la sincronización agregada los soluciona, dando argumentos convincentes al respecto.

No es necesario que el programa que entreguen sea una modificación de éste, pero si deberán mantener al idea de TAD sincronizados .

Producción de Agua

Se deberá entregar además del programa final que incluya toda la sincronización necesaria para la producción de agua.
No es necesario generar compilación condicional a fin de generar diferentes versiones de código.

El informe deberá mostrar como se sincronizó el problema, asi como una explicación convincente de porqué resulta correcta dicha sincronización.

El Puente Colgante de una Vía

Idem al anterior, el programa, y la documentación detallada de como se sincronizó el problema y argumentos convincentes que demuestren que esta resulta correcta.

Cómo se debe Entregar

Cada problema y  se coloca en un directorio distinto, debajo del directorio Lab3Gxx, donde xx es el número de grupo, siguendo el árbol que se muestra a continuación. El informe que incluye los 3 problemas deberá estar en el directorio Lab3Gxx/ .
A partir de todo esto generar un archivo tar.gz que incluya todo recursivamente desde el directorio Lab3Gxx/ con el siguiente comando de línea:

[juan@hal juan]$ tar -zcvf Lab3Gxx.tar.gz Lab3Gxx/

Finalmente enviar el archivo como adjunto a un email a la dirección so2002@famaf.unc.edu.ar .

Tips

Resulta fundamental no confiar jamás en un par de ejecuciones exitosas, probablemente con otra forma de sched_yield() nuestro multiprograma ya no funcione correctamente. Recuerden que el planificador es nuestro peor enemigo y cosas que aquí y ahora funcionan correctísimamente, en dos días y en otra máquina pueden fallar siempre. Prueben sus códigos terminados en diferentes máquinas, con distintas versiones del SO y bajo distintas condiciones de carga.

Como hacer debugging en programas multihilos es casi magia negra, resulta absolutamente indispensable utilizar programación defensiva con asserts y manejo de errores de syscalls, además de estar más que seguros que los TAD funcionan correctamente en un entorno monoprogramación.

Utilizen todos los artilugios para generar interleavings ricos (srand, /dev/random), a fin de asegurar que cada ejecución producirá un interleaving distinto con alta probabilidad.

Imprimir información de debugging resulta también fundamental. Es posible generar un esquema de debugging con salida controlada, definiendo una función void debug(char *mensaje), que internamente controle si los mensajes se eliminarán o se escribirán y a donde. Probablemente una función void debug(int nivel, char *mensaje) , sea un poco más sofisticada, pero también más útil, y básicamente imprime todos los mensajes que tienen un nivel de debugging por debajo de una constante DEBUG , con lo cual los mensajes con nivel bajo son generales y a medida que subimos de nivel aumenta la especificidad.
Como la escritura de la información de debugging es manejada por el kernel del SO, y esté suele hacerlo de manera asíncrona (puede escribir un poco después de que se llamó a la syscall), es posible forzar la sincronicidad, por ejemplo con un syscall fflush(stdout) , a fin de obtener un temporizado más preciso de los mensajes.

Una buena función de impresión del TAD, también puede ayudar mucho, asi como funciones de autotesteo del estilo lavadero_autotesteo que comprueben cosas tan básicas como que pedir una máquina y después preguntar si está disponible, sea verdadero.

Tareas Adicionales

Si les sobra tiempo pueden hacer las siguientes mejoras:  

Nicolás Wolovick, 23 de Octubre de 2002