En informática , la programación de velocidad monótona ( 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 tiempos de respuesta. El análisis monótono de tarifas se utiliza junto con esos sistemas para proporcionar garantías de programación para una aplicación en particular.
Introducción
Una versión simple del análisis de velocidad monótona asume que los subprocesos tienen las siguientes propiedades:
- Sin uso compartido de recursos (los procesos no comparten recursos, por ejemplo , un recurso de hardware , una cola o cualquier tipo de bloqueo o no bloqueo de semáforos ( ocupado-espera ))
- 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 se adelanta inmediatamente a todas las demás tareas)
- Prioridades estáticas asignadas de acuerdo con las convenciones monótonas de tarifas (las tareas con períodos / plazos más cortos reciben prioridades más altas)
- Los tiempos de cambio de contexto y otras operaciones de subprocesos son gratuitos y no tienen ningún impacto en el modelo
Es un modelo matemático que contiene una simulación calculada de períodos en un sistema cerrado, donde los programadores rotativos y de tiempo compartido no satisfacen las necesidades de programación de otra manera. La programación monótona de tarifas 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 de velocidad monótona 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 de velocidad monótona también puede hacerlo. El algoritmo de programación de plazos monótonos 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 monótona de los plazos es óptima cuando los plazos son inferiores a los períodos. [3] Para el modelo de tareas 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:
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 la fecha límite un período después) para el proceso i , y n es el número de procesos que se programarán. Por ejemplo, U ≤ 0,8284 para dos procesos. Cuando el número de procesos tiende al infinito , esta expresión tenderá a:
Por lo tanto, una estimación aproximada cuando es que RMS puede cumplir con todos los plazos si la utilización total de la CPU, U , es inferior al 70%. El otro 30% de la CPU se puede dedicar a tareas de menor prioridad que no son en tiempo real. Para valores más pequeños de n o en los casos en que U se acerque a esta estimación, se debe utilizar el límite de utilización calculado.
En la práctica, para el proceso, debe representar el peor de los casos (es decir, el tiempo de cálculo más largo) y debe representar la fecha límite en el peor de los casos (es decir, el período más corto) en el que debe ocurrir todo el procesamiento.
Límite superior para conjuntos de tareas armónicos
Liu y Layland señalaron que este límite se puede relajar al valor máximo posible de 1.0, si se trata de tareas , dónde 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ónicas . 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 fechas límite de tiempo flexible o el uso de un enfoque de asignación de prioridad dinámica para permitir para un límite superior.
Generalización a cadenas armónicas
Kuo y Mok [5] demostraron que para un conjunto de tareas compuesto por subconjuntos de tareas armónicas K (conocidas como cadenas armónicas ), la prueba de límite superior mínimo se convierte en:
En el caso en que ningún período de tarea sea un múltiplo entero de otro, se puede pensar que el conjunto de tareas está compuesto por n subconjuntos de tareas armónicos 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. Cuándo, el límite superior se convierte en 1.0, lo que representa una utilización completa.
Límites estocásticos
Se ha demostrado que un sistema de tareas periódicas generado 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, fechas límite) que no se pueden garantizar para todas las tareas. conjuntos, y en algunos casos los autores encontraron que la utilización alcanzó el límite superior mínimo presentado por Liu y Layland.
Enlace hiperbólico
El límite hiperbólico [7] es una condición suficientemente más estricta para la programabilidad que la presentada por Liu y Layland:
- ,
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.
El 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 punto muerto . En la práctica, esto se resuelve deshabilitando la preferencia o por herencia prioritaria . Los métodos alternativos son utilizar algoritmos sin bloqueo o evitar compartir un mutex / semáforo entre subprocesos con diferentes prioridades. Esto es para que los conflictos de recursos no puedan resultar en primer lugar.
Inhabilitación de la preferencia
- Las primitivas
OS_ENTER_CRITICAL()
yOS_EXIT_CRITICAL()
que bloquean las interrupciones de la CPU en un kernel en tiempo real, por ejemplo, MicroC / OS-II - La
splx()
familia de primitivas que anidan el bloqueo de interrupciones del dispositivo (FreeBSD 5.x / 6.x),
Herencia prioritaria
- El protocolo de herencia de prioridad básica [8] promueve la prioridad de la tarea que mantiene el recurso frente a la prioridad de la tarea que solicita ese recurso en el momento en que se realiza la solicitud. Tras la liberación del recurso, se restaura el nivel de prioridad original antes de la promoción. Este método no evita los interbloqueos y sufre un bloqueo encadenado . Es decir, si una tarea de alta prioridad accede a múltiples recursos compartidos en secuencia, es posible que tenga que esperar (bloquear) en una tarea de menor prioridad para cada uno de los recursos. [9] El parche en tiempo real para el kernel de Linux incluye una implementación de esta fórmula. [10]
- El protocolo de techo de prioridad [11] mejora el protocolo de herencia de prioridad básica asignando una prioridad de techo a cada semáforo, que es la prioridad del trabajo más alto que jamás accederá a ese semáforo. Un trabajo no puede adelantarse a 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 los interbloqueos y limita el tiempo de bloqueo como máximo a la longitud de una sección crítica de menor prioridad. Este método puede ser subóptimo, ya que puede causar un bloqueo innecesario. El protocolo de techo de prioridad está disponible en el kernel en tiempo real de VxWorks . También se conoce como Protocolo de prioridad del casillero más alto (HLP). [12]
Los algoritmos de herencia de prioridad se pueden caracterizar por dos parámetros. Primero, la herencia es perezosa (solo cuando es esencial) o inmediata (aumenta la prioridad antes de que haya un conflicto). En segundo lugar está la herencia optimista (aumentar una cantidad mínima) o pesimista (aumentar en más de la cantidad mínima):
pesimista | optimista | |
---|---|---|
inmediato | OS_ENTER_CRITICAL() / OS_EXIT_CRITICAL() | splx() , casillero más alto |
perezoso | protocolo de techo de prioridad, protocolo de herencia de prioridad básica |
En la práctica, no hay diferencia matemática (en términos del límite de utilización del sistema 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. [ 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 corrigió en Marte cambiando las banderas de creación del semáforo para habilitar la herencia de prioridad.
Interrumpir las rutinas de servicio
Todas las rutinas de servicios de interrupción (ISR), ya sea que tengan una fecha límite estricta en tiempo real o no, deben incluirse en el análisis de RMS para determinar la capacidad de programación en los casos en que los ISR tienen prioridades por encima de todas las tareas controladas por el programador. Es posible que un ISR ya tenga la prioridad adecuada según las reglas de RMS si su período de procesamiento es más corto que el del proceso más corto que no es ISR. Sin embargo, un ISR con un período / fecha límite más largo que cualquier período de proceso que no sea 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 capacidad de programación de un conjunto de tareas.
Mitigar 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 probar 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 más corta controlada por el programador 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 el RMS. Con el fin de demostrar la capacidad de programación, establezcay recalcular el factor de utilización para el ISR (que también eleva el factor de utilización total). En este caso, cambiará de a . Este factor de utilización se usaría al sumar el factor de utilización total para el conjunto de tareas y compararlo con el límite superior para demostrar la capacidad de programación. Se debe enfatizar que el ajuste del período del ISR es solo para análisis y que el período real del ISR permanece sin cambios.
Otro método para mitigar un ISR mal priorizado es usar el ISR para establecer solo un nuevo semáforo / mutex mientras se mueve el procesamiento que requiere mucho tiempo a un nuevo proceso que se ha priorizado apropiadamente usando RMS y se bloqueará en el nuevo semáforo / mutex. Al determinar la capacidad de programación, se debe restar un margen de utilización de la CPU debido a la actividad de ISR del límite superior mínimo. Es posible que se ignoren los ISR con una utilización insignificante.
Ejemplos de
Ejemplo 1
Proceso | Tiempo de ejecución | Período |
---|---|---|
P1 | 1 | 8 |
P2 | 2 | 5 |
P3 | 2 | 10 |
Bajo RMS, P2 tiene la tasa más alta (es decir, el período más corto) y, por lo tanto, tendría la prioridad más alta, seguida de P1 y finalmente P3.
Límite superior mínimo
La utilización será: .
La condición suficiente para procesos, bajo los cuales podemos concluir que el sistema es programable es:
Porque , y debido a que estar por debajo del límite mínimo superior es una condición suficiente, se garantiza que el sistema es programable.
Ejemplo 2
Proceso | Tiempo de ejecución | Período |
---|---|---|
P1 | 3 | dieciséis |
P2 | 2 | 5 |
P3 | 2 | 10 |
Bajo RMS, P2 tiene la tasa más alta (es decir, el período más corto) y, por lo tanto, tendría la prioridad más alta, seguida de P3 y finalmente P1.
Límite superior mínimo
Usando el límite de Liu y Layland, como en el Ejemplo 1, la condición suficiente para procesos, bajo los cuales podemos concluir que el conjunto de tareas es programable, permanece:
La utilización total será: .
Desde Se determina que no se garantiza que el sistema sea programable por parte de Liu y Layland.
Atado hiperbólico
Usando el límite hiperbólico más estricto de la siguiente manera:
se encuentra que el conjunto de tareas es programable.
Ejemplo 3
Proceso | Tiempo de ejecución | Período |
---|---|---|
P1 | 7 | 32 |
P2 | 2 | 5 |
P3 | 2 | 10 |
Bajo RMS, P2 tiene la tasa más alta (es decir, el período más corto) y, por lo tanto, tendría la prioridad más alta, seguida de P3 y finalmente P1.
Límite superior mínimo
Usando el límite de Liu y Layland, como en el Ejemplo 1, la condición suficiente para procesos, bajo los cuales podemos concluir que el conjunto de tareas es programable, permanece:
La utilización total será: .
Desde Se determina que no se garantiza que el sistema sea programable por parte de Liu y Layland.
Atado hiperbólico
Usando el límite hiperbólico más estricto de la siguiente manera:
Desde se determina que no se garantiza que el sistema sea programable por el enlace hiperbólico.
Análisis armónico de conjuntos de tareas
Porque , 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, el número de subconjuntos de tareas armónicas, K , es 2 .
Desde se determina que el sistema es programable.
Ver también
- Programación monótona con fecha límite
- Deos , un sistema operativo en tiempo real con particiones de tiempo y espacio que contiene un programador Rate Monotonic en funcionamiento.
- Programación de prioridad dinámica
- Fecha límite más temprana primera programación
- RTEMS , un sistema operativo de código abierto en tiempo real que contiene un programador monotónico de velocidad en funcionamiento.
- Programación (informática)
Referencias
- ^ Liu, CL ; Layland, J. (1973), "Programación de algoritmos 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.
- ^ Bovet, Daniel P .; Cesati, Marco, Comprensión del kernel de Linux, http://oreilly.com/catalog/linuxkernel/chapter/ch10.html#85347 Archivado el 21 de septiembre de 2014 en Wayback Machine .
- ^ Leung, JY; Whitehead, J. (1982), "Sobre la complejidad de la programación con 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.
- ^ Alan Burns y Andy Wellings (2009), Lenguajes de programación y sistemas en tiempo real (4a ed.), Addison-Wesley, págs. 391, 397, ISBN 978-0-321-41745-9
- ^ T.-W. Kuo, AK Mok (1991), "Ajuste de carga en sistemas adaptativos en tiempo real", Proc. Simposio de sistemas en tiempo real : 160-170, doi : 10.1109 / REAL.1991.160369Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ Lehoczky, J .; Sha, L .; Ding, Y. (1989), "El algoritmo de programación monótono de velocidad: caracterización exacta y comportamiento promedio de casos", Simposio de sistemas en tiempo real de IEEE , págs. 166-171, doi : 10.1109 / REAL.1989.63567 , ISBN 978-0-8186-2004-1.
- ^ Enrico Bini, Giorgio C. Buttazzo y Giuseppe M. Buttazzo (2003), "Rate Monotonic Analysis: the Hyperbolic Bound", IEEE Transactions on Computers , 52 (7): 933–942, doi : 10.1109 / TC.2003.1214341 , hdl : 11382/200358Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ Lampson, BW ; Redell, DD (1980), "Experiencia con procesos y monitores en Mesa", Comunicaciones del ACM , 23 (2): 105-117, CiteSeerX 10.1.1.46.7240 , doi : 10.1145 / 358818.358824.
- ^ Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Tercera ed.), Nueva York, NY: Springer, p. 225
- ^ "Wiki de Linux en tiempo real" . kernel.org. 2008-03-26 . Consultado el 14 de marzo de 2014 .
- ^ Sha, L .; Rajkumar, R .; Lehoczky, JP (1990), "Protocolos de herencia prioritarios: un enfoque para la sincronización en tiempo real", IEEE Transactions on Computers , 39 (9): 1175-1185, doi : 10.1109 / 12.57058.
- ^ Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Tercera ed.), Nueva York, NY: Springer, p. 212
- ^ http://research.microsoft.com/~mbj/Mars_Pathfinder/
- ^ http://anthology.spacemonkeys.ca/archives/770-Mars-Pathfinder-Reset-Bug.html
Otras lecturas
- Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications , Nueva York, NY: Springer.
- Alan Burns y Andy Wellings (2009), Lenguajes de programación y sistemas en tiempo real (4a ed.), Addison-Wesley, ISBN 978-0-321-41745-9
- Liu, Jane WS (2000), Sistemas en tiempo real , Upper Saddle River, Nueva Jersey: Prentice Hall, Capítulo 6.
- Joseph, M .; Pandya, P. (1986), "Finding response times in real-time systems", BCS Computer Journal , 29 (5): 390–395, doi : 10.1093 / comjnl / 29.5.390.
- Sha, Lui; Goodenough, John B. (abril de 1990), "Real-Time Scheduling Theory and Ada", IEEE Computer , 23 (4): 53–62, doi : 10.1109 / 2.55469
enlaces externos
- Error de Mars Pathfinder de Research @ Microsoft
- Lo que realmente sucedió en el Mars Rover Pathfinder por Mike Jones de The Risks Digest, Vol. 19, número 49
- [1] La razón real del error Mars Pathfinder, pero aquellos que realmente se ocuparon de él, en lugar de alguien cuya empresa y, por lo tanto, el valor de las acciones dependía de la descripción del problema, o alguien que escuchó a alguien hablar sobre el problema.