La CPU y el ciclo de instrucción

1. Lenguaje de máquina y ensamblador

En el tema 5 vimos que las instrucciones son números guardados en memoria, y leímos los primeros bytes de la función main: f3 0f 1e fa 55 48 89 e5. Esa secuencia de bytes es lenguaje de máquina, lo único que una CPU entiende.

Cada instrucción de máquina indica dos cosas: qué operación realizar y con qué operandos. Las operaciones disponibles son pocas y muy elementales:

• Mover un valor: de la memoria a un registro, de un registro a la memoria, o entre registros.
• Calcular: sumar, restar, multiplicar, comparar, operar bit a bit.
• Saltar: continuar la ejecución en otra dirección, siempre o solo si se cumple una condición.
• Controlar la máquina: unas pocas instrucciones especiales que veremos al hablar del kernel.

Como nadie puede leer cómodamente números, cada instrucción tiene una forma escrita equivalente, el lenguaje ensamblador. La correspondencia es directa: una línea de ensamblador, una instrucción de máquina.

El conjunto de instrucciones que entiende una familia de procesadores se llama arquitectura. Las dos más extendidas son x86-64, de los procesadores Intel y AMD, y ARM (aarch64), de los teléfonos y de los Mac actuales. Son incompatibles entre sí: un ejecutable compilado para una no funciona en la otra, porque sus bytes significan otra cosa. Por eso gcc necesita saber para qué arquitectura compila, y por eso el kernel informa la suya con uname -m.

2. Los registros

Los registros son las celdas de almacenamiento que están dentro de la propia CPU. Son muy pocos —unas decenas— y extremadamente rápidos: la CPU opera sobre ellos sin tener que ir a la memoria. Casi todas las instrucciones leen o escriben al menos uno. En un procesador de 64 bits, cada registro guarda 64 bits.

Algunos sirven para cualquier cosa y otros tienen un papel fijo. Estos son los de x86-64 que nos interesan:

Dos aclaraciones sobre los nombres. El contador de programa se llama también program counter o PC, que es el término general; rip es su nombre en x86-64. Y los registros tienen nombres alternativos para sus partes: eax designa los 32 bits inferiores de rax, y es el que se usa al trabajar con un int.

De toda la tabla, dos registros son los protagonistas del resto del curso: el contador de programa, que determina qué se ejecuta, y el puntero de pila, que sostiene las llamadas a función.

3. El ciclo de instrucción

Desde que recibe energía hasta que se apaga, la CPU repite un mismo ciclo de tres pasos:

1. Captar (fetch). La CPU lee de la memoria la instrucción que está en la dirección indicada por el contador de programa. Acto seguido, incrementa el contador para que apunte a la instrucción que sigue.
2. Decodificar (decode). La unidad de control interpreta los bytes leídos: de qué operación se trata y cuáles son sus operandos.
3. Ejecutar (execute). Se realiza la operación: la ALU calcula, se copia un valor o se modifica el contador de programa si es un salto.

Al terminar, y antes de captar la instrucción siguiente, la CPU comprueba si algún dispositivo solicita atención. Ese cuarto paso, las interrupciones, tiene su propio bloque en el curso; por ahora basta con saber que existe.

Expresado con la sintaxis de C, todo el comportamiento de una CPU cabe en un bucle:

while (hay_energia) {
    instruccion = memoria[PC];           /* 1. captar                   */
    PC = PC + longitud(instruccion);     /*    apuntar a la siguiente   */

    ejecutar(decodificar(instruccion));  /* 2 y 3. puede modificar PC   */

    if (hay_interrupcion_pendiente)      /* 4. tema 17                  */
        atender_interrupcion();
}

Dos observaciones sobre ese bucle, que parecen menores y no lo son:

• El contador de programa avanza antes de ejecutar. Durante la ejecución de una instrucción, el PC ya contiene la dirección de la siguiente. Por eso una instrucción de salto solo necesita escribir otro valor en él.
• La CPU no se detiene nunca. No existe un estado «sin programa». Si no hay nada útil que hacer, el sistema operativo debe darle algo: una tarea especial de espera que mantiene el procesador en reposo hasta la próxima interrupción.

4. Una ejecución paso a paso

Sigamos el ciclo con un programa de tres instrucciones que suma 5 y 7. Está cargado en memoria a partir de la dirección 0x1000:

Ahora el estado de los registros después de cada vuelta del ciclo. El signo ? indica un valor desconocido, lo que hubiera quedado de antes:

La tabla muestra tres cosas. Primero, que en x86-64 las instrucciones tienen longitud variable: dos de ellas ocupan cinco bytes y la tercera, dos; el PC avanza en cada caso lo que corresponde. Segundo, que el número 5 está dentro de la propia instrucción, en los bytes 05 00 00 00, guardado en el orden little endian que vimos en el tema 5. Y tercero, la más importante: el estado completo de este programa en un instante dado son los valores de sus registros. Si alguien anotara rip, eax y edx después del ciclo 2, detuviera la máquina y más tarde los restaurara, el programa continuaría como si nada hubiera pasado. Guarda esa idea: volveremos a ella en la sección 9.

5. Saltos: cómo se toman decisiones

Si el contador de programa solo avanzara, un programa sería una lista de instrucciones ejecutada una vez de principio a fin. Los if, los while y los for existen gracias a las instrucciones de salto, que escriben una dirección nueva en el contador de programa.

• Un salto incondicional (jmp) cambia el PC siempre.
• Un salto condicional lo cambia solo si se cumple una condición. Si no, la ejecución sigue en la instrucción de abajo.

La condición se evalúa en dos tiempos. Una instrucción de comparación (cmp) resta sus operandos y, sin guardar el resultado, anota en el registro rflags cómo fue: si dio cero, si fue negativo. Luego, la instrucción de salto condicional consulta esos bits. Veamos un bucle en C y su traducción:

int suma = 0;
for (int i = 1; i <= 5; i++)
    suma += i;

        mov   $0, %eax        # suma = 0
        mov   $1, %ecx        # i = 1
bucle:  add   %ecx, %eax      # suma += i
        add   $1, %ecx        # i++
        cmp   $5, %ecx        # compara i con 5 y anota el resultado en rflags
        jle   bucle           # si i <= 5, el PC vuelve a "bucle"

La palabra bucle es una etiqueta: un nombre para la dirección de esa instrucción. jle significa «saltar si es menor o igual» (jump if less or equal). Mientras i no supere 5, el contador de programa retrocede y las mismas cuatro instrucciones se ejecutan otra vez. No hay nada más: todas las estructuras de control de todos los lenguajes se reducen a comparar y saltar.

6. La pila y las llamadas a función

Llamar a una función es también un salto, con una dificultad añadida: al terminar, hay que volver al punto desde donde se la llamó, y ese punto es distinto en cada llamada. Además, una función puede llamar a otra, y esta a otra más. La CPU necesita recordar una cadena de «lugares a los que volver».

La solución es la pila (stack): una zona de la memoria que se usa como una pila de platos, donde lo último que se guarda es lo primero que se retira. El registro puntero de pila (rsp) contiene en todo momento la dirección del tope. Cuatro instrucciones trabajan con ella:

Con call y ret, las llamadas anidadas se resuelven solas: cada call apila una dirección de retorno y cada ret retira la más reciente, de modo que siempre se vuelve a quien llamó en último lugar.

La pila guarda más que direcciones de retorno. Cada llamada reserva en ella un bloque, llamado marco de pila (stack frame), con todo lo que esa ejecución de la función necesita: sus variables locales, los registros que debe conservar y la dirección de retorno. Cuando la función termina, su marco se descarta. Esa es la razón por la que las variables locales de C dejan de existir al salir de la función, y por la que la recursión funciona: cada llamada tiene su propio marco, con su propia copia de las variables.

Hay una convención que sorprende la primera vez: en x86-64, y en casi todas las arquitecturas, la pila crece hacia las direcciones bajas. Guardar un valor resta al puntero de pila. Es solo una convención, pero tiene consecuencias prácticas que veremos al estudiar la memoria de un proceso.

7. La pila vista desde C

Podemos observar los marcos sin usar ensamblador. La siguiente función se llama a sí misma tres veces y, en cada nivel, muestra la dirección de su variable local:

#include <stdio.h>

void bajar(int nivel)
{
    int local = nivel;

    printf("nivel %d  variable local en %p\n", nivel, (void *)&local);
    if (nivel < 4)
        bajar(nivel + 1);
}

int main(void)
{
    bajar(1);
    return 0;
}

$ gcc -Wall -Wextra -g pila.c -o pila
$ ./pila
nivel 1  variable local en 0x7ffc8a3e1b2c
nivel 2  variable local en 0x7ffc8a3e1afc
nivel 3  variable local en 0x7ffc8a3e1acc
nivel 4  variable local en 0x7ffc8a3e1a9c

Hay un solo nombre, local, y cuatro direcciones distintas: una variable por cada marco. Las direcciones disminuyen con cada llamada, lo que confirma el sentido en que crece la pila, y lo hacen a intervalos regulares —en este ejemplo, 0x30, es decir, 48 bytes—, que es el tamaño de cada marco de bajar. Las direcciones exactas y el tamaño del marco dependen del sistema y del compilador.

8. El ciclo en vivo con gdb

El depurador gdb puede detener un programa, avanzar una instrucción de máquina por vez y mostrar los registros. Es lo más parecido a mirar el ciclo de instrucción con lupa. Usemos el programa más simple posible:

int main(void)
{
    int a = 5;
    int b = 7;
    int c = a + b;
    return c;
}

$ gcc -Wall -Wextra -g suma.c -o suma
$ ./suma
$ echo $?                        # el valor que devolvió main
12

El programa no imprime nada; devuelve el resultado como código de salida. Ahora lo ejecutamos dentro del depurador. Los comandos que escribimos están resaltados:

$ gdb -q ./suma
Reading symbols from ./suma...
(gdb) break main                  # detenerse al llegar a main
Breakpoint 1 at 0x1131: file suma.c, line 3.
(gdb) run
Breakpoint 1, main () at suma.c:3
3	    int a = 5;
(gdb) display/i $pc               # mostrar siempre la instrucción a la que apunta el PC
1: x/i $pc
=> 0x555555555131 <main+8>:	movl   $0x5,-0xc(%rbp)
(gdb) stepi                       # ejecutar UNA instrucción de máquina
4	    int b = 7;
=> 0x555555555138 <main+15>:	movl   $0x7,-0x8(%rbp)
(gdb) stepi
5	    int c = a + b;
=> 0x55555555513f <main+22>:	mov    -0xc(%rbp),%edx
(gdb) stepi
=> 0x555555555142 <main+25>:	mov    -0x8(%rbp),%eax
(gdb) stepi
=> 0x555555555145 <main+28>:	add    %edx,%eax
(gdb) stepi
=> 0x555555555147 <main+31>:	mov    %eax,-0x4(%rbp)
(gdb) info registers rax rdx rip
rax            0xc                 12
rdx            0x5                 5
rip            0x555555555147      0x555555555147 <main+31>
(gdb) quit

Cada stepi es una vuelta del ciclo de instrucción, y la flecha => marca la instrucción a la que apunta el contador de programa, es decir, la próxima que se ejecutará. Qué se puede leer en la sesión:

• El contador de programa avanza según la longitud de cada instrucción: de …131 a …138 hay siete bytes; de …13f a …142, tres; de …145 a …147, dos.
• Una línea de C son varias instrucciones. La línea 5, int c = a + b;, se tradujo en cuatro: traer a a un registro, traer b a otro, sumar y guardar el resultado. La CPU no puede sumar dos valores de la memoria directamente; necesita pasarlos por registros.
• Las variables locales viven en la pila. -0xc(%rbp) significa «la dirección que está 12 bytes por debajo de rbp», dentro del marco de main. Allí está a; b está en -0x8(%rbp) y c en -0x4(%rbp).
• Tras la suma, rax contiene 12 y rip ya señala la instrucción siguiente, la que guardará ese valor en c.

Es el mismo recorrido de la tabla de la sección 4, ahora sobre un programa real. Las instrucciones adicionales aparecen porque compilamos sin optimizar, y en ese modo el compilador guarda cada variable en la pila para que el depurador pueda mostrarla.

9. Qué significa para el sistema operativo

Todo lo anterior es hardware puro: no intervino el sistema operativo. Pero de aquí salen cuatro ideas sobre las que se apoya el resto del curso.

El contexto de ejecución

Vimos en la sección 4 que el estado de un programa en un instante dado son los valores de sus registros. A ese conjunto se lo llama contexto. La consecuencia es directa: para detener un programa y continuarlo más tarde, basta con guardar sus registros en la memoria y, llegado el momento, restaurarlos. El programa no puede notar la pausa.

Esa operación es el cambio de contexto, y es el mecanismo detrás de la multitarea. Cuando en el tema 2 dos bucles infinitos se repartían un procesador, el kernel estaba haciendo exactamente esto decenas de veces por segundo: guardar los registros de uno, cargar los del otro.

Quien controla el contador de programa controla la máquina

La CPU ejecuta lo que el contador de programa señale. Para «darle la CPU» a un programa, el kernel escribe en ese registro la dirección de las instrucciones del programa; a partir de ahí, es el programa el que se ejecuta y el kernel queda detenido. La pregunta inevitable es cómo vuelve el kernel a ejecutarse si el programa no salta voluntariamente hacia él. La respuesta es el cuarto paso del ciclo: las interrupciones, que obligan a la CPU a cargar en el contador de programa una dirección del kernel.

Algunos registros e instrucciones están reservados

Los registros de control de la tabla de la sección 2 determinan, entre otras cosas, qué memoria puede ver el programa en ejecución. Si un programa común pudiera modificarlos, toda la protección sería inútil. Por eso la CPU solo permite tocarlos en modo kernel, como veremos en el tema 12.

Cada flujo de ejecución necesita su pila

Como la pila contiene las direcciones de retorno y las variables locales, dos ejecuciones independientes no pueden compartirla. Cada proceso, y cada hilo dentro de un proceso, tiene la suya; cambiar de uno a otro incluye cambiar el puntero de pila. El propio kernel usa pilas separadas de las de los programas, para no depender de memoria que estos controlan.

10. Las CPU reales

El ciclo que describimos es el modelo correcto para razonar, pero un procesador actual lo implementa con mucha más sofisticación para ganar velocidad:

• Segmentación (pipeline): mientras una instrucción se ejecuta, la siguiente ya se está decodificando y otra más se está captando, como en una línea de montaje.
• Ejecución fuera de orden: el procesador reordena internamente las instrucciones que no dependen entre sí para no quedar esperando.
• Predicción de saltos: ante un salto condicional, apuesta por un camino y empieza a ejecutarlo antes de conocer el resultado de la comparación. Si se equivoca, descarta el trabajo.
• Varios núcleos: cada núcleo ejecuta su propio ciclo, con sus propios registros. Además, muchos procesadores presentan cada núcleo físico como dos procesadores lógicos; es lo que lscpu informa como «Thread(s) per core: 2».

Lo importante es que todas estas técnicas son invisibles para el programa: el resultado es siempre el mismo que si las instrucciones se hubieran ejecutado una por una y en orden. Por eso podemos seguir pensando con el modelo simple.

La frecuencia que figura junto al nombre de un procesador, por ejemplo 3 GHz, indica el ritmo de su reloj interno: tres mil millones de pulsos por segundo. Sirve como orden de magnitud de la velocidad a la que gira el ciclo, y da la medida de por qué, para una CPU, esperar unos milisegundos a un disco es una eternidad.

11. Resumen

• La CPU solo entiende lenguaje de máquina: instrucciones elementales codificadas como bytes. El ensamblador es su forma legible.
• Cada arquitectura (x86-64, ARM) tiene sus propias instrucciones, incompatibles con las de las demás.
• Los registros son el almacenamiento interno de la CPU. Los dos esenciales son el contador de programa y el puntero de pila.
• La CPU repite sin pausa el ciclo captar, decodificar y ejecutar, y entre instrucción e instrucción comprueba si hay interrupciones.
• Las decisiones y los bucles se implementan con comparaciones y saltos, que modifican el contador de programa.
• La pila guarda las direcciones de retorno y las variables locales en marcos, uno por llamada, y crece hacia las direcciones bajas.
• El estado de un programa es el contenido de sus registros: guardarlos y restaurarlos permite pausarlo y reanudarlo. Es el cambio de contexto.
• Quien fija el contador de programa decide qué se ejecuta; el sistema operativo depende de las interrupciones para recuperarlo.

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Repite la sesión de gdb con suma.c. Antes de cada stepi, predice en cuántos bytes avanzará el contador de programa y compruébalo con info registers rip.
2. Ejecuta objdump -d suma | grep -A12 '<main>:' e identifica las instrucciones que viste en el depurador. ¿Cuáles son las tres primeras y las dos últimas, que no ejecutamos paso a paso?
3. En la misma sesión de gdb, ejecuta info registers rsp rbp. ¿Cuál de los dos tiene la dirección más baja?
4. Quita la condición if (nivel < 4) de pila.c para que la recursión no termine. Ejecuta el programa redirigiendo la salida (./pila > salida.txt) y averigua con tail -1 salida.txt hasta qué nivel llegó. Relaciónalo con el valor de ulimit -s.
5. Compila suma.c con gcc -O2 suma.c -o suma_opt y mira su main con objdump -d. ¿Dónde quedó la suma?