Teste de Escalonabilidade Em Modelos Estendidos (FINAL)

TESTE DE ESCALONABILIDADE EM MODELOS ESTENDIDOSCOMPARTILHAMENTO DE RECURSOS

RELAÇÕES DE PRECEDÊNCIA

COMPONENTES: DANIEL LUIS M. TIMPONI R.A.: 16607

KAUÊ MARTINS SILVA R.A.: 16629

LUIZ OTÁVIO NUNES R.A.: 16635

TALES PELINSARI R.A.: 16646

TESTE DE ESCALONABILIDADE EM MODELOS ESTENDIDOS

Deadline Igual ao PeríodoTESTE DE ESCALONABILIDADE EM MODELOS ESTENDIDOS

TESTE DE ESCALONABILIDADE EM MODELOS ESTENDIDOSDeadline Igual ao Período

É apresentado um teste onde a utilização do processador não tem mais um sentido estático, dependente somente das restrições temporais das tarefas, mas é também função de uma janela de tempo t considerada no seu cálculo. As tarefas de prioridade maior ou igual a i que estão disponíveis para execução no processador no intervalo t constituem a carga cumulativa ("workload") Wi(t) deste intervalo e é dada por:


A divisão do "workload" W(t) pelo valor de t dá a percentagem de utilização do processador nesse intervalo de tempo t, considerando apenas tarefas de prioridade maior ou igual a Ti :

A condição necessária e suficiente para que a a tarefa Ti seja escalonável é que exista um valor de t em que a sua utilização U(t) seja menor ou igual a 1.


Correspondem ao tempo de chegada das tarefas Tj de prioridade maior ou igual a Ti, ocorrendo dentro do periodo Pi.

Deadline Igual Menor que o PeríodoTESTE DE ESCALONABILIDADE EM MODELOS ESTENDIDOS

TESTE DE ESCALONABILIDADE EM MODELOS ESTENDIDOSDeadline Igual Menor que o Período

O modelo assume também tarefas com "deadlines" menores aos seus períodos (Di<= Pi). Esse teste está fundamentado no conceito de tempo de resposta.

O tempo de resposta máximo de uma tarefa foi introduzido como sendo o tempo transcorrido entre a chegada e o término de sua execução, considerando a máxima interferência que a tarefa pode sofrer de outras tarefas de maior ou igual prioridade.


A solução é conseguida a partir do cálculo de aproximação de Ri, quando =

como condição de partida =

O método não converge quando a utilização do conjunto de tarefas for maior que 100%



Nos modelos apresentados até aqui as tarefas são assumidas como periódicas e liberadas sempre no início de cada período. Contudo isto nem sempre corresponde a uma hipótese realista.

Escalonadores ativados por tempo ("ticket scheduler") podem ser fonte do atraso na liberação de tarefas:

As tarefas tem as suas chegadas detectadas nos tempos de ativação do escalonador, determinando atrasos nas suas liberações.

Esses atrasos podem ser expressados no pior caso como "release jitters" (J)


Para determinar as modificações necessárias no sentido de representar no cálculo dos tempos de resposta as variações na liberação das tarefas, é necessário que se introduza o conceito de período ocupado (“busy period”).

Um período ocupado i corresponde a uma janela de tempo Wi onde ocorre a execução contínua de tarefas com prioridade maior ou igual a i (pi = i).

Deadline ArbitrárioTESTE DE ESCALONABILIDADE EM MODELOS ESTENDIDOS

TESTE DE ESCALONABILIDADE EM MODELOS ESTENDIDOSDeadline Arbitrário

Em modelos de deadline arbitrário, podemos ter (D > P).

Tarefas com estas características sofrem interferência interna.

Logo, para cálculo do tempo de resposta, também temos de levar em consideração a interferência da própria tarefa sobre si mesmo.

Nesta extensão é assumido que a execução de qualquer liberação de uma tarefa será atrasada até que liberações anteriores da mesma tarefa sejam executadas completamente.


Considera-se então o "i-busy period" incluindo q+1 ativações de Ti que podem se sobrepor na concorrência ao processador pois Di > Pi . O valor da janela de tempo Wi(q) correspondente é dado por:

O tempo de resposta da ativação de Ti é dada por:

Para que se obtenha o tempo de resposta máximo Ri da tarefa Ti é necessário que se faça a inspeção de todos "i-busy periods", na ordem de valores crescentes de q (q=0, 1, 2, 3,..), até um valor de janelaque verifique a condição:


Se o efeito de "deadlines" arbitrários for incluído em modelos onde as liberações não coincidem com os tempos de chegada das instâncias da tarefa T , a janela de tempo Wi (q) e o tempo de resposta Ri passam a ser dados, respectivamente, por:


(0)= (1) -q

O valor do tempo de resposta R3(0) corresponde a 25. Com W3(0) superando o período P3 (P3 = 20) então, essa janela não corresponde ao maior "busy period" de prioridade 3.


= (1) -q

Com isto obtemos R3(1) = W3(1) - P3 = 10. Como W3(1)<2P3 temos então o máximo "busy period" envolvendo duas ativações da tarefa T3

COMPARTILHAMENTO DE RECURSOS

COMPARTILHAMENTO DE RECURSOSTarefas dependentes

As tarefas apresentadas nos exemplos anteriores eram tarefas independentes, mas em sistemas de tempo real geralmente não ocorre dessa forma. Muitas tarefas possuem relação entre elas.

As tarefas dependentes criam bloqueios em tarefas mais prioritárias, também chamados de inversões de prioridades.

Esses bloqueios são inevitáveis em um escalonamento dirigido a tarefas dependentes. Sabemos que evitar esses bloqueios ao máximo seria de grande importância, por isso, foram criados métodos para reduzir esse número (Protocolo Herança de Prioridade e o Protocolo de Prioridade Teto).

COMPARTILHAMENTO DE RECURSOSTarefas dependentes

COMPARTILHAMENTO DE RECURSOSProtocolo Herança de Prioridade

Nesse método, as prioridades deixam de ser estáticas, ou seja, de acordo com a figura anterior, quando T1 e T4 sofrem bloqueio, a prioridade passa a ser em T1. Evitando assim que tarefas intermediárias atrasem a execução em seções críticas.

Tarefas possuem duas prioridades: Tarefas possuem prioridade nominal ou estática (RM, DM, etc).

Tarefas possuem prioridade dinâmica ou ativa (Derivadas das ações de bloqueio que ocorrem no sistema).


Uma tarefa mais prioritária quando executada sob o PHP pode sofrer dois tipos de bloqueios:

Bloqueio direto: ocorre quando a tarefa mais prioritária tenta acessar o recurso compartilhado já bloqueado pela tarefa menos prioritária.

Bloqueio por herança: ocorre quando uma tarefa de prioridade intermediária é impedida de continuar sua execução por uma tarefa que tenha herdado a prioridade de uma tarefa mais prioritária.


COMPARTILHAMENTO DE RECURSOSBloqueio Transitivo

Ocorre quando há uma sequência de tarefas aninhadas, ou seja, quando uma tarefa possui ligações com outras tarefas simultaneamente.

Esses bloqueios simultâneos podem causar deadlocks.

COMPARTILHAMENTO DE RECURSOSBloqueio Transitivo

COMPARTILHAMENTO DE RECURSOSCálculo do Bloqueio Máximo

O cálculo do bloqueio no PHP envolve diversas variações, o que pode tornar estes cálculos muitas vezes complicados e imprecisos.

A seguir vamos apresentar alguns métodos para o cálculo deste bloqueio máximo.


Aqui o teste do RM é estendido no sentido de incorporar as relações de exclusão de um conjunto de tarefas:

No somatório do teste acima, considera-se a utilização de tarefas com prioridade maior ou igual a pi .

No termo Bi / Pi , corresponde à utilização perdida no bloqueio de Ti por tarefas menos prioritárias.

Nesta equação, podemos ver se o escalonamento será possível e se a tarefa irá executar dentro do seu tempo de deadline.


Esse teste é mais impreciso que o teste apresentado anteriormente, ou seja, os resultados obtidos aqui podem ser diferentes do anterior. Digamos que nos valores obtidos nesse teste não foi possível o escalonamento, os cálculos então precisariam ser refeitos no teste anterior para confirmar esse resultado. Mas se um teste for escalonável, não precisará refazer os cálculos para ter a confirmação da resposta.

Outro teste, porém mais simples pode ser realizado utilizando apenas a fórmula abaixo:


A seguir temos o modelo para calcular o escalonamento de prioridades fixas, utilizando o bloqueio que cada tarefa sofre no conjunto.


O teste baseado em tempo de resposta para modelos envolvendo deadlines arbitrários, é estendido utilizando a seguinte fórmula:

O calculo de Bi (maior sessão crítica que bloqueia Ti) nem sempre é exato, o que deixa os resultados bastantes imprecisos.

COMPARTILHAMENTO DE RECURSOSProtocolo de Prioridade de Teto

É usado para escalonamentos de prioridades fixas, como o rate monotonic.

Limita o número de bloqueios ou inversões de prioridade para evitar deadlocks.

Dirigido para escalonamento de prioridade fixa.

COMPARTILHAMENTO DE RECURSOSProtocolo de Prioridade de Teto

Assegura que apenas um bloqueio é realizado por seção. Se uma tarefa de menos prioridade interferir em uma de maior prioridade, esse protocolo não deixa que outra tarefa com prioridade inferior interfira novamente no processo.

Se ocorrer o bloqueio em mais de duas tarefas, a tarefa com menor prioridade inicial que passou a ser a principal recebe um valor de prioridade teto, significando que ela passa a ser a tarefa de prioridade máxima.

Uma tarefa só acessa um recurso compartilhado se sua prioridade ativa for maior que a prioridade teto de qualquer recurso já previamente bloqueado

COMPARTILHAMENTO DE RECURSOSBloqueio ceiling

O protocolo de prioridade de teto introduz um novo tipo de bloqueio chamado de ceiling, onde uma tarefa fica bloqueada porque não possui prioridade dinâmica superior a de maior prioridade teto entre os recursos ocupados. Esse bloqueio é necessário para evitar as cadeias de bloqueios e os deadlocks.

COMPARTILHAMENTO DE RECURSOSImmediate Priority Ceiling Protocol (IPCP)

Uma versão melhorada do PCP.

A herança de prioridade no IPCP deixa de se dar quando a seção crítica bloqueia a tarefa mais prioritária. A tarefa menos prioritária tem sua prioridade ativa elevada, assumindo logo no início da seção crítica a prioridade teto do recurso acessado, com isso, garantimos que um tarefa só poderá ser bloqueada no início de sua execução e que a partir do momento de sua execução, somente uma tarefa de maior prioridade poderá interromper o processo.

COMPARTILHAMENTO DE RECURSOSImmediate Priority Ceiling Protocol (IPCP)

T3 começa sua execução

T3 entra em seção crítica (fecha o Semáforo S3)

T2 inicia seu processamento interrompendo T3(preempção de T3)

T2 sofre bloqueio direto: S3 “fechado” por T3 que reassume e herda prioridade de T2

T3 entra na seção crítica aninhada ao fechar semáforo S2

T1 inicia e interrompe T3. T1 é mais prioritária que T3 com a prioridade herdada de T2

T1 tenta fechar semáforo S1, é bloqueado por “ceiling”; possui prioridade igual ao maior “ceiling” de semáforo já fechado pelas outras tarefas.

T3 libera semáforo S2. T1 é reativado e interrompe T3. T1 entra em S1.

T1 libera S1T1 fecha Semáforo S2

T1 libera S2

T1 termina e T3 reassume na prioridade herdada de T2T2 libera S3 ; fecha e libera S1; e completa. T3 reassume e completa

T3 libera S3 retornando a sua prioridade estática. T2 interrompe T3 e fecha S3

COMPARTILHAMENTO DE RECURSOS Teste de Escalonabilidade no PCP

Mesmas fórmulas do PHP

Só muda o conceito de bloqueio máximo (Bi).

Duração da maior sessão crítica que pode bloquear pelo algoritmo de Teto.

RELAÇÕES DE PRECEDÊNCIA

RELAÇÕES DE PRECEDÊNCIAOffsets

A tarefa sucessora de uma precedência é liberada pela passagem do tempo de offset.

O uso de "offsets" pode representar em sub-utilização de recursos, uma vez que a sucessora é sempre liberada por tempo em situação de pior caso

RELAÇÕES DE PRECEDÊNCIAComunicação entre Tarefas

Relações de precedência podem ser definidas através das necessidades de comunicação e sincronização entre as tarefas

As tarefas tipicamente, recebem mensagens, executam seus processamentos e por fim, enviam seus resultados ou sinais de sincronização na forma de mensagens.

RELAÇÕES DE PRECEDÊNCIAOffsets Vs. Comunicação entre Tarefas

A diferença está em tempo de execução:

A liberação por passagem de tempo é uma técnica estática onde o "offset" é definido previamente, impondo sempre o pior caso de liberação,

A liberação por mensagem é dinâmica e o pior caso de liberação eventualmente pode acontecer.

RELAÇÕES DE PRECEDÊNCIAAtividades

O conceito de atividade é usado como a entidade encapsuladora de tarefas que se comunicam e/ou se sincronizam.

Cada atividade é representada por um grafo orientado acíclico onde os nodos representam tarefas e os arcos identificam as relações de precedência.

RELAÇÕES DE PRECEDÊNCIAAtividades

O conceito de atividade é usado como a entidade encapsuladora de tarefas que se comunicam e/ou se sincronizam.

Cada atividade é representada por um grafo orientado acíclico onde os nodos representam tarefas e os arcos identificam as relações de precedência.

As atividades são ditas síncronas quando as tarefas liberam suas sucessoras pelo envio de mensagens

As atividades são ditas assíncronas quando a liberação envolve "offsets”.

RELAÇÕES DE PRECEDÊNCIAVerificação da Escalonabilidade

O modelo introduzido coloca as atividades como síncronas o que implica em tratar precedências como "release jitters". Como as tarefas possuem "deadlines" relativos menores que seus respectivos períodos, a verificação de escalonabilidade pode ser feita usando as equações:

A escalonabilidade é verificada por:


T1 é a mais prioritária e não sofre interferência de outras tarefas. O seu tempo de resposta é : R1= C1+J1= 11.


A tarefa T2 sofre interferência só da tarefa T1 e do seu tempo de resposta máximo.

Com W2=20 e tomando J2=3, o valor do tempo de resposta é dado por R2=23


A tarefa T3, por sua vez, sofre interferências de T1 e de um jitterPorque sua liberação depende da conclusão de T2(J3=R2)

O tempo de resposta de T3 é dado por: R3 =W3+J3=38


A tarefa T4, por sua vez, sofre interferências de T1 e T3 e um "jitter" de T2 (J=R2)

A tarefa T4 tem o seu pior tempo de resposta portanto em 48 (R4=W4+J4).

Se compararmos os tempos de resposta encontrados com os "deadlines' relativos das respectivas tarefas na figura 2.13, verificamos que as tarefas são escalonáveis..

BIBLIOGRÁFIA

Jean-Marie F.; Fraga, J. S.; e Oliveira, R. S., Sistemas de Tempo Real, Departamento de Automação e Sistemas, Universidade Federal de Florianópolis, Florianópolis-SC, 2000, Acessado em 12 de abril de 2013, Disponível em <http://www.das.ufsc.br/~romulo/livro-tr.pdf>;

Araujo, R. G. B., Simulador de escalonamento em tempo real – CHEDDAR, Departamento de Engenharia e Arquitetura, Universidade de Salvador BA, , Acessado em 12 de abril de 2013, Disponível em < http://www.harpia.eng.br/disciplinas/str/Simulador_Cheddar%20-%20How%20to.pdf >.

The Cheddar project : a free real time scheduling analyzer

LINK PARA DOWNLOAD: http://beru.univ-brest.fr/~singhoff/cheddar/ ;

http://beru.univ-brest.fr/~singhoff/cheddar/



Documents

Teste de Escalonabilidade Em Modelos Estendidos (FINAL)