Upload
others
View
4
Download
0
Embed Size (px)
Citation preview
1César Ofuchi – [email protected]
Escalonamento
(Scheduling)
César Yutaka Ofuchi
(adaptado do prof. André Schneider de Oliveira/
prof. Hugo Vieira)
2César Ofuchi – [email protected]
Ciclo de Vida de Serviços
3César Ofuchi – [email protected]
Escalonamento de Processos
• Responsável por determinar qual tarefa deve ganhar o processador, possibilitando a execução de diferentes tarefas em sistemas monocore
• Gerenciamento das tarefas deve respeitar o compartilhamento de recursos e comunicação entre tarefas
• Escalonador deve escolher a tarefa de acordo com critérios pré-estabelecidos (prioridade, deadline,...), dentre os processos prontos (ready) para executar
• Preempção pode ser utilizada para retirar um processo em execução e colocar outro mais prioritário.
4César Ofuchi – [email protected]
Diagrama de Gantt
5César Ofuchi – [email protected]
Tipos de Tarefas
• Periodicidade permite a formulação de modelos analítico para prever e
garantir os tempos de computação dentro de intervalos aceitáveis.
•
• Tarefas aperiódicas e esporádicas devem ser transformadas em tarefas
periódicas, mesmo que isto conduza a situações de utilização do
processador muito pessimistas.
6César Ofuchi – [email protected]
Métodos de Escalonamento
• Não preemptivo/Cooperativo– Threads decidem voluntariamente quando parar
• Ex. First Come First Served
• Preemptivo– Serviço de uma tarefa pode ser suspenso temporariamente
em qualquer ponto e a qualquer instante.
• Prioridade fixa. Ex: “Round Robin”
• Prioridade variável. Ex: ”Earliest Deadline First”
Yield()
8César Ofuchi – [email protected]
Algoritmos de Escalonamento para tarefas periódicas
• Não preemptivo:
– First Come First Serve
• Preemptivo
– Prioridade Fixa:
• Round Robin
• Análise Monotônica
– Taxa/Rate (RMA) >Prioridade para períodos menores
– Prazo/Deadline (DMA) >Prioridade para prazos
menores
– Prioridade dinâmica:
• Earliest Deadline First – Deadline mais perto
• Least Laxity First – Menor tempo para cumprir tarefa
9César Ofuchi – [email protected]
First Come First Served- FCFS
• Escalonamento dinâmico não-preemptivo em que a ordem de execução dos serviços é determinada pela
ordem em que entram no estado PRONTO.
• Raramente utilizado em aplicações em tempo real, a não
ser como meio de desempate entre serviços de uma
mesma fila de prioridade em escalonadores mais
complexos.
10César Ofuchi – [email protected]
Round Robin (Time Slicing)
• Escalonamento dinâmico preemptivo para tarefas de mesma prioridade semelhante ao FCFS no tratamento da ordem de execução dos serviços.
• No entanto, cada serviço recebe o controle do processador por um intervalo de tempo máximo Tq.
• Se o serviço não terminar dentro do intervalo Tq, será preemptido e terá que aguardar o próximo intervalo para continuar.
• Serviços podem ceder voluntariamente o controle do processador (Yielding) antes do final do seu intervalo de tempo.
12César Ofuchi – [email protected]
Round Robin
• Desempenho fortemente influenciado por:– Tempo Tq
– Tempo de execução das tarefas
– Nº de tarefas ativadas
• Resultado final entre dois extremos se comparado ao FCFS– Semelhante: Tq ≥ tempo de execução da tarefa mais demorada
Cdemorada
– Ineficiência total: Tq ≤ tempo de execução do mecanismo de preempção (Tpreempção).
τ Cdemorada
τ1
Tq
τ2
Tpreempção
Tq
13César Ofuchi – [email protected]
Round Robin + Prioridades + CMSIS RTX
• Tarefas com maior prioridade executam até o
final de seu ciclo de vida (por ex. infinito)
• Caso seja necessário retirar a thread de
execução:– Ceder voluntariamente - Yield()- não funciona pois a tarefa
continua na vez de executar devido a prioridade
– Necessário forçar a thread a não fazer nada por meio de
delays ou aguardar recurso/eventos ou mudar sua prioridade.
14César Ofuchi – [email protected]
Earliest Deadline First
• Seleciona o serviço com prazo terminando mais cedo dentre o conjunto de serviços que estão no estado PRONTO.
• Não-preemptivo: o serviço selecionado executa até o final, até entrar no estado SUSPENSO/BLOQUEADO ou até entrar voluntariamente no estado PRONTO.
• Preemptivo: o serviço pode ser preemptido por outro serviço com prazo terminando mais cedo.
15César Ofuchi – [email protected]
Exemplo – EDF Preemptivo
EDF não-preemptivo não é adequado, devido a interferência de
serviços demorados com prazos longos em serviços recém-
chegados com prazos mais curtos
16César Ofuchi – [email protected]
Least Laxity First
• Tempo de relaxamento: diferença de tempo
entre o prazo efetivo e o prazo estimado do
serviço.
17César Ofuchi – [email protected]
Least Laxity First
• Prioridade determinada dinâmicamente, de modo que o serviço com menor tempo de relaxamento tenha a maior prioridade.
• Enquanto o serviço está no estado EXECUTANDO, seu prazo permanece inalterado.
• No entanto, quando está no estado PRONTO ou SUSPENSO/BLOQUEADO, seu prazo de termino estimado aumenta e portanto seu tempo de relaxamento diminui.
• Em algum momento no futuro será o serviço com maior prioridade.
18César Ofuchi – [email protected]
Least Laxity First
• Quando duas ou mais tarefas possuem tempos
de relaxamento muito próximos, acontece um
efeito do tipo “pingue-pongue”, causando alto
número de preempções que afetam
negativamente o desempenho.
• Adequado para escalonamento preemptivo
apenas (pelas mesmas razões do método EDF).
19César Ofuchi – [email protected]
Highest Priority First
• Determina a ordem de execução das tarefas
pela prioridade (pré-determinadas no projeto).
• Critérios:
– Importância e periodicidade das tarefas
• Prioridades estáticas pré-determinadas
– Análise Monotônica de Taxa - Rate (RMA)
• Prioridades maiores para serviços com períodos menores
– Análise Monotônica de Prazo – Deadline (DMA)
• Prioridades maiores para serviços com prazos menores
20César Ofuchi – [email protected]
Taxa de Utilização do Processador
• A taxa de utilização do processador em uma
tarefa é seu tempo de computação Ci dividido
pelo seu período Ti.
• Teoricamente, um conjunto de n tarefas é
escalonável se a soma das taxas de utilização
de todas as tarefas for menor ou igual a um:
𝑖=1
𝑛𝐶𝑖𝑇𝑖≤ 1
• Na prática, somente sob certas condições:– Serviços devem encaixar-se perfeitamente em todas as
combinações de fase entre ativações
21César Ofuchi – [email protected]
2
6+
3
12+
5
12= 1
Exemplo sem Prioridades
2/6
3/12
5/12
Taxa de
Utilização
1
22César Ofuchi – [email protected]
1
3+1
5+
5
11= 0,988
Exemplo com Prioridades (RMA)
1/3
1/5
5/11
Taxa de
Utilização
0,988
23César Ofuchi – [email protected]
Teorema 1 – Liu & Layland, 1973
• Seja um conjunto de n tarefas periódicas com
prazos iguais aos períodos e prioridades por RMA
em ambiente preemptivo.
• Liu & Layland (1973) estabelecem um limite
máximo U(n) para a taxa de utilização do
processador, que garante a escalonabilidade
deste conjunto de tarefas:
𝑖=1
𝑛𝐶𝑖𝑇𝑖≤ 𝑈 𝑛 = 𝑛 2 ൗ1 𝑛 − 1
24César Ofuchi – [email protected]
Comportamento de U(n)
n tarefas
Não escalonável
Incerteza
Escalonável
25César Ofuchi – [email protected]
Teorema 2 – Liu & Layland, 1973
• “Se um conjunto de tarefas periódicas e
independentes é ativado no mesmo instante, e
cada tarefa atende o seu primeiro prazo, então
todos os futuros prazos serão atendidos”.
• O teorema não condiciona o conjunto de
tarefas a RMA, sendo aplicável a qualquer
esquema de prioridades estáticas.
26César Ofuchi – [email protected]
Exercício para entrega APS
• Seja um conjunto de tarefas J1, J2 e J3, com os
seguintes períodos (Ti) e tempos de computação
(Ci):
• Os prazos das tarefas são iguais aos respectivos
períodos e suas prioridades atribuídas por RMA.
TarefasTempo de
computação (C) us
Período (T) us
J1 200 600
J2 300 1000
J3 600 2000
27César Ofuchi – [email protected]
Exercício para entrega APS
• Faça o escalonamento no intervalo de 0 a
6000us em intervalo de 100us.
• Pode-se afirmar que os períodos das tarefas são
harmônicos?
• Determine se este conjunto de tarefas é
teoricamente escalonável pelos seguintes
métodos:1. Taxa de utilização do processador
2. Rate Monotonic? Faça o escalonamento e verifique o
Limite U(n) do Teorema de Liu & Layland (1973) também.
Entregar o exercício em software de planilha como
Excel ou Calc (libre office) até dia S11 23/11, S12
23/12.
28César Ofuchi – [email protected]
Escalonamento com Bloqueio
• Tarefas não são independentes portanto escalonamentos estudados até aqui não são válidos.
• Recursos compartilhados– Mutexes
– Semáforos
– Sincronização
• Problemas– Impasse de bloqueio (deadlock)
– Inversão de prioridades
• Soluções– Protocolo de herança de prioridade
– Protocolo de teto de prioridade
30César Ofuchi – [email protected]
Inversão de Prioridades
No instante 17, a tarefa τ1 solicita a trava de S1 e, não
conseguindo, permanece bloqueada até que o recurso S1
seja liberado no instante 23.
S2 S2
S2
S1 S1
S1
31César Ofuchi – [email protected]
Inversão de Prioridades
S2 S2
S2
S1 S1
S1
O tempo de bloqueio do recurso S1 é igual a 6, sendo fortemente influenciado pela interferência das tarefas τ2 e τ3 no tempo de resposta
da tarefa τ4
t=6
32César Ofuchi – [email protected]
Mars Pathfinder – Inversão de Prioridade
• AGRAVANTE pois temporizador (watchdog) reiniciava o sistema
caso tg demorasse muito
Solução: HABILITAR flag de HERANÇA de PRIORIDADE!!
33César Ofuchi – [email protected]
Priority Inheritance Protocol
• Sob o Protocolo de Herança de prioridade, uma tarefa possui:
– uma prioridade básica atribuída estaticamente
– uma prioridade ativa.
• A prioridade ativa de uma tarefa durante a seção crítica
que detém a trava de um recurso é igual ao máximo entre
sua prioridade básica e a maior prioridade ativa do
conjunto de tarefas bloqueadas que esperam pela
liberação do recurso.
34César Ofuchi – [email protected]
Priority Inheritance Protocol
- No instante 17 a tarefa τ1 requisita a trava do recurso S1, que está bloqueado pela
tarefa τ4;
- Tarefa τ4 herda a prioridade da tarefa τ1 e passa a ser executada
- Tarefa τ4, retoma sua prioridade original após a liberação do recurso em questão
prioridade
S1
S2
35César Ofuchi – [email protected]
Priority Inheritance Protocol
• CMSIS RTOS utiliza este método para os mutexes
• O Protocolo de Herança de Prioridade não
previne impasses de bloqueio e além disso pode
levar à formação de cadeias de bloqueio.
36César Ofuchi – [email protected]
Priority Ceiling Protocol
• Extensão do PIP mas com regra sobre o acesso
aos recursos livres (para garantir que todos os
recursos necessários estão livres).
• É definido um teto (ceiling) de prioridade para
cada recurso igual à prioridade mais elevada de
entre as tarefas que o usam.
• Uma tarefa só pode tomar um recurso se este
estiver livre e se sua prioridade ativa for maior (>)
que o teto do sistema ou se detém a trava do
recurso que fixou o teto geral.
37César Ofuchi – [email protected]
Priority Ceiling Protocol – Definição do teto
S1 tem teto de prioridade igual a 4(utilizado nas tarefas τ1 e τ4)
S1
S2 S2 tem teto de prioridade igual a 4(utilizado nas tarefas τ1 e τ2)
38César Ofuchi – [email protected]
Priority Ceiling Protocol
No instante 13 a tarefa τ4 obtém a trava do recurso S1 e o
teto geral passa para o teto de prioridade desse recurso
S1
S2
S1
S1
39César Ofuchi – [email protected]
Priority Ceiling Protocol
No instante 15 a tarefa τ2 requisita a trava do recurso S2 e não consegue,
pois sua prioridade não é maior que o teto geral.
A prioridade ativa da tarefa τ4 passa para o máximo das prioridades ativas
das tarefas τ2 e τ4 (3), envolvidas com o recurso em questão.
S1
S1
40César Ofuchi – [email protected]
Priority Ceiling Protocol
No instante 17 a tarefa τ1 requisita a trava do recurso S1 e não consegue,
pois sua prioridade ativa não é maior que o teto geral;
A prioridade ativa da tarefa τ4 passa para o máximo das prioridades
ativas das tarefas τ1 e τ4, envolvidas com o recurso em questão
S1
41César Ofuchi – [email protected]
Priority Ceiling Protocol
No instante 19 a tarefa τ4 libera o recurso S1 e sua prioridade ativa volta
para a sua prioridade básica;
O teto geral passa momentaneamente para 0
S1
S1
42César Ofuchi – [email protected]
Priority Ceiling Protocol
Ainda no instante 19 a tarefa τ1 obtém a trava do recurso S1
O teto geral passa para o teto de prioridade do recurso em questão
S1
S1
43César Ofuchi – [email protected]
Priority Ceiling Protocol
No instante 20 a tarefa τ1 libera o recurso S1 e sua prioridade ativa
volta para a sua prioridade básica (neste caso, a mesma);
O teto geral passa momentaneamente para 0
S1
S1
44César Ofuchi – [email protected]
Priority Ceiling Protocol
Ainda no instante 20 a tarefa τ1 obtém a trava do recurso S2
O teto geral passa para o teto de prioridade do recurso em questão
45César Ofuchi – [email protected]
Priority Ceiling Protocol
O que acontece nos instantes 15 e 17 previne impasses de bloqueio!
Não é permitindo que outros recursos com teto de prioridade <= ao
teto geral (recurso S2 nesse exemplo) sejam travados.
46César Ofuchi – [email protected]
Resumo
• Escalonamento de tarefas periódicas/independentes
– Não preemptivo: First Come First Serve
– Preemptivo:
• Prioridade Fixa:
– Round Robin
– Análise Monotônica (Liu & Layland)
» Taxa/Rate (RMA) >Prioridade para períodos menores
» Prazo/Deadline (DMA) >Prioridade para prazos menores
• Prioridade dinâmica:
– Earliest Deadline First – Deadline mais perto
– Least Laxity First – Menor tempo para cumprir tarefa
• Escalonamento com bloqueio
– Problemas: Inversão de Prioridade/Deadlock
– Protocolo de Herança de Prioridade
– Protocolo de Teto de Prioridade
47César Ofuchi – [email protected]
Considerações Suplementares
• Escalonamento de tarefas Esporádicas /Aperiódicas
– Algumas técnicas:
• “Background Service” – Tarefas executadas quando
processador esta ocioso
• “Polling Server (PS)” – Tarefa periódica extra de baixa
prioridade usada como servidor de para as tarefas
aperiódicas
• “Deferrable Server”/“Sporadic Server”- Tarefa periódica
de alta prioridade para servir pedidos aperiódicos.
48César Ofuchi – [email protected]
Referências
• Luguesi, J. L., Ambiente de Apoio ao Ensino e
Aprendizado do Escalonamento em Sistemas em Tempo Real. Dissertação de Mestrado, UTFPR, 2006– Capítulos 2 e 3, especialmente
• Liu, C. L.; Layland, J. W., Scheduling Algorithms for
Multiprogramming in a Hard-Real-Time Environment.
Journal of the Association for Computing Machinery
20(1), pp. 46-61, 1973
• Sha, L.; Rajkumar, R.; Lehoczky, J. P., Priority
Inheritance Protocols: An Approach to Real-Time Synchronization. In IEEE Transactions on Computers
39(9), pp. 1175-1185, 1990
49César Ofuchi – [email protected]
Prática (pré-requisitos)
• Verificar se o arquivo RTX_Conf_CM.c está com OS_TICK correto e
RoundRobin habilitado em 5ms.
• Verificar se a configuração da library está em SWO (caso
contrário printf não funciona de forma correta).
50César Ofuchi – [email protected]
Prática (pré-requisitos)
• Adicione um novo grupo chamado
“examples_scheduling” para prática.
51César Ofuchi – [email protected]
Prática parte 1
Baixar arquivo example_scheduler.c
• Execute o programa e verifique seu funcionamento.– Verifique pelos printfs quanto tempo cada thread tem para
executar e desenhe um gantt manualmente.
– Altere o parâmetro OS_ROBINTOUT para 15 e verifique o que acontece.
– Faça o job1 entregar (Yield) a tarefa antes (como se elativesse menos tempo)
– Desabilite o OS_ROBIN e rode o programa, o que acontece? Qual o tipo de escalonamento utilizado? Como fazer o programa alternar entre as tarefas, implemente. Adicionar threadYield ou delay (o 1º é mais eficiente)
• Volte as configurações originais, mas troque o while(tC>0) no job1 por while(1) e aumente a prioridade do job1. O que acontece?– Tente o método Yield para entregar a tarefa.
– Tente o método osDelay para entregar a tarefa.
– Que diferença você nota?
52César Ofuchi – [email protected]
Prática parte 2
Baixar arquivo example_scheduler_mutex_isr.c
• Execute o programa e verifique seu
funcionamento.– No job3 faça com que o loop interno que imprime “crítico”
não seja preemptido.
– Qual a solução empregada?
• Coloque um breakpoint no código da ISR, rode o
programa e aperte o joystick aleatoriamente– A ISR tem que prioridade? Ela influencia nos printfs?
– Proteja a região crítica que imprime desabilitando/habilitando
as interrupções.