La Feria Programador completamente ( SFC ) es un planificador de procesos que se fusionó con la liberación 2.6.23 (octubre de 2007) del Linux kernel y es el programador predeterminado de las tareas de la SCHED_NORMAL
clase (es decir, tareas que no tienen ninguna ejecución en tiempo real limitaciones). Maneja la asignación de recursos de la CPU para ejecutar procesos y tiene como objetivo maximizar la utilización general de la CPU al mismo tiempo que maximiza el rendimiento interactivo.
Autor (es) original (es) | Ingo Molnár |
---|---|
Desarrollador (es) | Desarrolladores del kernel de Linux |
Escrito en | C |
Sistema operativo | Kernel de Linux |
Tipo | planificador de procesos |
Licencia | GPL-2.0 |
Sitio web | kernel |
A diferencia del programador O (1) anterior utilizado en los kernels de Linux 2.6 más antiguos, que mantenían y cambiaban las colas de ejecución de tareas activas y caducadas, la implementación del programador CFS se basa en colas de ejecución por CPU, cuyos nodos son entidades programables ordenadas por tiempo. que se mantienen ordenados por árboles rojo-negros . El CFS elimina la antigua noción de intervalos de tiempo fijos por prioridades y, en cambio, tiene como objetivo dar una parte justa del tiempo de CPU a las tareas (o, mejor, a las entidades programables). [1] [2]
Algoritmo
Una tarea (es decir, un sinónimo de hilo) es la entidad mínima que Linux puede programar. Sin embargo, también puede administrar grupos de subprocesos, procesos completos de múltiples subprocesos e incluso todos los procesos de un usuario determinado. Este diseño conduce al concepto de entidades programables, donde las tareas son agrupadas y administradas por el programador en su conjunto. Para que este diseño funcione, cada task_struct
descriptor de tarea incrusta un campo de tipo sched_entity
que representa el conjunto de entidades al que pertenece la tarea.
Cada tipo de cola de ejecución por CPU cfs_rq
ordena las sched_entity
estructuras de una manera ordenada en el tiempo en un árbol rojo-negro (o 'rbtree' en la jerga de Linux), donde el nodo más a la izquierda está ocupado por la entidad que ha recibido la menor porción de ejecución. tiempo (que se guarda en el vruntime
campo de la entidad). Los nodos están indexados por el " tiempo de ejecución " del procesador en nanosegundos. [3]
También se calcula un " tiempo máximo de ejecución " para cada proceso para representar el tiempo que el proceso habría esperado ejecutarse en un "procesador ideal". Este es el tiempo que el proceso ha estado esperando para ejecutarse, dividido por el número total de procesos.
Cuando se invoca el planificador para ejecutar un nuevo proceso:
- Se elige el nodo más a la izquierda del árbol de programación (ya que tendrá el menor tiempo de ejecución gastado ) y se envía para su ejecución.
- Si el proceso simplemente completa la ejecución, se elimina del sistema y del árbol de programación.
- Si el proceso alcanza su tiempo máximo de ejecución o se detiene (voluntariamente o por interrupción), se reinserta en el árbol de programación en función del tiempo de ejecución que acaba de utilizar .
- El nuevo nodo situado más a la izquierda se seleccionará del árbol, repitiendo la iteración.
Si el proceso pasa mucho tiempo durmiendo, entonces su valor de tiempo invertido es bajo y automáticamente obtiene el impulso de prioridad cuando finalmente lo necesita. Por lo tanto, estas tareas no obtienen menos tiempo de procesador que las tareas que se ejecutan constantemente.
La complejidad del algoritmo que inserta nodos en la cfs_rq
cola de ejecución del programador CFS es O ( log N), donde N es el número total de entidades. La elección de la siguiente entidad a ejecutar se realiza en tiempo constante porque el nodo más a la izquierda siempre se almacena en caché.
Historia
El trabajo de Con Kolivas con la programación, más significativamente su implementación de la " programación justa " llamada Fecha límite de escalera giratoria , inspiró a Ingo Molnár a desarrollar su CFS, como reemplazo del programador O (1) anterior , acreditando a Kolivas en su anuncio. [4] CFS es una implementación de un algoritmo de programación clásico bien estudiado llamado colas equitativas ponderadas . [5] Originalmente inventado para redes de paquetes , la cola justa se había aplicado previamente a la programación de CPU con el nombre de programación de pasos . CFS es la primera implementación de un programador de procesos de cola justa ampliamente utilizado en un sistema operativo de propósito general. [5]
El kernel de Linux recibió un parche para CFS en noviembre de 2010 para el kernel 2.6.38 que ha hecho que el programador sea más "justo" para su uso en computadoras de escritorio y estaciones de trabajo. Desarrollado por Mike Galbraith usando ideas sugeridas por Linus Torvalds , el parche implementa una característica llamada autogrouping que aumenta significativamente el rendimiento del escritorio interactivo. [6] El algoritmo coloca los procesos principales en el mismo grupo de tareas que los procesos secundarios. [7] (Los grupos de tareas están vinculados a sesiones creadas a través de la setsid()
llamada al sistema. [8] ) Esto resolvió el problema de los tiempos de respuesta interactivos lentos en sistemas de múltiples núcleos y múltiples CPU ( SMP ) cuando estaban realizando otras tareas que utilizan muchos Subprocesos de uso intensivo de CPU en esas tareas. Una explicación simple es que, con este parche aplicado, uno puede seguir viendo un video, leer un correo electrónico y realizar otras actividades típicas de escritorio sin fallas o problemas mientras, por ejemplo, se compila el kernel de Linux o se codifica el video.
En 2016, el programador de Linux fue parcheado para un mejor rendimiento multinúcleo, según las sugerencias descritas en el documento "El programador de Linux: una década de núcleos desperdiciados". [9]
Ver también
Referencias
- ^ Amor, Robert (2010). Desarrollo del kernel de Linux (3ª ed.). Estados Unidos de América: Addison Wesley. págs.41--61. ISBN 9780672329463.
- ^ "Linux: el programador completamente justo | KernelTrap" . web.archive.org . 2007-04-19 . Consultado el 16 de mayo de 2021 .
- ^ Descripción de CFS en ibm.com
- ^ Molnár, Ingo (13 de abril de 2007). "[parche] Núcleo del programador modular y programador completamente justo [CFS]" . linux-kernel (lista de correo).
- ^ a b Iluminado.; Baumberger, D .; Hahn, S. (2009). "Programación justa de multiprocesador eficiente y escalable utilizando round robin ponderado distribuido" (PDF) . Avisos ACM SIGPLAN . 44 (4): 65. CiteSeerX 10.1.1.567.2170 . doi : 10.1145 / 1594835.1504188 .
- ^ El parche de kernel de Linux de ~ 200 líneas que hace maravillas
- ^ Galbraith, Mike (15 de noviembre de 2010). "[RFC / RFT PATCH v3] Re: [RFC / RFT PATCH v3] programado: grupos de tareas automáticos por tty [CFS]" . linux-kernel (lista de correo).
- ^ Galbraith, Mike (20 de noviembre de 2010). "[PATCH v4] programado: grupos de tareas automatizados por sesión" . linux-kernel (lista de correo).
- ^ Lozi, Jean-Pierre; Leprosos, Baptiste; Funston, Justin; Gaud, Fabien; Quema, Vivian; Fedorova, Alexandra. "El programador de Linux: una década de núcleos desperdiciados" (PDF) . EuroSys 2016 . Consultado el 15 de junio de 2019 .
enlaces externos
- Corbet, Jonathan (17 de abril de 2007). "Programadores: la trama se complica" . LWN.net . Archivado desde el original el 6 de septiembre de 2017 . Consultado el 21 de julio de 2016 .
- Corbet, J. (2 de julio de 2007). "Programación del Grupo CFS" . LWN.net. Archivado desde el original el 6 de septiembre de 2017 . Consultado el 21 de julio de 2016 .
- Corbet, J. (16 de octubre de 2007). "Programación justa de usuarios y otros parches del programador" . LWN.net. Archivado desde el original el 12 de junio de 2017 . Consultado el 24 de noviembre de 2016 .
- Corbet, J. (17 de noviembre de 2010). "Programación grupal basada en TTY" . LWN.net. Archivado desde el original el 21 de mayo de 2018 . Consultado el 24 de noviembre de 2016 .
- Corbet, J. (6 de diciembre de 2010). "Programación grupal y alternativas" . LWN.net. Archivado desde el original el 11 de junio de 2017 . Consultado el 24 de noviembre de 2016 .
- Singh Pabla, Chandandeep (1 de agosto de 2009). "Programador completamente justo" . linuxjournal.com . Archivado desde el original el 18 de marzo de 2018 . Consultado el 17 de noviembre de 2014 .
- Jones, Tim (15 de diciembre de 2009). "Dentro del programador completamente justo de Linux 2.6" . ibm .
- Lozi, Jean-Pierre (21 de abril de 2016). "El programador de Linux: una década de núcleos desperdiciados" (PDF) . ACM . Archivado desde el original (PDF) el 5 de febrero de 2018 . Consultado el 24 de noviembre de 2016 .