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).
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 vía 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.
Linux está basado en la planificación tradicional de Unix añadiendo 2 clases de prioridad para procesos de tiempo real flexibles. Las tres clases de prioridad de Linux son las siguientes:
SCHED_FIFO: hilos de tiempo real con planificación FIFO.
SCHED_RR: hilos de tiempo real con planificación por turno rotatorio.
SCHED_OTHER: hilos que no son de tiempo real y otros.
Dentro de cada clase se utilizan múltiples prioridades, siendo las prioridades de las clases de tiempo real mayores que la de la clase SCHED_OTHER. Para los hilos FIFO, se aplican las siguientes reglas:
1. El sistema no interrumpe la ejecución de un hilo FIFO, excepto en los siguientes casos:
a) Pasa a estar listo otro hilo FIFO de mayor prioridad.
b) El hilo FIFO en ejecución se bloquea a la espera de un evento, como una E/S.
c) El hilo FIFO en ejecución abandona el procesador como resultado de la ejecución de la primitiva sched_yield.
2. Cuando se interrumpe un hilo FIFO en ejecución, pasa a la cola asociada a su prioridad.
3. Cuando un hilo FIFO pasa a listo y tiene mayor prioridad que el hilo que está en ejecución, se expulsa al hilo en ejecución y pasa a ejecutar el hilo de mayor prioridad. Si más de un hilo tiene esta mayor prioridad, se escoge al que lleva más tiempo esperado.
La política SCHED_RR es similar a la SCHED_FIFO, excepto por el uso de un cuanto de tiempo asociada a cada hilo. Cuando un hilo SCHED_RR ha consumido su cuanto de tiempo, pasa a suspendido y se escoge un hilo de tiempo real con una prioridad igual o mayor.
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 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).
INTEGRANTES
CABRERA KARLA
PULLA CINTHIA
RAMOS JAMMIL
