51
BC1518-Sistemas Operacionais Escalonamento Escalonamento de CPU de CPU Prof. Marcelo Z. do Nascimento [email protected] Escalonamento Escalonamento de CPU de CPU 3° ° ° ° ° Quadrimestre uadrimestre de 2010 de 2010

bc1518 ufabc SO Aula 04 Escalonamento de cpuhostel.ufabc.edu.br/~marcelo.nascimento/BC1518Q3... · Escalonamento de CPU 12 Quando CPU é liberada, ... Escalonador mantém uma lista

  • Upload
    hakhue

  • View
    222

  • Download
    0

Embed Size (px)

Citation preview

BC1518-Sistemas Operacionais

EscalonamentoEscalonamento de CPUde CPU

Prof. Marcelo Z. do Nascimento

[email protected]

EscalonamentoEscalonamento de CPUde CPU33°°°°°°°° QQuadrimestreuadrimestre de 2010de 2010

Roteiro�Conceito

�Despachante

�Critérios de escalonamento

�Algoritmos de escalonamento�Algoritmos de escalonamento

�Escalonamento em múltiplos processadores;

�Exemplos em Sistemas Operacionais;

�Leituras sugeridas;

�Exercícios.

Conceito

Quando a CPU precisa decidir se executa um

processo que atualiza a tela depois que um usuário

fecha uma janela, ou executa um processo que envia

mensagem eletrônica em um sistema multiprogramação.

3

A escolha faz uma enorme diferença para a percepção do usuário

Conceito

• Os processos alternam entre 2

estados: CPU e E/S;

• Começa com um burst (surto) de

CPU e burst de E/S;

4

• Programa I/O-bound => muitos

burst de CPU curtos;

• Programa CPU-bound-> alguns burst

de CPU longos.

• Importante na seleção de um

algoritmo de escalonamento.

Ciclo de burts

Conceito

Pronto Em execução

tempo

5

Bloqueado

seleçãoEspera por I/O ou evento

Conclusão de I/O ou evento

Conceito

Situações nas quais escalonamento é necessário:

�� Um novo processo é criado e passa para estado de pronto;Um novo processo é criado e passa para estado de pronto;

�� Um processo terminou sua execução e um processo pronto Um processo terminou sua execução e um processo pronto deve ser executado;deve ser executado;

6

�� Processo é bloqueado (dependência de E/S)=> outro deve ser Processo é bloqueado (dependência de E/S)=> outro deve ser executado;executado;

�� Interrupção de E/S, o escalonador deve decidir por: Interrupção de E/S, o escalonador deve decidir por:

••Executar o processo que estava esperando esse evento; Executar o processo que estava esperando esse evento;

••Continuar executando o processo que já estava sendo Continuar executando o processo que já estava sendo executado.executado.

Escalonamento

� S.O. escolhe qual processo deve ser executado na CPU

=> Escalonador de CPU;

� Escalonador deve se preocupar com a eficiência da

CPU, pois o chaveamento de processos é complexo e

custoso:

7

custoso:

� Afeta desempenho do sistema e satisfação do usuário.

� Algoritmos que realizam o chaveamento de processos

prontos para executar de acordo com regras bem

estabelecidas.

O esquema de escalonamento:

� Não preemptivo (cooperativo): Não permite

interrupções externa à tarefa até que seja liberado pelo

seu término ou pela troca para o estado esperando.� Exemplo: Windows 3.x.

Escalonamento

8

� Exemplo: Windows 3.x.

� Preemptivo: Interrompe a execução de uma tarefa e

transfere a CPU para outro; � Necessário mecanismo para coordenar acesso aos dados;

� Afeta o projeto de Kernel do SO => mudanças de filas E/S;

� Chamada de sistema deve ser concluída antes da troca;

� Exemplo: Windows XP, Mac OS X.

� Componente envolvido na função do escalonador de

CPU;

� Módulo que dá o controle da CPU ao processo;

� Função:� Trocar o contexto;

Trocar para o modo usuário;

Despachante

9

� Trocar para o modo usuário;

� Desviar para local apropriado no programa de usuário.

� Chamado durante a troca de processo;

� Tempo gasto para interromper um processo e iniciar a

execução de outro definido por latência de despacho.

Critérios para escalonamento

� Utilização de CPU:

� manter a CPU tão ocupada quanto possível Maximizar;

� Vazão (throughput):

número de processos que completam sua execução por

10

� número de processos que completam sua execução por

unidade de tempo. Maximizar;

� Tempo de Proporcionalidade:

� quantidade tempo para executar um processo particular.

Minimizar;

� Tempo de Espera:

� quantidade de tempo que um processo espera na fila dos prontos. Minimizar;

Tempo de Resposta:

Critérios para escalonamento

11

� Tempo de Resposta:

� quantidade de tempo que leva de quanto um pedido foi feito até que a primeira resposta seja produzida, não a saída (para ambientes de tempo - compartilhado) Minimizar;

� Algoritmo de escalonamento FIFO (first in, first out));

� Processo que solicita a CPU primeiro, a recebe primeiro.

� Quando processo entra na fila de pronto, seu PCB é

ligado ao final da fila.

Escalonamento de CPU

12

� Quando CPU é liberada, ela é alocada ao processo no

início da fila.

� Tempo de espera normalmente longo;

� Efeito comboio: todos os outros processo aguardam

quando há um grande processo em execução na CPU.

Interrupção qualquer(E/S)

CPU

Fila de entrada

Primeiro a chegar, primeiro a ser atendido (PCPA)

13

(E/S) 0

Fila de entrada

23 1

CPU

Fila de entrada

Primeiro a chegar, primeiro a ser atendido (PCPA)

14

CPU não controla o tempo dos processos!(não-preemptivo)

1Fila de entrada

30 2

Exemplo: prog A (15 milissegundos),

B (2 milissegundos)

C (1 milisegundo).

Tempo pode variar substancialmente se os tempos de retorno da CPU variarem

muito

Primeiro a chegar, primeiro a ser atendido (PCPA)

15

A linha de tempo (diagrama de Gantt) é

0 15 18

A CB

17

0 1 18

AC B

3

Tempo médio = 16,67

Tempo médio = 7,3

Tempo de retorno

Vantagem:

� fácil de implementar.

Desvantagem:

Primeiro a chegar, primeiro a ser atendido (PCPA)

16

Desvantagem:

� tempo de retorno imprevisíveis.

� problemático em sistemas de tempo compartilhado.

Programa menor primeiro (MP)

� Algoritmo Shortest job first (SJF);

� Associa a cada processo o tamanho do próximo burst de

CPU do processo;

� A CPU atribui o processo que tem o próximo retorno de

17

CPU menor (burst);

� Em caso de empate (tempo de retorno) dos processo, o

algoritmo FIFO é utilizado;

� Não preemptivo e trabalha de acordo com a extensão

de seus ciclos de CPU.

Exemplo: Programas A B C D

ciclo de CPU 5 2 6 4

A linha de tempo (diagrama de Gantt) é

Programa menor primeiro (MP)

18

0 2 17

B D

11

Tempo médio = 9,0A C

6

Se fosse utilizado o FIFO, o tempo médio seria de 10,5

A B C D

8 44 4

Em ordem:

B C D A

4 44 8

Menor job primeiro:

Programa menor primeiro (MP)

19

Em ordem:retorno A = 8retorno B = 12retorno C = 16retorno D = 20Média K 56/4 = 14

Menor job primeiro:retorno B = 4retorno C = 8retorno D = 12retorno A = 20Média K 44/4 = 11

Vantagem:

� minimiza tempo médio de espera;

Desvantagem:

� adiantamento indefinido de alguns programas, ou

Programa menor primeiro (MP)

20

� adiantamento indefinido de alguns programas, ou

seja, não há como saber a extensão do próximo burst

de CPU.

Menor tempo restante (MTR)

� Preemptivo do MP;

� Processos com menor tempo de execução são executados primeiro;

21

� Se um processo novo chega e seu tempo de execução é menor do que do processo corrente na CPU, a CPU suspende o processo corrente e executa o processo que acabou de chegar;

� Requer conhecimento prévio do tempo de CPU (sistema em lote).

Exemplo: Tempo de chegada 0 1 2 3 (distante em 1 ciclo de CPU)

Programa A B C D

Ciclo de CPU 6 3 1 4

A linha de tempo (diagrama de Gantt) é

Menor tempo restante (MTR)

22

0 1

DA B C B A

2 3 5 9 14

Programa A B C D

Tempo retorno 14 4 1 6Tempo médio = 6,25

A linha de tempo (diagrama de Gantt) é

MP teria um tempo médio de 7,75

Vantagem:

� garante execução rápida de programas importantes.

Desvantagem:

Menor tempo restante (MTR)

23

Desvantagem:

� sobrecarga com mudanças de contexto;

Escalonamento de CPU

� Algoritmos para Sistemas Interativos:

� Alternância circular (Round-Robin);

� Prioridades;

� Filas múltiplas;

24

� Filas múltiplas;

� Próximo processo mais curto (Shortest Process Next);

� Garantido;

� Loteria;

� Fração justa (Fair-Share).

� Algoritmo alternância circular (AC)

� Escalonanento Round-Robin;

� Tempo compartilhado;

� Preemptivo;

Escalonamento de CPU

25

� Cada processo recebe um tempo de execução chamado quantum; ao final desse tempo, o processo é bloqueado e outro processo é colocado em execução;

� Escalonador mantém uma lista de processos prontos.

� Trabalha primeiro a chegar, primeiro a ser atendido.

Ex.: Tempo de chegada 0 1 2 3

Programa A B C D

Ciclo de CPU 8 4 9 5

Algoritmo alternância circular (AC)

26

Ciclo de CPU 8 4 9 5

A B C

8 25

Programa A B C D

Tempo retorno 20 7 24 22Tempo médio = 18,25

12

16

D A C

20

24

D C

26

0 4

quantum

Vantagem:

� proporciona tempos de resposta razoáveis para usuários interativo.

Desvantagem:

Algoritmo alternância circular (AC)

27

� requer seleção de quantum de tempo ideal;

� se for muito pequeno, ocorrem muitas trocas diminuindo, assim, a eficiência da CPU; se for muito longo o tempo de resposta é comprometido.

� Associa-se a cada processo um nível de prioridade, deacordo com os interesses do sistema.

Exemplo: Gerenciador da CPU determina a prioridadepara programas que:

Algoritmo com Prioridade

Escalonamento de CPU

28

�Necessidade de memória;

�Tempo total de CPU;

�Número e tipo de dispositivos periféricos.

� Cada processo possui uma prioridade => os processos

prontos com maior prioridade são executados

primeiro;

� Prioridades podem ser dinâmica ou estática;

Estática -> um processo é criado com uma

Algoritmo com Prioridade

29

� Estática -> um processo é criado com uma

determinada prioridade e esta prioridade é mantida

durante todo o tempo de vida;

�Dinâmica -> prioridade do processo é ajustada de

acordo com o estado de execução do processo e/ou

sistema.

� Escalonamento de alta e baixa prioridade:� Indicadas por algum intervalo de número;

� Não existe um acordo geral sobre se 0 é de maior ou menor prioridade;

� Exemplo:

Algoritmo com Prioridade

30

� Exemplo: � ajustar a prioridade em função da fração quantum que foi

realmente utilizado pelo processo;

� Classes de processos com mesma prioridade;

� Agendados para executar em ordem FIFO;

� Preemptivo ou não preemptivo;

mais altaFILAS

• Agrupar processos em classes de prioridades

• Dentro de cada classe usar o escalonamento circular

Algoritmo com Prioridade

31

1

2

3

4mais alta

mais baixa

prioridade

FILAS

processos prontos(Round-Robin)

Vantagem:

� garante execução rápida de programas importantes.

Desvantagem:

� Adiantamento indefinido de alguns programas;

Algoritmo com Prioridade

32

Adiantamento indefinido de alguns programas;

� Um processo de baixa prioridade não pode executar.

� Solução: técnica do envelhecimento

� busca aumentar gradualmente a prioridade do processo

que estão no sistema por um longo tempo.

� Filas múltiplas (multinível):

� Divide a fila de prontos em várias filas separadas;

� CTSS (Compatible Time Sharing System);

� Cada processo é atribuído a uma fila:

� Exemplo: prioridades, tipo de processo;

Escalonamento de CPU

33

� Exemplo: prioridades, tipo de processo;

� Cada fila de prioridade possui quantum diferente;

� Cada fila tem seu próprio algoritmo de escalonamento (ex.: FIFO, MP);

� Escalonamento entre as filas:

� Exemplo: Primeiro plano e segundo plano.

� Preemptivo.

Filas multinível

34

Fila multinível com feedback

• Filas múltiplas com realimentação• Permite que um processo se mova entre as filas;• Separar de acordo com burst de CPU;

• Se utilizar muito tempo da CPU é movido para uma fila de menor prioridade;

• Processos de menor prioridade são executados por um

35

• Processos de menor prioridade são executados por um quantum processos

• Se necessário dois quantum na próxima classe e quatro quantum e assim por diante.

Este algoritmo diminui o número de comutações da CPU entre os processos ativos

Fila multinível com feedback

• Um processo entra na fila

F0 a qual emprega o FIFO. • Quando entra em execução

recebe 8 milisegundos.

• Se não finalizar em 8

milisegundos e movido para

36

milisegundos e movido para

a fila F1. • Em F1 é recebe 16

milisegundos para FIFO;

• Se ainda não concluir e

movida para próxima fila.

� Algoritmo próximo processo mais curto� Mesma idéia do Shortest Job First dos sistemas em lote;

Problema: Processos Interativos não se conhece o

Escalonamento de CPU

37

� Problema: Processos Interativos não se conhece o tempo necessário para execução;

� Como empregar esse algoritmo: ESTIMATIVA de TEMPO.

� Algoritmo garantido:� Garantias são dadas aos processos dos usuários:

� n usuários -> 1/n do tempo de CPU para cada usuários;

� Algoritmo por loteria:Cada processo recebe tickets que lhe dão direito de

Escalonamento de CPU

38

� Cada processo recebe tickets que lhe dão direito de execução;

� Algoritmo por fração justa:� O dono do processo é levado em conta;� Se um usuário A possui mais processos que um usuário B, o usuário A terá prioridade no uso da CPU;

� Sistema homogêneo – termos de funcionamento;

� Técnicas de multiprocessamento:

� Assimétrica: Escalonamento, processamento de E/S

tratadas pelo servidor mestre. Os demais equipamentos

Escalonamento em múltiplos processadores

39

tratadas pelo servidor mestre. Os demais equipamentos

executam somente código do usuário;

� Simétrico (SMP):cada processador é auto-escalonado. Os

processos podem estar numa fila de pronto ou cada CPU tem

sua fila de prontos.

� Exemplo: Windows XP, Linux, Mac OS X.

Afinidade:

� Auto custo de invalidação e preenchimento dos caches

pela troca de processos em uma CPU;

� Maioria dos sistemas SMP tenta evitar a migração de

processo de uma CPU para outra –> afinidade de

Escalonamento em múltiplos processadores

40

processo de uma CPU para outra –> afinidade de

processador

� Podemos ter:

� Afinidade flexível: tenta manter o processo em execução no

mesmo processador, mas não há garantia.

� Afinidade rígido: especifica o processador e não deve migrar

para outras CPUs.

Balanceamento de Carga:

� O Balanceamento busca manter a carga de trabalho distribuída

uniformente entre todas as CPUs num sistema SMP

� Necessário em sistemas em que cada CPU tem sua própria fila

privada de processos elegíveis para execução;

Escalonamento em múltiplos processadores

41

� Duas técnicas são aplicadas:

� Migração Push: uma tarefa específica verifica periodicamente a carga

de cada CPU e eventualmente distribui ela movendo (pushing) a tarefa;

� Migração Pull: CPU ociosa puxa uma tarefa esperando de um

processador ocupado

� Alguns sistemas implementam ambas - exemplo: Linux.

� O balanceamento se opõe aos benefícios da afinidade do processador

Escalonamento de CPU

� Tempo é um fator crítico;

� Produzir saídas corretas em determinado momento

� Exemplos de sistemas críticos:

� Aviões;

Hospitais;

42

� Hospitais;

� Usinas Nucleares;

� Bancos;

� Multimídia;

� Importante: obter respostas em atraso e tão ruim quanto não obter respostas;

Sistemas em Tempo Real

� Tipos de STR:

� Hard Real Time: atrasos não são tolerados;� Aviões, usinas nucleares, hospitais;� Ex. responder as altas temperaturas no núcleo de uma usina nuclear;

43

de uma usina nuclear;

� Soft Real Time: atrasos são tolerados;� Bancos; Multimídia;� Ex. coletar dados de controle de tráfego aéreo a cada segundo;

Sistemas em Tempo Real

� Tipos de STR:

� Eventos causam a execução de processos:� Síncronos: ocorrem em intervalos regulares de tempo;

44

tempo;� Assíncronos: ocorrem em intervalores irregulares de tempo;

� Algoritmos podem ser:

� estáticos (tomada da decisão antes de iniciar) ou

� dinâmicos (não apresentam essas restrições).

� Escalonador preemptivo baseado em prioridade;� A thread de prioridade mais alta sempre será executada

primeira

� Prioridade pode mudar – decrementa após o tempo quantum de execução;

� Há 32 níveis de prioridade, sendo separada em filas

Windows XP - Escalonador

� Há 32 níveis de prioridade, sendo separada em filas

� Classe de Real-time (fixo): níveis 16 a 31

� Outras classes (variável): níveis 1 a 15.

� Baseado em prioridade com dois intervalos:

� Tempo Real: 0 a 99

� Nice: 100 a 140 (de -20 a 19)

� Tarefa de mais alta prioridade tem maior quantum de CPU diferente do Win XP e Solaris

Linux - Escalonador

� Execução: ciclo de bursts de CPU e E/S

� Escalonador seleciona um processo na fila de

pronto;

� Despachante executa a comutação

Algoritmos de escalonamento

Aula 05 - Sumário

� Algoritmos de escalonamento

� FIFO, MP, MTR, AC, Prioridade, Fila multiníveis

� Escalonamento em multiprocessador

� Afinidade versus balanciamento

Leituras Sugeridas

� Silberschatz, A., Galvin, P. B. Gagne, G. Sistemas Operacionais com Java. 7º , edição. Editora, Campus, 2008 .

� Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg. Fundamentos de Baer; Gagne, Greg. Fundamentos de sistemas operacionais. 6 ed. Rio de Janeiro: LTC, 2009.

Acesse o link abaixo:

http://hostel.ufabc.edu.br/~marcelo.nascimento/

Nota de Aula

Obrigado!!!

Exercícios1 - Considere que cinco processos sejam criados no instante de tempo0 (P1 , P2, P3 , P4 e P5) e possuam as características descritas natabela a seguir:

50

Desenhe um diagrama ilustrando o escalonamento dos processos e seus respectivos tempos de retorno, segundo as políticas especificadas a seguir. O tempo de troca de contexto deve ser desconsiderado.

a) FIFO b) MPc) MTR

Exercícios2- Considere o seguinte conjunto de processos, com o ciclo de CPU expresso em milessegundos:Processo Ciclo PrioridadeP1 10 3P2 1 1P3 2 3P4 1 4P5 5 2

Os processos são considerados como tendo chegado na ordem P1, P2 , P3, P4, P5, todos no instante 0.

51

P4, P5, todos no instante 0.

a- Desenhe quatro diagramas de Gantt que ilustrem a execução desses processos usando o escalonamento PCPA, MP, por prioridade não preemptiva (um número de prioridade mais baixo) e AC (alternância circular - quantum = 1).b - Qual é o tempo de retorno de cada processo para cada um dos algoritmos de escalonamento do item 1.c - Qual dos escalonamento do item 1 resulta no tempo de retorno médio mínimo (em relação a todos os processos).d- Defina a diferença entre escalonamento preemptivo e não-preemptivo?