FECHA LÍMITE PROGRAMADA

SCHED_DEADLINEes un planificador de CPU disponible en el núcleo Linux desde la versión 3.14, ^{[1] [2]} basado en los algoritmos early deadline first (EDF) y constant widthwide server (CBS) ^{[3] , que admite reservas de recursos: cada tarea programada bajo dicha política está asociada con un} presupuesto Q (también conocido como tiempo de ejecución ), y un período P, correspondiente a una declaración al núcleo de que esa tarea requiere Q unidades de tiempo cada P unidades de tiempo, en cualquier procesador. Esto lo hace SCHED_DEADLINEparticularmente adecuado para aplicaciones en tiempo real , como multimedia o control industrial, donde P corresponde al tiempo mínimo transcurrido entre activaciones posteriores de la tarea, y Q corresponde al tiempo de ejecución en el peor de los casos necesario para cada activación de la tarea.

El núcleo de Linux contiene diferentes clases de planificador. ^[4] De forma predeterminada, el núcleo utiliza un mecanismo de planificador llamado Completely Fair Scheduler (CFS) introducido en la versión 2.6.23 del núcleo. ^[5] Internamente, esta clase de planificador predeterminada también se conoce como , y el núcleo también contiene dos clases de planificación en tiempo real SCHED_NORMALcompatibles con POSIX ^[6]SCHED_FIFO llamadas (realtime first-in-first-out ) y SCHED_RR(realtime round-robin ) ambas tienen prioridad sobre la clase predeterminada. ^[4] La SCHED_DEADLINEclase de planificación se agregó al planificador de Linux en la versión 3.14 de la línea principal del núcleo de Linux , lanzada el 30 de marzo de 2014, ^{[7] [8]} y tiene prioridad sobre todas las demás clases de planificación.

El planificador predeterminado, CFS, hace un muy buen trabajo al lidiar con diferentes casos de uso. Por ejemplo, al mezclar cargas de trabajo por lotes, como compilaciones de código de larga ejecución o procesamiento numérico, 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 una programación predecible y precisa, normalmente tiene que recurrir a uno de los otros planificadores en tiempo real, SCHED_RR o SCHED_FIFO, que aplican una prioridad fija para programar tareas por prioridades, y cuyas tareas se programan antes que cualquier tarea en la clase SCHED_NORMAL.

Al mezclar cargas de trabajo en tiempo real con requisitos de tiempo heterogéneos en el mismo sistema, un problema bien conocido SCHED_RRes SCHED_FIFOque, como se basan en las prioridades de las tareas, las tareas de mayor prioridad que se ejecutan durante más tiempo del esperado pueden retrasar arbitrariamente las tareas de menor prioridad de forma descontrolada.

En cambio, con SCHED_DEADLINE, las tareas declaran de forma independiente sus requisitos de tiempo, en términos de un tiempo de ejecución por tarea necesario en cada período por tarea (y que vence dentro de una fecha límite por tarea desde el inicio de cada período), y el núcleo las acepta en el planificador después de una prueba de capacidad de planificación. Ahora, si una tarea intenta ejecutarse durante más tiempo que su presupuesto asignado, el núcleo suspenderá esa tarea y aplazará 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 importante propiedad de que, en sistemas de un solo procesador o en sistemas multiprocesador particionados (donde las tareas se dividen entre las CPU disponibles, por lo que cada tarea está fijada en una CPU específica y no puede migrar), SCHED_DEADLINEse garantiza que todas las tareas aceptadas se programen 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 incluso en presencia de tareas que bloquean y reanudan su ejecución: esto se hace restableciendo la fecha límite de programación de una tarea a un período completo de diferencia, siempre que una tarea se activa demasiado tarde. En el caso general de tareas libres para migrar en un multiprocesador, como SCHED_DEADLINEimplementa EDF global, se aplica el límite de tardanza general para EDF global, como se explica en ^{[9] .}

Para entender mejor cómo funciona el programador, considere un conjunto de SCHED_DEADLINEtareas con períodos potencialmente diferentes, teniendo la fecha límite igual al período. Para cada tarea, además del tiempo de ejecución configurado y el período (relativo), el núcleo 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 fechas límite 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 ejecutarse en cualquier CPU, el núcleo la deja ejecutarse como máximo durante el presupuesto actual disponible, y siempre que se desprograma la tarea, su presupuesto actual se reduce por la cantidad de tiempo que se ha ejecutado. Una vez que el presupuesto actual llega a cero, la tarea se suspende (se limita) 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 por 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, con una fecha límite actual que está muy cerca de expirar, 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 con fecha límite tanto como su presupuesto. Para evitar este problema, SCHED_DEADLINEadopta la regla de programación de activación definida en el algoritmo CBS. Cuando una tarea se despierta, si ha transcurrido un tiempo relativamente pequeño desde que se bloqueó la tarea, entonces la fecha límite actual anterior y el presupuesto se mantienen sin cambios para la tarea. Sin embargo, si ha transcurrido una cantidad excesiva de tiempo, entonces el núcleo restablece la fecha límite actual a la hora actual más el período de reserva, y el presupuesto actual al presupuesto de reserva asignado. Para una explicación más larga con ejemplos, consulte. ^[9]

En un sistema multiprocesador o multinúcleo, SCHED_DEADLINEimplementa 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, particionando 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á fijada a una partición de CPU específica.

Para obtener detalles técnicos sobre SCHED_DEADLINE, consulte la documentación disponible dentro del árbol de código fuente del núcleo. ^[9] Para obtener más detalles sobre el CBS y cómo permite el aislamiento temporal, consulte el documento original de CBS, ^[3] o la sección sobre el CBS en este artículo ^[10] aparecido en lwn.net.

La idea inicial de una clase de planificación Linux basada en el algoritmo Earliest Deadline First (EDF) nació en el pequeño contexto del Laboratorio de Sistemas de Tiempo Real (ReTiS) de la Scuola Superiore Sant'Anna ^[11] y su empresa derivada Evidence Srl. ^[12] Luego, Evidence Srl aprovechó 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 (contratado por 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 de escalado de frecuencia (es decir, GRUB-PA ^[17] ).

El parche se ha publicado periódicamente en la comunidad del kernel a través de la lista de correo del kernel de Linux (LKML). Cada versión alineaba el código con la última versión del kernel y tenía en cuenta los comentarios recibidos en el envío anterior. A medida que la popularidad del programador aumentaba, un mayor número de desarrolladores del kernel comenzaron a proporcionar sus comentarios y contribuciones.

El proyecto fue originalmente llamado SCHED_EDFy presentado a la comunidad del kernel de Linux en 2009. ^[18] Con este nombre también fue presentado al Real-Time Linux Workshop después de algunas semanas. ^[19] El nombre ha sido cambiado 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 publicado las siguientes versiones:

• La primera versión del planificador se presentó el 22 de septiembre de 2009, con el nombre de SCHED_EDF. ^[18]
• La primera versión del programador después del cambio de nombre SCHED_DEADLINEfue enviada a LKML el 16 de octubre de 2009. ^[21]
• La segunda versión del programador se envió a LKML el 28 de febrero de 2010 y tenía 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 programador 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 programador se envió a LKML el 23 de mayo de 2012. ^[25]
• La sexta versión del programador se envió a LKML el 24 de octubre de 2012. ^[26]
• La séptima versión del programador se envió a LKML el 11 de febrero de 2013. ^[27] Las matemáticas internas se restringieron a una resolución de microsegundos (para evitar desbordamientos) y se eliminó la etiqueta RFC.
• La octava versión del programador se envió a LKML el 14 de octubre de 2013. ^[28]
• La novena versión del programador se envió a LKML el 7 de noviembre de 2013. ^[29]
• La última versión se fusionó con el núcleo principal de Linux (número de confirmación a0fa1dd3cdbccec9597fe53b6177a9aa6e20f2f8 ^[30] ), y desde entonces es una parte regular del mismo.

En artículos publicados en los sitios web Linux Weekly News ^[31] y Phoronix ^[32] se afirma que SCHED_DEADLINEes posible que se integre en el núcleo principal en las próximas versiones. Finalmente, después de más de cuatro años y de la presentación de nueve versiones, el parche ha sido aceptado y se ha integrado en el núcleo 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 núcleo Linux, en el contexto de otros proyectos de investigación europeos, incluidos OCERA, ^[33] la arquitectura AQuoSA dentro del proyecto FRESCOR, ^[34] e IRMOS. ^[35] Sin embargo, estos esfuerzos previos 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 núcleo 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 ha evolucionado aún más para reducir el consumo de energía en 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]

SCHED_DEADLINESe 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 , 11º 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, núm. 3, págs. 72–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 de multiprocesador en Linux , 15.º Taller sobre Linux en tiempo real (RTLWS), Lugano-Manno, Suiza, octubre de 2013. ^[44]
• Luca Abeni, Juri Lelli, Claudio Scordino, Luigi Paolopoli, Recuperación de CPU voraz para SCHED_DEADLINE , Actas del 16.º Taller sobre 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: práctica y experiencia, 46(6): 821–839, junio de 2016. ^[46]
• Claudio Scordino, Luca Abeni, Juri Lelli, Programación en tiempo real consciente de la energía en el núcleo de Linux , 33.° Simposio ACM/SIGAPP sobre informática 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 de 2012, ^{[51] [52]} y en la Embedded Linux Conference de 2013. ^[53]

El proyecto tiene una página oficial. ^[54] Antes de la integración 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 principal, el código oficial está incluido 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 su integración en el núcleo principal, SCHED_DEADLINEya estaba integrado en el Proyecto Yocto . ^[28] y también había habido cierto interés para su inclusión en proyectos Linaro . ^[62]

• Fecha límite virtual elegible más temprana para la programación (EEVDF)