Algoritmos de Escalonamento de Tarefas
1/19
INTRODUÇÃO
Um sistema de tempo real é definido como um sistema em que a precisão e a
correcção finais dependem não só do resultado computacional, mas também do tempo
consumido para produzir esses resultados.
Hoje em dia encontramo-nos rodeados de sistemas de tempo real, desde simples
sistemas de controlo de uma linha de montagem até ao controlo dos sistemas de voo dos
aviões e futuramente no controlo das estações espaciais.
A maior parte dos sistemas baseiam-se em informação conhecida à priori –
sistemas estáticos – o que leva a elevados custos de produção e manutenção. A próxima
geração de sistemas de tempo real para situações críticas (hard real time) serão
desenvolvidas de forma a serem dinâmicas, previsíveis e flexíveis.
Quando temos que levar em linha de conta o tempo, como é o caso dos sistemas
de tempo real, um dos principais problemas que se nos depara consiste em “arrumar” o
conjunto de tarefas que compõe o sistema dentro de um determinado período de tempo.
O escalonamento de tarefas envolve a distribuição de recursos e tempo pelas
tarefas de forma a serem atingidos certos patamares de performances. Este é talvez o
assunto mais estudado no âmbito dos sistemas de tempo real e é também aquele que se
apresenta com mais possibilidades de aprofundamento visto que é um tema em
constante desenvolvimento.
A forma de medir a performance de um sistema de escalonamento depende do
propósito do sistema de tempo real. Isto faz com que haja um sem número de formas de
avaliar essas performances já que em cada situação temos que dar mais ênfase a um
determinado aspecto do sistema. Enquanto num algoritmo estático prevalece a
necessidade de diminuir o tamanho da tabela (horário), num sistema dinâmico temos
que dar mais importância à minimização do tempo de resposta.
Esta variedade de métricas que existem torna mais difícil a comparação de
algoritmos de escalonamento. Outro aspecto que torna esta comparação menos clara,
são as características das tarefas que cada sistema executa. As tarefas podem ser
associadas a tempos de computação, utilização de recursos, prioridades, precedências e,
como não podia deixar de ser, tempo. Se uma tarefa for periódica a sua frequência é
importante, se for esporádica então dá-se importância ao tempo limite de execução
(deadline).
Do que vimos até agora podemos concluir que uma das principais características
de um sistema de tempo real é a previsibilidade. A análise do escalonamento tem que
Algoritmos de Escalonamento de Tarefas
2/19
ser feita de modo a prever se o conjunto de tarefas a escalonar vai ou não cumprir o
tempo limite de execução. Aparecem assim vários paradigmas do escalonamento que
dependem de :
•
Se um sistema faz ou não a análise do escalonamento.
•
Em caso afirmativo, este é estático ou dinâmico?
•
O resultado da análise produz uma tabela na qual são indicadas todas as
tarefas a executar?
Baseado-nos nestes pontos podemos identificar os seguintes tipos de algoritmos :
•
Algoritmos estáticos geridos por uma tabela – Estes algoritmos são
estáticos ou seja, não há alterações ao longo da execução, e as tarefas a
executar
estão
indicadas
numa
tabela
que
o
algoritmo
consulta
constantemente.
•
Algoritmos estáticos preemptivos – aqui a diferença para o anterior reside na
inexistência de qualquer tabela. Durante a execução as tarefas são executadas
começando pela de maior prioridade.
•
Algoritmos dinâmicos planeados – ao contrário dos anteriores aqui o
algoritmo não executa todas as tarefas que chegam ao processador, executa
apenas aqueles que é possível concluir dentro do prazo.
•
Algoritmos dinâmicos de “melhor esforço” – nestes algoritmos não se
analisa a executabilidade da tarefa, o sistema tenta apenas cumprir todos os
deadlines, pode por isso acontecer que uma tarefa seja abortada durante a
execução.
Algoritmos de Escalonamento de Tarefas
3/19
STATIC CYCLIC SCHEDULING
(Escalonamento Estático Cíclico - EEC)
Esta é talvez a mais antiga forma de escalonamento. É um tipo de escalonamento
off-line, que só suporta tarefas periódicas.
O padrão de execução das tarefas é armazenado num calendário, após ter sido
determinado por um algoritmo configurador. Durante a execução o programa de
escalonamento segue à risca a informação contida no calendário.
A primeira questão a surgir prende-se com o tamanho da tabela e a quantidade de
memória que ela irá ocupar, pois com o crescente número de vezes que as tarefas se
executariam, ela tornar-se-ia gigantesca. Na realidade não é isto que se verifica. O que
acontece é que o programa percorre toda a tabela e quando atinge o seu fim regressa ao
início do calendário dando assim origem ao nome de escalonamento cíclico. O período
de repetição é dado pelo mínimo múltiplo comum (m.m.c.) entre os períodos de cada
uma das tarefas ( T= mmc (ti ) ). Vai-se apresentar de seguida um cronograma que
demonstra do escalonamento de cinco tarefas utilizando este tipo de algoritmo :
Tarefa
T
C
A
25
10
B
25
8
C
50
5
D
50
4
E
100
2
Legenda :
T : Período
C : Tempo de computação
Algoritmos de Escalonamento de Tarefas
4/19
Uma vez que o algoritmo de execução é tão simples, a análise do cumprimento
dos deadlines também efectuada de uma forma simples. É apenas necessário percorrer o
calendário para verificar que os requisitos temporais de cada tarefa são obedecidos. O
âmago da questão prende-se então com o algoritmo de escalonamento off-line utilizado
para gerar a tabela.
Podemos encontrar vários algoritmos que efectuam essa operação, mas antes de
entrarmos nesse assunto temos de encontrar um modelo que represente este sistema de
escalonamento.
Não é necessário criar restrições ao modelo, estas surgem das limitações do
algoritmo e devidas ao escalonamento estático.
Uma vez que a execução das tarefas é pré-planeada só podemos permitir tarefas
periódicas, pois as esporádicas seriam de difícil tratamento e ocupariam mais tempo do
aquele necessário para a sua execução - o seu tratamento seria feito através de polling, o
que faria aumentar o tempo de execução (polling+execução ).
Outra limitação diz respeito ao tamanho da tabela. Esta não pode ocupar muito
espaço de memória uma vez que esta é um recurso muito limitado. A tabela deve ser
percorrida no mais pequeno período de tempo possível de forma que o regresso seu ao
início seja feito sem introduzir estagnações na execução.
Como vimos anteriormente o período mínimo de execução das tarefas é-nos dado
através do conceito de mínimo múltiplo comum do período das tarefas em questão. Esta
abordagem pode levar à obtenção de períodos de execução muito superiores ao
necessário e consequentemente a um calendário maior. A forma normalmente utilizada
para resolver esta situação consiste em alterar o valor dos períodos das tarefas –
normalmente diminuí-los – de forma a torná-los múltiplos simples uns dos outros,
tornando assim a tabela mais pequena. Em contrapartida este processo provoca o
aumento da utilização do processador e torna os períodos de execução das tarefas mais
pequenos que o necessário.
O algoritmo construtor da tabela é avaliado pela sua performance. Um modelo
simples (tarefas periódicas e independentes) pode ser facilmente resolvido através deste
tipo de escalonamento, mas podemos criar um modelo mais complexo introduzindo o
conceito de partilha de dados por duas tarefas. Neste caso o algoritmo tem que garantir a
execução de uma tarefa, que esteja a aceder a esses dados,
interrupção.
não permitindo a sua
Algoritmos de Escalonamento de Tarefas
5/19
ESCALONAMENTO DE PRIORIDADES FIXAS.
- Escalonamento “RATE MONOTONIC”.
Este tipo de escalonamento começou a ser desenvolvido no início da década de
70, principalmente a partir do aparecimento de um artigo da autoria de C. L. Liu e J. W.
Layland.
No escalonamento de prioridade fixa o controlador do processo tem que garantir
que é a tarefa de prioridade mais alta que está a ser executada em qualquer altura.
Basicamente o funcionamento pode descrever-se da seguinte forma :
Se tivermos uma tarefa de baixa prioridade a ser executada, no
momento em que chaga uma tarefa de prioridade mais alta a execução
da primeira é interrompida para dar lugar à exe cução da outra
(preempção). Se durante a execução desta tarefa por pedida a
execução de outra de prioridade intermédia o processador continua a
executar a tarefa de prioridade mais elevada e só depois de a terminar
é que vai iniciar a execução da tarefa de prioridade intermédia.
A tarefa de prioridade reduzida será executada no fim e só apenas
se não aparecer não nenhuma de prioridade mais elevada.
A análise de um algoritmo de escalonamento requer um modelo onde se
consideram os aspectos mais relevantes para o comportamento do sistema. No estudo
deste algoritmo vamos considerar os seguintes aspectos para efectuar a pretendida
modelização :
- Todas as tarefas são periódicas.
- Os períodos são iguais aos tempos limite (deadlines).
- As tarefas não podem autobloquear-se ou auto-suspender-se.
Outra consideração que devemos efectuar consiste no modo como as prioridades são
determinadas. Neste caso quanto menor for o período da tarefa maior será a sua
prioridade, ou seja estas são determinadas de acordo com o período (RATE
MONOTONIC).
Outros aspectos levados em consideração no desenvolvimento deste tipo de
escalonamento, embora desnecessários, foram a assumpção que as tarefas tinham que
Algoritmos de Escalonamento de Tarefas
6/19
ser periódicas e que os tempos de execução das tarefas deveriam ser constantes.
Resumindo, este algoritmo efectua um escalonamento preemptivo e de prioridades
fixas.
Como podemos verificar se um conjunto de tarefas é escalonável ?
Uma possibilidade de verificar a escalonabilidade de um conjunto de tarefas pode
ser através da utilização do seguinte teste :
(
)
 Ci 
1
 ≤ n 2 n − 1
i =1  i 
n
∑  T
n à n.º de tarefas a
escalonar
Mas a análise efectuada através desta expressão não é exacta. A situação da
desigualdade não se verificar não significa que as tarefas não sejam escalonáveis.
Vai-se apresentar de seguida um exemplo demonstrativo da falibilidade deste
método :
Considere-se o seguinte conjunto de tarefas :
TAREFA
T
D
C
PRIORIDADE
A
52
52
12
BAIXA
B
40
40
10
MÉDIA
C
30
30
10
ALTA
Através do cálculo do somatório indicado na expressão obtemos uma taxa de
utilização (U) de 81.41%. Calculando o segundo membro da inequação chegamos ao
valor 77.98%. concluí-se então que, segundo este teste, as tarefas não são escalonáveis
podendo verificar-se falhas no cumprimento dos deadlines. No entanto estas tarefas são
escalonáveis, pois se todas as tarefas cumprirem os prazos na situação mais difícil
(invocação simultânea de todas as tarefas) então os deadlines serão cumpridos. É esta
situação que se apresenta de seguida :
Algoritmos de Escalonamento de Tarefas
7/19
Invocação
Fim de execução
Preempção
Como se verifica conseguiu-se efectuar o escalonamento de todas as tarefas –
todas cumprem os deadlines – apesar do teste de escalonamento indicar o contrário.
- Análise Exacta.
Em 1986 dois investigadores – Mathai Joseph e Paritosh Pandya –
desenvolveram um modelo de análise exacta do algoritmo de escalonamento que foi
referido previamente.
Neste modelo foi introduzido o conceito de tempo de resposta de uma tarefa na
pior situação, ou seja o tempo necessário para levar a cabo uma tarefa na pior das
hipóteses.
Uma vez calculado este tempo o teste para verificar a possibilidade de escalonar
um determinado conjunto de tarefas é simples. É apenas necessário que o tempo de
resposta do pior caso seja inferior ao tempo limite ( deadline ).
Com isto podemos eliminar duas restrições do escalonamento através de
prioridades fixas que eram a necessidade dos períodos das tarefas serem iguais aos
tempos limite e a incapacidade de lidar com tarefas esporádicas ( não-periódicas ). A
primeira verifica-se porque, como é sabido, podemos comparar o tempo de resposta na
pior situação com outro valor e verificar se o primeiro é suficientemente pequeno de
maneira a ser possível escalonar as tarefas. Quanto às tarefas esporádicas este modelo
lida com elas com relativa facilidade. Como já vimos anteriormente uma tarefa
Algoritmos de Escalonamento de Tarefas
8/19
esporádica é aquela que é provocada por um acontecimento atípico ao processo. No
algoritmo apresentado inicialmente a uma tarefa deste género seria atribuído um
deadline elevado ou um período muito pequeno o que resultaria, aquando da análise das
tarefas, numa impossibilidade de efectuar o seu correcto escalonamento, o que na
realidade não era verdade, já que este podia ser realizado.
Vai-se de seguida analisar a expressão que caracteriza este modelo :
Ri = C i +
 Ri 
∑  Cj
∀ j∈hp (i )  T j 
hp(i) é o conjunto de
tarefas de prioridade
superior à de i.
x
é a função tecto
que nos dá o inteiro mais
pequeno maior ou igual
a x.
Esta expressão lança logo à partida a dúvida da sua resolução, uma vez que a
incógnita ( Ri ) aparece em ambos os membros da equação.
A resolução deste problema passa pela criação de uma relação recursiva, onde
uma iteração serve para calcular valores de Ri que respondam à equação. O valor que
interessa é o mais pequeno.
Podemos então transformar a equação de forma a obtermos o seguinte :
Rin +1 = C i +
 Rin 
∑  Cj
∀ j ∈hp ( i )  T j 
O termo Rin+1 é a (n+1)-ésima aproximação ao pior tempo de resposta Ri.
Podemos ver facilmente que as aproximações vão sendo cada vez maiores até que o
resultado da iteração se torne convergente ou exceda algum limite. As iterações são
iniciadas com qualquer valor menor ou igual que Ri, por exemplo Rio =02 .
Através desta análise o valor de Ri só é válido se for menor ou igual ao período
dessa tarefa, isto porque se o tempo de resposta for maior que o período então uma
tarefa i poderia ser atrasada devido a uma invocação prévia de si mesma. Quer isto
também dizer que em cada tarefa o tempo limite tem que ser menor ou igual ao período.
Vamos agora aplicar esta análise ao conjunto de tarefas que já tínhamos referido
anteriormente :
Algoritmos de Escalonamento de Tarefas
TAREFA
A
B
C
9/19
T
52
40
30
D
52
40
30
C
12
10
10
Primeiro que tudo temos que definir as prioridades que vamos atribuir às tarefas.
Uma vez que estamos a caracterizar o método rate monotonic vamos utilizá-lo para esse
efeito. Desta forma a tarefa de maior prioridade será a C, seguida da B e finalmente a
tarefa A.
Vamos calcular RA primeiro. O conjunto de tarefas de prioridade superior a A e
formado por B e C. Assim as aproximações serão dadas por :
 R0 
R0 
R 1A = C A +  A  C B +  A C C = C A = 12
 TB 
 TC 
 12 
 12 
R A2 = C A +  C B +  C C = 32
T B 
 TC 
 32 
 32 
R 3A = C A +  C B +  C C = 42
T B 
 TC 
 42 
 42 
R A4 = C A +  C B +  C C = 52
T B 
 TC 
R 5A = 52
como se pode verificar a partir da quinta aproximação os resultados começam a
convergir, por isso RA=52.
Seguindo o mesmo processo obtemos RB=20 e RC=10.
Então podemos acrescentar à tabela inicial uma coluna com os piores tempos de
resposta de cada tarefa :
TAREFA
A
B
C
T
52
40
30
D
52
40
30
C
12
10
10
R
52
20
10
Algoritmos de Escalonamento de Tarefas
10/19
Como se pode ver na tabela anterior este conjunto de tarefas é escalonável, o que
vem contradizer o método inicial (Liu e Layland).
Este tipo de aproximação serve perfeitamente, por enquanto, os nossos propósitos.
É-nos possível alcançar os três objectivos a que nos propomos sempre que desejamos
efectuar um escalonamento de um dado conjunto de tarefas (configuração, análise e
execução). A configuração consiste em determinar as prioridades das tarefas (neste caso
menor período => maior prioridade). Até agora vimos dois exemplos de análise, o teste
proposto no estudo inicial de Liu e Layland e a análise exacta que acabámos de expôr.
Finalmente a execução consiste em realizar a tarefa de maior prioridade que esteja em
fila de espera.
-Deadline Monotonic vs Rate Monotonic.
No modelo inicial rate monotonic verificámos que para ser escalonável, todas as
tarefas de um sistema tinham de cumprir a seguinte condição :
à O período de uma tarefa tinha de ser igual ao seu deadline.
Mas como vimos anteriormente, o cálculo do pior tempo de resposta ( R )
permite-nos ter tempos diferentes para essas características.
Como se pode verificar facilmente, um algoritmo rate monotonic não é o melhor
para uma situação em que temos D<=T. a uma tarefa urgente mas pouco frequente
continua a ser atribuída uma prioridade baixa uma vez que o período ( T ) é elevado e
provavelmente não irá cumprir o seu deadline.
Aparece assim um outro algoritmo de ordenamento de tarefas , o deadline
monotonic, que tal como o próprio nome indica atribuí a prioridade mais alta à tarefa
com menor deadline. Este sistema é o melhor para o caso em que D <= T.
Algoritmos de Escalonamento de Tarefas
11/19
- Partilha de recursos, bloqueamento de tarefas.
Uma das restrições existentes no modelo inicial de escalonamento era que as
tarefas não podiam ser bloqueadas ou suspenderem-se a si próprias. Isto tornava a
partilha de recursos, principalmente dados, muito difícil.
Podemos recordar-nos do algoritmo de escalonamento estático cíclico, onde
vimos que tínhamos que limitar o acesso aos dados pelas tarefas. Chamámos a isto o
problema da concorrência.
Uma das formas de resolver esta situação consiste na criação de semáforos. Os
semáforos são um conceito introduzido por Edsgar Djikstra em 1960. Servem para
regular o acesso à informação e aos recursos por parte das tarefas, impedindo o acesso
de uma tarefas a essa informação após outra ter dado indicação que está a aceder à
mesma.
Uma vez activado o semáforo, a tarefa é executada dentro de uma secção crítica.
A tarefa que chegou no fim só pode aceder aos dados ou recurso após a primeira tarefa
ter desactivado o semáforo.
O problema dos semáforos reside aqui. É que uma tarefa pode tentar aceder a uma
determinado recurso e este já ter sido bloqueado por outra tarefa de menor prioridade,
fazendo com que a tarefa mais prioritária fique retida enquanto o semáforo não for
desactivado. Vamos apresentar um exemplo.
Consideremos o seguinte conjunto de tarefas :
TAREFA
A
B
C
T
D
50
10
500 500
3000 3000
C
5
250
1000
Admita-se que as tarefas A e C partilham um conjunto de dados e que cada uma
requer um tempo de computação para aceder aos dados de 1ms. Um semáforo s controla
o acesso à informação partilhada.
Considere-se também que a tarefa C está a ser executada e activa o semáforo s no
instante t. após C ter activado o semáforo a tarefa A é iniciada, e como tem prioridade
mais alta começa a ser executada. Um pouco mais tarde - instante t+2 – a tarefa B é
invocada, mas como não tem a prioridade mais alta não é executada.
Algoritmos de Escalonamento de Tarefas
12/19
No instante t+3 a tarefa A precisa de aceder aos dados que partilha com C e tenta
activa s, o que não consegue porque a tarefa C já o activou. Nesta altura A bloqueia à
espera que o semáforo seja desactivado.
Nesta situação a tarefa que tem mais prioridade é a B, que necessita de 250ms
para ser executada, terminando de o ser no instante t+253, então a tarefa C torna-se a de
maior prioridade e é executada. No instante t+254 a tarefa C desbloqueia o semáforo e a
tarefa A começa a ser executada, mas já sem cumprir o seu deadline.
O processo descrito acima pode ser ilustrado pela seguinte figura :
A tarefa que atrasa a execução da A é a B apesar de esta ter prioridade inferior.
Este efeito é conhecido como INVERSÃO DE PRIORIDADES e verifica-se quando uma
tarefa de menor prioridade atrasa a execução doutra de prioridade superior. As
consequências poderiam ser mais nefastas, no caso de existirem mais tarefas entre A e C
que viriam atrasar ainda mais a tarefa de maior prioridade.
Pelo que vimos até agora os semáforos apenas lançaram o caos no escalonamento
das tarefas. É aqui que temos que introduzir um outro conceito que nos resolverá o
problema, a HERANÇA DE PRIORIDADES.
É notório que quando A tenta aceder à informação “guardada” por s, mas não
consegue visto este estar “trancado” por C, a execução desta última torna-se urgente
pois contribuí directamente para o atraso de A.
Por isso, porque não atribuir, momentaneamente, a prioridade de A a C por forma
a apressar a sua execução. Vejamos o que acontece.
Algoritmos de Escalonamento de Tarefas
13/19
No instante t a tarefa C acede ao semáforo s. Neste momento a tarefa A é activada
e começa a ser executada. No instante t+2 B é invocada, mas não é executada pois não é
a tarefa de maior prioridade. No instante t+3 a tarefa tenta “trancar” o semáforo mas não
o consegue porque C já o fez, então A é bloqueada e C herda a sua prioridade, o que a
torna a tarefa de maior prioridade começando assim a ser executada.
No instante t+4 ela termina de aceder aos dados e “destranca” s. Aqui a tarefa C
adquire a sua prioridade normal e A começa a ser executada acedendo aos dados
partilhados e fechando o semáforo. A tarefa A termina a sua execução no instante t+9
cumprindo o seu tempo limite.
O processo é demonstrado na figura seguinte.
t+9
t+9
No entanto continua a verificar-se um problema que é a possibilidade de acontecer
uma situação de deadlock, que é o equivalente a tempos de resposta infinitos, para o
pior caso.
Podemos ilustrar o caso da seguinte forma, utilizando dois semáforos (s1 e s2 ).
No instante t a tarefa C bloqueia s1 , seguidamente a tarefa A bloqueia s2 e tenta
bloquear s1 o que não consegue pois este fora bloqueado pela tarefa C. Aqui a tarefa A é
suspensa e a C herda a prioridade de A recomeçando a execução.
Nesse instante a tarefa C tenta aceder a s2 , mas não consegue pois este já foi
bloqueado por A. Neste caso atinge-se uma situação em que nenhuma tarefa pode ser
executada – deadlock.
Algoritmos de Escalonamento de Tarefas
14/19
O problema pode ser resolvido através da utilização de um algoritmo que não se
ressinta do problema da inversão de prioridades e do deadlock. Esse algoritmo é o
PRIORITY CEILING que vamos apresentar de seguida.
- Protocolo Priority Ceiling.
Este protocolo é relativamente recente (1987) e vem colocar algumas restrições à
forma de bloqueio e libertação dos semáforos. A primeira refere-se à impossibilidade de
uma tarefa ocupar um semáforo entre invocações, ou seja quando termina a execução de
uma secção crítica tem que libertar todos os semáforos. Quanto à segunda restrição
refere-se à forma de bloqueio e libertação dos semáforos, que deve ser feita de forma
piramidal, ou seja – considerando dois semáforos – se o bloqueio for feita da forma
s1 às2
a libertação deve ser feita na ordem inversa e nunca na mesma ordem do
bloqueio.
O protocolo define um determinado período limitado de tempo (de computação)
para a execução da secção crítica em que uma tarefa i ocupa o semáforo. Este assume,
também, que a tarefa i pode bloquear semáforos de um determinado conjunto conhecido
inicialmente ( uses(i) à conjunto de semáforos de i).
Este protocolo baseia-se no conceito de tecto de prioridade, que é a máxima
prioridade de entre as tarefas que usam um determinado recurso com um semáforo
afecto. Por outras palavras podemos dizer que tecto de prioridade é a prioridade da
tarefa de maior prioridade que usa um determinado semáforo.
O protocolo consiste no seguinte, a prioridade dinâmica de uma tarefa é o maior
valor entre a sua prioridade e a das tarefas que ela bloqueia, assim uma tarefa só pode
utilizar um recurso se a sua prioridade dinâmica for maior que o tecto de prioridade de
todos os recursos em uso por outras tarefas, ou seja uma tarefa i só pode bloquear um
semáforo se a sua prioridade for superior às prioridades tecto de todos os semáforos já
bloqueados. Se esta condição não se verificar então a nossa tarefa inicial é bloqueada no
semáforo.
Se o semáforo já está bloqueado, a tarefa i não o pode bloquear pois a sua
prioridade não pode ser maior que o tecto de prioridade do semáforo. Quando a tarefa i
bloqueia o semáforo a tarefa que o ocupa presentemente herda a prioridade da tarefa i.
Algoritmos de Escalonamento de Tarefas
15/19
Este protocolo tem prioridades interessantes, tais como a inexistência de deadlock,
uma tarefa i só é atrasada, no máximo, uma vez por uma tarefa de menor prioridade em
que este atraso é função do cumprimento da secção crítica.
- Protocolo de Herança Imediata.
O protocolo anterior é talvez o mais difícil, tanto de entender como de aplicar. O
algoritmo escalonador tem que verificar constantemente qual é a tarefa que está
bloqueada, em que semáforo e quais foram as prioridades herdadas. Do mesmo modo o
algoritmo perde muito tempo a verificar se uma tarefa pode bloquear um semáforo.
Há um protocolo que se baseia no mesmo principio (pior tempo de resposta) que é
o protocolo de HERANÇA IMEDIATA. Este protocolo tem o mesmo modus operandi
que o PRIORITY CEILING, mas tem um comportamento em tempo real diferente.
Basicamente o seu comportamento é o seguinte :
Quando uma tarefa i pretende bloquear um semáforo esta modifica de imediato a
sua prioridade para o maior valor entre a sua prioridade e a prioridade tecto do
semáforo. Quando a tarefa desbloqueia o semáforo o valor da sua prioridade regressa
ao valor inicial.
É fácil de perceber porque é que a tarefa i só é atrasada, no máximo, por uma
tarefa de menor prioridade, tal como no protocolo anterior :
Não pode haver duas tarefas de baixa prioridade que bloqueiem dois semáforos
com tectos superiores ao da tarefa i, isto porque uma delas terá herdado, imediatamente,
a prioridade mais alta, e como tal a outra tarefa não pode ser executada e assim bloquear
outro semáforo.
Verifica-se também que não há necessidade de bloquear e desbloquear o
semáforo, pois este não pode estar bloqueado quando a tarefa i o tenta fazer, pois então
haveria outra tarefa de prioridade superior à de i a ser executada e e assim esta não o
poderia ser, não tentando então bloquear o semáforo.
Como a herança de prioridades é imediata a tarefa i é bloqueada, no máximo,
antes de começar a ser executada, isto porque se uma tarefa de prioridade mais baixa
retiver o controlo de um semáforo que possa bloquear a tarefa i então esta terá herdado
uma prioridade superior à de i e quando esta for invocada não começa a ser executada
imediatamente esperando que a tarefa de prioridade mais baixa acabe de ser executada,
Algoritmos de Escalonamento de Tarefas
16/19
nesse momento não haverá semáforos que travem a progressão da tarefa “i” e esta pode
ser executada sem entraves, a não ser que seja desalojada por outra de maior prioridade.
Esta propriedade de herança imediata é muito útil quando é necessário
implementar um algoritmo escalonador.
Em vários sistemas operativos a concorrência é controlada à custa da actuação de
interrupções. Este protocolo funciona da mesma maneira, apenas foram substituídas as
interrupções por tarefas.
IMPLEMENTAÇÃO DE ESCALONADORES DE PRIORIDADE FIXA .
Introdução
Como vimos anteriormente, através das equações desenvolvidas, não são
permitidas alterações de “comportamento” pelo escalonador. Vimos, por exemplo, que
essas equações não prevêem custos de implementação do escalonamento.
Neste capítulo descrevem-se duas maneiras de implementar um escalonamento de
prioridades fixas de forma a permitir alterações de comportamento dessas
implementações.
Escalonamento por acontecimentos
Neste tipo de implementação criam-se duas filas, uma, de execução, é ordenada
por prioridade das tarefas, a outra , de espera, que é ordenada pelo tempo que uma
tarefa pretende demorar até ser libertada.
Quando uma tarefa executa uma instrução de espera, o algoritmo retira-a da fila
de execução e coloca-a na fila de espera. Após terminar o transporta da tarefa entre as
filas, o algoritmo actua uma interrupção da CPU que inicializa um temporizador, o qual
irá avisar o algoritmo quando for altura de executar a tarefa que se encontra à cabeça da
fila de espera.
Quando a interrupção do temporizador é activada todas as tarefas com tempos de
libertação iguais ou menores que o tempo da interrupção são transferidos para a fila de
execução.
Algoritmos de Escalonamento de Tarefas
17/19
O atraso do escalonador pode ser calculado tendo em conta que o factor de
bloqueamento para todas as tarefas inclui o tempo de processamento da instrução de
espera. Este período de processamento é contabilizado no pior tempo de resposta da
execução dessa instrução.
Temos também de considerar o tempo de processamento das interrupções de
temporização. Como é sabido uma interrupções ocorre ao mesmo tempo que uma terfa
pretende ser executada. Para
cada tarefa real do sistema podemos criar uma tarefa
fictícia com uma prioridade muito elevada, o mesmo período da tarefa real e um tempo
de execução igual ao pior tempo de computação do manipulador da interrupção.
Há alguns problemas que devem ser ultrapassados neste tipo de escalonamento. O
hardware de temporização deve ser sofisticado, pois a programação que o algoritmo lhe
vai impôr implica o armazenamento de longos períodos de tempo. Nalguns
processadores o temporizador não é capaz de executar, convenientemente, essa função o
que vai aumentar a complexidade do algoritmo de escalonamento, pois quando se
verificar algum problema este deve ser detectado pelo algoritmo de maneira a que este
possa manter o controlo do tempo.
Outro problema verifica-se quando o algoritmo obriga o temporizador a provocar
a interrupção num intervalo de tempo muito pequeno o que leva a que o interrupção
possa ocorrer novamente antes que a tarefa seja libertada.
È devido a esta complexidade que surge outro tipo de implementação que é o
escalonamento por momentos.
Escalonamento por momentos
Esta é uma forma mais simples de implementar um algoritmo de escalonamento
de prioridade fixa. Como anteriormente o escalonador pode ser invocado aquando de
uma instrução de espera e pode alterar a tarefa a executar se chegar uma de maior
prioridade do que aquela que está a computar. No entanto, ao contrário da aproximação
anterior, o temporizador não é programado para interromper a execução num dado
momento. Em vez disso o temporizador é programado para levantar uma interrupção a
intervalos regulares de tempo (momentos). Quando o escalonador é invocado pelo
temporizador ele apenas interroga a fila de espera para verificar se existem tarefas que
possam ser executadas.
Algoritmos de Escalonamento de Tarefas
18/19
Isto vem acabar com os problemas de corrida e de perda de interrupções desde
que o escalonador não demore mais do que o período regular previamente definido.
No entanto a análise efectuada na aproximação anterior já não é válida, pois temos
que ter em consideração a transferência de tarefas pode ser atrasada até um (1) intervalo
de tempo, o que não se verificava na análise anterior, tornando-a por isso, inválida.
Devemos também ter em conta o tempo de execução do escalonador, o que pode
ser feito tendo em calculando o seu pior tempo de execução e então tratando-o como
uma tarefa de alta prioridade com período igual ao intervalo de tempo do temporizador.
Na pior das situações o escalonador transfere todas as tarefas da fila de espera
para a de execução, mas esta situação ocorre muito raramente e por isso não é
considerada nesta aproximação.
O melhor procedimento será criar um conjunto de tarefas fictícias de maneira a
modelizar os custos de manipulação das filas e criar uma tarefa periódica simples para
modelizar os custos de temporização.
Comparação dos dois modelos
Podemos comparar os dois modelos e analisar quais são as suas vantagens e
desvantagens.
A maior vantagem da segunda aproximação é a sua simplicidade, tanto de
elaborar como de perceber. Da mesma forma também não requer grandes
potencialidades em termos de hardware. Por último nesta implementação não há
condições para se verificarem corridas entre as interrupções.
O escalonamento por acontecimentos é de uma forma geral mais eficiente que o
escalonamento por momentos e tem como maior desvantagem a sua complexidade.
Algoritmos de Escalonamento de Tarefas
19/19
CONCLUSÕES
Neste trabalho tentámos elaborar um apanhado relacionado com escalonamento de
tarefas e os seus algoritmos.
Incidimos mais fortemente ao nível dos algoritmos para situações de sistemas
mono-processador e com prioridades fixas, embora alguns deles, devido à sua evolução,
já não seja muito correcto considerá-los de prioridade fixa como vimos para o fim.
Este é um capítulo dos Sistemas de Tempo Real em que, por mais restrito que seja
o assunto, nunca é possível abrangê-lo na sua totalidade, por isso, e como somos meros
alunos, é natural que se verifiquem algumas falhas.
BIBLIOGRAFIA
à Planeamento de Tarefas – Paulo Moisés, 1999.
à Real Time Systems by Fixed Priority Scheduling – K. Tindell e H. Hansson,
1997
à Planificación Dinámica de Tareas – Alejandro Alonso, 1996