Aula 14 — Sistemas de Tempo Real

Objetivos

Ao final desta aula você deve ser capaz de:

• Distinguir sistemas de tempo real crítico (hard) de não-crítico (soft) com exemplos concretos.
• Explicar os dois tipos de latência (interrupção e despacho) e por que minimizá-las é fundamental.
• Caracterizar tarefas periódicas com os parâmetros t, d e p, e calcular utilização de CPU.
• Aplicar o algoritmo Rate Monotonic Scheduling (RMS): atribuir prioridades e construir gráfico de Gantt.
• Aplicar o algoritmo Earliest Deadline First (EDF): atribuir prioridades dinâmicas e comparar com RMS.
• Identificar o limite de utilização do RMS (fórmula N * (2^(1/N) - 1)) e quando o EDF é superior.
• Descrever o scheduling de cotas proporcionais e o uso da API POSIX (SCHED_FIFO, SCHED_RR).

---

Conteúdo

O que é um sistema de tempo real?

Em sistemas convencionais, a corretude de uma computação depende apenas do resultado lógico: dado que a saída está certa, não importa quando ela chegou. Em sistemas de tempo real, a corretude depende tanto do resultado quanto do tempo:

Uma resposta correta entregue depois do prazo é equivalente a uma resposta errada.

Sistema convencional:   Resultado correto = correto (quando quer que chegue)
Sistema de tempo real:  Resultado correto entregue dentro do deadline = correto
                        Resultado correto entregue APÓS o deadline = ERRADO

Analogia: um airbag automotivo que infla 200ms depois da colisão — a resposta lógica está correta (inflar), mas o timing errado torna a resposta inútil ou fatal.

Hard vs. Soft Real-Time

Classificação	Definição	Consequência de perder deadline	Exemplos
Hard real-time	Perder o deadline é falha catastrófica	Falha do sistema, perigo físico	Freios ABS, controle de voo, pacemaker, airbag, usinas nucleares
Soft real-time	Perder o deadline degrada a qualidade	Degradação de serviço, não catastrófico	Streaming de vídeo, jogos, interface gráfica, VoIP

Soft real-time é atendido por qualquer SO moderno com scheduling por prioridades preemptivo — processos de tempo real recebem a maior prioridade. Hard real-time requer algoritmos formalmente verificáveis que garantam que nenhum deadline jamais será perdido.

---

Minimizando a latência

Um sistema de tempo real é dirigido por eventos: uma roda derrapa, um sensor detecta obstáculo, um pacote de rede chega. O sistema deve responder no prazo.

Latência do evento = tempo entre a ocorrência do evento e seu atendimento.

Evento ocorre
      │
      ▼
[ Interrupção gerada ]
      │  latência de interrupção
      ▼
[ ISR inicia execução ]
      │  latência de despacho
      ▼
[ Processo de tempo real executa ]
      │
      ▼
  Evento atendido

Latência de interrupção

Tempo desde a chegada da interrupção até o início da rotina de serviço de interrupção (ISR). Composta por:

1. Tempo para concluir a instrução em execução
2. Identificação do tipo de interrupção
3. Salvamento do contexto do processo atual

Fator crítico: interrupções desabilitadas para proteger estruturas de dados do kernel. Enquanto interrupções estão desabilitadas, eventos ficam enfileirados — mas nenhum ISR começa. SOs de tempo real real exigem que intervalos com interrupções desabilitadas sejam extremamente curtos e limitados.

Latência de despacho

Tempo para o despachante interromper o processo atual e iniciar o processo de tempo real. Composta por:

1. Preempção do processo em execução no kernel (requer kernel preemptivo)
2. Liberação de recursos retidos por processos de baixa prioridade

Exemplo (Solaris): com preempção desabilitada: latência > 100ms. Com preempção habilitada: latência < 1ms — diferença de 100×.

A técnica mais eficaz para minimizar a latência de despacho é o kernel preemptivo — que pode ser interrompido a qualquer momento, inclusive durante chamadas de sistema.

---

Scheduling baseado em prioridades

O requisito mínimo para soft real-time: scheduler baseado em prioridades preemptivo. Processos de tempo real recebem a maior prioridade disponível.

Linux: prioridades 0–99 para tempo real (acima do CFS)
Windows: classe REALTIME_PRIORITY_CLASS (prioridades 16–31)
Quando processo RT fica pronto → preempta qualquer processo normal imediatamente

Isso não garante hard real-time — apenas garante que processos RT executarão antes de qualquer processo normal. Não há garantia de que cumprirão seus deadlines específicos.

---

Tarefas periódicas: parâmetros formais

Algoritmos de scheduling de tempo real crítico assumem que as tarefas são periódicas com os seguintes parâmetros:

Parâmetro	Símbolo	Definição
Tempo de processamento	t	Tempo de CPU necessário por período
Deadline	d	Prazo máximo para conclusão dentro do período
Período	p	Intervalo entre ativações da tarefa
Taxa	1/p	Frequência de ativação

Restrição: 0 ≤ t ≤ d ≤ p

Utilização da CPU por uma tarefa periódica: U_i = t_i / p_i

Utilização total: U = Σ(t_i / p_i) — deve ser ≤ 1 (100%) para que o sistema seja escalonável.

Algoritmo de controle de admissão: antes de aceitar uma nova tarefa, o scheduler verifica se os deadlines de todas as tarefas (incluindo a nova) continuarão sendo cumpridos. Se não puder garantir, rejeita a tarefa.

---

Rate Monotonic Scheduling (RMS)

Regra: prioridade estática inversamente proporcional ao período — tarefas com período menor recebem prioridade mais alta.

Período menor → mais frequente → maior importância → prioridade MAIOR
Período maior → menos frequente → menor importância → prioridade MENOR

RMS é ótimo entre algoritmos de prioridade estática: se um conjunto de tarefas não pode ser escalonado por RMS, nenhum algoritmo de prioridade estática consegue escaloná-lo.

Limite de utilização do RMS

O RMS não consegue utilizar 100% da CPU. O limite de utilização para N tarefas é:

U_RMS = N * (2^(1/N) - 1)

N tarefas	Limite de utilização
1	100,0%
2	82,8%
3	77,9%
5	74,4%
∞	69,3% ≈ ln(2)

Interpretação: se a utilização total ≤ limite, RMS garante que todos os deadlines são cumpridos. Se a utilização excede o limite, RMS pode perder deadlines (mas não necessariamente — o limite é conservador).

Exemplo 1 — RMS com sucesso

P1: p=50, t=20 → U₁ = 20/50 = 0,40
P2: p=100, t=35 → U₂ = 35/100 = 0,35
Utilização total = 0,75 < 0,828 (limite para N=2) → RMS garante cumprimento dos deadlines.

RMS: P1 tem prioridade maior (período menor).

Gráfico de Gantt — RMS (P1 prioridade maior):
│   P1(20)   │      P2(30)      │P1(20)│P2(5)│     idle     │
0           20                 50    70    75             100
                         P2 preemptado em t=50 por P1
 
Deadlines: P1 termina em 20 < 50 ✓ e em 70 < 100 ✓
           P2 termina em 75 < 100 ✓
Todos os deadlines cumpridos!

Exemplo 2 — RMS falha, EDF resolve

P1: p=50, t=25 → U₁ = 0,50
P2: p=80, t=35 → U₂ = 0,4375
Utilização total = 0,9375 > 0,828 → RMS não garante.

Gráfico de Gantt — RMS (P1 prioridade maior):
│    P1(25)    │    P2(25/35)    │P1(25)│P2?│
0             25                50    75   80
                          P2 preemptado em t=50 por P1
P2 precisa de mais 10ms → disponível em t=75
P2 deadline = 80 → termina em 85 > 80 ✗  DEADLINE PERDIDO!

---

Earliest Deadline First (EDF)

Regra: prioridade dinâmica baseada no deadline absoluto mais próximo — o processo com deadline mais cedo recebe maior prioridade. Quando um processo se torna executável, anuncia seu deadline ao scheduler.

EDF: sempre executa o processo cujo deadline absoluto é MENOR
     Quando novo processo chega ou deadline muda → reavalia prioridades

EDF é teoricamente ótimo: pode escalonar qualquer conjunto de tarefas com utilização ≤ 100%. Na prática, o overhead de mudança de contexto e tratamento de interrupções impede 100% real.

Diferença crítica entre RMS e EDF:

• RMS: prioridades fixas (estáticas) — simples de implementar, previsível sob sobrecarga
• EDF: prioridades dinâmicas — complexo, ótimo em utilização, comportamento imprevisível sob sobrecarga

EDF no Exemplo 2 (onde RMS falhou)

P1: p=50, t=25 | P2: p=80, t=35

Gráfico de Gantt — EDF:
t=0:  P1 deadline=50, P2 deadline=80 → P1 executa (deadline menor)
t=25: P1 terminou. P2 executa.
t=50: P1 novo período, deadline=100. P2 deadline=80 < 100 → P2 continua!
      (EDF difere de RMS aqui: P2 não é preemptado)
t=60: P2 terminou. P1 executa.
t=85: P1 terminou.
t=80: P2 segundo período, deadline=160 (futuro).
 
│    P1(25)   │        P2(35)         │   P1   │...
0            25                      60      85
P1 deadline 50 ✓ (termina em 25)
P2 deadline 80 ✓ (termina em 60)
TODOS OS DEADLINES CUMPRIDOS!

EDF aproveitou que P2 tinha deadline mais próximo em t=50, mesmo sendo P2 de "menor prioridade" no RMS.

Comparação RMS vs. EDF

Aspecto	RMS	EDF
Tipo de prioridade	Estática (pelo período)	Dinâmica (pelo deadline atual)
Otimalidade	Ótimo entre prioridade estática	Ótimo teoricamente (100% utilização)
Limite de utilização	N*(2^(1/N)-1) ≈ 69% para N→∞	100% (teórico)
Implementação	Simples	Mais complexo
Comportamento sob sobrecarga	Previsível (tarefas de menor prioridade perdem deadline)	Imprevisível (qualquer tarefa pode perder)
Uso na indústria	Preferido (previsibilidade)	Pesquisa, Linux SCHED_DEADLINE

Por que a indústria prefere RMS? Previsibilidade é mais importante que eficiência máxima em sistemas hard real-time. Com RMS, sabe-se exatamente quais tarefas perderão deadline em caso de sobrecarga. Com EDF, qualquer tarefa pode perder — dificulta certificação de segurança.

---

Scheduling de Cotas Proporcionais

Regra: T cotas totais distribuídas entre aplicações. Cada aplicação com N cotas recebe N/T do tempo de CPU.

Exemplo: T = 100 cotas totais
  Processo A: 50 cotas → 50% da CPU
  Processo B: 15 cotas → 15% da CPU
  Processo C: 20 cotas → 20% da CPU
  Disponível:  15 cotas
  Novo processo D solicita 30 cotas → REJEITADO (só há 15 disponíveis)

Funciona com controle de admissão: um novo processo só é admitido se houver cotas suficientes disponíveis para não violar as garantias dos processos existentes.

---

API POSIX de Tempo Real

O padrão POSIX.1b define classes de scheduling para threads de tempo real:

Classe	Comportamento
SCHED_FIFO	FIFO dentro de cada nível de prioridade. Thread de maior prioridade executa até terminar ou bloquear — sem time-sharing entre mesma prioridade.
SCHED_RR	Round-robin dentro de cada nível de prioridade. Similar ao SCHED_FIFO, mas com time-sharing entre threads de mesma prioridade.
SCHED_OTHER	Comportamento definido pela implementação (normalmente CFS no Linux).
SCHED_DEADLINE	Implementação EDF no Linux (kernel ≥ 3.14).

/* Somente leitura — configurando política de scheduling POSIX */
#include <pthread.h>
#include <sched.h>
 
pthread_attr_t attr;
int policy;
 
pthread_attr_init(&attr);
 
/* obtém a política atual */
pthread_attr_getschedpolicy(&attr, &policy);
/* policy == SCHED_OTHER (padrão), SCHED_FIFO, ou SCHED_RR */
 
/* define SCHED_FIFO para thread de tempo real */
pthread_attr_setschedpolicy(&attr, SCHED_FIFO);
 
/* define prioridade dentro da classe RT */
struct sched_param param;
param.sched_priority = 50;   /* 1–99 para SCHED_FIFO/RR no Linux */
pthread_attr_setschedparam(&attr, &param);
 
/* cria thread com atributos de tempo real */
pthread_create(&tid, &attr, funcao_rt, NULL);

No Linux: prioridades RT (SCHED_FIFO/RR) ficam na faixa 1–99. Prioridade 99 = maior. Tarefas RT sempre preemptam tarefas CFS (SCHED_OTHER), independentemente do vruntime.

Atividade prática rápida: observe as classes de scheduling dos processos em execução:

ps -eo pid,cls,pri,ni,comm | grep -v CLS | head -20
# CLS: TS=tempo compartilhado, FF=FIFO, RR=round-robin
chrt -f 50 ./meu_programa   # executa com SCHED_FIFO prioridade 50

---

Exemplos do mundo real

Sistema          Tipo    Deadline típico    Tecnologia
──────────────────────────────────────────────────────────
Freios ABS       Hard    3–5 ms             RTOS dedicado
Airbag           Hard    < 30 ms            RTOS dedicado
Controle de voo  Hard    10–50 ms           VxWorks, RTEMS
Marca-passo      Hard    variável           RTOS certificado
Controle nuclear Hard    < 100 ms           RTOS certificado
Streaming 4K     Soft    16–33 ms/frame     Linux com RT patches
VoIP             Soft    20–150 ms          Linux SCHED_RR
Jogos online     Soft    16–33 ms/frame     SO de propósito geral
Interface gráfica Soft   16 ms (60 fps)     prioridade elevada

---

Resumo dos algoritmos de tempo real

Classificação de sistemas:
  Soft RT: scheduler preemptivo por prioridade → suficiente
  Hard RT: garantias formais de deadline → RMS ou EDF
 
Algoritmos para Hard RT:
  RMS: prioridade estática pelo período (p menor → prioridade maior)
       Ótimo entre prioridade estática. Limite ≈ 69%. Previsível.
  
  EDF: prioridade dinâmica pelo deadline absoluto mais cedo
       Ótimo teórico (100%). Imprevisível sob sobrecarga.
       Linux: SCHED_DEADLINE desde 3.14
 
  Cotas proporcionais: garantias percentuais de CPU por grupo

---

Exercícios

Questões dissertativas

Q1

Qual a diferença fundamental entre um sistema de tempo real crítico (hard) e não-crítico (soft)? Dê dois exemplos concretos de cada tipo e explique por que a distinção importa para o design do SO.

Q2

Explique os dois tipos de latência em sistemas de tempo real (latência de interrupção e latência de despacho) e descreva o que compõe cada uma. Por que o kernel preemptivo é crucial para minimizar a latência de despacho?

Q3

Duas tarefas periódicas: P1(p=40, t=15) e P2(p=60, t=20). Calcule a utilização total. O RMS garante que todos os deadlines serão cumpridos? Use a fórmula do limite de utilização.

Q4Difícil

Para as tarefas P1(p=50, t=25) e P2(p=80, t=35), construa o gráfico de Gantt para RMS e para EDF no intervalo [0, 100]. Indique quais deadlines são cumpridos ou perdidos em cada algoritmo.

Q5

Por que o RMS é preferido na indústria de sistemas embarcados/tempo real em relação ao EDF, mesmo que o EDF tenha utilização teórica de 100%?

Q6

Explique o problema de inversão de prioridades. Como ele interfere na latência de despacho em sistemas de tempo real? Qual a solução clássica?

Q7

Qual a diferença entre SCHED_FIFO e SCHED_RR no POSIX? Em que situação você usaria cada um para threads de tempo real?

Q8

Três tarefas: P1(p=20, t=5), P2(p=50, t=10), P3(p=100, t=20). Calcule a utilização total e determine se o RMS garante o cumprimento de todos os deadlines usando o limite teórico.

Q9

O Linux implementa SCHED_DEADLINE baseado em EDF. Qual a diferença prática entre usar SCHED_FIFO com prioridade 99 e SCHED_DEADLINE para uma tarefa de tempo real?

Q10Difícil

Por que sistemas de tempo real crítico não podem simplesmente usar Linux padrão com threads SCHED_FIFO de alta prioridade? Quais garantias um RTOS dedicado (VxWorks, RTEMS) oferece que o Linux não oferece por padrão?

---

Quiz de múltipla escolha

Quiz10 questões

1. Um sistema de freios ABS detecta uma roda derrapando mas só consegue acionar os freios 200ms depois (deadline era 5ms). Do ponto de vista de sistemas de tempo real, o que aconteceu?

• a)O sistema funcionou corretamente — a resposta estava logicamente certa
• b)Houve uma falha de soft real-time — degradação de qualidade aceitável
• c)Houve uma falha de hard real-time — a resposta correta após o deadline é equivalente a nenhuma resposta
• d)O sistema entrou em deadlock
• e)O scheduler escolheu o algoritmo errado

2. Qual o principal fator que aumenta a latência de interrupção em sistemas de tempo real?

• a)O número de processos na fila de prontos
• b)O tamanho do quantum de tempo usado no scheduling
• c)Intervalos em que interrupções ficam desabilitadas enquanto o kernel atualiza estruturas de dados
• d)O algoritmo de scheduling usado (FIFO, RR, etc.)
• e)O número de núcleos de CPU disponíveis

3. No RMS, qual tarefa recebe maior prioridade entre T1(p=20ms) e T2(p=50ms)?

• a)T2 — período maior significa mais tempo disponível, então deve ter maior prioridade
• b)T1 — período menor significa maior frequência de execução, portanto maior prioridade
• c)Igual — ambas têm a mesma prioridade no RMS
• d)Depende do tempo de execução (t) de cada tarefa
• e)Depende do deadline (d) de cada tarefa

4. Qual é o limite de utilização máximo garantido pelo RMS com N=2 tarefas?

• a)50%
• b)69,3%
• c)78,0%
• d)82,8%
• e)100%

5. No EDF, como as prioridades são atribuídas e quando elas mudam?

• a)Prioridades fixas pelo período, como no RMS — nunca mudam
• b)Prioridades atribuídas pelo tempo de execução (t) — mudam quando t muda
• c)Prioridades dinâmicas pelo deadline absoluto mais próximo — reavaliadas quando um processo se torna executável ou completa sua tarefa
• d)Prioridades aleatórias, como no scheduling por loteria
• e)Prioridades atribuídas pelo usuário via nice — nunca mudam automaticamente

6. Por que o EDF é teoricamente ótimo mas a indústria prefere RMS para sistemas de segurança crítica?

• a)EDF é mais difícil de implementar em hardware dedicado
• b)EDF under sobrecarga tem comportamento imprevisível — qualquer tarefa pode perder deadline; RMS tem degradação previsível (tarefas de menor prioridade falham primeiro)
• c)EDF consome mais CPU do que RMS para calcular as prioridades
• d)EDF não suporta preempção; RMS é preemptivo
• e)EDF só funciona com tarefas periódicas; sistemas reais têm tarefas esporádicas

7. Qual a diferença prática entre SCHED_FIFO e SCHED_RR para threads de mesma prioridade?

• a)SCHED_FIFO usa deadline como critério; SCHED_RR usa período
• b)SCHED_FIFO não permite preempção; SCHED_RR com preempção por quantum entre threads de mesma prioridade
• c)SCHED_FIFO é para processos; SCHED_RR é para threads
• d)SCHED_FIFO usa utilização proporcional; SCHED_RR usa FIFO
• e)São idênticos — diferem apenas no nome

8. Uma tarefa RT precisa de 10ms de CPU a cada 40ms. Sua utilização é 25%. Junto com outras 3 tarefas que somam 50% de utilização, o sistema tem 75% total. O RMS garante os deadlines para N=4 tarefas?

• a)Sim — 75% < 100%, então o sistema é escalonável
• b)Não — o limite para N=4 é menor que 75%
• c)Sim — o limite RMS para N=4 é 75,7%, e 75% < 75,7%
• d)Não — RMS não funciona com N > 3 tarefas
• e)Depende das prioridades atribuídas

9. O problema de inversão de prioridades na Mars Pathfinder (1997) foi resolvido como?

• a)Substituindo RMS por EDF no VxWorks a bordo
• b)Reduzindo a frequência das tarefas de alta prioridade
• c)Ativando remotamente a herança de prioridade nos semáforos do VxWorks — em Marte
• d)Adicionando mais núcleos de CPU à sonda
• e)Usando SCHED_DEADLINE em vez de SCHED_FIFO

10. Qual é o scheduling padrão de processos normais (não RT) no Linux, e como tarefas RT (SCHED_FIFO/RR) se relacionam com ele?

• a)Round-Robin (RR) para ambos — tarefas RT têm quantum menor
• b)CFS (Completely Fair Scheduler) para processos normais; tarefas SCHED_FIFO/RR têm prioridade de classe superior e sempre preemptam processos CFS
• c)FIFO para ambos — tarefas RT apenas têm quantum maior
• d)Prioridades por nice para ambos — RT tem nice negativo
• e)Filas multiníveis com retroalimentação para normais; RT usa fila separada sem retroalimentação

---

Referências

Principais (essenciais)

• SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Fundamentos de Sistemas Operacionais. 9. ed. LTC, 2015.
  • §6.6 — Scheduling da CPU de Tempo Real (latência, RMS, EDF, cotas, POSIX)

Aprofundamento (opcionais)

• LIU, C. L.; LAYLAND, J. W. "Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment." JACM, v. 20, n. 1, 1973. (artigo original do RMS)
• STANKOVIC, J. A. "Misconceptions About Real-Time Computing." IEEE Computer, 1988.
• man 7 sched, man 2 sched_setscheduler — documentação POSIX de scheduling no Linux.
• RTEMS Project: https://www.rtems.org — RTOS de código aberto para sistemas embarcados críticos.

---

Recursos Complementares

Opcional — Vídeos para reforçar os conceitos desta aula.

▶25:00:00

ENAprofundamento

Operating Systems — Full Course (25h)

freeCodeCamp.org

Para esta aula, foque no módulo Real-Time CPU Scheduling dentro do curso completo.