Programación monotónica de tasas

Técnica de programación en informática

En informática , la programación monotónica de velocidad ( RMS ) ^[1] es un algoritmo de asignación de prioridad utilizado en sistemas operativos en tiempo real (RTOS) con una clase de programación de prioridad estática. ^[2] Las prioridades estáticas se asignan de acuerdo con la duración del ciclo del trabajo, por lo que una duración de ciclo más corta da como resultado una prioridad de trabajo más alta.

Estos sistemas operativos son generalmente preventivos y tienen garantías deterministas en cuanto a los tiempos de respuesta. El análisis monotónico de velocidad se utiliza junto con estos sistemas para proporcionar garantías de programación para una aplicación en particular.

Introducción

Una versión simple del análisis de tasa monótona supone que los hilos tienen las siguientes propiedades:

• Sin intercambio de recursos (los procesos no comparten recursos, por ejemplo, un recurso de hardware , una cola o cualquier tipo de semáforo bloqueado o no bloqueado ( esperas ocupadas ))
• Los plazos deterministas son exactamente iguales a los períodos
• Prioridades estáticas (la tarea con la prioridad estática más alta que se puede ejecutar reemplaza inmediatamente a todas las demás tareas)
• Prioridades estáticas asignadas según las convenciones de tasa monótona (las tareas con períodos/plazos más cortos reciben prioridades más altas)
• Los tiempos de cambio de contexto y otras operaciones de subproceso son gratuitos y no tienen impacto en el modelo.

Es un modelo matemático que contiene una simulación calculada de períodos en un sistema cerrado, donde los planificadores de turnos rotativos y de tiempo compartido no logran satisfacer las necesidades de programación de otra manera. La programación monotónica de tasa analiza un modelo de ejecución de todos los subprocesos del sistema y determina cuánto tiempo se necesita para cumplir con las garantías para el conjunto de subprocesos en cuestión.

Optimalidad

La asignación de prioridad monotónica de tasa es óptima bajo los supuestos dados, lo que significa que si cualquier algoritmo de programación de prioridad estática puede cumplir con todos los plazos, entonces el algoritmo monotónico de tasa también puede hacerlo. El algoritmo de programación monotónica de plazos también es óptimo con períodos y plazos iguales, de hecho en este caso los algoritmos son idénticos; además, la programación monotónica de plazos es óptima cuando los plazos son menores que los períodos. ^[3] Para el modelo de tarea en el que los plazos pueden ser mayores que los períodos, el algoritmo de Audsley dotado de una prueba de programabilidad exacta para este modelo encuentra una asignación de prioridad óptima. ^[4]

Límites superiores de utilización

Límite superior mínimo

Liu y Layland (1973) demostraron que para un conjunto de n tareas periódicas con períodos únicos, existe un cronograma factible que siempre cumplirá con los plazos si la utilización de la CPU está por debajo de un límite específico (dependiendo del número de tareas). La prueba de capacidad de programación para RMS es:

${\displaystyle U=\sum _{i=1}^{n}{U_{i}}=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq n({2}^{1/n}-1)}$

donde U es el factor de utilización, C _i es el tiempo de cálculo para el proceso i , T _i es el período de liberación (con fecha límite un período después) para el proceso i , y n es el número de procesos a programar. Por ejemplo, U ≤ 0,8284 para dos procesos. Cuando el número de procesos tiende hacia el infinito , esta expresión tenderá hacia:

${\displaystyle \lim _{n\rightarrow \infty }n({\sqrt[{n}]{2}}-1)=\ln 2\approx 0.693147\ldots }$

Por lo tanto, una estimación aproximada de cuándo RMS puede cumplir con todos los plazos es si la utilización total de la CPU, U , es inferior al 70 %. El 30 % restante de la CPU se puede dedicar a tareas de menor prioridad y que no sean en tiempo real. Para valores más pequeños de n o en casos en los que U esté cerca de esta estimación, se debe utilizar el límite de utilización calculado. ${\displaystyle {n}\geq {10}}$

En la práctica, para el proceso, debería representar el tiempo de cálculo del peor caso (es decir, el más largo) y debería representar la fecha límite del peor caso (es decir, el período más corto) en el que debe ocurrir todo el procesamiento. ${\displaystyle {i^{th}}}$ ${\displaystyle {C_{i}}}$ ${\displaystyle {T_{i}}}$

Relación con la teoría de colas

En la teoría de colas , T _i se denomina tiempo entre llegadas y C _i se denomina tiempo de servicio . Estos dos parámetros se suelen especificar como tasas:

${\displaystyle \lambda _{i}={1 \over T_{i}}}$es la tasa de llegada , y

${\displaystyle \mu _{i}={1 \over C_{i}}}$es la tarifa del servicio .

La utilización para cada tarea, denotada ρ _i , es entonces:

${\displaystyle \rho _{i}={\lambda _{i} \over \mu _{i}}={C_{i} \over T_{i}}=U_{i}}$

Como arriba.

Límite superior para conjuntos de tareas armónicas

Liu y Layland observaron que este límite se puede relajar al valor máximo posible de 1,0, si para las tareas , donde y , es un múltiplo entero de , lo que quiere decir que todas las tareas tienen un período que no es solo un múltiplo del período más corto, , sino que el período de cualquier tarea es un múltiplo de todos los períodos más cortos. Esto se conoce como un conjunto de tareas armónico. Un ejemplo de esto sería: . Liu y Layland reconocen que no siempre es factible tener un conjunto de tareas armónico y que, en la práctica, se pueden utilizar otras medidas de mitigación, como el almacenamiento en búfer para tareas con plazos flexibles o el uso de un enfoque de asignación de prioridad dinámica para permitir un límite superior. ${\displaystyle {T_{m}}}$ ${\displaystyle {T_{i}}}$ ${\displaystyle {T_{m}}{>}{T_{i}}}$ ${\displaystyle i=1...m-1}$ ${\displaystyle {T_{m}}}$ ${\displaystyle {T_{i}}}$ ${\displaystyle {T_{1}}}$ ${\displaystyle [{T_{1}},{T_{2}},{T_{3}},{T_{4}}]=[1,3,6,12]}$

Generalización a cadenas armónicas

Kuo y Mok ^[5] demostraron que para un conjunto de tareas compuesto de K subconjuntos de tareas armónicas (conocidos como cadenas armónicas ), la prueba de límite superior mínimo se convierte en:

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq K({2}^{1/K}-1)}$

En el caso en que para cada tarea, su período es un múltiplo exacto de cada otra tarea que tiene un período más corto, el conjunto de tareas puede considerarse como compuesto de n subconjuntos de tareas armónicas de tamaño 1 y, por lo tanto , , lo que hace que esta generalización sea equivalente al límite superior mínimo de Liu y Layland. Cuando , el límite superior se convierte en 1,0, lo que representa la utilización completa. ${\displaystyle {K}{=}{n}}$ ${\displaystyle {K}{=}{1}}$

Límites estocásticos

Se ha demostrado que un sistema de tareas periódicas generadas aleatoriamente generalmente cumplirá con todos los plazos cuando la utilización sea del 88% o menos, ^[6] sin embargo, este hecho depende de conocer las estadísticas exactas de la tarea (períodos, plazos) que no se pueden garantizar para todos los conjuntos de tareas, y en algunos casos los autores encontraron que la utilización alcanzó el límite superior mínimo presentado por Liu y Layland.

Límite hiperbólico

El límite hiperbólico ^[7] es una condición suficiente más estricta para la programabilidad que la presentada por Liu y Layland:

${\displaystyle \prod _{i=1}^{n}(U_{i}+1)\leq 2}$,

donde U _i es la utilización de la CPU para cada tarea. Es el límite superior más estricto que se puede encontrar utilizando solo los factores de utilización de tareas individuales.

Intercambio de recursos

En muchas aplicaciones prácticas, los recursos se comparten y el RMS no modificado estará sujeto a riesgos de inversión de prioridad y bloqueo . En la práctica, esto se soluciona deshabilitando la preempción o mediante la herencia de prioridad . Los métodos alternativos son usar algoritmos sin bloqueo o evitar compartir un mutex/semáforo entre subprocesos con diferentes prioridades. Esto es para que no se produzcan conflictos de recursos en primer lugar.

Desactivación de la prelación

• Los primitivos OS_ENTER_CRITICAL()y OS_EXIT_CRITICAL()que bloquean las interrupciones de la CPU en un núcleo en tiempo real, por ejemplo, MicroC/OS-II
• La splx()familia de primitivas que anidan el bloqueo de las interrupciones del dispositivo (FreeBSD 5.x/6.x),

Herencia prioritaria

• El protocolo básico de herencia de prioridad ^[8] promueve la prioridad de la tarea que posee el recurso a la prioridad de la tarea que solicita ese recurso en el momento en que se realiza la solicitud. Al liberar el recurso, se restaura el nivel de prioridad original antes de la promoción. Este método no evita los bloqueos y sufre bloqueos encadenados . Es decir, si una tarea de alta prioridad accede a múltiples recursos compartidos en secuencia, puede tener que esperar (bloquearse) en una tarea de menor prioridad para cada uno de los recursos. ^[9] El parche en tiempo real Archivado el 13 de octubre de 2020 en Wayback Machine para el kernel de Linux incluye una implementación de esta fórmula. ^[10]

• El protocolo de techo de prioridad ^[11] mejora el protocolo básico de herencia de prioridad al asignar una prioridad máxima a cada semáforo, que es la prioridad del trabajo más alto que alguna vez accederá a ese semáforo. Un trabajo no puede preemptar una sección crítica de menor prioridad si su prioridad es menor que la prioridad máxima para esa sección. Este método evita bloqueos y limita el tiempo de bloqueo a, como máximo, la longitud de una sección crítica de menor prioridad. Este método puede ser subóptimo, ya que puede causar bloqueos innecesarios. El protocolo de techo de prioridad está disponible en el núcleo de tiempo real de VxWorks . También se lo conoce como Protocolo de prioridad de bloqueo más alta (HLP). ^[12]

Los algoritmos de herencia de prioridad se pueden caracterizar por dos parámetros. En primer lugar, si la herencia es perezosa (solo cuando es esencial) o inmediata (aumenta la prioridad antes de que haya un conflicto). En segundo lugar, si la herencia es optimista (aumenta una cantidad mínima) o pesimista (aumenta más que la cantidad mínima):

En la práctica, no existe diferencia matemática (en términos del límite de utilización del sistema de Liu-Layland) entre los algoritmos perezosos e inmediatos, y los algoritmos inmediatos son más eficientes de implementar, por lo que son los utilizados por la mayoría de los sistemas prácticos. ^{[ cita requerida ]}

Un ejemplo del uso de la herencia de prioridad básica está relacionado con el " error de reinicio de Mars Pathfinder " ^{[13] [14]} que se solucionó en Mars cambiando los indicadores de creación del semáforo para habilitar la herencia de prioridad.

Rutinas de servicio de interrupción

Todas las rutinas de servicio de interrupción (ISR), ya sea que tengan una fecha límite en tiempo real estricta o no, deben incluirse en el análisis RMS para determinar la posibilidad de programación en los casos en que las ISR tienen prioridades por encima de todas las tareas controladas por el programador. Es posible que una ISR ya tenga la prioridad adecuada según las reglas RMS si su período de procesamiento es más corto que el del proceso no ISR más corto. Sin embargo, una ISR con un período/fecha límite más largo que cualquier período de proceso no ISR con una fecha límite crítica da como resultado una violación de RMS e impide el uso de los límites calculados para determinar la posibilidad de programación de un conjunto de tareas.

Mitigación de los ISR mal priorizados

Un método para mitigar un ISR mal priorizado es ajustar el análisis reduciendo el período del ISR para que sea igual al del período más corto, si es posible. La imposición de este período más corto da como resultado una priorización que se ajusta a RMS, pero también da como resultado un factor de utilización más alto para el ISR y, por lo tanto, para el factor de utilización total, que aún puede estar por debajo del límite permitido y, por lo tanto, se puede demostrar la capacidad de programación. Como ejemplo, considere un ISR de hardware que tiene un tiempo de cálculo, de 500 microsegundos y un período, , de 4 milisegundos. Si la tarea controlada por el programador más corto tiene un período, de 1 milisegundo, entonces el ISR tendría una prioridad más alta, pero una tasa más baja, lo que viola RMS. A los efectos de demostrar la capacidad de programación, establezca y vuelva a calcular el factor de utilización para el ISR (que también aumenta el factor de utilización total). En este caso, cambiará de a . Este factor de utilización se utilizaría al sumar el factor de utilización total para el conjunto de tareas y compararlo con el límite superior para demostrar la posibilidad de programación. Se debe enfatizar que el ajuste del período del ISR es solo para fines de análisis y que el período real del ISR permanece inalterado. ${\displaystyle {C_{isr}}}$ ${\displaystyle {T_{isr}}}$ ${\displaystyle {T_{1}}}$ ${\displaystyle {T_{isr}}={T_{1}}}$ ${\displaystyle {U_{isr}}{=}{C_{isr}}/{T_{isr}}}$ ${\displaystyle {0.5ms}/{4ms}{=}0.125}$ ${\displaystyle {0.5ms}/{1ms}{=}0.5}$

Otro método para mitigar un ISR mal priorizado es utilizar el ISR solo para establecer un nuevo semáforo/mutex mientras se traslada el procesamiento que requiere mucho tiempo a un nuevo proceso que se haya priorizado adecuadamente utilizando RMS y que se bloqueará en el nuevo semáforo/mutex. Al determinar la capacidad de programación, se debe restar un margen de utilización de CPU debido a la actividad del ISR del límite superior mínimo. Los ISR con una utilización insignificante pueden ignorarse.

Ejemplos

Ejemplo 1

Según RMS, P2 tiene la tasa de liberación más alta (es decir, el período de liberación más corto) y, por lo tanto, tendría la máxima prioridad, seguido de P1 y finalmente P3.

Límite superior mínimo

La utilización será:

${\displaystyle U={\frac {1}{8}}+{\frac {2}{5}}+{\frac {2}{10}}=0.725}$.

La condición suficiente para los procesos, bajo la cual podemos concluir que el sistema es programable es: ${\displaystyle 3\,}$

${\displaystyle {U_{lub}}=3(2^{\frac {1}{3}}-1)=0.77976}$

Debido a que , y debido a que estar por debajo del límite mínimo superior es una condición suficiente, se garantiza que el sistema sea programable. ${\displaystyle U<U_{lub}}$

Ejemplo 2

Según RMS, P2 tiene la tasa de liberación más alta (es decir, el período de liberación más corto) y, por lo tanto, tendría la máxima prioridad, seguido de P3 y, finalmente, P1.

Límite superior mínimo

Utilizando el límite de Liu y Layland, como en el Ejemplo 1, la condición suficiente para los procesos, bajo la cual podemos concluir que el conjunto de tareas es programable, sigue siendo: ${\displaystyle 3\,}$

${\displaystyle {U_{lub}}=3(2^{\frac {1}{3}}-1)=0.77976}$

La utilización total será:

${\displaystyle U={\frac {3}{16}}+{\frac {2}{5}}+{\frac {2}{10}}=0.7875}$.

Desde entonces , no se garantiza que el sistema pueda programarse según el límite de Liu y Layland. ${\displaystyle U>U_{lub}}$

Límite hiperbólico

Utilizando el límite hiperbólico más estricto de la siguiente manera:

${\displaystyle \prod _{i=1}^{n}(U_{i}+1)=({\frac {3}{16}}+1)*({\frac {2}{5}}+1)*({\frac {2}{10}}+1)=1.995\leq 2}$

Se encontró que el conjunto de tareas es programable.

Ejemplo 3

Según RMS, P2 tiene la tasa más alta (es decir, el período más corto) y, por lo tanto, tendría la máxima prioridad, seguido de P3 y, finalmente, P1.

Límite superior mínimo

Utilizando el límite de Liu y Layland, como en el Ejemplo 1, la condición suficiente para los procesos, bajo la cual podemos concluir que el conjunto de tareas es programable, sigue siendo: ${\displaystyle 3\,}$

${\displaystyle {U_{lub}}=3(2^{\frac {1}{3}}-1)=0.77976}$

La utilización total será:

${\displaystyle U={\frac {7}{32}}+{\frac {2}{5}}+{\frac {2}{10}}=0.81875}$.

Desde entonces , no se garantiza que el sistema pueda programarse según el límite de Liu y Layland. ${\displaystyle U>U_{lub}}$

Límite hiperbólico

Utilizando el límite hiperbólico más estricto de la siguiente manera:

${\displaystyle \prod _{i=1}^{n}(U_{i}+1)=({\frac {7}{32}}+1)*({\frac {2}{5}}+1)*({\frac {2}{10}}+1)=2.0475}$

Dado que se determina que no se garantiza que el sistema sea programable según el límite hiperbólico. ${\displaystyle 2.0{<}2.0475}$

Análisis de conjuntos de tareas armónicas

Debido a que las tareas 2 y 3 pueden considerarse un subconjunto de tareas armónicas, la tarea 1 forma su propio subconjunto de tareas armónicas. Por lo tanto, la cantidad de subconjuntos de tareas armónicas, K , es 2 . ${\displaystyle {T_{3}}={2{T_{2}}}}$

$${\displaystyle {U_{lub,harmonic}}=K(2^{\frac {1}{K}}-1)=2(2^{\frac {1}{2}}-1)=0.828}$$

Utilizando el factor de utilización total calculado anteriormente (0,81875), ya que se determina que el sistema es programable. ${\displaystyle 0.81875<0.828}$

Véase también

• Programación monótona con plazos límite
• Deos , un sistema operativo en tiempo real particionado en el tiempo y el espacio que contiene un Programador Monótono de Tasa funcional.
• Programación de prioridades dinámicas
• Fecha límite más temprana, primera programación
• RTEMS , un sistema operativo en tiempo real de código abierto que contiene un Programador Monótono de Tasa en funcionamiento.
• Programación (informática)
• Teoría de colas
• La fórmula de Kingman

Referencias

1. Liu, CL ; Layland, J. (1973), "Algoritmos de planificación para multiprogramación en un entorno de tiempo real estricto", Journal of the ACM , 20 (1): 46–61, CiteSeerX  10.1.1.36.8216 , doi :10.1145/321738.321743, S2CID  207669821.
2. Bovet, Daniel P.; Cesati, Marco, Entendiendo el núcleo de Linux, http://oreilly.com/catalog/linuxkernel/chapter/ch10.html#85347 Archivado el 21 de septiembre de 2014 en Wayback Machine .
3. Leung, JY; Whitehead, J. (1982), "Sobre la complejidad de la programación de prioridad fija de tareas periódicas en tiempo real", Evaluación del desempeño , 2 (4): 237–250, doi :10.1016/0166-5316(82)90024-4.
4. Alan Burns y Andy Wellings (2009), Sistemas en tiempo real y lenguajes de programación (4.ª ed.), Addison-Wesley, págs. 391, 397, ISBN 978-0-321-41745-9
5. T.-W. Kuo; AK Mok (1991). "Ajuste de carga en sistemas adaptativos en tiempo real". [1991] Actas del Duodécimo Simposio de Sistemas en Tiempo Real . págs. 160–170. doi :10.1109/REAL.1991.160369. ISBN 0-8186-2450-7. Número de identificación del sujeto  31127772.
6. Lehoczky, J.; Sha, L.; Ding, Y. (1989), "El algoritmo de programación monótona de velocidad: caracterización exacta y comportamiento de caso promedio", Simposio de sistemas en tiempo real IEEE , págs. 166-171, doi :10.1109/REAL.1989.63567, ISBN 978-0-8186-2004-1, Identificador único  de 206524469.
7. Enrico Bini; Giorgio C. Buttazzo; Giuseppe M. Buttazzo (2003), "Análisis monótono de velocidad: el límite hiperbólico", IEEE Transactions on Computers , 52 (7): 933–942, doi :10.1109/TC.2003.1214341, hdl : 11382/200358
8. Lampson, BW ; Redell, DD (1980), "Experiencia con procesos y monitores en Mesa", Comunicaciones de la ACM , 23 (2): 105–117, CiteSeerX 10.1.1.46.7240 , doi :10.1145/358818.358824, S2CID  1594544 .
9. Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (tercera edición), Nueva York, NY: Springer, pág. 225
10. "Real-Time Linux Wiki". kernel.org. 2008-03-26 . Consultado el 2014-03-14 .
11. Sha, L.; Rajkumar, R.; Lehoczky, JP (1990), "Protocolos de herencia de prioridad: un enfoque para la sincronización en tiempo real", IEEE Transactions on Computers , 39 (9): 1175–1185, doi :10.1109/12.57058.
12. Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Sistemas informáticos en tiempo real: algoritmos y aplicaciones de programación predecible ) (tercera edición), Nueva York, NY: Springer, pág. 212
13. "Mike Jones en Microsoft Research".
14. "Error de reinicio de Mars Pathfinder - Antología de interés". Archivado desde el original el 5 de octubre de 2011. Consultado el 9 de septiembre de 2008 .

Lectura adicional

• Buttazzo, Giorgio (2011), Sistemas informáticos de tiempo real estricto: algoritmos y aplicaciones de programación predecibles , Nueva York, NY: Springer.
• Alan Burns y Andy Wellings (2009), Sistemas en tiempo real y lenguajes de programación (4.ª ed.), Addison-Wesley, ISBN 978-0-321-41745-9
• Liu, Jane WS (2000), Sistemas en tiempo real , Upper Saddle River, NJ: Prentice Hall, Capítulo 6.
• Joseph, M.; Pandya, P. (1986), "Detección de tiempos de respuesta en sistemas en tiempo real", BCS Computer Journal , 29 (5): 390–395, doi : 10.1093/comjnl/29.5.390.
• Sha, Lui; Goodenough, John B. (abril de 1990), "Teoría de programación en tiempo real y Ada", IEEE Computer , 23 (4): 53–62, doi :10.1109/2.55469, S2CID  12647942

Enlaces externos

• Error en Mars Pathfinder de Research @ Microsoft
• Lo que realmente ocurrió en el explorador marciano Pathfinder, por Mike Jones, de The Risks Digest, vol. 19, número 49
• [1] La verdadera razón del error de Mars Pathfinder, según quienes realmente lo solucionaron, en lugar de alguien cuya empresa y, por lo tanto, el valor de sus acciones dependían de la descripción del problema, o alguien que escuchó a alguien hablar sobre el problema.