Planificadores de disco genéticos

Los planificadores de disco (también conocidos como IO schedulers) son una parte del sistema operativo que se encarga de reordenar las peticiones de acceso al disco para garantizar equidad y el mejor tiempo de acceso posible. Esto es especialmente importante en entornos de multiprogramación, dónde el acceso concurrente de varios procesos al disco puede provocar que el acceso a bloques sea cercano a la aleatoriedad, provocando unos tiempos de posicionamiento (seek time) de los cabezales inaceptables. Para solucionar el problema se pueden aplicar distintas políticas (noop, elevator y sus variantes, etc..), pero en este caso vamos a hablar de schedulers genéticos.

Que son los algoritmos genéticos?

Los algoritmos genéticos son aquellos que, inspirados en la selección natural, ofrecen una heurística basada en la evolución de una población de posibles soluciones hasta llegar a la más óptima. Para ello deberemos determinar una función que sea capaz de evaluar en cada iteración lo adecuadas que son las soluciones. Para la siguiente iteración crearemos un nuevo grupo de soluciones usando los más óptimos del paso anterior y técnicas como la recombinación genética y la mutación.

Muy bien, todo muy bonito y elegante, pero ..

¿Por que usarlos para diseñar IO schedulers?

Las políticas de planificación de entrada/salida sirven a un fin en concreto; el Noop funciona muy bien para discos de estado sólido, el CFQ es ideal para sistemas multiusuario, y el anticipatorio funciona muy bien para servidores Apache, por ejemplo. Todos tienen terrenos muy marcados, y en caso de tener un entorno muy dinámico, con cargas de trabajo cambiantes, no sabremos por cual nos debemos decantar. Dado este ambiente, ¿que mejor que un algoritmo que evolucione hasta encontrar la solución más adecuada?

Las implementaciones actuales[1], desgraciadamente, no son capaces de estabilizar la población para encontrar una solución óptima en un tiempo razonable (se barajan tiempos de unos 1000 segundos para responder adecuadamente a la nueva carga del sistema). Afortunadamente, esto abre camino a nuevas investigaciones en este campo que prometen interesantes avances.

[1] A Study of Genetic Algorithms for I/O Scheduling