El temporizador, la multiprogramación y la multitarea

1. El programa que no suelta la CPU

En el tema 2 lanzamos dos bucles infinitos sobre un mismo procesador y vimos que cada uno recibía la mitad del tiempo, aunque ninguno contenía una línea para ceder el turno. En el tema 11 el hecho se volvió un problema teórico: el kernel solo se ejecuta cuando algo lo invoca, y un bucle que suma números no lo invoca nunca.

Repasemos las tres entradas al kernel a la luz de ese programa:

La tercera fila es la única esperanza, y tal como está no alcanza: en un equipo sin actividad de teclado, de disco ni de red, podría no llegar ninguna interrupción durante mucho tiempo. La solución es añadir un dispositivo cuya actividad esté garantizada.

2. Un dispositivo que solo sabe interrumpir

Un temporizador es un dispositivo que genera una interrupción cuando transcurre un intervalo de tiempo fijado por el kernel. No transfiere datos ni se conecta con nada exterior: su única función es devolver el control al kernel en un momento determinado.

Por dentro es un contador. El kernel escribe en él un valor; un oscilador de cuarzo lo hace disminuir a ritmo constante; cuando llega a cero, el circuito activa su línea de interrupción. Puede trabajar de dos maneras: periódica, recargándose solo para interrumpir a intervalos regulares, o de un solo disparo, interrumpiendo una vez en el instante que se le indique.

Para el resto del sistema es un dispositivo como los demás. Interrumpe por el mecanismo del tema 17, tiene su vector y su manejador. Lo singular es que la interrupción no anuncia ningún suceso: el suceso es que pasó el tiempo.

Una PC tiene varios circuitos de este tipo, de épocas distintas, y conviene separar dos funciones que se confunden con facilidad: avisar cuando pasa un intervalo, y decir cuánto tiempo transcurrió.

$ cat /sys/devices/system/clocksource/clocksource0/current_clocksource
tsc
$ grep -E 'CPU|timer|LOC' /proc/interrupts
            CPU0       CPU1       CPU2       CPU3
   0:          9          0          0          0   IO-APIC    2-edge      timer
 LOC:    3120447    2987102    3054418    3011950   Local timer interrupts

La salida confirma lo que adelantamos en el tema 17. Linux usa el temporizador antiguo solo durante el arranque, y después trabaja con el de cada núcleo: cada procesador tiene su propio reloj despertador. En una máquina virtual la fuente de la hora tiene otro nombre, como kvm-clock, porque la proporciona el hipervisor.

3. El tic

La forma clásica de usar el temporizador es programarlo para que interrumpa a intervalos fijos. Cada una de esas interrupciones es un tic, y su frecuencia se elige al compilar el kernel, en un parámetro llamado HZ:

$ grep 'CONFIG_HZ=' /boot/config-$(uname -r)
CONFIG_HZ=1000

Mil tics por segundo significa uno cada milisegundo. Otras distribuciones usan 250, uno cada cuatro milisegundos. En WSL el archivo no existe, y el valor se consulta con zcat /proc/config.gz | grep 'CONFIG_HZ='.

El manejador del tic es breve, como todo manejador, y hace cuatro cosas. Cada una explica algo que usamos en temas anteriores sin saber de dónde salía:

La segunda fila aclara cómo mide el kernel el tiempo de CPU. No cronometra cada tramo: toma una muestra en cada tic y carga el intervalo completo a quien encuentra en ese instante. Es una estimación estadística, muy buena para duraciones largas y poco fiable para las muy breves.

Un tic fijo tiene un inconveniente: despierta al procesador mil veces por segundo aunque no haya nada que hacer, lo que en un portátil se paga en batería. Por eso Linux funciona desde hace años en modo sin tic. Cuando un núcleo queda ocioso, el kernel programa su temporizador para un solo disparo, en el momento del próximo suceso previsto, y lo deja dormir hasta entonces. Cuando un programa vuelve a ocuparlo, restablece el tic periódico. Es lo que medimos en el tema 17: un equipo en reposo atendía unos cientos de interrupciones por segundo, y al lanzar un programa de cálculo aparecían unas mil más.

4. De la multiprogramación a la multitarea

Con el temporizador disponible se puede completar una historia que empezamos en el tema 3. Repartir un procesador entre varios programas exige responder una pregunta: ¿cuándo se cambia de uno a otro? Hubo tres respuestas, y cada una necesitó algo más del hardware.

En los sistemas cooperativos, cada programa debía llamar con frecuencia a una función del sistema para dar paso a los demás. Funcionaba mientras todos colaboraban. Bastaba un programa con un error, atrapado en un bucle, para que la máquina entera dejara de responder y hubiera que reiniciarla. Quienes usaron esos sistemas recuerdan bien la experiencia.

Apropiativa traduce el inglés preemptive: el sistema se apropia de la CPU, se la quita al programa. Es la única forma que no depende de la buena conducta de nadie, y por eso es la base de la protección del recurso CPU que anunciamos en la tabla del tema 2.

Los sistemas actuales combinan las dos reglas de cambio. Un programa deja la CPU cuando se bloquea esperando algo, como en la multiprogramación, y también cuando el kernel se la quita. Lo veremos reflejado en dos contadores distintos en la sección 8.

5. El cambio de contexto, paso a paso

En el tema 6 definimos el contexto de un programa como el contenido de sus registros, y adelantamos que guardarlo y restaurarlo permite pausarlo y reanudarlo. Con las interrupciones del tema 17 ya tenemos el momento en que ocurre.

Un cambio de contexto es la operación por la que el kernel deja de ejecutar un proceso y pasa a ejecutar otro: guarda el estado del primero, de modo que pueda continuar más adelante, y restaura el estado guardado del segundo.

Sigamos el caso de dos programas, A y B, que solo calculan. A tiene la CPU.

1. El temporizador interrumpe. La CPU termina la instrucción en curso de A, guarda su contador de programa, su puntero de pila y su registro de estado en la pila de kernel de A, y pasa a modo kernel. cambio de modo
2. El kernel guarda el resto de los registros de A en esa misma pila. Hasta aquí es una interrupción cualquiera. modo kernel
3. El manejador del tic hace sus cuentas y comprueba que A ya usó su turno. Deja anotado que hay que elegir de nuevo. modo kernel
4. Antes de volver, el kernel llama al planificador, que elige a B. modo kernel
5. El kernel cambia de pila: guarda el puntero de la pila de kernel de A y carga el de la pila de kernel de B, donde están los registros que se guardaron cuando B fue interrumpido. modo kernel
6. Cambia el espacio de direcciones. Carga en el registro cr3 las tablas de memoria de B. A partir de aquí, las direcciones significan otra cosa. modo kernel
7. Restaura los registros de B y ejecuta la instrucción de retorno. cambio de modo
8. B continúa en la instrucción donde había quedado, con todos sus registros como los dejó. modo usuario

El paso 5 es el centro de la operación, y es más simple de lo que parece. El kernel no «copia» el estado de un proceso a otro lugar: cada proceso tiene su propia pila de kernel, la que presentamos en el tema 12, y su estado ya quedó guardado allí al entrar. Cambiar de proceso es cambiar de pila. El retorno, que en una interrupción corriente devolvería el control a A, saca de la pila de B los registros de B.

El paso 6 usa la instrucción privilegiada del tema 12 que escribe en cr3. Es lo que da a cada proceso su memoria propia: el mismo número de dirección lleva a datos distintos según qué tablas estén activas.

Ninguno de los dos programas percibe nada. Para A, entre una instrucción y la siguiente pasó un tiempo. Es lo mismo que le ocurre con cualquier interrupción, solo que más largo.

6. Quién decide: el planificador

En el paso 4 apareció una pieza nueva. El planificador (scheduler) es la parte del kernel que elige, entre los procesos que están en condiciones de ejecutarse, cuál recibe la CPU y por cuánto tiempo. Ese tiempo máximo se llama quantum o porción de tiempo.

Conviene separar con cuidado dos cosas que colaboran:

Este tema trata del mecanismo. La política es un asunto extenso, porque no existe un reparto ideal: un servidor quiere completar la mayor cantidad de trabajo; un equipo de escritorio, que la ventana responda al instante; un sistema que controla una máquina, que cierta tarea se ejecute sin falta antes de un plazo. Son objetivos que se contradicen.

Linux no usa un quantum fijo. Su planificador calcula cuánto le corresponde a cada proceso según cuántos compiten y qué prioridad tienen, e intenta que todos reciban una parte justa; el resultado son turnos de unos pocos milisegundos. Los estados de un proceso y los algoritmos de planificación se presentan en el tema 26 y se estudian a fondo en el curso de procesos.

7. Experimento: dos bucles y un procesador

Repetimos el experimento del tema 2 con un programa propio, para estar seguros de lo que contiene:

int main(void)
{
    volatile unsigned long contador = 0;

    for (;;)
        contador++;                     /* ni una sola llamada al sistema */
}

$ gcc -Wall -Wextra -g bucle.c -o bucle
$ taskset -c 0 ./bucle &           # los dos, obligados a usar el procesador 0
[1] 5210
$ taskset -c 0 ./bucle &
[2] 5211

$ top -b -n 1 | grep bucle
   5210 diego     20   0    2680   1024    936 R  50.0   0.0   0:08.41 bucle
   5211 diego     20   0    2680   1024    936 R  50.0   0.0   0:08.39 bucle

$ grep ctxt /proc/5210/status
voluntary_ctxt_switches:	0
nonvoluntary_ctxt_switches:	2874

$ kill %1 %2

El programa no hace ninguna llamada al sistema después de arrancar; conectarle strace -p, como en el tema 16, no muestra una sola línea. Y sin embargo:

• Cada copia recibe la mitad del procesador. Ninguna pudo impedírselo a la otra.
• La terminal siguió respondiendo. La shell, top y grep se ejecutaron con normalidad mientras los bucles corrían.
• El kernel lleva la cuenta. El archivo status de cada proceso informa cuántas veces dejó la CPU por decisión propia y cuántas se la quitaron. Este proceso nunca la cedió, y se la quitaron miles de veces.
• kill funcionó. Tampoco es obvio: ¿cómo se le avisa algo a un programa que no escucha? El kernel deja anotada la señal, y la aplica la próxima vez que ese proceso pasa por el kernel. Gracias al temporizador, eso ocurre a lo sumo un tic después.

8. Contar los cambios

Los dos contadores del archivo status corresponden a las dos reglas de cambio de la sección 4:

Un programa puede consultar sus propios contadores con getrusage, la llamada que usamos en el tema 18. El siguiente tiene dos modos: en uno calcula durante cinco segundos, y en el otro hace cien pausas de diez milisegundos.

#include <stdio.h>
#include <string.h>
#include <sys/resource.h>
#include <time.h>

int main(int argc, char *argv[])
{
    struct rusage uso;

    if (argc == 2 && strcmp(argv[1], "calcular") == 0) {
        volatile unsigned long n = 0;
        time_t fin = time(NULL) + 5;

        while (time(NULL) < fin)        /* cinco segundos sin pedir nada al kernel */
            n++;

    } else if (argc == 2 && strcmp(argv[1], "dormir") == 0) {
        struct timespec pausa = { 0, 10 * 1000 * 1000 };    /* 10 milisegundos */

        for (int i = 0; i < 100; i++)
            nanosleep(&pausa, NULL);    /* cada pausa cede la CPU */

    } else {
        fprintf(stderr, "uso: %s calcular|dormir\n", argv[0]);
        return 1;
    }

    getrusage(RUSAGE_SELF, &uso);
    printf("Cambios voluntarios:   %ld\n", uso.ru_nvcsw);
    printf("Cambios involuntarios: %ld\n", uso.ru_nivcsw);
    return 0;
}

El modo calcular consulta la hora en cada vuelta, y aun así no entra al kernel: time es una de las funciones que se resuelven en el vDSO, como vimos en el tema 15.

$ gcc -Wall -Wextra -g turnos.c -o turnos
$ ./turnos dormir
Cambios voluntarios:   100
Cambios involuntarios: 0

$ ./turnos calcular                 # solo, con procesadores libres
Cambios voluntarios:   0
Cambios involuntarios: 14

$ taskset -c 0 ./turnos calcular & taskset -c 0 ./turnos calcular; wait
Cambios voluntarios:   0
Cambios involuntarios: 842
Cambios voluntarios:   0
Cambios involuntarios: 839

Las tres ejecuciones muestran las tres situaciones posibles:

• El que duerme cede siempre. Cien pausas, cien cambios voluntarios, ninguno forzado. Nunca agotó un turno, porque lo abandonaba antes.
• El que calcula sin competencia casi no es molestado. El temporizador lo interrumpió miles de veces en cinco segundos, pero en casi todas el kernel comprobó que nadie más quería ese procesador y lo dejó seguir. Una interrupción del temporizador no implica un cambio de contexto: es solo la oportunidad de hacerlo.
• Los dos que compiten se turnan. Obligados a compartir un procesador, cada uno fue desalojado más de ochocientas veces. En cinco segundos, son turnos de unos tres milisegundos.

Las cifras de la segunda y la tercera ejecución varían con el equipo, la versión del kernel y lo que haya en marcha; las proporciones entre ellas se mantienen.

9. El ritmo del sistema

Para ver el efecto en todo el equipo sirve vmstat, que cada segundo informa, entre otras cosas, las interrupciones y los cambios de contexto ocurridos. El kernel publica los totales en /proc/stat, en las líneas intr y ctxt; vmstat calcula la diferencia. Lo ejecutamos mientras, en otra terminal, se lanzan los dos bucles de la sección 7:

$ vmstat 1 4
procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
 0  0      0 7214032 182344 4601220    0    0     0    12  402  655  1  0 99  0  0
 0  0      0 7213880 182344 4601224    0    0     0     0  388  640  1  0 99  0  0
 2  0      0 7213100 182344 4601230    0    0     0     0 1412  985 26  0 74  0  0
 2  0      0 7213096 182348 4601230    0    0     0     8 1398  992 25  0 75  0  0

Cada número se explica con lo visto. Las mil interrupciones adicionales son el tic del procesador 0, que dejó de estar ocioso. Los cambios de contexto aumentaron en unos 340 por segundo: los turnos de tres milisegundos de la sección anterior. Y us marca 25 porque el equipo tiene cuatro procesadores y uno de ellos está ocupado por completo.

La primera fila tiene también su interés: un equipo «sin hacer nada» realiza cientos de cambios de contexto por segundo. Son los servicios y los hilos del kernel, que despiertan un instante, hacen su tarea y vuelven a dormir. Las versiones recientes de vmstat añaden una columna más al final.

10. Lo que cuesta cambiar

Un cambio de contexto no produce nada útil: es tiempo que no se dedica a ningún programa. Tiene dos componentes.

• El costo directo: guardar y restaurar registros, ejecutar el planificador, cambiar las tablas de memoria. Del orden de un microsegundo.
• El costo indirecto, que suele ser mayor. El proceso que entra encuentra las cachés del procesador llenas con los datos del que salió, y sus primeros accesos a memoria son lentos. Lo mismo vale para la caché de traducciones de direcciones, que en parte hay que descartar al cambiar de espacio de direcciones.

La duración del turno es, por lo tanto, un compromiso:

Con turnos de tres milisegundos y un costo total de unos pocos microsegundos por cambio, la pérdida ronda el uno por mil, y tres milisegundos están muy por debajo de lo que una persona percibe. De ahí la ilusión: cada programa avanza a saltos, pero tan seguidos que parece continuo.

El costo ayuda también a interpretar un síntoma. Un valor de cs de decenas o cientos de miles por segundo indica que el sistema gasta una parte seria de su capacidad en cambiar de tarea, normalmente porque hay muchos más procesos activos que procesadores, o procesos que se despiertan unos a otros sin parar.

11. Despertar a tiempo

El temporizador no sirve solo para quitar la CPU. Es también lo que permite a un programa esperar un tiempo determinado sin consumirla. Cuando un programa llama a sleep o a nanosleep:

1. El kernel anota en qué instante debe despertarlo, lo marca como dormido y entrega la CPU a otro. Es un cambio voluntario.
2. Programa el temporizador para que interrumpa en ese instante, si no había ya un aviso anterior.
3. Al llegar la interrupción, comprueba qué esperas vencieron y marca esos procesos como listos.
4. El proceso continúa cuando el planificador le da un turno.

Es la misma estructura de la tecla del tema 17: una llamada al sistema que duerme al proceso y una interrupción que lo despierta. Solo cambia el dispositivo. Y explica los tres segundos casi exactos que midió strace -T sobre demora en el tema 16.

El paso 4 tiene una consecuencia que se puede medir. El siguiente programa pide pausas de un milisegundo y comprueba cuánto duraron en realidad:

#include <stdio.h>
#include <time.h>

int main(void)
{
    struct timespec pausa = { 0, 1000 * 1000 };     /* pedir 1 milisegundo */
    struct timespec antes, despues;

    for (int i = 0; i < 5; i++) {
        clock_gettime(CLOCK_MONOTONIC, &antes);
        nanosleep(&pausa, NULL);
        clock_gettime(CLOCK_MONOTONIC, &despues);

        long micros = (despues.tv_sec - antes.tv_sec) * 1000000L
                    + (despues.tv_nsec - antes.tv_nsec) / 1000;

        printf("Pedido: 1000 us   Real: %ld us\n", micros);
    }
    return 0;
}

$ gcc -Wall -Wextra -g siesta.c -o siesta
$ ./siesta
Pedido: 1000 us   Real: 1068 us
Pedido: 1000 us   Real: 1059 us
Pedido: 1000 us   Real: 1061 us
Pedido: 1000 us   Real: 1057 us
Pedido: 1000 us   Real: 1063 us

La pausa nunca dura menos de lo pedido, y siempre dura un poco más. Hay dos motivos. El kernel agrupa a propósito los despertares cercanos, para interrumpir menos veces. Y despertar no es ejecutar: cuando la espera vence, el proceso pasa a estar listo y todavía debe recibir un turno. En un equipo con mucha carga, la diferencia puede ser de varios milisegundos.

La regla general es que un sistema de uso general garantiza un mínimo, no un máximo. Las pausas, los plazos y los tiempos de respuesta son aproximados. Cuando una tarea debe ejecutarse sin falta dentro de un plazo, como en el control de un motor o de un freno, se necesita un sistema operativo de tiempo real, diseñado para dar esa garantía. Los presentamos en el tema 23.

12. Con varios núcleos

Hasta aquí razonamos con un solo procesador, y para eso obligamos a los programas a compartir el número 0. Con varios núcleos aparece una distinción que conviene fijar:

Un equipo actual tiene las dos cosas. Con ocho núcleos se ejecutan de verdad ocho programas a la vez, y los cientos restantes se turnan sobre ellos. Para el kernel, cada núcleo es un procesador completo, con su propio temporizador —las columnas de la fila LOC— y su propia lista de procesos listos. El planificador añade a su tarea una decisión más: en qué núcleo se ejecuta cada proceso. Procura no moverlos, por el mismo motivo de las cachés que vimos en la sección 10, y los traslada cuando un núcleo queda sobrecargado y otro ocioso.

Para coordinarse, los núcleos se interrumpen entre sí. Cuando un proceso despierta y el más adecuado para ejecutarlo es otro núcleo, el primero le envía una interrupción para que revise su lista. Es la fila RES de /proc/interrupts, cuyo nombre completo es «interrupciones de replanificación».

La multitarea apropiativa tiene una consecuencia para quien programa, y es bueno conocerla desde ahora. Un programa puede ser interrumpido entre dos instrucciones cualesquiera, y otro puede ejecutarse mientras tanto. Mientras cada programa trabaja con su propia memoria, no importa. Cuando varios flujos de ejecución comparten datos, sí: uno puede quedar interrumpido a mitad de una modificación, y el otro encontrar los datos a medio cambiar. Es el origen de los errores de concurrencia, de los más difíciles de reproducir, y la materia de un curso entero de esta ruta.

13. Cierre del bloque

Con este tema termina el bloque de interrupciones, y quedan completas las tres entradas al kernel que enumeramos en el tema 11:

La última fila es un caso particular de la segunda, pero merece su lugar aparte: es la que convierte al kernel de un servicio que espera ser llamado en la autoridad que gobierna la máquina. Sin ella, todo lo demás dependería de la buena voluntad de los programas.

Junto con los modos de ejecución del tema 12, estos mecanismos forman la base completa de un sistema operativo. El procesador impide que un programa haga lo que no debe; las llamadas al sistema le dan una forma controlada de pedirlo; las interrupciones y el temporizador aseguran que el kernel nunca pierda el mando.

Pero todo descansa sobre una preparación previa. Alguien tuvo que construir la tabla de vectores, registrar los manejadores y programar el temporizador antes de que el primer programa se ejecutara. Ese trabajo se hace una sola vez, entre que se pulsa el botón de encendido y aparece la pantalla de inicio de sesión. Es el contenido del bloque siguiente: el arranque.

14. Resumen

• Un programa que solo calcula no entra nunca al kernel por su cuenta. El temporizador garantiza que el kernel recupere el control igualmente.
• El temporizador es un dispositivo que interrumpe cuando transcurre un intervalo fijado por el kernel. En los equipos actuales hay uno en cada núcleo.
• En cada tic, el kernel actualiza el tiempo, anota a quién corresponde el intervalo, despierta a los procesos cuya espera venció y comprueba si hay que cambiar de proceso.
• Un núcleo ocioso no recibe tics: el kernel programa un solo aviso para el próximo suceso previsto.
• En la multiprogramación se cambia de programa cuando el actual debe esperar; en la multitarea cooperativa, cuando cede; en la apropiativa, cuando el kernel lo decide.
• El cambio de contexto guarda el estado de un proceso y restaura el de otro. En esencia consiste en cambiar de pila de kernel y de tablas de memoria.
• El temporizador y el cambio de contexto son el mecanismo; el planificador, que elige a quién dar la CPU, es la política.
• Un cambio es voluntario si el proceso se bloquea e involuntario si el kernel lo desaloja. Una interrupción del temporizador no siempre produce un cambio.
• vmstat muestra las interrupciones y los cambios de contexto por segundo de todo el sistema.
• Cambiar de contexto tiene un costo, sobre todo por las cachés; la duración de los turnos es un compromiso entre rapidez de respuesta y rendimiento.
• Las pausas duran como mínimo lo pedido, nunca exactamente.
• Con varios núcleos hay paralelismo real, además de la concurrencia por turnos.

15. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Lanza tres copias de bucle en el procesador 0 y predice el porcentaje de cada una antes de mirar top. Luego lanza las tres sin taskset: ¿qué cambia, y por qué?
2. Con dos copias de bucle en el procesador 0, lee dos veces nonvoluntary_ctxt_switches con diez segundos de diferencia y calcula la duración media de un turno.
3. Ejecuta ./turnos calcular sin competencia y compara sus cambios involuntarios con el valor de CONFIG_HZ multiplicado por cinco. ¿Cuántas interrupciones del temporizador recibió por cada desalojo?
4. Lanza cuatro copias de ./turnos calcular en el procesador 0. ¿Cómo cambia la cantidad de desalojos de cada una respecto del caso con dos?
5. Observa vmstat 1 mientras ejecutas ./tiempos pedir, del tema 11. ¿Qué columnas cambian? ¿Aumenta cs? Explica por qué una llamada al sistema no es un cambio de contexto.
6. Con watch -n 1 -d 'grep -E "CPU|LOC" /proc/interrupts', lanza taskset -c 2 ./bucle y observa qué columna se acelera.
7. Ejecuta siesta mientras corren tantas copias de bucle como procesadores tenga tu equipo. ¿Cómo cambian las pausas reales?
8. Modifica siesta.c para pedir pausas de 100 microsegundos y de 10 milisegundos. ¿El exceso es proporcional a lo pedido o es más bien constante?
9. Consulta los contadores de tu shell con grep ctxt /proc/$$/status. ¿De qué tipo son casi todos? Relaciónalo con lo que hace una shell la mayor parte del tiempo.