Algoritmo de Escalonamento FIFO

Prévia do material em texto

Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
55
First-in-First-Out – FIFO (Primeiro que entra é o primeiro que sai) que também 
é conhecido como first come, first served - FCFS (Primeiro que chega é o primeiro a ser 
servido). Esse pode ser considerado o algoritmo de escalonamento mais simples e que não 
é preemptivo. À CPU é atribuída uma lista de processos que são executados na ordem de 
chegada e, basicamente, há uma fila única de processos prontos. Podemos dizer também 
que o processo que chega primeiro ao estado de pronto é o selecionado para execução. 
Esse algoritmo é bastante simples porque é necessária somente uma fila. Os processos que 
passam para o estado de pronto entram no final da fila, enquanto os processos que estão 
sendo executados entram em estado de bloqueado. O próximo da fila está na posição do 
início e são escalonados. Esse algoritmo é fácil de entender e de implementar. Podemos 
Aula 07
TIPOS DE
ESCALONAMENTO
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
56
considerá-lo como um algoritmo justo, pois ele pode ser comparado a uma fila de pessoas 
para comprar ingressos de um show, por exemplo, Repare na figura 1 que se segue, como 
é simples entender esse tipo de algoritmo.
Figura 1
Figura 2
Apesar de ser um algoritmo bastante simples, esse tipo de escalonamento 
apresenta algumas deficiências. Um dos principais problemas é a possibilidade de prever 
quando o processo será executado, já que isso depende do tempo de processamento dos 
outros processos que se encontram na frente. Como esse tipo de escalonamento respeita 
somente a ordem de chagada, ele não tem uma preocupação com o tempo de espera do 
processador. Vamos fazer uma pequena comparação com processos semelhantes, mas 
com um tempo médio diferenciado.
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
57
Vamos analisar a figura 2 na página anterior. Nas primeiras entradas, o processo 
maior está entrando por último. Portanto, um processo menor pode levar mais tempo 
que o esperado para ser processado. Ele só se utiliza do processador depois dos outros 
processos, inclusive o maior, que vai utilizar por mais tempo a CPU. Já na segunda 
entrada dos processos podemos perceber que os processos menores entraram primeiro 
para serem processados. Assim, eles não precisarão esperar muito tempo.
A única diferença que se segue na figura é a da entrada dos processos na fila de 
pronto. O tempo médio de espera dos processos da primeira entrada é igual a (0+10+14)/3 
= 8 u.t. e o tempo médio da segunda entrada de processos é (7+0+4)/3 = 3,7 u.t. A 
diferença que se dá entre as médias de tempo é bastante significativa, e é justificada pela 
diferença dos tempos de processador entre os processos.
Outro problema nesse tipo de algoritmo é que os processos de CPU-bound levam 
vantagem sobre os de E/S-bound. Isso porque no caso de se ter um processo de E/S-bound 
mais importante do que um de CPU-bound, não é possível tratar esse tipo de diferença 
entre os processos.
O tipo de escalonamento FIFO é um algoritmo implementado do tipo não 
preemptivo. Inicialmente foi desenvolvido para sistemas monoprogramáveis, com 
processamento Bach, e se torna ineficiente se for aplicado em ambiente interativo de 
tempo compartilhado.
De certo modo, sistemas em lote permitem um escalonamento em três níveis 
diferentes, ou seja, quando os jobs chegam ao sistema eles são adicionados em uma 
fila de entrada, armazenados em disco, e tem-se um escalonador de admissão que faz 
a decisão de qual dos jobs será adicionado no sistema. Os outros jobs são mantidos na 
fila de entrada por um momento até que sejam selecionados para serem adicionados ao 
sistema. Um algoritmo feito para admissão pode ser uma mescla de jobs orientados à 
computação com jobs orientados à E/S. Mas pensando bem, os jobs curtos poderiam ser 
adicionados com mais agilidade. Enquanto isso, os jobs mais longos ficam esperando, 
pois o escalonador de admissão tem a liberdade de manter alguns jobs na fila de entrada 
e pode colocar depois os jobs que chegam, se estiverem de acordo com a política de 
escalonamento do algoritmo. Quando o job é adicionado no sistema, o processo é criado 
para ele. Assim, ele passa a competir pela CPU, mas o que pode acontecer é que se 
houver um número muito grande de processos, pode não haver espaço suficiente para 
todos na memória. Por isso, alguns processos devem ser levados para o disco. O segundo 
nível de escalonamento é que decide quais processos devem ser mantidos na memória e 
quais permanecerão em disco. Podemos chamar esse tipo de escalonador de escalonador 
de memória. Como o próprio nome sugere, é ele que decide qual processo deve ficar na 
memória e qual deve permanecer em disco. Observe na figura que se segue como pode 
ocorrer o escalonamento em três níveis.
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
58
Escalonamento Shortest-Job-First (SJF), ou seja, o job mais curto primeiro. 
Mas consideremos 4 jobs, sendo “A,B,C,D”, com tempos de processamento de 8,4,4,4, 
respectivamente e vamos deixar que o escalonador escolha o processo que tenha o tempo 
mais curto para processar primeiro. Ao executar nessa ordem, o tempo de retorno para 
o processo “A” é de 8 minutos, para “B” é de 12 minutos, para “C” é de 16 minutos e 
para “D” sequencialmente é de 20 minutos, o que resulta em uma média de 14 minutos. 
Considere agora a execução desses processos mas com a seleção do processo mais curto 
primeiro. Os tempos de retorno agora são 4, 8, 12 e 20 minutos, pois agora ele tem uma 
média de 11 minutos.
Devemos nos atentar que o job mais curto primeiro é muito bom somente se 
todos os Jobs estiverem disponíveis simultaneamente.
Com a versão de um algoritmo que podemos dar a distinção de o próximo job de 
menor tempo restante, ou seja, o próximo job mais curto é o primeiro (shortest remaining 
time next). Esse algoritmo necessita saber previamente o tempo de execução do job e 
quando chega um novo job. O seu tempo total é comparado ao tempo restante do job que 
está sendo executado no momento. Se esse tempo for menor, o job que está em execução é 
interrompido e o job menor é executado. Essa versão do algoritmo é implementada como 
preemptivo. Essa implementação permite que novos jobs tenham um melhor desempenho. 
ESCALONAMENTO COOPERATIVO
A implementação por escalonamento cooperativo é desenvolvida para que seja 
alcançado um grau maior em aplicações de escalonamento que não possuem mecanismo 
de preempção, como o FIFO e o SJF, que são não preemptivos. Para isso, um processo 
em execução pode, voluntariamente, liberar a CPU e retornar à fila de pronto, dando, 
assim, a possibilidade de que outro processo seja escalonado para o uso da CPU. Isso 
Figura 3
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
59
permite melhor uso da CPU. O que se destaca nesse tipo de algoritmo é que a liberação 
da CPU não é responsabilidade do sistema operacional, e sim exclusiva do processo 
que está em execução, que de maneira cooperativa libera a CPU para outro job. Com 
essa implementação de escalonamento, o processo que está em execução faz uma 
verificação periodicamente em uma fila de mensagens para determinar a existência de 
jobs na fila de pronto. 
Mas isso pode causar alguma dor de cabeça, pois como a interrupção não é 
de responsabilidade do sistema operacional e sim do processo que está em execução, 
o que pode ocorrer é um processo não verificar a fila de mensagens. Nesse caso, os 
outros processos não terão a chance de ser executados até a liberação da CPU pelo job 
em execução. Isso pode causar um problema para a multiprogramação cooperativa, 
na medida em que uma aplicação pode ficar por muito tempo em processamento, 
utilizando a CPU.
ESCALONAMENTO CIRCULAR 
Escalonamento circular ou (round Robin sheduling), é do tipo preemptivo. 
É um tipo de escalonamento produzido para sistemas de tempo compartilhado. Esse 
algoritmoé muito semelhante ao sistema do tipo FIFO (Fisrt-in-First-out), mas com uma 
diferença, a de que quando o processo passa para o estado de execução ele tem um tempo 
predeterminado, ou seja, um tempo limite de uso do processador, que é denominado fatia 
de tempo (Time-slice) ou, também, conhecido como quantum. No escalonamento circula 
quando o processo é escalonado para a sua execução. Logo uma nova fatia de tempo é 
determinada. Caso essa fatia de tempo seja excedida, o sistema operacional interrompe 
o processo que está em execução, salva todo seu contexto e direciona o processo para o 
final da fila. Todo esse mecanismo é denominado de preempção por tempo. Esse sistema 
de escalonamento circular é considerado um dos mais simples e mais justos, porque a 
cada processo é atribuído o seu intervalo de tempo e, quando termina o seu tempo, ele 
passa para o final da fila e outro processo se utiliza da CPU, já com a sua fatia de tempo 
predeterminada. 
Observe na figura que se segue e veja que a fila de processos em estado de 
pronto é tratada como uma fila circular. O escalonamento é feito normalmente quando 
o processo da fila está em estado de pronto. O processo ficará em execução até que ele 
conclua o processamento ou que sua fatia de tempo termine. Aí ele sofre uma preempção 
pelo sistema operacional. Depois disso, outro processo é escalonado, tendo como critério 
a política de FIFO.
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
60
Cada sistema operacional tem sua política de tempo estabelecida para a 
fatia. Essa fatia de tempo pode variar de 10 a 100 milissegundos, valor que afeta 
diretamente o desempenho do sistema de escalonamento circular. Pode ser que com 
uma fatia de escalonamento muito alta, esse algoritmo caia no mesmo comportamento 
do algoritmo de escalonamento FIFO. Por outro lado, se tiver uma fatia de tempo 
muito pequena, pode ser que tenhamos um problema como um número muito alto de 
preempções, o que ocasionaria a baixa no desempenho do sistema, afetando, assim, o 
tempo de turnaround dos processos.
A grande vantagem do escalonamento circular é permitir que um processo não 
fique o tempo todo usando a CPU, sendo que a quantidade de tempo de utilização é igual 
à fatia de tempo definida no sistema. O escalonamento circular é muito adequado para 
sistemas de tempo compartilhado em que há diversos processos interativos concorrendo 
para o uso da CPU. Uma das desvantagens da utilização desse sistema de escalonamento 
é que os processos de CPU, os CPU-bound têm vantagens sobre os processos de E/S, 
os E/S-bounds, devido à característica do sistema. Os processos CPU-bounds tendem a 
utilizar, por completo, a fatia de tempo, enquanto os processos E/S-bounds estão mais 
possibilitados a passar para o estado de espera antes de sofrer preempção por tempo, o 
que influencia em uso desigual do processador entre os processos.
Para amenizar a situação, um aprimoramento nesse tipo de escalonamento é 
colocado, como mostra a figura abaixo. É criada uma fila auxiliar de pronto, ou seja, ele 
sai da fila e do estado de espera e vai para outra fila em estado de pronto. Tais processos, 
da fila auxiliar, têm preferência no escalonamento em relação à outra fila. O escalonador 
só escalona um processo da fila de pronto quando a fila auxiliar estiver vazia. E quando 
o processo é escalonado a partir da fila auxiliar, a sua fatia de tempo é calculada como 
sendo o valor da fatia de tempo do sistema, menos o tempo de processador que o processo 
utilizou na última vez em que foi escalonado a partir da primeira fila, a fila de pronto. 
Figura 4
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
61
Esse algoritmo tem um grau maior de complexidade, mas com a vantagem de que ele 
balanceia melhor o uso do processador, o que o torna mais equilibrado.
ESCALONAMENTO POR PRIORIDADE
Podemos observar em uma fila de pessoas, que algumas podem ter prioridade 
de atendimento. O mesmo pode acontecer com o escalonamento por prioridade. Em 
filas onde não se tem prioridade, cada um se utiliza do serviço com o tempo necessário 
para resolver o seu problema, igual ao que ocorre com os processos em um sistema de 
escalonamento sem prioridade.
Em computadores que possam ter apenas um proprietário, podem existir vários 
processos, mas, alguns dos processos podem ter uma importância maior que o outro. 
Pode-se dizer, então, que alguns processos têm mais prioridade de processamento que 
outros. Nesse tipo de escalonamento, o processo que está na fila em seu estado de pronto 
e que tem maior prioridade, é sempre o escolhido para o uso da CPU. E os processos que 
têm valores iguais são escalonados seguindo critérios do tipo de escalonamento FIFO. 
Este tipo de escalonamento é preemptivo. Sua preempção é associada ao valor de cada 
processo, que é chamado de prioridade de execução. Nesse tipo de escalonamento, o uso 
de fatia de tempo não existe e como consequência, o processo em execução não pode ter 
nenhuma preempção por tempo.
Nesse tipo de escalonamento, o uso da CPU só terá perda caso o processo tenha 
uma mudança voluntária para o estado de pronto, ou se um processo com maior prioridade 
passar para o estado de pronto. No caso de o processo que passar para o estado de pronto 
tiver algum processo em execução, mas com uma prioridade menor, o sistema operacional 
se encarrega de interromper o processo corrente, salvar seu contexto e colocá-lo em 
estado de pronto. Esse tipo de escalonamento é chamado de preempção por prioridade. 
Após isso, o processo com maior prioridade é escalonado.
Figura 5
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
62
Observe a figura 6, para cada tipo de prioridade existe uma fila de processos 
em estado de pronto. O escalonamento ocorre na medida em que o processo dá 
mais prioridade e está no estado de pronto. Assim ele é escalonado e colocado em 
execução até o seu término ou até que fique em estado de espera voluntariamente 
ou que ocorra uma preempção, no caso de um processo com mais prioridade estar 
na fila em estado de pronto.
Veja na figura, em uma escala de prioridade, em que o grau de maior prioridade 
tem o valor 5 e o de menor, valor 1.
 
O escalonamento por prioridade pode ser implementado de modo que não se use 
a preempção. Pode ser de uma maneira simplificada, apenas colocando os processos com 
maior prioridade na frente da fila, em estado de pronto, e os processos deixam o estado 
de execução apenas quando terminarem o uso da CPU.
Figura 6
Figura 7
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
63
Cada sistema operacional tem a sua própria faixa de valores de prioridade. Alguns 
têm valores de 0 a 31, sendo que o de valor maior tem prioridade. Os outros têm o valor 
de 0 a 127, mas os de menor valor têm prioridade.
A prioridade de execução é classificada por características do software de 
um processo, e pode ser classificada estática ou dinamicamente. Com a prioridade 
estática, o processo não tem o seu valor de priorização alterado. Por outro lado, a 
prioridade dinâmica pode ser ajustada de acordo com os critérios definidos pelo sistema 
operacional. Cada processo do sistema tem suas características e critérios de prioridade 
com possibilidade de alterar o valor da prioridade do processo. Isso permite que se 
possa ajustar os critérios de escalonamento. Claro que isso ocorre de acordo com o 
comportamento de cada processo no sistema.
Um problema nesse tipo de escalonamento é causado por processos de baixa 
prioridade, pois eles podem não ser escalonados, ficando permanentemente na fila de 
pronto. Esse problema é denominado starvation, e pode ser resolvido principalmente 
em sistemas que são implementados com prioridade dinâmica, é a técnica de aging. 
Essa solução funciona da seguinte maneira: ele incrementa gradualmente a prioridade 
dos processos que permanecem na fila por um longo período de tempo. Esse tipo de 
escalonamento tem a capacidade de diferenciaros processos por meio de critérios de 
importância, e os processos com um grau maior de prioridade têm a preferência para serem 
escalonados. Esse tipo de técnica é muito útil para sistemas de tempo real, em aplicações 
de controle de processo e também em aplicações de sistemas de tempo compartilhado.
ESCALONAMENTO CIRCULAR COM PRIORIDADE
É um tipo de escalonamento que tem como implementação a fatia de tempo 
e a prioridade de execução ligadas a cada processo. Os processos, nesse modo de 
escalonamento, ficam no estado de execução até o término do seu processamento, até 
que voluntariamente ele passa para o estado de espera ou que aconteça uma preempção 
por tempo ou por prioridade. Com isso, espera-se melhor distribuição do processador 
entre os processos, e os processos de E/S-bound recebem do administrador do sistema 
valores maiores de prioridade do que os de processos de CPU-bound. Com isso, o sistema 
operacional se torna mais justo entre esses tipos de processos CPU-bound e E/S-bound. 
É uma forma de compensar os processos de E/S-bound, compartilhando o processador 
de forma mais igualitária. Esse tipo de escalonamento é muito utilizado em sistemas de 
tempo compartilhado.
No escalonamento circular com prioridade tem-se duas modalidades, do tipo 
dinâmica ou estática. No escalonamento circular com prioridade estática, sua prioridade 
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
64
é dada através do contexto de software de cada processo que permanece sem alteração 
durante a sua existência. Já no escalonamento circular com prioridade dinâmica, pode 
ser possível a alteração da prioridade de um processo dinamicamente, que pode ser 
ocasionado pelo administrador do sistema ou até mesmo por algumas políticas do próprio 
sistema operacional.
Algum ajuste dinâmico de prioridade dos processos são definidos pelo sistema 
operacional. Para isso é tirada uma base do comportamento dos processos. Esse é um 
exemplo de comportamento adaptativo. Com isso, é possível um melhoramento no 
balanceamento e na utilização da CPU por processos de diferentes perfis. Algumas 
operações são mais lentas que outras. Isso faz com que o processo permaneça por mais 
tempo no estado de espera. Com isso, os processos que permanecem por mais tempo na 
espera têm um ganho no uso do processador, para que seja compensado em relação aos 
processos de CPU-bound. Devemos lembrar que os processos de CPU-bounds não são 
prejudicados por esse tipo de escalonamento, pois eles podem ser executados durante o 
tempo de espera dos processos de E/S-bound.
FILAS MÚLTIPLAS
O escalonamento por múltiplas filas (multilevel queue scheduling) é aquele que 
tem várias filas de processo pronto e cada uma das filas com a sua prioridade definida. A 
cada processo é designada a fila apropriada, através de características próprias, contando 
com a importância da aplicação, o tipo de processamento ou a área de memória necessária. 
Assim, o processo é designado à sua fila. 
Como vimos que os processos possuem características distintas, um único 
mecanismo torna-se inviável para atender a todos os tipos de processos. Por essa razão há 
uma grande vantagem no tipo de escalonamento de múltiplas filas. A sua grande vantagem 
é que se tem tipos de mecanismos de escalonamento diferentes em um sistema operacional. 
Cada fila possui o seu próprio tipo, pois alguns processos podem ser escalonados por um 
mecanismo de FIFO e outro pode ser escalonado no tipo de escalonamento circular. O 
mecanismo não dá prioridade aos processos, e isso fica associado à fila. Nesse tipo de 
sistema, o processo sofre preempção, mas isso se um outro processo entra em fila e esse 
processo tenha uma prioridade maior do que aquilo que está em execução. O sistema 
operacional somente escalona processos de uma determinada fila, caso todas as outra, 
com maior prioridade estejam vazias.
Veja na figura 8, logo abaixo, uma exemplificação de como pode ficar um 
escalonamento por filas múltiplas.
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
65
Escalonamento por múltiplas filas com Realimentação é um tipo de escalonamento 
quase igual ao de múltiplas filas. A diferença é que um funciona com realimentação e 
os processos podem mudar de fila durante o seu processamento. Sua grande vantagem 
é permitir que o sistema operacional identifique dinamicamente o comportamento do 
processo e o coloque na fila de prioridade e, também, o tipo de escalonamento mais 
adequado. Permite que o processo seja colocado em diversas filas, fazendo com que o 
sistema operacional implemente um mecanismo adaptativo.
ATIVIDADES 
As atividades referentes a esta aula estão disponibilizadas na ferramenta 
“Atividades”. Após respondê-las, envie-nas por meio do Portfólio- ferramenta do 
ambiente de aprendizagem UNIGRAN Virtual. Em caso de dúvidas, utilize as ferramentas 
apropriadas para se comunicar com o professor.
Figura 8
Sistemas Operacionais I - France Ricardo Marques Gonzaga - UNIGRAN
66