Escalonamento de Tempo Real

Métodos de escalonamento de processos para sistemas de tempo real

Escalonamento de Processos

Programa que foi ativado Estados de um processo:

Ready Running

Waiting

New Halted

CriaçãoEscalonador

Término

Esperandoevento

Eventoocorreu

ID do Processo

Estado

Program Counter

Memory PointersContexto (regs.)

I/O Status

Prioridade

Accounting Info• tempo CPU• limites, etc.

Bloco de Controle

Filas de Escalonamento

Long-term

queue

Short-term

queueCPU

I/Oqueue

I/Oqueue

I/Oqueue

I/O

I/O

I/O

Processrequest FIM

High-levelscheduling

Short-termscheduling

I/O scheduling

InterruptHandler

Interruptof process

Interrupt from I/O

Exemplo

Contr. Serviços

Scheduler

contr. interrupção

Sist. Operacional

ARun

B“Ready”

Outros processos

Execu-tando

Sist. Operacional

A“Waitin

g

B“Ready

Execu-tando

Contr. Serviços

Scheduler

contr. interrupção

Outros processos

A“Waitin

g

BRun Execu-

tando

Contr. Serviços

Scheduler

contr. interrupção

Outros processos

Sist. OperacionalProcesso A parou:• Req. serviço ao

S.O.• Interrupção de A

Ex. erro• Interrupção de

outra fonteEx. I/O

Processo A parou:• Req. serviço ao

S.O.• Interrupção de A

Ex. erro• Interrupção de

outra fonteEx. I/O

Taxonomia de Escalonamento

Dinâmico Requer kernel flexível

Estático Baixo overhead Não flexível

Online Decisões tomadas

online

Pre-emptivo

Mono-Processador

Offline Decisões tomadas

offline

Não pre-emptivo

Multi-processador

EscalonamentoPre-runtime

20 50

0 50

10 60 70

C ( = 20) D ( = 20)

A ( = 20)

Relations: A C B C

Processor1

Processor2

40 80

20

30

d’Ar’A

d’B d’C d’Dr’C r’B, r’

D

B ( = 20)cB cCcD

cA

20 50

0

10 60 70

B ( = 20)C ( = 20) D ( = 20)

A ( = 20)

Relations: C A B C

Processor1

Processor2

40 80

30

30

d’Ar’A

d’B d’Dr’C d’Cr’,BD

cBcCcD

cA

50

r’

Escalonamento pre-runtime

CreateRootNode rootLN = ØCN = {root}

stop: node q has a feasible solution

ProduceBasicSchedule( q )

LN = LN {q}

stop: iST | lateness(i) = minLateness i has an optimal but unfeasible solution

LN = Ø minLateness minLLB

LLB( q ) minLateness LLB( q ) 0

lateness(q) 0

n | n CNAdjustRelations( n )

q | consistent(q) = true

parentNode = i | ( LLB(i) = min ( LLB(n) | n LN ) )LN = LN - {parentNode}CreateBranchSets(parentNode)CN = CreateChildNodes(parentNode)

Yes

Yes

No

No

Yes

No

Exemplo 2

Relations: A B, B C, C D

Relations: B A, B C, C D

20 60 70

1

2

9540 100

4025

d’C

d’D

r’C

r’A d’A r’D

0

r’B

5

d’Er’E

45 55

D

80

E

60

d’B

C

B

70

2

95

4525

d’C

d’D

r’C

r’,A r’D

0

r’B

5

d’Er’Ed’A

45 55 80

60

d’B

25

C

EDA B

75

A

Relations: A B, B C, C D

Relations: B A, B C, C D

20 60 70

1

2

9540 100

4025

d’C

d’D

r’C

r’A d’A r’D

0

r’B

5

d’Er’E

45 55

D

80

E

60

d’B

C

B

70

2

95

4525

d’C

d’D

r’C

r’,A r’D

0

r’B

5

d’Er’Ed’A

45 55 80

60

d’B

25

C

EDA B

75

A

Exemplo 3

3

d’B

1

d’D

r’A d’A

r’ ,C r’D

r’B

D2

12080 1100 60 9020

70 80400 50 90

700 10 5020

d’C

95

r’E

75

d’Er’F

85

E

d’F

115

F

Relations:A B, B C,B D, D E

C

B

A

3

d’B

C

1

d’D

r’A d’A

r’,C r’D

r’B

D

A

2

B

110400 60

70400 60 90

400 10 50

d’C

95

r’E

75

d’Er’F

85

E

d’F

115

F

3

d’B

C

1

d’D

r’A d’A

r’,C r’D

r’B

D

A

2

B

1100 6020

80400 50 60 90

700 10 5020

d’C

95

r’E

75

d’Er’F

85

E

d’F

115

F

Real-Time KernelsNúcleos operacionais para sistemas de tempo real

Introdução Que funções um núcleo deve ter? Que tipos existem? Como são implementados? Núcleo: comprar ou construir, eis a

questão.

Funções de um núcleo Escalonamento Dispatcher Comunicação entre tarefas

Tipos de Núcleo Nano-kernel:

Uma única thread (apenas task dispatching) Micro-kernel:

+ escalonamento (multi-tasking) Kernel:

+ comunicação Executivo

Blocos privados de memória, I/O e outros serviços (maioria dos kernels comerciais)

Sistema Operacional Interface com usuário (shell), gerenciamento de arquivos, segurança.

Sistemas de Tempo Real - STRImplementação

WCET: Restrições Impostas Memória virtual Memória cache Alocação dinâmica de memória Garbage collection Recursão

Técnicas de Implementação Interrupção Exceção Polling

Processos em background e Foreground

Co-rotinas

Polled Loop

Exemplo:while TRUE do

{if (sensor_ativo)

{

processe_dados();sensor_ativo =

FALSE;}

}

Polled Loop com interrupções Elimina switch bounce

while TRUE do{if (tecla_ativa)

{contador = 0;while (contador <

3);tecla_ativa =

FALSE;processe_dados();}

}

interrupt Clock {contador++;}

Phase/State-Driven Code Processos são implementados como FSMs

while TRUE{get(input);estado = transicao[ord(input)][state];executeProcesso(estado);}

executeProcesso(state estado){switch estado

case 0: processo0;case 1: processo1;

}

Corotinas (Ada e Modula-2) Dificil de Programar

ProcessoA(){while TRUE switch estadoA

case 0: faseA0;case 1: faseA1;

}

ProcessoB(){while TRUE switch estadoB

case 0: faseB0;

case 1: faseB1;}

Modelo de Pilha Tarefas são controladas diretamente por interrupção Salvam seu contexto na pilha Usado em sistemas embarcados

Taski

salva contexto executa código restaura contexto

Round-robin com time slicing Tarefas tem tempo fixo de execução Salvam seu contexto na pilha Usado em sistemas embarcados

Sistemas baseados em prioridade Rate-monotonic

Requer um kernel (pequeno S.O.) para escalonar as tarefas dinamicamente

Todas as tarefas são periódicas Tarefas esporádicas podem ser tratadas por “servidores esporádicos”,

que são tarefas periódicas Tarefas com menor período têm maior prioridade Existem técnicas de análise capazes de garantir a priori se um conjunto

específico de tarefas é escalonável, ou seja, que obedecerão seus deadlines. Para isso, é necessário que:

Todos os deadlines sejam iguais aos períodos Não haja precedência ou exclusão mútua

Sistemas baseados em prioridade Deadline monotonic

Baseado no rate monotonic Todas as tarefas são periódicas Tarefas esporádicas podem ser tratadas por

“servidores esporádicos”, que são tarefas periódicas Tarefas com menor deadline têm maior prioridade Também permite analisar a escalonabilidade, mas não

é necessário que os os deadlines sejam iguais aos períodos

Sistemas foreground/background Caso geral de SETR Foreground

Processos com interrupções (ex. round-robin, prioridade fixa) Background

Processos sem interrupções (pre-emptáveis pelos processos em foreground)

Se p = tempo processos foreground

e = tempo de execução background

t = e / (1-p) = período dos background.

Problema da Exclusão Mútua Garantir que apenas um processo

acesse um dado compartilhado por vez: definição de seções críticas

Problemas: deadlock starvation (oposto de fairness)

Resolvendo a exclusão mútua

Busy-waiting• Controle de acesso a região

– variável Lock

Lock = 0 pode entrarlock = 1 bloqueado

loop: test lock bne loop add #1, loop

e se houver Interrupção?

Desabilitar interrupçõesSimplicidadeSimplicidade

Regiões devem ser pequenasRegiões devem ser pequenas

Inviável em multiprocessadoresInviável em multiprocessadores

Núcleo: comprar ou construir Existem núcleos para sistemas

embarcados? Performance Complexidade Corretude

Comunicação

Mailboxes Regiões Críticas Primitivas de comunicação Semáforos

Comentários Multi-tarefa em tempo real pode ser conseguido sem

interrupções (mais fácil de analisar) Um kernel cíclico sem interrupção usa um ou mais ciclos

principais para descrever a ordem de execução de ciclos menores

Arquiteturas foreground/background são as mais usadas Modelo task-control block é usado em kernels e S.O.

comerciais com No. de tarefas dinâmico e indeterminado. Quanto mais flexibilidade no kernel, mais complexo, lento

e difícil de analisar