Lectores–escritores

Problema: los lectores pueden leer en paralelo; los escritores necesitan acceso exclusivo. Queremos paralelismo y ausencia de starvation.

🎯 Al terminar podrás

1. Explicar el patrón lightswitch (el primero cierra, el último abre) y por qué deja a los escritores con starvation.
2. Decir por qué la versión con mutex falla (el mutex tiene dueño).
3. Leer una solución con lock + condition variables y decir a quién favorece mirando la condición del while de cada uno.
4. Proponer una versión con prioridad a escritores (o justa) y su costo.

Antes necesitas: Monitores

• Simulador predice el estado antes de pulsar el paso siguiente
• Detective escribe tu hipótesis del bug antes de abrir el diagnóstico
• Debate elige una alternativa para el escenario y defiéndela

Solución 0: un solo semáforo (r-w-sequential.c)

Semaphore sem_data = 1;
Reader: wait(sem_data); read_data();  signal(sem_data);
Writer: wait(sem_data); write_data(); signal(sem_data);

Es correcta pero secuencial: dos lectores no pueden leer a la vez. Se pierde el paralelismo.

Solución 1: varios lectores con un contador (r-w-starvation.c)

Semaphore sem_data = 1, sem_nr = 1;  int nr = 0;
Reader:
    wait(sem_nr);  nr++; if (nr == 1) wait(sem_data);  signal(sem_nr);   // el primero cierra
    read_data();
    wait(sem_nr);  nr--; if (nr == 0) signal(sem_data); signal(sem_nr);  // el último abre
Writer: wait(sem_data); write_data(); signal(sem_data);

Es el patrón lightswitch. Hay paralelismo entre lectores, pero los escritores pueden sufrir starvation: si siempre hay algún lector dentro, nr nunca llega a 0.

Solución 2: lo mismo con mutex, y por qué falla

Si se reemplazan los semáforos por mutex_lock y mutex_unlock, el lector que bloquea lock_data (el primero) puede no ser el que lo desbloquea (el último). Un mutex tiene dueño, así que desbloquearlo desde otro hilo es comportamiento indefinido. Es el problema señalado en la diapositiva 19.

Solución 3: lock + condition variables (r-w-broadcast.c)

mutex_t lock_cont; int nr = 0, nw = 0; cond_t cond_rd, cond_wr;

Reader:
    mutex_lock(&lock_cont);
    while (nw > 0) cond_wait(&cond_rd, &lock_cont);
    nr++;
    mutex_unlock(&lock_cont);
    read_data();
    mutex_lock(&lock_cont);
    nr--;
    if (nr == 0) cond_signal(&cond_wr);
    mutex_unlock(&lock_cont);

Writer:
    mutex_lock(&lock_cont);
    while (nr > 0 || nw > 0) cond_wait(&cond_wr, &lock_cont);
    nw++;
    mutex_unlock(&lock_cont);
    write_data();
    mutex_lock(&lock_cont);
    nw--;
    cond_signal(&cond_wr);
    cond_broadcast(&cond_rd);
    mutex_unlock(&lock_cont);

• Los datos se leen y escriben fuera del lock. El lock solo protege los contadores, y por eso hay paralelismo real entre lectores.
• Sigue favoreciendo a los lectores: un lector entra si nw == 0, aunque haya escritores esperando.

🔮 Predice antes de seguir

En la solución 3, un escritor está esperando porque hay 2 lectores dentro. Llega un tercer lector. ¿Entra o espera? ¿Qué parte del código lo decide?

Ya tengo mi respuesta: comparar

Entra. El lector solo espera mientras nw > 0 (escritores activos), y el escritor que espera todavía no incrementó nw. Mientras sigan llegando lectores, nr nunca baja a 0 y el escritor puede esperar indefinidamente: starvation de escritores. Para dar prioridad a los escritores, el lector también debe esperar si hay escritores esperando (un contador ww), como en r-w-sol-example.c.

Simulador

Monitor lectores–escritores

Agrega hilos. Clic en un hilo activo para que salga. En modo Mesa, los despertados quedan en listo: haz clic para que readquieran el lock y re-evalúen su while.

Mesa (pthreads)Hoare

Preferencia lectores (diap. 21–22)Preferencia escritores

+ Lector+ EscritorReiniciar

Esperando en cond_rd / cond_wr

Listos (despertados, sin el lock)

Dentro (datos compartidos)

nr (lectores activos)0

nw (escritores activos)0

escritores esperando0

lectores que adelantaron a un escritor0

Prueba: +Lector, +Escritor, +Lector, +Lector… con preferencia de lectores, el escritor puede esperar para siempre.

Prueba: +Escritor, +Lector (espera), luego saca al escritor. En modo Mesa, el lector queda listo. Antes de hacer clic en él, agrega +Escritor varias veces: con preferencia de escritores, el lector re-evalúa su while, ve escritores y vuelve a dormir.

La solución de la Sem05: AR / WR / AW / WW (prioridad a escritores)

Restricciones: los lectores entran cuando no hay escritores, los escritores cuando no hay lectores ni escritores, y un solo hilo manipula las variables de estado a la vez (con lock).

int AR = 0, WR = 0, AW = 0, WW = 0;      // lectores activos/esperando, escritores activos/esperando
Condition okToRead, okToWrite;

Reader() {                                Writer() {
    lock.Acquire();                           lock.Acquire();
    while ((AW + WW) > 0) {  // ¿seguro?      while ((AW + AR) > 0) {   // ¿seguro?
        WR++;                                     WW++;
        okToRead.wait(&lock);                     okToWrite.wait(&lock);
        WR--;                                     WW--;
    }                                         }
    AR++;                                     AW++;
    lock.Release();                           lock.Release();
    AccessDatabase(ReadOnly);                 AccessDatabase(ReadWrite);
    lock.Acquire();                           lock.Acquire();
    AR--;                                     AW--;
    if (AR == 0 && WW > 0)                    if (WW > 0) okToWrite.signal();      // prioridad a escritores
        okToWrite.signal();                   else if (WR > 0) okToRead.broadcast(); // todos los lectores
    lock.Release();                           lock.Release();
}                                         }

Simulación de la diapositiva: llegan R1, R2, W1 y R3.

Evento	AR	WR	AW	WW	Qué pasa
R1 llega	1	0	0	0	AW + WW = 0, así que entra
R2 llega	2	0	0	0	entra: R1 y R2 leen en paralelo
W1 llega	2	0	0	1	AW + AR = 2 > 0, así que duerme en okToWrite
R3 llega	2	1	0	1	WW = 1, así que R3 también espera, aunque no haya ningún escritor activo
R1 sale	1	1	0	1	AR ≠ 0, así que no señala a nadie
R2 sale	0	1	0	1	AR == 0 y WW > 0, así que hace okToWrite.signal()
W1 escribe	0	1	1	0	sale del while: WW— y AW++
W1 sale	0	1	0	0	WW == 0 y WR > 0, así que hace okToRead.broadcast()
R3 lee y sale	0	0	0	0	todo inactivo

Preguntas de la diapositiva, respondidas

• ¿Por qué se libera el lock antes de AccessDatabase? Porque el lock protege las variables de estado, no los datos. Si se tuviera durante una lectura larga, no habría paralelismo entre lectores y todo quedaría serializado.
• ¿Por qué dar prioridad a los escritores? Para que no sufran starvation y los lectores vean datos actualizados. Un escritor que espera impide que entren lectores nuevos (el WW > 0 en la condición del lector).
• ¿Por qué broadcast a los lectores y no signal? Porque todos los lectores que esperan pueden entrar a la vez; con signal solo entraría uno.
• ¿Pueden los lectores sufrir starvation? Sí: si siempre hay escritores esperando o llegando, (AW + WW) > 0 nunca se hace falso.
• ¿Qué pasa si se quita la condición al salir el lector (siempre okToWrite.signal())? Sigue siendo correcto, gracias al while de Mesa: el escritor despertado revisa (AW + AR) > 0 y, si aún hay lectores, vuelve a dormir. Solo se pierde eficiencia con despertares inútiles.
• ¿Y si ese signal se cambia por broadcast? También es correcto: despiertan todos los escritores, uno entra y el resto vuelve a dormir. Es menos eficiente (thundering herd).
• ¿Y con una sola condition variable okContinue para todos? Obliga a usar broadcast. Con signal se podría despertar a quien no corresponde (un lector cuando debía pasar un escritor): ese lector vuelve a dormir y el escritor nunca recibe su señal, lo que produce un deadlock por wake-up perdido. Con broadcast es correcto, pero caro.

Prioridad a escritores (evitar su starvation)

Ver versión con prioridad a escritores (es la de r-w-sol-example.c del curso)

int nr = 0, nw = 0, ww = 0;   // ww = escritores esperando

Reader:
    lock(&m);
    while (nw > 0 || ww > 0) cond_wait(&cond_rd, &m);   // cede ante escritores que esperan
    nr++;
    unlock(&m);
    read_data();
    lock(&m);
    if (--nr == 0 && ww > 0) cond_signal(&cond_wr);
    unlock(&m);

Writer:
    lock(&m);
    ww++;
    while (nr > 0 || nw > 0) cond_wait(&cond_wr, &m);
    ww--; nw++;
    unlock(&m);
    write_data();
    lock(&m);
    nw--;
    if (ww > 0) cond_signal(&cond_wr);    // primero otro escritor
    else        cond_broadcast(&cond_rd); // si no, todos los lectores
    unlock(&m);

El r-w-sol-example.c de clase implementa exactamente esto como un struct rw_monitor con begin_read, end_read, begin_write y end_write (contadores active_readers, active_writers y waiting_writers). Ahora los lectores pueden sufrir starvation si llegan escritores sin parar. La versión justa alterna turnos, con un turn o lotes por fase, igual que en el baño unisex.

Stallings con semáforos: fig. 5.25 (lectores) y 5.26 (escritores)

La fig. 5.25 es la solución 1 de arriba (x protege readcount y wsem es el lightswitch). Allí los escritores pueden sufrir starvation.

Fig. 5.26, prioridad a escritores: agrega writecount, y (que protege a writecount), rsem (bloquea a todos los lectores mientras haya un escritor que quiera entrar) y z.

int readcount, writecount; semaphore x = 1, y = 1, z = 1, wsem = 1, rsem = 1;

void reader() {                               void writer() {
  while (true) {                                while (true) {
    semWait(z);                                   semWait(y);
      semWait(rsem);                                writecount++;
        semWait(x);                                 if (writecount == 1) semWait(rsem); // primer escritor cierra a los lectores
          readcount++;                            semSignal(y);
          if (readcount == 1) semWait(wsem);      semWait(wsem);
        semSignal(x);                             WRITEUNIT();
      semSignal(rsem);                            semSignal(wsem);
    semSignal(z);                                 semWait(y);
    READUNIT();                                     writecount--;
    semWait(x);                                     if (writecount == 0) semSignal(rsem); // último escritor reabre
      readcount--;                                semSignal(y);
      if (readcount == 0) semSignal(wsem);      }
    semSignal(x);                             }
  }
}

¿Para qué sirve z? Hace que solo un lector a la vez espere en rsem; los demás se encolan en z. Así, cuando llega un escritor y hace semWait(rsem), compite con un lector como máximo y no con una fila entera. Los escritores «se saltan la fila» de lectores.

Conclusión: ninguna de las dos políticas elimina la starvation de ambos lados. Para eso hace falta una disciplina adicional, como una cola FIFO común o un torniquete (ver la solución de la diapositiva 25).

La «solución ejemplo» de la diapositiva 25

Reader:                                Writer:
mutex_lock(&lock_data);                mutex_lock(&lock_data);      // turnstile
  mutex_lock(&lock_nr); nr++;            mutex_lock(&lock_nr);
  mutex_unlock(&lock_nr);                while (nr > 0) cond_wait(&cond, &lock_nr);
mutex_unlock(&lock_data);                mutex_unlock(&lock_nr);
read_data();                           write_data();
mutex_lock(&lock_nr); nr--;            mutex_unlock(&lock_data);
if (nr == 0) cond_signal(&cond);
mutex_unlock(&lock_nr);

lock_data actúa como torniquete. Un escritor que llega lo toma y no lo suelta hasta terminar, así que los lectores nuevos se quedan en la puerta y los que ya estaban dentro terminan (nr → 0). Con eso se evita la starvation de escritores sin contadores extra, y los lectores siguen leyendo en paralelo entre escrituras.

🔮 Debate: ¿a quién le das prioridad?

Elige prioridad a lectores, a escritores o turnos justos para: (1) un catálogo de productos que se lee miles de veces por segundo y se actualiza una vez al día; (2) un sistema de precios de bolsa que se actualiza todo el tiempo y no puede mostrar precios viejos.

Ya tengo mi respuesta: comparar

• (1) Prioridad a lectores: las escrituras son tan raras que su starvation es improbable, y se maximiza el paralelismo de lectura. Igual conviene un torniquete, por si la carga cambia.
• (2) Prioridad a escritores: un precio viejo es un error, así que la escritura no puede esperar a que se vacíe la sala. El costo: los lectores pueden sufrir starvation si hay escrituras continuas.
• Turnos justos: alternar (después de una escritura entran todos los lectores que esperaban, y luego otro escritor) evita la starvation de ambos, a cambio de más lógica.

⚠️ Errores que cuestan puntos

• Decir que la solución 3 ya da prioridad a escritores porque usa condition variables.Mira la condición: el lector solo espera si hay escritores activos, así que sigue favoreciendo a los lectores.
• Reemplazar el semáforo del lightswitch por un mutex.El que bloquea (el primer lector) puede no ser el que desbloquea (el último). El mutex tiene dueño.
• Leer y escribir los datos dentro del lock de los contadores.El lock protege solo los contadores. Si los datos se leen dentro, se pierde el paralelismo entre lectores.

Autoevaluación

0/4 correctas · 0 respondidas Reiniciar

1. En la solución 1 (lightswitch con semáforos), ¿quién puede sufrir starvation?

a) Los lectoresb) Los escritoresc) Nadied) Ambos

2. ¿Por qué la solución con mutex (diap. 18–19) es incorrecta?

a) Hay deadlockb) Un lector bloquea lock_data y otro lector distinto lo desbloquea: el mutex tiene dueñoc) Los escritores entran juntosd) No hay paralelismo

3. En la solución 3, al salir un escritor hace signal(cond_wr) y broadcast(cond_rd). En Mesa, ¿quién entra?

a) Siempre el escritorb) Siempre los lectoresc) Quien readquiera el lock primero; los demás re-evalúan su whiled) Nadie

4. En la solución de la diap. 25, ¿qué papel cumple lock_data?

a) Proteger nrb) Torniquete: un escritor que lo toma impide que entren lectores nuevosc) Condition variabled) Ninguno

🗣️ Explícalo tú (Feynman)

Explica qué es el lightswitch y por qué causa starvation de escritores.

Dilo en voz alta o escríbelo en 4–5 líneas, sin mirar la página. Después revisa qué te faltó.

Tu explicación debería mencionar…

• El primer lector que entra cierra el acceso a los escritores (wait(sem_data)) y el último que sale lo abre.
• Mientras haya al menos un lector dentro, el contador nunca llega a 0 y el escritor sigue esperando.
• Con lectores que se solapan continuamente, el escritor espera para siempre.
• La solución: un torniquete o un contador de escritores esperando, que impida entrar a lectores nuevos.

📈 ¿Qué tan bien lo dominas?

Elige pensando en lo que hiciste, no en lo que leíste. Para marcar 3 tienes que haber resuelto un ejercicio nuevo sin pistas y haberlo justificado. Si solo lo leíste y sientes que «ya entendí», todavía es un 1.

0No lo reconozco o lo confundo con otro tema1Lo entiendo leyendo, pero no lo aplico solo2Resuelvo ejercicios parecidos a los vistos, con alguna pista3Resuelvo uno nuevo sin ayuda y justifico cada paso4Lo transfiero: comparo alternativas y veo casos límite

Fuente ·for_partial/pending_themes/09-OSL-Monitors_ReaderWriter.pdf · código del curso so/sem6/r-w-sequential.c, r-w-starvation.c, r-w-broadcast.c, r-w-sol-example.c · lab2/Resumenes/11-Lectores-Escritores.md