Consigna y casos de uso
Implementa un bloqueo de lectura y escritura seguro para subprocesos: varios lectores pueden retenerlo simultáneamente, mientras que un escritor debe retenerlo de manera exclusiva. Explica la política de espera, las reglas de activación, la reentrada y cómo evitas la inanición indefinida de los escritores. Puedes usar un mutex y variables de condición, pero no un bloqueo de lectura y escritura integrado.
Esta pregunta es adecuada para roles de backend, infraestructura y concurrencia. Evalúa invariantes de sincronización y compensaciones (trade-offs) en lugar de un lenguaje de programación específico.
Lo que evalúa el entrevistador
- Si defines los invariantes primero: a lo sumo un escritor activo y ningún lector activo mientras un escritor retiene el bloqueo.
- Si la "equidad" (fairness) se convierte en una regla de admisión ejecutable.
- Si manejas activaciones espurias (spurious wakeups), rutas excepcionales, adquisiciones recursivas y bloqueos mutuos por actualización (upgrade deadlocks).
- Si proporcionas complejidad, pruebas y un límite para reutilizar una biblioteca estándar de producción.
Aclaraciones antes de responder
Confirma si la adquisición debe ser interrumpible o con tiempo límite (timed), si un subproceso puede reentrar, si se requiere la actualización de lectura a escritura y si equidad significa FIFO estricto o progreso eventual del escritor. Si no se especifica, propón un diseño mínimo no reentrante, sin capacidad de actualización y con preferencia de escritor, e indica ese límite explícitamente.
Una respuesta en 30 segundos
Nombra el estado: activeReaders, activeWriter y waitingWriters. Un lector ingresa solo cuando no hay ningún escritor ni escritores en cola; un escritor ingresa solo cuando ambos conteos de activos están vacíos. Protege cada cambio de estado con un mutex y despierta a un escritor o a un grupo de lectores en la liberación. Vuelve a verificar los predicados en un bucle while después de cada activación de variable de condición. Prohíbe la actualización de lectura a escritura a menos que la API defina un protocolo explícito.
Solución paso a paso
Estado e invariantes
activeWriter es un booleano, activeReaders es un conteo no negativo y waitingWriters cuenta los escritores en cola. El invariante clave es que activeWriter == true implica activeReaders == 0; un escritor puede ingresar solo cuando ambos están vacíos. El conteo de espera controla la política y no significa que se retenga un bloqueo.
Adquisición y liberación
Un lector espera a !activeWriter && waitingWriters == 0; un escritor espera a !activeWriter && activeReaders == 0. Vuelve a verificar después de cada retorno de variable de condición para manejar activaciones espurias. Al liberar un escritor, envía una señal a un escritor si hay alguno en cola; de lo contrario, transmite (broadcast) a los lectores. Cuando el último lector sale, envía una señal a un escritor.
~~~text readLock(): mutex.lock() while activeWriter or waitingWriters > 0: readersCondition.wait(mutex) activeReaders += 1 mutex.unlock()
writeLock(): mutex.lock() waitingWriters += 1 while activeWriter or activeReaders > 0: writersCondition.wait(mutex) waitingWriters -= 1 activeWriter = true mutex.unlock()
writeUnlock(): mutex.lock() activeWriter = false if waitingWriters > 0: writersCondition.signal() else: readersCondition.broadcast() mutex.unlock() ~~~
Equidad y rendimiento (throughput)
| Política | Admisión de lectores | Beneficio | Riesgo |
|---|---|---|---|
| Preferencia de escritor | Sin escritor activo y waitingWriters == 0 | Limita la inanición de escritores | La latencia de lectura aumenta durante una ráfaga de escritores |
| Preferencia de lector | Sin escritor activo | Alto rendimiento de lectura | Un escritor puede sufrir inanición |
| FIFO aproximado | Admitir en orden de cola | Latencia más predecible | Mayor complejidad de estado y de colas |
Oracle documenta que el modo no equitativo (non-fair) puede posponer indefinidamente a un lector o escritor, mientras que el modo equitativo (fair) utiliza una política aproximada al orden de llegada y, por lo general, renuncia al rendimiento. Distingue "sin inanición" de FIFO estricto en la entrevista.
Respuesta modelo
Comenzaría con una implementación no reentrante y con preferencia de escritor. Un mutex protege todos los contadores. Los lectores se incrementan solo cuando no hay ningún escritor activo o en espera; los escritores esperan hasta que ambos conteos de activos estén vacíos. Cada retorno de variable de condición vuelve a verificar su predicado en un bucle while. Al liberar, se envía una señal a un escritor cuando hay uno en cola; de lo contrario, se transmite a los lectores. Esto preserva el invariante de exclusión y evita que un flujo interminable de nuevos lectores se adelante a un escritor.
Rechazaría explícitamente la actualización de lectura a escritura: un lector que espera un bloqueo de escritura puede evitar que otros lectores lo liberen y provocar un interbloqueo (deadlock). El llamador debe liberar el bloqueo de lectura y competir nuevamente, o usar un protocolo de actualización en cola separado. Para interrupciones, tiempos de espera, reentrada, diagnósticos o equidad estricta, usaría una primitiva de plataforma documentada y probaría su semántica en lugar de copiar un bloqueo incompleto en el código de negocio.
Errores comunes
- Reemplazar
whileporif, permitiendo que una activación espuria eluda el predicado. - Ignorar los escritores en cola y admitir lectores indefinidamente.
- Despertar solo a un lector después de la liberación de un escritor, o transmitir incondicionalmente creando un problema de rebaño atronador (thundering herd).
- Permitir actualizaciones sin una cola de actualización, haciendo que dos lectores esperen el uno por el otro.
- Tratar
tryLockcomo una garantía de equidad. Oracle señala explícitamente que untryLockno bloqueante puede colarse (barge).
Preguntas de seguimiento y respuestas
¿Cómo pruebas los invariantes?
Mantén una instantánea de prueba atómica: valida con aserciones que haya cero lectores al entrar un escritor y que no haya ningún escritor al entrar un lector. Ejecuta subprocesos de lectores y escritores aleatorizados, y registra la secuencia de eventos cada vez que falle una aserción.
¿Cómo pruebas la inanición del escritor?
Genera lectores continuamente mientras un escritor espera. Registra el tiempo desde la entrada en cola hasta la admisión del escritor y el recuento máximo de espera. El objetivo es el progreso eventual, no una promesa fija y arbitraria de milisegundos.
¿Por qué no usar un mutex ordinario?
Un mutex ordinario es más simple y a menudo tiene una latencia más estable. Un bloqueo de lectura y escritura solo puede ayudar cuando dominan las lecturas y las secciones críticas de lectura son lo suficientemente largas como para superponerse. Elige con una prueba de rendimiento (benchmark), no por intuición.
¿Puede ser reentrante?
Rastrea el subproceso del escritor y el recuento de retenciones, además de los recuentos de lectura por subproceso. Eso amplía sustancialmente las reglas de actualización y liberación. Si no se requiere la reentrada, prohibirla mantiene más pequeño el espacio de estados.
¿Qué aporta POSIX a la discusión?
POSIX expone operaciones separadas de bloqueo de lectura y bloqueo de escritura con retornos de error definidos. La implementación aún debe respetar las reglas de la plataforma para la prioridad y el comportamiento recursivo; no se debe presentar una política personalizada como una garantía de POSIX.
¿Cuándo deberías dejar de escribirlo manualmente?
Cuando importen la interrupción, los tiempos de espera, los diagnósticos, la reentrada o la portabilidad, prefiere una primitiva verificada como ReentrantReadWriteLock de Java o pthread_rwlock_* de POSIX, y registra la elección de equidad en la revisión.