Un programador O (1) (pronunciado "O de 1 programador", "O grande de 1 programador" o "programador de tiempo constante") es un diseño de programación de kernel que puede programar procesos dentro de una cantidad constante de tiempo, independientemente de cuántos los procesos se ejecutan en el sistema operativo . Esta es una mejora con respecto a los programadores O (n) utilizados anteriormente , que programan procesos en una cantidad de tiempo que escala linealmente en función de la cantidad 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 2.6.0 a 2.6.22 de Linux (2003-2007), momento en el que fue reemplazado por Completely Fair Scheduler .
Descripción general
El programador de Linux se revisó completamente con el lanzamiento del kernel 2.6 en 2003. [1] [2] El nuevo programador se llamó programador O (1). El algoritmo utilizado por el programador O (1) se basa en matrices de procesos activos y vencidos para lograr un tiempo de programación constante. A cada proceso se le asigna un cuanto de tiempo fijo, después del cual se reemplaza y se traslada a la matriz caducada. Una vez que todas las tareas de la matriz activa han agotado su cuanto de tiempo y se han movido a la matriz caducada, se produce un cambio de matriz. Debido a que se accede a las matrices solo a través de un puntero, cambiarlas es tan rápido como intercambiar dos punteros. [3] Este conmutador convierte a la matriz activa en la nueva matriz caducada vacía, mientras que la matriz caducada se convierte en la matriz activa.
Acerca de la notación O (1)
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 usa para denotar 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 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 en 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]
Mejora en el rendimiento del programador de Linux
El programador de Linux 2.6.8.1 no contiene ningún algoritmo que se ejecute en un tiempo peor que O (1). [6] Es decir, se garantiza que cada parte del programador se ejecutará dentro de una cierta cantidad de tiempo constante, independientemente de cuántas tareas haya en el sistema. Esto permite que el kernel de Linux maneje de manera eficiente una gran cantidad de tareas sin aumentar los costos generales a medida que aumenta la cantidad de tareas. Hay dos estructuras de datos clave en el programador 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.
Asuntos
El principal problema de este algoritmo son las complejas heurísticas que se utilizan para marcar una tarea como interactiva o no interactiva. El algoritmo intenta identificar procesos interactivos analizando el tiempo promedio de sueño (la cantidad de tiempo que el proceso pasa esperando una entrada). Los procesos que duermen durante largos períodos de tiempo probablemente estén esperando la entrada del usuario, por lo que el programador asume que son interactivos. El programador otorga una prima de prioridad a las tareas interactivas (para un mejor rendimiento) al tiempo que 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 ] causando un comportamiento no interactivo de un proceso interactivo.
Reemplazo
En 2.6.23 (octubre de 2007), se introdujo el Programador Completamente Justo , en sustitución del Programador O (1). Según Ingo Molnar, autor del CFS, su diseño central se puede resumir en una sola frase: "CFS básicamente modela una 'CPU ideal y precisa para múltiples tareas' en hardware real". [7]
Ver también
- Complejidad del tiempo
- Brain Fuck Scheduler (BFS): un programador de procesos diseñado para el kernel de Linux en agosto de 2009 como alternativa a CFS y al programador O (1).
Referencias
- ^ "Presentación del kernel 2.6 | Linux Journal" . www.linuxjournal.com . Consultado el 19 de julio de 2019 .
- ^ Chandandeep Singh Pabla (1 de agosto de 2009). "Programador completamente justo" . diario de Linux . Consultado el 9 de septiembre de 2014 .
- ^ Robert Love. "El programador de procesos de Linux" . Consultado el 9 de septiembre de 2014 .
- ^ dws. "Una introducción informal a la notación O (N)" . Consultado el 9 de septiembre de 2014 .
- ^ Rob Bell. "Una guía para principiantes de la notación Big O" . Consultado el 9 de septiembre de 2014 .
- ^ Josh Aas. "Comprensión del programador de CPU de Linux 2.6.8.1" (PDF) . Consultado el 9 de septiembre de 2014 .
- ^
, Ingo Molnar. @elte.hu>"Archivo del kernel de Linux: Re: uso justo del reloj en CFS" . lkml.iu.edu . Consultado el 30 de agosto de 2018 .
enlaces externos
- Comprensión del programador de CPU de Linux 2.6.8.1 ; Josh Aas, 17 de febrero de 2005
- HybridThreads (Hthreads) ; Un sistema operativo compatible con POSIX co-diseñado por HW / SW con un programador O (1) implementado en hardware
- Dentro del planificador de Linux ; Escrito por M. Tim Jones, un artículo de IBM developerWorks
- David Mosberger. "Una mirada más cercana al planificador de Linux O (1)" . Laboratorios de investigación de HP. Archivado desde el original el 16 de marzo de 2012.