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:
-
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. - 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. - 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. - 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. - 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. - 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. - 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
Autor: Vinayak Hegde
Traducción al español por Rafa Pereira
el día 13 de Mayo 2003,
para La Gaceta de Linux
Jun 3rd, 2009 at 9:29
Esto es absolutamente genial. Es un privilegio que personas como Rafa Pereira se dediquen a traducir estas maravillas a las cuales los que no dominamos la lengua inglesa no tenemos acceso. Gracias y esta buenísimo
Sep 5th, 2009 at 10:31
Una Pregunta… Quien planifica al planificador..?
May 24th, 2010 at 14:35
Hello, tengo una pregunta,, como hago para cambiar la planificacion de linux con C o C++,,, porfavor ayudenme,, lo necesito de urgencia