Inversões de Prioridade Não
Limitadas em Sistemas de
Tempo Real e um Estudo das
Possíveis Soluções…
Paulo Felício
André Quinta
(Ufa !)
João Lopes
André Carvalho
Inversões de Prioridade



Uso frequente de algoritmos de escalonamento
por prioridade com preempção
Contenção no acesso a recursos partilhados por
tarefas de diferentes prioridades
Tarefas de elevada prioridade atrasadas pela
execução de tarefas de menor prioridade
Inversões de Prioridade

Na análise de escalonabilidade, cada tarefa tem
que acomodar, entre a activação e a deadline :
Tempo de execução
 Tempo de preempção
 Tempo de bloqueio


É necessário minimizar a duração da inversão de
prioridades, através do estudo da sua fonte,
melhorando a previsibilidade.
Fontes de Inversão de Prioridade
Semáforos e regiões críticas


Primitivas comuns de regulação do acesso a recursos a
recursos partilhados
Regiões críticas :




Segmentos de código que acedem a recursos partilhados
Executados de forma mutuamente exclusiva
Cada tarefa tem que obter o bloqueio do semáforo
pretendido antes de entrar na região crítica
É bloqueada caso não o consiga, ficando em fila de
espera
Será que é suficiente na limitação do atraso
máximo ?
Fontes de Inversão de Prioridade
Semáforos e regiões críticas
Prioridade
T1
T2
T3
Fontes de Inversão de Prioridade
Semáforos e regiões críticas
Prioridade
T1
T2
T3
Fontes de Inversão de Prioridade
Filas de espera
Q1
Q2
Q3
Primitivas de Sincronização
Inibição de Preempção
Como prevenir uma unbounded priority inversion ?

Inibir a preempção na execução de uma tarefa
Quando uma tarefa de prioridade inferior está dentro da sua região critica
não deixar que haja preempção por uma tarefa que tenha prioridade maior.
Isto pode ser feito desactivando a preempção durante a execução de todas as regiões
criticas.

Vantagens
 Implementação simples
 Eficaz desde que a duração da maior região crítica seja menor que a mais pequena
das deadlines
 Desvantagens
 Tarefas de prioridade alta podem ser bloqueadas pelas de prioridade baixa.

Primitivas de Sincronização
Inibição de Preempção
Quando existe preempção provocada por um dispositivo externo.

Podemos inibir a preempção através de Interrupts

O acesso com exclusão mútua será garantido se:
A inibição das interrupções for feita antes da execução da região critica.
Sendo activada, após execução da região critica.

Vantagens
 Não usa tempo de processador (ao desactivar e activar os interrupts).
 Pode ser usado por algoritmos de prioridades estáticas ou dinâmicas.
 Cada tarefa só pode bloquear uma vez, com a duração da maior das regiões
críticas das tarefas de menor prioridade.

Desvantagens
 Só deve ser usada com regiões criticas muito curtas.
 Corre-se o risco de perder interrupts quando a inibição dos interrupts não é curta.
Primitivas de Sincronização
Inibição de Preempção
Prioridade
T1
T2
T3
Primitivas de Sincronização
Inibição de Preempção
O Priority Ceiling Protocol Emulation
 A ideia é fazer um disable selectivo da preempção.

Inibe-se as possíveis preempções de tarefas com prioridade média, elevando-se
suficientemente a prioridade das tarefas de prioridade inferior.

A prioridade mais alta de todas as tarefas em contenção (que fechará o semáforo) será
copiada para um campo associado ao semáforo (esta prioridade designa-se Priority Ceiling)

Quando uma tarefa faz a chamada ao SO para abrir o semáforo fechado, o SO atribui à
tarefa a prioridade necessária para o abrir.

Apenas uma tarefa, de entre as que podem fechar o semáforo, pode estar na sua região critica
em qualquer momento.


Vantagens
 método mais eficaz na inibição das preempções
 Livre de Deadlock - só uma tarefa pode estar na região critica
Desvantagens
 Uma tarefa pode ser bloqueada por uma tarefa de menor prioridade (quando ocorre
auto suspensão das tarefas de menor prioridade)
Priority Inheritance Protocol
Protocolo de Herança de Prioridades
Prioridade
T1
T2
T3
A tarefa T3 começa a executar,
usando um determinado recurso
partilhado.
A tarefa T1, após ter iniciado, precisa
de aceder à região crítica “ocupada”
por T3. É bloqueada e dá a T3
prioridade P1  HERANÇA de
PRIORIDADE
Enquanto T3 executa, T2 fica pronta
mas é bloqueada por T3.
 T3 sai da região crítica e volta logo a
ter prioridade P3.
 T1 executa até ao fim, não deixando
T2 executar (P1>P2).
 T2 executa (P2>P3), e por último T3
termina.
Priority Inheritance Protocol
Protocolo de Herança de Prioridades
Nao consigo
aceder ao recurso.
Estou a ser
bloqueado de
forma directa!!!
Prioridade
T1
T2
T3
Até queria executar
mas tenho duas tarefas
à minha frente!!!
Quando T1 quer aceder ao recurso,
esta é bloqueada de forma directa
(Direct Blocking)
Quando T2 quer executar, está
impedida devido a T1 que por sua vez
também o está devido a T3. Diz-se
que T2 bloqueia de forma indirecta
(Push Through Blocking).
É óbvio que a duração do “Push Through Blocking” depende da região crítica.
Priority Inheritance Protocol
Protocolo de Herança de Prioridades
Este protocolo é “bom”, porque torna-se fácil
de compreeder e concretizar.
Por outro lado (Há sempre outro lado!!! )
Este protocolo não resolve problemas de:
 “Chained blocking” (bloqueio em cadeia)
 “Deadlock”
Priority Ceiling Protocol
Protocolo de Tecto de Prioridade
Elimina a possibilidade de ocorrer chained blocking e deadlocks
O tecto de prioridade de um semáforo ( S ) é a prioridade mais alta
de entre as tarefas que o podem fechar
Regras do PCP:
• Uma tarefa pode interromper outra de menor prioridade;
• Uma tarefa não pode entrar numa região crítica a não ser
que a sua prioridade seja maior do que os tectos de
prioridades dos semáforos fechados por outras tarefas;
• Uma tarefa que bloqueie outra de maior prioridade, herda
a sua prioridade (herança de prioridades)
Priority Ceiling Protocol
Protocolo de Tecto de Prioridade
Uma tarefa apenas pode fechar um semáforo quando todos os
semáforos de que essa tarefa vai precisar estejam livres.
Uma tarefa pode ser bloqueada por outra de menor prioridade que
use um semáforo que tenha um tecto pelo menos igual à sua
prioridade.
Priority Ceiling Protocol
Protocolo de Tecto de Prioridade
S0 = P1
A seguir vou
usar um recurso
que está
fechado, vou dar
a minha
prioridade
S1 = P1
S1 = P2
Mais à frente vou usar um recurso que
está fechado, não posso continuar
Alguém com maior prioridade interrompeu-me
Esta tarefa
tem a
prioridade
superior aos
tectos dos
semáforos
fechados
Priority Ceiling Protocol
Protocolo de Tecto de Prioridade
Pros and cons:
• Ao contrário do PIP, não há chained blocking nem deadlocks
• De concretização mais difícil, uma vez que são necessários
novos campos tanto para o TCB como para os semáforos
• É necessária uma programação mais cuidada por parte do
programador
Frase do dia:
“Priority Ceiling means that while a thread owns the mutex it
runs at a priority higher than any other thread that may
acquire the mutex.”
Bibliografia:
Artigo de Sadegh Davari, Lui Sha
"Sources of Unbounded Priority Inversions in Real-Time Systems and a
Comparativ Study of Possible Solutions"
Operating Systems Review, 26(2):110-120. ACM Press. April 1992.