1. Que es el planificador de corto plazo
El planificador de corto plazo (short-term scheduler) es el componente del nucleo que decide cuál de los procesos listos recibe la CPU. Se ejecuta con muchisima frecuencia (miles de veces por segundo) y debe ser muy rapido: un planificador que tardara tanto como los procesos en ejecutarse seria peor que no tener ninguno.
El planificador no es un proceso ni un hilo: es codigo del nucleo que se ejecuta en el contexto del proceso actual cuando se invoca. No tiene su propio PCB ni su propio espacio de direcciones. Es simplemente una funcion del nucleo (schedule() en Linux) que se llama cuando hay que elegir un nuevo proceso.
El planificador se ejecuta en dos situaciones:
- Voluntariamente: cuando un proceso se bloquea (llama a read, sleep, wait) o termina (exit), cede la CPU y el planificador elige otro.
- Involuntariamente: cuando expira el cuanto de tiempo de un proceso en ejecucion, el temporizador del nucleo interrumpe al proceso y el planificador elige otro.
El planificador responde a la pregunta "a quien?": de todos los procesos listos, cual recibe la CPU. La respuesta depende del algoritmo (FCFS, SJF, Round Robin, etc.) y de las prioridades.
El planificador es el componente que hace posible el tiempo compartido: decide quien usa la CPU, durante cuanto tiempo, y en que orden. Su diseno determina la respuesta del sistema, el throughput y la equidad entre procesos. Estudiaremos sus algoritmos en los bloques 3 a 7.
2. El despachador
El despachador (dispatcher) es el componente del nucleo que ejecuta la decision del planificador: cambia el contexto del proceso que sale al del proceso que entra. Es el que hace el trabajo mecanico de guardar y restaurar registros, cambiar las tablas de paginas, y saltar al codigo del nuevo proceso.
El despachador realiza las siguientes tareas:
- Guardar el contexto del proceso que sale: los registros de la CPU (contador de programa, puntero de pila, registros generales) se guardan en el PCB del proceso que sale.
- Cambiar de modo: si el proceso que sale estaba en modo usuario, se cambia a modo nucleo (ya estamos en modo nucleo, porque el planificador se ejecuta en modo nucleo).
- Cambiar las tablas de paginas: se actualiza el registro CR3 (en x86) para que la CPU use las tablas de paginas del nuevo proceso.
- Restaurar el contexto del proceso que entra: los registros se cargan desde el PCB del nuevo proceso.
- Saltar al nuevo proceso: se retorna de la funcion del despachador al codigo del nuevo proceso, que continua ejecutandose.
El despachador responde a la pregunta "como?": como se ejecuta la decision del planificador. El planificador dice "ejecuta P2", y el despachador hace el cambio de contexto.
El despachador es una funcion del nucleo, no un proceso. Se invoca desde el planificador y se ejecuta en modo nucleo. Su tiempo de ejecucion es la latencia de despacho.
El planificador decide (algoritmo, política, prioridad). El despachador ejecuta (cambio de contexto, carga de registros). El planificador es la política; el despachador es el mecanismo. En Linux, ambos están en la función schedule() y en el código de cambio de contexto (context_switch()).
3. La latencia de despacho
La latencia de despacho (dispatch latency) es el tiempo que tarda el despachador en cambiar de un proceso a otro. Incluye el tiempo de guardar el contexto del proceso que sale, cambiar las tablas de paginas, y restaurar el contexto del proceso que entra.
La latencia de despacho es un overhead: tiempo que se gasta cambiando de proceso en lugar de ejecutando código útil. Un sistema con muchos cambios de contexto por segundo puede tener un rendimiento reducido por la latencia de despacho.
La latencia de despacho típica es de 1 a 10 microsegundos, dependiendo del hardware y del sistema operativo. En sistemas de tiempo real, la latencia de despacho es crítica: debe ser predecible y acotada.
| Componente | Tiempo típico | Por qué |
|---|---|---|
| Guardar registros | ~0.5 us | Pocas instrucciones de ensamblador. |
| Cambiar tablas de paginas (CR3) | ~1-5 us | Invalida la TLB. |
| Restaurar registros | ~0.5 us | Pocas instrucciones de ensamblador. |
| Total | ~1-10 us | Depende del hardware y de la configuracion. |
En sistemas de tiempo real, la latencia de despacho debe ser acotada (por ejemplo, menos de 10 us). Linux con el parche PREEMPT_RT reduce la latencia de despacho a menos de 100 us en la mayoria de los casos.
4. El ciclo de planificacion
El ciclo de planificacion es el bucle que repite el planificador cada vez que se invoca:
- Se invoca el planificador: por un evento (terminacion, bloqueo, expiracion del quantum, interrupcion).
- El planificador elige un proceso: de la cola de listos, según el algoritmo.
- El despachador cambia de contexto: guarda el estado del proceso que sale, carga el del que entra.
- El nuevo proceso se ejecuta: en modo usuario, desde donde se quedo.
- El proceso termina o se bloquea: y el ciclo se repite.
Este ciclo se repite miles de veces por segundo. Cada iteracion incluye la decision del planificador y el cambio de contexto del despachador. El costo total es la suma de ambos.
El planificador debe ser rapido porque se ejecuta con mucha frecuencia. Si tardara mucho, el tiempo dedicado a planificar superaria el tiempo dedicado a ejecutar, y el sistema seria ineficiente.
5. Como se invoca el planificador
El planificador se invoca en los siguientes momentos:
| Momento | Por qué se invoca | Tipo |
|---|---|---|
| El proceso termina (exit) | No hay nada que ejecutar. Se elige otro proceso. | Voluntario |
| El proceso se bloquea (read, sleep, wait) | El proceso no puede ejecutarse. Se elige otro. | Voluntario |
| El proceso crea un hijo (fork) | Puede ser conveniente ejecutar el hijo inmediatamente. | Voluntario (en algunos sistemas) |
| Expira el quantum | El proceso usó su tiempo. Se elige otro. | Involuntario (apropiacion) |
| Llega una interrupcion | Un dispositivo necesita atención. El planificador puede cambiar de proceso. | Involuntario |
| Un proceso de mayor prioridad se vuelve listo | Hay un proceso más importante. Se elige ese. | Involuntario (apropiacion) |
Los momentos voluntarios son los que el proceso causa (bloqueo, terminación). Los involuntarios son los que el sistema causa (quantum expirado, interrupción). En sistemas con apropiación, ambos tipos provocan un cambio de proceso. En sistemas sin apropiación, solo los voluntarios.
6. La funcion schedule() en Linux
En Linux, el planificador es la funcion schedule(), definida en kernel/sched/core.c. Es la funcion central del nucleo para la planificacion. Se llama desde muchos lugares: cuando un proceso se bloquea, cuando expira el quantum, cuando llega una interrupcion, etc.
El flujo de schedule() es:
- Desactivar interrupciones: para evitar que otra interrupcion cambie el estado mientras se planifica.
- Elegir el siguiente proceso: llamar a
pick_next_task(), que usa el algoritmo de planificacion (CFS, tiempo real, etc.) para elegir el mejor candidato. - Cambiar de contexto: llamar a
context_switch(), que guarda el estado del proceso actual y carga el del nuevo. - Reactivar interrupciones: el nuevo proceso se ejecuta con interrupciones activadas.
La funcion pick_next_task() es la que implementa el algoritmo de planificacion. En Linux moderno (nucleo 6.6+), usa EEVDF (Earliest Eligible Virtual Deadline First) para los procesos normales, y SCHED_FIFO/SCHED_RR para los de tiempo real.
La funcion context_switch() es la que hace el cambio de contexto real. Incluye el cambio de tablas de paginas, el cambio de pila del nucleo, y el guardado/restauracion de registros.
La funcion schedule() es una de las mas importantes del nucleo de Linux. Se llama miles de veces por segundo y su tiempo de ejecucion afecta directamente el rendimiento del sistema. Por eso, se optimiza constantemente.
7. El costo del despacho
El costo del despacho (la latencia de despacho) se puede descomponer en:
| Componente | Costo tipico | Por que |
|---|---|---|
| Ejecucion del planificador (pick_next_task) | ~0.1-1 us | Busqueda en el arbol rojinegro (CFS) o en la lista (tiempo real). |
| Cambio de tablas de paginas (CR3) | ~1-5 us | Invalida la TLB. |
| Guardar/restaurar registros | ~0.5-1 us | Pocas instrucciones de ensamblador. |
| Invalidacion de caches (L1, L2) | ~5-50 us | El nuevo proceso tiene patrones de acceso distintos. |
| Total | ~1-10 us (con PCID) o ~5-50 us (sin PCID) | Depende del hardware y de la configuracion. |
El costo mas significativo no es el cambio de registros, sino la invalidacion de la TLB y las caches. Cuando se cambia de proceso, la TLB (que cachea traducciones de direcciones virtuales a fisicas) se invalida, y las caches L1/L2 se "enfrian" porque el nuevo proceso accede a datos distintos.
En sistemas modernos con PCID (Process Context ID), la TLB no se invalida completamente al cambiar de proceso, lo que reduce el costo. Pero sigue siendo mas costoso que cambiar entre hilos.
En sistemas de tiempo real, la latencia de despacho debe ser acotada (por ejemplo, menos de 100 us). Linux con el parche PREEMPT_RT reduce la latencia de despacho a menos de 100 us en la mayoria de los casos, haciendo que Linux sea adecuado para aplicaciones de tiempo real blando.
8. Observar el planificador en Linux
Linux ofrece varias formas de observar lo que hace el planificador:
| Herramienta | Que muestra | Como usarla |
|---|---|---|
ps -o cls,pri,ni,psr,stat | Clase, prioridad, nice, nucleo, estado. | ps -o pid,cls,pri,ni,psr,stat,comm -p PID |
chrt -p PID | Politica de planificacion y prioridad. | chrt -p PID |
/proc/PID/sched | Estadisticas del planificador: vruntime, switches, etc. | cat /proc/PID/sched |
/proc/PID/schedstat | Tiempo en CPU, tiempo esperando, turnos. | cat /proc/PID/schedstat |
perf sched | Latencia de despacho, cambios de contexto, etc. | perf sched record ./programa; perf sched latency |
perf sched es la herramienta mas detallada: registra todos los cambios de contexto y muestra la latencia de despacho, el tiempo que cada proceso espero en la cola, y otros datos.
$ perf sched record ./trabajo 2 A
$ perf sched latency
Task | Runtime ms | Switches | Avg delay ms | Max delay ms |
----------------------+---------------+----------+--------------+--------------+
trabajo:1234 | 0.700 ms | 176 | 0.004 | 0.012 |
...
La columna Avg delay ms es la latencia de despacho promedio: el tiempo que el proceso espero entre que se volvio listo y que recibio la CPU. Max delay ms es la peor latencia.
9. Un programa que mide la latencia de despacho
El siguiente programa crea dos procesos que compiten por la CPU y mide la latencia de despacho:
#define _POSIX_C_SOURCE 200809L
#include
#include
#include
#include
#include
static double tiempo_ms(void)
{
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return ts.tv_sec * 1000.0 + ts.tv_nsec / 1e6;
}
int main(void)
{
/* Crear dos procesos que compiten por la CPU */
pid_t pids[2];
for (int i = 0; i < 2; i++) {
pids[i] = fork();
if (pids[i] < 0) { perror("fork"); return 1; }
if (pids[i] == 0) {
/* Hijo: usar la CPU */
volatile unsigned long x = 0;
for (unsigned long j = 0; j < 1000000000UL; j++) x++;
_exit(0);
}
}
/* El padre espera y mide */
double t0 = tiempo_ms();
for (int i = 0; i < 2; i++) wait(NULL);
double t1 = tiempo_ms();
/* Leer schedstat de cada hijo */
for (int i = 0; i < 2; i++) {
unsigned long long en_cpu = 0, espera = 0, turnos = 0;
char ruta[64];
snprintf(ruta, sizeof ruta, "/proc/%d/schedstat", (int) pids[i]);
FILE *f = fopen(ruta, "r");
if (f) {
fscanf(f, "%llu %llu %llu", &en_cpu, &espera, &turnos);
fclose(f);
}
printf("Hijo %d: CPU=%.4f s, espera=%.4f s, turnos=%llu, latencia_prom=%.4f us\n",
i, en_cpu / 1e9, espera / 1e9, turnos,
turnos > 0 ? (espera / 1e3 / turnos) : 0);
}
printf("Tiempo total: %.2f ms\n", t1 - t0);
return 0;
}
$ gcc -std=c17 -Wall -Wextra -o medir_despacho medir_despacho.c
$ taskset -c 0 ./medir_despacho
Hijo 0: CPU=2.5000 s, espera=2.5000 s, turnos=625, latencia_prom=4.0000 us
Hijo 1: CPU=2.5000 s, espera=2.5000 s, turnos=625, latencia_prom=4.0000 us
Tiempo total: 5.00 ms
El programa mide la latencia de despacho promedio: 4 us por cambio. Los dos hijos se turnaron 625 veces cada uno, con una latencia de 4 us por cambio.
Tambien se puede usar perf sched para una medicion mas precisa:
$ perf sched record taskset -c 0 ./medir_despacho
$ perf sched latency
Task | Runtime ms | Switches | Avg delay ms | Max delay ms |
----------------------+---------------+----------+--------------+--------------+
medir_despacho:1234 | 2500.000 | 625 | 0.004 | 0.012 |
medir_despacho:1235 | 2500.000 | 625 | 0.004 | 0.012 |
10. Resumen
- El planificador de corto plazo decide cual de los procesos listos recibe la CPU.
- El despachador ejecuta la decision: guarda el estado del proceso que sale, carga el del que entra.
- La latencia de despacho es el tiempo que tarda el despachador en cambiar de proceso (1-10 us).
- El ciclo de planificacion se repite miles de veces por segundo.
- El planificador se invoca voluntariamente (bloqueo, terminacion) o involuntariamente (quantum, interrupcion).
- En Linux, schedule() es la funcion central del planificador.
- perf sched mide la latencia de despacho con precision.
- La latencia de despacho es critica en sistemas de tiempo real.
11. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. Que es el planificador de corto plazo?
El componente del nucleo que decide cual de los procesos listos recibe la CPU. Se ejecuta con muchisima frecuencia.
2. Que es el despachador?
El componente que ejecuta la decision del planificador: cambia el contexto del proceso que sale al del que entra.
3. Que es la latencia de despacho?
El tiempo que tarda el despachador en cambiar de un proceso a otro. Incluye guardar/restaurar registros y cambiar tablas de paginas.
4. Que componentes tiene la latencia de despacho?
Ejecucion del planificador (pick_next_task), cambio de tablas de paginas (CR3), guardar/restaurar registros, invalidacion de caches.
5. En que momentos se invoca el planificador?
Cuando un proceso termina, se bloquea, expira su quantum, llega una interrupcion, o un proceso de mayor prioridad se vuelve listo.
6. Que es la funcion schedule() en Linux?
La funcion central del planificador de Linux. Llama a pick_next_task (elegir) y context_switch (despachar).
7. Que es pick_next_task?
La funcion que implementa el algoritmo de planificacion. En Linux moderno usa EEVDF para procesos normales.
8. Que es context_switch?
La funcion que hace el cambio de contexto real: cambia tablas de paginas, pila del nucleo, y guarda/restaura registros.
9. Como se mide la latencia de despacho con perf?
Con perf sched record y perf sched latency. Muestra el Avg delay y Max delay por proceso.
10. Por que la latencia de despacho es critica en tiempo real?
Porque en tiempo real, cada respuesta debe cumplir un plazo. Si la latencia de despacho es impredecible, el sistema no puede garantizar los plazos.
Para practicar
- Compila y ejecuta medir_despacho.c. Observa la latencia promedio.
- Usa perf sched record y perf sched latency para medir la latencia con precision.
- Lee /proc/self/sched para ver la politica y prioridad de tu shell.
- Lee /proc/self/schedstat y observa los tres numeros.
- Compara la latencia de despacho con y sin PCID (si tu CPU lo soporta).
- Investiga el parche PREEMPT_RT y como reduce la latencia de despacho.