Lab3: TADs sincronizados

Objetivos


Introducción

En el Laboratorio anterior utilizamos las facilidades de concurrencia de gruesa granularidad de UNIX. Creamos y esperamos 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, como por ejemplo el sistema de archivos, y vimos cómo 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 dos 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 procesos 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 muchos recursos de tiempo (cpu) y espacio (memoria).
Los hilos en cambio, lo único que no comparten son los registros del microprocesador y el espacio de la pila, por lo que 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 en los hilos es posible transferir información entre componentes simplemente leyendo y escribiendo en el espacio de memoria compartida, 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, incorpora 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).

Es muy interesante la discusión que se propone en "The Art of Unix Programming" en el capítulo 7 "Multiprogramming", sobre todo en la subsección "Threads Threat or Menace?", atacando abiertamente el uso de hilos en la multiprogramación.

Como crear hilos

Veamos, a través un ejemplo, como crear 2 hilos que impriman por la salida estandar, N veces "Hola Mundo" y M veces"Mundo Hola" respectivamente.
Necesitamos incluir la cabecera de la biblioteca pthreads, 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.


holaMundo.c
#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 puede hacer con 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 trivializa. 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 un ejercicio típico de concurrencia, donde hay un multiprograma con 2 componentes, cada una de estas incrementa y decrementa cíclicamente 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 más 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 del multiprograma escrito en el Lenguaje de los Comandos Guardados de Dijkstra (LCGD).


programTopology.c
#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 una secuencia (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.


setBuffer.c

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

#define CAPACIDAD 16

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

/* 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 */
}
}


/* 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 la 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.i
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.
Nosotros los llamaremos TADs sincronizados, título de éste Laboratorio.

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 e 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 éstas (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:


prodCons.c
#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

Sincronizando con Variables de Condición

Podemos pensar los semáforos como una primitiva de sincronización que con dos operaciones, una que espera en ciertas condiciones -P(s) espera si s=0- y otra que señalizan la continuación -V(s)-. Estas condiciones de espera son predicados específicos a fin de mantener el invariante de semáforo 0<=s.
Las variables de condición son el tercer y último mecanismo de sincronización que veremos y nos permite esperar y señalizar por condiciones más generales que las impuestas en 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 para esperar es pthread_cond_wait. 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 de manera que invaliden la condición que se asocia a cond. Exactamente esto es lo que se puntualiza en la página 269 respecto de 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 cómputo, pero para que éste sea correcto, tenemos que poner a 0 un gran vector A de valores que están en memoria compartida. Sería deseable que existan 2 hilos de ejecución, donde uno ponga a 0 los lugares pares del vector y 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:


barrera.c
#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;
for(i=paridad; i<TAMANIO; i+=2) {
vector[i] = i;
}
printf("Termino %d\n", paridad); pthread_mutex_lock(&barrera.mutex);
barrera.n++;
if (N<=barrera.n) { /* todas las componentes llegaron */
pthread_cond_broadcast(&barrera.llegaron);
} else { /* faltan de llegar */
pthread_cond_wait(&barrera.llegaron, &barrera.mutex);
}
pthread_mutex_unlock(&barrera.mutex);
printf("Paso %d\n", paridad);
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 está produciendo constantemente valores al azar extraídos del no-determinismo del entorno (interrupciones, contadores, memoria, etc.).

Ejercicios

Tareas

Se deberán resolver dos problemas no-antropomorfos de sincronización:

Ambos son TAD que implementan de alguna manera el tipo función, la Tabla almacena objetos en los índices [0,N), mientras que el Entorno almacena pares de cadena (clave,valor), donde cada clave es única.
La Tabla podria ser utilizada por ejemplo para manejar la tabla de descriptores de procesos o descriptores de archivos de un núcleo. El Entorno tiene un uso directo para manejar el environment de los procesos (man environ).

Los códigos de ambos TAD están completos, y funcionan correctamente en aplicaciones seriales, si embargo cuando paralelizamos su uso, fallan.
La tareas será entonces:

El código que se entregue deberá estar preparado tanto para evidenciar los problemas, como para mostrar que ellos no ocurren luego de la solución.
Se utilizará compilación condicional para generar las distintas versiones ejecutables.

Tabla Sincronizada

Este TAD tiene los siguientes problemas:
  1. De vez en cuando algunas aserciones fallan.
  2. También puede ocurrir que se asigne un mismo índice de la tabla a dos hilos distintos.
  3. Cuando hay más procesos que índices en la tabla, los procesos suelen obtiener un "Tabla Llena".
La tarea es sencilla, se deberá modificar el código de forma tal que por un lado se expongan de manera concreta los problemas identificados, y además se los solucione, pudiendo compilar versiones con todas las combinaciones posibles de problemas y soluciones.

Entorno Sincronizado

Para env los problemas son más sutiles y a priori no aparecen de alguna manera explícita en el código que se les entrega. Entonces, la tarea de estudiar el código y pensar en los posibles problemas es su responsabilidad.
Como en el caso anterior, haciendo uso de compilación condicional, se podrán generar las versiones con y sin los diversos problemas que genera la concurrencia.

El problema del balance entre simplicidad de la sincronizació y el grado de paralelismo no es menor en este problema. El TAD env es una pequeña base de datos en ambientes con muchos clientes (procesos) consultando y modificando una cantidad inmensa de datos, la eficiencia juega un papel fundamental.

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.
También es importante, relacionar los éstos problemas con los que se dieron en el teórico (sección crítica, productor-consumidor, lectores-escritores, filósofos comensales, etc.), pues aunque los problemas no son exactamente iguales, pueden ser solucionados como combinaciones de éstos.

Tabla Sincronizada

Casi toda la cáscara del problema está lista, sólo se deberá incluir suficiente sincronización como para que no ocurran los problemas, pero no tanta que lleve a un comportamiento secuencial (pocos interleavings posibles).
Se pueden utilizar cualquiera de los 3 mecanismos de sincronización de pthreads enunciados (locks, semáforos y/o variables de condición), pero siempre dentro del TAD Tabla definido en tabla.{c,h}.

Antes de comenzar a resolver los problemas es necesario mejorar la producción de interleavings, utilizando alguna de las funciones del módulo yield, o bien otras que ustedes propongan. La idea es que los problemas surjan, de otra manera en la mayoría de los casos se obtiene una ejecución serial.
Notar que probablemente tengan que insertar numerosos yield() en la implementacion del TAD, pero tengan cuidado, con el problema detectado, un par de sched_yield() bien colocados pueden ser suficientes para evidenciar el problema.

Entorno Sincronizado

A manera de hint podemos decir que la solución al problema de lectores/escritores (Finkel p.279) puede resultar útil, en todas sus versiones: semáforos, monitores, variables de condición, etc. También existen soluciones más simples.
Problemas de sincronización como este y otros (puente de una sola vía, semáforo general a partir de uno binario, el barbero dormilón, etc.), 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 la técnica.

El código que se entrega casi no tiene aserciones que muestren cuando el programa se desvía de su camino natural. Su implementador, Antonio Lenton probablemente haya testeado el código fuertemente en ejecuciones seriales, pero seguramente no lo hizo en entornos paralelos.
Como la implementación del TAD utiliza un árbol binario de búsqueda rojo-negro para hacer eficientes las búsquedas, deberán comprender mínimamente cuando uno de éstos árboles cumple con las condiciones de consistencia. Pueden encontrar descripciones en libros de algoritmos y estructuras de datos.
Cuando tengan las condiciones de consistencia, podrán insertar asserts para forzar una excepción en caso de que no se cumplan.

Este problema, como el anterior admiten varias soluciones, desde las más sencillas pero con un bajo grado de paralelismo, hasta algunas más complicadas, que dan más libertad al planificador.

Qué se debe Entregar

Este laboratorio es diferente a los anteriores en cuanto a que el trabajo de programación es mínimo, por lo tanto la mayor carga estará en el informe.
El informe deberá indicar cuales eran los problemas, y como la sincronización agregada los soluciona, dando argumentos convincentes al respecto.
En el informe tambíen se pueden copiar y pegar secuencias de ejecución correctas e incorrectas que se produzcan, pedazos de código donde se producen los problemas, etc.

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, etc.), 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 la libc, y está suele hacerlo de manera asíncrona (puede escribir un poco después de que se llamó la función), es posible forzar la sincronicidad, por ejemplo con la llamada de la libc 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 table_autotest que comprueben cosas tan básicas como que pedir un indice de la tabla y después preguntar si está disponible, sea falso.

Tareas Adicionales

Si les sobra tiempo pueden hacer las siguientes mejoras:

Nicolás Wolovick, 9 de Octubre de 2003