Colas con prioridades

01 · Punto de partida

No todos pueden esperar lo mismo

En la guardia, el código rojo pasa aunque haya llegado último; en el soporte, el cliente gold salta al silver; en la red, la voz adelanta a los datos. Las prioridades reparten la espera por urgencia, no por llegada: el VIP vuela y la clase baja paga.

El trabajo total no cambia (work-conserving), pero la Wq por clase sí: con 20% de VIP, el VIP espera 2 min donde FIFO daba 8, y el común 10. Diseñar prioridades es elegir quién paga.

• ¿Cómo se definen las clases y qué regla las ordena?
• ¿Expulsiva o no expulsiva: interrumpir o esperar el fin?
• ¿Cuánto gana el VIP y cuánto pierde el resto?
• ¿Cómo evito que la clase baja inaniciona?

02 · Definición

Clases, expulsión y conservación

03 · El corazón: quién interrumpe a quién

El fin elige, la expulsión interrumpe

Sin expulsión, el VIP que llega con el servidor ocupado espera lo que queda (inversión acotada). Con expulsión resume, lo interrumpe y retoma después; con repeat, lo tira y reempieza (caro). La práctica usa no expulsiva + clases pocas; la urgencia vital usa expulsiva.

1. 1
   Etiquetar al llegar.

   Cada arribo trae prio (1 VIP). La tasa por clase λ_i sale de la mezcla.

2. 2
   Encolar por clase.

   La espera se ordena por (prio, arr), no por llegada. El motor FEL no cambia.

3. 3
   Elegir o interrumpir.

   No expulsiva: en cada fin, el mínimo. Expulsiva: al llegar un 1 con un 2 en curso, pausar y atender.

4. 4
   Medir por clase.

   Wq_i, L_i y Little por clase. La global sola escondería a quién se castigó.

Preemptive-resume

Interrumpe y retoma donde quedó (costo de contexto). El VIP casi no espera; el resto paga la reanudación.

Preemptive-repeat

Interrumpe y reempieza de cero (caro con S largos). Solo si el VIP lo vale de verdad.

Inanición y aging

Con VIP continuo, la clase baja no sale nunca. Aging: la prioridad mejora con la espera acumulada.

Cobham (M/M/1)

Wq_k = R/((1−σ_k−1)(1−σ_k)), con R = λE[S²]/2 y σ_k = Σ_i≤kρ_i. La fórmula del reparto.

04 · Ejemplos

Cuatro clases con historia

1. 1
   Guardia (triage 1-2-3, expulsiva).

   El rojo interrumpe la consulta verde: resume después. Vidas contra espera.

2. 2
   Soporte gold/silver (no expulsiva).

   El gold adelanta en cada fin; el silver paga +25% de Wq a cambio del contrato.

3. 3
   Red voz sobre datos.

   La voz (clase 1) salta paquetes: latencia baja a costa de jitter en datos.

4. 4
   Taller urgente.

   La pieza que para la línea es prio 1 del día: el resto se reordena sin parar máquinas.

05 · Representación en Python

Dos arribos, una regla con tupla

Dos Poisson (λ₁, λ₂) mezclados por tiempo; la espera elige (prio, arr). El motor es el de siempre.

# Mezclar dos clases Poisson en una agenda (p=20% VIP)
import random
random.seed(39)
lam, p = 0.5, 0.2
t = 0.0
agenda = []
for _ in range(6):
    t += random.expovariate(lam)
    prio = 1 if random.random() < p else 2
    agenda.append((round(t, 2), prio))
print(agenda)

# FIFO vs PRIO no expulsivo, c=1: Wq por clase
def correr(jobs, key):
    t, res = 0.0, {1: [], 2: []}
    pend = sorted(jobs, key=lambda j: j["arr"])
    esp, i, orden = [], 0, []
    while len(orden) < len(jobs):
        while i < len(pend) and pend[i]["arr"] <= t:
            esp.append(pend[i]); i += 1
        if not esp:
            t = pend[i]["arr"]; continue
        e = min(esp, key=key); esp.remove(e)
        res[e["prio"]].append(t - e["arr"]); orden.append(e["id"]); t += e["S"]
    return {k: round(sum(v)/len(v), 2) if v else 0 for k, v in res.items()}

jobs = [{"id": "A", "arr": 0, "S": 6, "prio": 2}, {"id": "B", "arr": 1, "S": 1, "prio": 2}, {"id": "C", "arr": 2, "S": 1, "prio": 1}]
print("FIFO:", correr(jobs, lambda e: e["arr"]))
print("PRIO:", correr(jobs, lambda e: (e["prio"], e["arr"])))

06 · Exploración

Laboratorio: FIFO contra PRIO, misma historia

Generamos una historia con λ total y fracción VIP p (semilla fija) y la corremos con ambas reglas (c = 1, no expulsivas). Las barras comparan Wq VIP y común en FIFO (claro) vs PRIO (sólido); el borde marca tu regla. Subí p y mirá cómo el privilegio se diluye cuando todos son VIP.

Parejas por clase: claro = FIFO, sólido = PRIO. Borde blanco = tu regla. Con p alta, PRIO se parece a FIFO.

Preguntas para explorar

1. Con λ=0.4, p=20%: ¿Wq VIP con PRIO vs FIFO? ¿Y la común? ¿Global?
2. Subí p a 50%: ¿qué le pasa a la ganancia VIP? ¿Por qué?
3. ¿Qué pasaría con p=20% pero regla expulsiva? (Anticipá sin simular.)

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: Cobham en números

λ₁=0.1, λ₂=0.3, S=2 Exp (E[S²]=8). Calculá R, Wq₁ y Wq₂ no expulsivas.

lam1, lam2, ES2 = 0.1, 0.3, 8.0
R = (lam1+lam2)*ES2/2
s1 = lam1*2
print(f"R={R} Wq1={R/(1-s1):.1f} Wq2={R/((1-s1)*(1-0.8)):.1f}")

Ejercicio 2: p que diluye

λ=0.4 fijo, p=10% vs 50% VIP. ¿σ₁ en cada caso? ¿Qué anticipás de Wq₁?

for p in [0.1, 0.5]:
    print(f"p={p:.0%} sigma1={0.4*p*2:.2f}")  # 0.08 vs 0.40

Ejercicio 3: aging en una línea

Escribí un key con envejecimiento: prioridad efectiva = prio − espera/10.

# key dinámica con t actual (clausura): la clase baja sube con su espera
t = 10.0
key_aging = lambda e: (e["prio"] - (t - e["arr"])/10, e["arr"])
print("La común que espera 20 suma −2: compite con VIP nuevos")

09 · Síntesis

Ideas para recordar

En el próximo tema conectaremos colas: las redes de colas.