Desempenho de computação paralela - UFFboeres/slides_AP/DesempenhoOpt.pdf · Shortest remaining time (SRT) • seleção: processo que precisa de menor tempo para terminar ... O

Desempenho de computação paralela o paralelismo existente na aplicação

decomposição do problema em subproblemas menores

a alocação destes subproblemas aos processadores

o modo de acesso aos dados:

– a existência de uma memória global

– ou distribuída comunicação por trocas de mensagens

a estrutura de interconexão entre os processadores

a velocidade dos processadores, memórias e rede de interconexão.

Em ambientes distribuídos, a meta é de explorar e tirar proveito ao máximo do

potencial computacional, sendo assim questões relacionadas ao gerenciamento de recursos do sistema muito importante

1

Escalonamento de Aplicações

Um algoritmo que estabelece como executar um algoritmo paralelo em um determinado sistema de computadores

Para implementar um escalonador, o problema tem que ser especificado:

– As características da aplicação devem ser especificadas

– As características cruciais do sistema de processadores em questão devem ser estabelecidas

2

Modelagem

Representação do problema – Algoritmo paralelo composto por processos/threads que sincronizam

parcialmente (comunicação/dependência)

– Conjunto de threads/processos independentes

Representação do ambiente de solução

Simplificação, sem omitir as características que afetam o desempenho em geral

3

Qual o objetivo Escalonar aplicações em um sistema paralelo e distribuído tal que o tempo de execução seja minimizado

Escalonar aplicações em um número limitado de processadores tal que o tempo de execução seja minimizado, considerando custo de comunicação

Escalonar aplicações em um número limitado de processadores tal que o tempo de execução seja minimizado considerando tempos limites (deadline), considerando custo de comunicação

o objetivo deve estar especificado

4

Questões de projeto Alocação de processos a processadores

Processos podem ser alocados a certos processadores e não mudar até o seu término

– Exemplo: processo Px é associado ao núcleo Ny até o seu término

– Escalonador de curto prazo é aplicado (pode ser preemptivo ou não)

– Vantagem:

• menos overhead/sobrecarga

• Escalonamento meio que estático

5

Questões de projeto Alocação de processos a processadores

(alocação estática de processos a processadores)

– Desvantagem:

• Associar em um determinado momento vários processos a um processador (núcleo) e outro processador se tornar ocioso – não explora a ociosidade de processador

Solução para minimiza a ociosidade de processadores

– um processo pode ser alocado a diferentes processadores durante sua vida

– Pode ser vantajoso em um ambiente de memória compartilhada devido a uma menor sobrecarga na troca de contexto

– No entanto pode aumentar chache miss

• Por que?

6

Questões de projeto Paradigmas de alocação

De qualquer forma, quem associa? Como pode ser o modelo?

Duas abordagens: mestre/trabalhador e peer

7

Paradigmas de alocação Mestre/trabalhador

As funções de escalonamento executam em um processador: o mestre

Os outros processadores executam os processos de usuário (os trabalhadores)

Abordagem é simples e as políticas de uniprocessador podem ser mais facilmente adaptadas

Conflitos ficam mais fáceis de serem resolvidos pois o mestre tem visão de toda a memória e todos os dispositivos de I/O

Desvantagem:

– Falha do mestre

– Mestre pode ser tornar um gargalo

8

Paradigmas de alocação Mestre/trabalhador

As funções de escalonamento executam em um processador: o mestre

Os outros processadores executam os processos de usuário (os trabalhadores)

Abordagem é simples e as políticas de uniprocessador podem ser mais facilmente adaptadas

Conflitos ficam mais fáceis de serem resolvidos pois o mestre tem visão de toda a memória e todos os dispositivos de I/O

Desvantagem:

– Falha do mestre

– Mestre pode ser tornar um gargalo

9

Paradigmas de alocação Peer ou escalonador distribuído

O núcleo pode ser executado em qualquer processador

Cada processador faz self-scheduling de um pool de processos disponíveis

Vantagem:

– melhor otimização do problema e visão global

Desvantagem:

– complicação de implementação

– Necessidade de sincronização de diferentes processadores

10

Escalonamento de processos Escalonamento de processos em um processador

Base de sistemas operacionais

Baseado em estado de processos ao longo de sua vida em um sistema

11

Escalonamento de processos

IC - UFF

executando pronto

despacho

pausa

admissão

finalização

saída pronto suspenso

bloqueado

espera evento

evento ocorre

suspenso bloqueado

evento ocorre

carrega

suspende

admissão

novo

carrega

suspende

suspende

12

Escalonamento de processos prontos

Crucial para o desempenho dos processos nos Sistemas

Dois aspectos principais – seleção

• qual processo será selecionado para execução

• baseado em prioridade/necessidade de recurso/características de tempo de execução

– modo de decisão • Preemptivo ou não preemptivo

13


Início

Parada

Busca nova instrução

Executa instrução

Verifica interrupção

Ciclo de busca Ciclo de execução Ciclo de interrupção

Interrupções inibidas

Interrupções permitidas

14


First Come First Served (FCFS)

• seleção: primeiro da fila

• modo decisão: não preemtivo

Round-robin (RR)

• seleção: primeiro da fila

• modo decisão: preemtivo – precisa definir quantum

15


Shortest process next (SPN)

• seleção: precisa saber tempo associado ao processo

• modo decisão: não preemtivo

Shortest remaining time (SRT)

• seleção: processo que precisa de menor tempo para terminar

• modo decisão: preemtivo – processo executando é interrompido com chegado de novo processo

16


Feedback

– Seleção: sem cálculo do futuro (previsão de tempo de execução)

– Decisão: preemptivo - por chegada de processo ou por quantum

– especificação de n filas:

• P1 entra na fila RQ0 e é escolhido para execução

• interrupção: P1 vai para RQ1

• .... P1 saiu da fila RQi quando foi escolhido para execução

• interrupção: P1 vai para RQi+1

– um processo é escolhido da fila de menor índice que contem processos prontos para serem executados

– jobs curtos – pouco tempo no sistema

– se um job chegar a fila RQn, depois passará para RQ0

17

Escalonamento de processos Tradicionalmente em sistemas de multiprocessadores, processos não estão alocados exclusivamente a um processador

Em geral:

Fila única

P1

P2

P3

P4

18

19

Escalonamento de Processos

Exemplo de estudo comparativo

S1 - sistema com um processador

S2 - sistema duo-processador

Supondo

taxa de processamento de cada processador em S2 = ½ taxa processamento do processador de S1

Então, a pergunta é: é melhor ter dois processadores mais lentos do que um mais rápido?

20

comparação entre FCFS e round-robin

RR: quantum bem maior que tempo de troca de contexto

RR: quantum com valor pequeno quando comparado ao tempo médio de serviço dos processos

• resultado da análise: depende do coeficiente de variação em relação ao tempo de serviço

Cs =

ou seja, o quanto varia o tempo de serviço entre os diferentes processos

s

s

Tσ


21

• σs - desvio padrão do tempo de serviço

• - tempo médio de serviço

• Cs

• se Zero: os tempos de serviços são similares

• pode ser alto: muita variação entre os tempos de serviço

sT


22

• FCFS pode ser problemático quando comparado com RR em um processador. Mas....

• FCFS em S2 (duo processado) é amenizado:

• enquanto um processo longo que chegou primeiro está sendo executado por um processador, outros processos são executados no outro

• pode ser tão bom quanto round-robin, principalmente se o número de processadores aumentar


23

• processo = conjunto de threads

• em um processador

• threads são vantajosas devido a E/S

• em vários processadores

• dividir a funcionalidade do processamento entre processadores leva a um maior ganho

• threads + multiprocessamento = exploração do grau de paralelismo da aplicação

– granularidade fina paralelismo não tão vantajoso

– alto grau de interação entre threads

Escalonamento de Threads

Escalonamento é mais complexo quando várias CPUs se tornam disponíveis

Processadores Homogêneos dentro de um mesmo multiprocessador

no entanto, já se inicia uma tendência de heterogeneidade: big and small CPUs


24

Algumas classes de políticas:

Compartilhamento/balanceamento de carga Gang scheduling Alocação a processadores específicos Escalonamento dinâmico


25

Balanceamento de carga

O escalonador supervisiona a carga dos processadores, e divide a carga

Não deixa processador ocioso toda vez que um processador está ocioso, a rotina do SO o seleciona

para executar a próxima thread

Uma fila global pode ser definida e as threads a serem executadas são incluídas Conforme a chegada do processo, as suas threads são inseridas na

ordem FCFS

Ordenadas de acordo com prioridade, ou pelo número de threads que cada processo tem


26

Balanceamento de carga

Alguns problemas com uma fila única

Gargalo

Se as threads sofrerem preempção podem ser depois associadas a processadores diferentes com caches diferentes

Threads que compartilham informações podem ser associadas a processadores distintos com espaço de memória distinto (cache ou memória principal)


27

Gang Scheduling

Tem sido aplicado ao conceito de escalonar simultaneamente um conjunto de threads que compõem um processo

O conceito é bastante vantajoso quando threads dependem uma das outras e não podem esperar sem perder desempenho de execução


28

Gang Scheduling

Melhora a performance de uma aplicação se as threads correlatas estiverem em execução

T1 e T2 são duas threads de um mesmo processo

T1 está sendo executada: precisa sincronizar com T2

T1 fica em espera até que T2 seja executado em algum processador

seria melhor T2 já estar executando em outro processador


29

30

Gang Scheduling

• N processadores, M aplicações com N ou menos threads cada aplicação

– cada aplicação poderia receber 1/M do tempo disponível, utilizando os N processadores

– nem sempre isso é eficiente

– alocação de tempo uniforme:

1 thread A2 4 threads A1 N = 4 ocioso

P1 P2 P3 P4

100%/8 = 12,5%

12,5% X 3 = 37,5% ocioso

½ ½


31


Gang Scheduling

• uma solução: dar pesos aos processos de acordo com o número de threads

– considerando todos os processos

– A1 tem 4/5 das threads – 80%

– A2 tem 1/5 das threads - 20%

– Cada thread tem 20% do tempo

ocioso

P1 P2 P3 P4

100%/20 = 5%

5% X 3 = 15% ocioso

4/5 1/5

32

Escalonamento de Threads e Processos

• Essas classes de escalonadores discutidos, tanto para processos como threads se encontram na maioria das vezes a nível de sistemas operacionais

• Pode-se definir um escalonador que gerencie a execução de uma aplicação paralela

• middleware

Escalonamento de Aplicações em Sistemas Distribuídos

classe de aplicações

– especificada pelo modelo da aplicação

a arquitetura enfocada constitui em um sistema de processadores de memória distribuída que se comunicam por trocas de mensagens

– modelo arquitetural apresenta as características importantes a serem consideradas

33

Escalonamento de Aplicações Alguns conceitos

Tarefa – uma unidade de computação

job = conj. de tarefas com objetivo comum

aplicação paralela tarefas que seguem uma ordem parcial

34

Escalonamento de Aplicações Escalonamento local X global

global tarefas são associadas a processadores

mapeamento, task placement, matching

local várias tarefas em um processador

No escalonamento global:

- migração – custoso e nem sempre usado (sala contexto, trasfere contexto para o novo processador, reinicializa tarefa)

- geralmente se refere a balanceamento de carga

35

Escalonamento de Aplicações preempção tarefas/jobs em execução podem ser transferidas (migradas)

– mais custos

não preempção geralmente em relação às tarefas

– tarefas não são interrompidas

– migração somente para tarefas ainda por executar

36

Escalonamento de Aplicações Estático

conhecimento de características associadas às aplicações antes da execução desta (estimativas)

relação de precedência entre os componentes da aplicação

Dinâmico

estimativas são conhecidas antes da execução e não as características reais.

a especificação do escalonamento é feita ao longo da execução da aplicação

– balanceamento de carga, por exemplo

37

Escalonamento Estático de Aplicações O Problema de Escalonamento de Tarefas em um conjunto de processadores é, em sua forma geral, NP-completo.

Uma variedade de heurísticas de escalonamento foram propostas, principalmente para um conjunto de processadores homogêneos, considerando ou não custo de comunicação associado à troca de mensagens

Alguns heurísticas que consideram um conjunto de processadores homogêneos foram analiticamente avaliadas, e foi concluído que escalonamento produzidos estão dentro de um fator do ótimo.

Algumas instâncias do problema possuem solução ótima

38

Modelo da Aplicação uma aplicação da classe de aplicações abordadas é constituída por um conjunto de tarefas, ordenadas parcialmente por uma relação de precedência

a classe de aplicações aqui discutida pode ser representada por um grafo acíclico direcionado (GAD) G = (V,E, , ), onde

– as tarefas da aplicação são representadas pelo conjunto de n vértices

V = { v1 , v2 , ... , vn }

– as relações de precedência que correspondem a dependência de dados são representadas pelo conjunto de dados

E = { (vi , vj ) }

39

Modelo da Aplicação

o peso de computação (vi) pode estar associado a cada tarefa de G (estimativa) correspondendo ao número de unidades de tempo necessários para executar a tarefa vi

o peso de comunicação (vi, vj ) pode estar associado a cada arco (vi,vj) de G (estimativa) correspondendo à quantidade de dados a serem enviados da tarefa vi para a vj

seja pred (vi) o conjunto de predecessores imediatos da tarefa vi , ou seja,

pred (vi) = {vj / (vj ,vi ) E }

seja succ (vi) o conjunto de sucessores imediatos da tarefa vi , ou seja,

succ (vi) = {vj / (vi , vj ) E }

40

Modelo da Arquitetura

definição de características que afetam o desempenho

processadores homogêneos e heterogêneos

número limitado ou não de processadores

memória distribuída ou compartilhada

topologia da rede de interconexão

modelo de comunicação

– latência de comunicação

– sobrecargas de envio e recebimento

– etc

41

Heurísticas de Escalonamento Heurísticas de Escalonamento Estático

heurísticas de construção: um algoritmo polinomial no tamanho da entrada que a cada iteração, especifica para uma tarefa o seu escalonamento

– tupla (tarefa, processador, tempo de início)

– ao final, uma só solução foi formada

– escalonamento deve ser válido (respeitar as relações de precedência e as características do modelo arquitetural)

difícil classificação

– técnica empregada

– modelo considerado

42

Heurísticas de Escalonamento

Heurísticas de Escalonamento Estático

List Scheduling

Algomeração de Tarefas

Minimização de Caminho Crítico

Replicação de Tarefas

43

Restrições de Escalonamento Seja um DAG: G(V,E) e uma modelo arquitetural

• Tempo de início (start time): st(vi , pk)

• Tempo de fim (finish time): ft(vi , pk) • Alocação do processador: proc (vi)

Restrições:

• De processador: duas tarefas não podem ter sobreposição de tempo no mesmo processador

pk = proc(vi)=proc(vj)

st (vi , pk) >= ft (vj , pk) OR st (vj , pk) >= ft (vi , pk)

44

Restrições de Escalonamento Seja um DAG: G(V,E) e uma modelo arquitetural

• Tempo de início (start time): st(vi , pk)

• Tempo de fim (finish time): ft(vi , pk) • Alocação do processador: proc (vi)

Restrições:

• de precedências: uma tarefa deve começar a ser executada depois que receber todas os dados de seus predecessores

vj pred( vj ), st (vj , pk) >= ft (vi , proc(vi)) + comm (vi, vj )

45

List Scheduling Estratégia (extremamente) gulosa

tradicional e bastante conhecida (utilizada) devido a sua simplicidade (baixa complexidade)

– escalonamento de instruções em unidades funcionais

– escalonamento em processadores heterogêneos (em número limitado)

Alguns conceitos importantes

tarefa livre - todos os seus predecessores imediatos já foram escalonados;

processador ocioso - em um determinado instante tk , não existe nenhuma tarefa sendo executada neste instante;

46

List Scheduling Framework

Definição da prioridade das tarefas vi V;

Enquanto ( existir vi não escalonado ) faça {

vi = a tarefa livre de maior prioridade;

pj = o processador ocioso onde vi começa mais cedo;

escalone vi no processador pj ;

determine as novas tarefas livres;

}

47

Prioridades associada às tarefas Caminho crítico

– Caminho no grafo com o maior “comprimento”

bottom-level, top-level, etc....

Medidas para definir a importância dum nó a ordem em que as tarefas são escalonadas é muito importante

48

Um Exemplo de GAD

6

3 2 1

0

pesos de execução em

pesos dos arcos em

5

4

4

5 2 7

6

6

3

2 4 8

1 3 2

5 4

49

Replicação de Tarefas Papadimitriou e Yannakakis (PY) – princípio da replicação

grafo acíclico direcionado G = (V, E) (UET-UCT)

– pesos de execução das tarefas: unitários

– pesos dos arcos: unitários

latência de comunicação L é o custo mais relevante

número ilimitado de processadores

A idéia é replicar para minimizar o tempo de execução

50

Replicação de Tarefas

Muitos algoritmos utilizaram a idéia de replicar tarefas para não ter que realizar comunicação entre processadores – Hoje seriam entre máquinas

Mas – quais custos associados a replicação de tarefas?

– O que significa replicar a tarefa?

51

Replicação de Tarefas O que o list scheduling faria?

4

3 2 1 0

52

L

Replicação de Tarefas Podemos melhorar? Precisa replicação?

4

3 2 1 0

53

L

Replicação de Tarefas Melhor caso, não adianta replicar

4

3 2 1 0

0

1

2

3

4

L

54

L

Replicação de Tarefas Como o list scheduling faria?

4 3 2 1

0

55

L

Replicação de Tarefas Podemos fazer melhor com replicação?

4 3 2 1

0

56

L

57

Escalonamento em Tempo Real

Uma definição:

o resultado correto de um problema deve ser produzido, mas também, o tempo que leva para ser produzido é essencial

é um sistema composto de tarefas em que algumas são urgentes

Para esse classe de aplicações, o SO, e particularmente o escalonador são de crucial importância

58

Atualidade em Sistema de Tempo Real

laboratórios de controle

robótica

trafego aéreo

telecomunicações

sistemas de controle

59

Próxima geração de Sistema de Tempo Real

(... que já é atual)

carros autonômicos

controladores de robôs com juntas elásticas

fábricas inteligentes

exploração de águas profundas

etc.

60

Sistema de Tempo Real

as tarefas ou processos podem ser urgentes ou não

associado a cada tarefa

tempo de fim

deadline

hard real time task: deadline tem que ser respeitado

X

soft real time task: deseja-se atingir o deadline

61

SO para Sistema de Tempo Real

tempo de resposta de seus serviços

tempo contabilizado a partir de sua requisição

depende:

tempo da rotina de tratamento de interrupção

iniciar a rotina do serviço (troca de contexto)‏

tempo de execução do seviço

mais interrupções, se ocorrerem

62


Controle do usuário

nestes sistemas, o usuário tem maior interação com o SO para alimentar dados da aplicação a ser executada

Confiabilidade

muito importante em Sistemas de Tempo Real

falhas devem ser tratadas de forma transparente ao usuário

tolerâncias a falhas via software

salvamento de dados para recuperação de processo

manter arquivos de entrada, etc

63


Confiabilidade

com mecanismos de tolerância a falhas, problemas podem ser contornados e a execução continua

esta operação pode ter estabilidade

quando ainda com falha, os deadlines são atingidos

64


aspectos que podem ser considerados:

existe uma análise do comportamento do sistema

a análise pode ser estática ou dinâmica

de acordo com a análise, o escalonamento é produzido

65


análise estática

determina a alocação das tarefas em tempo de execução

não necessariamente determina o escalonamento, mas as prioridades entre as tarefas

o sistema pode ser preemptivo, realocar, de acordo com as essas prioridades

análise dinâmica

considerando as restrições do sistema para atingir o melhor desempenho

deadlines das tarefas são considerados

se um processo não atinge seu deadline é abortado

66


análise estática

bom para aplicações que são executadas repetidamente

problema: estimativas precisas

análise estática, que determina prioridades

uma análise a priori pode auxiliar na especificação da importância das tarefas

deadlines podem ser considerados

dinâmica

quando o sistema tem um caráter dinâmico, com tarefas chegando aleatoriamente

deadlines devem ser obedecidos

67


Escalonador de curto prazo – papel crucial

importante que as tarefas críticas (hard real time tasks) sejam executadas não ultrapassando deadlines

o máximo de tarefas não críticas devem ser executadas

Maioria de Sistemas de Tempo real

dificuldade de atingir deadlines

quando um deadline está para ser atingido, a tarefa é rapidamente escalonada

68

Escalonamento baseado em Deadlines

Nos sistemas de tempo real, as seguintes informações são utilizadas:

tempo que o processo/tarefa fica pronta

caso de tarefas periódicas – esta seqüência de tempos pode ser pré-conhecida

deadline de início e de fim

tempo que uma tarefa tem que (a partir do qual deve) começar e tempo que a tarefa deve estar terminada

tempo de processamento

em caso de desconhecimento, o SO pode usar algum modelo de previsão

69


conjunto de recursos requisitados pelas tarefas (sem ser processadores)

prioridade

tarefas críticas podem ter prioridade absoluta (tem que ser executadas o mais rápido)

caso de falha: sistema aborta

se executado de qualquer modo, prioridades são reavaliadas

estrutura da tarefa

uma tarefa pode ser um conjunto de subtarefas, algumas sendo críticas e outras não

70


Seleção e decisões

qual tarefa deve ser a próxima a ser escalonada

mais do que acabar mais rápido, é mais importante que escalone as tarefas tal que as aplicações terminem de acordo com os deadlines

não preempção

quando deadline de início devem ser utilizados, faz mais sentido visto que preempção não é permitida. Assim, dá para assegurar que a data limite de início será atingida

71


Seleção e decisões

preempção ser permitida para atingir deadline

mais apropriado quando tarefas tem deadlines de fim

Processo X está sendo executado e Y está pronto – os dois tem deadlines de fim associados

dependendo, X sofre interrupção para que Y seja escalonado para atingir seu deadline, tal que X não perca seu deadline

72


Um exemplo: tarefas periódicas – se repetem com freqüência

Tarefa A

deadlines a cada 20ms

duração de 10ms (cada período)

chega a cada 20ms

Tarefa B

deadline a cada 50ms

duração de 25ms

chega a cada 50ms

preempção é permitida

73


Processo periódicos Chegada Tempo de

Execução Deadline de fim

A(1) 0 10 20

A(2) 20 10 40

A(3) 40 10 60

A(4) 60 10 80

A(5) 80 10 100

..... ..... ..... .....

B(1) 0 25 50

B(2) 50 25 100

..... ..... ..... .....

74


Decisões são efetuadas a cada 10ms, e escalonamento por prioridade

A tem prioridade

A1

B1

A2

B1

A3

B2

A4

B2

A5

B2

10

20

30

40

50

60

70

80

90

B1 atinge deadline

75


Decisões são efetuadas a cada 10ms, e escalonamento por prioridade

B tem prioridade

B1 A2

A3

B2 A5

10

20

30

40

50

60

70

80

90

A1 atinge deadline e nem foi executado

A4 atinge deadline, poderia ter executado por 5 ut

76


Decisões são efetuadas a cada 10ms, e escalonamento por prioridade: menor deadline de fim

Menor deadline de fim

A1

B1

A2

B1 A3

A4

B2 A5

B2

10

20

30

40

50

60

70

80

90

77


Tarefas Aperiódicas – sem preempção

earliest deadline:

A será logo escalonado e B não poderá ser executado

Processo Chegada Ts Deadline

início

A 10 20 110

B 20 20 20

C 40 20 50

D 50 20 90

E 60 20 70

78


Tarefas Aperiódicas – sem preempção

menor deadline, conhecimento a priori, mesmo que o processador fique ocioso:

B é escalonado antes, mas o processador fica ocioso até este ser submetido (pois senão não será atendido devido a não preempção)

Processo Chegada Ts Deadline

início

A 10 20 110

B 20 20 20

C 40 20 50

D 50 20 90

E 60 20 70

79

Escalonamento com taxa monotônica

Rate Monotonic Scheduling (RMS)

muito usado em escalonamento de tempo real em tarefas que acontecem periodicamente

Escalonar primeiro a tarefa de maior prioridade

Prioridade: escolha da tarefa com menor tempo de serviço

considerando todas as tarefas prontas, ao ordenarmos as tempos de serviço, se observa que este tempo cresce monotonicamente

80


Em caso de tarefas periódicas, parâmetros relevantes para esse tipo de escalonamento:

tempo entre chegadas entre cada instância da tarefa = período T

o inverso deste período de tempo é a frequência (em Hz)

tempo de execução da tarefa C

C <= T

se a tarefa sempre é executada até seu término, a utilização do processador é

U = C/T

81


a política garante ou não que tarefas críticas encontrem seus deadlines

Suponha que existam n tarefas. Para que todas encontrem seus deadlines é preciso que:

U(n) = C1/T1 + C2/T2 + .... + Cn/Tn <= 1

quer dizer, a soma de utilização de processador não pode ultrapassar de 1

quando igual a 1: o processador está sendo totalmente utilizado

82


Limite superior UL(n)

Liu e Layland (1973) mostraram que para um conjunto de n tarefas periodas um escalonamento viável que alcança os deadlines é possível, se a utilização da CPU está de acordo com o limite

UL(n) = C1/T1 + C2/T2 + .... + Cn/Tn <= n (21/n – 1)

isso depende do número de tarefas

83


UL(n) = C1/T1 + C2/T2 + .... + Cn/Tn <= n (21/n – 1)

n UL(n) = n (21/n – 1)

1 1.0

2 0,828

3 0,779

4 0,756

5 0,743

6 0,734

..... .....

∞ ln 2 = 0,693

84


Suponha que existam três tarefas periódicas tal que Ui = Ci/Ti

O limite superior para que as três tarefas sejam escalonáves, usando escalonamento monotônico RMS, é :

UL(3) = C1/T1 + C2/T2 + C3/T3 <= 3 (21/3– 1) = 0,779

Como a utilização total de processador para as três tarefas é menor que o limite superior para o RMS então é possível executá-las de acordo com o RMS

Tarefa Ci Ti (período) Ui

P1 20 100 0,2

P2 40 150 0,267

P3 100 350 0,286

U(3) = 0,753

85


Também pode ser comprovado que o limite superior da utilização de processador pode ser utilizado para escalonamento com a prioridade:

Deadline mais cedo

86


Considere as tarefas Pi com (Ci , Ti) associados

{(1,3),(1,5),(1,6),(3,10)}

Qual a utilização de CPU:

Qual o limite superior

Conclusão?

87



{(1,3),(1,5),(1,6),(3,10)}

Qual a utilização de CPU:

U (4) = 1/3 + 1/5 + 1/6 + 3/10 = 0.899

Qual o limite superior

UL(4) = 4 (21/4– 1) = 0.756

Conclusão?

as quatro tarefas não são escalonáveis

88



{(1,3),(1,5),(1,6),(3,10)}

E as três primeiras tarefas?

89



{(1,3),(1,5),(1,6),(3,10)}

E as três primeiras tarefas?

U(3)= 1/3 + 1/5 + 1/6 = 0.699

UL (3) = 0.779

Logo: as três primeiras tarefas são escalonáveis.

Documents

Desempenho de computação paralela - UFFboeres/slides_AP/DesempenhoOpt.pdf · Shortest remaining time (SRT) • seleção: processo que precisa de menor tempo para terminar ... O