1. O abismo fundamental entre “rápido” e “tempo real”

Na linguagem cotidiana, “processamento em tempo real” é frequentemente confundido com “execução ultrarrápida”. Contudo, nem mesmo um servidor com processador superescalar multicore de vários gigahertz, capaz de responder consultas em média em um milissegundo, jamais poderia controlar o sistema Fly-by-Wire de um avião comercial, o acionamento de um airbag automotivo ou um marca-passo cardíaco. Por quê? Porque sistemas de propósito geral otimizam a vazão média (Average Throughput): se um cálculo leva $0,5\,\text{ms}$ em $99,999\,\%$ das vezes, mas uma vez em um milhão atrasa $200\,\text{ms}$ devido a um cache miss, page fault ou pausa do Garbage Collector (GC), o avião perde sustentação ou o airbag explode após a colisão.

Segundo a formulação clássica de Donald Gillies e Hermann Kopetz, o axioma da computação em tempo real estabelece que a corretude de um sistema depende não apenas da exatidão lógica e aritmética do resultado, mas também do instante físico $t$ em que ele é entregue em relação ao seu prazo final (deadline $d_i$). Pela função de utilidade temporal $U(t)$, distinguem-se três classes:

• Tempo real rígido (Hard Real-Time): Perder um único prazo ($t > d$) causa falha catastrófica ($U = -\infty$, ex.: controle de voo, freios ABS). Exige prova matemática estática offline.
• Tempo real firme (Firm Real-Time): Um resultado atrasado tem valor zero ($U = 0$) e é descartado imediatamente (ex.: inspeção visual em esteira de alta velocidade, cancelamento de ordens em HFT).
• Tempo real brando (Soft Real-Time): A utilidade decai continuamente após $d$ (ex.: streaming de vídeo a 60 fps, chamadas VoIP).

2. O pesadelo do tempo de execução no pior caso (WCET)

Toda teoria de escalonamento em tempo real pressupõe conhecer previamente o tempo de execução no pior caso (Worst-Case Execution Time, $C_i$) de cada tarefa $\tau_i$. Aqui reside um profundo paradoxo da arquitetura de computadores: quase todos os mecanismos de hardware criados para acelerar a velocidade média de uma CPU (caches L1/L2/L3, predição de desvio, execução fora de ordem OoO, TLB, DVFS e interrupções de gerenciamento do sistema SMI não mascaráveis) destroem a previsibilidade do WCET.

Em pipelines Out-of-Order com caches ocorrem inclusive anomalias temporais (Timing Anomalies): um acerto local de cache (Cache Hit) pode permitir que um caminho especulativo ocupe antes um barramento compartilhado, tornando o tempo total de execução do programa maior do que se tivesse ocorrido um erro de cache (Cache Miss)! Por isso, sistemas críticos (DO-178C Nível A, ISO 26262 ASIL-D) utilizam memória Scratchpad SRAM / TCM determinística e travamento de cache (Cache Locking), calculando estaticamente o limite superior do WCET via interpretação abstrata e a técnica de enumeração implícita de caminhos (IPET) como um problema de programação linear inteira (ILP) sobre o grafo de fluxo de controle (CFG):

3. Liu & Layland (1973): Escalonamento periódico (RMS vs. EDF)

Seja um conjunto de $n$ tarefas periódicas independentes $\Gamma = \{\tau_1, \dots, \tau_n\}$ com $\tau_i = (C_i, T_i, D_i)$ (WCET $C_i$, período $T_i$, prazo implícito $D_i = T_i$). A utilização total do processador é:

Em 1973, C. L. Liu e James W. Layland demonstraram os teoremas fundamentais que regem prioridades estáticas e dinâmicas:

3.1 Escalonamento Monotônico em Taxa (RMS) e o limite $\ln 2 \approx 69,3\,\%$

No escalonamento preemptivo de prioridade fixa, a regra Rate Monotonic (RMS) atribui prioridades estáticas em ordem inversa ao período: quanto menor o período $T_i$ (maior a frequência $1/T_i$), maior a prioridade estática. Liu & Layland provaram o teorema do instante crítico (o pior tempo de resposta de $\tau_i$ ocorre quando ela é liberada simultaneamente com todas as tarefas de maior prioridade em $t=0$) e a otimalidade do RMS entre todos os algoritmos de prioridade fixa, com o menor limite superior de utilização:

Importante: $69,3\,\%$ é apenas uma condição suficiente, não necessária! Se os períodos forem harmônicos (cada período é múltiplo inteiro dos menores, ex.: $5\,\text{ms}, 10\,\text{ms}, 20\,\text{ms}$), o RMS atinge 100% de utilização. Para conjuntos gerais, a análise de tempo de resposta (RTA) de Joseph & Pandya (1986) fornece uma condição necessária e suficiente exata por iteração de ponto fixo ($R_i \le D_i$):

3.2 Primeiro o Prazo Mais Cedo (EDF) e a otimalidade de $100\,\%$

No escalonamento preemptivo de prioridade dinâmica, o Earliest Deadline First (EDF) concede a cada instante a prioridade máxima ao trabalho pronto cujo prazo absoluto $d_{i,k} = r_{i,k} + D_i$ esteja mais próximo. Em um monoprocessador, a condição necessária e suficiente de escalonabilidade sob EDF atinge o limite físico:

Exemplo: Com $\tau_1 = (C_1=2, T_1=5)$ e $\tau_2 = (C_2=4, T_2=7)$, a utilização é $U = 97,14\,\%$. Sob RMS, a chegada de $\tau_{1,2}$ em $t=5$ ($d=10$) interrompe cegamente $\tau_{2,1}$ ($d=7$, faltando apenas $1\,\text{ms}$), causando $R_2 = 8 > 7$ (perda de prazo!). Sob EDF, em $t=5$, como $d_{2,1}=7 < d_{1,2}=10$, o EDF impede a preempção e $\tau_{2,1}$ termina a tempo em $t=6 \le 7$.

Ainda assim, a indústria (VxWorks, FreeRTOS, QNX, AUTOSAR) prefere RMS/DMS porque, sob sobrecarga transitória ($U > 1,0$), o EDF sofre um efeito dominó catastrófico onde uma tarefa atrasada monopoliza a CPU e faz todas as seguintes falharem em cadeia, enquanto o RMS protege $100\,\%$ as tarefas críticas de alta prioridade e é implementado em $O(1)$ com bitmap e instrução CLZ.

4. O incidente da Mars Pathfinder da NASA (1997) e a inversão de prioridade

Em julho de 1997, após pousar em Marte, a sonda Mars Pathfinder da NASA (CPU IBM RAD6000 rodando o RTOS VxWorks) começou a sofrer reinicializações completas forçadas pelo seu watchdog, perdendo dias inteiros de dados científicos.

A causa foi uma inversão de prioridade ilimitada (Unbounded Priority Inversion) entre três tarefas disputando um mutex $M$ que protegia o “barramento de informações” compartilhado:

• A tarefa meteorológica de baixa prioridade $\tau_L$ (ASI/MET) trava o mutex $M$;
• A tarefa crítica de distribuição do barramento de alta prioridade $\tau_H$ (bc_dist) acorda, solicita $M$ e fica bloqueada;
• Antes que $\tau_L$ libere $M$, chegam tarefas de comunicação de prioridade média $\tau_M$ (que não usam $M$!). Como $\text{Priority}(\tau_M) > \text{Priority}(\tau_L)$, $\tau_M$ interrompe $\tau_L$ por longo tempo, impedindo que $\tau_L$ destrave $M$ e mantendo $\tau_H$ bloqueada até o watchdog reiniciar a espaçonave.

  flowchart TD
    subgraph Bug["Inversão de prioridade ilimitada na Mars Pathfinder (1997)"]
        B1["1. Tarefa de baixa prioridade τ_L trava o mutex M"] --> B2["2. Tarefa de alta prioridade τ_H solicita M e entra em estado BLOQUEADO"]
        B2 --> B3["3. Chega a tarefa de prioridade média τ_M (que não usa M)!<br/>Como Priority(τ_M) > Priority(τ_L), τ_M interrompe τ_L e monopoliza a CPU"]
        B3 --> B4["4. τ_L não consegue liberar M -> τ_H fica bloqueada indefinidamente<br/>O watchdog expira e força o reset completo da sonda em Marte!"]
    end

  flowchart TD
    subgraph Fix["Protocolos de sincronização de Sha, Rajkumar & Lehoczky (1990)"]
        F1["Solução A: Protocolo de Herança de Prioridade (PIP)<br/>Ao bloquear τ_H em M, o kernel eleva a prioridade efetiva de τ_L<br/>ao nível de τ_H! τ_M não pode interromper e τ_L libera M imediatamente"]
        F2["Solução B: Protocolo de Teto de Prioridade Imediato (ICPP)<br/>Cada mutex M recebe um teto Ceil(M) = maior prioridade de seus usuários.<br/>Elevação imediata ao travar: zero deadlock e no máximo 1 bloqueio (B_i)!"]
        F1 --> F2
    end

A solução matemática foi provada por Sha, Rajkumar e Lehoczky em 1990:

1. Protocolo de Herança de Prioridade (PIP: Priority Inheritance Protocol): Quando $\tau_H$ bloqueia em um mutex $M$ mantido por $\tau_L$, o kernel eleva temporariamente a prioridade efetiva de $\tau_L$ ao nível de $\tau_H$, impedindo que $\tau_M$ interrompa. Após reproduzir o bug na Terra, os engenheiros do JPL enviaram a 190 milhões de quilômetros um comando C ao shell do VxWorks alterando na RAM a variável global SEM_INVERSION_SAFE de 0 para 1, salvando a missão!
2. Protocolo de Teto de Prioridade (PCP / ICPP: Immediate Priority Ceiling Protocol): Como o PIP ainda permite bloqueio encadeado e deadlock, o ICPP (padrão em POSIX PTHREAD_PRIO_PROTECT e AUTOSAR OS) atribui a cada mutex $M_k$ um teto estático $\text{Ceil}(M_k) = \max\{\text{Priority}(\tau_i) \mid \tau_i \text{ usa } M_k\}$ e eleva a prioridade de qualquer tarefa no exato instante em que ela adquire $M_k$. Isso garante ausência total de deadlocks e limita o bloqueio máximo de qualquer tarefa a no máximo uma única seção crítica ($B_i$):