Programación de tasa monótona

La asignación de prioridad de tasa monótona es óptima bajo los supuestos dados, lo que significa que si cualquier algoritmo de planificación de prioridad estática puede cumplir con todos los plazos, entonces el algoritmo de tasa monótona también puede. El algoritmo de planificación de plazo monótono también es óptimo con períodos y plazos iguales; de hecho, en este caso los algoritmos son idénticos. Además, la planificación de plazo monótona 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 planificabilidad exacta para este modelo, encuentra una asignación de prioridad óptima. ^{[ 4 ]}

Liu y Layland (1973) demostraron que, para un conjunto de n tareas periódicas con periodos únicos, existe una programación factible que siempre cumplirá con los plazos si la utilización de la CPU está por debajo de un límite específico (que depende del número de tareas). La prueba de programabilidad 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 a infinito , esta expresión tenderá a:

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

Por lo tanto, una estimación aproximada cuando${\displaystyle {n}\geq {10}}$RMS puede cumplir con todos los plazos si la utilización total de la CPU, U , es inferior al 70 %. El 30 % restante de la CPU puede dedicarse a tareas de menor prioridad que no requieren procesamiento en tiempo real. Para valores menores de n o en casos donde U se aproxime a esta estimación, se debe utilizar el límite de utilización calculado.

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

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 por ρ _i , es entonces:

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

como se indicó anteriormente.

Liu y Layland señalaron que este límite puede relajarse al valor máximo posible de 1.0, si para las tareas${\displaystyle {T_{m}}}$,${\displaystyle {T_{i}}}$dónde${\displaystyle {T_{m}}{>}{T_{i}}}$y${\displaystyle i=1...m-1}$,${\displaystyle {T_{m}}}$es un múltiplo entero de${\displaystyle {T_{i}}}$, lo que significa que todas las tareas tienen un período que no es simplemente un múltiplo del período más corto,${\displaystyle {T_{1}}}$, 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ónicas . Un ejemplo de esto sería: ${\displaystyle [{T_{1}},{T_{2}},{T_{3}},{T_{4}}]=[1,3,6,12]}$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 temporal para tareas con plazos flexibles o el uso de un enfoque de asignación de prioridades dinámicas, para permitir un límite superior.

Kuo y Mok ^{[ 5 ]} demostraron que para un conjunto de tareas compuesto por K subconjuntos de tareas armónicas (conocidos como cadenas armónicas ), la prueba del 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 cualquier otra tarea que tenga un período más corto, el conjunto de tareas puede considerarse compuesto por n subconjuntos de tareas armónicas de tamaño 1 y, por lo tanto,${\displaystyle {K}{=}{n}}$, lo que hace que esta generalización sea equivalente a la cota superior mínima de Liu y Layland. Cuando${\displaystyle {K}{=}{1}}$, el límite superior se convierte en 1,0, lo que representa la utilización total.

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 las tareas (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ás bajo presentado por Liu y Layland.

La cota hiperbólica ^{[ 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 ajustado que se puede encontrar utilizando únicamente los factores de utilización de cada tarea individual.

• Las OS_ENTER_CRITICAL()primitivas 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 interrupciones de dispositivos ( FreeBSD 5.x/6.x ),

• 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 lo solicita en el momento de la solicitud. Al liberarse el recurso, se restablece el nivel de prioridad original anterior a la promoción. Este método no evita los interbloqueos y sufre de bloqueo encadenado . Es decir, si una tarea de alta prioridad accede a varios recursos compartidos en secuencia, puede tener que esperar (bloquearse) a 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 la Wayback Machine para el kernel de Linux incluye una implementación de esta fórmula. ^{[ 10 ]}

• El protocolo de prioridad máxima ^{[ 11 ]} mejora el protocolo básico de herencia de prioridad asignando una prioridad máxima a cada semáforo, que corresponde a la prioridad del trabajo de mayor prioridad que accederá a dicho semáforo. Un trabajo no puede interrumpir una sección crítica de menor prioridad si su prioridad es inferior a la prioridad máxima de esa sección. Este método evita interbloqueos y limita el tiempo de bloqueo a, como máximo, la duración de una sección crítica de menor prioridad. Este método puede ser subóptimo, ya que puede provocar bloqueos innecesarios. El protocolo de prioridad máxima está disponible en el núcleo en tiempo real de VxWorks . También se conoce como Protocolo de Prioridad del Bloqueador de Mayor Prioridad (HLP). ^{[ 12 ]}

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

En la práctica, no existe ninguna 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 que utilizan la mayoría de los sistemas prácticos.

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 Marte cambiando las banderas de creación del semáforo para habilitar la herencia de prioridad.

Un método para mitigar una ISR mal priorizada es ajustar el análisis reduciendo el período de la ISR para que sea igual al del período más corto, si es posible. Imponer 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 la 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 planificabilidad. Como ejemplo, considere una ISR de hardware que tiene un tiempo de computación,${\displaystyle {C_{isr}}}$de 500 microsegundos y un período,${\displaystyle {T_{isr}}}$, de 4 milisegundos. Si la tarea controlada por el planificador más corta tiene un período,${\displaystyle {T_{1}}}$de 1 milisegundo, entonces la ISR tendría una prioridad más alta, pero una tasa más baja, lo que viola RMS. Para los fines de probar la planificabilidad, establezca${\displaystyle {T_{isr}}={T_{1}}}$y recalcular el factor de utilización para el ISR (lo que también aumenta el factor de utilización total). En este caso,${\displaystyle {U_{isr}}{=}{C_{isr}}/{T_{isr}}}$cambiará de${\displaystyle {0.5ms}/{4ms}{=}0.125}$a${\displaystyle {0.5ms}/{1ms}{=}0.5}$Este factor de utilización se usaría al sumar el factor de utilización total del conjunto de tareas y compararlo con el límite superior para demostrar la planificabilidad. Cabe destacar que el ajuste del período del ISR es solo para fines de análisis y que el período real del ISR permanece sin cambios.

Otro método para mitigar una rutina de servicio de interrupción (ISR) con prioridad incorrecta consiste en usarla únicamente para establecer un nuevo semáforo/mutex, mientras se traslada el procesamiento que consume mucho tiempo a un nuevo proceso con la prioridad adecuada mediante RMS, que se bloqueará en el nuevo semáforo/mutex. Al determinar la planificabilidad, se debe restar un margen de utilización de CPU debido a la actividad de la ISR del límite superior mínimo. Las ISR con una utilización insignificante pueden ignorarse.

En el marco del 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, seguida de P1 y, finalmente, P3.

En el marco del 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, seguida de P3 y, finalmente, P1.

En el marco del 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, seguida de P3 y, finalmente, P1.