Upload
hakhue
View
222
Download
0
Embed Size (px)
Citation preview
BC1518-Sistemas Operacionais
EscalonamentoEscalonamento de CPUde CPU
Prof. Marcelo Z. do Nascimento
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.
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.
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?