11.1 Panorama general
Las colas intervienen en cualquier arquitectura que procese actividades en secuencia o necesite priorizar eventos. En este tema describimos los contextos donde se aplican con mayor frecuencia, resaltando el tipo de cola adecuado, los objetivos que persiguen y las consideraciones de diseño. No incluimos código para mantener el foco en la teoría; las implementaciones llegarán en temas posteriores.
11.2 Buffer productores/consumidores
El problema productores/consumidores aparece en sistemas concurrentes donde uno o varios hilos generan datos y otros los consumen. Para absorber picos se usa una cola circular o un deque protegido con mecanismos de sincronización (mutex, semáforos, monitores). Las decisiones clave son:
- Capacidad del buffer: fija para hardware embebido, dinámica cuando la carga es impredecible.
- Política de bloqueo: los productores esperan si el buffer está lleno y los consumidores si está vacío.
- Instrumentación: la cola permite medir latencias y detectar backlog antes de saturar el sistema.
11.3 Simulación de turnos con eventos discretos
En simuladores de turnos se modelan clientes que llegan según una distribución estadística y servidores que procesan solicitudes en orden FIFO. Una cola enlazada registra cada evento (llegada, fin de servicio) junto con su marca de tiempo. El motor extrae el evento más próximo, avanza el reloj y genera nuevos eventos derivados. Este enfoque permite:
- Estimar tiempos de espera y tamaño promedio de la cola.
- Probar diferentes políticas de servicio (un servidor vs. múltiples ventanillas).
- Medir el impacto de la variabilidad en las llegadas, manteniendo la cola como estructura central.
11.4 Scheduler Round Robin
El planificador Round Robin en sistemas operativos asigna un quantum fijo de CPU a cada proceso y lo devuelve al final de la cola si aún no terminó. La cola elegida suele ser un deque para mover elementos entre extremos sin copiar. Temas clave:
- Determinación del quantum: demasiado corto incrementa los cambios de contexto, demasiado largo degrada la interactividad.
- Tratamiento de procesos bloqueados: si un proceso espera E/S, se retira temporalmente de la cola.
- Prioridades: algunos sistemas usan múltiples colas Round Robin con quanta distintos para cada nivel.
11.5 Colas de prioridad en grafos
Algoritmos como Dijkstra, Prim o A* necesitan extraer rápidamente el nodo con mejor heurística o menor distancia conocida. Una cola de prioridad basada en heap min mantiene el nodo más prometedor en la raíz y admite operaciones decrease-key para actualizar prioridades. Aspectos teóricos relevantes:
- La complejidad O((V + E) log V) surge de las operaciones logarítmicas de inserción y extracción en el heap.
- El invariante del algoritmo (distancia mínima confirmada) depende de que la cola siempre entregue el menor costo.
- Las versiones orientadas a rendimiento introducen colas especializadas (binomial, Fibonacci) cuando decrease-key es muy frecuente.
11.6 Eventos asíncronos y bucles de mensajes
Las aplicaciones con interfaces gráficas, motores de juego o sistemas distribuidos coordinan numerosos eventos asincrónicos. Un bucle principal consume una cola de eventos mientras los productores (entradas del usuario, red, temporizadores) agregan elementos. Consideraciones:
- Modelo de seguridad: muchas implementaciones adoptan colas MPMC (multi-producer, multi-consumer) lock-free para minimizar la contención.
- Orden de procesamiento: el evento más antiguo se atiende primero, pero puede añadirse una prioridad para tiempo real.
- Backpressure: cuando el consumidor no alcanza a procesar, la cola actúa como buffer y se disparan estrategias de descarte o compresión.
11.7 Redes, QoS y pipelines
Los routers, balanceadores de carga y pipelines multimedia emplean colas para regular el acceso a recursos compartidos. Ejemplos teóricos:
- Quality of Service: se mantienen varias colas, una por clase de servicio, y un scheduler aplica pesos para garantizar ancho de banda mínimo.
- Pipelines de video/audio: colas lock-free entre etapas evitan que una fase lenta detenga al resto; el tamaño del buffer determina la latencia total.
- Colas de retransmisión: los mecanismos ARQ en redes almacenan paquetes pendientes hasta recibir confirmación y liberan espacio en función del acknowledgement.
11.8 Guía para seleccionar la cola adecuada
Independientemente del dominio, elegir una cola implica responder:
- ¿El flujo es potencialmente infinito? Prefiere estructuras enlazadas o heaps reescalables.
- ¿Importa el orden cronológico estricto o una prioridad dinámica? Opta por FIFO puro o por colas de prioridad.
- ¿Existe concurrencia? Determina si necesitas lock-free, semáforos o simplemente un buffer local.
- ¿Se deben medir tiempos de espera? Las colas sirven como punto de análisis para registrar métricas y alarmas.