ESCALONAMENTO DE PROCESSOS

Prévia do material em texto

ALGORITMOS DE ESCALONAMENTO DE PROCESSOS 
 
Emmanuel Bitello1 
Maico Douglas Goulart2 
Rodrigo Lima3 
 
RESUMO 
 
O objetivo deste trabalho é verificar como os escalonamentos de processos 
funcionam e estabelecer uma demonstração de características. Com isso verificar por 
meio desses fatores o algoritmo que se comporta melhor levando em consideração 
tudo que for citado. 
 
 
 
 
 
 
 
 
 
 
 
Palavras-chave: Processos. Sistema. CPU. Escalonamento. Prioridades. 
 
1 Graduando de Análise e Desenvolvimento de Sistemas pela Faculdade de Desenvolvimento do Rio Grande do 
Sul (FADERGS). Endereço Eletrônico: emmanuelbitello@gmail.com; 
2 Graduando de Redes de Computadores pela Faculdade de Desenvolvimento do Rio Grande do Sul (FADERGS). 
Endereço Eletrônico: goulart.maico@gmail.com; 
3 Graduando de Análise e Desenvolvimento de Sistemas pela Faculdade de Desenvolvimento do Rio Grande do 
Sul (FADERGS). Endereço Eletrônico: rodrigo.lima_web@hotmail.com; 
mailto:goulart.maico@gmail.com
mailto:goulart.maico@gmail.com
 
1. INTRODUÇÃO 
 
Quando um ou mais processos estão prontos para serem executados, o 
sistema operacional em si deve decidir qual processo será o eleito para ser executado 
primeiro. Os processos ao serem executados concorrem a CPU. O escalonador 
(scheduler) é a parte de um sistema operacional encarregado de decidir dentre os 
processos prontos qual deles será colocado em execução. Para isso, existem 
situações que devem ocorrer para os processos serem escalonados: 
 
● Quando um processo é criado; 
● Quando um processo termina; 
● Quando um processo faz uma operação de I/O; 
● Interrupção de relógio (sistemas preemptivos). 
 
Critérios do escalonamento: 
● Utilização da CPU 
○ Em geral, é desejável que o processador permaneça a maior parte do 
tempo ocupado. 
● Throughput 
○ Número de processos executados em um determinado intervalo de 
tempo. 
○ Em geral, a maximização do throughput é desejada. 
● Tempo de turnaround 
○ Tempo que um processo leva desde sua admissão no sistema até seu 
término. 
○ Considera tempo de espera para alocação de memória, espera na fila 
de processos prontos, processamento e operações de entrada e saída. 
○ Em geral, a minimização do tempo de turnaround é desejada. 
 
 
● Tempo de resposta 
○ Tempo decorrido do momento da submissão de um pedido ao sistema 
até a primeira resposta produzida. 
○ Em geral, a minimização do tempo de resposta é desejada. 
Os escalonadores são divididos em 3 tipos: 
● Swapper: Seleciona os processos que irão da memória secundária para a área 
comum (processo que ainda não está em estado de pronto) da memória 
principal. Ele é intimamente ligado à gerência de memória. 
 
● Scheduler: Transfere o processo da área comum para a fila de pronto, onde 
irá efetivamente disputar recursos de processamento. 
 
● Dispatcher: Mais comum de escalonador é aquele que transfere os processos 
da fila de pronto para a CPU. Pode ser acionado por interrupções do relógio, 
por chamadas de sistema ou por interrupções de entrada e saída. 
 
Existem alguns tipos de escalonamento, como serão apresentados a seguir. 
 
2. ESCALONAMENTO FIRST-IN-FIRST-OUT (FIFO) 
 
O escalonamento FIFO (First In First Out - “primeiro que entra primeiro que sai”) 
funciona da seguinte maneira: O processo que chegar primeiro, é o primeiro a ser 
acionado para execução. Para que isso ocorra é necessário um fila de processos 
prontos, esperando pelo uso do processador. Quando um processo é acionado ele 
utiliza a CPU sem ser interrompido. 
Essa forma impossibilita prever quando o processo entrará em execução. 
Também há a possibilidade de processos CPU-bound de menor importância no 
sistema prejudicarem processos de I/O-Bound mais prioritários. 
A implementação do FIFO é simples e fácil. Basta manter uma fila de todas as 
páginas na memória. Elas são adicionadas ao final da fila quando lidas para a 
memória. A página que sofre *swap para o disco é sempre escolhida da frente da fila. 
 
 
Figura 1. Escalonamento FIFO Simples - Fonte: IFPR. 
 
3. ESCALONAMENTO SHORTEST-JOB-FIRST (SJF) 
 
O escalonamento SJF é um algoritmo por prioridade que é definida em função 
do uso da CPU. Ele privilegia processos de tamanho menor no uso da CPU. Quando 
a informação sobre o tempo de execução (CPU burst) não se encontra disponível, o 
ciclo deve ser estimado ou usa-se o anterior. Quando os usos de CPU são iguais usa-
se o algoritmo FIFO para desempate da situação. 
Existem dois tipos: O preemptivo, quando um processo entrar para a fila dos 
prontos. Para executar verifica-se se o seu burst é menor que o restante do processo 
atualmente em execução, e, o não preemptivo quando deixa o processo em execução 
terminar o seu CPU burst (uso da CPU). 
Sua utilização fornece o menor tempo médio de espera possível entre os 
processos ativos. Processos I/O bound são favorecidos. 
Nesse algoritmo existe a dificuldade de determinar o tempo do próximo ciclo de 
CPU de cada processo. O uso de prioridade (preempção) pode deixar que alguns 
processos de baixa prioridade fiquem esperando indefinidamente pela CPU. 
 
 
 
Figura 2. Escalonamento SJF - Fonte: Passei Direto. 
 
4. ESCALONAMENTO PREEMPTIVO 
 
O escalonamento preemptivo atribui um período de tempo ao processo. Ao final 
do período fixado, se o processo ainda estiver em execução, será suspenso e outro 
processo será escolhido para ser executado. O período ou quantum é gerenciado por 
um relógio, que possibilita a interrupção a qualquer tempo pelo SO. 
Em sistemas preemptivos um processo pode perder a CPU a qualquer 
momento para outro processo, sem qualquer aviso. Isto gera condições de corrida e 
a necessidade de semáforos, contadores de eventos, monitores, ou algum outro 
método de comunicação interprocessos. 
 
[...] A preempção também afeta o projeto do kernel do sistema operacional. 
Durante o processamento de uma chamada de sistema, o kernel pode estar 
ocupado com uma atividade em nome de um processo. Essas atividades 
podem envolver a alteração de importantes dados do kernel (por exemplo, filas 
de I/O). [...] (SILBERSCHATZ; GALVIN; GAGNE, 2015, p.235) 
 
Atualmente a maioria dos sistemas operacionais utilizam políticas de 
escalonamento preemptivas para os processos. 
 
 
 
 
5. ESCALONAMENTO CIRCULAR (ROUND ROBIN) 
 
O escalonamento circular (round robin scheduling) é um escalonamento do tipo 
preemptivo, que serve especialmente para sistemas de tempo compartilhado. 
Sua principal vantagem é não permitir que os processos monopolizem a UCP, 
sendo o tempo o tempo máximo alocado continuamente igual à fatia de tempo definida 
no sistema. 
Um problema que ocorre é que processos CPU-bound são beneficiados no uso 
do processador em relação aos processos I/O-bound, o que provoca um 
balanceamento desigual no uso processador. 
 
 
Figura 3. Escalonamento Round Robin - Fonte: INF SUL DE MINAS. 
 
 
6. ESCALONAMENTO POR PRIORIDADES 
 
No escalonamento por prioridades, os processos de maior prioridade são 
escalonados preferencialmente. O algoritmo é implementado com um clock, que 
interrompe o processador em determinados intervalos de tempo, reavaliando as 
prioridades e podendo escalonar outro processo. 
Se existir um processo na fila de pronto com prioridade maior que o processo 
em execução, o sistema operacional realiza a preempção deste processo e o 
processo com maior prioridade é escalonado. 
É muito útil em sistemas de tempo real pois permite diferenciar processos de 
acordo com sua importância, porém processos com baixa prioridade podem ficar 
indefinidamente na fila de pronto. 
 
 
 
Figura 4. Escalonamento por Prioridades - Fonte: Universidade de São Paulo. 
 
7. ESCALONAMENTO POR MÚLTIPLAS FILAS 
 
 Nesse escalonamento, os processos associados às filas em função de 
características próprias, como importância para a aplicação, tipo do processamentoou área de memória necessária. 
 A sua principal vantagem é a possibilidade da convivência de mecanismos de 
escalonamento distintos em um mesmo sistema operacional. Nesse mecanismo, o 
processo não possui prioridade, ficando essa característica associada a fila. O 
processo sofre preempção caso um outro processo entre em uma fila de maior 
prioridade’’ 
 
Figura 5. Escalonamento por Múltiplas Filas - Fonte: Universidade de São Paulo. 
● Implementa diversas filas de processos no estado pronto, onde cada processo 
é associado exclusivamente a uma delas. 
● Cada fila possui um mecanismo próprio de escalonamento, em função das 
características dos processos. 
● Cada fila possui uma prioridade associada. 
 
● O sistema só pode escalonar processos de uma fila, se todas as outras de 
prioridade maior estiverem vazias. 
 
8. CONCLUSÃO 
 
Tabela 1 – Escalonamentos e suas características 
Escalonamento Vantagem Desvantagem 
FIFO 
É um escalonamento 
simples de compreender, o 
primeiro a entrar é o 
primeiro a sair. 
Muito sensível a ordem de 
chegada. Se processos maiores 
chegarem primeiro aumentarão o 
tempo médio de espera. 
SJF 
 
Redução do tempo médio 
de turnaround dos 
processos (desde sua 
criação até seu fim). 
Pela entrada de dados ser uma 
ação imprevisível, estimar o 
tempo de uso do processador 
acaba sendo impossível. 
Preemptivo 
Prioriza a execução de 
processos como no caso 
de aplicações de tempo 
real onde o fator de tempo 
é crítico. 
Pode ocorrer interrupção de um 
processo no momento que não 
seria o mais adequado. 
Round Robin 
 
Não permitir que um 
processo monopolize a 
CPU. 
Processos CPU-Bound são mais 
beneficiados no uso do 
processador, diferente dos I/O-
Bound, pois tendem a utilizar a 
fatia de tempo completamente. 
Prioridade 
 
Permite diferenciar 
processos de acordo com 
sua importância. 
 
Sofre de Starvation, quando os 
processos com baixa prioridade 
acabam ficando indefinidamente 
na fila do “pronto”. 
Múltiplas Filas 
Possui diversos 
mecanismos de 
escalonamento em um 
mesmo sistema 
operacional. 
Um processo não pode ser 
redirecionado para outra fila mais 
adequada (para caso, no decorrer 
do tempo, seu comportamento 
seja alterado). 
Fonte: Elaborado pelos autores de acordo com a pesquisa realizada. 
 
 O escalonamento de processos é um subsistema do sistema operacional 
responsável por decidir quais processos serão executados em determinado momento. 
Nos dias atuais os sistemas utilizam de preempção para responder melhor a seus 
diversos processos existentes, somando isso a utilização de outros algoritmos em 
conjunto para uma melhor performance e decisão do escalonador (scheduler). Logo 
a melhor utilização dos escalonamentos é uma adequação conjunta dos algoritmos, 
buscando eficiência para o sistema operacional. 
 
9. REFERÊNCIAS 
 
ALEX COLETTO ENGENHEIRO DE COMPUTAÇÃO. Escalonamento de 
Processos. Disponível em <https://alexcoletta.eng.br/artigos/escalonamento-de-
processos/>. Acesso em: 26 de maio 2020. 
 
FERPA’S BLOG. Escalonamento de Processos. Disponível em 
<https://acessaferpa.wordpress.com/escalonamento-fifo/>. Acesso em: 29 de maio 
2020. 
 
GSIGMA. Gerência do Processador (Escalonamento de Processos). Disponível 
em <https://www.gsigma.ufsc.br/~popov/aulas/so1/cap8so.html>. Acesso em: 27 de 
maio 2020. 
 
IFSULDEMINAS. Redes de Computadores – Fundamentos de Sistemas 
Operacionais – 2º Período. Disponível em 
<https://www.passeidireto.com/arquivo/69218874/escalonamento-sjf>. Acesso em: 
30 de maio 2020. 
 
IME - USP. Gerência do Processador - Adão de Melo Neto. Disponível em 
<https://www.ime.usp.br/~adao/GP.pdf>. Acesso em: 04 de jun 2020. 
 
INSTITUTO DE COMPUTAÇÃO - UNICAMP. Escalonamento de Processos e 
Threads. Disponível em <https://www.ic.unicamp.br/~islene/1s2008-
mc514/sched/sched.pdf>. Acesso em: 28 de maio 2020. 
 
PASSEI DIRETO. Escalonamento-SJF. Disponível em 
<https://www.passeidireto.com/arquivo/69218874/escalonamento-sjf>. Acesso em: 
30 de maio 2020. 
 
PREZI. Algoritmo de escalonamento SJF. Disponível em 
<https://prezi.com/11dgbwmi4efe/algoritmo-de-escalonamento-sjf/>. Acesso em: 29 
de maio 2020. 
 
RAFAEL HENRIQUE DALEGRAVE ZOTTESSO. Escalonamento FIFO. Disponível 
em <http://www.zottesso.com.br/professor/disciplinas/SO/04-
Escalonamento%20FIFO.pdf>. Acesso em: 28 de maio 2020. 
 
SILBERSCHATZ, Abraham. GALVIN, Peter Baer. GAGNE, Greg. Fundamentos de 
Sistemas Operacionais. 9º Edição. Editora LTC, 2015. 
 
SLIDESHARE. Sistemas Operacionais - Escalonamento de Processos. 
Disponível em <https://pt.slideshare.net/TallesNascimentoRodrigues/sistemas-
operacionais-escalonamento-de-processos>. Acesso em: 28 de maio 2020. 
 
UEPG. FIFO Uma abordagem simples. Disponível em 
<https://deinfo.uepg.br/~alunoso/2016/FIFO/index.html>. Acesso em: 28 de maio 
2020. 
https://alexcoletta.eng.br/artigos/escalonamento-de-processos/
https://alexcoletta.eng.br/artigos/escalonamento-de-processos/
https://www.gsigma.ufsc.br/~popov/aulas/so1/cap8so.html
https://www.ime.usp.br/~adao/GP.pdf
https://www.ic.unicamp.br/~islene/1s2008-mc514/sched/sched.pdf
https://www.ic.unicamp.br/~islene/1s2008-mc514/sched/sched.pdf
https://prezi.com/11dgbwmi4efe/algoritmo-de-escalonamento-sjf/
http://www.zottesso.com.br/professor/disciplinas/SO/04-Escalonamento%20FIFO.pdf
http://www.zottesso.com.br/professor/disciplinas/SO/04-Escalonamento%20FIFO.pdf
https://pt.slideshare.net/TallesNascimentoRodrigues/sistemas-operacionais-escalonamento-de-processos
https://pt.slideshare.net/TallesNascimentoRodrigues/sistemas-operacionais-escalonamento-de-processos
https://deinfo.uepg.br/~alunoso/2016/FIFO/index.html