FIFO, LIFO y prioridades

01 · Punto de partida

Tres llamados, tres ganadores

Llegan juntos un jubilado (trámite de 6 min), dos jóvenes (1 min cada uno) y una urgencia (prio 1). Con FIFO sale el jubilado primero y los jóvenes esperan 6 y 7 min. Con LIFO sale el último joven y el jubilado —que llegó primero— espera hasta el final. Con prioridades la urgencia salta a todos aunque haya llegado última.

El lote y el trabajo son idénticos; el orden decide la varianza: FIFO la contiene, LIFO la dispara, prioridades la concentran en la clase baja. Este tema abre cada regla y mide su efecto.

• ¿Qué cambia entre atender por llegada, por pila o por clase?
• ¿Cuál minimiza la queja, cuál la media y cuál salva al urgente?
• ¿Quién puede quedar esperando para siempre con cada regla?
• ¿Cómo programo las tres sin reescribir el simulador?

02 · Definición

Cola, pila y clases

03 · El corazón: varianza e inanición

Misma media global, distinto reparto

Con llegadas y servicios fijos, las tres reglas no expulsivas terminan el lote al mismo tiempo. Pero mirá trabajo por trabajo: con FIFO las esperas crecen parejo; con LIFO el primero paga todo y el último nada; con PRIO el VIP paga casi cero y la clase 3 paga doble. La media global apenas se mueve (SPT la movería, Tema 25); la máxima y la del VIP se mueven muchísimo.

1. 1
   FIFO: orden de llegada.

   Cada fin toma al de menor arr. Nadie salta: la espera máxima queda acotada por el lote.

2. 2
   LIFO: orden inverso.

   Cada fin toma al de mayor arr. El primero del lote queda al fondo: si siguen llegando, puede no salir nunca.

3. 3
   PRIO: clase primero.

   Cada fin toma (clase, arr) mínimo. El VIP que llega tarde igual adelanta a los comunes que esperan.

4. 4
   Medir tres números.

   Media (eficiencia), máxima (justicia) y VIP (urgencia). Una regla se elige según cuál de los tres pese más.

LCFS-PR

LIFO con expulsión y reanudación: el que llega interrumpe y luego se retoma. Muy tratable en M/M/1 teórico; en la calle, caótico.

Inversión de prioridades

Un común en servicio bloquea al VIP que llega (no expulsivo). Se mitiga con expulsión o con cuanto corto (Round-Robin).

Envejecimiento (aging)

La clase baja sube de rango cuanto más espera: evita inanición sin quitarle el filo al VIP. Típico en schedulers.

SIRO / RANDOM

Sorteo entre los que esperan: referencia “neutral”. Su varianza está entre FIFO y LIFO; sirve de testigo en experimentos.

04 · Ejemplos

Dónde vive cada una

1. 1
   Ventanilla única (FIFO).

   Número por orden de llegada. El cartel “se atiende por orden” es FIFO escrito en la pared.

2. 2
   Deshacer y migas (LIFO).

   Ctrl+Z revierte lo último; la pila de llamadas retorna lo más reciente. Ahí LIFO es justicia estructural.

3. 3
   Guardia y soporte premium (PRIO).

   Triage 1-2-3 y SLA gold/silver: el VIP adelanta sin pedir permiso. La clase baja necesita aging o cuota.

05 · Representación en Python

Cola, pila y clases con la misma espera

FIFO es popleft, LIFO es pop, PRIO es “el de menor (clase, arr)”. Tres selectores, un solo motor.

# Tres próximos, misma espera
from collections import deque
esp = [{"id": "A", "arr": 0, "prio": 2}, {"id": "B", "arr": 1, "prio": 2}, {"id": "C", "arr": 2, "prio": 1}]
cola = deque(sorted(esp, key=lambda e: e["arr"]))
print("FIFO atiende:", cola[0]["id"], "| LIFO atiende:", cola[-1]["id"])
print("PRIO atiende:", min(esp, key=lambda e: (e["prio"], e["arr"]))["id"])

# Lote completo con regla intercambiable (c=1, no expulsiva)
def correr(jobs, key):
    t, ws = 0.0, {}
    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)
        ws[e["id"]] = round(t - e["arr"], 2); orden.append(e["id"]); t += e["S"]
    return orden, ws

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}]
for n, k in [("FIFO", lambda e: e["arr"]), ("LIFO", lambda e: -e["arr"]), ("PRIO", lambda e: (e["prio"], e["arr"]))]:
    print(n, correr(jobs, k))

06 · Exploración

Laboratorio: quién paga cada regla

Un servidor, N trabajos con arribo, S y clase ★ (1 = VIP). Probá FIFO, LIFO y PRIO en tres escenarios: lote (todos en 0), flujo (escalonados) y VIP tarde. El bloque naranja es el que más esperó; el gris previo es su Wq. Mirá media, máxima y VIP: el makespan casi no se mueve.

Bloque = servicio S con su J; ★ = VIP. Gris previo = espera. Naranja = la espera máxima de la corrida.

Preguntas para explorar

1. En Lote con N=5, ¿orden y máxima con FIFO vs LIFO? ¿Media? ¿Qué invirtió LIFO?
2. En Flujo, ¿quién es el naranja con LIFO? ¿Por qué sufre el primero?
3. En VIP tarde con PRIO: ¿Wq del VIP vs FIFO? ¿Qué le pasa a la máxima del resto?

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: lote en t=0

A(0,6), B(0,1), C(0,1) juntos. ¿Orden y Wq con cada regla (PRIO: C es VIP)?

# FIFO: A,B,C -> Wq 0,6,7 | LIFO: C,B,A -> 0,1,2 | PRIO(C VIP): C,B,A -> 0,1,2
for wq in [[0, 6, 7], [2, 1, 0]]:
    print("Wq media:", round(sum(wq)/len(wq), 2))  # 4.33 vs 1.0

Ejercicio 2: el primero sufre LIFO

A(0,2), B(1,2), C(2,2): ¿Wq de A con FIFO y con LIFO?

# FIFO: A[0,2) B[2,4) C[4,6): A espera 0. LIFO: A[0,2) C[2,4) B[4,6): A espera 0...
# ...pero si A llega y la pila no para: probá A(0,2),B(0.5,2),C(1,2),D(1.5,2)
print("Con flujo continuo, LIFO deja a A al fondo: simulalo en el lab.")

Ejercicio 3: PRIO con desempate

Dos VIP juntos: ¿quién primero? Escribí el key y comprobalo.

esp = [{"id": "V1", "arr": 0, "prio": 1}, {"id": "V2", "arr": 1, "prio": 1}, {"id": "C", "arr": 0, "prio": 2}]
print(min(esp, key=lambda e: (e["prio"], e["arr"]))["id"])  # V1

09 · Síntesis

Ideas para recordar

En el próximo tema cerraremos la cola por el otro extremo: la capacidad de una cola.