Evolução Arquitetural e Microprogramação

Prof. César Augusto M. Marcon

ARQUITETURA DE COMPUTADORES II

2 / 24

Índice

1. Evolução das Arquiteturas

2. Multiprogramação

3 / 24

Evolução das Arquiteturas

• Arquitetura Tradicional– Uma única unidade ativa

MemóriaMemória

SSCPUCPUEE

MemóriaMemória

SSCPUCPUEE• Unidades de E/S autônomas– Multiprogramação

• Hierarquia de Memória– Acelerar alimentação da CPU

MemóriaMemória

SSCPUCPUEE

L2L2

L1L1

4 / 24

Evolução das Arquiteturas

• Pipeline

– Separa memória de dados e instruções– Pipe de instrução (superescalar)– Pipe de dados (máquinas vetoriais)

SSEEFF DD WWEE

FF DD WWEEFF DD WWEECPUCPU

MemóriaMemória

L2L2

L1L1

• Diversas técnicas arquiteturais

5 / 24

Considerações

• Processamento paralelo implica várias unidades simultaneamente ativas

• Processador é uma unidade ativa, mas não a única– Partes autônomas dentro do processador, como ULAs – Sistemas autônomos fora do processador, como unidades de E/S

• Processamento paralelo pode também existir em máquinas com apenas um processador

6 / 24

Índice

1. Evolução das Arquiteturas

2. Multiprogramação

7 / 24

Multiprogramação

• Conceito– Técnica para executar simultaneamente vários processos

• Habilitador– Unidades de E/S se tornaram ativas Executam operações de forma

autônoma liberando processador para outras tarefas

• Funcionalidade– SO intercala CPU e E/S entre diferentes processos

– Quando técnica é bem aplicada dá impressão de paralelismo espacial

• Paralelismos– Processamento paralelo espacial entre CPU e unidades de E/S

– Processamento paralelo temporal entre diferentes processos

• Objetivos– Aumentar taxa de utilização do processador mantê-lo ocupado maior parte

do tempo

– Aumentar chance do SO encontrar processo pronto para rodar (que não esteja esperando por E/S)

8 / 24

Multiprogramação

• Exemplo de multiprogramação considerando CPU e E/S unidades autônomas

i1 o1

c1 i2 o2

c2 i3 o3

c3

P1 P2 P3

c1 c2 c3CPU

i1 o1

c1

P1

i2 o2P2

i3 o3

c3P3

Ganho de tempo

i1 i2 o1 i3 o2 o3E/S

c2 Devido a CPU operar em paralelo com E/S

9 / 24

Multiprogramação

• A redução do tempo total de execução de aplicações depende de técnicas a serem aplicadas, tais como:

– Escalonamento com time-sharing para a execução das tarefas

– Alteração da ordem de chegada das tarefas– Múltiplas unidades de E/S

10 / 24 MultiprogramaçãoCompartilhamento Temporal (Time Sharing)

• Funcionalidade– Processos são executados em fatias de tempo (time-slices)

– Ao termino da fatia, novos processos são escalonados• Processo preemptado vai para final da fila de pronto

• Vantagens– Consegue atender todos processos

– Tempo de resposta aceitável para aplicações não críticas

– Evita que processos CPU bound tomem conta do processador

• Compromissos– Time-slice muito pequeno muita troca de processos alto custo para o

sistema por causa do salvamento de contexto

– Achar time-slice que seja bom compromisso entre qualidade e custo

11 / 24 MultiprogramaçãoAlteração da Ordem de Chegada

• Alteração da ordem de chegada de tarefas é atribuição do escalonador• Escalonamento

– Normalmente executado por um SO– Depende das necessidades da aplicação e características da arquitetura alvo e SO

• Algoritmos de escalonamento– FIFO (First In First Out)

• Primeiro a chegar é o primeiro a ser atendido– RR (Round-Robin)

• Todo processo executa uma fatia de tempo (time-slice) e depois é escalonado o próximo• Processos são executados como uma FIFO, enquanto não terminarem

– SJF (Smallest Job First)• Tarefas mais rápidas executadas primeiro• Evita que processos demorados elevem tempo de atendimento dos demais

– RM (Rate Monotonic)• Tarefas que tem menor período são atendidas antes

– EDF (Earliest deadline First)• Tarefas que tem deadline mais perto são atendidas antes• Escalonamento dinâmico• Utilizado com tarefas de tempo real

– ...• Considerações de Alteração de Ordem de Chegada e Time-slice

– Time-slices muito grande fazem comportamento do sistema parecer com FIFO, time-slices muito pequenos parecem com SJF (Smallest Job First)

12 / 24 Multiprogramação Alteração da Ordem de Chegada

• Aplicação cj. de tarefas

= {1, 2}

• Tarefas

= (período, computação)

• Exemplo

= {(5, 1), (7, 3)}

U = 1 / 5 + 3 / 7

= 0.63 < ln 2

escalonável por RM

• Fator de utilização

Exemplo de escalonamento RM (tarefas periódicas)

13 / 24

= {(5, 2), (7, 4)} : U = 2 / 5 + 4 / 7 = 34 / 35 = 0.97

0.97 < 1 escalonável por EDF

0.97 > ln 2 não escalonável por RM tarefa perde deadline

Multiprogramação Alteração da Ordem de Chegada

Exemplos de escalonamento RM e EDF

14 / 24 MultiprogramaçãoUtilização de Múltiplas Unidades de E/S

• Objetivo– Aumentar desempenho geral do sistema pela redução do gargalo de

entrada e saída de informações

• Como alcançar– Aumentando número de unidades de E/S que participam do

processamento paralelo

• Conseqüência– Escalonador pode tratar vários pedidos de E/S simultaneamente– Aumento do Speed-Up (fator de aceleração) – Redução do tempo de execução de vários processos

15 / 24

Multiprogramação

• Aplicando as otimizações vistasI. Alteração da ordem de chegadaII. Múltiplas unidades E/SIII. Escalonamento com time-sharing

i1 o1

c1 i2 o2

c2 i3 o3

c3

P1 P2 P3

P2

P3

P1

Ganho de tempo

i2

c2

i3

c2

c3

i1

c3

c1 o1

o2

o3

c1

c3

i1 o1

c1

P1

i2 o2P2

i3 o3

c3P3

Ganho de tempo

c2Devido a CPU operar em paralelo com E/S

Devido aos itens I, II e III

16 / 24

1. Dada uma aplicação composta por 2 tarefas (T0 e T1), sendo estas tarefas caracterizadas (em ns) em uma arquitetura alvo hipotética conforme tabela abaixo, faça um gráfico que mostre o uso da CPU e de uma entrada e saída

2. Verifique se a aplicação caracterizada acima é escalonável por Rate Monotonic (RM). Faça o mesmo para Earliest deadline First (EDF). Considere os seguintes dados a mais:

– Utilize as técnicas aprendidas em multiprogramação para obter redução do tempo de execução global do sistema descrito, sendo estas:

• time-sharing

• múltiplas entradas e saídas

• alteração da ordem de chegada

– Dados para os exercícios • Sistema operacional com time-slice de 1ns

• Troca de contexto com tempo desprezível

• Processador com 2 unidades de entrada e saída

Tarefas Instante de chegada Entrada de dados Computação Saída de dados Período / DeadlineT0 0 2 3 2 10T1 2 1 4 1 8

Exercícios

17 / 24

Resposta de Exercícios

Exercício 1

18 / 24

Resposta de Exercícios

Exercício 2

19 / 24

1. Como a multiprogramação acelera a execução de um grupo de programas mesmo em uma máquina com apenas um processador?

2. Comente a afirmação: - ”A replicação de unidades de entrada e saída é um paralelismo em nível de aplicação”

3. Mostre algumas técnicas que podem ser utilizadas para melhorar o uso da CPU com multiprogramação. Mostre também as conseqüências do uso destas técnicas

4. Qual o grande problema da otimização tipo time sharing com time-slices muito pequenos? E com time-slices muito grandes?

Exercícios

20 / 24

5. (ENADE 2008 - 59) No projeto de sistemas de tempo real, normalmente são atribuídas prioridades às tarefas. Escalonadores orientados à preempção por prioridade são utilizados para ordenar a execução de tarefas de modo a atender seus requisitos temporais. Inversão de prioridade é o termo utilizado para descrever a situação na qual a execução de uma tarefa de mais alta prioridade é suspensa em benefício de uma tarefa de menor prioridade. A inversão de prioridade pode ocorrer quando tarefas com diferentes prioridades necessitam utilizar um mesmo recurso simultaneamente. A duração desta inversão pode ser longa o suficiente para causar a perda do deadline das tarefas suspensas. Protocolos de sincronização em tempo real auxiliam limitando e minimizando a inversão de prioridades. Considere o conjunto de três tarefas com as seguintes características:a. T1 tem prioridade 1 (mais alta), custo de execução total de 6 ut (unidades de tempo) e instante de

chegada t1 = 6. A partir de seu início, após executar durante 1 ut, essa tarefa necessita do recurso compartilhado R1 durante 2 ut. Para concluir, utiliza o recurso compartilhado R2 durante 2 ut finais.

b. T2 tem prioridade 2, custo de execução total de 8 ut e instante de chegada t2 = 3. A partir de seu início, após executar durante 2 ut, a tarefa necessita do recurso compartilhado R2 durante 2 ut.

c. T3 tem prioridade 3 (mais baixa), custo total de execução de 12 ut e instante de chegada t3 = 0. A partir de seu início, após executar durante 2 ut, essa tarefa necessita do recurso compartilhado R1 durante 2 ut.

• A partir dessas informações, desenhe a(s) linha(s) de tempo(s) para que um escalonamento dessas três tarefas em um único processador seja possível, utilizando-se o protocolo de herança de prioridade. Neste protocolo, enquanto uma tarefa de maior prioridade necessitar usar um recurso compartilhado com uma tarefa de menor prioridade, a tarefa de menor prioridade herda a prioridade da tarefa de mais alta prioridade.

Exercícios

21 / 24

5. Resposta:

• No momento em que a tarefa T1 inicia, o recurso R2 está sendo usado pela tarefa T2, portanto bloqueado, e o recurso R1 está sendo usado pela tarefa T3, bloqueado também. Quando T1 requisita o recurso R1, fica bloqueada, pois R1 está em uso por T3. Com o protocolo de herança de prioridade, a tarefa T3 herda a prioridade de T1. Com isso, ganha o processador, pois passa a ter prioridade maior que T2. Desta forma, conclui o uso do recurso R1 e o libera. A tarefa T3 retorna à sua prioridade original e a tarefa T1 ganha o processador (pois é a de maior prioridade). Com isso, adquire, utiliza e libera o recurso R1 e continua a execução até solicitar o recurso R2, que está bloqueado pela tarefa T2. A tarefa T2 herda a prioridade de T1, conclui o uso do recurso R2 e o libera, retornando à sua prioridade original. Com isso, novamente a tarefa T1 ganha o processador e passa agora a utilizar o recurso R2, e depois o libera.

Resposta de Exercícios

22 / 24

6. Qual a importância do escalonamento de tarefas na multiprogramação, em relação ao tempo de execução global? Em relação à execução de programas de tempo real?

7. Mostre alguns algoritmos de escalonamento para aplicações de tempo real e a sua funcionalidade

Exercícios

23 / 24

6. Qual a importância do escalonamento de tarefas na multiprogramação, em relação ao tempo de execução global? Em relação à execução de programas de tempo real?

• Caso alguma tarefa não esteja utilizando a CPU, ela pode ser preemptada, sendo escalonada uma nova tarefa, de forma que a CPU fique sempre ocupada. Desta forma, o tempo de execução global tende a reduzir.

• Sistemas de tempo real se beneficiam do escalonamento possibilitando que tarefas de tempo real tenham privilégio de uso da CPU conforme seus deadlines.

7. Mostre alguns algoritmos de escalonamento para aplicações de tempo real e a sua funcionalidade

• Rate-monotonic (RM): escalonamento estático. Tarefas com menor período são priorizadas pelo escalonador.

• Earliest deadline first (EDF): escalonamento dinâmico. Tarefas com o deadline mais próximo são priorizadas pelo escalonador.

Resposta de Exercícios

24 / 24

• Utilize as técnicas aprendidas em multiprogramação para obter redução do tempo de execução global do sistema descrito, sendo estas:

– time-sharing– múltiplas entradas e saídas– alteração da ordem de chegada

• Dados para os exercícios – Sistema operacional com time-slice de 1ns– Troca de contexto com tempo desprezível– Processador com 2 unidades de entrada e saída– Característica das tarefas frente à arquitetura alvo, considerando os tempos em ns

1. Faça um gráfico sem aplicar as técnicas2. Faça um gráfico para a aplicação de cada técnica3. Faça agora um gráfico que utilize as 3 técnicas conjuntas4. Verifique se a aplicação é escalonável por rate monotonic e por EDF5. Faça um gráfico comparando escalonamentos round-robin, rate monotonic e EDF,

tendo os recursos disponíveis acima

Tarefas Instante de chegada Entrada de dados Computação Saída de dados Período / DeadlineT0 3 1 4 1 10T1 1 2 2 3 9T2 2 1 3 1 12

Exercícios