Inversão de Prioridade e Herança de Prioridade

Inversão de prioridade é o que acontece quando a garantia central de um escalonador por prioridade, a de que a tarefa executável de maior prioridade sempre roda em seguida, acaba sendo violada na prática por uma tarefa que o escalonador considera de prioridade inferior. O escalonador em si não está com defeito; o problema é que “executável” e “bloqueada num lock” não são a mesma coisa que o escalonador pensa que são, e um lock segurado por uma tarefa de baixa prioridade pode deixar uma de alta prioridade presa esperando independentemente do que o escalonador de outra forma escolheria rodar.

O cenário de três tarefas

O caso clássico precisa de exatamente três tarefas: uma tarefa de baixa prioridade L adquire um mutex para proteger algum recurso compartilhado, e logo depois, uma tarefa de alta prioridade H tenta adquirir esse mesmo mutex e bloqueia, já que L ainda o está segurando. Até aqui isso é bloqueio comum e limitado: H simplesmente espera L terminar sua seção crítica e liberar o lock, o que deveria acontecer logo já que L é de baixa prioridade e recebe pouco tempo de CPU para começar. A inversão aparece quando uma terceira tarefa, M, de prioridade entre L e H, se torna executável durante essa espera: M não tem interesse algum no mutex, mas como M supera L em prioridade, o escalonador preempta L em favor de M, e L, a única tarefa realmente capaz de liberar o lock que H está esperando, não roda de novo até M terminar. H, nominalmente a tarefa de maior prioridade no sistema, acaba esperando por M indiretamente, uma tarefa com a qual não tem relação alguma e, por prioridade, nunca deveria estar bloqueada atrás.

Prioridade:  H > M > L

t0: L adquire o mutex
t1: H bloqueia no mutex (L o segura)
t2: M se torna executável, preempta L (M > L)
    -- H agora efetivamente espera atrás de M, apesar de H > M --
t3: M termina, L retoma, libera o mutex
t4: H finalmente adquire o mutex e prossegue

Sem M no quadro, a espera de H é limitada pelo tempo que a seção crítica de L normalmente leva; com M se tornando executável repetidamente (ou, no pior caso, um fluxo ilimitado de tarefas de mesma prioridade cada uma preemptando L brevemente por sua vez), a espera de H não tem limite algum, o que é exatamente o que separa contenção de lock comum de inversão de prioridade especificamente.

Herança de prioridade

Herança de prioridade fecha essa brecha fazendo com que o próprio lock, em vez do escalonador, ajuste a prioridade de quem quer que atualmente o segure: no momento em que H bloqueia num mutex que L segura, a prioridade efetiva de L é temporariamente elevada para igualar a de H, enquanto L continuar segurando esse mutex. Com L agora rodando na prioridade de H, M não pode mais preemptá-la, já que M não é mais de prioridade superior à tarefa que de fato segura o lock; L roda, termina sua seção crítica, libera o mutex, volta à sua prioridade original, e H adquire o lock logo em seguida. O limite na espera de H é restaurado para algo próximo do caso original, a duração da seção crítica de L, em vez de permanecer indefinido.

void mutex_lock(struct mutex *m) {
    struct task *waiter = current_task();
    if (m->owner && waiter->priority > m->owner->priority) {
        m->owner->effective_priority = waiter->priority;
        reschedule_if_needed(m->owner);
    }
    // ... bloqueia até adquirir ...
}

void mutex_unlock(struct mutex *m) {
    m->owner->effective_priority = m->owner->base_priority;
    // ... acorda um esperando, libera ...
}

Uma cadeia de locks aninhados torna isso recursivo em vez de um único ajuste: se a própria L bloquear num segundo mutex segurado por alguma outra tarefa enquanto roda na prioridade herdada de H, essa segunda tarefa herda a prioridade de H por sua vez, e assim por diante, já que caso contrário a mesma inversão simplesmente reapareceria um lock mais fundo na cadeia.

Custos e alternativas

Herança de prioridade não é de graça: toda aquisição de lock agora precisa comparar a prioridade de quem espera com a de quem atualmente segura e potencialmente propagar um ajuste, uma contabilidade que um spinlock ou mutex comum simplesmente não faz, e o caso de seguir a cadeia acima pode, num design patológico de locks aninhados, tocar um número genuinamente grande de tarefas para uma única operação de lock. Protocolos de teto de prioridade trocam parte desse custo de tempo de execução por um custo estático: todo lock recebe, de antemão, um teto igual à maior prioridade que qualquer tarefa que algum dia possa adquiri-lo teria, e uma tarefa que adquire o lock imediatamente roda nesse teto pela duração inteira, esteja ou não uma tarefa de prioridade maior realmente esperando ainda. Isso evita a contabilidade de propagação no momento da aquisição, já que a prioridade certa já é conhecida em vez de descoberta dinamicamente, ao custo de exigir que o conjunto completo de possíveis donos de todo lock seja conhecido antecipadamente, algo direto num sistema de tempo real com tarefas fixas e consideravelmente menos num kernel de propósito geral onde o mesmo mutex pode ser alcançável a partir de caminhos de código nem todos enumerados de antemão.

Notas de implementação

Inversão de prioridade não é uma preocupação hipotética levantada só em livros didáticos: os resets de software de 1997 do rover Mars Pathfinder foram eventualmente rastreados exatamente a esse cenário, uma tarefa de coleta de dados de baixa prioridade segurando um mutex de barramento compartilhado sendo preemptada por uma tarefa de comunicação de prioridade média, deixando faminta uma tarefa de gerenciamento de barramento de alta prioridade tempo suficiente para um watchdog timer concluir que o sistema havia travado e forçar um reset. A correção, uma vez identificada, foi habilitar herança de prioridade no mutex em questão, enviada como um patch de software para uma sonda já em Marte, o que é uma demonstração tão forte quanto existe de que isso é um bug de corretude com consequências reais, não um caso de canto teórico num artigo de escalonamento.

Referências

^ L. Sha, R. Rajkumar, e J. Lehoczky, “Priority Inheritance Protocols: An Approach to Real-Time Synchronization,” IEEE Transactions on Computers, 1990: o artigo original definindo herança de prioridade e o protocolo de teto de prioridade.
^ M. Jones, “What really happened on Mars Rover Pathfinder,” The Risks Digest, 1997: o relato escrito pelo próprio engenheiro sobre o incidente de inversão de prioridade do Pathfinder e sua correção em voo.

Ver também

Schedulers: a política baseada em prioridade cuja garantia o cenário deste artigo viola.
Synchronization: o mecanismo de mutex que uma tarefa de baixa prioridade segura no cenário acima, e onde a implementação de lock de um kernel de fato vive.