Wiki CC3301

Herramientas de usuario

Herramientas del sitio

Estás aquí: start » threads
Traza: • unix-es • threads
threads

Diferencias

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

Enlace a la vista de comparación

Ambos lados, revisión anteriorRevisión previa
Próxima revisión		Revisión previa
threads [2014/09/24 22:33] – [Ejercicios] lmateuthreads [2018/07/06 00:04] (actual) – [Productor/consumidor] lmateu
Línea 115: Línea 115:
 </code> </code>
  
-La tipo Args se crea para poder pasar varios argumentos al thread, albergar el pid del thread+El tipo Args se crea para poder pasar varios argumentos al thread, albergar el pid del thread
 y retornar el resultado final. y retornar el resultado final.
  
Línea 193: Línea 193:
 Suponga que un banco atiende una infinidad de clientes que compran en el comercio con 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 la tarjeta redcompra.  Se necesita un programa que autorice las compras si el saldo
-es suficiente o la rechaze si es insuficiente.  El problema es que comunicarse con+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 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. se decidió utilizar múltiples threads para comunicarse con los terminales de redcompra.
Línea 257: Línea 257:
 ==== Mutex ==== ==== Mutex ====
  
-Los sistemas de threads ofreces diversas herramientas de sincronización.  Una de ellas+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 son los mutex que sirven específicamente para garantizar la exclusión mutua.  Un mutex
 se manipula con las siguientes funciones: se manipula con las siguientes funciones:
Línea 318: Línea 318:
 ==== Productor/consumidor ==== ==== Productor/consumidor ====
  
-El siguiente programa lee de Internet un video y lo muestre en pantalla:+El siguiente programa lee de Internet un video y lo muestra en pantalla:
  
 <code> <code>
Línea 359: Línea 359:
   }   }
      
-  void consumidor(Buffer *buf) {+  void *consumidor(void *ptr) { // porque se usa en pthread_create 
 +    Buffer *buf= ptr;
     for (;;) {     for (;;) {
       Cuadro *cuadro= get(buf);       Cuadro *cuadro= get(buf);
Línea 366: Línea 367:
       mostrarCuadro(cuadro);       mostrarCuadro(cuadro);
     }     }
 +    return NULL;
   }   }
      
   void reproducirVideo() {   void reproducirVideo() {
     Buffer *buf= nuevoBuffer(60);     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);     productor(buf);
-    pthread_join(pid, NULL);+    pthread_join(t, NULL);
   }   }
 </code> </code>
Línea 418: Línea 420:
 más energía de la necesaria y acelerando así el consumo de la batería de un notebook. más energía de la necesaria y acelerando así el consumo de la batería de un notebook.
  
-==== Semáforos ==== 
- 
-Un semáforo es un contenedor de tickets.  En él se pueden depositar un ticket con sem_post y 
-extraer un ticket con sem_wait.  La garantía es que si sem_wait no encuentra tickets entonces no 
-retorna hasta que algún thread invoque sem_post para depositar un ticket. 
- 
-Un semáforo se manipula con las siguientes funciones: 
- 
-<code> 
-  #include <semaphore.h> 
-  sem_t sem; 
-  sem_init(&sem, 0, tickets_iniciales); 
-  sem_post(&sem); 
-  sem_wait(&sem); 
-</code> 
- 
-La siguiente es una implementación correcta de la estructura Buffer del productor/consumidor. 
- 
-<code> 
-  /* Versión correcta */ 
-  typedef struct { 
-    int size; 
-    Cuadro **array; 
-    int in, out; 
-    sem_t empty, full; 
-  } 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= 0; 
-    sem_init(&buf->empty, 0, size); 
-    sem_init(&buf->full, 0, 0); 
-    return buf; 
-  } 
-   
-  void put(Buffer *buf, Cuadro *cuadro) { 
-    sem_wait(&buf->empty); 
-    buf->array[buf->in]= cuadro; 
-    buf->in= (buf->in+1) % buf->size; 
-    sem_post(&buf->full); 
-  } 
-   
-  Cuadro *get(Buffer *buf) { 
-    Cuadro *cuadro; 
-    sem_wait(&buf->full); 
-    cuadro= buf->array[buf->out]; 
-    buf->out= (buf->out+1) % buf->size; 
-    sem_post(&buf->empty); 
-    return cuadro; 
-  } 
-</code> 
- 
-=== Ejercicio: múltiples productores y múltiples consumidores === 
- 
-Hay muchos problemas que se pueden paralelizar usando la abstracción productor/consumidor. 
-En ellos la solución es la misma de arriba.  Solo cambia el código del productor, del consumidor 
-y los ítemes que se depositan en el Buffer.  Pero el código del buffer es el mismo. 
  
-El problema del productor/consumidor se puede generalizar a múltiples productores y 
-múltiples consumidores que comparten el mismo buffer.  Muestre que en este caso el 
-código para depositar y extraer elementos de buffer puede sufrir de data-races. 
-Corrija el código usando un semáforo o mutex adicional. 
  
 ==== Monitores ==== ==== Monitores ====
Línea 774: Línea 713:
 un deadlock (a veces se traduce al español como abrazo mortal). un deadlock (a veces se traduce al español como abrazo mortal).
  
-=== Primera solución correcta y eficiente ===+=== Solución correcta y eficiente ===
  
 La mejor solución a este problema es introducir un orden en los mutex y pedirlos siempre en orden La mejor solución a este problema es introducir un orden en los mutex y pedirlos siempre en orden
Línea 806: Línea 745:
 pedir ordenadamente los mutex que protegen cada estructura.  Esto garantiza la ausencia pedir ordenadamente los mutex que protegen cada estructura.  Esto garantiza la ausencia
 de deadlock. de deadlock.
- 
-=== Segunda solución correcta y eficiente === 
- 
-La segunda solución se basa en que el deadlock solo se produce si los 5 filósofos llegan a cenar. 
-Si se limita a 4 los filósofos que pueden cenar, ya no habrá deadlock.  Entonces se usa un semáforo 
-con 4 tickets iniciales: 
- 
-<code> 
-  pthread_mutex_t palitos[5]; 
-  sem_t portero; /* con 4 tickets iniciales */ 
-   
-  void filosofo(int i) { 
-    for (;;) { 
-      sem_wait(&portero); 
-      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]); 
-      sem_post(&portero); 
-      pensar(); 
-    } 
-  } 
-</code> 
- 
-El problema de esta solución es que solo se aplica a 5 filósofos y 5 palitos.  No se puede 
-generalizar a un número variable de threads accediendo a múltiples estructuras 
-de datos. 
  
 === Hambruna === === Hambruna ===
Línea 847: Línea 758:
 Para lograr el máximo paralelismo es tentador idear una solución en donde un filósofo pueda empezar 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 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 con semáforos porque no existe un mecanismo para pedir un semáforo pero no bloquearse si el semáforo no tiene tickets.  Sin embargo esto sí se puede lograr de manera sencilla con monitores, como se aprecia+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: en la siguiente solución:
  
Línea 948: Línea 859:
 Las funciones enterRead, exitRead, enterWrite y exitWrite no realizan trabajo útil.  Están ahí 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 solo para efectos de sincronización.  Cuando enterRead detecta que hay un escritor modificando
-el diccionario, entonces no retorna hasta sea factible entrar.  De la misma forma, enterWrite+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. 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, Entonces el problema de sincronización se reduce a programar las funciones enterRead, exitRead,
Línea 1003: Línea 914:
 El problema de esta solución es que los lectores se pueden concertar para entrar y 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 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.+
  
  
Línea 1217: Línea 937:
   * 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/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/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]].   * Pregunta 2 del [[http://users.dcc.uchile.cl/~lmateu/CC3301/controles/ex-122.pdf|examen de 2012/2]].
threads.1411598015.txt.gz · Última modificación: por lmateu