SO 06

Prévia do material em texto

1 
Sistemas Operacionais 
Escalonamento 
 
 
Objetivos 
 
– Escalonamento 
– Escalonamento não preemptível 
– Escalonamento preemptível 
– Monitoramento 
 
1 – Escalonamento 
1.1 – Funções do escalonamento 
Funções do escalonamento 
 
• A política de escalonamento de um sistema operacional 
possui diversas funções básicas como: 
 
Manter o processador ocupado a maior parte do tempo 
Balancear o uso da UCP entre os processos 
Privilegiar a execução de aplicações críticas 
Maximizar o throughput do sistema 
Oferecer tempos de resposta razoáveis para usuários 
interativos 
 
 
 
 
Funções do escalonamento 
Funções do escalonamento 
 
• Cada sistema operacional possui a sua rotina de 
escalonamento adequada ao seu propósito e às suas 
características; 
• Sistemas de tempo compartilhado e de tempo real possuem 
requisitos distintos na forma de escalonar os processos; 
• O escalonamento trata a fila de prontos dos processos; 
 
 
 
1.2 – Escalonador e dispatcher 
Escalonador 
• É uma das mais importantes rotinas do sistema operacional; 
• Em um sistema multiprogramável, o escalonador é 
fundamental, pois todo o compartilhamento do processador é 
dependente dessa rotina; 
 
 
 
Dispatcher 
 
• É a rotina responsável por trocar os contextos dos processos 
após o escalonador determinar qual processo deve fazer uso 
do processador; 
• O período gasto na substituição de um processo por 
outro é denominado de latência do dispatcher; 
 
 
 
1.3 – Critérios do escalonamento 
Critérios do escalonamento 
 
• Utilização do processador = Fazer com que o processador 
fique ocupado a maior parte do tempo; 
• Throughput = É a quantidade de processos executados em 
um intervalo de tempo; 
• Tempo do processador = É o tempo em que um processo 
leva no estado de execução durante o seu processamento; 
 
 
 
 
 
Critérios do escalonamento 
• Tempo de espera = É o tempo em que o processo fica na fila 
de pronto a espera de ser executado pela primeira vez; 
• Tempo de turnaround = É o tempo total que um processo 
leva desde a sua criação até o seu termino, considerando 
todos os estados do processo; 
• Tempo de resposta = É o tempo decorrido entre uma 
requisição ao sistema ou a aplicação e o instante em que a 
resposta é exibida; 
• A política de escalonamento tenta equilibrar todos estes 
critérios, ou então, dependendo da característica, 
priorizar algum deles; 
 
 
 
 
 
 
 
 
2 – Escalonamentos não 
preemptiveis 
Escalonamento não preemptível 
 
• Foi o primeiro tipo de escalonamento implementado nos 
sistemas operacionais multiprogramáveis, predominando o 
processamento batch; 
• Neste tipo de escalonamento, nenhum evento externo pode 
ocasionar o desvio do processador, ou seja, o processo só sai 
do estado de execução caso termine o seu processamento ou 
execute instruções que mudem para o estado de espera (I/O); 
 
 
 
 
 
 
 
2.1 – Escalonamento FIFO 
First-in-First-Out - FIFO 
• O primeiro processo a chegar no estado de pronto, será o 
primeiro processo a ser selecionado para a execução; 
 
 
 
 
 
 
SIMULADORES !!!!! 
Carta Gantt no FIFO 
 
• Qual a média do tempo de espera em cada caso? 
• Qual a média do turnaround em cada caso? 
 
 
 
 
 
Vantagens do FIFO 
 
 
 
• É um algoritmo de simples implementação; 
 
 
 
 
 
 
 
Desvantagens do FIFO 
 
• Imprevisibilidade do tempo de inicio do processo, uma vez 
que este algoritmo não se preocupa em melhorar os tempos 
de espera; 
• Processo CPU-bound levam maior vantagem, uma vez que 
o I/O-bound vão sempre para o final da fila de prontos; 
• Não é adequado para sistemas operacionais interativos; 
 
 
 
 
 
 
2.2 – Escalonamento SJF 
Shortest-Job-First - SJF 
 
• É selecionado o processo que tem menor tempo do 
processador a executar; 
• O operador da máquina ao colocar o processo, entrava 
manualmente com o tempo de CPU do processo como 
contexto de software; 
• O tempo do processo era baseado em análise estatísticas 
das execuções de processos anteriores; 
 
 
 
 
 
SIMULADORES !!!!! 
Carta Gantt no SJF 
 
• Qual a média do tempo de espera em cada caso? 
• Qual a média do turnaround em cada caso? 
 
 
 
 
 
Vantagens do SJF 
 
 
 
• Melhora o tempo de espera e de turnaround 
em relação ao FIFO; 
 
 
 
 
 
 
Desvantagens do SJF 
 
• O usuário determina o tempo do processador para cada 
processo, e partir daí, o escalonador selecionava os 
processos conforme o tempo SJF; 
• Possibilidade de haver “starvation” para processos longos 
(alto tempo de CPU), ou tipicamente CPU-Bound; 
 
 
 
 
 
Desvantagens do SJF 
 
• O usuário determina o tempo do processador para cada 
processo, e partir daí, o escalonador selecionava os 
processos conforme o tempo SJF; 
• Possibilidade de haver “starvation” para processos longos 
(alto tempo de CPU), ou tipicamente CPU-Bound; 
 
 
 
 
 
2.3 – Escalonamento cooperativo 
Cooperativo 
 
• Como forma de equilibrar melhor o uso da CPU entre os 
processos na fila de pronto, os processos liberam 
voluntariamente o processador e entram novamente na fila de 
pronto; 
• O sistema operacional não tem intervenção nesta política, 
pois, a liberação da CPU dependem de instruções específicas 
dos processos; 
• Escalonamento utilizado no windows 3.1 e 3.11. 
 
 
 
 
 
Vantagens do cooperativo 
 
• Melhor distribuição da CPU entre os processos; 
• Gera um pseudo time-slice, como se fosse um sistema 
preemptivo; 
 
 
 
 
Desvantagens do cooperativo 
 
• Programas mal escritos podem entrar em looping, 
monopolizando a CPU; 
• O tempo de troca dos processos não é tarefa do sistema 
operacional, logo, maior probabilidade de erros por parte dos 
programadores; 
 
 
 
 
3 – Escalonamentos preemptiveis 
Escalonamento preemptível 
 
• Os processos são interrompidos pelo sistema operacional; 
• O uso da preempção faz com que seja possível priorizar a 
execução de processos; 
• Melhor balanceamento do uso do processador entre os 
processos; 
• A preempção é largamente utilizada em sistemas 
operacionais de tempo compartilhado e de tempo real; 
 
 
 
 
 
 
3.1 – Escalonamento circular 
Circular (Round robin) 
 
• Esse algoritmo é bastante similar ao FIFO, porém, cada 
processo tem um tempo limite para uso do processador; 
• Este tempo de uso é conhecido como time-slice ou quantum 
de tempo; 
• O tempo é gerado pelo relógio da máquina; 
• Este método baseado em relógio, é conhecido como 
preempção por tempo; 
 
 
 
Circular (Round robin) 
SIMULADORES !!!!! 
Carta Gantt para Circular 
 
• Qual o valor do time-slice? 
• Qual a média do tempo de espera em cada caso? 
• Qual a média do turnaround em cada caso? 
 
 
 
 
 
Vantagens do circular 
 
• Os processos não monopolizam a CPU em virtude do time-
slice, que variam entre 10 e 100 ms (depende do sistema 
operacional); 
• É um escalonamento aceitável em sistemas multitarefas; 
 
 
 
 
Desvantagens do circular 
• Os processos CPU-bound são beneficiados por utilizar todo 
o time-slice, enquanto os I/O-bound não são priorizados e 
sempre quando saem da fila de espera, vão para o final da filade prontos; 
• Valores altos de time-slice podem tender a um 
comportamento FIFO; 
• Valores baixos de time-slice geram muitas preempções, 
ocasionando muitas mudanças de contextos pelo dispatcher, 
gerando muito overhead; 
• O time-slice tem que ser maior que o tempo de latência do 
dispatcher (USAR SIMULADOR !!!!!!) 
 
 
 
Time slice (Local timer interrupts) 
#watch -d -n 1 cat /proc/interrupts 
3.2 – Escalonamento por 
prioridades 
Prioridades 
 
• A preempção é realizada com base em um valor de 
prioridade dada a cada processo; 
• O processo com maior prioridade na fila de pronto é o 
escolhido para a execução, ou seja, o primeiro; 
• Processos de mesma prioridade comportam-se como o 
FIFO; 
• Não existe preempção do processo por tempo; 
• A perda do processador ocorrerá ao término voluntário do 
processo ou ao estado de espera; 
 
 
 
 
Prioridades 
Carta Gantt prioridades 
 
• Qual o valor do time-slice? 
• Qual a média do tempo de espera em cada caso? 
• Qual a média do turnaround em cada caso? 
 
 
 
 
 
Rescheduling 
 
• O escalonador de prioridades é implementando com base 
em uma política de preempção por tempo (interrupção do 
relógio por tempo); 
• Este tempo serve para que o escalonador organize a fila de 
prontos, caso chegue novos processos com maiores 
prioridades; 
• Em caso de não haver mudanças nas prioridades, o 
escalonador não fará mudança na ordem dos processos da 
fila de pronto; 
 
 
 
 
Rescheduling interrupts < Timer INT 
Prioridades estáticas e dinâmicas 
 
• A prioridade estática é aquela em que não pode ser 
modificada em tempo real de execução; 
• A prioridade dinâmica é aquela em que pode ser modificada 
em tempo real de execução, a partir de uma entrada do 
usuário ou pelo próprio sistema operacional em função do 
comportamento do processo; 
 
 
 
Vantagens das prioridades 
 
• Dar maior tempo de CPU a um processo que precise de 
mais tempo; 
• Processos I/O-bound podem ser priorizados; 
• Mais utilizado em sistemas de tempo real; 
 
 
Desvantagens das prioridades 
 
• Processos com menor prioridade podem tender a um 
“starvation” quando chegar processos de maior prioridade na 
fila de prontos; 
 
3.3 – Escalonamento circular com 
prioridades 
Circular com prioridades 
 
• Implementa o conceito de time-slice e de prioridade de 
execução associada a cada processo; 
• Neste escalonamento um processo permanece no estado de 
execução até o seu término natural, ou passe para o estado 
de espera ou sofra preempção por prioridade ou tempo; 
• Este escalonamento permite o melhor balanceamento no 
uso da UCP, com a possibilidade de diferenciar o grau de 
importância dos processos; 
• Amplamente utilizado em sistemas de tempo 
compartilhado; 
 
 
 
Circular com prioridades 
Escalonamento do linux >> Vide slide!! 
#!/bin/bash 
 
while : ; do 
 cont=$(($cont+1)) 
 echo "p1 $cont" 
 sleep 0.05 
 
done 
#!/bin/bash 
 
while : ; do 
 cont=$(($cont+1)) 
 echo "p2 $cont" 
 sleep 0.05 
 
done 
• Execute os dois scripts através de ./teste1sh & ./teste2.sh 
• Através dos sinais NICE E RENICE do htop, verifique o 
comportamento destes dois processos; (-20 a 19 PRI)!!! 
• Ajuste os valeres de tempo para verificar o impacto, e 
explique as respostas!!!! 
 
 
Questionamentos 
 
• Na ferramenta htop, quem é PRI e NI? 
• Mexa na prioridade do processo e verifique o range de 
variação; 
• Através do NI e do resultado da execução dos scripts 
anteriores, verifique como aumentar ou diminuir a prioridade; 
• O escalonador muda dinamicamente a prioridade porque? 
(evitar o “starvation” pelo algoritmo do envelhecimento ou 
idade); 
 
#schedtool - 1 
 
 
 
• apt-get install schedtool 
• man schedtool (ler o manual) 
 
#schedtool PID 
 
Discuta os itens de saída do comando; 
 
 
 
#schedtool - 2 
 
Executar os testes no programa thread1.c (quatro threads 
com while(1) loop infinito) 
 
Após a execução, verificar o uso de CPU de cada thread e o 
tempo de execução de cada uma delas pelo comando abaixo; 
 
#htop –d -1 
 
 
#schedtool - 3 
 
Escalonando CPUs 
 
#schedtool –a 0x2 PID 
 
• Escalone a metade das threads para um núcleo só!!!!! 
 
• Verifique o tempo e o consumo da CPU de cada uma thread 
e compare!!!!; 
 
#schedtool - 3 
 
 
#watch –d –n -1 cat /proc/interrupts 
 
Desloque todas a threads para a CPU 1, e verifique se as 
interrupções do teclado ficam comprometidas assim como as 
do mouse; 
 
 
#schedtool - 4 
 
Mudando as políticas de escalonamento 
 
#schedtool –F –p 20 PID (FIFO) 
#schedtool –R –p 20 PID (Round Robin) 
#schedtool - 5 
 
Copie thread1 para /sbin 
Inicializando um programa com parâmetros específicos 
 
#schedtool –F –p 20 –a 0x2 –e thread1 
 
Discuta o resultado e compare com o escalonamento –R e –B 
Visualize dentro do htop os tempos de escalonamento 
#schedtool - Fim 
 
Coloque a máquina com apenas 1 CPU e execute 
#schedtool –F –p 20 –a 0x1 –e thread1 
Para as seguintes situações: 
 
Quatro threads em loop infinito 
Quatro threads contando números e imprimindo só no final 
Quatro threads contando e imprimindo cada número contado 
DISCUTA O RESULTADO!!!!!! 
 
 
 
3.4 – Escalonador real 
Escalonador real 
 
• Na prática, sistemas operacionais implementam mais de um 
algoritmo de escalonamento; 
• Este tipo escalonamento é conhecido como múltiplas filas, 
sendo que cada uma delas utiliza um algoritmo de 
escalonamento distinto com suas políticas independentes; 
• Processos de sistema utilizam FIFO; 
 
#schedtool 1 2 3 4 5 6 7 8 9 10 
 
 
Escalonador real – Múltiplas filas 
 
 
 
 
4 – Monitoramento 
4.1 – Métricas da CPU 
#top ou htop 
 
• %su = Processos em modo usuário 
• %sy = Processos em modo kernel 
• %ni = Processos em modo usuário com nice (variação da 
prioridade) 
• %id = Ociosidade da CPU 
• %wa = Espera por E/S 
• %hi = Tratamento de interrupções de hardware 
• %si = Tratamento de interrupções de software 
• %st = Tempo usado para máquinas virtuais; 
 
4.2 – Média de consumo 
#top ou htop 
 
 
LOAD AVERAGE 
 
Média de consumo % em 1 minuto 
Média de consumo % em 5 minutos 
Média de consumo % em 15 minutos 
#top 
 
Execute #./thread1 
Execute #iozone –a 
E compare as métricas 
 
Execute mais de um processo thread1 
 
A máquina ficou lenta??? Justifique!!! 
 
#vmstat 1 
 
 
 
• in = quantidade de interrupções por segundo 
• cs = quantidade de trocas de contexto por segundo (dispacher) 
• %us = processos em modo usuário 
• %sy = processos em modo kernel 
• %id = ociosidade da CPU 
• %wa = espera por E/S