Disciplina de la cola

01 · Punto de partida

La misma fila, tres llamados distintos

Se libera una caja y esperan Ana (hace 10 min, trámite de 1 min), Bruno (hace 2 min, trámite de 8 min) y Carla (embarazada, llegó última). ¿A quién llama? Con FIFO va Ana; con SPT (el más corto primero) también Ana; con prioridades va Carla; con LIFO iría el último. El trabajo total es el mismo, pero quién espera y cuánto cambia por completo.

Esa es la disciplina de la cola: la regla que elige al próximo cuando un servidor se libera (y si alguien puede interrumpir). No cambia la capacidad, pero reparte la espera.

• ¿Quién sigue cuando se libera un servidor: el primero, el último, el más corto, el más urgente?
• ¿Alguien puede pasar al frente o interrumpir al que se atiende?
• ¿El orden cambia el trabajo total o solo quién lo sufre?
• ¿Qué es justo y qué es eficiente: coinciden?

02 · Definición

Tres familias de reglas

03 · El corazón: orden sin cambiar trabajo

Repartir espera, no crear capacidad

Si el servidor no descansa habiendo cola, la suma de trabajo ΣS es intocable: FIFO, LIFO o SPT terminan el mismo lote casi al mismo tiempo (makespan igual, salvo ocio por llegadas futuras). Lo que sí cambia es quién esperó: SPT adelanta enanos y hunde gigantes; prioridades adelantan al VIP aunque llegue tarde; LIFO deja a alguno esperando eternamente si no para el arribo.

1. 1
   Listar solo a los presentes.

   La regla elige entre arr ≤ t, no entre futuros. Si nadie espera, el servidor queda ocioso hasta la próxima llegada.

2. 2
   Aplicar la regla.

   FIFO: menor arr; LIFO: mayor arr; SPT: menor S; PRIO: menor prio (empate → FIFO).

3. 3
   Encadenar sin ocio.

   Inicio = t, fin = t + S. El atraso de un gigante se hereda tal cual al siguiente: por eso el orden importa.

4. 4
   Medir por clase.

   Wq global más Wq por prioridad/tamaño. Una disciplina se juzga por a quién beneficia y a quién inaniciona.

Work-conserving

Nunca ocio con espera. Conserva ΣS y el makespan del lote. FIFO, LIFO, SPT y PRIO no expulsiva lo son.

Inanición (starvation)

Con prioridades o SPT extremo, el gigante o la clase baja pueden esperar muchísimo. LIFO con arribo continuo también la produce.

Expulsiva vs no expulsiva

No expulsiva: el que está en servicio termina. Expulsiva (preemptive): un VIP lo interrumpe (resume o repeat). Potente y costosa.

SPT y SRPT

SPT (no expulsivo) minimiza la espera media entre reglas sin conocer futuro. SRPT (expulsivo, menor tiempo restante) la minimiza aún más.

04 · Ejemplos

Cuatro mostradores, cuatro reglas

1. 1
   Banco fila única (FIFO).

   El que llegó primero pasa. Justo y simple; el de 8 min traba a los de 1 min que vinieron detrás.

2. 2
   Impresora compartida (SPT).

   El trabajo de 1 página salta al de 100: la media se desploma y el gigante espera (pero igual imprime).

3. 3
   Guardia hospital (prioridades expulsivas).

   El código rojo interrumpe la consulta leve (preemptive-resume): el leve espera, el grave vive.

4. 4
   CPU por rondas (Round-Robin).

   Cada proceso usa un cuanto y vuelve a la cola: nadie inaniciona y todos avanzan de a poco.

05 · Representación en Python

Elegir es una función de una línea

La espera es una lista de dicts {id, arr, S, prio}. Cambiar de disciplina es cambiar el key de selección; el motor de simulación no se toca.

# La misma espera, cuatro próximos distintos
esp = [{"id": "A", "arr": 0, "S": 1}, {"id": "B", "arr": 1, "S": 8}, {"id": "C", "arr": 2, "S": 2}]
print("FIFO:", min(esp, key=lambda e: e["arr"])["id"])   # A
print("LIFO:", max(esp, key=lambda e: e["arr"])["id"])   # C
print("SPT:", min(esp, key=lambda e: e["S"])["id"])      # A (aquí coincide)

# Simular N con regla intercambiable (no expulsiva, c=1)
def simular(jobs, key):
    t, orden, wqs = 0.0, [], []
    pend = sorted(jobs, key=lambda j: j["arr"])
    espera, i = [], 0
    while len(orden) < len(jobs):
        while i < len(pend) and pend[i]["arr"] <= t:
            espera.append(pend[i]); i += 1
        if not espera:
            t = pend[i]["arr"]; continue
        e = min(espera, key=key); espera.remove(e)
        wqs.append(t - e["arr"]); orden.append(e["id"]); t += e["S"]
    return orden, sum(wqs)/len(wqs)

jobs = [{"id": "A", "arr": 0, "S": 8}, {"id": "B", "arr": 1, "S": 1}, {"id": "C", "arr": 2, "S": 1}]
print("FIFO:", simular(jobs, lambda e: e["arr"]))
print("SPT:", simular(jobs, lambda e: e["S"]))

06 · Exploración

Laboratorio: mismo lote, cuatro órdenes

Un servidor, N trabajos con arribo, duración S y prioridad ★ (1 = VIP). Elegí la regla y el escenario: mezclado, gigante primero o VIP que llega tarde. La fila muestra cada trabajo (largo = S, ★ = VIP, naranja = el que más esperó). El makespan casi no se mueve; las esperas sí.

Cada bloque es un trabajo J1… con su S; la ★ marca al VIP. El gris previo al bloque es su espera Wq. El naranja es el que más esperó en esa corrida.

Preguntas para explorar

1. En Mezclado con N=5, ¿Wq media con FIFO vs SPT? ¿Makespan? ¿Qué conservó el orden y qué repartió?
2. Pasá a LIFO: ¿quién es el naranja (el que más espera)? ¿Por qué LIFO castiga al primero?
3. En “VIP tarde” con PRIO: ¿Wq del VIP vs FIFO? ¿Qué paga el resto?

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: el próximo según cada regla

Espera con (arr, S, prio): A(0,8,2), B(1,1,2), C(2,1,1). ¿A quién elige cada regla?

esp = [{"id": "A", "arr": 0, "S": 8, "prio": 2}, {"id": "B", "arr": 1, "S": 1, "prio": 2}, {"id": "C", "arr": 2, "S": 1, "prio": 1}]
print("FIFO:", min(esp, key=lambda e: e["arr"])["id"])   # A
print("SPT:", min(esp, key=lambda e: e["S"])["id"])      # B o C
print("PRIO:", min(esp, key=lambda e: (e["prio"], e["arr"]))["id"])  # C

Ejercicio 2: FIFO vs SPT en números

Con A(0,8), B(1,1), C(2,1): ¿Wq media con FIFO y con SPT?

# FIFO: A[0,8) B[8,9) C[9,10): Wq = 0,7,7 -> 4.67
# SPT no expulsivo: A[0,8) igual (nadie lo interrumpe al estar en curso)
print("FIFO:", round((0 + 7 + 7) / 3, 2))  # 4.67

Ejercicio 3: prioridades con desempate

Escribí el key de PRIO con desempate FIFO y usalo en tu simulador.

key_prio = lambda e: (e["prio"], e["arr"])
esp = [{"id": "A", "arr": 0, "S": 1, "prio": 2}, {"id": "B", "arr": 0, "S": 1, "prio": 1}]
print(min(esp, key=key_prio)["id"])  # B: primero prio, luego arr

09 · Síntesis

Ideas para recordar

En el próximo tema abriremos cada regla: FIFO, LIFO y prioridades con sus efectos.