Wiki CC3301

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
===== Threads =====

La llamada al sistema //fork// crea un //proceso Unix// que posee su propio espacio de direcciones independiente
de los demás procesos.  Los procesos pesados no comparten nada de su memoria.  Solo pueden intercambiar
datos a través de archivos, pipes o sockets.  Se dice que estos procesos son //pesados//, porque son caros en cuanto
a la cantidad de recursos que necesitan, el sobrecosto en tiempo de CPU para que el núcleo pueda transferir
el procesador de un proceso a otro y el sobrecosto de comunicación para poder intercambiar datos con otros procesos.

Desde los inicios de la computación se discutió la necesidad de crear un proceso más barato, o también se dice
un proceso liviano.  Un proceso liviano comparte su memoria con otros procesos livianos.  Con el tiempo estos
procesos se denominaron //threads// o en español, //hebras// o //hilos// de ejecución.  A los conceptores de los
lenguajes de programación no les gusta este tipo de procesos por lo frágil que resultan los programas
que los usan: mal programados sufren de caídas aleatorios, bloqueos sorpresivos o simplemente resultados
no confiables.

Con la aparición del lenguaje Java y los procesadores multi-cores, la discusión quedó sanjada en favor
de la existencia de los threads.  Tomó un tiempo adaptar lenguajes como C que no fueron concebidos
para ofrecer threads.  Las primeras implementaciones eran efectivamente muy frágiles, pero hoy en
día las aplicaciones que los usan pueden ser robustas si son bien programadas.  Esto no es fácil,
requiere de una disciplina que vamos a inculcar en este curso y en el próximo (Sistemas Operativos).

Observación: este documento es suficiente para efectos del curso pero si Ud. desea profundizar
en el tema puede consultar [[https://computing.llnl.gov/tutorials/pthreads/|POSIX Threads Programming]]
(link aportado por un ex-alumno del curso).

==== Creación de threads ====

Para crear un thread en Linux desde C se usa:

  int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                     void *(*start_routine) (void *), void *arg);

Esta llamada lanza un nuevo thread que comparte la memoria con la del thread que hace la invocación.
De esta forma un proceso se convierte en un espacio de direcciones y un enjambre de threads que
comparte ese espacio de direcciones.

El nuevo thread ejecuta la función //start_routine// y todos las funciones que ésta llame en un
nuevo stack de usualmente 8 MB.  Si el thread se crea exitosamente pthread_create retorna 0.  Un valor
distinto de 0 significa que el thread no se pudo crear por ejemplo porque se excedió el número
máximo de procesos que puede crear un mismo usuario (típicamente 80).

Para que ps muestre los threads de un proceso hay que usar ''ps -fL''.  La columna LWP es el pid del thread.
==== Término de un thread ====

Un thread termina cuando la función de inicio retorna o cuando desde ese thread se invoca la función:

  void pthread_exit(void *retval);

Cuidado, el thread no debe invocar exit, porque esto significaría el término de todo el proceso con su
enjambre de threads.

==== Esperar el término de un thread ====

Como ocurre con los procesos pesados, alguien debe enterrar un thread, pero no necesita ser su creador (o padre).
Esto se hace con:

  int pthread_join(pthread_t thread, void **retval);

Solo un thread debe hacer esta invocación.  Si nunca se invoca pthread_join, el thread se convierte en un
zombie y su identificador de thread jamás será liberado.

=== Ejemplo: factorial ===

El siguiente programa calcula usando 2 threads el factorial de un número recibido como argumento desde la línea
de comandos.  Ejemplo:

  % fact 6

Código del programa:

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

  double mult(int i, int j) {
    int k;
    double p= 1.;
    for (k=i; k<=j; k++)
      p *= k;

    return p;
  }

  typedef struct {
    int i, j;
    pthread_t pid;
    double res;
  } Args;

  void *mult_thread(void *ptr) {
    Args *args= (Args*)ptr;
    args->res= mult(args->i, args->j);
    return NULL;
  }

  int main(int argc, char **argv) {
    int n= atoi(argv[1]);
    int l= (n+1)/2;
    Args args1, args2;

    args1.i= 1;
    args1.j= l;
    pthread_create(&args1.pid, NULL, mult_thread, &args1);

    args2.i= l+1;
    args2.j= n;
    pthread_create(&args2.pid, NULL, mult_thread, &args2);

    pthread_join(args1.pid, NULL);
    pthread_join(args2.pid, NULL);
    printf("factorial=%1.14g\n", args1.res*args2.res);
    return 0;
  }
</code>

El tipo Args se crea para poder pasar varios argumentos al thread, albergar el pid del thread
y retornar el resultado final.

=== Ejercicio ===

  * ¿Cómo podría modificar este programa de modo de lanzar un solo thread adicional y aún obtener el mismo grado de paralelismo?
  * Modifique el programa anterior de modo que se reciba como segundo argumento en la línea de comandos el número de threads que se deben crear.

=== Ejemplo: multiplicación de matrices ===

La función par_mult calcula el producto de 2 matrices usando p threads.  Recibe como argumentos:

  * n: el tamaño de las matrices
  * p: el número de threads a utilizar
  * a y b: las matrices que se deben multiplicar
  * c: la matriz en donde dejar el resultado

En cada threads se invoca la función mult que multiplica un rango de filas de la
matriz a por la matriz b completa.  Estudie el siguiente código.

<code>
  #include <stdlib.h>
  #include <pthread.h>

  typedef double **Matriz;

  void mult(int n, int ini, int fin, Matriz a, Matriz b, Matriz c) {
    int i, j, k;

    for (i= ini; i<fin; i++)
      for (j= 0; j<n; j++) {
        double s= 0.;
        for (k= 0; k<n; k++)
          s += a[i][k] * b[k][j];
        c[i][j]= s;
      }
  }

  typedef struct {
    int n, ini, fin;
    Matriz a, b, c;
    pthread_t pid;
  } Args;

  void *mult_thread(void *ptr) {
    Args *args= (Args*)ptr;
    mult(args->n, args->ini, args->fin, args->a, args->b, args->c);
    return NULL;
  }

  void par_mult(int n, int p, Matriz a, Matriz b, Matriz c) {
    int l= (n-1)/p + 1;
    int i;
    Args *args_a= (Args*)malloc(p*sizeof(Args));

    for (i= 0; i<p; i++) {
      Args *args= &args_a[i];
      args->n= n;
      args->ini= l*i;
      args->fin= i==p-1 ? n : args->ini+l;
      args->a= a;
      args->b= b;
      args->c= c;
      pthread_create(&args->pid, NULL, mult_thread, args);
    }

    for (i= 0; i<p; i++) {
      Args *args= &args_a[i];
      pthread_join(args->pid, NULL);
    }
    free(args_a);
  }
</code>

==== Secciones críticas ====

Suponga que un banco atiende una infinidad de clientes que compran en el comercio con
la tarjeta redcompra.  Se necesita un programa que autorice las compras si el saldo
es suficiente o la rechace si es insuficiente.  El problema es que comunicarse con
los terminales de redcompra es lento debido a la latencia de la red, de modo que
se decidió utilizar múltiples threads para comunicarse con los terminales de redcompra.

Nos abstraeremos del problema de comunicación con el terminal y solo diremos que se
requiere programar la función //autorizar// que recibe como argumentos el
número de una cuenta y el monto de la compra.  La función debe consultar si hay saldo
suficiente.  Si lo hay actualizar el saldo y retornar verdadero.  Si no lo hay, retornar falso.
Además Ud. dispone de un diccionario que asocia números de cuenta con el saldo.
La función //autorizar// es invocada entonces desde los múltiples threads que se comunican
con los terminales de redcompra.

La siguiente sería una versión incorrecta de la función //autorizar//.  Supondremos que
al inicio del programa se invocará una sola vez la función //inicializacion// que se encarga
de crear el diccionario:

<code>
  /* Versión *incorrecta* */
  Diccionario dicc;

  void inicializacion() {
    dicc= nuevoDiccionario();
  }
  
  int autorizar(int cuenta, int monto) {
    int saldo= consultar(dicc, cuenta);
    if (monto>saldo)
      return FALSO;
    else {
      int nuevo_saldo = saldo - monto;
      modificar(dicc, cuenta, nuevo_saldo);
      return VERDADERO;
    }
  }
</code>

El problema ocurre porque hay familias que comparten la misma cuenta y es perfectamente
posible que el marido y su mujer hagan compras simultáneas.  Por lo tanto podría ocurrir
que el saldo sea 100 y que ambos hagan una compra por 100.  Las 2 compras se atienden
en threads distintos.  El primer thread llama a consultar y determina que existe saldo
para el marido.  El segundo thread llama a consultar, antes de que el primer thread
realice la llamada a modificar, y por lo tanto también determina que hay saldo.
Entonces ambos calculan que el nuevo saldo es 0 y llaman paralelamente a modificar dejando
el saldo en 0.  Pero el banco perdió 100, autorizando equivocadamente una de las compras
y peor aún, el saldo no quedó en negativo.

Este error en programación concurrente se denomina //data race//.  Para asegurar que
los resultados siempre sean correctos se necesita asegurar la //exclusión mutua// de
los threads mientras ejecutan //actualizar//, es decir se debe impedir que 2 threads
lleguen a ejecutar simultáneamente esa función.  Un trozo de código
que necesita la exclusión mutua de los threads para que se ejecute correctamente
se denomina una //sección crítica//.

Las secciones críticas limitan el paralelismo, pero en este ejemplo
se considera que el tiempo de consulta y modificación del diccionario es marginal
en comparación con el tiempo de comunicación con el terminal (microsegundos vs.
muchos milisegundos) de modo que la pérdida de paralelismo no es significativa.

La exclusión mutua es un caso particular de sincronización de threads.
Existen otros casos de sincronización como cuando un thread necesita
esperar a que otro thread suministre algún dato para poder continuar.

==== Mutex ====

Los sistemas de threads ofrecen diversas herramientas de sincronización.  Una de ellas
son los mutex que sirven específicamente para garantizar la exclusión mutua.  Un mutex
se manipula con las siguientes funciones:

<code>
  #include <pthread.h>
  pthread_mutex_t mutex;
  pthread_mutex_init(&mutex, NULL);
  phtread_mutex_destroy(&mutex);
  pthread_mutex_lock(&mutex);
  phtread_mutex_unlock(&mutex);
</code>

Para ver como se usan
veamos como se resuelve con un mutex el problema de la actualización de los saldos de
cuenta.

<code>
  /* Versión correcta */
  
  Diccionario dicc;
  pthread_mutex_t dicc_mutex;
  
  void inicialización() {
    dicc= nuevoDiccionario();
    pthread_mutex_init(&dicc_mutex, NULL);
  }
  
  int autorizar(int cuenta, int monto) {
    int saldo, res;
    pthread_mutex_lock(&dicc_mutex);
    saldo= consultar(dicc, cuenta);
    if (monto>saldo)
      res= FALSO;
    else {
      int nuevo_saldo = saldo - monto;
      modificar(dicc, cuenta, nuevo_saldo);
      res= VERDADERO;
    }
    pthread_mutex_unlock(&dicc_mutex);
    return res;
  }
</code>

La función pthread_mutex_lock solicita entrar a la sección crítica adquiriendo la propiedad del mutex.
La función pthread_mutex_unlock anuncia la salida de la sección crítica liberando el mutex.
Dado el mutex m, la garantía que entregan las funciones pthread_mutex_lock y
pthread_mutex_unlock es que en todo instante a lo más hay un thread que invocó pthread_mutex_lock(&m),
éste retornó, pero el mismo thread aún no invoca pthread_mutex_unlock(&m).  Es decir solo un thread
puede adquirir el mutex.  Si un thread invoca
pthread_mutex_lock, pero determina que retornar de inmediato es una violación de la garantía porque otro
thread adquirió el mutex previamente entonces pthread_mutex_lock espera hasta que el otro thread
anuncie su salida con pthread_mutex_lock.

=== Ejercicio ===

Estudie el caso de sección crítica que aparece en
[[https://wiki.dcc.uchile.cl/cc3301/start#clase_14threadsregiones_criticas|https://wiki.dcc.uchile.cl/cc3301/start#clase_14threadsregiones_criticas]].  Compile y ejecute los 2 programas.

==== Productor/consumidor ====

El siguiente programa lee de Internet un video y lo muestra en pantalla:

<code>
  void reproducirVideo() {
    for (;;) {
      Cuadro *cuadro= leerCuadro();
      if (cuadro==null)
        break;
      mostrarCuadro(cuadro);
    }
  }
</code>

La función leerCuadro lee de Internet un cuadro del video (frame) y la función mostrarCuadro lo muestra
en la pantalla.  El problema es que las latencias de Internet son imprevisibles y puede ocurrir
que leerCuadro tome demasiado tiempo y no se alcance a mostrar el siguiente cuandro con lo que se pierde
la fluidez del video.  Para evitar estos saltos se propone leer por adelantado hasta N cuadros y así
mantener una reserva por si leerCuadro se demora más de lo acostumbrado.  No se deben leer más de N
cuadros para no ocupar memoria en exceso.  Si la velocidad del enlace de Internet es insuficiente
va a ocurrir que en algún momento se agoten los cuadros, y en ese caso no queda otra que esperar a que
llegue un cuadro, sacrificando la fluidez del video.

Para implementar esta solución se requiere usar un thread que denominaremos productor que se encarga
de llamar a leerCuadro una y otra vez depositando los cuadros obtenidos en una estructura que
llamaremos buffer.  Un segundo thread que denominaremos consumidor extrae los cuadros del buffer e
invoca mostrarCuadro.  El buffer admite almacenar hasta solo N cuadros.  Si el consumidor encuentra
que el buffer está vacío entonces espera hasta que el productor deposite un cuadro.  Por otra parte
si el productor encuentra el buffer lleno, espera hasta que el consumidor extraiga un cuadro.

La siguiente es la implementación de los threads productor y consumidor:

<code>
  void productor(Buffer *buf) {
    for (;;) {
      Cuadro *cuadro= leerCuadro();
      put(buf, cuadro);
      if (cuadro==NULL)
        break;
    }
  }
  
  void *consumidor(void *ptr) { // porque se usa en pthread_create
    Buffer *buf= ptr;
    for (;;) {
      Cuadro *cuadro= get(buf);
      if (cuadro==NULL)
        break;
      mostrarCuadro(cuadro);
    }
    return NULL;
  }
  
  void reproducirVideo() {
    Buffer *buf= nuevoBuffer(60);
    pthread_t t;
    pthread_create(&t, NULL, consumidor, buf);
    productor(buf);
    pthread_join(t, NULL);
  }
</code>

El problema se reduce a implementar el tipo Buffer, put y get.  La siguiente es una implementación incorrecta.

<code>
  /* Versión incorrecta */
  typedef struct {
    int size;
    Cuadro **array;
    int in, out;
    int n;
  } Buffer;
  
  void put(Buffer *buf, Cuadro *cuadro) {
    while (buf->n==buf->size)
      /* busy waiting */;
    buf->array[buf->in]= cuadro;
    buf->in= (buf->in+1) % buf->size;
    buf->n++;
  }
  
  Cuadro *get(Buffer *buf) {
    Cuadro *cuadro;
    while (buf->n==0)
      /* busy-waiting */ ;
    cuadro= buf->array[buf->out];
    buf->out= (buf->out+1) % buf->size;
    buf->n--;
    return cuadro;
  }
</code>

Esta solución es incorrecta porque puede ocurrir que el productor y el consumidor incrementen
y decrementen n simultáneamente haciendo que se pierda un cuadro o que se gane un cuadro inexistente.
Es decir se produce un data-race.

Una solución es transformar las líneas que incrementan y decrementan n en una sección crítica
usando un mutex para garantizar la exclusión mutua.

Pero aún así esta solución sería ineficiente porque los ciclos de busy-waiting consumen el 100%
del //core// que los ejecuta, dificultando la ejecución de otros procesos o threads, y por último consumiendo
más energía de la necesaria y acelerando así el consumo de la batería de un notebook.



==== Monitores ====

Una forma más intuitiva de resolver los problemas de sincronización se logra con los monitores.
Con los pthreads de Linux, un monitor está conformado por un mutex (tipo pthread_mutex_t) y al menos una condición (tipo pthread_cond_t).
El mutex sirve para garantizar la exclusión mutua de los threads al manipular una estructura
de datos y la condición sirve para suspender threads cuando una operación no se puede realizar
todavía, hasta que un segundo thread realice otra operación.

A modo de ejemplo, consideremos nuevamente el problema del productor/consumidor.
Si el buffer está vacío, el consumidor debe esperar hasta que un productor deposite un cuadro.
Del mismo modo, si el buffer está lleno,
el productor debe espera hasta que un consumidor extraiga un cuadro.

Más arriba ya se enunció como manipular un mutex.  Estas son las funciones para manipular una condición:

  #include <pthread.h>
  pthread_mutex_t mutex;
  pthread_cond_t cond;
  pthread_cond_init(&cond, NULL);
  pthread_cond_destroy(&cond);
  
  pthread_cond_broadcast(&cond);
  pthread_cond_signal(&cond);
  pthread_cond_wait(&cond, &mutex);
  struct timespec abstime;
  pthread_cond_timedwait(&cond, &mutex, &abstime);

Veamos una solución al problema del productor/consumidor usando condiciones:

<code>
  #include <stdlib.h>
  #include <pthread.h>

  typedef int Cuadro;

  /* Version correcta */
  typedef struct {
    int size;
    Cuadro **array;
    int in, out, cnt;
    pthread_mutex_t mutex;
    pthread_cond_t cond;
  } Buffer;
  
  Buffer *nuevoBuffer(int size) {
    Buffer *buf= (Buffer*)malloc(sizeof(Buffer));
    buf->size= size;
    buf->array= (Cuadro**)malloc(size*sizeof(Cuadro*));
    buf->in= buf->out= buf->cnt= 0;
    pthread_mutex_init(&buf->mutex, NULL);
    pthread_cond_init(&buf->cond, NULL);
    return buf;
  }
  
  void put(Buffer *buf, Cuadro *cuadro) {
    pthread_mutex_lock(&buf->mutex);
    while (buf->cnt==buf->size)
      pthread_cond_wait(&buf->cond, &buf->mutex);
    buf->array[buf->in]= cuadro;
    buf->in= (buf->in+1) % buf->size;
    buf->cnt++;
    pthread_cond_broadcast(&buf->cond);
    pthread_mutex_unlock(&buf->mutex);
  }
  
  Cuadro *get(Buffer *buf) {
    Cuadro *cuadro;
    pthread_mutex_lock(&buf->mutex);
    while (buf->cnt==0)
      pthread_cond_wait(&buf->cond, &buf->mutex);
    cuadro= buf->array[buf->out];
    buf->out= (buf->out+1) % buf->size;
    buf->cnt--;
    pthread_cond_broadcast(&buf->cond);
    pthread_mutex_unlock(&buf->mutex);
    return cuadro;
  }
</code>

La idea es que buf->mutex controla el acceso al buffer.  El invariante que se debe preservar consiste en que solo
un thread puede trabajar con el buffer en un instante dado.  Para lograrlo se declara en el buffer una variable
de tipo mutex.  Tener la propiedad del buffer es equivalente a tener la propiedad del mutex.  Para empezar a trabajar con
el buffer se debe solicitar primero su propiedad con la operación pthread_mutex_lock y cuando se termina hay que liberarlo
con pthread_mutex_unlock para que otros threads puedan obtener la propiedad del mismo buffer.
El siguiente diagrama muestra esta funcionalidad:

{{ :lock2.png?300 |}}

En 1, el productor acaba de invocar put y por lo tanto llama a pthread_mutex_lock para ganar la propiedad del buffer, es decir el mutex que controla el acceso al buffer.  En 2, el consumidor necesita obtener un cuadro del buffer y llama a pthread_mutex_lock, pero debe esperar porque el buffer lo posee el productor.  En 3, el productor libera el buffer y por lo tanto lo adquiere el consumidor, pudiendo extraer el cuadro requerido (suponiendo que el buffer no está vacío).  En 4, el consumidor libera el buffer.  En este caso se dice que hubo contención por el buffer, es decir una tarea trató de obtener el buffer cuando era la propiedad de otra tarea.

La operación pthread_cond_wait está asociada con un mutex y una condición.  El thread que lo invoca
libera el mutex y se bloquea a la espera de una operación pthread_cond_broadcast o pthread_cond_signal
sobre la misma condición.  La primera despierta a todos los threads bloqueados en un pthread_cond_wait
en esa condición.  La función pthread_cond_signal por otra parte despierta un solo thread.  El siguiente
diagrama muestra cómo se usa pthread_cond_wait y pthread_cond_broadcast en la solución para el buffer
para que el consumidor espere cuando encuentra el buffer vacío:

{{ :wait3.png?300 |}}

En 1, el productor llama a leerCuadro para fabricar el primer cuadro.  En 2, el consumidor llama a get para obtener un cuadro.  Para ello adquiere el buffer en 3 llamando a pthread_mutex_lock, pero se encuentra con el buffer vacío y por lo tanto se coloca en espera, llamando a pthread_cond_wait en 4, a la espera de un broadcast.  Observe que en 3 no hubo contención por el buffer, ya que éste estaba libre cuando se solicitó.  En 5, el productor terminó de fabricar el primer cuadro y llama a put para depositarlo en el buffer.  En 6, adquiere sin problemas el buffer porque el consumidor lo liberó en 4.

El productor llama a pthread_cond_broadcast en 7, lo que despierta al consumidor, pero este último continúa esperando ahora la propiedad del buffer.  El consumidor no puede continuar inmediatamente después de broadcast, porque ya no habría exclusión mutua y podrían ocurrir dataraces.  En 8, el productor libera el buffer y por lo tanto lo adquiere el consumidor, el que extraerá el cuadro recién depositado, sin peligro de dataraces porque el productor ya no está manipulando el buffer.  Observe que en 9, el consumidor invoca un broadcast que no despierta a ninguna tarea y luego libera el buffer en 10.  Cuando se llama a mostrarCuadro en 11 se obtiene la concurrencia buscada por esta solución ya que una tarea lee un cuadro al mismo tiempo que otra tarea muestra un cuadro previo.  En 12, el productor deposita un segundo cuadro en el buffer y el consumidor lo obtiene en 13 sin tener que esperar porque el buffer ya contiene el cuadro solicitado (depositado en 12).

=== El productor/consumidor: caso general ===

El problema recién resuelto es un caso particular de un productor y un consumidor de cuadros de video.  En el caso general
pueden haber múltiples productores y consumidores de alguna clase de objetos que llamaremos ítemes.  Un ítem se fabrica llamando a alguna función que llamaremos ''produce'' y se
consume con la función ''consume''.  Muchos problemas se pueden resolver con varios
threads que depositan ítemes en un buffer y otros tantos threads los extraen del buffer.

El único que hay que hacer al buffer que se programó más arriba, para el caso de la lectura y despliegue de video, es el tipo de los ítemes almacenados en el buffer.  Observe que este
buffer funciona correctamente para invocaciones concurrentes de put (o de get), gracias a
que el mutex garantiza su exclusión mutua.

Un punto importante a considerar es que los monitores no especifican un orden en el que se despiertan los threads después de un broadcast.  Esto es cierto con los monitores de pthreads y también con los de Java.
En el siguiente diagrama veremos qué sucede cuando 3 threads consumidores solicitan extraer un ítem de un buffer que se encuentra vacío:

{{ :broadcast3.png?500 |}}

En 1, el consumidor A llamó a get, y por lo tanto pide el buffer, pero se encuentra con que el buffer está vacío de modo que espera llamando a pthread_cond_wait en 2 y liberando así el buffer.  En 3, el consumidor B llamó a get y pide el buffer, que está libre.  En 4, el consumidor C pide el buffer pero hay contención: no lo obtiene porque lo tiene el consumidor B y en consecuencia espera.  En 5, el consumidor B se da cuenta que el buffer está vacío y llama a pthread_cond_wait, lo que libera el buffer y entonces el consumidor C adquiere el buffer.  En 6, se da cuenta que está vacío y llama a pthread_cond_wait.  En este momento hay 3 consumidores que esperan un ítem.

Mientras tanto el productor estaba ocupado produciendo un ítem.  En 7, llamó a put para depositar el ítem que acaba de producir y por lo tanto adquirió el buffer.  Ahora llama a pthread_cond_broadcast para despertar a los 3 consumidores.  Pero los consumidores no pueden continuar hasta adquirir la propiedad del buffer.  En 8, el productor libera el buffer llamando a pthread_mutex_unlock.

En este punto, lo intuitivo es que el consumidor A adquiere el buffer, pero en general la especificación de los monitores no garantiza el orden en que los threads adquieren el monitor después de un broadcast.  Por eso, en este ejemplo se eligió que el consumidor B adquiriese el buffer en primer lugar (pero también pudo haberlo hecho el consumidor A o el consumidor C).  Entonces éste extrae el ítem del buffer, dejándolo vacío, y libera el buffer en 9.  Ahora adquiere el buffer el consumidor A (pero pudo haber sido el consumidor C) y encuentra que el buffer está vacío y por lo tanto llama a pthread_cond_wait, para continuar esperando.

Este ejemplo subraya la importancia de usar while en vez de if en la llamada a pthread_cond_wait.  En general en las soluciones con monitores, suele ocurrir que al despertarse de un wait las condiciones para proceder con la operación todavía no se cumplen y se debe continuar esperando.  Aún cuando parezca que en su solución sí se puede usar if, use while de todas formas porque es altamente probable que su intuición lo engañe.  Y por último, el volver a evaluar la condición del while es un costo marginal en tiempo de CPU.

El consumidor A libera el buffer en 10.  Esto despierta al consumidor C que también encuentra vacío el buffer y llama a pthread_cond_wait en 11.  En 12, el productor deposita un segundo ítem y llama a pthread_cond_broadcast, lo que despierta a los consumidores A y C.  Observe que el consumidor B está consumiendo el primer ítem.  Cuando put llama a pthread_mutex_unlock, el consumidor C adquiere el buffer y extrae el segundo ítem y libera el buffer en 13.  Ahora es el consumidor A el que adquiere el buffer pero continúa esperando en 14, hasta que el productor termine el 3er ítem.
Observe que nada impide que los consumidores B o C vuelvan a llamar a get y queden a la espera de un ítem.  Cuando el productor deposite el 3er ítem, podría ocurrir que el consumidor A no sea el ganador de este ítem y continuar así esperando.

=== Uso de múltiples condiciones ===

El problema de broadcast es que genera muchos cambios de un thread a otro inútiles porque cuando un productor
deposita un elemento, solo un consumidor podrá extraerlo.  Es tentador usar pthread_cond_signal, pero en este
problema hay condiciones de borde que podrían llevar a un deadlock cuando se usa solo una condición.
Esto está bien explicado en [[http://stackoverflow.com/questions/37026/java-notify-vs-notifyall-all-over-again|Java: notify() vs. notifyAll() all over again]].  La explicación es para el caso del productor/consumidor escrito
en Java, y por lo tanto se usa notify en vez de signal y notifyAll en vez de broadcast.

La siguiente solución usa 2 condiciones para resolver el problema:

<code>
  #include <stdlib.h>
  #include <pthread.h>

  typedef int Cuadro;

  /* Version correcta */
  typedef struct {
    int size;
    Cuadro **array;
    int in, out, cnt;
    pthread_mutex_t mutex;
    pthread_cond_t noempty, nofull;
  } Buffer;
  
  Buffer *nuevoBuffer(int size) {
    Buffer *buf= (Buffer*)malloc(sizeof(Buffer));
    buf->size= size;
    buf->array= (Cuadro**)malloc(size*sizeof(Cuadro*));
    buf->in= buf->out= buf->cnt= 0;
    pthread_mutex_init(&buf->mutex, NULL);
    pthread_cond_init(&buf->noempty, NULL);
    pthread_cond_init(&buf->nofull, NULL);
    return buf;
  }
  
  void put(Buffer *buf, Cuadro *cuadro) {
    pthread_mutex_lock(&buf->mutex);
    while (buf->cnt==buf->size) /* 1 */
      pthread_cond_wait(&buf->nofull, &buf->mutex);
    buf->array[buf->in]= cuadro;
    buf->in= (buf->in+1) % buf->size;
    buf->cnt++;
    pthread_cond_signal(&buf->noempty);
    pthread_mutex_unlock(&buf->mutex);
  }
  
  Cuadro *get(Buffer *buf) {
    Cuadro *cuadro;
    pthread_mutex_lock(&buf->mutex);
    while (buf->cnt==0)  /* 2 */
      pthread_cond_wait(&buf->noempty, &buf->mutex);
    cuadro= buf->array[buf->out];
    buf->out= (buf->out+1) % buf->size;
    buf->cnt--;
    pthread_cond_signal(&buf->nofull);
    pthread_mutex_unlock(&buf->mutex);
    return cuadro;
  }
</code>

Esta nueva solución sí usa signal pero tiene una condición para las casillas vacías en el buffer
y otra para las casillas llenas.  Como signal despierta un solo thread es más eficiente porque
gatilla menos cambios de un thread a otro thread.

Hay que destacar que se debe mantener el while de 1 y 2.  Piénselo muy bien si va a usar if antes de llamar a pthread_cond_wait.  En el siguiente diagrama se muestra que el consumidor que espera en A, al despertarse podría //no obtener// el ítem recién depositado, lo que demuestra la importancia de usar while.

{{ :while2.png?500 |}}

En 1 el consumidor A encuentra el buffer vacío y por lo tanto espera llamando a pthread_cond_wait.  En 2, el productor llamó a put para depositar un ítem y obtiene el buffer.  En 3, el consumidor B solicita el buffer para extraer un ítem del buffer, pero hay contención, es decir el buffer está ocupado y por lo tanto espera.  El consumidor B no espera porque llamó a pthread_cond_wait, si no que espera en el pthread_mutex_lock por la propiedad del monitor.  En 4, el productor llama a phthread_cond_signal y despierta al consumidor A, la única tarea que esperaba en la condición noempty.  En este instante tanto el consumidor A como el consumidor B compiten por obtener el buffer.  Cuando en 5, el productor libera el buffer, no está especificado quién obtiene el buffer.  Se eligió que lo obtenga el consumidor B, el que encuentra un ítem en el buffer y lo extrae.  En 6 libera el buffer y ahora sí lo recibe el consumidor A, el que encuentra el buffer vacío y por lo tanto debe llamar nuevamente a pthread_cond_wait.  //De haberse usado if en vez de while en el código de más arriba, el consumidor A hubiese continuado erróneamente con la extracción de un ítem que ya fue extraído por el consumidor B, entregando así basura//.
==== La cena de los filósofos ====

En programación concurrente es muy frecuente plantear problemas usando metáforas que aparentemente
no tienen nada que ver con computación.  Pero no se engañen: estas metáforos sí representan una
amplia gama de problemas prácticos, solo que plantearlos en forma concreta resulta engorroso y requeriría mucho
tiempo.  La metáfora resulta simple de entender.

El más célebre de estos problemas es la cena de los filósofos (en Inglés //dining philosophers//) que
fue planteado por Edsger Dijkstra para explicar los 3 errores más frecuentes en programación
concurrente: data-races, deadlocks y starvation (hambruna).  A veces este problema también es conocido
como el restaurant chino y es la forma en que se planteará en estos apuntes.

El problema consiste en que 5 filósofos comen arroz frecuentemente en un restaurant chino, cuyo dueño es un
sabio chino que adora plantearles problemas desafiantes.  Es por eso que el sabio les reserva una mesa circular
con 5 puestos pero solo coloca 5 palitos en la mesa.  Para poder comer arroz un filósofo necesita tomar
los 2 palitos que están a su izquierda y derecha, pero el de la izquierda debe ser compartido con el
filósofo que se sienta a su izquierda y el de la derecha compartido a su vez con el filósofo de su
derecha. La restricción más importante es que 2 filósofos no pueden comer con el mismo palito al mismo tiempo.

{{ :mesa.png?200 |}}

=== Primera solución incorrecta ===


Veamos primero la solución //incorrecta//.  Cada filósofo es representado por un thread que recibe
como argumento un entero que identifica al filósofo, con valores 0, 1, 2, 3 o 4.  Esta es la función
que ejecuta cada uno de estos 5 threads:

<code>
  void filosofo(int i) {
    for (;;) {
      comer(i, (i+1)%5);
      pensar();
    }
  }
</code>

La función ''comer'' recibe como argumentos las identificaciones de los palitos con que va a comer el
filósofo (de 0 a 4).  Es fácil ver que con esta solución, dado que hay 5 instancias de filosofo ejecutándose,
puede darse que en un momento 2 filósofos estén comiendo con el mismo palito.  Esto es un data-race.

=== Solución trivial ineficiente ===

Una solución simple y correcta, pero ineficiente consiste en usar un único mutex que
asegura la exclusión mutua de los filósofos mientras comen.  Así se evita que 2
filósofos lleguen a comer con el mismo palito:

<code>
  pthread_mutex_t m;
  void filosofo(int i) {
    for (;;) {
      pthread_mutex_lock(&m);
      comer(i, (i+1)%5);
      pthread_mutex_unlock(&m);
      pensar();
    }
  }
</code>

Sin embargo, esta solución es demasiado restrictiva porque en general se puede
lograr que hasta 2 filósofos coman en paralelo sin dataraces.  Eso es lo que
se perseguirá en las soluciones que vienen a continuación.

=== Segunda solución incorrecta ===

La segunda solución (incorrecta) que se viene a la mente es usar 5 mutex para garantizar la exclusión
mutua en el uso de los 5 palitos.  Esto quedaría así:

<code>
  pthread_mutex_t palitos[5];
  
  void filosofo(int i) {
    for (;;) {
      pthread_mutex_lock(&palitos[i]);
      pthread_mutex_lock(&palitos[(i+1)%5]);
      comer(i, (i+1)%5);
      pthread_mutex_unlock(&palitos[i]);
      pthread_mutex_unlock(&palitos[(i+1)%5]);
      pensar();
    }
  }
</code>

Observe que es imprescindible soltar los mutex cuando se está pensando.  Si no se estaría
limitando el parelelismo inútilmente.

Esta solución es incorrecta porque se puede dar que los 5 filósofos reserven el mutex asociado al palito
de su izquierda y se queden indefinidamente esperando reservar el mutex asociado con el palito de su
derecha.  Indefinidamente porque el mutex que esperan nunca será liberado.  Esto se llama
un deadlock (a veces se traduce al español como abrazo mortal).

=== Solución correcta y eficiente ===

La mejor solución a este problema es introducir un orden en los mutex y pedirlos siempre en orden
ascendente.  En este caso los filósofos 0 a 3 piden los mutex en orden ascendente, pero el número
4 lo pide en orden descendente (4 primero y luego el 0).  El siguiente código se asegura
de que el filósofo 4 también pida los mutex en orden ascendente:

<code>
  pthread_mutex_t palitos[5];
  
  void filosofo(int i) {
    for (;;) {
      int m1= min(i, (i+1)%5);
      int m2= max(i, (i+1)%5);
      pthread_mutex_lock(&palitos[m1]);
      pthread_mutex_lock(&palitos[m2]);
      comer(i, (i+1)%5);
      pthread_mutex_unlock(&palitos[i]);
      pthread_mutex_unlock(&palitos[(i+1)%5]);
      pensar();
    }
  }
</code>

Observe que los mutex se pueden devolver en cualquier orden.

El interés de esta solución es que se puede aplicar en el caso más complejo en que
un número variable de threads necesita acceder a varias estructuras de datos compartidas
para poder realizar una transacción.
En ese caso, se introduce un orden en las estructuras de datos y el programa debe
pedir ordenadamente los mutex que protegen cada estructura.  Esto garantiza la ausencia
de deadlock.

=== Hambruna ===

El problema de estas 2 soluciones es que en ocasiones un filósofo puede retener inútilmente el palito a su izquierda
esperando que se libere el palito de su derecha, pero impidiendo que coma el filósofo de su izquierda.
El siguiente diagrama muestra esta ineficiencia:

{{ :palito.png?400 |}}

En a, los filósofos 0, 1 y 2 solicitan con éxito el primero de los palitos que necesitan para comer.  En b solicitan el segundo palito, pero solo el filósofo 2 lo logra.  El filósofo 1 espera porque el palito 2 lo tiene reservado el filósofo 2 y el filósofo 0 espera porque el palito 1 lo tiene reservado el filósofo 1.  En c el filósofo 2 comienza a comer.  El problema es que en esta situación el filósofo 0 podría comer porque el filósofo 1 no está comiendo con el palito 1.  Solo lo tiene reservado.

Para lograr el máximo paralelismo es tentador idear una solución en donde un filósofo pueda empezar
a comer solo cuando ambos palitos están libres, pero si alguno está ocupado, el que está libre sigue libre
para que otro filósofo pueda ocuparlo.  Esto es difícil de lograr solo con mutex, pero sí se puede lograr agregando una condición, como se aprecia
en la siguiente solución:

<code>
  pthread_mutex_t mutex;
  pthread_cond_t cond;
  int palitos[5]= {0, 0, 0, 0, 0}; /* 0 desocupado, 1 ocupado */

  void pedir(int i, int j) {  
    pthread_mutex_lock(&mutex);
    while (palitos[i] || palitos[j])
      pthread_cond_wait(&cond, &mutex); /* uno de los palitos está ocupado */
    palitos[i] = palitos[j] = 1;
    pthread_mutex_unlock(&mutex);
  }
  
  void devolver(int i, int j) {
    pthread_mutex_lock(&mutex);
    palitos[i] = palitos[j] = 0;
    pthread_cond_broadcast(&cond);
    pthread_mutex_unlock(&mutex);
  }

  void filosofo(int i) {
    for (;;) {
      pedir(i (i+1)%5);
      comer(i, (i+1)%5);
      devolver(i (i+1)%5);

      pensar();
    }
  }
</code>

Esta solución no sufre de dataraces ni de deadlock pero tiene un defecto: hambruna (en Inglés starvation).
Esto se demuestra en el siguiente diagrama:

{{ :hambruna.png?400 |}}

En a, el filósofo 0 obtiene los palitos 0 y 1.  En b, el filósofo 1 solicita los palitos 1 y 2, pero no obtiene ninguno de los 2 porque el palito 1 está ocupado.  En c, el filósofo 2 obtiene los palitos 2 y 3, justo antes de que el filósofo 0 libere en d los palitos 0 y 1.  Entonces, el filósofo 1 se despierta y ve que el palito 1 está libre, pero esta vez es el palito 2 el que está ocupado de modo que continúa esperando.  En e, el filósofo 0 le da hambre nuevamente y quiere comer.  Obtiene los palitos 0 y 1, justo antes de que el filósofo esté satisfecho y devuelva en f los palitos 2 y 3.  Nuevamente se despierta el filósofo 1 para descubrir que el palito 1 está libre pero no el palito 0, y continúa esperando.  Y así cada vez que se despierta el filósofo 1 descubre que uno de los palitos está ocupado porque siempre habrá un filósofo que comience a comer justo antes de que el otro libere sus palitos.  De esta forma, el filósofo 1 se morirá de hambre.

Cuando una solución se programa de tal forma que ningún thread puede sufrir hambruna se dice en Inglés que la solución es //fair//, o que posee //fairness// como atributo.  Se acepta traducir al español este término señalando que una solución es justa o equitativa, pero es una mala traducción porque en ningún caso significa que los threads tengan la misma probabilidad de que su solicitud sea satisfecha.  El significado de fairness es menos exigente: una solicitud será satisfecha tarde o temprano, pero mientras para un thread podría ser temprano, para otro podría ser tarde.

Observe que la hambruna es distinta de un deadlock porque afecta a un solo thread (en algunos casos un subconjunto de threads).  En el caso del deadlock, todos los filósofos se mueren de hambre, pero porque todos esperan que otro filósofo libere el palito que necesitan, aunque esto nunca ocurrirá.

La situación de hambruna se da en muchas soluciones y se considera un aspecto negativo, pero a veces se acepta porque evitarla puede ser complejo.  En este caso se aplica un principio
de diseño que se denomina //worse is better// o peor es mejor.  La complejidad añadida en
tratar de obtener una solución que
evite la hambruna pero maximice el paralelismo puede llevar al fracaso de la aplicación.  En este curso se explicitará en el enunciado de los controles o tareas cuando se debe evitar la hambruna.  Si el enunciado no dice nada, su solución sí puede sufrir de hambruna.

En todo caso, lo usual es no dar prioridad a la eficiencia y por lo tanto concluiremos
que la primera solución correcta que se entregó más arriba es la mejor solución, y no sufre de hambruna.

==== Lectores/escritores ====

El último problema de sincronización famoso se da cuando se requiere acceso paralelo al
consultar una estructura de datos compartida, pero acceso exclusivo cuando se modifica.

Consideremos por ejemplo el caso de un diccionario con las operaciones definir, consultar
y eliminar.  Los threads que consultan el diccionario pueden hacerlo en paralelo.  Estos
threads se denominan //lectores//.  Por otro lado un thread que define o elimina se llama
un //escritor// y debe operar en exclusión mutua con cualquier otro thread que requiera el diccionario
sea lector o escritor.

La implementación trivial consiste en usar un mutex para garantizar exclusión mutua al operar
con el diccionario.  Esta implementación es correcta pero ineficiente porque los lectores
no operan en paralelo.

A continuación veremos una estrategia para resolver cualquier tipo
de problema en donde se pueden idenficar lectores y escritores, no solo el caso del diccionario.
Pero para aterrizar la solución usaremos como referencia el caso del diccionario.  Por simplicidad
supondremos que existe un único diccionario y por lo tanto se usarán variables globales.

La idea es que los lectores anuncian su entrada con enterRead() antes de iniciar una consulta
del diccionario y con exitRead() después de terminarla.  Del mismo modo los escritores anuncian
su entrada con enterWrite() antes de iniciar una definición o eliminación y con exitWrite después
de concluirla:

<code>
  void definir(char *k, char *v) {
    enterWrite();
    ... implementación ...
    exitWrite();
  }

  char *consultar(char *k) {
    enterRead();
    ... implementación ...
    exitRead();
    return ...
  }
  
  void eliminar(char *k) {
    enterWrite();
    ... implementación ...
    exitWrite();
  }
</code>

Las funciones enterRead, exitRead, enterWrite y exitWrite no realizan trabajo útil.  Están ahí
solo para efectos de sincronización.  Cuando enterRead detecta que hay un escritor modificando
el diccionario, entonces no retorna hasta que sea factible entrar.  De la misma forma, enterWrite
no retorna hasta que no hayan lectores o escritores dentro del diccionario.
Entonces el problema de sincronización se reduce a programar las funciones enterRead, exitRead,
enterWrite y exitWrite.

=== Primera solución ===

Esta solución es la más simple pero veremos que adolece de hambruna.  Se usará un monitor.

<code>
  pthread_mutex_t mutex;
  pthread_cond_t cond;
  int readers= 0;
  int writing= FALSE;
  
  void enterRead() {
    pthread_mutex_lock(&mutex);
    while (writing)
      pthread_cond_wait(&cond, &mutex);
    readers++;
    pthread_mutex_unlock(&mutex);
  }
  
  void exitRead() {
    pthread_mutex_lock(&mutex);
    readers--;
    if (readers==0)
      pthread_cond_broadcast(&cond);
    pthread_mutex_unlock(&mutex);
  }
  
  void enterWrite() {
    pthread_mutex_lock(&mutex);
    while (readers>0 || writing)
      pthread_cond_wait(&cond, &mutex);
    writing= TRUE;
    pthread_mutex_unlock(&mutex);
  }
  
  void exitWrite() {
    pthread_mutex_lock(&mutex);
    writing= FALSE;
    pthread_cond_broadcast(&cond);
    pthread_mutex_unlock(&mutex);
  }
</code>

Observe que al usar un monitor estas operaciones de sincronización se ejecutan en exclusión
mutua.  No habrá paralelismo al ejecutar enterRead por ejemplo, aún cuando se trata de un
lector.  Pero se supone que el tiempo de ejecución de enterRead y exitRead es marginal.
Lo importante es lograr que haya paralelismo para el código que se encuentra entre las
llamadas a enterRead y exitWrite en la operación de consulta.

El problema de esta solución es que los lectores se pueden concertar para entrar y
salir alternadamente, impidiendo que un escritor pueda modificar el diccionario, cayendo
así en //hambruna//.  En sistemas operativos se verán soluciones de los lectores/escritores
que evitan la hambruna.


==== El patrón de uso de monitores ====

La mayoría de los problemas de sincronización se resuelven usando el siguiente patrón:

<code>
pthread_mutex_lock(&m);
while ( … )
  pthread_cond_wait(&c, &m);    /* A */
  … consulta/actualización de la sincronización …
  pthread_cond_broadcast(&m);   /* B */
pthread_mutex_unlock(&m);
</code>

Según el problema podría no ser necesario A o B.

==== Ejercicios ====

  * Pregunta 1 del [[http://users.dcc.uchile.cl/~lmateu/CC3301/controles/c3-122.pdf|control 3 de 2012/2]].  En esta pregunta tiene que agregar las llamadas que piden el mutex, esperan, notifican y devuelven el mutex para el caso de un hombre y programar el caso de una mujer.
  * Pregunta 1 del [[http://users.dcc.uchile.cl/~lmateu/CC3301/controles/ex-131.pdf|examen de 2013/1]].  Pruebe su solución con el archivo [[http://users.dcc.uchile.cl/~lmateu/CC3301/download/parking.zip|parking.zip]].  Siga las instrucciones que se indican en el archivo Makefile.
  * Pregunta 1 del [[http://users.dcc.uchile.cl/~lmateu/CC3301/controles/c2-141.pdf|control 2 de 2014/1]].  Pruebe su solución con el archivo [[http://users.dcc.uchile.cl/~lmateu/CC3301/download/integral.zip|integral.zip]].  Siga las instrucciones que se indican en el archivo Makefile.  Esta pregunta es corta pero tiene su dificultad conceptual.  Cubre tanto la materia de punteros a funciones como paralelización usando threads.
  * Pregunta 2 del [[http://users.dcc.uchile.cl/~lmateu/CC3301/controles/ex-122.pdf|examen de 2012/2]].