Planificación de CPU

📐 Fundamento

Para comparar algoritmos hace falta medir. Cinco métricas clásicas:

Definiciones formales. Para un proceso que llega en $t_{\text{llegada}}$, comienza a ejecutarse en $t_{\text{inicio}}$ y termina en $t_{\text{fin}}$:

• Tiempo de retorno: $T_r = t_{\text{fin}} - t_{\text{llegada}}$.
• Tiempo de espera: $T_e = T_r - T_{\text{ráfaga}}$ (donde la ráfaga es el tiempo de CPU que el proceso necesita).
• Tiempo de respuesta: $T_{\text{resp}} = t_{\text{inicio}} - t_{\text{llegada}}$.

Trade-offs. Algunos objetivos chocan:

• Maximizar throughput suele aumentar tiempo de espera (priorizás eficiencia, no equidad).
• Minimizar tiempo de respuesta requiere preempción frecuente (más overhead).
• Equidad y eficiencia son a menudo opuestos.

Por eso hay distintos algoritmos: cada uno optimiza distinto.

Apropiativo (preemptive) vs no apropiativo. Un planificador es apropiativo si puede interrumpir un proceso que está ejecutándose para darle el CPU a otro. No apropiativo si una vez que un proceso empieza, sigue hasta que termine o se bloquee voluntariamente.

• Apropiativo: más justo, mejor respuesta, pero más overhead por cambios de contexto.
• No apropiativo: simple, sin overhead, pero un proceso largo monopoliza la CPU.

Los SO modernos son apropiativos.

📐 Fundamento

FCFS es la política más simple: los procesos se atienden en el orden en que llegan. Una cola FIFO, sin más.

• Apropiativo: No.
• Implementación: trivial — una sola cola.
• Justicia: alta (orden de llegada).

Ejemplo.

Diagrama de Gantt:

| P1 (0-24) | P2 (24-27) | P3 (27-30) |

• $T_{\text{espera}}$: P1 = 0, P2 = 24, P3 = 27. Promedio: 17.
• $T_{\text{retorno}}$: P1 = 24, P2 = 27, P3 = 30. Promedio: 27.

Problema célebre — efecto convoy. Si llegan en orden P1 (largo), P2 (corto), P3 (corto), los cortos esperan al largo. Si fuera al revés (P2, P3, P1), el promedio sería mucho menor:

• P2 espera 0, P3 espera 3, P1 espera 6. Promedio espera: 3.

Mismo trabajo total, distinto promedio. La política importa.

Cuándo usar FCFS: sistemas batch sin urgencia, donde la simplicidad pesa más que el rendimiento. Casi nunca en sistemas interactivos.

📐 Fundamento

SJF ejecuta primero el proceso más corto entre los que están listos.

• Apropiativo: versión apropiativa = SRTF (Shortest Remaining Time First).
• Justicia: baja (los largos pueden esperar mucho — starvation).
• Óptimo: demostrablemente minimiza tiempo de espera promedio.

Ejemplo (no apropiativo).

Diagrama:

| P1 (0-7) | P3 (7-8) | P2 (8-12) | P4 (12-16) |

(En t=7 P1 termina; entre los que llegaron, P3 es el más corto.)

Tiempo de espera promedio: $(0 + 6 + 3 + 7)/4 = 4$.

Versión SRTF (apropiativa):

| P1 (0-2) | P2 (2-4) | P3 (4-5) | P2 (5-7) | P4 (7-11) | P1 (11-16) |

• En t=2 llega P2 (ráfaga 4 < restante de P1 = 5). Cambia.
• En t=4 llega P3 (ráfaga 1 < 2 restantes de P2). Cambia.
• En t=5 llega P4 (ráfaga 4 > 2 restantes de P2). P2 sigue.
• En t=7 termina P2. Quedan P1 (5), P4 (4). P4 es más corto.
• En t=11 termina P4. P1 corre hasta 16.

Tiempo de espera promedio: $\approx 3.0$.

El problema de SJF: cómo predecir la ráfaga. Es imposible saber cuánto va a durar un proceso antes de ejecutarlo. La práctica usa promedio histórico (estimación exponencial):

donde $t_n$ es la ráfaga real anterior y $\tau_n$ la estimación previa, $\alpha \in [0, 1]$ pesa cuánto cuenta el reciente.

Starvation. Si llegan procesos cortos sin parar, los largos nunca corren. Es un problema serio. Una solución: aging — aumentar la prioridad del proceso a medida que espera.

📐 Fundamento

Round Robin asigna a cada proceso un cuanto (quantum) de tiempo fijo. Cuando expira, el proceso vuelve al final de la cola y sigue el siguiente.

• Apropiativo: sí, por timer.
• Diseñado para: sistemas interactivos, donde la respuesta importa.
• Justicia: alta (todos reciben CPU regularmente).

Ejemplo con cuanto = 4.

| P1 (0-4) | P2 (4-7) | P3 (7-10) | P1 (10-14) | P1 (14-18) | P1 (18-22) | P1 (22-26) | P1 (26-30) |

Tiempo de espera promedio: $(6 + 4 + 7)/3 = 5.66$.

Trade-off del cuanto:

• Cuanto muy chico → muchos cambios de contexto. El SO gasta más tiempo cambiando que ejecutando.
• Cuanto muy grande → degenera en FCFS (un proceso ocupa la CPU una eternidad).
• Cuanto típico: 10–100 ms en sistemas modernos.

Regla práctica: el cuanto debe ser un poco más grande que la ráfaga típica de un proceso interactivo, así la mayoría termina antes de ser interrumpida.

Costo del cambio de contexto. Aproximadamente 1–10 µs en hardware moderno: guardar registros del proceso saliente, cargar los del entrante, invalidar TLB y caché parcialmente. Si el cuanto fuera 10 µs y el cambio cuesta 10 µs, la mitad del tiempo se va en overhead. Por eso los cuantos son del orden de ms, no µs.

📐 Fundamento

Cada proceso tiene un número de prioridad. El planificador siempre elige al de mayor prioridad entre los listos.

• Apropiativo o no.
• SJF es un caso particular (prioridad = inversa de la ráfaga).
• Las prioridades pueden ser estáticas (fijas) o dinámicas (cambian con el tiempo).

Quién asigna la prioridad:

• Sistema: el kernel decide según comportamiento (CPU-bound vs I/O-bound).
• Usuario: comandos como nice y renice en Unix.

$ nice -n 10 ./mi_programa     # arranca con prioridad baja
$ renice -n -5 -p 1234         # mejorá la prioridad del PID 1234 (root)

En Linux, la "prioridad de niceness" va de -20 (la más alta, solo root) a +19 (la más baja). El default es 0.

Problema: starvation. Igual que SJF — procesos de baja prioridad pueden no ejecutarse nunca si siguen llegando otros prioritarios.

Solución: aging. Aumentar la prioridad efectiva en función del tiempo de espera:

Así un proceso que esperó mucho eventualmente "gana" su turno.

📐 Fundamento

MLFQ es el algoritmo "inteligente" que combina varios anteriores. La idea: aprender del comportamiento de cada proceso.

Estructura:

• Hay varias colas (típicamente 3–8), con distintas prioridades.
• Cuanto más alta la cola, más corto el cuanto.
• Procesos nuevos entran en la cola más alta.
• Si un proceso usa todo su cuanto, baja una cola (parece CPU-bound, "castiguelo").
• Si un proceso libera CPU antes de su cuanto (I/O), se queda o sube (parece I/O-bound, "favorezcalo").
• Periódicamente, todos los procesos vuelven arriba (evitar starvation).

Por qué funciona:

• Procesos interactivos (editores, navegadores) hacen mucha I/O y rara vez consumen su cuanto entero. Se quedan en colas altas → respuesta rápida.
• Procesos batch (compilación, simulación) consumen cuantos enteros. Bajan a colas más bajas → no entorpecen a los interactivos.
• Sin saber a priori qué tipo es cada proceso, el sistema lo clasifica observando.

Variaciones. Los detalles cambian: cuántas colas, qué cuanto en cada una, cuándo subir, cuándo bajar, qué tan seguido "resetear". UNIX tradicional, Windows NT, Solaris — todos usan variantes de MLFQ.

📐 Fundamento

Hasta acá hablamos como si hubiera una CPU. La realidad: tu computadora tiene 4, 8, 16 o más núcleos. Eso agrega complicaciones:

Decisiones nuevas:

1. ¿Cada núcleo tiene su propia cola o hay una cola global?
2. ¿Si un núcleo está ocioso, roba trabajo de otros?
3. ¿Mantener un proceso en el mismo núcleo (afinidad) o moverlo libremente?

Afinidad de CPU. Cuando un proceso corre en el núcleo 0, deja datos en su caché L1/L2. Si lo movés al núcleo 3, el caché está frío — todo el trabajo cuesta más. Por eso los planificadores modernos prefieren mantener procesos en el mismo núcleo (afinidad), aunque a veces hay que reequilibrar.

Linux: taskset permite forzar afinidad.

$ taskset -c 0,1 ./mi_programa   # corré solo en núcleos 0 y 1
$ taskset -p <pid>                # consultar afinidad actual

Work stealing. Cuando un núcleo se queda sin trabajo, busca en las colas de otros núcleos y "roba" tareas. Es la técnica clásica de schedulers paralelos modernos (Go, Rust Tokio, .NET ThreadPool).