DSRT
Um escalonador dinâmico para
sistemas de tempo real flexível
Motivação




Aplicações de áudio/vídeo são afetadas
pelo tempo
É preciso que os sistemas operacionais
ofereçam tempo de processamento
suficiente e constante
Aplicações tradicionais também devem
utilizar a CPU de forma justa
Criar um escalonador fora do kernel
Descrição





Desenvolvido como um sistema intermediário
(middleware)
Processo roda em nível de usuário
Escalona tarefas periódicas (tempo real) e
aperiódicas
Possui controle de admissão de processos
Versões para Linux, SunOS, Irix e Windows
NT
Características







Garante a alocação de CPU para processos
que utilizem divisão de tempo de
processamento (time-sharing)
Proteção contra utilização excedente de
processamento (overrun)
Teste de utilização de CPU
Suporte a multiprocessadores
Monitoração do escalonador
Reserva de CPU para ser utilizada no futuro
Se adapta dinamicamente às características
dos processos
Arquitetura
Solicitação de Recursos
Aplicação
Resource Broker
ID da reserva ou
sugestão de parâmetros alternativos
Aloca
Recursos
Escalonador de Recursos
Envia dados de
desempenho
Monitor
DSRT
Resource Broker

Realiza





controle de admissão de pedidos
alocação de recursos
alteração de parâmetros
liberação de recursos
Cliente faz solicitações da forma (Q, s, d)



Q = Qualidade esperada do recurso (CPU)
s = Tempo de início da requisição
d = Duração da requisição
Estrutura de dados

TAST (Timely Adaptive State Tree)

Folhas armazenam dois dados


slot_load = carga reservada localmente
event_list = lista de ações que devem ser
executadas naquele intervalo de tempo

Nós armazenam dois dados


max_load = carga máxima dos seus filhos
block_load = carga mínima em todos os seus
filhos
TAST
Algoritmo de Admissão

2 passos



Varre a TAST em busca de espaço para a alocação do
recurso solicitado
Atualiza a TAST para refletir as mudanças
Caso a alocação não possa ser realizada, o
sistema oferece alternativas viáveis ao cliente



Manter a qualidade de serviço e tempo de início, mas
diminuir a duração
Manter o tempo de início e duração mas diminuir a
qualidade do serviço
Manter a qualidade de serviço e a duração, mas alterar o
início da reserva
Negociação
Escalonador de Recursos




Utiliza o conceito de classes de CPU para
classificar os processos conforme seu padrão
de processamento
Agenda os processos de todas as classes para
utilizar a CPU, procurando garantir os
contratos de QoS
Suporta processos com várias linhas de
execução (multi-threaded)
Se adapta dinamicamente a excessos (bursts)
e estouros (overruns) de processamento
Tipos de Garantia

O DSRT oferece 2 tipos de garantias:

Garantia Flexível

Garante o processamento reservado, mas pode
ser influenciada por interrupções de I/O e page
faults

Garantia Estatística

É definida uma porcentagem de excessos de
processamento (bursts) que terá agendamento
garantido de processamento
Classes de CPU

Os processos podem ser classificados
em 4 classes principais:




Tempo de Processamento Periódico
Constante (PCPT)
Tempo de Processamento Periódico
Variável (PVPT)
Utilização do Processador Constante e
Aperiódica (ACPU)
Eventos
Tempo de Processamento
Periódico Constante (PCPT)


Utilizada para aplicações que possuem
processamento constante durante período
fixo
2 parâmetros devem ser especificados




Período (P)
Tempo de Processamento de Pico (PPT)
A cada P é garantido PPT de processamento
Caso o processamento ultrapasse PPT, não há
garantias
Tempo de Processamento
Periódico Variável (PVPT)


Utilizada para aplicações que não possuem
processamento fixo em um determinado período de
tempo
4 parâmetros devem ser especificados






Período (P)
Tempo de Processamento de Pico (PPT)
Tempo de Processamento Mínimo (SPT)
Tolerância a Excessos (BT)
A cada P há garantia flexível de SPT e garantia
estatística de SPT + BT
Todo processamento que ultrapasse SPT + BT não é
garantido
Utilização do Processador
Constante e Aperiódica (ACPU)


Utilizada com aplicações que necessitem de
alguma porcentagem do processador, sem
período fixo
1 parâmetro deve ser especificado



Utilização do Processador no Pico (PPU)
É garantido PPU% do tempo da CPU
A cada iteração o processo deve especificar
seu próximo prazo
Eventos


A reserva é feita para apenas um período
2 parâmetros devem ser especificados



Período (P)
Tempo de Processamento de Pico (PPT)
É garantido PPT no período P
A classificação do processo pode ser feita
automaticamente!
Partições de Processamento

Requisitos de CPU são divididos em 3
partições:

Partição de Tempo Real


Partição de Estouro


Responsável por agendar as porções reservadas de CPU
Responsável por agendar os excessos (bursts) e estouros
(overruns) de processamento
Partição de Divisão de Tempo

Responsável por agendar os processos tradicionais de
divisão de tempo (time-sharing)
Estratégias de Adaptação


As aplicações definem se querem e qual o
método
2 estratégias principais

Média Exponencial


Calcula os valores de pico das duas últimas iterações e
com base em um fator calcula o valor de pico para a
atual
Estatística

Define-se quantos estouros (overruns) de processamento
podem ocorrer por iteração e o valor de pico é ajustado
utilizando-se este valor
Exemplos
Exponencial
Estatística
Interface de Programação


Chamadas de função disponíveis em
C++ e Java
Três fases



teste de processamento
reserva de recursos
execução
Teste de Processamento

probe (int period = 0)


probeEnd()


Inicia a fase de teste de processamento da aplicação. Se for
um processo periódico, deve indicar o tempo do teste.
Fim do teste de processamento
probeMatch(CpuReserve *cr)

Devolve os parâmetros de reserva (classe de CPU, período,
tempo de processamento de pico, etc.) mais apropriados
para o processo
Reserva de Recursos

reserve(CpuReserve* cr, int pid=0)
 Reserva os recursos descritos em cr para o processo de pid
pid

modify(CpuReserve* cr, int pid=0)
 Modifica os recursos do processo pid para o especificado
em cr

setAdaptStrategy(AdaptStrategy *as, int pid=0)
 Escolhe a estratégia de adaptação do processo pid

free(int pid=0)
 Libera os recursos reservados
Execução

start(timeval begin, int pid=0)
 Inicia a execução em tempo real do processo pid no tempo
futuro begin. Caso o tempo não seja especificado, é uma
reserva imediata.

yield()
 Marca o fim de uma iteração do processo. Através desta
chamada são detectados estouros (overruns) e falta
(underruns) de processamento.

stop(int pid=0)
 Pára temporariamente a execução em tempo real do
processo pid, permitindo que ele altere seus parâmetros de
reserva.
// Fase de teste
cpu.probe();
cpu.start();
for(int i=0; i<numProbeIterations; i++){
doJob();
cpu.yield();
}
cpu.probeEnd()
cpu.probeMatch(&reservation);
// Fase de reserva
CpuApi cpu;
cpu.reserve(reservation);
cpu.setAdaptStrategy(strategy);
// Fase de execução
cpu.start();
for(int i=0; i<numIterations; i++){
doJob();
cpu.yield();
}
cpu.free();
Implementação em UNIX


Escalonador deve ser executado com permissão de root
Agendamento das tarefas é feito através da troca das prioridades dos
processos
Prioridade
maior
Escalonador
2º maior
Processo TR
executando
...
Não usado
Time Sharing
qualquer
Qq processo TS
Tempo Real em
espera
menor
Processos TR
esperando
Tempo Real

Processo
Escalonador gasta duas trocas de contexto + algumas system calls
para mudança de prioridade dos processos
Implementação em NT



Implementação semelhante à do UNIX, mas o
Windows possui apenas 4 classes x 7 prioridades =
28 prioridades
No Windows entretanto, se um processo estoura seu
tempo de processamento, o temporizador pode
deixar de acordar o escalonador
Para o Windows, assume-se processos “bemcomportados”
Monitor



Utiliza um servidor LDAP
Um processo paralelo ao Escalonador
recebe informações dele e atualiza o
servidor LDAP
Um monitor remoto lê as informações
do servidor LDAP e mostra ao usuário
Cenário de Teste

Visualizador de mpeg mostrando um vídeo a





10 fps
8 e 4 fps
Compilador gcc compilando o visualizador de
mpeg
Programa calculando sen e cos
Programa que copia frames para um buffer
circular (consumidor de memória)