Scheduling Cause-Effect Chains without Timing Anomalies in End-to-End Latency

Título: Agendamento de Cadeias Causa-Efeito sem Anomalias de Tempo na Latência de Ponta a Ponta

1. Problema

Em sistemas de tempo real (como os usados em direção autônoma), é crucial que tanto a execução individual das tarefas quanto a propagação de dados atendam a restrições temporais rigorosas. As Cadeias Causa-Efeito (CE) são utilizadas para modelar e analisar o comportamento de ponta a ponta, focando em métricas como o Tempo Máximo de Reação (MRT) e a Idade Máxima de Dados (MDA).

O principal desafio identificado é a existência de Anomalias de Tempo (Timing Anomalies - TAs). Uma anomalia de tempo ocorre quando uma redução local no tempo de execução de uma tarefa (ou em outras cadeias concorrentes) resulta, paradoxalmente, em um aumento da latência total de ponta a ponta.

• Consequências: A presença de TAs torna a análise precisa dos limites superiores de latência extremamente difícil, pois o pior caso não ocorre necessariamente quando todas as tarefas executam com seu Tempo Máximo de Execução (WCET).
• Limitações das Soluções Atuais:
  1. Métodos que eliminam TAs forçando a execução online de todas as tarefas com seu WCET (como em [10]) garantem segurança, mas sacrificam drasticamente a latência média, tornando o sistema ineficiente.
  2. Métodos de análise segura que não alteram o agendamento (como em [11, 12]) ainda lidam com TAs, resultando em limites superiores de latência excessivamente pessimistas e grandes.

2. Metodologia Proposta

Os autores propõem o primeiro tratamento que elimina as anomalias de tempo na latência de ponta a ponta com perda de latência média negligenciável. A solução baseia-se no conceito de Fluxo de Dados Determinístico (DDF - Deterministic Data Flow).

A abordagem é dividida em duas fases (Offline e Online) e visa resolver duas causas fundamentais das anomalias:

1. Variação na estrutura das cadeias de dependência: Mudanças na ordem de execução alteram quais jobs (instâncias de tarefas) se comunicam entre si.
2. Variação nos tempos de leitura/escrita: A incerteza sobre quando os dados são lidos ou escritos altera a duração da cadeia.

Mecanismos Principais:

• Definição de DDF: O DDF estabelece relações de comunicação fixas entre jobs (produtores e consumidores) baseadas em uma simulação offline com WCET.
• Objetivo 1: Leitura Após Escrita (RAW - Read-After-Write):
  • Garante que um job consumidor só inicie a leitura após o job produtor ter concluído a escrita.
  • Implementação: Modificação dos atributos das tarefas (tempo de liberação e prioridades) no agendamento FP (Fixed-Priority) de tempo-triggered (TT-FP). Isso cria dependências de execução sem transformar o sistema em um modelo híbrido de tempo-triggered e event-triggered, preservando a análise de segurança.
• Objetivo 2: Leitura do Intencionado (RFI - Read-From-Intended):
  • Garante que cada job leia os dados do produtor específico definido no DDF, mesmo que dados mais recentes de outras instâncias da mesma tarefa estejam disponíveis.
  • Implementação: Uso de um mecanismo de comunicação multi-tamponada (multi-buffer). Isso permite armazenar múltiplos dados de diferentes jobs de escrita e selecionar o buffer correto conforme o DDF, evitando que a leitura "pule" para um dado indesejado devido a variações de tempo.

Prova de Corretude:
Os autores provam formalmente que, sob DDF:

1. As cadeias de jobs de avanço imediato (immediate forward chains) permanecem invariantes, independentemente de as execuções online serem WCET ou menores.
2. Os limites superior e inferior dos tempos de início e fim dos jobs são preservados pelo agendamento TT-FP modificado.
   Consequentemente, o pior caso de latência (MRT) pode ser calculado com precisão executando apenas uma simulação offline com WCET, eliminando a necessidade de análise exaustiva de cenários.

3. Contribuições Chave

• Insight Fundamental: Identificação das duas causas raiz das anomalias de tempo em latência de ponta a ponta: mudanças estruturais nas cadeias de dependência de jobs e variações nos tempos de leitura/escrita.
• Tratamento Livre de Anomalias (TA-free): Apresentação de uma solução que elimina TAs em cadeias CE sob agendamento FP, com perda de latência média mínima (negligenciável).
• Abordagem de Modelagem: Definição de uma cadeia de avanço imediato mais geral, compatível tanto com comunicação por registro quanto por multi-tamponamento.
• Prova Formal: Demonstração matemática de que o tratamento proposto elimina as anomalias de tempo.
• Avaliação Experimental: Resultados robustos comparando o método com o estado da arte (SOTA).

4. Resultados Experimentais

Os experimentos foram realizados com conjuntos de tarefas sintéticos e benchmarks automotivos, comparando o método proposto com:

• M23: Análise segura com TAs (sem eliminação).
• M21: Tratamento que força execução WCET online (elimina TAs, mas com alta latência média).

Desempenho Observado:

• Tempo Máximo de Reação (MRT): Redução de 9% a 12% em média em comparação com a análise segura existente (M23), chegando a até 61% em casos específicos. O método é mais preciso e menos pessimista.
• Tempo de Reação Médio (ART): O método proposto mantém a latência média muito próxima da solução original (M23), com um aumento de apenas 2% a 5%. Isso é significativamente melhor que a solução M21, que força execução WCET e tem latência média igual ao pior caso.
• Jitter (Variação) de Latência: Redução de 53% a 68% no jitter em comparação com M23, devido à estabilização da estrutura das cadeias de dependência.
• Overhead de Memória: O uso de buffers múltiplos resulta em um aumento muito pequeno no uso de memória.
• Escalabilidade: O método mantém a escalabilidade do sistema; se um conjunto de tarefas era escalável antes, continua escalável após a aplicação do tratamento.

5. Significância

Este trabalho é significativo porque resolve um dilema fundamental em sistemas de tempo real críticos: a tensão entre segurança analítica (garantir limites de tempo precisos) e desempenho médio (eficiência de execução).

• Ao eliminar as anomalias de tempo sem sacrificar a eficiência média, o método permite que sistemas críticos (como automotivos e aeroespaciais) operem com limites de latência mais apertados e previsíveis.
• A capacidade de calcular o pior caso exato através de uma única simulação offline simplifica drasticamente o processo de validação e certificação de sistemas complexos.
• A técnica é aplicável a sistemas de agendamento de prioridade fixa (FP), amplamente utilizados na indústria.