1	2	3	4	5	6
Especificación	Modelado	Verificación	Implementación	Verificación	Análisis
PARA QUÉ	QUÉ		CÓMO
¿Cuál es el problema?	¿Qué tiene que hacer el sistema?	¿El modelo cumple la especificación?	¿Cómo hace lo que tiene que hacer? (modelo refinado)	¿La implementación cumple la especificación?	¿Se cumplen los plazos en el caso peor?
LTL, CTL	FSM / xFSM	nuXmv	fsm.h / fsm.c	nuXmv	Análisis del tiempo
		(model checking)	Ejecutivo cíclico / FreeRTOS / Reactor	(model checking)	de respuesta

Para empezar...
Leer [Barns&Wellings] capítulo 11. Gran parte de esta página es traducción directa de ese capítulo.

Transparencias
Lee las transparencias usadas en clase de Juan A. de la Puente, de ETSIT-UPM.

Aprende los detalles
Lee capítulo 3 de [Barry].

Un sistema de tiempo real no es un sistema más rápido. Tan solo se trata de un sistema que dispone de mecanismos para garantizar que se cumplen los plazos asignados a las distintas tareas. Cuando estos plazos están completamente garantizados en todos los casos, se habla de Hard Real-Time Systems (sistemas de tiempo real estricto), por contraposición con los que permiten que algunos plazos no se cumplan (Soft Real-Time Systems). En Ingeniería Aeroespacial el foco debe estar en los de tiempo real estricto.

En temas anteriores hemos modelado el sistema con máquinas de estado jerárquicas, extendidas y no deterministas. No es preciso indicar el orden exacto en el que se ejecutan las acciones para garantizar que el sistema es correcto. Esto implica que el modelo del sistema frecuentemente incluye un considerable no-determinismo. La forma precisa en que se entrelazan las reacciones a los eventos del sistema no influye en la corrección desde el punto de vista funcional. En cualquier caso se cumplen las propiedades LTL y CTL. Sin embargo puede influir y mucho en el tiempo necesario para reaccionar (latencia) o para realizar las tareas, porque la ejecución de unas tareas puede afectar a otras cuando existen recursos compartidos.

En esta página utilizaremos la misma notación que [Barns&Wellings]. Utilizaremos el modelo simplificado en el que los tiempos de cambio de contexto son despreciables. Asegúrate de que entiendes todos los conceptos que se mencionan en la tabla siguiente.

Símbolo	Significado
$C_i$	Tiempo de cómputo en el caso peor (WCET) de la tarea $i$.
$T_i$	Periodo de la tarea $i$.
$D_i$	Plazo (deadline) de la tarea $i$.
$I_i$	Tiempo de interferencia en la tarea $i$ debido a tareas más prioritarias.
$B_i$	Tiempo de bloqueo en la tarea $i$ debido a tareas menos prioritarias que comparten recursos.
$R_i$	Tiempo de respuesta de la tarea $i$.
$U_i$	Utilización debida a la tarea $i$, es decir, $C_i/T_i$.

Nuestro modelo de tareas estará basado en todo lo realizado anteriormente. Cada tarea corresponderá a la función update de una máquina de estados. El conjunto de tareas no es más que el conjunto de máquinas de estado concurrentes. En algunos casos tendremos que imponer restricciones adicionales para que la ejecución corresponda a la secuencia deseada. Por ejemplo, como explicamos en el tema de máquinas de estado concurrentes las máquinas de estado jerárquicas necesitan una secuencia de ejecución particular (orden parcial) entre la máquinas que contiene el estado padre y la máquina que lo refina. La máquina más profunda en la jerarquía siempre debe ejecutarse antes que la menos profunda. Esto puede tratarse fácilmente con una correcta asignación de prioridades.

La estructura más utilizada para la planificación de tareas de tiempo real es el ejecutivo cíclico. Esto se debe más a una visión conservadora. que pretende conocer a priori todos los detalles de la ejecución, más que a un motivo técnico. La ejecución se planifica en un hiperperiodo que es el mínimo común múltiplo de los periodos de las tareas que se deben ejecutar. El hiperperiodo se divide en un conjunto de ciclos menores (típicamente de duración igual a la del menor periodo) y se colocan las tareas de manera que se cumplan los periodos y plazos. Para ilustrarlo veamos un ejemplo:

En este esquema no es necesaria ninguna tarea del sistema operativo, puesto que simplemente se llama a las funciones de cada tarea en secuencia. Tampoco hay problemas de acceso concurrente (no son necesarios los mutex ni ninguna otra primitiva de sincronización). En el caso de ejemplo de la figura correspondería a algo así:

1fsm_t *a, *b, *c, *d, *e;
2for (int ciclo = 0; ; ciclo = (ciclo + 1) % 4) {
3    switch (ciclo) {
4    case 0:
5        fsm_update(a); fsm_update(b); fsm_update(c);
6        break;
7    case 1:
8        fsm_update(a); fsm_update(b); fsm_update(d); fsm_update(e);
9        break;
10    case 2:
11        fsm_update(a); fsm_update(b); fsm_update(c);
12        break;
13    case 3:
14        fsm_update(a); fsm_update(b); fsm_update(d);
15        break;
16    }
17}

Nótese que todas las máquinas de estado implementadas hasta ahora en este curso responden a este esquema salvo por el hecho de que solo tenemos un ciclo menor.

Sin embargo plantea muchos problemas:

• Es complejo incorporar tareas esporádicas, especialmente cuando las tasas de utilización son elevadas.
• Es complejo incorporar tareas con periodos muy grandes en comparación con el resto, porque alarga el hiperperiodo y por tanto los ciclos menores que hay que planificar.
• La dificultad intrínseca de construir el ejecutivo cíclico con muchas tareas (es un problema NP-hard).
• Las tareas que tienen un $C_i$ mayor que lo que puede asignarse en cada ciclo menor deben dividirse en tareas menores. Eso es muy problemático porque puede afectar a la corrección y por tanto requiere nueva verificación del modelo. Recuerda que en este curso asumimos que las tareas son invocaciones a funciones update de las máquinas de estado concurrentes que se ejecutan en el sistema.

Esquemas frecuentes de asignación de prioridades son:

• Rate-monotonic scheduling, o planificación monótona en frecuencia. Las prioridades se asignan según la frecuencia ($1/T_i$). A mayor frecuencia, mayor prioridad. Este esquema no es óptimo cuando el plazo de las tareas difiere de su periodo.
• Deadline-monotonic scheduling, o planificación monótona en plazos. Las prioridades se asignan en orden inverso a sus plazos. Las tareas con menos plazo tienen mayor prioridad. Este esquema es óptimo con el modelo de tareas simplificado en el que despreciamos la influencia de los cambios de contexto.
• Esquemas de asignación dinámica de prioridades. Permiten acomodar mejor la variación de carga en el sistema por tareas esporádicas.

Sea un sistema de 4 tareas con los datos que muestra la tabla. Las prioridades están asignadas siguiendo una planificación monótona en plazos.

Tarea	$T_i$	$C_i$	$D_i$	$P_i$
$\tau_1$	20	3	5	4
$\tau_2$	15	3	7	3
$\tau_3$	10	4	10	2
$\tau_4$	20	3	20	1

En FreeRTOS tendríamos una implementación trivial:

1#include <freertos/FreeRTOS.h>
2#include <freertos/task.h>
3
4void task_1 (void* p) { /* ... */}
5void task_2 (void* p) { /* ... */}
6void task_3 (void* p) { /* ... */}
7void task_4 (void* p) { /* ... */}
8
9void app_main() 
10{
11    TaskHandle_t t1, t2, t3, t4;
12    xTaskCreate (task_1, "t1", 2048, NULL, 4, &t1);
13    xTaskCreate (task_2, "t2", 2048, NULL, 3, &t2);
14    xTaskCreate (task_3, "t3", 2048, NULL, 2, &t3);
15    xTaskCreate (task_4, "t4", 2048, NULL, 1, &t4);
16}

Consulta el tema de Recursos compartidos para una descripción de los mecanismos de FreeRTOS para sincronización durante el acceso a recursos.

En el contexto de esta asignatura utilizaremos las tareas como una de las opciones de implementación de las máquinas de estados concurrentes. La implementación con tareas difiere muy poco de la implementación con ejecutivo cíclico:

1. Cada máquina de estados corresponde a una tarea periódica cuyo único contenido funcional es la llamada a fsm_update de esa máquina de estados. El periodo y la prioridad de esta tarea deberá determinarse mediante el Análisis del Tiempo de Respuesta.

2. Las comunicaciones entre las diferentes máquinas de estado implican acceso a variables compartidas entre dos o más tareas. Por tanto es necesario añadir mecanismos de sincronización entre ellas.

3. La función app_main pasa a estar prácticamente vacía. Solamente tiene que llamar al constructor de las máquinas de estado, crear las primitivas de sincronización (e.g. mutexes) para acceso a variables compartidas y crear las tareas correspondientes a cada una de las máquinas de estado.

Veamos un esquema para ilustrar el método. Cada máquina de estados con variables compartidas tendrá las primitivas de acceso necesarias para sincronizar los accesos. El método es similar a la implementación de las máquinas de estado extendidas. Las primitivas de sincronización se comportan como una variable de estado más.

1typedef struct {
2    fsm_t parent;
3    int variable;
4    SemaphoreHandle_t mutex;
5} my_fsm_t;

Ahora, cada vez que se accede a cada variable compartida (tanto para lectura como para escritura) debemos usar la primitiva de sincronización correspondiente:

1// ...
2xSemaphoreTake(self->mutex, portMAX_DELAY);
3self->variable = 0;
4xSemaphoreGive(self->mutex);
5// ...

En cuanto a la implementación de la tarea es también elemental. Por ejemplo:

1typedef struct {
2    fsm_t* fsm;
3    TickType_t period;
4} task_data_t;
5
6void fsm_task (void* p)
7{
8    task_data_t* data = (task_data_t*) p;
9
10    TickType_t last = xTaskGetTickCount();
11    for (;;) {
12        fsm_update (data->fsm);
13        vTaskDelayUntil(&last, data->period);
14    }
15}

La misma tarea se puede usar para todas las máquinas de estado, puesto que todo lo que cambia se pasa en la estructura del argumento. La función app_main queda reducida a su mínima expresión. Por ejemplo, veamos tres máquinas de estado con una variable compartida entre t1y t2 y otra compartida entre t2 y t3:

1void app_main()
2{
3    SemaphoreHandle_t m1 = xSemaphoreCreateMutex();
4    SemaphoreHandle_t m2 = xSemaphoreCreateMutex();
5
6    my_fsm1_t* fsm1 = my_fsm1_new(..., m1);
7    my_fsm2_t* fsm2 = my_fsm2_new(..., m1, m2);
8    my_fsm3_t* fsm3 = my_fsm3_new(..., m2);
9
10    task_data_t data1 = { fsm1, pdMS_TO_TICKS(10) };
11    task_data_t data2 = { fsm2, pdMS_TO_TICKS(20) };
12    task_data_t data3 = { fsm3, pdMS_TO_TICKS(30) };
13
14    xTaskHandle t1, t2, t3;
15    xTaskCreate (fsm_task, "t1", 2048, &data1, 4, &t1);
16    xTaskCreate (fsm_task, "t2", 2048, &data2, 3, &t2);
17    xTaskCreate (fsm_task, "t3", 2048, &data3, 2, &t3);
18}

Nótese cómo la segunda máquina necesita los dos mutex, mientras que las otras solo necesitan un mutex.

Advertencia
Adapta los nombres de los tipos auxiliares a tu problema (my_fsm_t, task_data_t, etc.).

Importante
Es importante utilizar el mismo mutex en todas las tareas que acceden a una misma variable compartida.