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.
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.
#include <stdio.h> |
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.
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: |
P1: |
#include <stdio.h> |
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.
|
[juan@hal juan]$ ./prodCons | wc -l |
[juan@hal juan]$ ./prodCons | head |
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];
} buffer_sync;
int pr, pw;
pthread_mutex_t mutex;
sem_t vacios;
sem_t llenos;
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);
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:
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) |
Normalmente la secuencia de instrucciones de espera sería la siguente:
pthread_mutex_lock(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;
} barrera;
pthread_mutex_t mutex;
pthread_cond_t llegaron;
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
return 0;
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);
}
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.).
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.
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.
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.
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.
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.