• Suscríbete al Feed Espacio Linux
  • Suscríbete al Feed por Email
  • Sigue a Espacio Linux en Identi.ca
  • Espacio Linux también en Facebook
  • Sigue a Espacio Linux en Twitter
  • Sigue a Espacio Linux en Google +
          Iniciar sesión | Registrarse

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

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


Temas:
Documentación, Sistema


Etiquetas:
,

Feed Espacio LinuxSi este artículo ha sido de tu interés, considera hacer un comentario o suscribirte al feed para que te enteres de nuevos artículos a través de tu lector de noticias o email.

Acerca del autor

3 Comentarios para “El Planificador de Linux”

  1. 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

  2. Una Pregunta… Quien planifica al planificador..?

  3. Hello, tengo una pregunta,, como hago para cambiar la planificacion de linux con C o C++,,, porfavor ayudenme,, lo necesito de urgencia

Publica un comentario

Puedes usar estas etiquetas XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <blockquote cite=""> <code> <em> <strong>