SCHED_DEADLINE
es un programador de CPU disponible en el kernel de Linux desde la versión 3.14, [1] [2] basado en los algoritmos Earliest Deadline First (EDF) y Constant Bandwidth Server (CBS) [3] , que admite reservas de recursos: cada tarea programada según dicha política está asociado con un presupuesto Q (también conocido como tiempo de ejecución ), y un período P, correspondiente a una declaración al kernel de que esa tarea requiere Q unidades de tiempo cada P unidades de tiempo, en cualquier procesador. Esto lo hace SCHED_DEADLINE
particularmente adecuado para tiempo real. aplicaciones, como multimedia o control industrial, donde P corresponde al tiempo mínimo que transcurre entre activaciones posteriores de la tarea, y Q corresponde al peor tiempo de ejecución necesario para cada activación de la tarea.
Información general sobre los programadores de CPU en el kernel de Linux
El kernel de Linux contiene diferentes clases de programadores. [4] Por defecto, el kernel usa un mecanismo de programación llamado Completely Fair Scheduler (CFS) introducido en la versión 2.6.23 del kernel. [5] Internamente, esta clase de programador predeterminada también se conoce como SCHED_NORMAL
, pero el kernel también contiene dos clases de programación en tiempo real compatibles con POSIX [6] denominadas SCHED_FIFO
(en tiempo real primero en entrar, primero en salir ) y SCHED_RR
(en tiempo real round-robin ) ambas de los cuales tienen prioridad sobre la clase predeterminada. [4] La SCHED_DEADLINE
clase de programación se agregó al programador de Linux en la versión 3.14 de la línea principal del kernel de Linux , lanzada el 30 de marzo de 2014, [7] [8] y tiene prioridad sobre todas las demás clases de programación.
El programador predeterminado, CFS, hace un muy buen trabajo al hacer frente a diferentes casos de uso. Por ejemplo, al mezclar cargas de trabajo por lotes, como compilaciones de código de larga duración o procesamiento de números, y aplicaciones interactivas como aplicaciones de escritorio, multimedia u otras, el CFS desprioriza dinámicamente las tareas por lotes en favor de las interactivas. Sin embargo, cuando una aplicación necesita un horario predecible y preciso, normalmente tiene que recurrir a uno de los otros programadores en tiempo real, SCHED_RR o SCHED_FIFO, que aplican prioridad fija para programar tareas por prioridades, y cuyas tareas se programan antes que cualquier tarea. en la clase SCHED_NORMAL.
Operación
Cuando se mezclan cargas de trabajo en tiempo real con requisitos de tiempo heterogéneos en el mismo sistema, un problema bien conocido de SCHED_RR
y SCHED_FIFO
es que, dado que se basan en las prioridades de las tareas, las tareas de mayor prioridad que se ejecutan durante más tiempo de lo esperado pueden retrasar arbitrariamente las tareas de menor prioridad en de una manera incontrolada.
Con SCHED_DEADLINE
, en cambio, las tareas declaran de forma independiente sus requisitos de tiempo, en términos de un per-tarea en tiempo de ejecución necesario cada per-tarea periodo (y por dentro de un per-tarea plazo ya que cada inicio de periodo), y el núcleo que lo acepta en el programador después de una prueba de programabilidad. Ahora, si una tarea intenta ejecutarse por más tiempo que su presupuesto asignado, el kernel suspenderá esa tarea y pospondrá su ejecución hasta su próximo período de activación. Esta propiedad del planificador que no conserva el trabajo le permite proporcionar aislamiento temporal entre las tareas. Esto da como resultado la propiedad importante de que, en sistemas de un solo procesador o en sistemas multiprocesador con particiones (donde las tareas se dividen entre las CPU disponibles, por lo que cada tarea está definida en una CPU específica y no se puede migrar), todas las SCHED_DEADLINE
tareas aceptadas están garantizadas. para ser programados para un tiempo total igual a su presupuesto en cada ventana de tiempo mientras dure su período, a menos que la tarea en sí se bloquee y no necesite ejecutarse. Además, una propiedad peculiar del algoritmo CBS es que garantiza el aislamiento temporal también en presencia de tareas que bloquean y reanudan la ejecución: esto se hace restableciendo una fecha límite de programación de tareas a un período completo de diferencia, siempre que una tarea se despierte demasiado tarde. En el caso general de las tareas que pueden migrar libremente en un multiprocesador, como SCHED_DEADLINE
implementa el EDF global, se aplica la tardanza general con destino al EDF global, como se explica en. [9]
Para comprender mejor cómo funciona el programador, considere un conjunto de SCHED_DEADLINE
tareas con períodos potencialmente diferentes, pero con una fecha límite igual al período. Para cada tarea, además del tiempo de ejecución configurado y el período (relativo), el kernel realiza un seguimiento de un tiempo de ejecución actual y una fecha límite actual (absoluta) . Las tareas se programan en las CPU en función de sus plazos actuales, utilizando EDF global. Cuando una política de programación de tareas se establece inicialmente en SCHED_DEADLINE
, la fecha límite actual se inicializa a la hora actual más el período configurado, y el presupuesto actual se establece igual al presupuesto configurado. Cada vez que se programa una tarea para que se ejecute en cualquier CPU, el kernel permite que se ejecute como máximo con el presupuesto actual disponible, y siempre que la tarea se desprograma, su presupuesto actual se reduce según la cantidad de tiempo que se ha ejecutado. Una vez que el presupuesto actual llega a cero, la tarea se suspende (regula) hasta el siguiente período de activación, cuando el presupuesto actual se vuelve a llenar al valor configurado y la fecha límite se adelanta en un valor igual al período de la tarea.
Esto no es suficiente para garantizar el aislamiento temporal . Una tarea que se suspende poco después de su activación, y luego se despierta cerca de su fecha límite actual o incluso más allá, se despertaría con casi la totalidad de su presupuesto configurado, pero con una fecha límite actual que está muy cerca de vencer, o incluso en el pasado. En tal condición, esa tarea se programaría antes que cualquier otra, y en un sistema de un solo procesador podría retrasar la ejecución de cualquier otra tarea de fecha límite por el tiempo que su presupuesto. Para evitar este problema, SCHED_DEADLINE
adopta la regla de programación de despertadores definida en el algoritmo CBS. Cuando una tarea se activa, si ha transcurrido un tiempo relativamente pequeño desde que se bloqueó la tarea, la fecha límite y el presupuesto actuales anteriores se mantienen sin cambios para la tarea. Sin embargo, si ha transcurrido una cantidad excesiva de tiempo, el núcleo restablece la fecha límite actual al tiempo actual más el período de reserva, y el presupuesto actual al presupuesto de reserva asignado. Para obtener una explicación más extensa con ejemplos, consulte. [9]
En un sistema multiprocesador o multinúcleo, SCHED_DEADLINE
implementa EDF global, por lo que las tareas pueden migrar entre las CPU disponibles. En tal caso, el presupuesto configurado es la cantidad total acumulada de tiempo que se permite que la tarea se ejecute en cualquier CPU durante cada período. Sin embargo, el programador también respeta las máscaras de afinidad de las tareas , por lo que se pueden crear fácilmente escenarios de programación particionados, particionar tareas en grupos donde cada grupo está restringido a una CPU específica, o escenarios de programación agrupados, obtenidos al particionar también las CPU y cada partición de tareas está anclada. hasta una partición de CPU específica.
Para obtener detalles técnicos sobre SCHED_DEADLINE
, consulte la documentación disponible en el árbol de fuentes del kernel. [9] Para más detalles sobre CBS y cómo permite el aislamiento temporal, consulte el documento original de CBS, [3] o la sección sobre CBS en este artículo [10] que apareció en lwn.net.
Historia
La idea inicial de una clase de programación de Linux basada en el algoritmo Earliest Deadline First (EDF) nació en el pequeño contexto del Laboratorio de sistemas en tiempo real (ReTiS) de Scuola Superiore Sant'Anna [11] y su empresa derivada Evidence Srl. [12] Luego, Evidence Srl apalancó la financiación del proyecto ACTORS, [13] [14] apoyado por la Comisión Europea a través del programa marco FP7, para financiar y promover el desarrollo de las primeras versiones del parche. La versión original ha sido desarrollada por Dario Faggioli (contrato de Evidence Srl para el desarrollo de las tres primeras versiones) y Juri Lelli (desde la cuarta versión) [15] con la ayuda esporádica de Michael Trimarchi y Fabio Checconi. Johan Eker ha estado a cargo de la coordinación dentro de ACTORS y del apoyo de Ericsson. Juri Lelli, Luca Abeni y Claudio Scordino han colaborado en el desarrollo de las funciones de recuperación (es decir, GRUB [16] ) y escalado de frecuencia (es decir, GRUB-PA [17] ).
El parche se ha lanzado periódicamente a la comunidad del kernel a través de la lista de correo del kernel de Linux (LKML). Cada lanzamiento alineó el código con la última versión del kernel y tuvo en cuenta los comentarios recibidos en el envío anterior. A medida que aumentó la popularidad del programador, un mayor número de desarrolladores de kernel comenzaron a proporcionar sus comentarios y su contribución.
El proyecto fue originalmente llamado SCHED_EDF
y presentado a la comunidad del kernel de Linux en 2009. [18] Con este nombre también se presentó al Real-Time Linux Workshop después de unas semanas. [19] El nombre se cambió a SCHED_DEADLINE después de la solicitud de la comunidad del kernel de Linux. [20]
A lo largo de los años, se han lanzado las siguientes versiones:
- La primera versión del planificador se envió el 22 de septiembre de 2009 con el nombre de
SCHED_EDF
. [18] - La primera versión del planificador después del cambio de nombre
SCHED_DEADLINE
se envió a LKML el 16 de octubre de 2009. [21] - La segunda versión del planificador se envió a LKML el 28 de febrero de 2010 y tuvo una primera implementación del protocolo de herencia de fecha límite. [22]
- La tercera versión del programador se envió a LKML el 29 de octubre de 2010 y agregó soporte para la programación multiprocesador global / agrupada a través de migraciones de tareas dinámicas. [23]
- La cuarta versión del planificador se envió a LKML el 6 de abril de 2012 y tiene un mejor manejo de la selección de rq para la migración dinámica de tareas y una mejor integración con PREEMPT_RT . [24]
- La quinta versión del planificador se envió a LKML el 23 de mayo de 2012. [25]
- La sexta versión del planificador se envió a LKML el 24 de octubre de 2012. [26]
- La séptima versión del planificador se envió a LKML el 11 de febrero de 2013. [27] Las matemáticas internas se han restringido a una resolución de microsegundos (para evitar desbordamientos) y se ha eliminado la etiqueta RFC.
- La octava versión del planificador se envió a LKML el 14 de octubre de 2013. [28]
- La novena versión del planificador se envió a LKML el 7 de noviembre de 2013. [29]
- La última versión se fusionó con el kernel principal de Linux (número de confirmación a0fa1dd3cdbccec9597fe53b6177a9aa6e20f2f8 [30] ), y desde entonces es una parte regular de él.
Los artículos en los sitios web de Linux Weekly News [31] y Phoronix [32] argumentaron que SCHED_DEADLINE
podría fusionarse con el núcleo principal en las próximas versiones. Finalmente, después de más de cuatro años y el envío de nueve versiones, el parche ha sido aceptado y combinado con el kernel de Linux 3.14. [7] [8]
Antes de SCHED_DEADLINE, el laboratorio de sistemas en tiempo real (ReTiS) [11] de la Scuola Superiore Sant'Anna había proporcionado varias otras implementaciones de código abierto de CBS y sus variantes dentro del kernel de Linux, en el contexto de otros proyectos de investigación europeos, incluido OCERA , [33] la arquitectura AQuoSA dentro del proyecto FRESCOR, [34] e IRMOS. [35] Sin embargo, estos esfuerzos anteriores comenzaron con un enfoque académico donde el objetivo principal era recopilar resultados experimentales para proyectos de investigación, en lugar de proporcionar una implementación adecuada para la integración dentro del núcleo principal. Con IRMOS, el laboratorio tuvo un primer contacto serio con los desarrolladores del kernel de Linux. [10]
Desde el kernel 4.13, SCHED_DEADLINE completó [36] CBS con el algoritmo Greedy Reclamation of Unused Bandwidth (GRUB). [37] El soporte ha sido desarrollado por ReTiS Lab con la colaboración de Evidence Srl.
Desde el kernel 4.16, SCHED_DEADLINE se ha desarrollado aún más para reducir el consumo de energía en las plataformas ARM mediante la implementación del algoritmo GRUB-PA. [17] El trabajo ha sido realizado por ARM Ltd. en colaboración con Evidence Srl y Scuola Superiore Sant'Anna. [38]
Antecedentes académicos
SCHED_DEADLINE
se ha presentado a través de algunos talleres académicos, conferencias y revistas:
- Dario Faggioli, Fabio Checconi, Michael Trimarchi, Claudio Scordino, una clase de programación EDF para el kernel de Linux , XI Taller de Linux en tiempo real (RTLWS), Dresde, Alemania, septiembre de 2009 [19] [39]
- Nicola Manica, Luca Abeni, Luigi Palopoli, Dario Faggioli, Claudio Scordino, Controladores de dispositivos programables: implementación y resultados experimentales , Taller internacional sobre plataformas de sistemas operativos para aplicaciones integradas en tiempo real (OSPERT), Bruselas, Bélgica, julio de 2010 [40] [ 41]
- Juri Lelli, Giuseppe Lipari, Dario Faggioli, Tommaso Cucinotta, Una implementación eficiente y escalable de EDF global en Linux , Taller internacional sobre plataformas de sistemas operativos para aplicaciones integradas en tiempo real (OSPERT), Oporto (Portugal), julio de 2011. [42] [43]
- Enrico Bini, Giorgio Buttazzo, Johan Eker, Stefan Schorr, Raphael Guerra, Gerhard Fohler, Karl-Erik Arzen, Vanessa Romero Segovia, Claudio Scordino, Gestión de recursos en sistemas multinúcleo: el enfoque ACTORS , IEEE Micro, vol. 31, no. 3, págs. 72 a 81, mayo / junio de 2011. [14]
- Andrea Parri, Juri Lelli, Mauro Marinoni, Giuseppe Lipari, Diseño e implementación del protocolo de herencia de ancho de banda multiprocesador en Linux , 15º Taller de Linux en tiempo real (RTLWS), Lugano-Manno, Suiza, octubre de 2013. [44]
- Luca Abeni, Juri Lelli, Claudio Scordino, Luigi Paolopoli, Greedy CPU reclamando para SCHED_DEADLINE , Actas del 16º Taller de Linux en tiempo real (RTLWS), Düsseldorf, Alemania, octubre de 2014. [45]
- Juri Lelli, Claudio Scordino, Luca Abeni, Dario Faggioli, Programación de fechas límite en el kernel de Linux , Software: Practice and Experience, 46 (6): 821-839, junio de 2016. [46]
- Claudio Scordino, Luca Abeni, Juri Lelli, Energy-Aware Real-Time Scheduling in the Linux Kernel , 33 ° Simposio ACM / SIGAPP sobre Computación Aplicada (SAC 2018), Pau, Francia, abril de 2018. [47]
- Claudio Scordino, Luca Abeni, Juri Lelli, Eficiencia energética y en tiempo real en Linux: teoría y práctica , ACM SIGAPP Applied Computing Review (ACR) Vol. 18 No. 4, 2018. [48]
El proyecto también se presentó en la Kernel Summit de 2010, [49] [50] en la Linux Plumbers Conference 2012, [51] [52] y en la Embedded Linux Conference 2013. [53]
Otra información
El proyecto tiene una página oficial. [54] Antes de la integración de la línea principal, el código solía estar disponible públicamente en un sitio web de GitHub, [55] que reemplazó al repositorio anterior en Gitorious. [56] Desde la integración de la línea principal, el código oficial se incluye en el árbol de fuentes del kernel de Linux.
Han aparecido varios artículos en Linux Weekly News , [1] [57] Slashdot , [58] OSNews [2] [59] y LinuxToday. [60] También se ha subido un vídeo a YouTube [61] .
Antes de la integración en el kernel de la línea principal, SCHED_DEADLINE
ya estaba integrado en el Proyecto Yocto . [28] y también ha habido cierto interés por su inclusión en los proyectos de Linaro . [62]
Referencias
- ^ a b [1] Noticias semanales de Linux, Programación de fechas límite para Linux
- ^ a b [2] OSNews, Programación de fechas límite en el kernel de Linux
- ^ a b [3] L. Abeni y G. Buttazzo, "Integración de aplicaciones multimedia en sistemas duros en tiempo real", Proc. del XIX Simposio de sistemas en tiempo real del IEEE, Madrid, 1998, págs.
- ^ a b Bar, Moshe. "El programador de Linux" . Diario de Linux . Consultado el 14 de abril de 2012 .
- ^ Molnár, Ingo (13 de abril de 2007). "[parche] Núcleo del programador modular y programador completamente justo [CFS]" . linux-kernel (lista de correo).
- ^ [4] Estándar IEEE para tecnología de la información: interfaz de sistema operativo portátil, POSIX.1b, extensiones en tiempo real (IEEE Std 1003.1b-1993)
- ^ a b "Kernel de Linux 3.14, Sección 1.1. Clase de programación de fecha límite para una mejor programación en tiempo real" . kernelnewbies.org . 2014-03-30 . Consultado el 2 de abril de 2014 .
- ^ a b [5] Phoronix, el kernel de Linux 3.14 ya tiene muchas características interesantes
- ^ a b c Programación de tareas de fecha límite
- ^ a b T. Cucinotta y F. Checconi, "El programador en tiempo real de IRMOS", sección "El CBS: Programación basada en EDF y aislamiento temporal"
- ^ a b [6] Laboratorio ReTiS, Scuola Superiore Sant'Anna, Pisa, Italia
- ^ [7] Evidence Srl, comunicado de prensa de SCHED_DEADLINE v6
- ^ [8] Proyecto ACTORS FP7
- ^ a b [9] Enrico Bini, Giorgio Buttazzo, Johan Eker, Stefan Schorr, Raphael Guerra, Gerhard Fohler, Karl-Erik Arzen, Vanessa Romero Segovia, Claudio Scordino, Gestión de recursos en sistemas multinúcleo: el enfoque ACTORS, IEEE Micro, vol. . 31, no. 3, págs.72-81, mayo / junio de 2011.
- ^ [10] Historia del proyecto SCHED_DEADLINE
- ^ "Recuperación de CPU para SCHED_DEADLINE [LWN.net]" . lwn.net . Consultado el 24 de octubre de 2018 .
- ^ a b "GRUB-PA" . git.kernel.org . Consultado el 24 de octubre de 2018 .
- ^ a b [11] Primera presentación de SCHED_DEADLINE (todavía se llama SCHED_EDF)
- ^ a b [12] Dario Faggioli, Fabio Checconi, Michael Trimarchi, Claudio Scordino, una clase de programación EDF para el kernel de Linux, XI Taller de Linux en tiempo real (RTLW), Dresde, Alemania, septiembre de 2009.
- ^ [13] Solicitud para cambiar el nombre de SCHED_EDF a SCHED_DEADLINE
- ^ [14] Primera versión de SCHED_DEADLINE
- ^ [15] Segunda versión de SCHED_DEADLINE
- ^ [16] Tercera versión de SCHED_DEADLINE
- ^ [17] Cuarta versión de SCHED_DEADLINE
- ^ [18] Quinta versión de SCHED_DEADLINE
- ^ [19] Sexta versión de SCHED_DEADLINE
- ^ [20] Séptima versión de SCHED_DEADLINE
- ^ a b [21] Octava versión de SCHED_DEADLINE
- ^ [22] Novena versión de SCHED_DEADLINE
- ^ [23] Confirme la fusión de SCHED_DEADLINE en el kernel de la línea principal
- ^ "Programación de fechas límite: ¿próximamente?" . lwn.net .
- ^ [24] Phoronix, SCHED_DEADLINE se agregará a Linux 3.14
- ^ [25] Proyecto de investigación europeo OCERA sobre CORDIS
- ^ [26] Proyecto de investigación europeo FRESCOR en CORDIS
- ^ [27] Proyecto de investigación europeo IRMOS en CORDIS
- ^ "kernel / git / torvalds / linux.git - árbol de fuentes del kernel de Linux" . git.kernel.org . Consultado el 5 de septiembre de 2017 .
- ^ [28] Algoritmo de recuperación codiciosa de ancho de banda no utilizado (GRUB)
- ^ "kernel / git / torvalds / linux.git - árbol de fuentes del kernel de Linux" . git.kernel.org . Consultado el 4 de enero de 2019 .
- ^ [29] Taller de Linux en tiempo real (RTLWS) 2009
- ^ [30] Nicola Manica, Luca Abeni, Luigi Palopoli, Dario Faggioli, Claudio Scordino, Controladores de dispositivos programables: implementación y resultados experimentales, Taller internacional sobre plataformas de sistemas operativos para aplicaciones integradas en tiempo real (OSPERT), Bruselas, Bélgica, julio de 2010
- ^ [31] Publicaciones internacionales ACTORS
- ^ [32] Juri Lelli, Giuseppe Lipari, Dario Faggioli, Tommaso Cucinotta, Una implementación eficiente y escalable de EDF global en Linux, Taller internacional sobre plataformas de sistemas operativos para aplicaciones integradas en tiempo real (OSPERT), Porto (Portugal), julio de 2011 .
- ^ [33] Taller internacional sobre plataformas de sistemas operativos para aplicaciones integradas en tiempo real (OSPERT), Oporto (Portugal), julio de 2011
- ^ [34] Taller de Linux en tiempo real (RTLWS) 2013
- ^ [35] Taller de Linux en tiempo real (RTLWS) 2014
- ^ Lelli, Juri (2015). "Programación de fechas límite en el kernel de Linux". Software: práctica y experiencia . 46 (6): 821–839. doi : 10.1002 / spe.2335 .
- ^ Scordino, Claudio; Abeni, Luca; Lelli, Juri (9 de abril de 2018). Programación en tiempo real consciente de la energía en el kernel de Linux . ACM. págs. 601–608. doi : 10.1145 / 3167132.3167198 . ISBN 9781450351911.
- ^ "Revisión de computación aplicada de ACM SIGAPP (ACR) Vol. 18 No. 4, 2018" (PDF) .
- ^ [36] SCHED_DEADLINE en Kernel Summit 2010 (KS2010)
- ^ [37] ReTiS Lab, SCHED_DEADLINE presentado en Kernel Summit 2010
- ^ [38] Conferencia de fontaneros de Linux 2012
- ^ [39] Proyecto SOOS, SCHED_DEADLINE en la Linux Plumbers Conference 2012
- ^ [40] Conferencia de Linux integrado, San Francisco, 2013. Detección de errores de fecha límite con SCHED_DEADLINE, Yoshitake Kobayashi, TOSHIBA Corporation
- ^ [41] Página web oficial del proyecto SCHED_DEADLINE
- ^ [42] Nuevo repositorio público de GitHub
- ^ "Copia archivada" . Archivado desde el original el 27 de diciembre de 2010 . Consultado el 11 de enero de 2011 .CS1 maint: copia archivada como título ( enlace ) Repositorio anterior de Gitorious
- ^ [43] Noticias semanales de Linux, agregando puntos a SCHED_DEADLINE
- ^ [44] Slashdot , programación de fechas límite propuesta para el kernel de Linux
- ^ [45] OSNews , nueva versión de SCHED_DEADLINE para Linux disponible
- ^ [46] LinuxToday, agregando puntos a SCHED_DEADLINE
- ^ [47] SCHED_DEADLINE video en YouTube
- ^ [48] SCHED_DEADLINE en Linaro