Rate monotonic scheduling

En ciencias de la computación, RMS (Rate Monotonic Scheduling)^[1]​ es un algoritmo de programación utilizado en los sistemas operativos de tiempo real con prioridad estática.^[2]​^[3]​ Las prioridades estáticas se asignan en función de la duración del período del trabajo. El trabajo más corto tiene la de mayor prioridad.

Estos sistemas operativos son apropiativos (con desalojo) y tienen garantías deterministas en cuanto a los tiempos de respuesta. RMS se utiliza en conjunción con esos sistemas para proporcionar garantías de tiempos de respuesta para una aplicación particular.

Descripción

La versión básica del algoritmo de planificación de tasa monotónica asume que los procesos/hilos tienen las siguientes propiedades:

• No comparten recursos, por ejemplo colas, semáforos, puertos, etc.
• Los plazos deterministas son exactamente igual a los períodos.
• Las prioridades son estáticas. La tarea de mayor prioridad estática que es ejecutable inmediatamente desaloja a todas las demás tareas.
• Las prioridades estáticas son asignadas de acuerdo a la convención de tasa monótona . La tarea con la menor relación período/plazo tiene la prioridad más alta.
• Los tiempos de cambio de contexto y otras operaciones del sistema operativo no tienen ningún impacto sobre el modelo.

Se trata de un modelo matemático que contiene una simulación calculada de períodos en un sistema cerrado, donde los planificadores round robin de tiempo compartido no cumplen con la programación de las necesidades. La planificación RMS realiza una modelización de ejecución de todos los procesos/hilos en el sistema y determina la cantidad de tiempo que se necesita para cumplir con las garantías para el conjunto de procesos/hilos que se trate.

Layland en 1973 demostró que para un conjunto de n tareas periódicas con períodos únicos, existe una planificación factible que siempre va a cumplir con los plazos si la utilización de la CPU está por debajo de un límite dependiente del número de tareas. La prueba de planificabilidad para RMS es:

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

donde Ci es el tiempo de computo, Ti es el período y n es el número de procesos/hilos.

Entonces

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

Con lo que encontramos un método fácil de calcular la planificabilidad.

Referencias

1. Liu, C. L. (1973). «Scheduling algorithms for multiprogramming in a hard real-time environment». Journal of the ACM (20): 46-61. doi:10.1145/321738.321743. 
2. Bovet, Daniel P. Understanding the Linux Kernel. 
3. oreilly.com