1. Virtualización de CPU

Los ordenadores actuales disponen de una cantidad limitada de recursos de hardware. En particular, una CPU cuenta con un número finito de núcleos físicos y solo puede ejecutar un conjunto reducido de instrucciones en cada instante. Sin embargo, un usuario esperaría poder ejecutar múltiples aplicaciones y procesos a la vez.

La solución a esto es la virtualización de CPU, que consiste en tomar uno o varios núcleos físicos de la CPU y simular, a partir de ellos, muchos más núcleos virtuales.

Abstracción, proceso.

#

Los programas, en sí, no son más que código compilado, una serie de instrucciones que el procesador es capaz de entender y ejecutar. Cuando no se están ejecutando, estas instrucciones simplemente están en disco paradas, no hacen nada. Cuando ejecutamos un programa, este se carga en memoria y la CPU va leyendo y ejecutando sus instrucciones de una en una, avanzando el PC, actualizando sus registros, etc.

Denominaremos proceso a un programa en ejecución. Un proceso no es solo el código, sino el código más su estado.

Si ejecutamos un único proceso, no hay problema, tiene toda la CPU para él solo, pero si tenemos varios, el sistema operativo debe elegir cuándo ejecutar uno y cuándo ejecutar otro. Primero se ejecuta uno un rato, luego se ejecuta el otro otro rato, y así hasta que ambos acaban, esto se conoce como time sharing.

1
2
3
4
5
6

PROC1: ----->      ----->      -----> FIN.
PROC2:       ----->      ----->      ---------------> FIN.
TIEMPO -------------------------------------------->

// "----->" = en ejecución.
// "      " = no en ejecución.

Para poder cambiar entre un proceso y otro (context switch), el sistema debe guardar toda la información necesaria para que el proceso a ejecutar pueda continuar exactamente donde se había quedado antes. Alguna de la información que debe almacenar el sistema (cada vez que se cambia) es:

• Registros de uso general
• Stack Pointer
• Program Counter (PC)
• Flags de estado

Estados de un proceso

#

Un proceso puede estar en varios estados:

• En ejecución: La CPU está activamente ejecutando sus instrucciones.
• Listo: El proceso está cargado en memoria y listo para ser ejecutado, pero no está en la CPU.
• Bloqueado: El proceso está esperando a un evento externo, como una lectura en disco. Para evitar bloquear el sistema, hasta que no termine el acceso a I/O, no vuelve a estar listo.

API de Procesos

#

Para que un usuario pueda crear, modificar o terminar un proceso, el sistema expone un API que, en Linux, cuenta con las siguientes syscalls:

• fork(): El proceso crea una copia casi idéntica de sí mismo (hijo) que empieza por la misma línea por la que iba el padre. La diferencia es que fork() devuelve 0 en el proceso hijo, y devuelve el PID del hijo en el proceso padre.
• wait(): El proceso padre espera a que termine un proceso hijo, luego continúa su ejecución. Con wait() el padre espera a que termine un proceso hijo cualquiera, con waitpid() se espera a uno específico. En ningún caso de estos se espera a que terminen todos los hijos.
• exec(): Dado un proceso, al ejecutar exec() se sustituye completamente el proceso actual en ejecución con otro ejecutable dado. P.ej, execvp(nombre_bin,array_args) ejecuta nombre_bin pasándole los argumentos a través de array_args (como un vector de strings). Si exec() tiene éxito, no vuelve nunca, esto significa que las instrucciones tras un exec() no se ejecutarán.
• kill(): Manda señales a los procesos, normalmente con el fin de pausarlos, reanudarlos, o detenerlos del todo. Algunas señales posibles son SIGINT, SIGHUP, SIGKILL, etc. Pueden verse todas ejecutando kill -l. Para evitar que cualquier proceso pueda intentar matar a cualquier otro, el sistema determina si un proceso tiene permiso o no para mandar señales a otro en función del usuario que inició el proceso que intenta mandar la señal.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <sys/wait.h>

int main(void){
    int pd = fork();
    if (pd < 0){
        printf("Error en el fork\n");
    }
    else if (pd == 0){ // hijo
        char *args[] = {"ls", "-al", NULL};
        execvp(args[0],args);
    }
    else { // padre
        printf("A: Esperando al proceso hijo de PID %d\n", pd);
        wait(NULL); // Esperamos a que acabe "cualquier proceso hijo" porque solo hay uno.
        printf("B: El proceso hijo ha terminado, ahora termina el padre, de PID %d", getpid());
    }
    return 0;
}

Este código hace lo siguiente:

• Inicia el programa e inmediatamente hace un fork(). Se crea el proceso hijo, que sigue ejecutando exactamente el mismo código.
• El proceso hijo tiene el valor 0 en pd. Mira el if y entra en su rama. Ahí se sustituye el proceso hijo por el binario ls con los argumentos ls -al, y se ejecuta.
  • Ponemos ls también como argumento de sí mismo porque en sistemas Unix, al hacer exec, el programa iniciado recibe como argv[] el array args[] (o como lo llame el programador). De hecho, args[0] ni siquiera tiene que coincidir con el nombre del binario, pero normalmente se hace así porque el programa espera recibir su propio nombre en argv[0].
• El proceso padre (ejecutándose antes o después, según elija el SO), tiene el valor PID_HIJO en pd. Mira el if y entra a su rama. Ahí muestra en pantalla el mensaje A (que puede salir antes o después del output de ls -al), luego, espera a que acabe el proceso hijo, y solo entonces imprime el mensaje B.

Hay que destacar que en este caso, aunque las syscalls se muestran como funciones en C (exec(),fork(), etc.) que vienen de librerías (como unistd.h), dentro de la implementación de tales funciones está la llamada al syscall real, siguiendo el estándar específico de cada arquitectura.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

$ strace ./shell
execve("./shell", ["./shell"], 0x7ffd5dcc5270 /* 72 vars */) = 0 
...[SNIP]...
write(1, "~> ", 13~> ) = 13
read(0whoami
, "whoami\n", 1024) = 7 # Ejecutamos "whoami" en el shell.
rt_sigprocmask(SIG_BLOCK, ~[], [], 8) = 0 # Se hace syscall "clone()" ↴
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f89b97e2a50) = 93103
rt_sigprocmask(SIG_SETMASK, [], NULL, 8) = 0
wait4(-1user # Devuelve "user"

LDE: Ejecución Directa Limitada

#

Para maximizar la seguridad respecto a lo que puede hacer (y hace) un proceso, lo ideal sería que el sistema operativo virtualizase cada paso que el proceso diese, esto es, que analizase cada instrucción y la simulase, como un intérprete. El problema es que esto sería exageradamente lento.

Por otro lado, para maximizar la velocidad de un proceso, lo ideal sería que se ejecutase directamente en la CPU, sin intervención del SO, y a la máxima velocidad a la que realmente el hardware le permitiese ir. El problema aquí sería que el proceso podría hacer cualquier cosa, tendría el control total de la máquina.

El punto medio entre seguridad y velocidad es la Ejecución Directa Limitada (LDE), que consiste en lo siguiente:

• Parte Directa: Cuando se ejecuta un programa (proceso), las instrucciones de dicho programa se ejecutan directamente en la CPU física, no se emula nada.
• Parte Limitada: Para controlar lo que el sistema puede hacer, se aplican varios mecanismos:
  • MODOS USER/KERNEL: Se distinguen 2 modos, el modo usuario, con un set de instrucciones limitado (Acceso a I/O y a memoria de otros procesos está prohibido); y modo kernel, con control total sobre la CPU. Los procesos se ejecutan en modo usuario, y el kernel en modo kernel. Si un proceso en modo user intenta ejecutar una instrucción solo disponible en modo kernel, tendrá lugar una excepción y posiblemente el kernel matará el proceso.

    

  • SYSCALLS: Si un proceso en modo usuario necesita hacer algo privilegiado (p.ej, leer un archivo), debe hacer una Syscall. Esto genera un trap (interrupción por software) que pasa el control al SO y eleva los privilegios de la CPU temporalmente a modo kernel, para que realice la acción de forma segura. Luego, el SO devuelve los datos solicitados y el control de la CPU al programa bajando de nuevo los privilegios a modo user.
  • TIMER INTERRUPTS: Para evitar que un proceso pueda entrar en un bucle infinito sin hacer syscalls y se quede con el control (limitado) de la CPU, el SO configura un temporizador de hardware, durante el arranque. Cada pocos milisegundos tiene lugar una interrupción que devuelve el control al SO.
  • CONTEXT SWITCH: Una vez el SO toma el control, puede elegir si quiere seguir ejecutando el proceso en activo o si quiere ponerlo en espera y dar tiempo de CPU a otro que esté listo. De elegir esto se encarga el Scheduler.

Scheduling

#

El sistema operativo ha tomado el control, ya sea por un syscall, excepción o timer interrupt. Ahora hay que decidir, cómo elegimos el proceso a ejecutar?

El Scheduler, en sí, no es más que un algoritmo encargado de elegir uno entre tantos procesos, y la política que elijamos para su funcionamiento dependerá de nuestro objetivo, pero en general los algoritmos de planificación buscar resolver estos dos problemas:

• Minimizar el Tiempo de Retorno (Turnaround Time): El tiempo que pasa desde que llega un trabajo (proceso) hasta que termina.
• Minimizar el Tiempo de Respuesa (Response Time): El tiempo que pasa desde que llega un trabajo hasta que se ejecuta por primera vez. Esto es crucial para un programa interactivo.

Para solucionar esto, se proponen varios modelos.

Modelos teóricos

#

Modelos Iniciales (Optimizar Tiempo de Retorno)

#

• FIFO (First-In, First-Out): El primero que llega es el primero en procesarse, hasta que se completa, luego el siguiente en haber llegado, y así en adelante. El problema llega cuando el primer proceso es muy largo, ya que los siguientes pueden tener que esperar mucho hasta ser ejecutados.
• SJF (Shortest Job First): Para solucionar el problema de las colas FIFO, se ejecutan primero los procesos más cortos. Aquí los problemas son dos: Necesitamos saber qué procesos van a acabar antes, y necesitamos saberlo antes de que hayan acabado (y el scheduler no es omnisciente), y además se asume que todos los procesos llegan a la vez. Si un proceso corto llega un milisegundo después de uno largo, se ejecutará después.
• STCF (Shortest Time-to-Completion First): Como el SJF, pero permite expulsar a un proceso largo atrás en la cola cuando llega uno más corto. Problema: Si hay un trabajo muy largo, puede llegar a no ejecutarse nunca.

Modelos Iniciales (Optimizar Tiempo de Respuesta)

#

• RR (Round Robin): Divide todos los procesos en trozos pequeños de tiempo llamados “quantum” de igual tamaño, para que todos se ejecuten un poco cada vez. Problema: Si el quantum es muy largo, RR se convierte en FIFO, y si es muy corto, el algoritmo pierde más tiempo de CPU cambiando de contexto entre un proceso y otro que ejecutando el proceso de verdad.

Aprendizaje Heurístico: MLFQ

#

• Multi-Level Feedback Queue: Usa el pasado para predecir el futuro. Cuenta con varias colas, cada una con diferente prioridad. Además, se define un quantum, como en RR.
  • Cada proceso en estado Ready está en una única cola de entre todas.
  • Cuando entra un proceso a la cola, entra en la cola de prioridad máxima.
  • Se ejecutan primero los procesos de la cola de máxima prioridad. Si hay más de uno, se hace round-robin entre ellos.
  • Si el proceso gasta todo su quantum sin ceder la CPU (I/O, Syscalls, etc., que es comportamiento típico de procesos interactivos), se asume que es un proceso pesado / no interactivo, y se le baja a una cola de menor prioridad.
  • Si el proceso cede la CPU, p.ej, haciendo operaciones de I/O, el Scheduler lo sube o mantiene en colas de prioridad alta para que responda rápido al usuario.
  • Para evitar que los procesos no interactivos se queden inactivos en el fondo, periódicamente se suben todos los procesos a la cola de mayor prioridad ("Impulso de prioridad").

La “memoria” con la que el MLFQ “predice el futuro” solo dura lo que dura el período del impulso de prioridad. Este normalmente suele ser de entre 1 y 5 segundos, mientras que un quantum suele durar entre 10 y 200ms.

Modelos Reales

#

Windows: NT Scheduler (MLFQ)

#

El kernel de Windows usa un scheduler basado en MLFQ, pero muy optimizado para la interactividad del usuario. Usa una cola de 32 niveles de prioridad. Estas colas se dividen en:

• Prioridades Fijas (16-31): Procesos críticos de hardware, drivers y audio. Si hay un proceso aquí, el sistema nunca le baja de prioridad
• Prioridades Dinámicas (0-15) Aplicaciones del usuario, aquí aplica MLFQ.

Además, Windows aplica modificaciones en determinadas situaciones. Por ejemplo, en una sesión de escritorio, la ventana activa (con foco) recibe el triple de quantum. Es decir, puede usar la CPU el triple de tiempo sin ser interrumpida.

Linux: CFS / EEVDF

#

CFS significa Completely Fair Scheduler, y el sistema busca eso, ser lo más justo / equitativo posible. Cada proceso tiene una medida: vruntime (tiempo de ejecución virtual), y el proceso ejecuta siempre la tarea con vruntime más pequeño. Para encontrar el proceso con menor vruntime, los procesos se organizan en un árbol rojo-negro.

El problema que tiene CFS es que no distingue entre procesos interactivos y no interactivos, por lo que un juego en primer plano posiblemente tenga el mismo tiempo de CPU que otro proceso no tan relevante que se ejecute en segundo plano, como la descarga de una actualización.

Para implementar prioridades, se usa un peso denominado Niceness, que va de -20 a +19. El niceness determina lo “bueno” que es un proceso hacia el resto, dejando más CPU a los demás. Si un proceso tiene niceness negativo (alta prioridad), su reloj de vruntime avanza más lento, haciendo que el sistema lo elija más a menudo.

Esta prioridad puede verse y modificarse en Linux desde la terminal. Para ver el niceness de los procesos, se puede ejecutar algo como ps ax -o pid,ni,cmd.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

# "NI" indica el niceness.
# Se puede ver que los elementos [kworker/...] tienen prioridad (niceness mínima),
# esto tiene sentido, ya que son hilos del kernel.
$ ps ax -o pid,ni,cmd | head
    PID  NI CMD
      1   0 /usr/lib/systemd/systemd --switched-root --system --deserialize=47 rhgb
      2   0 [kthreadd]
      3   0 [pool_workqueue_release]
      4 -20 [kworker/R-rcu_gp]
      5 -20 [kworker/R-sync_wq]
      6 -20 [kworker/R-kvfree_rcu_reclaim]
      7 -20 [kworker/R-slub_flushwq]
      8 -20 [kworker/R-netns]
     10 -20 [kworker/0:0H-kblockd]

Para ejecutar un programa con un niceness determinado, se puede ejecutar nice -n [NICENESS] programa, para cambiar el niceness de un proceso se puede usar renice.

1
2
3
4
5
6

$ nice -n 10 tarea_larga
$ nice -n -10 sudo tarea_importante 
# Para dar prioridad a un proceso (niceness negativo) suelen hacer falta privilegios de admin.
# En cambio, ser bueno hacia el resto es más fácil y no requiere nada 😃

renice -n 15 -p 9172 # Cambia niceness de proceso con PID 9172 a 15

Desde 2023 (versión del kernel 6.6), el kernel de Linux sustituyó por completo CFS y se introdujo un algoritmo de scheduling nuevo denominado EEVDF (Earliest Eligible Virtual Deadline First).

EEVDF comparte con CFS todo lo mencionado: Intenta ser justo entre todos los procesos, pero intenta solucionar el problema de la interactividad que tiene CFS.

Esto lo hace seleccionando de entre todos los procesos solo aquellos a los que el sistema “debe” tiempo de CPU (en base a una medida). Luego, se calcula para cada uno de ellos un deadline que representa el momento en el que el proceso debería terminar de recibir su cuota de CPU. Finalmente, de entre todos los procesos elegidos al principio, se elige el que tiene menor deadline (más temprano). Es decir, de nuevo, hace exactamente lo que indican sus siglas. Más info aquí.