Escalonamento de taxa monotônica (RMS)
O Rate-Monotonic Scheduling (RMS) é um algoritmo de escalonamento com prioridade estática para tarefas periódicas em um sistema de tempo real. Ele atribui prioridades com base na frequência da tarefa: quanto menor o período de uma tarefa (maior sua taxa), maior sua prioridade. O RMS é um algoritmo de prioridade estática ótimo, o que significa que, se qualquer algoritmo de prioridade estática puder escalonar um conjunto de tarefas, o RMS também poderá. A capacidade de escalonamento pode ser verificada por meio de um teste baseado em utilização.
O escalonamento Rate-Monotonic (RMS) é um pilar da teoria de sistemas de tempo real, introduzido em um artigo seminal de 1973 por Liu e Layland. Ele fornece um método simples, porém poderoso, para escalonar um conjunto de tarefas independentes, preemptíveis e periódicas em um único processador. O princípio fundamental é atribuir uma prioridade fixa a cada tarefa, inversamente proporcional ao seu período. Uma tarefa que precisa ser executada a cada 10 ms terá uma prioridade maior do que uma tarefa que é executada a cada 100 ms.
A importância do RMS reside em sua otimalidade e na existência de um teste de escalonabilidade simples. Está comprovado que ele é uma política de escalonamento de prioridade estática ótima. Isso significa que, se um conjunto de tarefas pode ser escalonado por qualquer algoritmo de prioridade estática, ele também pode ser escalonado pelo RMS. A escalonabilidade de um conjunto de tarefas sob o RMS pode ser determinada usando um teste de limite de utilização. Para um conjunto de n tarefas, a utilização total do processador U é a soma do tempo de execução Ci dividido pelo período Ti para cada tarefa i: U = ∑i=1n Ci/Ti. Liu e Layland provaram que se essa utilização total for menor ou igual a um limite específico, [latex]U le n(2^{1/n}-1)[/latex], então o conjunto de tarefas tem garantia de ser escalonável (ou seja, nenhum prazo será perdido). À medida que n tende ao infinito, esse limite converge para [latex]ln(2) approx 0,693[/latex]. Isso fornece uma condição suficiente, mas não necessária, para a escalonabilidade. Um teste mais preciso, porém complexo, chamado análise exata ou análise de tempo de resposta, também pode ser usado.
UNESCO Nomenclature: 1203
Ciência da Computação
Precursores
- teoria das filas
- pesquisa operacional
- primeiros trabalhos sobre algoritmos de agendamento de computadores
- desenvolvimento de sistemas operacionais de tempo compartilhado
Aplicações
- sistemas de controle de satélite
- aplicações de controle automotivo
- aviônicos e sistemas de controle de voo
- Automação industrial e robótica
- processamento de sinal em tempo real
Ideias de Inovação Potencial
Devido ao tráfego de bots de coleta de dados, atualmente superior a 40 mil por dia, este conteúdo é reservado aos membros da comunidade.
> Login < ou > Registrar < (100% gratuito) para acessar isso, assim como todo o restante do conteúdo e das ferramentas restritas.
Relacionado a: escalonamento monotônico por taxa, RMS, sistemas de tempo real, algoritmo de escalonamento, prioridade estática, tarefas periódicas, análise de escalonabilidade, limite de utilização, Liu e Layland, escalonamento ótimo.