Existe cierto número de heurísticos para analizar la planificabilidad de un sistema.

Inicialmente asumiremos que $C_i \leq T_i$, y tiempos de cambios de contexto despreciables. En este caso el tiempo de respuesta es el tiempo de cómputo más el tiempo de bloqueo por esperar la liberación de secciones críticas, más el tiempo de interferencia.

$R_i = C_i + B_i + I_i$

El tiempo de interferencia es el número de veces que pueda activarse cada tarea más prioritaria por el tiempo de cómputo de dicha tarea.

$I_i = \sum_{j\in hp(i)}\left\lceil\frac{R_i}{T_j}\right\rceil\cdot C_j$

El tiempo de bloqueo depende del número de secciones críticas y del algoritmo de ajuste dinámico de la prioridad en los mutex. En FreeRTOS solo se implementa el algoritmo de herencia de prioridad (OPCP), por lo que solo trataremos ese caso.

El algoritmo de herencia de prioridad consiste en que cuando una tarea adquiere un mutex ésta va a heredar la prioridad de la tarea de mayor prioridad que está esperando a que se libere este mutex en cada momento. Es decir, cuando una tarea más prioritaria entra en una región crítica, la tarea que tiene el recurso hereda la prioridad de esta nueva tarea más prioritaria. Para ilustrarlo utilizaremos el ejemplo de las transparencias de Juan Antonio de la Puente. Cuatro tareas ($\tau_1$ a $\tau_4$) se caracterizan por una secuencia de acciones con tiempos de cómputo máximos, algunas de ellas acceden a dos recursos compartidos (X e Y). Las características de periodicidad no son relevantes para este ejemplo, pero analizamos un caso particular en el que las activaciones se producen en unos instantes de activación determinados ($t_a$).

Es interesante comparar la planificación de este caso con y sin algoritmo de herencia de prioridad. El siguiente ejemplo ilustra el problema de la inversión de prioridad. La tarea $\tau_1$ es la más prioritaria pero se ve bloqueada por la tarea $\tau_4$ que tiene el recurso $X$ y las tareas $\tau_2$ y $\tau_3$ progresan a pesar de que no son las más prioritarias. En este caso el bloqueo total, en general, no está acotado. Eso es indeseable para un sistema de tiempo real estricto.

Sin algoritmo de herencia de prioridadCon algoritmo de herencia de prioridadCon algoritmo de techo de prioridad inmediato

Ilustración del fenómeno de inversión de prioridad para el caso de mutex sin algoritmo de herencia de prioridad.

Con el algoritmo de herencia de prioridad la tarea $\tau_1$ se bloquea algo menos. El algoritmo ayuda a mitigar la inversión de prioridad pero, por contra, el tiempo de respuesta de las tareas $\tau_2$ y $\tau_3$ se incrementa. Como la tarea $\tau_2$ comparte también recursos con la tarea $\tau_1$ ese alargamiento contribuye también al bloqueo de $\tau_1$.

Vamos a analizar el bloqueo máximo que se produce al usar este mecanismo. Para ello, ten en cuenta que:

• Una tarea (ver por ejemplo $\tau_3$) que no accede a ningún recurso compartido también puede sufrir bloqueo.
• Solo pueden producir bloqueos las regiones críticas de recursos que tienen techo de prioridad igual o superior a la tarea que se bloquea.
• Una tarea puede sufrir más de un bloqueo, pero solamente una vez por recurso y una vez por tarea de menor prioridad.

Para ver esto último solo hay que pensar en el momento que se produce el bloqueo. El bloqueo ocurre cuando la tarea que consideramos o una de prioridad superior intenta acceder al recurso. En ese momento la tarea que tiene el recurso, de baja prioridad, hereda temporalmente la prioridad de la tarea que intenta acceder al recurso, para que acabe cuanto antes. Este bloqueo se termina en el momento en que suelta el recurso y, en ese caso, la tarea de baja prioridad no podrá acceder a un nuevo recurso compartido hasta que terminen las más prioritarias. Lo mismo ocurre cuando varias tareas luchan por un mismo recurso. Solo la tarea más prioritaria recibirá la CPU en el momento en que la menos prioritaria lo libere, no importa cuantas otras tareas quieran el recurso mientras esto ocurre.

Veamos los techos de prioridad de los recursos para ver qué regiones críticas podrían bloquear:

| |4|4

Por tanto, cada tarea podría bloquear una vez por cada recurso y una vez por cada tarea de menor prioridad como máximo. Por tanto el bloqueo máximo es:

$B_i = \sum_{j \in lp(i), k}C_{j,k}$

donde $C_{j,k}$ es el tiempo requerido por la tarea $j$ para acceder al recurso $k$ (0 si no lo accede).

Una solución todavía mejor es el algoritmo de techo de prioridad inmediato, en el que la tarea que adquiere el recurso compartido hereda la prioridad de la tarea más prioritaria de cuantas van a acceder a ese recurso. Desafortunadamente, FreeRTOS no implementa esta posibilidad, aunque es relativamente sencillo implementarla por nosotros mismos. En este curso utilizaremos un esquema simplificado protegiendo el acceso a los recursos con una inhabilitación temporal del planificador, como veremos en el tema sobre recursos compartidos.

En este caso la tarea $\tau_1$ tiene el mínimo bloqueo posible, lo necesario para que $\tau_4$, que había obtenido el recurso X, termine de utilizarlo. Las tareas $\tau_2$ y $\tau_3$ no progresan hasta que la más prioritaria haya terminado. Es decir, cada tarea solo puede tener un bloqueo por ciclo, por lo que:

$B_i = \max_{j \in lp(i), k}C_{j,k}$