Un planificador O(1) (pronunciado "planificador O de 1", "planificador O grande de 1" o "planificador de tiempo constante") es un diseño de planificación del núcleo que puede planificar procesos dentro de una cantidad de tiempo constante, independientemente de cuántos procesos se estén ejecutando en el sistema operativo . Esto es una mejora con respecto a los planificadores O(n) utilizados anteriormente , que programan procesos en una cantidad de tiempo que escala linealmente en función de las cantidades de entradas.
En el ámbito de los sistemas operativos en tiempo real , la ejecución determinista es clave, y un programador O(1) puede proporcionar servicios de programación con un límite superior fijo en los tiempos de ejecución.
El programador O(1) se utilizó en las versiones de Linux 2.6.0 a 2.6.22 (2003-2007), momento en el que fue reemplazado por el Programador Completamente Justo .
El planificador de Linux fue revisado completamente con el lanzamiento del kernel 2.6 en 2003. [1] [2] El nuevo planificador se llamó planificador O(1). El algoritmo utilizado por el planificador O(1) se basa en matrices de procesos activos y expirados para lograr un tiempo de programación constante. A cada proceso se le asigna un quantum de tiempo fijo, después del cual se lo preempta y se lo mueve a la matriz expirada. Una vez que todas las tareas de la matriz activa han agotado su quantum de tiempo y se han movido a la matriz expirada, se produce un cambio de matriz. Debido a que se accede a las matrices solo a través de punteros, cambiarlas es tan rápido como intercambiar dos punteros. [3] Este cambio hace que la matriz activa sea la nueva matriz expirada vacía, mientras que la matriz expirada se convierte en la matriz activa.
Un algoritmo opera sobre una entrada, y el tamaño de esa entrada generalmente determina su tiempo de ejecución. La notación Big O se utiliza para indicar la tasa de crecimiento del tiempo de ejecución de un algoritmo en función de la cantidad de entrada. Por ejemplo, el tiempo de ejecución de un algoritmo O(n) aumenta linealmente a medida que crece el tamaño de la entrada n. [4] El tiempo de ejecución de un algoritmo O(n 2 ) crece cuadráticamente . Si es posible establecer un límite superior constante para el tiempo de ejecución de un algoritmo, se considera que es O(1) (se podría decir que se ejecuta en "tiempo constante"). Es decir, se garantiza que un algoritmo O(1) se completará en una cierta cantidad de tiempo independientemente del tamaño de la entrada. [5]
El planificador de Linux 2.6.8.1 no contenía ningún algoritmo que se ejecutase en un tiempo peor que O(1). [6] Es decir, se garantiza que cada parte del planificador se ejecutará dentro de una cierta cantidad constante de tiempo independientemente de cuántas tareas haya en el sistema. Esto permite que el núcleo de Linux maneje eficientemente cantidades masivas de tareas sin aumentar los costos generales a medida que crece el número de tareas. Hay dos estructuras de datos clave en el planificador de Linux 2.6.8.1 que le permiten realizar sus tareas en tiempo O(1), y su diseño gira en torno a ellas: colas de ejecución y matrices de prioridad.
El principal problema de este algoritmo es la compleja heurística que se utiliza para marcar una tarea como interactiva o no interactiva. El algoritmo intenta identificar los procesos interactivos analizando el tiempo medio de inactividad (la cantidad de tiempo que el proceso pasa esperando una entrada). Los procesos que inactivan durante largos períodos de tiempo probablemente estén esperando la entrada del usuario, por lo que el programador supone que son interactivos. El programador otorga una bonificación de prioridad a las tareas interactivas (para un mejor rendimiento) mientras penaliza las tareas no interactivas al reducir sus prioridades. Todos los cálculos para determinar la interactividad de las tareas son complejos y están sujetos a posibles errores de cálculo, [ cita requerida ] lo que provoca un comportamiento no interactivo de un proceso interactivo.
En la versión 2.6.23 (octubre de 2007) se introdujo el Completely Fair Scheduler , que sustituyó al Scheduler O(1). Según Ingo Molnar, el autor del CFS, su diseño básico se puede resumir en una sola frase: "Básicamente, el CFS modela una 'CPU multitarea ideal y precisa' en hardware real". [7]
