Diferencias

Muestra las diferencias entre dos versiones de la página.

--- threads [2018/06/26 13:53] – [La cena de los filósofos] lmateu
+++ threads [2018/07/06 00:04] (actual) – [Productor/consumidor] lmateu
@@ Línea 359: / Línea 359: @@
   }
-  void consumidor(Buffer *buf) {
+  void *consumidor(void *ptr) { // porque se usa en pthread_create
+    Buffer *buf= ptr;
     for (;;) {
       Cuadro *cuadro= get(buf);
@@ Línea 366: / Línea 367: @@
       mostrarCuadro(cuadro);
     }
+    return NULL;
   }
   void reproducirVideo() {
     Buffer *buf= nuevoBuffer(60);
-    pthread_pid_t pid;
+    pthread_t t;
-    pthread_create(&pid, NULL, (void *(*)(void *))consumidor, (void*)buf);
+    pthread_create(&t, NULL, consumidor, buf);
     productor(buf);
-    pthread_join(pid, NULL);
+    pthread_join(t, NULL);
   }
 </code>
@@ Línea 912: / Línea 914: @@
 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//.
+así en //hambruna//.  En sistemas operativos se verán soluciones de los lectores/escritores
+que evitan la hambruna.
-=== Segunda solución ===
-Esta solución evita la hambruna por medio de la metáfora de la isapre.  Como en una
-isapre los threads deben pedir un número antes de realizar su operación.  Un thread
-solo puede entrar a realizar su operación cuando el número que aparece en un visor
-coincide con el número que se le asignó.  De esta forma las entradas
-se satisfacen en orden FIFO (//first in first out//), aunque las lecturas se hacen
-en paralelo y por lo tanto las salidas pueden ocurrir en un orden no FIFO.
-En esta solución los lectores no pueden concertarse para causar hambruna a un escritor
-porque una vez que el escritor recibe su número, ningún otro lector podrá entrar
-al diccionario.  Tarde o temprano los lectores que habían entrado previamente tendrán
-que salir y será el turno del escritor.
-<code>
-  pthread_mutex_t mutex;
-  pthread_cond_t cond;
-  int readers= 0;
-  int display= 0;
-  int serial= 0;
-  void enterRead() {
-    int myNum;
-    pthread_mutex_lock(&mutex);
-    myNum= = serial++;
-    while (myNum!=display)
-      pthread_cond_wait(&cond, &mutex);
-    readers++;
-    display++;
-    pthread_cond_broadcast(&cond); /* Ver nota */
-    pthread_mutex_unlock(&mutex);
-  }
-  void exitRead() {
-    pthread_mutex_lock(&mutex);
-    readers--;
-    if (readers==0)
-      pthread_cond_broadcast(&cond);
-    pthread_mutex_unlock(&mutex);
-  }
-  void enterWrite() {
-    int myNum;
-    pthread_mutex_lock(&mutex);
-    myNum= serial++;
-    while (readers>0 || myNum!=display)
-      pthread_cond_wait(&cond, &mutex);
-    pthread_mutex_unlock(&mutex);
-  }
-  void exitWrite() {
-    pthread_mutex_lock(&mutex);
-    display++;
-    pthread_cond_broadcast(&cond);
-    pthread_mutex_unlock(&mutex);
-  }
-</code>
-Nota: el broadcast se necesita acá porque el incremento de display podría gatillar
-que un lector que se encontraba esperando ahora puede entrar.
-//**Discusión**//: Esta solución funciona pero puede ser muy ineficiente.  El problema es el siguiente.
-Supongamos que hay un escritor trabajando y n lectores esperando.  Cuando el escritor se va, en el peor
-caso se pueden requerir hasta O(n^2) cambios de thread a thread para que todos los lectores comiencen
-a trabajar.  Esto es muy ineficiente.  Esto se puede bajar a O(n) usando múltiples variables de condición.
-==== Equivalencia entre herramientas de sincronización ====
-Los semáforos y monitores (mutex + condición) son equivalentes, en el sentido que si un
-problema se puede resolver con una herramienta, entonces también se puede resolver con la otra
-herramienta.  La única excepción la constituye el timeout de //pthread_cond_timedwait//
-que no se puede implementar con las semáforos por sí solos.
-Probaremos la equivalencia implementando un semáforo a partir de un monitor y un monitor
-a partir de un semáforo.  Esto le ayudará a comprender el significado de ambas herramientas.
-=== Semáforo implementado con monitores ===
-<code>
-  #include <pthread.h>
-  typedef struct {
-    int tickets;
-    pthread_cond_t vacio; /* Condicion para esperar entrar al semáforo */
-    pthread_mutex_t mutex;
-  } Semaphore;
-  void sema_init(Semaphore *sema, int ini) {
-    sema->tickets = ini;
-    pthread_cond_init(&sema->vacio, NULL);
-    pthread_mutex_init(&sema->mutex, NULL);
-  }
-  void sema_wait(Semaphore *sema) {
-    pthread_mutex_lock(&sema->mutex);
-    while (sema->tickets == 0) /* Nunca un if! */
-      pthread_cond_wait(&sema->vacio, &sema->mutex);
-    sema->tickets--;
-    pthread_mutex_unlock(&sema->mutex);
-  }
-  void sema_post(Semaphore *sema) {
-      pthread_mutex_lock(&sema->mutex);
-      sema->tickets++;
-      pthread_cond_signal(&sema->vacio); /* siempre libero a uno solo */
-      pthread_mutex_unlock(&sema->mutex);
-  }
-</code>
-Observe que se uso signal en vez de broadcast.  Esto se puede hacer porque hay un solo
-tipo de threads esperando: threads que esperan obtener un ticket.  Por lo tanto basta
-una sola condición.  En el problema del buffer hay 2 tipos de threads en espera: los
-que esperan extraer un ítem del buffer y los que esperan depositar un ítem.  Por ello
-se necesitan 2 condiciones, o alternativamente si se usa una sola condición usar
-broadcast en vez de signal.
-=== Ejercicio ===
-El problema de la implementación de más arriba es que un thread T que se despierta
-después de un sem_wait no necesariamente obtiene el ticket recién depositado
-con sem_post.  Como T todavía tiene que esperar por la propiedad del mutex, puede
-ocurrir que llega un nuevo thread U que invoca sem_wait y le roba el mutex a T.
-El resultado es que U obtiene el ticket a pesar de que T lleva mucho más tiempo
-esperándolo.
-Modifique su implementación de modo que se garantice que el thread T reciba el ticket.
-Base su implementanción en la metáfora de la Isapre: para evitar las colas hay un
-distribuidor de números en la entrada y un visor que indica a quién se atiende
-actualmente.  De la misma forma, haga que el que invoca sem_wait obtenga un número
-y espera hasta que el visor indique al menos ese número.
-=== Monitores a partir de semáforos ===
-La siguiente es una implementación de un verdadero monitor, el que fusiona el mutex
-con la condición, a la manera de los monitores de Java.
-<code>
-  #include <pthread.h>
-  #include <semaphore.h>
-  typedef struct node {
-    sem_t wait;
-    struct node *next;
-  } Node;
-  typedef struct {
-    sem_t mutex;
-    Node *head;
-  } Monitor;
-  void mon_init(Monitor *mon) {
-    sem_init(&mon->mutex, 0, 1);
-    mon->head= NULL;
-  }
-  void mon_lock(Monitor *mon) {
-    sem_wait(&mon->mutex);
-  }
-  void mon_unlock(Monitor *mon) {
-    sem_post(&mon->mutex);
-  }
-  void mon_wait(Monitor *mon) {
-    Node node;
-    sem_init(&node.wait, 0, 0);
-    node.next= mon->head;
-    mon->head= &node;
-    sem_post(&mon->mutex);
-    sem_wait(&node.wait);   /* se bloquea a la espera del broadcast */
-    sem_destroy(&node.wait);
-    sem_wait(&mon->mutex);  /* se bloquea a la espera del monitor */
-  }
-  void mon_broadcast(Monitor *mon) {
-    Node *node;
-    for (node= mon->head; node!=NULL; node= node->next)
-      sem_post(&node->wait);
-    mon->head= NULL;
-  }
-</code>
-Este código no efectúa ninguna validación con respecto al buen uso de los monitores,
-es decir que las operaciones mon_unlock, mon_wait y mon_broadcast solo se invoquen
-cuando se obtuvo previamente el monitor con mon_lock.
-=== Ejercicio ===
-Implemente a partir de semáforos un monitor con múltiples condiciones, a la manera
-de los mutex y condiciones de pthreads.