Planificación apropiativa y no apropiativa

1. Que es la apropiacion

La apropiacion (preemption) es la capacidad del sistema operativo de quitarle la CPU a un proceso que esta ejecutandose, sin que el proceso la haya soltado voluntariamente. El proceso se interrumpe, se guarda su estado, y se le da la CPU a otro proceso. Cuando el proceso interrumpido vuelve a ejecutarse, continua desde donde se quedo.

Sin apropiacion, un proceso que no se bloquea ni termina puede usar la CPU indefinidamente. Con apropiacion, el sistema puede garantizar que todos los procesos reciben tiempo de CPU, incluso si uno de ellos es un bucle infinito.

La apropiacion se basa en el temporizador del hardware: el nucleo programa el temporizador para que genere una interrupcion periodicamente (cada quantum). Cuando la interrupcion ocurre, el nucleo invoca al planificador, que puede decidir cambiar de proceso.

2. Planificacion no apropiativa

En la planificacion no apropiativa (non-preemptive), una vez que un proceso recibe la CPU, la retiene hasta que termina o se bloquea voluntariamente. El sistema no puede quitarle la CPU.

Los momentos en que el sistema puede cambiar de proceso son solo los voluntarios: cuando el proceso termina, se bloquea en E/S, o cede la CPU explicitamente.

Las caracteristicas son:

• Simplicidad: no se necesita un temporizador ni interrupciones de quantum.
• Sin overhead de cambios forzados: no hay cambios de contexto por expiracion del quantum.
• Un proceso puede monopolizar la CPU: si un proceso no se bloquea ni termina, los demas esperan indefinidamente.
• Menor latencia de respuesta: si un proceso corto llega mientras se ejecuta uno largo, debe esperar a que el largo termine o se bloquee.

Los sistemas no apropiativos son adecuados para:

• Sistemas por lotes: donde los trabajos se ejecutan de principio a fin sin interaccion.
• Sistemas de tiempo real: donde un proceso debe completarse sin interrupciones (aunque esto es raro; la mayoria de los sistemas de tiempo real usan apropiacion con prioridades).
• Sistemas embebidos simples: donde la complejidad de la apropiacion no se justifica.

Ejemplos de algoritmos no apropiativos: FCFS (First-Come First-Served), SJF no apropiativo, planificacion por prioridades no apropiativa.

3. Planificacion apropiativa

En la planificacion apropiativa (preemptive), el sistema puede quitarle la CPU a un proceso que esta ejecutandose, incluso si no ha terminado ni se ha bloqueado. Esto se hace cuando expira el quantum, cuando llega un proceso de mayor prioridad, o cuando una interrupcion lo requiere.

La apropiacion requiere:

• Un temporizador de hardware: que genere interrupciones periodicas.
• Un manejador de interrupciones: que invoque al planificador.
• Soporte del hardware para guardar y restaurar el estado: el cambio de contexto.

Las caracteristicas son:

• Mejor respuesta: los procesos cortos e interactivos reciben la CPU rapidamente.
• Equidad: todos los procesos reciben turnos de CPU.
• Overhead: los cambios de contexto forzados consumen tiempo de CPU.
• Complejidad: requiere manejo de interrupciones y sincronizacion.

Los sistemas apropiativos son adecuados para:

• Sistemas de tiempo compartido: donde varios usuarios comparten la máquina.
• Sistemas interactivos: donde la respuesta al usuario es prioritaria.
• Sistemas de proposito general: Linux, Windows, macOS.

Ejemplos de algoritmos apropiativos: Round Robin, SRTF (SJF apropiativo), planificacion por prioridades apropiativa, CFS.

4. Los cuatro momentos de decision

El sistema operativo toma decisiones de planificacion en cuatro momentos. La diferencia entre un sistema apropiativo y uno no apropiativo esta en cuantos de estos momentos estan disponibles:

Los momentos 1 y 2 son voluntarios: el proceso cede la CPU. Los momentos 3 y 4 son involuntarios: el sistema decide cambiar de proceso.

En un sistema no apropiativo, solo se puede cambiar de proceso en los momentos 1 y 2 (voluntarios). En un sistema apropiativo, tambien se puede cambiar en los momentos 3 y 4 (involuntarios), y ademas cuando expira el quantum.

La diferencia clave es el momento 4: cuando un proceso bloqueado se desbloquea (por ejemplo, cuando llega un paquete de red o termina una lectura de disco), en un sistema apropiativo se puede interrumpir al proceso actual y ejecutar el que se desbloqueo. En un sistema no apropiativo, hay que esperar a que el proceso actual termine o se bloquee.

5. Apropiativo vs no apropiativo

La elección entre apropiativo y no apropiativo depende del caso de uso. Los sistemas de propósito general (Linux, Windows, macOS) usan apropiación porque la respuesta y la equidad son más importantes que la simplicidad. Los sistemas por lotes y algunos sistemas de tiempo real usan no apropiación porque la simplicidad y la predicibilidad son más importantes.

6. Apropiación y el quantum

En un sistema apropiativo, el quantum (o time slice) es el intervalo de tiempo que un proceso puede usar la CPU antes de que el planificador lo interrumpa. Es el mecanismo que hace posible el tiempo compartido.

El quantum se configura en el sistema operativo y puede variar:

• Linux (CFS): el quantum se calcula dinámicamente según el número de procesos listos. Típicamente 6 ms para pocos procesos, hasta 24 ms para muchos.
• Windows: el quantum es de ~10-15 ms para procesos normales, y ~1-2 ms para procesos de tiempo real.
• macOS: el quantum es de ~10 ms.

El quantum es un compromiso:

• Quantum muy corto: buena respuesta (los procesos interactivos reciben la CPU rápidamente), pero muchos cambios de contexto (overhead).
• Quantum muy largo: pocos cambios de contexto (bajo overhead), pero mala respuesta (los procesos interactivos esperan demasiado).

7. Apropiación en Linux

Linux es un sistema apropiativo. El núcleo puede quitarle la CPU a un proceso en cualquier momento, no solo cuando se bloquea o termina.

La apropiación en Linux se implementa con:

• El temporizador del hardware (timer interrupt): genera una interrupción periódica (típicamente cada 1-4 ms, según el kernel y la configuración).
• El manejador de interrupciones: invoca al planificador (schedule()) para decidir si cambiar de proceso.
• La apropiación por prioridad: si un proceso de mayor prioridad se vuelve listo, el planificador lo ejecuta inmediatamente.

Linux también soporta no apropiación para casos específicos:

• SCHED_BATCH: una política de planificación que minimiza las interrupciones para procesos de cálculo por lotes.
• SCHED_IDLE: una política que solo ejecuta el proceso cuando no hay nada más que hacer.
• Secciones críticas del núcleo: algunas operaciones del núcleo son no apropiativas para evitar inconsistencias.

En Linux, la apropiación se puede deshabilitar temporalmente en secciones críticas del núcleo (con preempt_disable()). Esto evita que una interrupción cambie de proceso mientras se manipulan estructuras internas del núcleo.

$ grep CONFIG_PREEMPT /boot/config-$(uname -r)
CONFIG_PREEMPT=y  # o CONFIG_PREEMPT_VOLUNTARY=y o CONFIG_PREEMPT_NONE=y

Linux se puede compilar con diferentes niveles de apropiación:

• CONFIG_PREEMPT_NONE: no apropiativo. Solo se planifica en puntos de bloqueo.
• CONFIG_PREEMPT_VOLUNTARY: apropiación voluntaria. El núcleo puede ceder la CPU en puntos específicos.
• CONFIG_PREEMPT: apropiación completa. El núcleo puede ser interrumpido en cualquier momento.
• CONFIG_PREEMPT_RT: tiempo real. Apropiación completa con latencia mínima.

8. Ventajas y desventajas

La apropiación tiene ventajas y desventajas:

La no apropiación también tiene ventajas:

En la práctica, todos los sistemas de propósito general (Linux, Windows, macOS) usan apropiación. Los sistemas por lotes y algunos sistemas embebidos usan no apropiación.

9. Un programa que demuestra la diferencia

El siguiente programa ejecuta un proceso que usa la CPU sin parar, y otro que hace E/S. Con apropiación, el proceso de E/S recibe la CPU entre los turnos del proceso de CPU. Sin apropiación, el proceso de CPU monopolizaría la CPU.

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

static double tiempo_ms(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec * 1000.0 + ts.tv_nsec / 1e6;
}

int main(void)
{
    /* Proceso limitado por CPU: usa la CPU sin parar */
    pid_t pid_cpu = fork();
    if (pid_cpu == 0) {
        volatile unsigned long x = 0;
        for (unsigned long i = 0; i < 2000000000UL; i++) x++;
        _exit(0);
    }

    /* Proceso limitado por E/S: hace E/S cada 100 ms */
    pid_t pid_io = fork();
    if (pid_io == 0) {
        for (int i = 0; i < 10; i++) {
            printf("I/O: iteracion %d\n", i);
            fflush(stdout);
            usleep(100000);  /* 100 ms */
        }
        _exit(0);
    }

    /* Padre: esperar a ambos */
    waitpid(pid_cpu, NULL, 0);
    waitpid(pid_io, NULL, 0);
    printf("Ambos terminaron\n");
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o apropiacion_demo apropiacion_demo.c
$ ./apropiacion_demo
I/O: iteracion 0
I/O: iteracion 1
I/O: iteracion 2
...
I/O: iteracion 9
Ambos terminaron

El proceso de E/S se ejecuta cada 100 ms, aunque el proceso de CPU use la CPU sin parar. Esto es porque el sistema es apropiativo: interrumpe al proceso de CPU y da turno al proceso de E/S. Sin apropiación, el proceso de E/S tendría que esperar a que el proceso de CPU terminara.

Se puede observar la apropiación con strace o con perf sched:

$ perf sched record ./apropiacion_demo
$ perf sched latency
 Task                  |   Runtime ms  | Switches | Avg delay ms | Max delay ms |
 ----------------------+---------------+----------+--------------+--------------+
 apropiacion_demo:CPU  |      2000.000 |       50 |        0.004 |        0.012 |
 apropiacion_demo:IO   |        10.000 |       10 |        0.002 |        0.008 |

El proceso de CPU se interrumpió 50 veces (cambios involuntarios). El proceso de E/S se ejecutó 10 veces (una por iteración). La latencia de despacho fue de ~4 us en promedio.

10. Resumen

• La apropiación es la capacidad de quitarle la CPU a un proceso sin que la haya soltado.
• En sistemas no apropiativos, un proceso retiene la CPU hasta que termina o se bloquea.
• En sistemas apropiativos, el sistema puede interrumpir al proceso (quantum, prioridad, interrupción).
• Los cuatro momentos de decisión son: terminación, bloqueo, creación y desbloqueo.
• El momento 4 (desbloqueo) es la diferencia clave entre apropiativo y no apropiativo.
• El quantum es el intervalo que un proceso puede usar la CPU antes de ser interrumpido.
• Linux es apropiativo y se puede compilar con diferentes niveles de apropiación.
• La apropiación mejora la respuesta y la equidad, pero añade overhead.
• Sistemas de tiempo real usan apropiación con prioridades para garantizar plazos.

11. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Compila y ejecuta apropiacion_demo.c. Observa como el proceso de E/S se ejecuta entre los turnos del proceso de CPU.
2. Verifica el nivel de apropiacion de tu kernel con grep CONFIG_PREEMPT /boot/config-$(uname -r).
3. Usa perf sched para observar la apropiacion en accion.
4. Escribe un programa que demuestre la diferencia entre apropiativo y no apropiativo (usando SCHED_BATCH).
5. Investiga el parche PREEMPT_RT y como reduce la latencia de despacho.
6. Compara la respuesta del sistema con CONFIG_PREEMPT_NONE vs CONFIG_PREEMPT.