Diferencias

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

--- threads-opt [2018/06/26 13:54] – lmateu
+++ threads-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
 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.