Colas de procesos y el planificador

1. Qué son las colas de procesos

Las colas de procesos son estructuras de datos del núcleo que organizan los procesos según su estado y lo que estan esperando. En lugar de tener una lista desordenada de todos los procesos, el núcleo mantiene colas separadas: una para los procesos listos para ejecutarse, y una para cada evento o recurso que los procesos pueden estar esperando.

Las colas no son colas en el sentido estricto (FIFO): son estructuras que permiten al planificador elegir rápidamente el siguiente proceso a ejecutar, y a los subsistemás del núcleo despertar a los procesos correctos cuándo ocurre un evento. En linux, las colas de listos se implementan como arboles rojo-negro (para CFS) o como listas doblemente enlazadas (para colas de espera).

Hay dos tipos fundamentales de colas:

• Cola de listos (run queue): contiene los procesos que estan listos para ejecutarse. El planificador elige de esta cola.
• Colas de espera (wait queues): una por cada evento o recurso. Contienen los procesos bloqueados esperando ese evento. Cuando el evento ocurre, los procesos se mueven de la cola de espera a la cola de listos.

2. La cola de listos

La cola de listos (run queue) contiene todos los procesos que estan en estado listo: preparados para ejecutarse, pero esperando que el planificador les asigne la CPU. Cada CPU tiene su propia cola de listos, lo que permite que los procesos se distribuyan entre los núcleos sin contencion.

En linux, la cola de listos no es una sola cola FIFO. Esta dividida en dos partes:

Los procesos de tiempo real siempre se ejecutan antes que los normales. Solo cuándo no hay procesos de tiempo real listos, el planificador atiende la cola normal. Los procesos normales nunca privan de CPU a los de tiempo real (a menos que estos ultimos se bloqueen).

3. Las colas de espera

Cada vez que un proceso se bloquea esperando un evento (leer del disco, recibir datos de la red, esperar a un hijo, adquirir un mutex), el núcleo lo saca de la cola de listos y lo pone en una cola de espera asociada a ese evento. Cuando el evento ocurre, el núcleo despierta a los procesos de esa cola y los mueve de vuelta a la cola de listos.

Hay una cola de espera por cada evento o recurso que se puede esperar:

Las colas de espera se implementan como listas doblemente enlazadas. Cuando un proceso se bloquea, se agrega a la lista. Cuando el evento ocurre, el núcleo recorre la lista y despierta a los procesos (los mueve a la cola de listos). En algunos casos se despierta a todos los procesos de la cola; en otros, Sólo a uno.

Un proceso puede estar en varias colas de espera a la vez, Sí esta esperando varios eventos. Y puede estar en una cola de espera y en la cola de listos simultaneamente, Sí fue despertado pero aun no se ejecuto.

4. El planificador

El planificador (scheduler) es el componente del núcleo que decide que proceso de la cola de listos se ejecuta a continuacion. Es el que dispara la transicion dispatch del diagrama de estados. Su objetivo es repartir la CPU entre los procesos de forma justa y eficiente.

El planificador se ejecuta en dos situaciones:

• Voluntariamente: Cuándo un proceso se bloquea (llama a read, sleep, wait) o termina (exit), cede la CPU llamando al planificador.
• Involuntariamente: Cuándo expira el cuánto de tiempo de un proceso en ejecución, el temporizador del núcleo interrumpe al proceso y llama al planificador (Preempcion).

El planificador no es un proceso ni un hilo: es código del núcleo que se ejecuta en el contexto del proceso actual cuándo se invoca. No tiene su propio PCB ni su propio espacio de direcciónes. Es simplemente una función del núcleo (schedule()) Que se llama cuándo hay que elegir un nuevo proceso.

5. CFS: el planificador de linux

Linux usa el Completely fair scheduler (CFS) para los procesos normales (SCHED_NORMAL). CFS intenta repartir la CPU de forma equitativa entre todos los procesos listos, de manera que cada uno reciba una fraccion proporcional a su peso (Prioridad).

La idea central de CFS es simple: mantiene un tiempo virtual para cada proceso, Que es el tiempo de CPU Que ha recibido ajustado por su peso. El proceso con el menor tiempo virtual es el que más tiempo de CPU necesita, y por eso es el que se ejecuta a continuacion.

CFS implementa esto con un arbol rojo-negro ordenado por tiempo virtual. El proceso con el menor tiempo virtual esta en el extremo izquierdo del arbol, y se puede encontrar en tiempo logaritminimo. Cuando un proceso se ejecuta, su tiempo virtual aumenta; Cuándo se bloquea, se saca del arbol; Cuándo se desbloquea, se reinserta.

CFS no usa un cuánto de tiempo fijo. En su lugar, calcula el tiempo que cada proceso debe ejecutarse para que, en un período dado (tipicamente 6 ms en un sistema con pocos procesos, hasta 24 ms con muchos), todos los procesos reciban su parte proporcional. El cuánto de tiempo de cada proceso es proporcional a su peso.

Esto significa que con pocos procesos, cada uno recibe un cuánto largo (buena respuesta, poco cambio de contexto). Con muchos procesos, cada uno recibe un cuánto corto (Más cambio de contexto, pero más equitativo).

6. El cuánto de tiempo

El Cuánto de tiempo (time slice o quantum) es la cantidad maxima de tiempo que un proceso puede usar la CPU antes de que el planificador lo interrumpa y le de el turno a otro. Es el mecanismo que hace posible el tiempo compartido: cada proceso recibe un pedazo de CPU, y sí no termina en ese tiempo, vuelve a la cola de listos.

En los sistemás clasicos, el cuánto es fijo (por ejemplo, 10 ms). En linux con CFS, el cuánto se calcula dinaminimamente según el número de procesos listos y sus pesos. Pero el concepto es el mismo: un proceso no puede usar la CPU indefinidamente sin que el planificador intervenga.

Cuando el cuánto expira, el temporizador del núcleo genera una interrupcion, el núcleo llama al planificador, y sí hay otro proceso con mayor prioridad o menor tiempo virtual, hace un cambio de contexto. Si el proceso actual sigue siendo el de mayor prioridad, puede continuar ejecutandose (con un nuevo cuánto).

7. Prioridades y nice

Los procesos no son todos iguales: algunos necesitan más CPU Que otros. El sistema permite asignar Prioridades a los procesos, Que el planificador usa para decidir a quién le toca el turno y cuánto tiempo recibe.

En linux hay dos mecanismos de prioridad:

• Prioridad estatica (nice): un valor de -20 a +19 Que el usuario o el programa asigna. -20 es la mayor prioridad, +19 la menor. Por omision, los procesos heredan el nice de su padre (tipicamente 0). Solo root puede asignar nice negativo.
• Prioridad dinaminima: el planificador ajusta la prioridad de un proceso según su comportamiento. Un proceso que usa mucha CPU recibe menor prioridad (es "penalizado"); un proceso interactivo que se bloquea frecuentemente recibe mayor prioridad (es "beneficiado"). Esto mejora la respuesta del sistema para el usuario.

En CFS, el nice se traduce a un peso. Un proceso con nice -20 tiene un peso mucho mayor que uno con nice +19, por lo que recibe una fraccion mayor de la CPU. La relacion es exponencial: cada nivel de nice cambia el peso en un factor de ~1.25.

Para cambiar el nice de un proceso desde la shell se usa nice (al lanzarlo) o renice (Después):

$ nice -n 10 ./programa (lanzar con nice 10)
$ renice -n 5 -p 1234 (cambiar nice del proceso 1234 a 5)
$ renice -n -5 -u ana (cambiar nice de todos los procesos de ana)

Desde C, se usa nice() o setpriority():

#define _POSIX_C_SOURCE 200809L
#include 
#include 
#include 

int main(void)
{
    int actual = getpriority(PRIO_PROCESS, 0);
    printf("nice actual: %d\n", actual);

    /* Subir el nice (bajar prioridad) - no requiere privilegios */
    if (setpriority(PRIO_PROCESS, 0, 10) == 0)
        printf("nice cambiado a 10\n");
    else
        perror("setpriority");

    /* Bajar el nice (subir prioridad) - requiere root */
    /* setpriority(PRIO_PROCESS, 0, -5); */

    return 0;
}

8. Colas de E/S

Además de la cola de listos y las colas de espera, el núcleo mantiene colas de E/S para los dispositivos. Cuando un proceso pide leer del disco o de la red, la operación se encola en la cola del dispositivo correspondiente, y el proceso se bloquea. Cuando el dispositivo termina la operación, el núcleo despierta al proceso.

Las colas de E/S son importantes para el rendimiento: Sí muchos procesos piden E/S al mismo tiempo, las operaciónes se serializan en la cola del dispositivo. El orden en que se atienden depende del planificador de E/S (I/O scheduler), Que puede reordenar las operaciónes para optimizar el acceso al disco (por ejemplo, agrupando lecturas cercanas en el disco).

En linux, los planificadores de E/S Disponibles son:

El planificador de E/S se configura por dispositivo en /sys/block/DEVICE/Queue/scheduler.

9. El planificador y el cambio de contexto

Cuando el planificador decide cambiar de proceso, se produce un cambio de contexto: el núcleo guarda el estado de la CPU del proceso actual en su PCB, carga el estado del nuevo proceso desde su PCB, y salta a la instruccion dónde se quedo. Es una operación costosa que incluye:

1. Guardar registros: el contador de programa, el puntero de pila, los registros generales y los de punto flotante se guardan en el PCB del proceso que sale.
2. Cambiar tablas de páginas: se actualiza el registro CR3 (en x86) para que la CPU use las tablas de páginas del nuevo proceso. Esto invalida la TLB (Translation lookaside buffer), Que cachea traducciones de direcciónes.
3. Cambiar la pila del núcleo: se actualiza el puntero de pila para usar la pila del núcleo del nuevo proceso.
4. Restaurar registros: se cargan los registros del nuevo proceso desde su PCB.
5. Actualizar current: el puntero current se actualiza para apuntar al nuevo proceso.
6. Retornar: se retorna de la función schedule() al nuevo proceso, Que continua ejecutandose.

El costo del cambio de contexto es de unos 1-10 microsegúndos, dependiendo del hardware y de sí la TLB se invalida completamente. Por eso, un sistema con muchos cambios de contexto por segúndo (por ejemplo, con cuántos muy cortos) puede tener un rendimiento reducido.

Los hilos tienen un cambio de contexto más barato que los procesos, porque comparten el espacio de direcciónes y no requieren cambiar las tablas de páginas. Es una de las razones por las que los hilos son preferibles para táreas que requieren mucha sincronizacion.

10. Observar la planificacion en /proc

Linux expone información sobre la planificacion en varios archivos de /proc:

$ cat /proc/self/sched | head -10
systemd (1, #threads: 1)
-------------------------------------------------------------------
se.exec_start                      : 12345678.901234
se.vruntime                        : 987654.321000
se.sum_exec_runtime                : 1234.567890
nr_switches                        : 5678
nr_voluntary_switches              : 1234
nr_involuntary_switches            : 4444
$ cat /proc/loadavg
0.05 0.02 0.01 2/123 4567

El campo nr_voluntary_switches cuenta los cambios de contexto que el proceso provoco voluntariamente (al bloquearse). nr_involuntary_switches cuenta los que provoco el planificador (al expirar el cuánto). La carga promedio (loadavg) Indica cuántos procesos estan listos o bloqueados: un valor alto significa que el sistema esta saturado.

11. Un programa que observa la planificacion

El siguiente programa crea varios procesos con distintos nice y los hace competir por la CPU, para observar como el planificador reparte el tiempo:

#define _POSIX_C_SOURCE 200809L
#include 
#include 
#include 
#include 
#include 

int main(void)
{
    int nice_values[] = {0, 10, -5};
    int n = 3;

    for (int i = 0; i < n; i++) {
        pid_t pid = fork();
        if (pid == 0) {
            setpriority(PRIO_PROCESS, 0, nice_values[i]);
            /* Usar la CPU durante 2 Segúndos */
            volatile unsigned long x = 0;
            for (int t = 0; t < 2; t++) {
                for (volatile int j = 0; j < 100000000; j++) x++;
            }
            printf("Proceso %d (nice %d) Terminó\n", getpid(), nice_values[i]);
            _exit(0);
        }
    }

    for (int i = 0; i < n; i++)
        wait(NULL);

    printf("Todos terminaron. Observa con: ps -o pid,ni,pcpu,comm\n");
    return 0;
}

Los procesos con nice menor (mayor prioridad) reciben más tiempo de CPU. Puedes observar esto con top o ps mientras se ejecutan.

12. Resumen

• Las colas de procesos organizan los procesos por estado y evento esperado.
• La cola de listos contiene los procesos listos para ejecutarse; hay una por CPU, con cola de tiempo real y cola normal (CFS).
• Las colas de espera contienen los procesos bloqueados esperando un evento.
• El planificador decide que proceso ejecutar a continuacion; se ejecuta voluntariamente (al bloquearse) o involuntariamente (al expirar el cuánto).
• CFS usa un arbol rojo-negro ordenado por tiempo virtual para repartir la CPU de forma equitativa.
• El cuánto de tiempo se ajusta dinaminimamente según el número de procesos listos.
• La prioridad nice (de -20 a +19) afecta el peso del proceso en CFS.
• Los cambios de contexto tienen un costo de 1-10 microsegúndos.
• Se puede observar la planificacion en /proc/PID/sched, /proc/sched_debug y /proc/loadavg.

13. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para prácticar

1. Ejecuta planificacion.c y observa con top como se reparte la CPU entre procesos con distintos nice.
2. Consulta /proc/self/sched y /proc/loadavg en tu sistema.
3. Usa nice y renice para cambiar la prioridad de un proceso y observa el efecto en top.
4. Lee /proc/sched_debug para ver las colas de listos del sistema.
5. Compara el número de cambios voluntarios e involuntarios de un proceso interactivo (Como bash) con uno que usa la CPU (Como un bucle infinito).
6. Consulta el planificador de E/S de tu disco con cat /sys/block/sda/Queue/scheduler.