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.
The significance of RMS lies in its optimality and the existence of a simple schedulability test. It is proven to be an optimal static-priority scheduling policy. This means that if a set of tasks can be scheduled by any static-priority algorithm, it can also be scheduled by RMS. The schedulability of a task set under RMS can be determined using a utilization bound test. For a set of ‘n’ tasks, the total processor utilization ‘U’ is the sum of the execution time [latex]C_i[/latex] divided by the period [latex]T_i[/latex] for each task ‘i’: [latex]U = \sum_{i=1}^{n} \frac{C_i}{T_i}[/latex]. Liu and Layland proved that if this total utilization is less than or equal to a specific bound, [latex]U \le n(2^{1/n}-1)[/latex], then the task set is guaranteed to be schedulable (i.e., no deadlines will be missed). As ‘n’ approaches infinity, this bound converges to [latex]\ln(2) \approx 0.693[/latex]. This provides a sufficient, but not necessary, condition for schedulability. A more precise but complex test, called exact analysis or response time analysis, can also be used.
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
- avionics and flight control systems
- Automação industrial e robótica
- real-time signal processing
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.