El Planificador de Linux

Porqué el Diseño del Planificador es crítico
Dos de las partes más críticas de un kernel son el subsistema de memoria y el planificador. Esto es debido a que estas dos piezas influyen en el diseño y afectan al comportamiento de prácticamente todos los demás elementos del kernel y del sistema operativo. Esta es también la razón por la que es deseable que estas dos piezas tengan un funcionamiento absolutamente correcto y un comportamiento óptimo. El kernel de Linux se utiliza en todo tipo de máquinas, desde pequeños dispositivos empotrados hasta grandes ordenadores (mainframes).
El diseño de su planificador es, en el mejor de los casos, magia negra.
No importa lo bueno que sea el diseño, siempre habrá quien piense que algunas categorías de procesos han tenido un trato injusto.

En el presente artículo he evitado deliveradamente incluir código porque
éste puede ser obtenido fácilmente en la red (ver las referencias). El artículo
dirige también la mirada hacia los desafíos con los que se han encontrado los
desarrolladores al rediseñar el planificador, hacia cómo han superado esos desafíos,
y hacia cuál podría ser la evolución futura del planificador. Dicho esto, no
hay nada como leer el código fuente para entender lo que sucede bajo la
superficie. Con los fuentes del kernel instalados, la implementación del
planificador se puede encontrar en kernel/sched.c.

Objetivos de la Planificación

El planificador de Linux intenta conseguir varios objetivos:

1. Ecuanimidad:

   El planificador debería repartir la CPU entre todos los procesos de forma
   ecuánime. En el nuevo kernel se ha trabajado para garantizar un
   reparto imparcial del tiempo de CPU entre los procesos.

2. Volumen de producción y eficiencia:

   El planificador debería intentar maximizar tanto el volumen de producción
   (throughput) como la eficiencia (utilización de la CPU). La forma habitual
   de incrementar la utilización de la CPU es incrementando el nivel de
   multiprogramación. Pero esto es beneficioso sólo hasta un cierto punto,
   a partir del cual se vuelve contraproducente.

3. Mínima Sobrecarga:

   Un planificador debería estar en ejecución el menor tiempo posible. La latencia
   del planificador debería ser mínima. Pero esta es la parte peliaguda. Generalmente
   la planificación en sí se considera trabajo no útil (??) . Ahora bien, si
   la planificación se hace de forma correcta aún a costa de consumir algo más de
   tiempo puede valer la pena. Pero ¿cómo decidimos cuál es el punto óptimo? La
   mayoría de los planificadores resuelven este problema utilizando políticas
   heurísticas.

4. Hacer cumplir una planificación basada en prioridades:

   Planificación basada en prioridades significa que algunos procesos tienen
   precedencia sobre otros. Como mínimo, el planificador debe distinguir entre
   procesos limitados por E/S y procesos limitados por CPU. Además, debe
   implementarse algún mecanismo que tenga en cuenta la edad de los procesos
   para evitar que algunos no tengan acceso a la CPU (inanición). Linux respeta
   las prioridades y distingue entre varias categorías de procesos. El kernel de
   Linux distingue entre trabajos planificados via batch y tareas interactivas.
   Todos ellos obtienen una cuota de CPU de acuerdo a sus prioridades.
   Probablemente alguien ha utilizado alguna vez el comando nice para cambiar
   la prioridad de un proceso.

5. Tiempo de turnaround, tiempo de espera:

   El tiempo de turnaround es la suma del tiempo de servicio y el tiempo de
   espera en la cola de ejecución (ready). El planificador intenta reducir ambos.

6. Tiempo de respuesta y variabilidad:

   El tiempo de respuesta de un programa debería ser lo menor posible. Además,
   otro factor importante, que a menudo se olvida, es la variabilidad entre los
   tiempos de respuesta. No es aceptable que el tiempo de respuesta medio sea
   bajo pero que algún usuario obtenga ocasionalmente un retraso de, digamos,
   diez segundos ejecutando un programa interactivo.

7. Miscelánea:

   El planificador intenta también cumplir otros objetivos como la predictibilidad.
   El comportamiento del planificador debería ser predecible para un conjunto dado
   de procesos con prioridades asignadas. El rendimiento del planificador debe
   decaer suavemente al aumentar la carga. Esto es especialmente importante en el
   caso de Linux al ser muy popular como servidor, ya que los servidores tienden a
   resultar sobrecargados durante los picos de mayor tráfico.

Mejoras en el planificador

• El algoritmo de planificación de complejidad O(1)

  El lector se puede preguntar, ¿qué es O(1)? Bien, voy a esbozar el significado
  de la notación O (conocida como O mayúscula – “Big-Oh”). Se pueden encontrar
  referencias a la notación O en cualquier buen libro de algoritmos.
  Esencialmente, la notación O intenta estimar el tiempo de ejecución de un
  algoritmo con independencia de los factores directamente relacionados con la
  máquina. Establece un límite superior al tiempo de ejecución del algoritmo,
  esto es, un límite superior al peor caso del algoritmo. Es una técnica
  excepcional para comparar la eficiencia de los algoritmos con respecto al tiempo
  de ejecución.

  Tomemos, por ejemplo, un algoritmo con dos bucles anidados y ambos con un
  rango de 1 a n-1 (donde n es el número de entradas del algoritmo), entonces
  el límite superior de su tiempo de ejecución se denota por
  O(N2). Análogamente, consideremos un algoritmo
  de búsqueda de un elemento en una lista enlazada desordenada. El peor caso
  es aquél en el que tenemos que recorrer toda la lista hasta su último
  elemento para localizar el elemento buscado o, pero aún, para comprobar que
  el elemento buscado no está en la lista. Decimos que este algoritmo tiene
  complejidad O(N) puesto que su tiempo de ejecución es
  directamente proporcional al número de elementos existentes en la lista – N.

  El planificador de Linux necesita un tiempo constante para planificar los
  procesos de la cola de ejecución (ready). En consecuencia, decimos que tiene
  complejidad O(1) . No importa cuál sea el número de procesos
  activos en el sistema Linux, el planificador siempre tarda un tiempo constante
  para planificar su ejecución. Todas las “partes” – activación, selección del
  siguiente proceso a ejecutar, conmutación del contexto y sobrecarga de la
  interrupción del temporizador – del kernel de Linux actual (la referencia aquí
  es la versión 2.5.49 – Ver los recursos para más detalles) tienen complejidad
  O(1). Por lo tanto, el nuevo planificador en su conjunto tiene complejidad O(1).

• Mejor Soporte para SMP y más escalable

  Como hemos mencionado en la introducción, el kernel de Linux puede ejecutarse en
  casi cualquier cosa desde relojes de pulsera a superordenadores. Los planificadores
  anteriores presentaban algunos problemas de escalabilidad. Algunos de estos
  problemas se resolvieron modificando el kernel específicamente para la aplicación
  y la arquitectura objetivos. Sin embargo, el diseño central del planificador no
  era muy escalable. El nuevo planificador es mucho más escalable y adecuado para
  SMP (Symmetric Multi-Processing: Multi-Procesamiento Simétrico). Ahora, el
  planificador se comporta mucho mejor que antes en sistemas SMP. Uno de los
  objetivos establecidos por Ingo Molnar, autor del planificador O(1), es que en
  SMP los procesadores no deberían estar inactivos cuando haya trabajo por hacer.
  Asimismo, se debería tener cuidado de que los procesos no se planifiquen para
  ejecución en procesadores diferentes ocasionalmente. De esta forma se evita la
  sobrecarga debida al relleno de la cache con los datos necesarios cada vez.

• Planificación batch de trabajos

  Esta no es exactamente una característica nueva, pero hay algunos parches que se
  pueden aplicar para añadir soporte de planificación batch. Los kernels anteriores
  también soportaban planificación batch en alguna medida. En la actualidad, la
  planificación batch se realiza utilizando niveles de prioridad. El kernel de
  Linux utiliza unos cuarenta niveles nice (si bien todos ellos son agrupados en unos
  cinco niveles de prioridad). Normalmente, los procesos planificados batch hacen
  uso de la CPU cuando no hay en ejecución muchos procesos interactivos ni procesos
  limitados por CPU, los cuales tienen mayor prioridad. Los procesos planificados
  batch obtienen cuantos temporales más largos que los procesos normales. De
  esta forma también se minimiza el efecto del intercambio frecuente de datos hacia
  y desde la cache, mejorando, por tanto, el comportamiento de los trabajos batch.

• Mejor comportamiento de los trabajos interactivos

  Entre los mayores avances del nuevo planificador se encuentran la detección de tareas
  interactivas y la mejora de su comportamiento. La detección de los trabajos
  interactivos se realiza en fragmentos de código desacoplados de los que realizan
  otras tareas de planificación como la gestión de los cuantos temporales. Los trabajos
  interactivos se detectan con la ayuda de estadísticas de uso. Esto significa que las
  tareas interactivas tienen buenos tiempos de respuesta bajo cargas de trabajo pesadas,
  y que los procesos ávidos de CPU no pueden monopolizar el tiempo de CPU. El nuevo
  planificador detecta las tareas interactivas y les otorga mayor precedencia que a
  otras tareas. Aún así, una tarea interactiva es planificada con otras tareas
  interactivas utilizando planificación Round-Robin. Esto es muy adecuado para usuarios
  de estaciones de trabajo ya que no apreciarán incrementos en los tiempos de respuesta
  cuando arrancan un trabajo con gran consumo de CPU como, por ejemplo, la codificación
  de canciones en formato ogg. Hay planes para combinar código O(1) y código expropiativo
  para mejorar los tiempos de respuesta de las tareas interactivas.

• Mayor escalabilidad y soporte para más arquitecturas

  Gracias al rediseño a que ha sido sometido, el nuevo planificador es más fácilmente
  escalable a otras arquitecturas como NUMA (Non-Uniform Memory Access: Acceso a Memoria
  No-Uniforme) y SMT. La arquitectura NUMA se utiliza en algunos servidores de altas
  prestaciones y supercomputadores. También se está trabajando en SMT (Symmetric
  Multi-Threading). SMT es conocido también por un nombre más popular: HyperThreading.
  Una de las razones es que ahora cada CPU tiene su propia cola de ejecución.
  Sólo la sub-parte de balanceo de carga tiene una visión “global” del sistema. De esta
  forma, las modificaciones para una arquitectura determinada tienen que hacerse,
  principalmente, en la sub-parte de balanceo de carga. También se ha publicado un
  parche para NUMA recientemente. De hecho, se ha incorporado en Linux 2.5.59. Los
  procesadores SMT implementan dos (o más) CPUs virtuales en el mismo procesador físico –
  un procesador “lógico” puede ejecutar código mientras el otro espera por acceso a
  memoria. Puede interpretarse SMT como una clase de sistema NUMA, puesto que los
  procesadores hermanos comparten la cache y, por lo tanto, acceden más rápidamente
  a aquellas direcciones de memoria a las que han accedido recientemente cualquiera de
  los otros. Se está trabajando también en SMT, pero el nuevo planificador O(1) maneja
  SMT bastante bien incluso sin ninguna modificación. Recientemente se ha liberado un
  parche para SMT. Aunque la arquitectura NUMA muestra cierto parecido con la
  arquitectura SMT, el planificador Linux los trata de forma diferente.

• Miscelánea

  El planificador da mayor prioridad a los hijos generados con fork() que al padre que los ha
  generado. Potencialmente, los servidores que utilizan la llamada fork para dar servicio a
  las peticiones podrían beneficiarse de esta característica. También podría ser útil para
  las aplicaciones GUI. También hay disponible en el kernel algo de planificación de tiempo
  real (basada en prioridades).

Recursos

• Página de Ingo Molnar: parches O(1)
• Interioridades del Kernel de Linux – Tigran Aivazian
• Consulte el Código Fuente del Kernel de Linux @ lxr.linux.no
  1. Diseño del Planificador
  2. Notas adicionales sobre funciones del planificador

Autor: Vinayak Hegde
Traducción al español por Rafa Pereira
el día 13 de Mayo 2003,
para La Gaceta de Linux