Enunciado y contexto
Implementa un semáforo asíncrono para un grupo de conexiones (connection pool) o un ejecutor de tareas. Comienza con una capacidad N; acquire() se pone en cola cuando no hay permisos disponibles y release() devuelve uno. Un elemento en espera puede agotar su tiempo de espera o ser cancelado. La cancelación no debe dejar una entrada fantasma en la cola ni impedir que otro elemento en espera avance. Define las liberaciones duplicadas, el comportamiento de cierre y la equidad (fairness).
Esto encaja en entrevistas de concurrencia, entornos de ejecución e infraestructura de backend. La API Semaphore de Oracle define permisos, selección FIFO equitativa opcional y adquisición interrumpible. La documentación de asyncio de Python describe un contador que disminuye al adquirir y aumenta al liberar, y distingue entre semáforos ordinarios y acotados. Las discusiones públicas de entrevistas incluyen los semáforos contadores y los límites de concurrencia como temas de entrevistas sobre sistemas operativos. Estas fuentes respaldan su representatividad, pero no establecen un enunciado ni una frecuencia fijos para ninguna empresa. La categoría es coding porque las habilidades fundamentales son los invariantes de estado, la limpieza de colas, las condiciones de carrera por cancelación y la implementación concurrente verificable.
Qué evalúan los entrevistadores
Primero, ¿define el candidato la propiedad del permiso? Una adquisición exitosa debe crear un token que pueda devolverse exactamente una vez. Una solicitud cancelada o con tiempo de espera agotado no tiene token y no debe llamar a release.
Segundo, ¿es real la equidad? Una vez que la cola no está vacía, una nueva liberación no debe permitir que una ruta rápida posterior eluda la cabecera; de lo contrario, una carga alta puede causar inanición (starvation) a un elemento antiguo en espera. La equidad FIFO requiere verificar la cola, asignar un permiso y despertar a un elemento en espera dentro de un único límite de sincronización.
Tercero, ¿pueden manejar la condición de carrera entre la cancelación y la reactivación? Es posible que un elemento en espera ya haya sido seleccionado por release y luego agote su tiempo de espera, o que agote su tiempo de espera antes de que release lo elimine. Ambas rutas deben competir por una única transición de estado y completar un elemento en espera como máximo una vez.
Por último, ¿las pruebas verifican el límite de concurrencia, el orden FIFO, la limpieza por tiempo de espera, el progreso tras la cancelación, la liberación duplicada, el cierre y el fallo de tareas en lugar de limitarse a acquire/release secuenciales?
Preguntas clarificadoras para hacer primero
- ¿La equidad es FIFO estricta o del mejor esfuerzo? El FIFO estricto evita la inanición, pero puede sacrificar el rendimiento (throughput).
- ¿Qué devuelve acquire? Un token de liberación o arrendamiento (lease) vincula la propiedad a una adquisición exitosa y reduce las liberaciones accidentales.
- ¿Qué sucede si la cancelación ocurre después de que se asigna un permiso? Define la precedencia de finalización; una vez que la promesa se resuelve, el llamador es dueño del arrendamiento y la cancelación solo afecta el trabajo posterior.
- ¿Es un error hacer release más veces que acquire? Un semáforo acotado debe rechazarlo o reportarlo; aumentar silenciosamente el contador viola la capacidad.
- ¿Cómo finaliza close a los elementos en espera? Close rechaza nuevas solicitudes y termina los elementos en cola con un error explícito de Closed; los arrendamientos retenidos aún pueden liberarse de forma segura.
Estructura de respuesta en 30 segundos
“Mantengo available, una cola de espera FIFO y un estado cerrado, con cada mutación en una única sección crítica. Acquire puede tomar la ruta rápida solo cuando la cola está vacía; una vez que existen elementos en espera, los llamadores posteriores se encolan. Release encuentra el primer elemento en espera activo, le transfiere un permiso y lo completa una vez; solo cuando no existe ningún elemento en espera activo incrementa available. Cada elemento en espera tiene un estado de cancelación y una finalización de un solo uso. El tiempo de espera y release compiten en ese mismo estado. Un acquire exitoso devuelve un arrendamiento que se puede liberar una sola vez. Las pruebas fuerzan FIFO, cancelación y liberación en el mismo límite, recuperación de permisos tras tiempo de espera, liberación duplicada, cierre y el límite de concurrencia.”
Respuesta detallada
1. Establecer el invariante central
Para una capacidad N, mantén available + held + reserved = N. available se puede asignar de inmediato, held pertenece a los llamadores mediante arrendamientos y reserved ha pasado de disponible a un elemento en espera seleccionado cuya devolución de llamada aún no se ha completado.
Cada elemento en espera tiene exactamente un estado terminal: pendiente, completado o cancelado. Un elemento cancelado no posee ningún permiso; un elemento completado debe producir un arrendamiento. El cierre no reclama los arrendamientos retenidos, pero impide nuevas adquisiciones.
2. Ruta rápida equitativa y cola
Cuando waiters está vacío y el semáforo está abierto, acquire puede consumir available directamente. Cuando la cola no está vacía, incluso si available > 0, un nuevo llamador se encola; de lo contrario, elude a un llamador más antiguo. Acquire y release deben verificar la cola bajo el mismo límite de sincronización.
Un nodo de la cola almacena la promesa del elemento en espera, el estado de cancelación, el manejador del temporizador y la función de finalización de un solo uso. Elimina los nodos completados o cancelados, o conserva lápidas (tombstones) que release omita de forma perezosa en la cabecera. Cualquiera de las dos estrategias necesita una demostración de que un elemento en espera activo no puede quedar permanentemente detrás de nodos inválidos.
3. Transferir permisos en release
Release primero verifica que el arrendamiento no haya sido liberado previamente y luego entrega el permiso al primer elemento en espera activo. El permiso pasa de retenido a reservado y se invoca la finalización del elemento en espera; no incrementes available ni busques de forma asíncrona, ya que un nuevo acquire podría colarse en la fila.
Si la cabecera está cancelada, omítela y límpiala, continuando con el siguiente elemento en espera. Solo si no existe ningún elemento en espera activo se debe available += 1. Un semáforo acotado rechaza liberaciones que superen N para que un error del llamador no pueda ocultar una fuga o una devolución doble.
4. Condiciones de carrera por cancelación y tiempo de espera
La cancelación y release pueden intentar finalizar el mismo elemento en espera. Utiliza un CAS de un solo uso, una comprobación de estado dentro del bloqueo o un mecanismo equivalente para que solo uno gane. Si la cancelación gana, elimina el elemento en espera sin cambiar available porque nunca poseyó un permiso. Si release ya ha reservado un permiso, la cancelación no puede devolverlo y permitir al mismo tiempo que release complete el mismo elemento en espera.
Una regla sencilla es que release marque el elemento en espera como completado dentro de la sección crítica antes de resolverlo. Una vez completado, un tiempo de espera solo puede registrar que el llamador abandonó el trabajo posterior; el llamador aún libera el arrendamiento que recibe. Un diseño más elaborado puede reclamar una reserva no entregada, pero esa reclamación pertenece a la misma máquina de estados en lugar de deducirse de una promesa rechazada.
5. Arrendamiento y liberación duplicada
Devuelve un arrendamiento con un indicador released. lease.release() puede pasar de falso a verdadero una sola vez. Una llamada duplicada devuelve un resultado idempotente o un error claro; no puede agregar dos permisos. Exponer un método release directo a llamadores arbitrarios pierde la asociación de propiedad, a menos que la API utilice explícitamente un modelo de conteo propiedad del llamador.
6. Cierre, fallos y contrapresión (backpressure)
Tras el cierre, rechaza nuevos acquires y finaliza los elementos en cola con Closed. Las tareas que retienen arrendamientos pueden terminar y liberar; release no debe descartar permisos simplemente porque el semáforo esté cerrado, o la cuenta de retenidos quedará sin explicación. Los fallos de las tareas aún liberan en finally.
Un semáforo limita la concurrencia, no la longitud de la cola. Una cola de espera no acotada convierte la contrapresión en consumo excesivo de memoria. El código de producción debe establecer un número máximo de esperas, un tiempo de espera o una política de rechazo, y registrar la duración de la espera, la tasa de cancelación y la profundidad de la cola.
7. Controlar las carreras con un planificador
No demuestres las carreras con esperas reales (sleeps). Utiliza un reloj manual y un planificador controlable para pausar en el encolamiento, cuando release selecciona un elemento en espera y cuando una devolución de llamada de tiempo de espera se encola pero aún no se ejecuta. En cada paso, valida available, held, la cantidad de elementos en espera activos y la propiedad del arrendamiento.
Cubre la inicialización inválida N=0, FIFO estricto con N=1, permisos múltiples, cancelación en la cabecera y en un elemento intermedio, tiempo de espera y liberación en el mismo límite, liberación duplicada, acquire antes y después de cerrar, fallo de tareas y la ausencia de inanición para un llamador con larga espera.
Respuesta de ejemplo de alta calidad
“Encapsulo la propiedad del permiso en un arrendamiento. El semáforo almacena available, elementos en espera FIFO y el estado de cierre, y todas las transiciones comparten un único límite de sincronización. Acquire toma la ruta rápida solo cuando la cola está vacía; una vez que existe un elemento en espera, las llamadas posteriores se encolan.
Release verifica que el arrendamiento se libere una sola vez, encuentra el primer elemento en espera activo, transfiere held a la reserva de ese elemento y lo completa una vez. Omite y limpia las cabeceras canceladas; solo cuando no hay ningún elemento en espera activo incrementa available. La cancelación y el tiempo de espera compiten con release en el mismo estado del elemento en espera, y una transición de un solo uso elige al ganador. Una cancelación antes de acquire no posee ningún permiso, mientras que un acquire completado entrega al llamador un arrendamiento que la cancelación no puede reemplazar.
Close rechaza nuevas solicitudes y finaliza los elementos en cola, mientras que los arrendamientos retenidos aún pueden liberarse. Las pruebas utilizan un reloj manual y un planificador para forzar FIFO, cancelación en cabecera y en el medio, tiempo de espera y liberación simultáneos, liberación duplicada, limpieza en finally tras un fallo y el límite de concurrencia. El invariante del contador demuestra que no se pierde ni se crea ningún permiso.”
Errores comunes
- Tomar la ruta rápida mientras la cola no está vacía → los nuevos llamadores eluden a los antiguos y los dejan en inanición → encola a todo llamador mientras existan elementos en espera.
- Incrementar available cuando un elemento en espera se cancela → es posible que release ya haya reservado su permiso → haz competir la cancelación y release en un único estado de un solo uso.
- Exponer un release sin propietario → las llamadas duplicadas crean permisos → devuelve un arrendamiento que se pueda liberar una sola vez.
- Incrementar available antes de despertar la cabecera → un nuevo llamador puede colarse → transfiere directamente bajo la misma sección crítica.
- Tratar el tiempo de espera como una reversión de un arrendamiento entregado → la tarea aún podría estar ejecutándose → distingue la cancelación durante la espera de un permiso adquirido.
- Permitir una cola no acotada → el límite de concurrencia se convierte en una fuga de memoria → establece un límite de cola, tiempo de espera o política de rechazo.
- Probar solo llamadas secuenciales → se omiten las carreras de cancelación y la liberación duplicada → fuerza intercalaciones con un planificador controlable.
- Descartar permisos retenidos al cerrar → los recuentos de recursos no pueden converger → permite que los arrendamientos retenidos se liberen en finally.
Preguntas de seguimiento y respuestas
¿Es siempre mejor la equidad FIFO?
No. FIFO evita la inanición y es fácil de explicar, pero una cabecera de larga ejecución o a punto de agotar su tiempo de espera puede provocar un bloqueo de cabeza de línea (head-of-line blocking). Una implementación orientada al rendimiento puede permitir una ruta rápida no equitativa, pero la inanición, el tiempo máximo de espera y la prioridad deben ser elecciones contractuales explícitas y no propiedades asumidas.
¿Cómo adquirirías múltiples permisos a la vez?
Registra la cantidad solicitada por cada elemento en espera y cúmplela solo cuando available sea suficientemente grande. El FIFO estricto puede hacer que las solicitudes de un solo permiso detrás de una cabecera multi-permiso esperen; permitir la omisión sacrifica la equidad. Elige una política y cuenta los permisos reservados, no los objetos en espera, en el invariante.
¿Qué sucede si una tarea se cancela a mitad de su ejecución?
El semáforo es dueño de los permisos, no de la interrupción de tareas. El llamador debe detener el trabajo al cancelarse y liberar el arrendamiento en finally; si el trabajo no se puede interrumpir, debe terminar antes de liberar. El semáforo no debe reclamar un permiso que todavía esté en uso.
¿Cuál es el límite entre un semáforo y un mutex?
Un semáforo representa un recuento de recursos disponibles, y diferentes actores pueden adquirir y liberar permisos. Un mutex representa propiedad exclusiva y normalmente requiere que el propietario lo desbloquee. Un semáforo con valor uno puede imitar la exclusión mientras pierde las comprobaciones de propiedad y la semántica de prioridad, por lo que se debe elegir la primitiva que coincida con el contrato de la API.