Reglas, aumento de prioridad y trampas - Planificación de la CPU

1. Las reglas básicas

En el tema 25 vimos las reglas básicas de MLFQ. Las repetimos aquí para tenerlas como referencia:

Regla	Descripción
R1	Si la prioridad de A > prioridad de B, A se ejecuta.
R2	Si la prioridad de A = prioridad de B, se ejecutan en Round Robin.
R3	Cuando un proceso llega, se coloca en la cola superior.
R4	Si un proceso usa todo su quantum, baja una cola.
R5	Si un proceso se bloquea en E/S antes de usar su quantum, permanece en la misma cola.

Estas reglas parecen razonables, pero tienen un problema: son vulnerables a trampas.

2. El problema de las reglas básicas

Las reglas básicas tienen dos problemas fundamentales:

Inanición de las colas inferiores. Si siempre hay procesos en la cola superior, los procesos de las colas inferiores nunca se ejecutan. La regla R5 permite que un proceso interactivo se quede en la cola superior indefinidamente si hace E/S frecuente. inanición
Trampas (gaming). Un proceso puede manipular su comportamiento para mantenerse en la cola superior y acaparar la CPU. trampas

El primer problema se resuelve con el refuerzo periódico (sección 3). El segundo es más sutil y requiere cambiar las reglas.

3. El refuerzo periódico (priority boost)

El refuerzo periódico (priority boost) es una técnica que periódicamente mueve todos los procesos a la cola superior, independientemente de su cola actual. Es la regla R6 de MLFQ.

R6: Después de un intervalo de tiempo S, todos los procesos se mueven a la cola superior.

El refuerzo periódico resuelve dos problemas:

Inanición: garantiza que todo proceso reciba CPU periódicamente, incluso si está en la cola inferior.
Cambios de comportamiento: un proceso que era de cálculo y se vuelve interactivo sube a la cola superior en el próximo refuerzo.

El intervalo S es un parámetro crítico:

S muy corto: todos los procesos suben frecuentemente. MLFQ se comporta como Round Robin con el quantum de la cola superior. Se pierde la diferenciación.
S muy largo: los procesos de las colas inferiores esperan mucho. La inanición persiste.

El valor típico de S es de decenas a cientos de milisegundos, dependiendo del sistema.

S es el parámetro más importante de MLFQ

El intervalo de refuerzo determina el equilibrio entre equidad (S corto) y eficiencia (S largo). Elegir S es el mayor desafío de MLFQ.

4. Cómo engañar al planificador

Un proceso puede manipular su comportamiento para mantenerse en la cola superior y acaparar la CPU. Esto se llama gaming o trampa. Hay dos trampas principales:

Trampa de la E/S: un proceso de cálculo hace operaciones de E/S ficticias (por ejemplo, leer un byte del disco) justo antes de que se le acabe el quantum. Como se bloquea en E/S antes de usar todo su quantum, la regla R5 lo mantiene en la cola superior. E/S ficticia
Trampa del quantum corto: un proceso hace una ráfaga de CPU ligeramente menor que el quantum, luego se bloquea brevemente, y repite. Nunca usa todo su quantum, así que nunca baja de cola. quantum corto

Ambas trampas explotan la regla R5: un proceso que no usa todo su quantum se mantiene en la cola superior, aunque sea un proceso de cálculo disfrazado.

5. La trampa de la E/S

La trampa de la E/S es la más fácil de implementar. Un proceso de cálculo (que debería estar en la cola inferior) hace una operación de E/S ficticia cada quantum:

trampa_io.c

/* Proceso de calculo que se disfraza de interactivo. */
while (1) {
    /* Hacer calculo por (quantum - epsilon) tiempo. */
    calcular(quantum - 1);
    /* Hacer una E/S ficticia (leer un byte). */
    read(fd, buf, 1);
    /* El proceso se bloquea en E/S antes de usar todo su quantum. */
    /* Segun la regla R5, permanece en la cola superior. */
}

Este proceso recibe un quantum de la cola superior, hace cálculo casi todo el quantum, y luego hace una E/S ficticia. Como no usa todo su quantum, la regla R5 lo mantiene en la cola superior. El proceso acapara la CPU con prioridad máxima, perjudicando a los procesos interactivos genuinos.

La trampa funciona porque el planificador no puede distinguir entre una E/S genuina (el proceso realmente necesita datos) y una E/S ficticia (el proceso solo quiere mantener su prioridad).

6. La trampa del quantum corto

La trampa del quantum corto es similar pero no requiere E/S. El proceso hace una ráfaga de CPU ligeramente menor que el quantum, luego cede la CPU voluntariamente (por ejemplo, con sched_yield()), y repite:

trampa_yield.c

/* Proceso de calculo que cede la CPU antes de usar todo el quantum. */
while (1) {
    /* Hacer calculo por (quantum - epsilon) tiempo. */
    calcular(quantum - 1);
    /* Ceder la CPU voluntariamente. */
    sched_yield();
    /* El proceso no usó todo su quantum, así que no baja de cola. */
}

Este proceso recibe un quantum, hace cálculo casi todo el quantum, y luego cede. Como no usó todo su quantum, no baja de cola. El proceso se mantiene en la cola superior indefinidamente.

La trampa del quantum corto es más difícil de detectar que la de la E/S, porque no implica operaciones de E/S que se puedan monitorizar.

7. Cómo evitar las trampas

Hay varias soluciones para evitar las trampas:

Solución	Cómo funciona	Ventaja	Desventaja
Medir el uso de CPU acumulado	En lugar de mirar si el proceso usó todo su quantum, medir cuánta CPU ha usado en total. Si supera un umbral, baja de cola.	Detecta trampas de E/S y de quantum corto.	Más complejo de implementar.
Contar el quantum como usado	Si un proceso se bloquea en E/S, se considera que usó todo su quantum (baja de cola).	Simple, efectivo contra la trampa de E/S.	Puede perjudicar a procesos interactivos genuinos.
Limitar el tiempo en la cola superior	Un proceso no puede estar en la cola superior más de T unidades de tiempo acumuladas.	Garantiza que todos bajen eventualmente.	Pierde la adaptabilidad.
Monitorear las E/S	Detectar E/S ficticias (muy frecuentes, muy cortas) y penalizar al proceso.	Detecta la trampa de E/S.	Complejo, puede tener falsos positivos.

La solución más usada es la segunda: contar el quantum como usado cuando el proceso se bloquea en E/S. Si un proceso se bloquea (por E/S o por yield) antes de usar todo su quantum, se considera que usó todo su quantum y baja de cola. Esto hace que la trampa de la E/S sea inefectiva: el proceso baja de cola de todos modos.

Esta solución tiene un costo: los procesos interactivos genuinos (que se bloquean en E/S antes de usar su quantum) también bajan de cola. Pero como suben periódicamente (regla R6), el impacto es limitado.

8. Las reglas completas

Con las soluciones anteriores, las reglas completas de MLFQ son:

Regla	Descripción
R1	Si la prioridad de A > prioridad de B, A se ejecuta.
R2	Si la prioridad de A = prioridad de B, se ejecutan en Round Robin.
R3	Cuando un proceso llega, se coloca en la cola superior.
R4a	Si un proceso usa todo su quantum, baja una cola.
R4b	Si un proceso se bloquea en E/S (o cede la CPU), se considera que usó todo su quantum y baja una cola. (Anti-trampa.)
R5	Periódicamente (cada S unidades), todos los procesos suben a la cola superior. (Refuerzo.)

La regla R4b es la que hace que las trampas sean inefectivas: un proceso que se bloquea en E/S baja de cola de todos modos, así que no puede mantenerse en la cola superior haciendo E/S ficticias.

9. Cómo lo resuelve Linux

Linux resolvió el problema de las trampas de dos formas:

Linux O(1) (pre-CFS): usaba MLFQ con las reglas completas (incluyendo R4b). Además, medía el uso de CPU acumulado de cada proceso y ajustaba la prioridad dinámicamente. Un proceso que usaba mucha CPU bajaba de prioridad; uno que usaba poca subía.
Linux CFS (actual): abandonó MLFQ y usa un enfoque diferente: el vruntime. Cada proceso acumula vruntime a medida que se ejecuta. Los procesos con menos vruntime se ejecutan primero. No hay colas ni trampas: el vruntime es una medida continua del uso de CPU, y no se puede manipular haciendo E/S ficticias (porque el vruntime solo aumenta cuando el proceso se ejecuta en la CPU).

CFS es inmune a las trampas de MLFQ porque no usa reglas de quantum: la prioridad se basa en el tiempo de CPU acumulado, no en si el proceso usó todo su quantum.

10. Simulador interactivo

Este simulador muestra cómo un proceso puede engañar a MLFQ con la trampa de la E/S, y cómo la regla R4b la evita:

Simulador · trampas en MLFQ

Modo Ráfaga del tramposo Ráfaga de los normales

Proceso	Tipo	Ráfaga	Inicio	Fin	Espera	Retorno

11. Resumen

Las reglas básicas de MLFQ son vulnerables a trampas.
La trampa de la E/S: hacer E/S ficticia para mantenerse en la cola superior.
La trampa del quantum corto: ceder la CPU antes de usar todo el quantum.
El refuerzo periódico (R6) resuelve la inanición de las colas inferiores.
La regla R4b (contar el quantum como usado al bloquearse) evita las trampas.
Linux CFS es inmune a las trampas porque usa vruntime en lugar de reglas de quantum.
El parámetro S (intervalo de refuerzo) es crítico para el comportamiento de MLFQ.

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

1. ¿Qué es una trampa en MLFQ?

Manipular el comportamiento del proceso para mantenerse en la cola superior y acaparar la CPU.

2. ¿En qué consiste la trampa de la E/S?

Hacer operaciones de E/S ficticias justo antes de que se acabe el quantum, para que la regla R5 mantenga al proceso en la cola superior.

3. ¿En qué consiste la trampa del quantum corto?

Hacer una ráfaga ligeramente menor que el quantum y ceder la CPU, para no usar todo el quantum y no bajar de cola.

4. ¿Qué es el refuerzo periódico?

Mover todos los procesos a la cola superior periódicamente (cada S unidades de tiempo).

5. ¿Qué problema resuelve el refuerzo periódico?

La inanición de las colas inferiores y los cambios de comportamiento.

6. ¿Qué es la regla R4b?

Si un proceso se bloquea en E/S, se considera que usó todo su quantum y baja de cola.

7. ¿Cómo evita la regla R4b las trampas?

Haciendo que las trampas de E/S sean inefectivas: el proceso baja de cola de todos modos.

8. ¿Por qué Linux CFS es inmune a las trampas de MLFQ?

Porque usa vruntime (tiempo de CPU acumulado) en lugar de reglas de quantum.

9. ¿Qué parámetro de MLFQ es el más crítico?

S, el intervalo de refuerzo periódico.

10. ¿Qué ocurre si S es muy corto?

MLFQ se comporta como Round Robin con el quantum de la cola superior.

Para practicar

Implementa la trampa de la E/S en el simulador y observa cómo el proceso acapara la CPU.
Activa la regla R4b y verifica que la trampa deja de funcionar.
Compara el comportamiento con S = 10 y S = 100.
Diseña una trampa que no use E/S ficticia.
Explica por qué CFS es inmune a las trampas de MLFQ.
Investiga cómo Windows previene las trampas en su planificador.