Modified Rate-Monotonic Algorithm for Scheduling Periodic Jobs with Deferred Deadlines

O artigo trata de uma extensão do clássico algoritmo de Taxa Monotônica para o caso de tarefas com deadline maior que o período. O algoritmo descrito é semi-estático e orientado a prioridades. O artigo é estruturado em seis partes, que serão descritas a seguir.

A primeira parte é a introdução. Nela os autores apresentam os conceitos básicos de tarefas e escalonadores. Apresentam também a motivação por detrás da modificação: estender o deadline além do período é uma técnica utilizada em situações de sobrecarga transiente.

A segunda parte trata de uma caracterização melhor das tarefas com deadline maior que o período. São apresentados conceitos e fórmulas que serão utilizadas principalmente na prova formal das características do novo algoritmo.

A terceira parte apresenta o algoritmo em si. A modificação divide as requisições em dois grupos: as antigas e as atuais. Para a determinação das prioridades das requisições, foram apresentadas três regras:

1. Todas as requisições atuais possuem prioridade menor que as antigas;

2. As prioridades de todas as requisições em cada grupo seguem as regras do algoritmo de Taxa Monotônica;

3. Todos as requisições antigas da mesma tarefa são escalonadas e executadas de forma FIFO (First In, First Out).

É apresentada ainda uma forma de implementação desse algoritmo. Não entrarei em detalhes nesse post, mas deve-se dizer que sua implementação não requer grandes mudanças em um framework que utiliza escalonamento de Taxa Monotônica.

A quarta e a quinta parte tratam da optimalidade do algoritmo e análise de um caso especial de tarefas no qual o algoritmo não é ótimo, respectivamente. Os seguintes corolários são válidos (considere a diferença entre o deadline de uma tarefa e o seu período como δ e o tempo de processamento dessa tarefa como τ):

1. O algoritmo é ótimo para escalonar tarefas cuja diferença entre o deadline e o período é igual a ou maior que o maior período p₁ de todas as tarefas;

2. O algoritmo é ótimo para escalonar um conjunto de duas tarefas, contanto que δ₂ ≥ τ₂ e δ₁ ≥ p₁.

Entretanto, esse algoritmo não é ótimo no caso que o deadline de uma tarefa é o dobro do seu período, para todas as tarefas do conjunto.

A última parte apresenta uma forma de tratar o caso de tratar um conjunto de tarefas que possuas tarefas que necessitem ser completadas até o seu período e outras com deadline maior que seu período. Nesse caso, as tarefas pertencentes à primeira classe são consideradas urgentes e são tratadas como tarefas antigas, o que garante a elas uma prioridade alta.

Referências

SHIN, Wei Kuan, LIU, Jane W. S., LIU, Chung L. (1993) “Modified Rate-Monotonic Algorithm for Scheduling Periodic Jobs with Deferred Deadlines”.