Algoritmos de Escalonamento

Sistemas de Tempo RealCentro de Informática - UFPE

Equipe Ademir Jr. André Guedes André Souza Bruno Barros Diêgo Santiago

Francisco Simões Rebeka Gomes Renato Marcelino Rodrigo Melo Valmir Sena

Roteiro

Algoritmos de escalonamentoRate MonotonicEarliest Deadline FirstDeadline Monotonic

Introdução

Escalonamento:“Procedimento de ordenar a execução de tarefas

na fila de pronto”Aspecto importante em sistemas com restrições

temporaisDetalhes de implementação tratados na fase de

projeto

Tarefa

Abstração básica de um “problema de escalonamento”:Concorrência por recursos computacionaisCorrectness e TimelinessPrecedência e ExclusãoHard / SoftPeriódicas / AperiódicasEsporádicas

Tarefa Tempo de Início Tempo de Término Tempo de Chegada Tempo de Liberação

Tempo de Computação Período Deadline Release Jitter

Tarefa Tempo de Início Tempo de Término Tempo de Chegada Tempo de Liberação

Tempo de Computação Período Deadline Intervalo Mínimo

Escalonamento

“Procedimento de ordenar a execução de tarefas na fila de pronto”

Escalonador Escala de execução Problema NP-Completo Algoritmo Ótimo Características:

Preemptivo / Não-Preemptivo Estático / Dinâmico Offline / Online

Escalonamento

Abordagens

Escalonamento

Teste de Escalonabilidade

Escalonamento

Utilização de uma tarefa

Rate Monotonic Scheduling

Motivação

STR desenvolvidos com técnicas empíricas podem ser altamente imprevisíveis

STR atuais são baseados em modificações dos sistemas time sharing: Multitarefas Escalonamento baseado em prioridade Suporte de um clock de tempo real

Motivação

Algoritmos de escalonamento não consideram:

Tempo de computaçãoRestrição de tempoRecursos compartilhadosRelação de precedência entre as tarefas

Definições

Algumas definições importantes com respeito a Tarefas PeriódicasC: WCET de uma tarefaT: Periodo de uma tarefaU: Processor Utilization Factor

Ulub: Least Upper Bound Processor Utilization Factor

Rate Monotonic Scheduling (RMS)

• Algoritmo de Escalonamento Preemptivo e com prioridades

• Prioridades fixas e inversamente proporcionais ao período

• Tem garantias determinísticas em relação ao tempo de resposta

• Qualquer tarefa pode ser interrompida por outra tarefa com maior prioridade que esteja no estado PRONTO

Rate Monotonic Scheduling (RMS)

PremissasAs tarefas são periódicas e independentesO “deadline” de cada tarefa coincide com o seu

período e são conhecidos e estáticosO tempo de computação (WCET) de cada tarefa é

conhecido e constanteO tempo de chaveamento dentre tarefas não

causa impacto no modelo

Rate Monotonic Scheduling (RMS)

Escalonabilidade por Liu e LaylandPara um conjunto de tarefas, se U <= Ulub então

ele esse conjunto de tarefas é escalonavel.Para um conjunto com n tarefas, o Ulub desse

conjunto em relação ao RMS é dado por:

Para )12(lub nnUn

...693147.02ln)12(lim

n

nn

Logo, para que um conjunto de n tarefas seja escalonável:

Onde:Ci é o custo da ith tarefaTi é o tempo de execução da ith tarefa

)12(1

nn

i i

i nT

CU

Rate Monotonic Scheduling (RMS)

• Escalonabilidade por Bini, Butazzo e Butazzo (2001)– Hiperbolic Bound for RMS– Mais abrangente

• Menos pessimista• Aceita problemas que a fórmula definida por Liu e Layland não

aceitaria– Um conjunto de tarefas com n é escalonável se:

• Onde Ui é o fator de utilização do processador da ith tarefa

Rate Monotonic Scheduling (RMS)

Considere as três tarefas:

Aplicando a fórmula, temos:

Então podemos dizer que estas tarefas são escalonáveis pelo RMS

Tarefa Período Tempo de execução Prioridade RM Utilização

A 100 20 1 0,2

B 150 40 2 0,267

C 350 100 3 0,286

779,0)12(3753,0 3

Rate Monotonic Scheduling (RMS)

Utilizando a fórmula de BBB, chegamos a mesma conclusão:

2)1(3

1

i

iU

21,9552344

Rate Monotonic Scheduling (RMS)

As tarefas A, B e C são executadas em t=0 Devido à sua freqüência, A assume o processador A conclui e B assume C assume e é interrompida logo após por A

Rate Monotonic Scheduling (RMS)

Tarefas Periódicas Ci Pi Di

Tarefa A 10 20 20Tarefa B 25 50 50

A,B A

0 4010 20 30 50

A B

…

Rate Monotonic Scheduling (RMS)

Vantagens

SimplicidadeRMS é ótimo para a classe de problemas na qual

ele se encontra inserido

Rate Monotonic Scheduling (RMS)

Desvantagens Na prática, a maioria dos problemas não possuem

suas tarefas totalmente independentes O RMS original pode causar problemas de inversão de

prioridades e deadlock Que pode ser resolvido com herança de prioridades Ou métodos alternativos, como o uso de algoritmos não-

bloqueáveis, ou evitar o compartilhamento de semáforo entre threads com prioridades diferentes

Rate Monotonic Scheduling (RMS)

Priority inheritance

Podem ser caracterizados por dois parâmetros:Herança retardada (‘lazy’) ou imediata

Retardada – apenas quando for essencial Imediata – aumenta a prioridade

Herança otimista ou pessimista Otimista – aloca uma quantia mínima Pessimista – aloca mais que o necessário

Priority inheritance (exemplo)• Considere as três tarefas:

Tarefa Prioridade

A Alta

B Média

C Baixa

• A e C utilizam o mesmo recurso• Enquanto C executa, ganha prioridade mais alta• B não consegue interromper C• C acaba de executar, muda de prioridade e acorda A• A interrompe C e termina de executar• B e C executam logo em seguida

Exemplos de uso Quem já usou RMS?

In 1989 IBM applied RMA to a sonar training system, allowing them to discover and correct performance problems [Lucas 92].

Since 1990, RMA was recommended by IBM Federal Sector Division (now Lockheed Martin) for its real-time projects.

RMA was successfully applied to active and passive sonar of a major submarine system of US Navy. RMA was selected by the European Space Agency as the baseline theory for its Hard Real-Time Operating

System Project. The applicability of RMA to a typical avionics application was demonstrated [Locke 91]. RMA was adopted in 1990 by NASA for development of real-time software for the space station data

management subsystem. In 1992 Acting Deputy Administrator of NASA, Aaron Cohen stated, "Through the development of rate monotonic scheduling, we now have a system that will allow (Space Station) Freedom's computers to budget their time to choose [among] a variety of tasks, and decide not only which one to do first but how much time to spend in the process."

Magnavox Electronics Systems Company incorporated RMA into real-time software development [Ignace 94]. RMA principles have influenced the design and development of the following standards:

IEEE Futurebus+ [Sha 91b] POSIX Ada 95

Tool vendors provide the capability to analyze real-time designs using RMA. RMA algorithms, such as priority inheritance, have been used by operating system and Ada compiler vendors.

Earliest Deadline First

EDF (Earliest Deadline First)

Algoritmo de escalonamento de tarefas periódicas

Define escalonamento baseado em prioridades

A tarefa mais prioritária é a que tem o deadline mais próximo do tempo atual

EDF (Earliest Deadline First)

A escala é produzida em tempo de execução por um escalonador preemptivo

Simplificações do Algoritmo:Tarefas periódicas e independentesDeadline igual ao período (Di=Pi).O tempo de computação conhecido e constante

(tempo do pior caso).Tempo de Chaveamento nulo.

Teste de Escalonabilidade do EDF

Pode ser realizado em tempo de projeto Caso obedeça as premissas do slide anterior

este teste é suficiente e necessário

Onde U é o uso do processador, C o tempo de computação e P é o período

11

n

i i

iP

CU

EDF (Earliest Deadline First)

Tarefas Periódicas Ci Pi Di

Tarefa A 10 20 20Tarefa B 25 50 50

11

n

i i

iP

CU 10/20 + 25/50 = 1

EDF (Earliest Deadline First)

Tarefas Periódicas Ci Pi Di

Tarefa A 10 20 20Tarefa B 25 50 50

A,B A

0 4010 20 30 50

A B

…

Exemplo de EDF

EDF (Earliest Deadline First)

Tarefas Periódicas Ci Pi Di

Tarefa A 10 20 20Tarefa B 25 50 50

A,B A

0 4010 20 30 50

A B

…

B perde o Deadline

Exemplo de RMS

Deadline Monotonic

Deadline Monotonic

Algoritmo de escalonamento estático Proposto por Leung e Whitehead em 1982 Similar ao Rate Monotonic

"The inverse-deadline priority assignment is an optimal priority assignment for one

processor."

Deadline Monotonic Características:

Prioridades EstaticasPreemptivoTodos os processos são periodicosDeadline <= PeriodoPrioridade é inversamente proporcional ao

DeadlineAlgoritmo ótimo

Deadline Monotonic

Onde:• Ti é o período;•Ci é o tempo de computação no pior caso (constante para cada instante);•Di é o deadline (constante para cada instante);

Figura 1. instância de tarefa no Deadline Monotonic

Deadline Monotonic

Como saber se todos os processos são escalonáveis utilizando o Deadline Monotonic?

Roda e ver se funciona!!

Ou utilizar o teste de agendamento proposto por Audsley.

Exemplo 1

Figura 2. exemplo de tarefas escalonadas no Deadline Monotonic

Deadline Monotonic

Maior tempo de resposta de uma tarefa periodica é igual a:

Ri = Ci + Ii Ci => Tempo de Computação da tarefa i no pior caso. Ii => Interferência sofrida pela tarefa i pela outras tarefas.

Se para toda tarefa i temos Ri <= Di , então o conjunto de tarefas será escalonavel com o Deadline Monotonic.

Deadline Monotonic

Substituindo:

Desejamos encontrar o menor valor de Ri que satisfaça essa igualdade.

j

i

j j

ii C

T

RI

1

1

j

i

j j

iii C

T

RCR

1

1

Deadline Monotonic

Algoritmo:

1. R = ∑ Cj

2. Calcula-se Ii

3. Se Ri = Ii + Ci , então o pior caso é Ri. Se não atualizar:

Ri = Ii + Ci, e voltar para o passo 2.

(0) i

j =1 k

k k k

(K + 1) k

Exemplo 2

C T D

P1 1 4 3

P2 1 5 4

P3 2 6 5

P4 1 11 10

Exemplo 2

R4 = 5 ; I4 = 5 ; temos: I4 + C4 != R4

R4 = I4 + C4 = 6 ; I4 = 6 ; temos: I4 + C4 != R4

.

.

.

.

R4 = I4 + C4 = 10 ; I4 = 9 ; temos: I4 + C4 = R4

Então pior tempo de resposta de P4 é:

R4 = R4 = 10

(1)

(4)

(0)

(5)

(0)

(1)

(0)

(0) (1)

(0)

(1)

(5) (5) (5)

(5)

Exemplo 2

C T D

P1 1 4 3

P2 1 5 4

P3 2 6 5

P4 1 11 10

Exemplo 2

Como R4 <= D4, então nesse caso P4 é escalonável utilizando o Deadline Monotonic.

Exemplo 2

Figura 3. gráfico do exemplo 2

Referências

Jean-Marie Farine, Sistemas de Tempo Real Giorgio C. Buttazzo, Hard Real-Time

Computing Systems Klein et al., A Practiotioner’s Handbook for

Real-Time Analysis Neil C. Audsley, Deadline Monotonic

Scheduling