Agendadores De Tarefas

Question

Teve uma discussão interessante com alguns colegas sobre as melhores estratégias de agendamento de tarefas em tempo real, mas nem todos tiveram um bom entendimento do comum ou útil agendamento de estratégias.

Para a sua resposta, por favor, escolher uma estratégia e ir sobre ele em algum detalhe, ao invés de dar um pouco de informação sobre várias estratégias.Se você tiver algo a acrescentar para alguém descrição e ele é curto, adicione um comentário, ao invés de incluir uma nova resposta (se é longo ou úteis, ou, simplesmente, uma melhor descrição e, em seguida, por favor, utilize uma resposta)

• Qual é a estratégia - descrever o caso geral (suponha que as pessoas saibam que uma tarefa é a fila, semáforos, bloqueios e outros OS fundamentos de fora o agendador de si)
• O que é a estratégia otimizada para (tarefa de latência, eficiência, em tempo real, jitter, compartilhamento de recursos, etc.)
• É em tempo real, ou pode ser feita em tempo real

As estratégias atuais:

• Prioridade Com Base Preemptive
• Menor consumo de energia mais lenta do relógio

-Adam

Answer 1

Como descrito em um artigo intitulado Em Tempo Real de Agendamento de Tarefas para a Energia-Consciente Sistemas Embarcados, Swaminathan e Chakrabarty descrever os desafios em tempo-real de agendamento de tarefas em baixa potência (embedded) dispositivos com várias velocidades do processador e o consumo de energia perfis disponíveis.O algoritmo de agendamento eles de estrutura de tópicos (e é mostrado para ser apenas cerca de 1% pior do que uma solução ótima em testes) tem uma maneira interessante de agendamento de tarefas que eles chamam de o LEDF Heurística.

A partir do papel:

O baixo consumo de energia mais antigas primeiro prazo heurística, ou simplesmente LEDF, é um extensão do conhecido primeiros deadline first (EDF) algoritmo.O operação de LEDF é como segue:LEDF mantém uma lista de todos os lançado tarefas, o chamado "ready list".Quando as tarefas são liberadas, a tarefa com o mais próximo prazo é o escolhido para ser executados.É efectuada uma verificação para ver se a tarefa prazo podem ser atendidas por de executá-lo em baixa tensão (velocidade).Se o prazo pode ser atendida, LEDF atribui a baixa tensão tarefa e a tarefa é iniciada a execução.Durante a tarefa da execução, outros tarefas podem entrar no sistema.Estes as tarefas são considerados para ser colocado automaticamente no "pronto lista".LEDF novamente seleciona a tarefa com o mais próximo prazo para ser executada.Como desde que existem tarefas esperando para ser executado, LEDF não manter o pro- cessor ocioso.Este processo é repetido até que todas as tarefas tenham sido agendada.

E em pseudo-código:

Repeat forever {
    if tasks are waiting to be scheduled {
        Sort deadlines in ascending order
        Schedule task with earliest deadline
        Check if deadline can be met at lower speed (voltage)
        If deadline can be met,
            schedule task to execute at lower voltage (speed)
        If deadline cannot be met,
            check if deadline can be met at higher speed (voltage)
        If deadline can be met,
            schedule task to execute at higher voltage (speed)
        If deadline cannot be met,
            task cannot be scheduled: run the exception handler!
    }
}

Parece que programar em tempo real é um interessante e evolução problema tão pequeno, de baixa potência, dispositivos tornar mais onipresente.Eu acho que esta é uma área em que nós vamos ver a abundância de investigação e estou ansioso para se manter a par!

Answer 2

Comum em tempo real esquema de agendamento é a utilização de prioridade baseado no multitarefa preemptiva.
Cada tarefas é atribuída a um diferente nível de prioridade.
A tarefa de prioridade mais alta no pronto fila será a tarefa que executa.Ele será executado até que dá até a CPU (i.e.atrasos, esperas em um semáforo, etc...) ou uma tarefa de prioridade mais alta torna-se pronto para ser executado.

A vantagem deste esquema é que o projetista do sistema tem controle total sobre quais as tarefas que irá executar a prioridade.O algoritmo de agendamento também é simples e deve ser determinista.

Por outro lado, a baixa prioridade de tarefas pode ser fome, para a CPU.Isso poderia indicar um problema de design.