Escalonamento de CPU - marcelo.nascimento/BC1518/aulas/bc1518_ufabc... · Escalonamento de CPU 2 ...…

Embed Size (px)

Text of Escalonamento de CPU - marcelo.nascimento/BC1518/aulas/bc1518_ufabc... · Escalonamento de CPU 2...

  • Prof. Marcelo Z. do Nascimento

    marcelo.nascimento@ufabc.edu.br

    BC1518-Sistemas Operacionais

    EscalonamentoEscalonamento de CPUde CPU22 QQuadrimestreuadrimestre de 2010de 2010

    ((aulaaula 05)05)

    RoteiroConceito

    Despachante

    Critrios de escalonamento

    Algoritmos de escalonamento

    Escalonamento em mltiplos processadores;

    Exemplos em Sistemas Operacionais;

    Leituras sugeridas;

    Exerccios.

  • 3

    Conceito

    Quando a CPU precisa decidir se executa um

    processo que atualiza a tela depois que um usurio

    fecha uma janela, ou executa um processo que envia

    mensagem eletrnica em um sistema multiprogramao.

    A escolha faz uma enorme diferena para a percepo do usurio

    4

    Conceito

    Os processos alternam entre 2

    estados: CPU e E/S;

    Comea com um burst (surto) de

    CPU e burst de E/S; Programa I/O-bound => muitos

    burst de CPU curtos;

    Programa CPU-bound-> alguns burst

    de CPU longos.

    Importante na seleo de um

    algoritmo de escalonamento.

    Ciclo de burts

  • 5

    Conceito

    Bloqueado

    Pronto Em execuo

    tempo

    seleoEspera por I/O ouevento

    Concluso de I/O ouevento

    6

    Conceito

    Situaes nas quais escalonamento necessrio:

    Um novo Um novo processoprocesso criadocriado e e passapassa parapara estadoestado de pronto;de pronto;

    Um Um processoprocesso terminouterminou suasua execuexecuoo e um e um processoprocesso pronto pronto devedeve ser ser executadoexecutado;;

    ProcessoProcesso bloqueadobloqueado ((dependnciadependncia de E/S)=> de E/S)=> outrooutro devedeve ser ser executadoexecutado;;

    InterrupInterrupoo de E/S, o de E/S, o escalonadorescalonador devedeve decidirdecidir porpor: :

    ExecutarExecutar o o processoprocesso queque estavaestava esperandoesperando esseesse eventoevento; ;

    ContinuarContinuar executandoexecutando o o processoprocesso queque jj estavaestava sendosendoexecutadoexecutado..

  • 7

    Escalonamento

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

    => Escalonador de CPU;

    Escalonador deve se preocupar com a eficincia da

    CPU, pois o chaveamento de processos complexo e

    custoso:

    Afeta desempenho do sistema e satisfao do usurio.

    Algoritmos que realizam o chaveamento de processos

    prontos para executar de acordo com regras bem

    estabelecidas.

    8

    O esquema de escalonamento:

    No preemptivo (cooperativo): No permite

    interrupes externa tarefa at que seja liberado pelo

    seu trmino ou pela troca para o estado esperando. Exemplo: Windows 3.x.

    Preemptivo: Interrompe a execuo de uma tarefa e

    transfere a CPU para outro; Necessrio mecanismo para coordenar acesso aos dados;

    Afeta o projeto de Kernel do SO => mudanas de filas E/S;

    Chamada de sistema deve ser concluda antes da troca;

    Exemplo: Windows XP, Mac OS X.

    Escalonamento

  • 9

    Componente envolvido na funo do escalonador de

    CPU;

    Mdulo que d o controle da CPU ao processo;

    Funo: Trocar o contexto;

    Trocar para o modo usurio;

    Desviar para local apropriado no programa de usurio.

    Chamado durante a troca de processo;

    Tempo gasto para interromper um processo e iniciar a

    execuo de outro definido por latncia de despacho.

    Despachante

    10

    Critrios para escalonamento

    Utilizao de CPU:

    manter a CPU to ocupada quanto possvel Maximizar;

    Vazo (throughput):

    nmero de processos que completam sua execuo por

    unidade de tempo. Maximizar;

    Tempo de Proporcionalidade:

    quantidade tempo para executar um processo particular.

    Minimizar;

  • 11

    Tempo de Espera:

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

    Tempo de Resposta:

    quantidade de tempo que leva de quanto um pedido foi feitoat que a primeira resposta seja produzida, no a sada (paraambientes de tempo - compartilhado) Minimizar;

    Critrios para escalonamento

    12

    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.

    Quando CPU liberada, ela alocada ao processo no

    incio da fila.

    Tempo de espera normalmente longo;

    Efeito comboio: todos os outros processo aguardam

    quando h um grande processo em execuo na CPU.

    Escalonamento de CPU

  • 13

    Interrupo qualquer(E/S)

    CPU

    0Fila de entrada

    23 1

    Primeiro a chegar, primeiro a ser atendido (PCPA)

    14

    CPU no controla o tempo dos processos!(no-preemptivo)

    CPU

    1Fila de entrada

    30 2

    Primeiro a chegar, primeiro a ser atendido (PCPA)

  • 15

    Exemplo: prog A (15 milissegundos),

    B (2 milissegundos)

    C (1 milisegundo).

    A linha de tempo (diagrama de Gantt)

    0 15 18

    A CB

    17

    0 1 18

    AC B

    3

    Tempo mdio = 16,67

    Tempo mdio = 7,3

    Tempo de retorno

    Tempo pode variarsubstancialmente se os tempos de retorno da CPU variarem

    muito

    Tempo de chegada

    0

    Primeiro a chegar, primeiro a ser atendido (PCPA)

    16

    Vantagem:

    fcil de implementar.

    Desvantagem:

    tempo de retorno imprevisveis.

    problemtico em sistemas de tempo compartilhado.

    Primeiro a chegar, primeiro a ser atendido (PCPA)

  • 17

    Programa menor primeiro (MP)

    Algoritmo Shortest job first (SJF);

    Associa a cada processo o tamanho do prximo burst de

    CPU do processo;

    A CPU atribui o processo que tem o prximo retorno de

    CPU menor (burst);

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

    algoritmo FIFO utilizado;

    No preemptivo e trabalha de acordo com a extenso

    de seus ciclos de CPU.

    18

    Exemplo: Programas A B C D

    ciclo de CPU 5 2 6 4

    0 2 17

    B D

    11

    Tempo mdio = 9,0A C

    6

    Se fosse utilizado o FIFO, o tempo mdio seria de 10,5

    A linha de tempo (diagrama de Gantt)

    Tempo de chegada

    0

    Programa menor primeiro (MP)

  • 19

    A B C D

    8 44 4

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

    B C D A

    4 44 8

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

    Programa menor primeiro (MP)

    20

    Vantagem:

    minimiza tempo mdio de espera;

    Desvantagem:

    adiantamento indefinido de alguns programas, ou

    seja, no h como saber a extenso do prximo burst

    de CPU.

    Programa menor primeiro (MP)

  • 21

    Menor tempo restante (MTR)

    Preemptivo do MP;

    Processos com menor tempo de execuo soexecutados primeiro;

    Se um processo novo chega e seu tempo de execuo menor do que do processo corrente na CPU, a CPU suspende o processo corrente e executa o processoque acabou de chegar;

    Requer conhecimento prvio do tempo de CPU (sistema em lote).

    22

    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

    0 1

    DA B C B A

    2 3 5 9 14

    Programa A B C D

    Tempo retorno 14 4 1 6Tempo mdio = 6,25

    A linha de tempo (diagrama de Gantt)

    MP teria um tempo mdio de 7,75

    Menor tempo restante (MTR)

  • 23

    Vantagem:

    garante execuo rpida de programas importantes.

    Desvantagem:

    sobrecarga com mudanas de contexto;

    Menor tempo restante (MTR)

    24

    Escalonamento de CPU

    Algoritmos para Sistemas Interativos:

    Alternncia circular (Round-Robin);

    Prioridades;

    Filas mltiplas;

    Prximo processo mais curto (Shortest Process Next);

    Garantido;

    Loteria;

    Frao justa (Fair-Share).

  • 25

    Algoritmo alternncia circular (AC)

    Escalonanento Round-Robin;

    Tempo compartilhado;

    Preemptivo;

    Cada processo recebe um tempo de execuo chamado quantum; ao final desse tempo, o processo bloqueado e outro processo colocado em execuo;

    Escalonador mantm uma lista de processos prontos.

    Escalonamento de CPU

    26

    Trabalha primeiro a chegar, primeiro a ser atendido.

    Ex.: Tempo de chegada 0 1 2 3Programa A B C D

    Ciclo de CPU 8 4 9 5

    A B C

    8 25

    Programa A B C D

    Tempo retorno 20 7 24 22Tempo mdio = 18,25

    12

    16

    D A C

    20

    24

    D C

    26

    0 4

    quantum

    Algoritmo alternncia circular (AC)

  • 27

    Vantagem:

    proporciona tempos de resposta razoveis para usurios interativo.

    Desvantagem:

    requer seleo de quantum de tempo ideal;

    se for muito pequeno, ocorrem muitas trocas diminuindo, assim, a eficincia da CPU; se for muito longo o tempo de resposta comprometido.

    Algoritmo alternncia circular (AC)

    28

    Associa-se a cada processo um nvel de prioridade, de acordo com os interesses do sistema.

    Exemplo: Gerenciador da CPU determina a prioridade para programas que:

    Necessidade de memria;

    Tempo total de CPU;

    Nmero e tipo de dispositivos perifricos.

    Algoritmo com Prioridade

    Escalonamento de CPU

  • 29

    Cada processo possui uma prioridade => os processos

    prontos com maior prioridade so executados

    primeiro;