Nuevo scheduler para el kernel
Con Kolivas ha presentado una nueva propuesta del scheduler para el kernel. Parece tan buena, y es tan simple y clara la estructura que seguramente será integrada rápidamente (quizás para la versión 2.6.22), el Rotating Staircase Deadline Scheduler.
Este nuevo planificador sigue teniendo, como los anteriores y estándar en UNIX, una lista activa y una inactiva. Los procesos sólo se seleccionan de la activa, cuando consumen todo su tiempo se mueven a la inactiva. Cuando ya no hay más procesos en la lista activa se intercambian los punteros y la que estaba inactiva pasa a ser la activa –y viceversa–.
Pero lo anterior no es lo nuevo, sino en cómo está estructurada cada una de esas listas. Como es de esperar, continúa con las bien conocidas “múltiples colas con retroalimentación”. Cada lista está dividida en varios niveles, cada nivel corresponde a una prioridad. Los procesos son movidos dinámicamente de un nivel a otra dependiendo de su prioridad dinámica –el nice en UNIX–.
Los procesos son seleccionados siempre por el nivel de mayor prioridad, sólo si no hay más procesos en ese nivel se pasa al siguiente –tal como se hace en el método de múltiples colas–.
A cada proceso se le asigna dos límites temporales –o cuantos–, una para el nivel en que están y otro para el tiempo máximo que pueden pasar antes de ser movidos a la cola inactiva. Cuando a un proceso se le acaba el tiempo para el nivel en que está es movido hacia el nivel inferior.
Pero además cada nivel tiene asignado un tiempo máximo, si se supera ese tiempo, todos los procesos que todavía están en dicho nivel son movidos al nivel inferior –le llaman una “rotación menor–.
Finalmente, cuando un proceso acaba su cuanto –o expiración– es movido a la cola inactiva. Cuando ya no quedan más procesos en la cola activa, se intercambian las colas, le llama “rotación mayor”.
Este método es muy simple, mucho más sencillo que el método actual, donde la prioridad está calculada por el tiempo de espera de cada proceso. Este cálculo es bastante complejo e impredecible, por lo que no se pueden calcular tiempos de respuesta máximo. En cambio con el nuevo método sí se puede calcular y demostrar formalmente que existe un tiempo máximo, y por lo tanto no se producen esperas infinitas (o starvations).
Parece que los tests que están haciendo para cargas extremas está dando resultados espectaculares, así que seguramente será rápidamente admitido en la siguiente ronda de desarrollo para el 2.0.22. La verdad es que ste nuevo scheduler me impresionó bastante, en primer lugar porque es de tan simple es bello, y en segundo lugar porque reusa, simplifica y mejora ideas que tienen 30 años.
Pero también me sorprende su autor, un médico en activo, solucionando semejante tipo de problemas informáticos.
Disclaimer: este apunte es una procastinación tamaño baño.
Ricardo,
Cuando dices “Los procesos son movidos dinámicamente de un nivel a otra dependiendo de su prioridad dinámica –el nice en UNIX–.” creo que te equivocas.
En Linux, la prioridad estática se define y controla mediante llamadas al sistema como nice(2), mientras que la prioridad dinámica se calcula a partir de la prioridad estática y, a su vez, es modificada dinámicamente por el núcleo en función del comportamiento del proceso. Cuando un proceso agota su quanto, su prioridad dinámica es disminuída. Cuando un proceso despierta de un estado de espera, su prioridad dinámica se incrementa para que entre en ejecución lo antes posible.
Comment by Felipe Alfaro Solana — Saturday 10/3/2007 @ 4:16
> Cuando dices “Los procesos son movidos dinámicamente de un nivel a otra dependiendo de su prioridad dinámica –el nice en UNIX–.” creo que te equivocas.
Sí, cony…
> Cuando un proceso agota su quanto, su prioridad dinámica es disminuída. Cuando un proceso despierta de un estado de espera, su prioridad dinámica se incrementa para que entre en ejecución lo antes posible.
Esa es la teoría básica de “colas múltiples con retroalimentación”, pero no es así en la realidad, mucho menos en el Linux, que es bastante más complejo para mejorar la respuesta de los procesos interactivos. Depende del valor de “sleep” del proceso y las prioridad de procesos relacionados que generan el “schedule”.
Comment by gallir — Saturday 10/3/2007 @ 10:42
> “Parece que los tests que están haciendo para cargas extremas está dando resultados espectaculares”
Sí, y lo que es muy interesante también es que gente de la LKML ha estado haciendo tests en entornos de escritorio con cargas de trabajo típicas y también han _notado_ una mejora, por lo que hay gente que opina que debería ser el planificador de procesos por defecto.
Comment by Tribe — Saturday 10/3/2007 @ 12:35
Dices que ahora puede calcularse un tiempo máximo de espera en las colas con este nuevo método. Entonces, ¿es un paso más para hacer de la ejecución de programas algo determinista?
Un saludo.
Comment by Arturo — Saturday 10/3/2007 @ 13:04
No, no es determinista porque no puedes establecer orden de ejecución. Sólo puedes calcular un tiempo máximo.
Comment by gallir — Saturday 10/3/2007 @ 13:35
Esta clase de post son los que mas me gustan de este blog :).
Comment by antonimo — Saturday 10/3/2007 @ 21:04
Hay que reconocer que Con Kolivas es una persona un tanto atípica, aunque me gustaría saber hasta que punto se puede decir que es un médico en activo, y no una persona que hizo la carrera de medicina (para mi son cosas muy distintas).
Y digo que es atípica porque la inmensa mayoría de los médicos que conozco son analfabétos tecnológicos, y prácticamente siempre tecnofobos (se que es una afirmación un tanto gratuita porque estoy generalizando en un colectivo muy amplio, pero trabajo para sanidad y tengo cierta experiencia en pelear con médicos)
Comment by DN — Sunday 11/3/2007 @ 3:07
Un nuevo planificador para el kernel de Linux
Un excelente artículo de Ricardo Galli en el que se hace una breve introducción al que parece que será el nuevo planificador de procesos del kernel de Linux. Si todo va bien, puede que sea incorporado ya en la versión 2.6.22. Lo más curioso del caso es…
Trackback by meneame.net — Wednesday 14/3/2007 @ 8:48
> Parece que los tests que están haciendo para cargas extremas está dando resultados espectaculares, así que seguramente será rápidamente admitido en la siguiente ronda de desarrollo para el 2.0.22.
no es 2.6.22 ?
Comment by davkx — Wednesday 14/3/2007 @ 17:35
Una gráfica aclaratoria de como va a funcionar este cacharro, vendría muy bien, para aclarar el tema a los más noveles (/me=novel).
Comment by Ricardo Fuentes — Wednesday 14/3/2007 @ 17:47
Ese no es el esquema tipico de un planificador normal y corriente? (solo pregunto)
Comment by nefertum — Wednesday 14/3/2007 @ 20:58
#10, el #11 tiene razón, ese esquema es muy básico y se llama “esquema de tres estados” (algunos eruditos prefieren llamarle “diagrama de Nail”).
No tiene nada que ver con el scheduler, o sí, tanto como las las ruedas y las gravedad con los diseños de coches
Comment by gallir — Wednesday 14/3/2007 @ 22:15
Si, lo se, solo lo ponía como ejemplo, haber si ud. profesor, nos daba una mano a los noveles para poder entender el nuevo scheduler del kernel
Comment by Ricardo Fuentes — Thursday 15/3/2007 @ 0:25
Buen post. Y para ayudar a la procrastinacion una pregunta sobre planificadores… ¿Que pasa con el de disco?, ¿los nuevos discos duros NAND haran innecesaria la planificacion de disco o de momento vamos a trabajar emulando discos con platos y cabezas?. Mira que me fastidiaria haberme chapado lo del CSCAN para que ahora desaparezca…
Comment by nim — Thursday 15/3/2007 @ 15:46
#14, en discos esta funcionando muy bien el “nuevo” CFQ (complete fair queue) que lo comenté en su momento: http://mnm.uib.es/gallir/posts/2004/12/25/49/
Lo de discos NAND, seguramente hará que cambie esta necesidad, aunque no la planificación, la CFQ sigue siendo muy buena para entornos de multiprogramación. Pero supongo que aparecerán otros problemas, como controlar la cantidad de escrituras que se hacen sobre la misma posición.
Comment by gallir — Thursday 15/3/2007 @ 16:06
Aquí hablan del nuevo Scheduler, reproduciendo un mail de Ingo Molnar http://kerneltrap.org/node/8059
Un saludete
Comment by habladorcito — Thursday 19/4/2007 @ 22:47