Gerência do Processador - IME-USPadao/GERENCIADOPROCESSADOR.pdf · As características do sistema operacional (sistemas de tempo compartilhado ou sistemas de tempo real) ... A MAIORIA

1

Gerência do Processador

Adão de Melo Neto

2

IntroduçãoSistemas Multiprogramáveis:– Múltiplos processos podem permanecer na memória principal

compartilhando o uso da CPU.– POLÍTICA DE ESCALONAMENTO Como diversos processos podem estarem estado de pronto devem

ser estabelecidos critérios para determinar qual processo seráescolhido para fazer uso do processador

Programa Processo

3

Processo/Memória Principal (revisão)

4

Critérios de Escalonamento

As características do sistema operacional (As características do sistema operacional (sistemas desistemas detempo compartilhado ou sistemas de tempo realtempo compartilhado ou sistemas de tempo real))

irão determinar quais os principais aspectosirão determinar quais os principais aspectosna implementação de uma política de escalonamentona implementação de uma política de escalonamento

Utilização do ProcessadorUtilização do Processador– 30% (sistema com carga baixa) e 90% (sistema bastante carregado)

ThroughputThroughput– Número de processos executados em determinado intervalo de tempo

Tempo de Processador/CPUTempo de Processador/CPU– Tempo que um processo leva no estado de execução durante seu processamento– As políticas de escalonamento não influenciam este tempo

Tempo de esperaTempo de espera– Tempo que um processo fica no estado de pronto aguardando ser executado

Tempo de Tempo de TurnaroundTurnaround– Tempo que leva desde a criação até seu término

Tempo de RespostaTempo de Resposta– Tempo decorrido desde a requisição ao sistema ou aplicação até o instante que a

resposta é exibida

Busca-se maximizar Busca-se minimizar

5

Funções de uma Política de Escalonamento- Manter processador ocupado a maior parte do tempo- Manter processador ocupado a maior parte do tempo- Balancear o uso da CPU entre os processos- Balancear o uso da CPU entre os processos- Privilegiar aplicações críticas- Privilegiar aplicações críticas- Maximizar o - Maximizar o throuput throuput do sistema.do sistema.- Maximizar o tempo de resposta- Maximizar o tempo de resposta

Rotina SCHEDULERRotina SCHEDULERImplementar a política de escalonamento do processador

Rotina DISPATCHERRotina DISPATCHER Implementar a troca de contexto entre processos

6

Escalonamentos Preemptivos Não-Preemptivos

PREEMPÇÃOCapacidade de um sistema operacional interromper um processo em

execução e substituí-lo por um outro

ESCALONAMENTO PREEMPTIVOSESCALONAMENTO PREEMPTIVOS(o sistema operacional pode interromper um(o sistema operacional pode interromper umprocesso e processo e passápassá--lo lo para o estado de pronto,para o estado de pronto,

a fim de a fim de alocar alocar outro processo na CPU)outro processo na CPU)

ESCALONAMENTOS NÃO-ESCALONAMENTOS NÃO-PREEMPTIVOSPREEMPTIVOS

(nenhum evento externo pode(nenhum evento externo podeocasionar a perda do uso doocasionar a perda do uso do

processador)processador)

7

Mudança de Estados de um Processo (revisão)(A) PRONTO (A) PRONTO →→ EXECUÇÃO EXECUÇÃO

( depende da política de( depende da política deescalonamento do Sistemaescalonamento do Sistema

Operacional)Operacional)

(B) EXECUÇÃO (B) EXECUÇÃO →→ ESPERA ESPERA(gerada por eventos do processo(gerada por eventos do processo

comocomooperações de E/S)operações de E/S)

(gerada por eventos externo:(gerada por eventos externo:Sistema operacional suspendeSistema operacional suspendepor um período de tempo apor um período de tempo a

execução do processo)execução do processo)

(D) EXECUÇÃO (D) EXECUÇÃO →→ PRONTO PRONTO(término da fatia de tempo que(término da fatia de tempo que

processo possui para suaprocesso possui para suaexecução)execução)

(C) ESPERA (C) ESPERA →→ PRONTO PRONTO(operação solicitada é atendida ou recurso esperado é concedido(operação solicitada é atendida ou recurso esperado é concedido

8

Vantagens da PreempçãoVantagens da Preempção

Priorizar Priorizar a execução de processos como noa execução de processos como nocaso de aplicações de tempo real onde o fator de tempo écaso de aplicações de tempo real onde o fator de tempo é

críticocrítico

Implementar políticas de escalonamento que compartilhemImplementar políticas de escalonamento que compartilhemo processador de maneira mais uniformeo processador de maneira mais uniforme

9

ESCALONAMENTO FIRST-IN_FIRST-OUT (FIFO)ESCALONAMENTO FIRST-IN_FIRST-OUT (FIFO)Não-Não-preemptivopreemptivoOs processos que passam para o estado de pronto Os processos que passam para o estado de pronto ⇒⇒ entram noentram nofinal de uma filafinal de uma fila e são escalonados quando chegam ao seu e são escalonados quando chegam ao seu inícioinício..Processo em execução Processo em execução termina o seu processamentotermina o seu processamento ou ou vai para ovai para oestado de espera estado de espera ⇒⇒ o o primeiro processo da fila é escalonado. primeiro processo da fila é escalonado.Processos que saem da fila de Processos que saem da fila de estado de esperaestado de espera ⇒⇒ entram no finalentram no finalda fila de pronto.da fila de pronto.

Final Início

11oo processo processo

Processo emProcesso emexecuçãoexecução

Escalonamento FIFO

10

ESCALONAMENTO FIRST-IN_FIRST-OUT (FIFO)ESCALONAMENTO FIRST-IN_FIRST-OUT (FIFO)

Duas situações distintas que Duas situações distintas que dependem do posicionamento dosdependem do posicionamento dosprocessos A , B e Cprocessos A , B e C na fila de estado de pronto. na fila de estado de pronto.Tempo de ProcessadorTempo de Processador–– A (10), B (4) e C (3)A (10), B (4) e C (3)

Tempo Médio de Espera (0 + 10 + 14 )/3 = 8 u.t

Tempo Médio de Espera (7 + 0 + 4 )/3 = 3,7 u.t

C → B → A A → C → B

11

ESCALONAMENTO FIRST-IN_FIRST-OUT (FIFO)ESCALONAMENTO FIRST-IN_FIRST-OUT (FIFO)

VantagensVantagens–– SimplesSimples

DesvantagensDesvantagens–– Impossibilidade de se prever quando um processo terá suaImpossibilidade de se prever quando um processo terá sua

execução iniciada (não se preocupa em melhorar o tempo médioexecução iniciada (não se preocupa em melhorar o tempo médiodo processo)do processo)

–– Processos CPU-Processos CPU-bound bound levam vantagem em relação aoslevam vantagem em relação aosprocessos I/O-processos I/O-boundbound

12

ESCALONAMENTO SHORSTEST-JOB-FIRST (SJF)ESCALONAMENTO SHORSTEST-JOB-FIRST (SJF)

Não-Não-preemptivo preemptivo em sua concepção originalem sua concepção originalSeleciona o processo em estado de pronto que tiver o menor tempoSeleciona o processo em estado de pronto que tiver o menor tempode processador ainda por executar.de processador ainda por executar.Tempo de processador estimado com base em análises estatísticasTempo de processador estimado com base em análises estatísticasde execuções passadasde execuções passadas..

A (10)B (4)C (3)

A (10) B (4) C (3)

Ordem na Fila (exemplo)

Como será executado

13


Tempo de ProcessadorTempo de Processador–– A (10), B (4) e C (3)A (10), B (4) e C (3)

Tempo Médio de Espera (7 + 3 + 0 )/3 = 3,3 u.t

14


VantagensVantagens–– Redução do tempo médio de Redução do tempo médio de turnaround turnaround (desde da criação do(desde da criação do

processo até o seu fim)dos processos.processo até o seu fim)dos processos.DesvantagensDesvantagens–– Impossibilidade de se estimar o tempo de processador paraImpossibilidade de se estimar o tempo de processador para

processo interativos (entrada de dados é uma açãoprocesso interativos (entrada de dados é uma açãoimprevisível).imprevisível).

–– Possibilidade de Possibilidade de starvationstarvation para processos do tipo CPU- para processos do tipo CPU-BoundBound

15

ESCALONAMENTO COOPERATIVOESCALONAMENTO COOPERATIVO

Escalonamento Escalonamento preemptivo preemptivo (preempção controlada pelo processo)(preempção controlada pelo processo)Um processo em execução pode voluntariamente liberar oUm processo em execução pode voluntariamente liberar oprocessador retornando à fila de pronto, possibilitando que outroprocessador retornando à fila de pronto, possibilitando que outroprocesso possa ser escalonado.processo possa ser escalonado.Um processo em execução verifica periodicamente a fila deUm processo em execução verifica periodicamente a fila demensagens para determinar se existem outros processos na fila demensagens para determinar se existem outros processos na fila depronto.pronto.

16

ESCALONAMENTO COOPERATIVOESCALONAMENTO COOPERATIVO

VantagensVantagens–– Aumenta o grau de multiprogramação em políticas deAumenta o grau de multiprogramação em políticas de

escalonamento que não possuem mecanismo de preempção.escalonamento que não possuem mecanismo de preempção.DesvantagensDesvantagens–– Caso um processo não verifique a fila de mensagens, osCaso um processo não verifique a fila de mensagens, os

demais não terão chance de serem executados.demais não terão chance de serem executados.Exemplo de UsoExemplo de Uso–– Primeiros sistemas operacionais Microsoft Windows ( multitarefaPrimeiros sistemas operacionais Microsoft Windows ( multitarefa

cooperativa )cooperativa )

17

ESCALONAMENTO CIRCULAR (ESCALONAMENTO CIRCULAR (Round Robin ScheduleRound Robin Schedule))

Escalonamento Escalonamento preemptivopreemptivoProjetado para sistemas de tempo compartilhado.Projetado para sistemas de tempo compartilhado.Semelhante ao FIFO, porém quando passa para o estado deSemelhante ao FIFO, porém quando passa para o estado deexecução existe um tempo limite para o uso do processados (time-execução existe um tempo limite para o uso do processados (time-sliceslice).).Fim do time-Fim do time-sliceslice, o sistema operacional interrompe o processo,, o sistema operacional interrompe o processo,salva seu contexto e o salva seu contexto e o direciona direciona ao final da fila de pronto.ao final da fila de pronto.

18


Exemploonde

a fatia de tempo éigual

a 2 u.t

19


VantagensVantagens–– Não permitir que um processo monopolize a CPU.Não permitir que um processo monopolize a CPU.

DesvantagensDesvantagens–– Processos CPU-Processos CPU-boundbound são mais beneficiados no uso do são mais beneficiados no uso do

processador do que os I/O-processador do que os I/O-boundbound, pois tendem a utilizar por, pois tendem a utilizar porcompleto a fatia de tempo.completo a fatia de tempo.

Exemplo de UsoExemplo de Uso–– Muito adequado para sistemas interativosMuito adequado para sistemas interativos

20

ESCALONAMENTO POR PRIORIDADESESCALONAMENTO POR PRIORIDADESEscalonamento Preemptivo Escalonamento Preemptivo ((implementávelimplementável de forma não- de forma não-preemptivapreemptiva))Um valor (prioridade de execução) é associado a cada processo e Um valor (prioridade de execução) é associado a cada processo e ppara cadaara cadaprioridade existe uma filaprioridade existe uma filaReavaliação das Prioridades Periodicamente:

–– O processo com maior prioridade em estado de pronto é escolhido para execuçãoO processo com maior prioridade em estado de pronto é escolhido para execução(escalonado).(escalonado).

–– Processo com valores iguais de prioridade são escolhido de acordo com FIFOProcesso com valores iguais de prioridade são escolhido de acordo com FIFOPreempção por prioridadePreempção por prioridade::

–– Não existe o conceito de time-Não existe o conceito de time-sliceslice (não existe preempção por tempo) (não existe preempção por tempo)

21

Implementada por Implementada por interrupção de interrupção de clockclock gerada em determinados intervalos de tempo agerada em determinados intervalos de tempo afim de que a rotina de escalonamento reavalie as prioridades dos processos fim de que a rotina de escalonamento reavalie as prioridades dos processos na fila dena fila de

estado de prontoestado de pronto..Caso haja processos na fila de pronto com maior prioridade que o processo em execução,Caso haja processos na fila de pronto com maior prioridade que o processo em execução,

o sistema operacional realiza a preempçãoo sistema operacional realiza a preempção

PREEMPÇÃO POR PRIORIDADEPREEMPÇÃO POR PRIORIDADE

ESCALONAMENTO POR PRIORIDADESESCALONAMENTO POR PRIORIDADES

22

IBM-AIXprioridade: 1 a 127


Prioridade de 1 a 5

23

ESCALONAMENTO POR PRIORIDADESESCALONAMENTO POR PRIORIDADESPrioridade de ExecuçãoPrioridade de Execução→→ccaracterística do Contexto de Software do Processoaracterística do Contexto de Software do Processo

–– Prioridade EstáticaPrioridade Estática (não alterada durante a existência do processo) (não alterada durante a existência do processo)–– Prioridade DinâmicaPrioridade Dinâmica (pode ser alterada de acordo com critérios do sistema operacional) (pode ser alterada de acordo com critérios do sistema operacional)

24

VantagensVantagens–– Permite diferenciar processos de acordo com sua importância.Permite diferenciar processos de acordo com sua importância.

DesvantagensDesvantagens–– StarvationStarvation

•• Processos com baixa prioridade podem ficar indefinidamente naProcessos com baixa prioridade podem ficar indefinidamente nafila de prontofila de pronto

•• Solução:Solução: mecanismo de mecanismo de agingaging (incremento gradual da prioridade (incremento gradual da prioridadede processos que ficam muito tempo na fila de pronto)de processos que ficam muito tempo na fila de pronto)

Exemplo de UsoExemplo de Uso–– Útil em sistemas de tempo real e aplicações de controle deÚtil em sistemas de tempo real e aplicações de controle de

processo.processo.


25

ESCALONAMENTO CIRCULAR POR PRIORIDADESESCALONAMENTO CIRCULAR POR PRIORIDADESEscalonamento PreemptivoEscalonamento PreemptivoUm valor (prioridade de execução) é associado a cada processo e Um valor (prioridade de execução) é associado a cada processo e ppara cadaara cadaprioridade existe uma filaprioridade existe uma filaPreempção por prioridade ou por tempo (time-Preempção por prioridade ou por tempo (time-sliceslice))

26

ESCALONAMENTO POR MÚLTIPLAS FILASESCALONAMENTO POR MÚLTIPLAS FILASExistem várias filas de processos em estado de pronto com uma prioridadeExistem várias filas de processos em estado de pronto com uma prioridadeespecífica.específica.O O processo não possui prioridadeprocesso não possui prioridade, ficando esta característica associada a fila, ficando esta característica associada a filaAs filas estão associadas aos tipos de processos (As filas estão associadas aos tipos de processos (exex: sistema, iterativos, : sistema, iterativos, batchbatch).).Cada fila possui um mecanismo próprio de escalonamento (isto permite queCada fila possui um mecanismo próprio de escalonamento (isto permite quealguns sejam escalonados pelo mecanismo FIFO enquanto outros pelo outro peloalguns sejam escalonados pelo mecanismo FIFO enquanto outros pelo outro pelocircular)circular)Sistema Operacional só pode escalonar processo de uma fila caso todas as outrasSistema Operacional só pode escalonar processo de uma fila caso todas as outrasfilas de maior prioridade estejam vaziasfilas de maior prioridade estejam vazias

Escalonamento Escalonamento por prioridadepor prioridade

Escalonamento CircularEscalonamento Circular

Escalonamento CircularEscalonamento Circular

27

VantagensVantagens–– Diversos mecanismos de escalonamento em um mesmoDiversos mecanismos de escalonamento em um mesmo

sistema operacionalsistema operacionalDesvantagensDesvantagens–– Um processo não pode ser redirecionado para uma outra filaUm processo não pode ser redirecionado para uma outra fila

mais adequada (caso altere seu comportamento no decorrer domais adequada (caso altere seu comportamento no decorrer dotempo)tempo)

ESCALONAMENTO POR MÚLTIPLAS FILASESCALONAMENTO POR MÚLTIPLAS FILAS

28

POLÍTICAS DE ESCALONAMENTO EMPOLÍTICAS DE ESCALONAMENTO EMSISTEMAS DE TEMPO COMPARTILHADOSISTEMAS DE TEMPO COMPARTILHADO

Caracterizam pelo processamento interativo (exigem tempo de respostaCaracterizam pelo processamento interativo (exigem tempo de respostarápidos)rápidos)A escolha da política para atingir este propósito deve levar em consideração oA escolha da política para atingir este propósito deve levar em consideração ocompartilhamento da CPU de forma interativacompartilhamento da CPU de forma interativaComportamento dos processos CPU-Comportamento dos processos CPU-Bound Bound e I/O-e I/O-Bound Bound nos escalonamentosnos escalonamentosapresentadosapresentados

29


Comportamento dos processos CPU-Comportamento dos processos CPU-BoundBound e I/O- e I/O-BoundBound no noEscalonamento FIFOEscalonamento FIFO

Muitas operações I/OMuitas operações I/OGrande parteGrande parte

do tempo em estado dedo tempo em estado deesperaespera

ProcessadorProcessadordistribuído dedistribuído deforma bastanteforma bastante

desigualdesigual

30

Mudança de Estados de um Processo (revisão)Mudança de Estados de um Processo (revisão)

31


Comportamento dos processos CPU-Comportamento dos processos CPU-BoundBound e I/O- e I/O-BoundBound no noEscalonamento Circular com time-Escalonamento Circular com time-slice slice igual a 5igual a 5

Melhoria daMelhoria dadistribuição dodistribuição do

tempo detempo deprocessador emprocessador emrelação ao FIFOrelação ao FIFO

32


Comportamento dos processos CPU-Comportamento dos processos CPU-BoundBound e I/O- e I/O-BoundBound no noEscalonamento Circular com PrioridadesEscalonamento Circular com Prioridades

Há uma melhoria doHá uma melhoria docompartilhamento do uso docompartilhamento do uso doprocessador pois foi possívelprocessador pois foi possívelassociar maior prioridade aoassociar maior prioridade ao

processo B (I/O-processo B (I/O-BoundBound))

33


A MAIORIA DOS SISTEMAS OPERACIONAIS DE TEMPOA MAIORIA DOS SISTEMAS OPERACIONAIS DE TEMPOCOMPARTILHADO UTILIZAM OCOMPARTILHADO UTILIZAM O

ESCALONAMENTO CIRCULAR COM PRIORIDADES DINÂMICASESCALONAMENTO CIRCULAR COM PRIORIDADES DINÂMICAS

34

POLÍTICAS DE ESCALONAMENTO EMPOLÍTICAS DE ESCALONAMENTO EMSISTEMAS DE TEMPO REALSISTEMAS DE TEMPO REAL

Sistemas de Tempo RealSistemas de Tempo RealÉ garantida a execução de processos dentro de limites rígidosÉ garantida a execução de processos dentro de limites rígidos

de tempo, sem o risco da aplicação ficar comprometida.de tempo, sem o risco da aplicação ficar comprometida.

EscalonamentoEscalonamentoO escalonamento deve levar em consideração a importância deO escalonamento deve levar em consideração a importância de

cada tarefa na aplicaçãocada tarefa na aplicação

Escalonamento mais AdequadoEscalonamento mais AdequadoO O escalonamento por prioridadeescalonamento por prioridade é o mais adequado desde que a é o mais adequado desde que a

cada processo é associado uma prioridade em função dacada processo é associado uma prioridade em função daimportância do processo dentro da aplicaçãoimportância do processo dentro da aplicação

Documents

Gerência do Processador - IME-USPadao/GERENCIADOPROCESSADOR.pdf · As características do sistema operacional (sistemas de tempo compartilhado ou sistemas de tempo real) ... A MAIORIA