Multiprogramación y planificación

1. Un trabajo, una CPU, tres procesos

Empecemos con un programa que no hace otra cosa que gastar CPU. Recibe cuántas unidades de trabajo debe hacer (una unidad son trescientos millones de sumas, unos 0,34 segundos en la máquina de pruebas), y al terminar informa cuánto tardó, cuánta CPU usó y cuánto tiempo pasó esperando en la cola sin ejecutarse. Ese último dato lo lee de /proc/self/schedstat, un archivo donde el núcleo lleva la cuenta de lo que el planificador hizo con el proceso:

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

#define VUELTAS_POR_UNIDAD 300000000UL      /* una unidad de trabajo ~ 0,3 s */

static double segundos(clockid_t reloj)
{
    struct timespec t;
    clock_gettime(reloj, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}

int main(int argc, char *argv[])
{
    int unidades = argc > 1 ? atoi(argv[1]) : 1;
    const char *nombre = argc > 2 ? argv[2] : "trabajo";
    double inicio = segundos(CLOCK_REALTIME);
    const char *t0 = getenv("T0");              /* instante en que se lanzó el lote */
    double origen = t0 ? atof(t0) : inicio;

    volatile unsigned long suma = 0;
    for (unsigned long i = 0; i < unidades * VUELTAS_POR_UNIDAD; i++)
        suma += i;

    double fin = segundos(CLOCK_REALTIME);
    double cpu = segundos(CLOCK_PROCESS_CPUTIME_ID);

    /* /proc/self/schedstat: tiempo en CPU, tiempo esperando en la cola y turnos */
    unsigned long long en_cpu = 0, espera = 0, turnos = 0;
    FILE *f = fopen("/proc/self/schedstat", "r");
    if (f) {
        if (fscanf(f, "%llu %llu %llu", &en_cpu, &espera, &turnos) != 3)
            en_cpu = espera = turnos = 0;
        fclose(f);
    }

    printf("%-8s unidades=%d  terminó en %5.2f s  CPU usada %4.2f s  esperó en la cola %5.2f s  turnos %llu\n",
           nombre, unidades, fin - origen, cpu, espera / 1e9, turnos);
    return 0;
}

El programa lee la variable de entorno T0 si existe: así varios procesos lanzados juntos pueden medir su tiempo desde el mismo instante, el de la salida de la shell, y no desde el momento en que cada uno empezó. Lo compilamos y lo ejecutamos una vez, obligándolo con taskset -c 0 a usar solo el núcleo 0:

$ gcc -std=c17 -Wall -Wextra -o trabajo trabajo.c
$ taskset -c 0 ./trabajo 1 solo
solo     unidades=1  terminó en  0.34 s  CPU usada 0.34 s  esperó en la cola  0.00 s  turnos 8

Nada de espera: el proceso tuvo el núcleo para él y tardó exactamente lo que necesita, 0,34 s. Ahora lanzamos tres a la vez en el mismo núcleo, cada uno con dos unidades de trabajo (0,69 s de CPU):

$ export T0=$(date +%s.%N)
$ taskset -c 0 ./trabajo 2 A & taskset -c 0 ./trabajo 2 B & taskset -c 0 ./trabajo 2 C & wait
C        unidades=2  terminó en  2.09 s  CPU usada 0.70 s  esperó en la cola  1.39 s  turnos 175
A        unidades=2  terminó en  2.10 s  CPU usada 0.70 s  esperó en la cola  1.39 s  turnos 176
B        unidades=2  terminó en  2.09 s  CPU usada 0.70 s  esperó en la cola  1.40 s  turnos 176

Cada proceso necesitaba 0,70 s de CPU, pero ninguno terminó antes de los 2,09 s. La diferencia es exactamente el tiempo que pasó listo para ejecutarse y sin CPU: 0,70 s de trabajo más 1,39 s de espera suman los 2,09 s. Fíjate también en la columna turnos: el núcleo les dio la CPU unas 175 veces a cada uno, es decir, el reparto se hizo en turnos de unos 4 ms. Los tres avanzaron a la vez, pero a un tercio de la velocidad.

2. El orden importa

En el experimento anterior los tres procesos eran idénticos, y el reparto equitativo era razonable. Pero ¿qué ocurre si los trabajos son de distinto tamaño? Lanzamos tres con 4, 2 y 1 unidades (1,38 s, 0,69 s y 0,34 s de CPU) de tres formas distintas, siempre en el núcleo 0 y midiendo todos desde el mismo origen. Primero, todos a la vez, dejando que el sistema los reparta:

$ export T0=$(date +%s.%N)
$ taskset -c 0 ./trabajo 4 A & taskset -c 0 ./trabajo 2 B & taskset -c 0 ./trabajo 1 C & wait
C        unidades=1  terminó en  1.07 s  CPU usada 0.35 s  esperó en la cola  0.71 s  turnos 88
B        unidades=2  terminó en  1.75 s  CPU usada 0.70 s  esperó en la cola  1.05 s  turnos 175
A        unidades=4  terminó en  2.44 s  CPU usada 1.39 s  esperó en la cola  1.05 s  turnos 183

Después, uno tras otro, empezando por el más grande (el orden en que los lanzamos, A, B, C) y empezando por el más chico (C, B, A):

$ export T0=$(date +%s.%N)
$ taskset -c 0 ./trabajo 4 A; taskset -c 0 ./trabajo 2 B; taskset -c 0 ./trabajo 1 C
A        unidades=4  terminó en  1.38 s  CPU usada 1.38 s  esperó en la cola  0.00 s  turnos 6
B        unidades=2  terminó en  2.07 s  CPU usada 0.69 s  esperó en la cola  0.00 s  turnos 8
C        unidades=1  terminó en  2.41 s  CPU usada 0.34 s  esperó en la cola  0.00 s  turnos 4
$ export T0=$(date +%s.%N)
$ taskset -c 0 ./trabajo 1 C; taskset -c 0 ./trabajo 2 B; taskset -c 0 ./trabajo 4 A
C        unidades=1  terminó en  0.35 s  CPU usada 0.34 s  esperó en la cola  0.00 s  turnos 3
B        unidades=2  terminó en  1.04 s  CPU usada 0.69 s  esperó en la cola  0.00 s  turnos 6
A        unidades=4  terminó en  2.42 s  CPU usada 1.38 s  esperó en la cola  0.00 s  turnos 8

(En las dos últimas ejecuciones esperó en la cola vale cero porque cada proceso no existía mientras esperaba su turno: lo lanzó la shell cuando el anterior terminó. Lo que le importa a un usuario es el tiempo que pasó desde que quiso ejecutarlo, y ese lo da la columna terminó en.) Reunimos los tres resultados:

Tres observaciones, que son el corazón de este curso:

• El trabajo total es el mismo. La CPU estuvo ocupada unos 2,4 s en los tres casos. Planificar no hace que la máquina vaya más rápido ni que se haga más trabajo.
• Lo que cambia es cuándo termina cada uno. El proceso C, de una unidad, esperó 2,41 s en el primer orden y solo 0,35 s en el último. El proceso A, al revés, terminó primero en el primer orden y último en el tercero.
• El promedio también cambia. Poner los trabajos cortos primero redujo el tiempo medio de 1,95 s a 1,27 s, un 35 % menos, sin tocar una sola instrucción de los programas.

Esa es la razón de ser del planificador. No hay un orden «correcto» en abstracto: hay órdenes que favorecen unas cosas (que el trabajo corto termine rápido, que nadie espere demasiado, que la máquina no se quede ociosa) y otros que favorecen otras. El curso consiste en conocer las políticas posibles, medir qué favorece cada una y entender cuál usa Linux.

3. Por qué hay varios procesos en memoria

Hasta aquí todos los procesos usaban la CPU sin parar. Los programas reales no son así: leen del disco, esperan datos de la red, esperan una tecla. Mientras un proceso espera una operación de entrada/salida, la CPU no tiene nada que hacer por él. Si el sistema tuviera un único proceso en memoria, la CPU quedaría ociosa durante toda esa espera, millones de ciclos que se perderían.

La solución es la multiprogramación: mantener varios procesos cargados a la vez, para que cuando uno se bloquea haya otro listo para recibir la CPU. Un modelo sencillo permite cuantificar la ganancia. Supón que cada proceso pasa una fracción p de su tiempo esperando entrada/salida, y que las esperas de los distintos procesos son independientes. La probabilidad de que todos estén esperando a la vez, con n procesos en memoria, es pⁿ, y por lo tanto:

Utilización de la CPU = 1 − pⁿ, donde p es la fracción de tiempo que cada proceso espera entrada/salida y n es el grado de multiprogramación (cuántos procesos hay en memoria).

Con procesos que esperan E/S el 80 % del tiempo (p = 0,8), una cifra normal para programas interactivos o que leen mucho del disco, la tabla es:

Con un solo proceso la CPU está ociosa el 80 % del tiempo; con diez, solo un 11 %. Cada proceso adicional ayuda, pero cada vez menos. El modelo es una simplificación (las esperas de los procesos no son realmente independientes, y mantener muchos procesos cuesta memoria), pero deja una idea clara: con multiprogramación, la CPU casi siempre tiene algo que ejecutar, y por eso hace falta decidir qué. Cuando solo hay un proceso listo, no hay nada que decidir; cuando hay varios, empieza el problema de la planificación.

4. Qué decide el planificador

En el tema 8 del curso anterior viste que los procesos listos esperan en la cola de listos y que el planificador elige uno. Veamos ahora esa decisión con más precisión. Este diagrama resume el recorrido de un proceso por el sistema y marca dónde interviene el planificador:

Cada vez que la CPU queda libre, o cuando algo hace sospechar que conviene cambiar de proceso, el planificador responde a tres preguntas:

1. ¿A quién? De todos los procesos listos, cuál recibe la CPU. Es la decisión central: por orden de llegada, el más corto, el de mayor prioridad, el que menos CPU recibió hasta ahora. cuál
2. ¿Por cuánto tiempo? Hasta que termine o pida entrada/salida, o durante un intervalo fijo (el quantum) tras el cual se le quita la CPU y se elige de nuevo. cuánto
3. ¿En qué núcleo? En una máquina con varios procesadores hay que elegir también dónde ejecutarlo, equilibrando la carga sin perder los datos que el proceso dejó en la caché de cada núcleo. dónde

Las dos primeras preguntas definen los algoritmos clásicos de los bloques 3 a 7; la tercera es el tema del bloque 8. Observa que el planificador no crea trabajo: solo reparte la CPU entre procesos que ya existen y ya están listos. Y que su decisión se repite miles de veces por segundo, por lo que tiene que ser muy rápida: un planificador que tardara tanto como los procesos en ejecutarse sería peor que no tener ninguno.

5. Probar con un simulador

Los números del experimento dependen de la máquina, pero el razonamiento es aritmética pura, y se puede jugar con él. Este simulador ejecuta tres procesos uno tras otro, sin interrupciones, en el orden que elijas. Todos llegan al instante 0. Para cada proceso calcula el tiempo de espera (cuánto pasó en la cola antes de recibir la CPU) y el tiempo de retorno (cuánto pasó desde que llegó hasta que terminó). Esas dos métricas se estudian a fondo en el bloque 2. Los valores iniciales, 24, 3 y 3, son un ejemplo clásico: un proceso largo y dos cortos.

Prueba con el orden P1, P2, P3: el proceso largo va primero y los dos cortos esperan 24 y 27 unidades, con una espera promedio de 17. Cámbialo a P2, P3, P1 y la espera promedio baja a 3, aunque se hizo exactamente el mismo trabajo. Lo que ocurrió se llama efecto convoy y lo estudiaremos en el tema 11. Prueba también a poner tres ráfagas iguales: entonces el orden no cambia nada, porque no hay ninguno «más corto» al que dar prioridad.

6. Objetivos que compiten

Si existiera un orden que fuera el mejor para todos, la planificación sería un problema resuelto. No existe, porque distintos usos de la máquina quieren cosas distintas, y a menudo contrarias:

En consecuencia, un sistema de propósito general como Linux no usa un único algoritmo, sino varias clases de planificación con reglas distintas, y un reparto que equilibra a las más comunes (bloque 10). Estudiaremos cada familia de algoritmos viendo qué favorece y a quién deja en desventaja.

7. Tres niveles de planificación

La palabra «planificador» se usa para tres decisiones distintas, que ocurren con frecuencias muy diferentes. Este curso se ocupa de la última:

Los dos primeros regulan cuántos procesos hay en memoria, es decir, el grado de multiprogramación; los estudia el curso de gestión de memoria. El de corto plazo es el que elige cuál de ellos usa la CPU, y por eso se lo llama también planificador de la CPU. Cuando en este curso digamos «el planificador», sin más, nos referimos a él.

8. Ver la planificación en Linux

Linux ofrece varias formas de mirar lo que el planificador hace. Ya usaste una, /proc/self/schedstat. Las demás permiten ver la política y la prioridad de un proceso. Las salidas son de un Ubuntu en WSL2 con núcleo 6.6.87 y 16 procesadores lógicos:

$ chrt -p $$
pid 453's current scheduling policy: SCHED_OTHER
pid 453's current scheduling priority: 0
$ ps -o pid,cls,pri,ni,psr,stat,comm -p $$
    PID CLS PRI  NI PSR STAT COMMAND
    453  TS  19   0  14 S+   bash
$ ps -e -o cls --no-headers | sort | uniq -c
     34  TS
$ chrt -m
SCHED_OTHER min/max priority	: 0/0
SCHED_FIFO min/max priority	: 1/99
SCHED_RR min/max priority	: 1/99
SCHED_BATCH min/max priority	: 0/0
SCHED_IDLE min/max priority	: 0/0
SCHED_DEADLINE min/max priority	: 0/0

La shell usa SCHED_OTHER, la política normal de Linux, que ps abrevia como TS (time sharing). Todos los 34 procesos de esta máquina están en esa clase, porque ninguno pidió una política de tiempo real. Las otras cinco que lista chrt -m aparecen en el curso: SCHED_FIFO y SCHED_RR (tiempo real, con prioridades del 1 al 99) en el tema 35, SCHED_DEADLINE en el mismo tema, y SCHED_BATCH y SCHED_IDLE en el bloque 10. La columna NI es el valor nice, que influye en cuánta CPU recibe un proceso de la clase normal (tema 37), y PSR es el núcleo en el que se ejecutó por última vez (14, entre los dieciséis disponibles). Para el detalle de un proceso:

$ grep -E 'policy|prio' /proc/self/sched
policy                                       :                    0
prio                                         :                  120
$ cat /proc/self/schedstat
907300 0 1

policy 0 es SCHED_OTHER, y prio 120 es la prioridad interna de un proceso con nice 0. El archivo schedstat tiene tres números: los nanosegundos que el proceso estuvo en la CPU (907 300, menos de un milisegundo para un cat), los que esperó en la cola de listos (0) y las veces que recibió la CPU (1). Son exactamente los datos que leyó trabajo.c. Los usaremos en el bloque 10 para verificar lo que digan los simuladores.

9. Cómo trabajaremos

Este curso se apoya en lo que aprendiste sobre procesos e hilos, y combina tres tipos de actividad:

1. Cálculo a mano: cada algoritmo se explica con un ejemplo pequeño, resuelto paso a paso y dibujado como diagrama de Gantt. Es lo que se pide en un examen, y lo que permite entender qué hace el algoritmo antes de programarlo. papel
2. Simuladores en JavaScript: después de entender un algoritmo lo programamos, como una función que recibe una lista de procesos y devuelve el diagrama y las métricas, y lo vemos funcionar en una página que puedes modificar. Todos comparten el mismo modelo de proceso, que definiremos en el tema 9. JavaScript
3. Comprobación en Linux: cuando hay algo que medir, como el costo de un cambio de contexto, el reparto de CPU según nice o la política de un proceso, lo medimos con programas en C compilados con gcc -std=c17 -Wall -Wextra y con las herramientas del sistema. Linux

$ sudo apt install build-essential procps util-linux linux-tools-common
# util-linux trae chrt, taskset y nice; procps trae ps y top;
# linux-tools-common trae perf, que usaremos en el último bloque

10. El mapa del curso

Los 44 temas avanzan desde el problema hasta el planificador de Linux. Cada bloque responde una pregunta:

Los bloques 1 y 2 son la base conceptual y de medida; los bloques 3 a 7 recorren los algoritmos clásicos, cada uno con su simulador; los bloques 8 y 9 extienden el problema a varios núcleos y a plazos estrictos; el bloque 10 baja a Linux; y el 11 reúne todo en proyectos.

11. Resumen

• Hay más procesos listos que núcleos: alguien tiene que decidir cuál usa la CPU. Esa es la tarea del planificador de corto plazo.
• Planificar no acelera la máquina ni reduce el trabajo total; cambia cuándo termina cada proceso. Para un proceso sin E/S, tiempo total = tiempo en CPU + tiempo de espera en la cola.
• En el experimento, tres trabajos de 4, 2 y 1 unidades dieron un tiempo medio de 1,95 s, 1,75 s o 1,27 s según el orden, con el mismo trabajo total de unos 2,4 s.
• La multiprogramación mantiene varios procesos en memoria para que la CPU tenga siempre algo que ejecutar; con esperas de E/S del 80 %, la utilización pasa del 20 % con un proceso al 89 % con diez (1 − pⁿ).
• El planificador decide a quién, por cuánto tiempo y, en máquinas con varios núcleos, dónde; y lo hace miles de veces por segundo, por lo que debe ser muy rápido.
• No existe un orden mejor para todos: lo interactivo, el cálculo por lotes, los servidores y el tiempo real quieren cosas distintas, y por eso Linux combina varias clases de planificación.
• Hay planificación de largo, mediano y corto plazo; este curso estudia la de corto plazo.
• En Linux se observa con ps -o cls,pri,ni, chrt -p, /proc/PID/sched y /proc/PID/schedstat; la clase normal es SCHED_OTHER (TS).

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Compila trabajo.c y repite el experimento con cuatro procesos de 2 unidades en un solo núcleo. Predice antes de ejecutar cuánto tardará cada uno, y comprueba que terminó en sea igual a CPU usada más esperó en la cola.
2. Ejecuta los tres procesos de 4, 2 y 1 unidades sin taskset en una máquina con varios núcleos. ¿Qué tiempos obtienes? ¿Por qué se parecen tanto a los de ejecutar cada uno solo?
3. Con el simulador, encuentra para los valores 24, 3, 3 el orden con mayor espera promedio y el de menor. ¿Qué regla simple da el mínimo? Compruébala con ráfagas 7, 2, 9.
4. Calcula a mano la utilización de la CPU con p = 0,9 para n = 1, 2, 4 y 8. ¿Cuántos procesos hacen falta para pasar del 90 %?
5. Ejecuta ps -e -o pid,cls,pri,ni,comm en tu sistema. ¿Hay algún proceso con una clase distinta de TS? Si lo hay, averigua con chrt -p PID qué política tiene.
6. Mira cat /proc/$$/schedstat varias veces en tu shell y observa cómo crece el primer número. ¿Cuántos turnos lleva tu shell? Compara con cat /proc/1/schedstat.