Aula06_Escalonamento_de_CPU

Prévia do material em texto

Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Aula 6 
Capítulo 6 – Escalonamento de CPU 
• 6.1 Conceitos básicos 
• 6.2 Critérios de Escalonamento 
• 6.3 Algoritmos de Escalonamento 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Escalonamento de CPU 
• O escalonamento de CPU é a base dos SOs 
multiprogramados. 
• Alternando a CPU entre os processos, o SO pode 
tornar o computador mais produtivo. 
• Vamos ver os conceitos básicos de escalonamento de 
CPU e diversos algoritmos de escalonamento de 
CPU. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
6.1 Conceitos Básicos 
• Em um sistema monoprocessado s um 
processo pode ser executado de cada vez. 
• Se houver mais processos, o restante ter de esperar 
que a CPU esteja livre e possa se reescalonada. 
• O objetivo da multiprograma ão ter algum processo 
em execu ão durante todos os momentos, para 
maximizar a utiliza ão da CPU. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
6.1 Conceitos Básicos 
• Com a multiprogramação, tentamos usar esse tempo 
de forma produtiva. 
• Diversos processos são mantidos na memória ao 
mesmo tempo. Quando um processo precisa esperar, 
o SO afasta a CPU desse processo e dá a CPU a 
outro processo. 
• O escalonamento é uma função fundamental do SO. 
Quase todos os recursos são escalonados antes do 
uso. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• A execu ão de um processo consiste em um ciclo de 
execu ão da CPU e espera por E/S. 
• Os processos alternam entre esses dois estados. 
• A execução do processo come a com um burst de 
CPU se segue com um burst de E/S, que por sua vez, 
 seguido por outro burst de CPU e assim por diante. 
• Por fim, o burst de CPU final termina com uma 
requisição do sistema para encerrar a execu ão. 
 
6.1.1 Ciclo de Burst (surto) CPU – E/S 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
6.1.1 Ciclo de Burst CPU – E/S 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• A curva geralmente é caracterizada como exponencial 
ou hiperexponencial – veja figura a seguir. 
• Existe um grande número de bursts de CPU curtos e 
um número pequeno de bursts de CPU longos. 
• Um programa I/O-bound (limitado por E/S) geralmente 
terá muitos bursts de CPU curtos. 
• Um programa CPU-bound (limitado por CPU) poderá 
ter alguns bursts de CPU longos. 
6.1.1 Ciclo de Burst CPU – E/S 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
6.1.1 Ciclo de Burst CPU – E/S 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Quando a CPU fica ociosa o SO dever escolher um 
processo dentre os processos que estão na fila de 
prontos para ser executado. 
• O processo de sele ão executado pelo 
escalonador de curto prazo ou escalonador de 
CPU. 
6.1.2 Escalonador de CPU 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• O escalonador seleciona um processo entre os 
presentes na mem ria que estão prontos para 
execu ão, e o aloca CPU. 
• Não necessariamente a fila de processos prontos 
uma fila FIFO (primeiro a entrar, primeiro a sair). 
• Podemos organizar a fila de prontos usando v rias 
estrat gias como veremos mais adiante. 
 
6.1.2 Escalonador de CPU 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• As decisões de escalonamento de CPU podem 
ocorrer sob as quatro circunstâncias a seguir: 
1. Quando um processo passa do estado executando para o 
estado esperando. 
2. Quando um processo passa do estado executando para o 
estado pronto. 
3. Quando um processo passa do estado esperando para o 
estado pronto. 
4. Quando um processo termina. 
6.1.3 Escalonamento preemptivo 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Nos casos 1 e 4, não há opção em termos de 
escalonamento. 
• Nestes casos dizemos que o esquema de 
escalonamento é não-preemptivo ou cooperativo. 
• Em escalonadores não-preemptivos, depois que a 
CPU foi alocada a um processo, o processo mantém a 
CPU até liberá-la terminando ou passando para o 
estado de espera. 
• Este esquema foi usado no Windows 3.x. 
6.1.3 Escalonamento preemptivo 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• O escalonamento preemptivo ocorre nos casos 2 e 3. 
• Escalonadores preemptivos trazem custos adicionais 
em relação a coordenação de acesso aos dados 
compartilhados. 
• Exemplo: 
– Considere o caso de dois processos que compartilhem 
os dados. Enquanto um está atualizando dados é 
interrompido para que o segundo processo possa 
executar. O segundo processo tenta ler os dados, que 
estão no estado inconsistente. Precisamos de novos 
mecanismos para coordenar o acesso a dados 
compartilhados. 
6.1.3 Escalonamento preemptivo 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• A preempção também tem um efeito no projeto do 
kernel, em alguns casos o processo pode solicitar 
uma chamada de sistema e o kernel pode estar 
ocupado com uma atividade solicitada por outro 
processo. 
• Tais atividades podem implicar na alteração de dados 
importantes do kernel. 
• O que acontece se o processo for interrompido no 
meio dessas mudanças e o kernel precisar ler ou 
modificar a mesma estrutura? 
 
 
6.1.3 Escalonamento preemptivo 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Certos SOs, incluindo a maioria das versões do UNIX, 
tratam desse problema esperando que uma chamada 
de sistema seja concluída ou que ocorra uma 
operação com um bloco de E/S antes de realizar um 
troca de contexto. 
• Esse esquema garante que a estrutura do kernel será 
simples, pois ele não se apropria de um processo 
enquanto as estruturas de dados do kernel estiverem 
em um estado incoerente. 
 
 
6.1.3 Escalonamento preemptivo 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Outro componente envolvido na função de 
escalonamento de CPU é o despachante. 
• Despachante (Dispatcher) o m dulo que dá o 
controle da CPU ao processo selecionado pelo 
escalonador de curto prazo. Essa função envolve: 
– Trocar o contexto. 
– Trocar o modo do usu rio. 
– Desviar para o local apropriado no programa do usu rio para 
reiniciar esse programa. 
6.1.4 Despachante 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• O despachante deve ser o mais r pido poss vel. Ele 
chamado durante a troca de processo. 
• Latência de despacho tempo gasto para o 
despachante interromper um processo e iniciar a 
execu ão de outro. 
6.1.4 Despachante 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Diferentes algoritmos de escalonamento têm 
diferentes propriedades e podem favorecer uma 
classe de processos mais que outra; 
• Os critérios usados incluem: 
– Utilização de CPU – mantém a CPU ocupada pelo máximo 
de tempo possível. 
– Vazão (Throughput) – número de processos que são 
completados por unidade de tempo. Para processos longos a 
taxa pode ser de um processo por hora; para transações 
curtas, pode ser 10 processos por segundo. 
6.2 Critérios de escalonamento 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
– Tempo de Retorno (Turnaround) – é o intervalo entre a 
submissão de um processo até seu término. Esse tempo é a 
soma dos períodosgastos esperando para acessar a 
memória, aguardando na fila de processos prontos, 
executando na CPU e realizando operações de E/S. 
– Tempo de espera – tempo que um processo gasta 
esperando na fila de prontos. 
6.2 Critérios de escalonamento 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
– Tempo de resposta o tempo que o processo leva para 
come ar a responder, mas não o tempo que leva para gerar 
a resposta. O tempo de resposta geralmente limitado pela 
velocidade do dispositivo de sa da. 
 desej vel maximizar a utiliza ão de CPU e a 
Vazão, e minimizar o tempo de retorno, o tempo de 
espera e o tempo de resposta. 
6.2 Critérios de escalonamento 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Utilização de CPU máxima 
• Vazão (Throughput) máxima 
• Tempo de retorno (Turnaround) mínimo 
• Tempo de espera mínimo 
• Tempo de resposta mínimo 
6.2 Critérios de escalonamento 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• O escalonamento de CPU trata do problema de 
decidir qual dos processos na fila de prontos deve ser 
entregue à CPU. 
• Existem muitos algoritmos de escalonamento de CPU 
diferentes. 
• A seguir veremos esses algoritmos: 
6.3 Algoritmos de escalonamento 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
 o algoritmo mais simples. 
• O processo que solicita a CPU primeiro, a recebe 
primeiro. 
• A implementa ão da pol tica FCFS facilmente 
gerenciada com a fila FIFO. 
6.3.1 Escalonamento 
First-Come, First-Served (FCFS) 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Quando um processo entra na fila de processos 
prontos, seu PCB ligado ao final da fila. 
• A CPU quando liberada aloca o processo que est no 
in cio da fila. 
• O tempo de espera m dio com a pol tica FCFS muitas 
vezes bem longo. 
6.3.1 Escalonamento 
First-Come, First-Served (FCFS) 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
 Processo Burst de CPU 
 (milissegundos) 
 P1 24 
 P2 3 
 P3 3 
• Suponha que o processo chegue na ordem: P , P e P . O 
diagrama de Gantt para o escalonamento será: 
 
 
 
 
– Tempo de espera para P = 0; P = 24; P = 27 
– Tempo de espera médio: (0 + 24 + 27)/3 = 17 milissegundos 
6.3.1 Escalonamento 
First-Come, First-Served (FCFS) 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
 
• Suponha que o processo chegue na ordem 
 P , P , P 
– O diagrama de Gantt para o escalonamento será: 
 
 
 
 
– Tempo de espera para P = 6; P = 0; P = 3 
– Tempo de espera médio: (6 + 0 + 3)/3 = 3 milissegundos 
 
• Muito melhor do que no caso anterior 
• Efeito comboio – processo curto atrás de processo longo 
6.3.1 Escalonamento 
First-Come, First-Served (FCFS) 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Esse algoritmo associa a cada processo a dura ão do 
seu pr ximo burst de CPU. 
• Usa esses tempos para escalonar o processo com o 
tempo mais curto. 
• Caso dois processos tenham a mesma dura ão do 
burst de CPU, o escalonamento FCFS ser usado 
para o desempate. 
• O termo mais apropriado para este algoritmo seria o 
pr ximo burst de CPU mais curto. 
6.3.2 Escalonamento 
Shortest Job First (SJF) 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
 Processo Burst de CPU 
 (milissegundos) 
 P1 7 
 P2 4 
 P3 1 
 P4 4 
 
 
 
 
– Tempo de espera para P = 9; P = 1; P = 0; P = 5 
– Tempo de espera médio: (9 + 1 + 0 + 5)/4 = 3,75 milissegundos 
6.3.2 Escalonamento 
Shortest Job First (SJF) 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• O escalonamento SJF comprovadamente timo, 
pois fornece o tempo m dio de espera m nimo para 
um determinado conjunto de processos. 
• A dificuldade com o algoritmo conhecer a dura ão 
do pr ximo pedido de CPU. 
• O escalonamento SJF usado com frequência em 
escalonamento de longo prazo. 
• Então ele não pode ser abordado no n vel de 
escalonamento de CPU de curto prazo. 
6.3.2 Escalonamento 
Shortest Job First (SJF) 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Uma t cnica utilizada tentar aproximar o 
escalonamento SJF. 
• Talvez não seja poss vel saber a dura ão do pr ximo 
burst de CPU, mas podemos tentar prever o seu valor. 
• Esperamos que o pr ximo burst de CPU seja 
semelhante em dura ão aos anteriores. 
• Assim podemos selecionar o processo com o menor 
burst de CPU previsto. 
6.3.2 Escalonamento 
Shortest Job First (SJF) 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• O algoritmo SJF pode ser preemptivo ou não 
preemptivo. 
– Caso seja preemptivo quando um novo processo chega na 
fila de processos prontos com tamanho de burst de CPU 
menor do que o tempo restante do processo atualmente em 
execução, ele é retirado. Esse esquema é conhecido como 
“Shortest Remaining Time First” (SRTF). 
– Não-preemptivo – uma vez dada ao processo, a CPU não 
pode ser preemptada até que complete seu burst de CPU. 
• O SJF o timo provê o menor tempo de espera 
m dio para um determinado conjunto de processos. 
6.3.2 Escalonamento 
Shortest Job First (SJF) 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
 Processo Chegada Burst de CPU 
 (milissegundos) 
 P1 0 7 
 P2 2 4 
 P3 4 1 
 P4 5 4 
• SJF (não-preemptivo) 
 
 
 
– Tempo de espera para: 
• P1 = 0 (tempo de atendimento) – 0 (chegada) = 0 
• P2 = 8 (tempo de atendimento) – 2 (chegada) = 6 
• P3 = 7 (tempo de atendimento) – 4 (chegada) = 3 
• P4 =12 (tempo de atendimento) – 5 (chegada) = 7 
– Tempo de espera médio = (0 + 6 + 3 + 7)/4 = 4 milissegundos 
6.3.2 Escalonamento 
Shortest Job First (SJF) 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Exemplo de SJF preemptivo 
 Processo chegada Burst de CPU 
 (milissegundos) 
 P1 0 7 
 P2 2 4 
 P3 4 1 
 P4 5 4 
• SJF (preemptivo) 
 
 
 
– Tempo de espera para: 
• P1 = (0 atendimento – 0 chegada) + (11 atendimento – 2 processamento) = 9 
• P2 = (2 atendimento – 2 chegada) + (5 atendimento – 4 processamento) = 1 
• P3 = (4 atendimento – 4 chegada) = 0 
• P4= (7 atendimento – 5 chegada) = 2 
– Tempo de espera médio = (9 + 1 + 0 +2)/4 = 3 milissegundos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Escalonamento por Prioridade 
• A prioridade est associada a cada processo, e a 
CPU alocada ao processo com prioridade mais alta. 
Processos de prioridade igual são escalonados na 
ordem FCFS. 
• As prioridades são indicadas por algum intervalo de 
n meros, como 0 a 7, ou 0 a 4095. 
• Contudo não existe um acordo geral com rela ão a se 
0 a maior ou a menor prioridade. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Escalonamento por Prioridade 
• Um valor de prioridade (inteiro) associado a cada 
processo. 
• A CPU alocada para o processo com a prioridade 
mais alta (menor inteiro = prioridade mais alta). 
– Escalonadores preemptivo por prioridade interrompe o 
processo em execução quando o processo que chega na filade pronto tem maior prioridade sobre o processo em 
execução. 
– Escalonadores não-preemptivo não interrrompe o processo 
em execução mas coloca o processo que chegou com maior 
prioridade no topo da fila de prontos. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Escalonamento por Prioridade 
• SJF é um escalonamento por prioridade em que a 
prioridade é o próximo tempo de surto de CPU 
previsto. 
• Problema => Estagnação – processos de baixa 
prioridade podem nunca ser executados. 
• Solução => Envelhecimento – conforme o tempo 
passa, aumente a prioridade do processo. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Escalonamento por Prioridade 
 Processo Prioridade Burst de CPU 
 (milissegundos) 
 P1 3 10 
 P2 1 1 
 P3 3 2 
 P4 4 1 
 P5 2 5 
• Não-preemptivo 
 
 
 
 
– Tempo de espera para P = 6; P = 0; P = 16; P = 18; P = 1 
– Tempo de espera médio = (6 + 0 + 16 + 18 + 1)/5 = 8,2 milissegundos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Escalonamento por Prioridade 
 Processo Chegada Prioridade Burst de CPU 
 (milissegundos) 
 P1 0 3 10 
 P2 1 4 1 
 P3 2 2 5 
 P4 3 3 2 
 P5 4 1 1 
• Preemptivo 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Escalonamento por Prioridade 
 Preemptivo 
 
 
 
 
– Tempo de espera para: 
• P1 = (0 atendimento – 0 chegada) + (8 atendimento – 2 processamento) = 6 
• P2 = (18 atendimento – 1 chegada) = 17 
• P3 = (2 atendimento – 2 chegada) (5 atendimento – 4 processamento) = 1 
• P4= (16 atendimento – 3 chegada) = 13 
• P5= (4 atendimento – 4 chegada) = 0 
 
– Tempo de espera médio = (6 + 17 + 1+ 13 + 0)/5 = 7,4 milissegundos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Escalonamento por Prioridade 
• Curiosidade sobre o escalonamento por 
prioridade: 
– Dizem que, quando desativaram o IBM 7094 no MIT em 
1973, encontraram um processo de baixa prioridade que 
tinha sido submetido em 1967 e ainda não tinha sido 
executado. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Algoritmo de escalonamento 
Round-Robin (RR) 
• Round-Robin (RR – Revezamento Circular) foi 
projetado especialmente para sistemas de tempo 
compartilhado. 
• É semelhante ao escalonamento FCFS, mas a 
preempção é acrescentada para alternar entre 
processos. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Algoritmo de escalonamento 
Round-Robin (RR) 
• Este escalonador introduz o conceito de QUANTUM 
DE TEMPO que é uma pequena unidade de tempo 
que geralmente é de 10 a 100 milissegundos. 
• A fila de prontos é tratada como uma fila circular, o 
escalonador de CPU percorre a fila de processos 
prontos, alocando a CPU a cada processo por um 
intervalo de tempo de até 1 quantum de tempo. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Algoritmo de escalonamento 
Round-Robin (RR) 
• Desempenho 
– Quantum de tempo grande  FIFO 
– Quantum de tempo pequeno  quantum precisa ser grande 
com relação ao tempo de troca de contexto ou o custo 
adicional será muito alto 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Exemplo de RR com 
Quantum de Tempo = 20 
 Processo Burst de CPU 
 (milissegundos) 
 P1 53 
 P2 17 
 P3 68 
 P4 24 
• O diagrama de Gantt : 
 
 
 
 
• Normalmente, turnaround m dio mais alto do que SJF, 
mas melhora a resposta 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Exemplo de RR com 
Quantum de Tempo = 20 
– Tempo de espera para: 
• P1 = 0 + (77 atendimento – 20 processamento) + (121 atendimento – 97 processamento) = 81 
• P2 = 20 
• P3 = 37 + (97 atendimento – 57 processamento) (134 atendimento – 117 processamento) = 94 
• P4= 57 + (117 atendimento – 77 processamento) = 97 
– Tempo de espera médio = (81 + 20 + 94 + 97)/4 = 73 milissegundos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Quantum de Tempo e 
Tempo de Troca de Contexto 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
O Turnaround varia Conforme o 
Quantum de Tempo 
Sistemas Operacionais com Java 
Referências 
• Capítulo 6 da referência abaixo: 
– SILBERSCHATZ, ABRAHAM; GAGNE, GREG; GALVIN, 
PETER BAES. Sistemas operacionais: com java. . Rio de 
Janeiro: Elsevier, 2004.