ArtigoSO 6

Prévia do material em texto

UNIVERSIDADE ESTADUAL DOMATO GROSSO DO SUL
LEANDRO BARRA DE MATTOS RGM - 31368
ARTIGO SOBRE O ESCALONAMENTO DO CPU
Dourados- MS
2017
UNIVERSIDADE ESTADUAL DO MATO GROSSO DO SUL
LEANDRO BARRA DE MATTOS RGM - 31368
ARTIGO SOBRE O ESCALONAMENTO DO CPU
Trabalho apresentado na Disciplina de Sistemas
Operacionais (SO), do 3º ano, Curso de Ciência
da Computação Faculdade de Ciências Exatas e
Tecnológicas da UEMS.
Orientador: Profº Felipe Pereira Perez
Dourados- MS
2017
Artigo sobre o Escalonamento do CPU
Leandro Barra de Mattos ∗
2017, v-1.0
Resumo
Pretende-se neste artigo abordar aspec-
tos teóricos que norteiam o Escalona-
mento do CPU, além de apresentar de
forma simples e objetiva os algoritmos
que podem ser utilizados para realizar
esse processo. É feito uma viagem em
torno dos principais algoritmos de es-
calonamento utilizados atualmente e
como cada um deles podem de uma
forma simples aumentar o desempe-
nho de um computador. E é feito tam-
bém uma análise das técnicas utiliza-
das para se avaliar qual dos algoritmos
é mais adequado para se utilizar em
um sistema operacional.
Palavras-chave: escalonamento,
CPU, algoritmos.
Introdução
O escalonamento de CPU é a base
dos sistemas operacionais multiprogramados.
Ao alternar a CPU entre os processos, o
sistema operacional pode tornar o computa-
dor produtivo. Neste artigo, apresentamos
os conceitos básicos de escalonamento e seus
critérios e vários algoritmos distintos de es-
calonamento de CPU e suas avaliações.
1 Críterios de Escalonamento
Diferentes algoritmos de escalona-
mento de CPU possuem diferentes proprieda-
des e podem favorecer uma classe dos proces-
∗leanmattos93@gmail.com
sos em detrimento de outra. Na escolha de
qual algoritmo será usado em determinada
situação, temos de considerar as proprieda-
des dos diversos algoritmos. Muitos critérios
foram sugeridos para a comparação de algo-
ritmos de escalonamento da CPU. A escolha
das características que serão usadas para a
comparação pode fazer uma diferença subs-
tancial na escolha do algoritmo considerado
melhor. Os critérios incluem os seguintes:
• Utilização de CPU: queremos manter
a CPU ocupada o máximo de tempo
possível. Em conceito, a utilização da
CPU pode variar de O a 100%. Em um
sistema real, ela deverá variar de 40%
(para um sistema pouco carregado) até
90% (para um sistema muito utilizado).
• Throughput (vazão): se a CPU esti-
ver ocupada executando processos, en-
tão o trabalho está sendo feito. Uma
medida do trabalho é o número de pro-
cessos concluídos por unidade de tempo,
algo chamado de vazão. Para processos
longos, essa taxa pode ser um processo
por hora; para transações curtas, ela
pode ser 1 O processos por segundo.
• Turnaround (tempo de retorno):
do ponto de vista de um processo especí-
fico, o critério importante é o tempo ne-
cessário para executar esse processo. O
intervalo desde o momento da submissão
de um processo até o momento do tér-
mino é o turnaround. O turnaround é a
soma dosperíodos gastos esperando para
entrar na memória, esperando na fila de
1
prontos (ready queue), executando na
CPU e realizando E/S.
• Tempo de espera: o algoritmo de es-
calonamento de CPU não afeta a quan-
tidade de tempo durante a qual um pro-
cesso é executado ou realiza E/S; ele
afeta apenas a quantidade de tempo que
um processo gasta esperando na fila de
prontos. O tempo de espera é a soma
dos períodos gastos aguardando na fila
de espera.
• Tempo de resposta: em um sistema
interativo, o turnaround pode não ser
o melhor critério. Em geral, um pro-
cesso pode produzir alguma saída rapi-
damente e pode continuar calculando
novos resultados enquanto os resulta-
dos anteriores estão sendo mostrados ao
usuário. Assim, outra medida é o tempo
desde a submissão de uma requisição até
a primeira resposta ser produzida. Essa
medida, chamada tempo de resposta, é o
tempo gasto para começar a responder,
e não o tempo gasto para a saída da
resposta. O turnaround é limitado pela
velocidade do dispositivo de saída.
É importante maximizar a utilização
e a throughput da CPU, reduzindo o tur-
naround, o tempo de espera e o tempo de
resposta. Na maioria dos casos, otimizamos
o valor da média. Contudo, sob algumas cir-
cunstâncias, é importante otimizar os valores
mínimo ou máximo, ao invés da média. Por
exemplo, para garantir que todos os usuá-
rios recebam um bom atendimento, podemos
tentar reduzir o tempo máximo de resposta.
Investigadores sugeriram que, para
sistemas interativos (como sistemas de
tempo compartilhado), é mais importante
minimizar a variância no tempo de resposta
do que minimizar o tempo de resposta médio.
Um sistema com tempo de resposta razoável
e previsível pode ser considerado mais dese-
jável do que um sistema que seja mais rápido
na média, porém bem variável. Entretanto,
pouco trabalho tem sido feito nos algoritmos
de escalonamento de CPU para reduzir a
variância.
A medida que discutirmos os diver-
sos algoritmos de escalonamento de CPU
na próxima seção, ilustraremos sua opera-
ção. Uma ilustração precisa envolver muitos
processos, cada um sendo uma sequência de
centenas de bursts de CPU e bursts de E/S.
No entanto, para simplificar, consideramos
apenas um burst de CPU (em milissegundos)
por processo em nossos exemplos. Nossa me-
dida de comparação é o tempo de espera
médio.
2 Algoritmos de Escalonamento
O escalonamento de CPU trata do
problema de decidir qual dos processos na
fila de prontos (ready queue) deve ser entre-
gue à CPU. Existem muitos algoritmos de
escalonamento de CPU diferentes.
2.1 Escalonamento First Come First Ser-
ver - FCFS
Certamente o mais simples dos algo-
ritmos de escalonamento de CPU é o algo-
ritmo de escalonamento First Come First
Serve - FCFS (primeiro a chegar, pri-
meiro a ser atendido). Com esse esquema,
o processo que requisita a CPU em primeiro
lugar recebe a CPU primeiro. A implemen-
tação da política FCFS é gerenciada com fa-
cilidade por meio de uma fila FIFO. Quando
um processo entra na fila de prontos (ready
queue), seu PCB é associado ao final da fila.
Quando a CPU está livre, ela é alocada ao
processo na cabeça da fila. O processo em
execução, em seguida, é removido da fila. O
código para o escalonamento FCFS é simples
de escrever e entender.
2.2 Escalonamento Shortest Job First -
SJF
Uma técnica diferente para escalona-
mento de CPU é o algoritmo de escalona-
mento Shortest Job First - SJF (me-
nor tarefa primeiro). Esse algoritmo as-
2
socia a cada processo o tamanho do próximo
burst de CPU do processo. Quando a CPU es-
tiver disponível, ela será alocada ao processo
que possui o menor próximo burst de CPU.
Se os próximos bursts de CPU de dois proces-
sos forem iguais, o escalonamento FCFS será
usado no desempate. Observe que um termo
mais apropriado para esse método de escalo-
namento seria algoritmo do próximo menor
burst de CPU (shortest next CPU-burst al-
gorithm), pois o escalonamento depende do
tamanho do próximo burst de CPU de um
processo, e não do tamanho total. Usamos o
termo SJF porque a maioria das pessoas e
livros-texto refere-se a esse tipo de escalona-
mento como SJF.
2.3 Escalonamento por Prioridade
O algoritmo SJF é um caso especial
do algoritmo de escalonamento por pri-
oridade. Uma prioridade é associada a cada
processo, e a cru é alocada ao processo com
a maior prioridade. Processos com amesma
prioridade são escalonados na ordem FCFS.
Um algoritmo SJF é um algoritmo por prio-
ridade no qual a prioridade (p) é o inverso do
próximo burst de CPU (previsto). Quanto
maior o burst de CPU, menor a prioridade,
e vice-versa.
Observe que discutimos sobre o es-
calonamento em termos de prioridade alta e
prioridade baixa. As prioridades são indica-
das por algum intervalo de números, como
O a 7, ou O a 4095. Contudo, não existeum
acordo geral com relação a se O é a maior ou
a menor prioridade. Alguns sistemas utilizam
números baixos para representar a prioridade
baixa; outros usam números baixos para a
prioridade alta. Essa diferença pode causar
confusão.
2.4 Escalonamento Round-Robin
O algoritmo de escalonamento
Round-Robin - RR (revezamento) foi
criado para sistemas de tempo comparti-
lhado. Ele é semelhante ao escalonamento
FCFS, mas a preempção é acrescentada para
alternar entre os processos. Uma pequena
unidade de tempo, chamada quantum de
tempo ou fatia de tempo, é definida. Um
quantum de tempo costuma variar de 1O a
l00 milissegundos. A fila de prontos é tra-
tada como uma fila circular. O escalonador
de CPU percorre a fila de prontos, alocando
a CPU a cada processo por um intervalo de
tempo de até 1 quantum de tempo.
Para implementar o escalonamento
RR, mantemos a fila de prontos como uma
fila de processos FIFO. Novos processos são
acrescentados ao final da fila de prontos. O
escalonador de CPU apanha o primeiro pro-
cesso da fila de prontos, define um tempori-
zador para interromper após 1 quantum de
tempo e despacha o processo. Em seguida,
acontecerá uma destas duas coisas: o pro-
cesso pode ter um burst de CPU de me-
nos de 1 quantum de tempo. Nesse caso, o
próprio processo liberará a CPU voluntari-
amente. O escalonador prosseguirá, então,
para o próximo processo na fila de pron-
tos. Caso contrário, se o burst de CPU do
processo em execução for maior do que 1
quantum de tempo, o temporizador dispa-
rará e causará uma interrupção no sistema
operacional. Uma troca de contexto será exe-
tutada e o processo será colocadono final da
fila de prontos. Por fim, o escalonador de
CPU selecionará o próximo processo na fila
de prontos.
2.5 Escalonamento Multilevel Queue
Outra classe de algoritmos de esca-
lonamento foi criada para situações em que
os processos são classificados em diferentes
grupos. Por exemplo, uma divisão comum
é feita entre processos de primeiro plano
(interativos) e processos em segundo plano
(batch). Esses dois tipos de processos pos-
suem requisitos diferentes para o tempo de
resposta e, por isso, podem ter necessidades
de escalonamento diferentes. Além disso, os
processos de primeiro plano podem ter pri-
oridade (definida externamente) acima dos
processos de segundo plano.
Um algoritmo multilevel queue
3
(fila multinível) divide a fila de prontos
(ready queue) em várias filas separadas. Os
processos são atribuídos a uma fila, em ge-
ral, com base em alguma propriedade do
processo, como tamanho de memória, priori-
dade do processo ou tipo de processo. Cada
fila possui seu próprio algoritmo de escalo-
namento. Por exemplo, filas separadas pode-
riam ser usadas para processos de primeiro
e segundo plano. A fila de primeiro plano
poderia ser escalonada por um algoritmo
RR, enquanto a fila de segundo plano seria
escalonada por um algoritmo FCFS.
Além disso, é preciso haver escalona-
mento entre as filas, o que é implementado
como um escalonamento preemptivo de prio-
ridade fixa. Por exemplo, a fila de primeiro
plano pode ter prioridade absoluta sobre a
fila de segundo plano.
2.6 Escalonamento Multilevel Feedback-
Queue
Em geral, em um algoritmo de es-
calonamento de fila multinível, os processos
recebem uma fila permanentemente na en-
trada do sistema. Os processos não se movem
entre as filas. Por exemplo, se houver filas
separadas para processos de primeiro e se-
gundo plano, eles não se movem de uma fila
para outra, pois não podem mudar sua na-
tureza de primeiro ou segundo plano. Essa
configuração tem a vantagem do baixo custo
adicional de escalonamento, mas é inflexível.
O escalonamento multilevel
feedback-queue (fila multinível com
feedback), ao contrário, permite que um
processo se mova entre as filas. A idéia
é separar os processos com diferentes
características de burst de CPU. Se um
processo utilizar muito tempo de CPU,
ele será movido para uma fila de menor
prioridade. Esse esquema deixa os processos
I/O-bound e interativos nas filas de maior
prioridade. Além disso, um processo que
espera muito tempo em uma fila de menor
prioridade pode ser movido para uma
fila de maior prioridade. Essa forma de
envelhecimento evita o starvation.
3 Avaliação de Algoritmo
Como selecionamos um algoritmo de
escalonamento de CPU para determinado
sistema? Como vimos na Seção 2, existem
muitos algoritmos de escalonamento, cada
um com seus próprios parâmetros. Como
resultado, a seleção de um algoritmo pode
ser difícil.
O primeiro problema é definir os cri-
térios a serem usados na seleção de um algo-
ritmo. Os critérios normalmente são defini-
dos em termos de utilização de CPU, tempo
de resposta ou throughput. Para selecionar
um algoritmo, primeiro temos de definir a
importância relativa dessas medições. Nos-
sos critérios podem incluir várias medições,
como:
• Maximizar a utilização de CPU sob a
restrição de o tempo de resposta má-
ximo ser de 1 segundo
• Maximizar a throughput de modo que o
turnaround seja (na média) linearmente
proporcional ao tempo de execução total
Quando os critérios de seleção tive-
rem sido definidos, desejamos avaliar os di-
versos algoritmos em consideração.
3.1 Modelagem Determinística
Uma classe importante dos métodos
de avaliação é a avaliação analítica. A ava-
liação analítica usa o algoritmo indicado, e
a carga de trabalho do sistema para pro-
duzir uma fórmula ou número que avalia o
desempenho do algoritmo para essa carga de
trabalho.
Um tipo de avaliação analítica é a
modelagem determinística. Esse método
apanha uma carga de trabalho específica pre-
determinada e define o desempenho de cada
algoritmo para essa carga de trabalho.
4
3.2 Modelos de Enfileiramento
Os processos executados em muitos
sistemas variam de um dia para outro, de
modo que não existe um conjunto estático de
processos (ou tempos) para uso na modela-
gem determinística. Entretanto, o que pode
ser determinada é a distribuição dos bursts
de CPU e E/S. Essas distribuições podem ser
medidas e depois aproximadas ou simples-
mente estimadas. O resultado é uma fórmula
matemática, descrevendo a probabilidade de
determinado burst de CPU. Em geral, essa
distribuição é exponencial e descrita por sua
média. De modo semelhante, a distribuição
de tempos quando os processos chegam no
sistema (a distribuição do tempo de chegada)
precisa ser dada. A partir dessas duas distri-
buições, é possível calcular, para a maioria
dos algoritmos, a média da throughput, da
utilização, do tempo de espera e assim por
diante.
O sistema computadorizado é des-
crito como uma rede de servidores. Cada
servidor possui uma fila de processos em es-
pera. A CPU é um servidor com sua fila
de prontos, assim como o sistema de E/S
com suas filas de dispositivo. Conhecendo as
taxas de chegada e as taxas de serviço, pode-
mos calcular a utilização, o tamanho médio
da fila, o tempo médio de espera e assim
por diante. Essa área de estudo é chamada
análise da rede de enfileiramento.
3.3 Simulações
Para obter uma avaliação mais pre-
cisa dos algoritmos de escalonamento, pode-
mos usar simulações. O uso de simulações
envolve a programação de um modelo do
sistema de computador. As estruturas de da-
dos do software representam os principais
componentes do sistema. O simulador possui
uma variável representando um relógio; à me-
dida que o valor dessa variável é aumentado,
o simulador modifica o estado do sistema
para refletir as atividades dos dispositivos,
dos processos e do escalonador. Enquanto
a simulação é executada, as estatísticas que
indicam o desempenho do algoritmo são co-
lhidas e impressas.
Os dados para controlar a simulação
podem ser gerados de diversas maneiras. O
método mais comum utiliza um gerador de
números aleatórios, programado para gerar
processos, tempos de burst de CPU, che-gadas, saídas e assim por diante, de acordo
com as distribuições de probabilidade. As dis-
tribuições podem ser definidas matemática
(uniforme, exponencial, Poisson) ou empirica-
mente. Se a distribuição tiver de ser definida
empiricamente, as medições do sistema real
sob estudo são tomadas. Os resultados defi-
nem a distribuição dos eventos no sistema
real; essa distribuição pode, então, ser usada
para controlar a simulação.
Contudo, uma simulação controlada
por distribuição pode ser pouco precisa, de-
vido aos relacionamentos entre os sucessivos
eventos no sistema real. A distribuição de
frequência indica apenas quantos ocorrem
em cada evento; ela não indica nada sobre a
ordem de sua ocorrência. Para corrigir esse
problema, podemos usar fitas de rastrea-
mento (trace tapes). Criamos uma fita de
rastreamento monitorando o sistema real e
registrando a seqüência de eventos reais. De-
pois, usamos essa seqüência para controlar
a simulação. As fitas de rastreamento ofe-
recem uma excelente maneira de comparar
dois algoritmos com o mesmo conjunto de
entradas reais. Esse método pode produzir
resultados precisos para suas entradas.
As simulações podem ser caras, exi-
gindo horas de tempo do computador. Uma
simulação mais detalhada pode oferecer resul-
tados mais precisos, mas também exige mais
tempo do computador. Além disso, as fitas
de rastreamento podem exigir uma grande
quantidade de espaço para armazenamento.
Finalmente, o projeto, a codificação e a de-
puração do simulador podem ser uma tarefa
importante.
5
3.4 Implementação
Até mesmo uma simulação possui
precisão limitada. A única maneira precisa
para avaliar um algoritmo de escalonamento
é codificá-lo, colocá-lo no sistema operacional
e ver como funciona. Essa técnica coloca
o algoritmo real no sistema real, para ser
avaliado sob condições de operação reais.
A principal dificuldade dessa técnica
é o alto custo. O custo aparece não apenas
na codificação do algoritmo e na modificação
do sistema operacional para dar suporte a
ele e às suas estruturas de dados exigidas,
mas também na reação dos usuários a um
sistema operacional alterado constantemente.
A maioria dos usuários não está interessada
na montagem de um sistema operacional
melhor; eles simplesmente querem que seus
processos sejam executados e usar seus resul-
tados. Um sistema operacional em constante
mudança não ajuda os usuários a realizarem
seu trabalho.
A outra dificuldade com qualquer
avaliação algorítmica é que o ambiente em
que o algoritmo é utilizado mudará. O ambi-
ente mudará não apenas no modo normal, à
medida que novos programas são escritos e
os tipos de problemas mudam, mas também
como resultado do desempenho do escalona-
dor. Se processos curtos recebem prioridade,
então os usuários podem dividir processos
maiores em conjuntos de processos menores.
Se os processos interativos recebem priori-
dade em relação a processos não interati-
vos, então os usuários podem passar para o
uso interativo.(SILBERSCHATZ; GALVIN;
GAGME, 2004)
Considerações Finais
De um modo geral foi abordado nesse
artigo um tema pouco visto em artigos e que
de certa forma está constantemente sendo
usado por todos que de alguma forma en-
tramos em contato com um computador ou
um sistema operação. Portanto é de extrema
importância se ter uma ideia de como um
escalonamento de CPU funciona e quais são
as avaliações que devem ser feitas para se
utilizar o melhor algoritmo de escalonamento
a fim de conseguir um sistema operacional
mais eficiente e muitas vezes mais rápido.
6
CPU Scheduling Article
Leandro Barra de Mattos ∗
2017, v-1.0
Abstract
In this article we intend to approach
the theoreticians that guide the CPU
Scheduling, besides presenting in a sim-
ple and objective way the algorithms
that can be used to carry out this pro-
cess. A trip around the main email
scalability algorithms is done and how
each of them can in a simple way in-
crease the performance of a computer.
And it is also an analysis of the tech-
niques for evaluating the algorithms
and more suitable for the use of an
operating system.
Keywords: scheduling, CPU, algo-
rithms.
Referências
SILBERSCHATZ, A.; GALVIN, P. B.;
GAGME, G. Sistemas operacionais:
conceitos e aplicações. 6. ed. Rio de Janeiro:
Elsevier, 2004. Citado na página 6.
∗leanmattos93@gmail.com
7
	Resumo
	Críterios de Escalonamento
	Algoritmos de Escalonamento
	Escalonamento First Come First Server - FCFS
	Escalonamento Shortest Job First - SJF
	Escalonamento por Prioridade
	Escalonamento Round-Robin
	Escalonamento Multilevel Queue
	Escalonamento Multilevel Feedback-Queue
	Avaliação de Algoritmo
	Modelagem Determinística
	Modelos de Enfileiramento
	Simulações
	Implementação
	Abstract
	Referências