Wiki CC3301

Herramientas de usuario

Herramientas del sitio

Estás aquí: start » threads-opt
Traza: • tipos • bits • shell • threads-opt
threads-opt

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-opt [2018/06/26 13:54] – lmateuthreads-opt [2018/06/26 13:57] (actual) – [Equivalencia entre herramientas de sincronización] lmateu
Línea 218: Línea 218:
 Implemente a partir de semáforos un monitor con múltiples condiciones, a la manera Implemente a partir de semáforos un monitor con múltiples condiciones, a la manera
 de los mutex y condiciones de pthreads. de los mutex y condiciones de pthreads.
 +
 +
 +=== Solución lectores/escritores sin hambruna ===
 +
 +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.
 +
  
threads-opt.1530021265.txt.gz · Última modificación: por lmateu