Simulação de Escalonamento de Processos

Prévia do material em texto

13/08/2017 PSSAV - Simulação de Escalonamento de Processos [Artigo]
https://www.vivaolinux.com.br/artigos/impressora.php?codigo=14004 1/7
PSSAV - SIMULAÇÃO DE ESCALONAMENTO DE PROCESSOS
Autor: João Cristiano Monteiro da Silva <jcristiano.c at gmail.com> 
Data: 22/01/2013 
INTRODUÇÃO AO ESCALONAMENTO DE PROCESSOS
No sistema operacional, cada programa em execução constitui um processo. Este processo é definido como
um conjunto necessário de informações para que o sistema operacional implemente a concorrência dos
programas, ou seja, é constituído por:
Contexto de hardware → Armazena o conteúdo dos registradores gerais da CPU e registradores de
uso específico;
Contexto de software → Especifica os limites e características dos recursos que podem ser
alocados pelo processo;
Espaço de endereçamento → Determina a área de memória pertencente ao processo onde
instruções e dados serão armazenados para execução.
Um processo é classificado como CPU-bound ou I/0-bound, de acordo com a utilização do processador e
dos dispositivos de E/S. Portanto:
Processo CPU-bound →: Passa a maior parte do tempo no estado de execução, utilizando o
processador, ou no estado pronto;
Processo I/O-bound → Passa a maior parte do tempo no estado de espera, pois realiza um elevado
número de operações de E/S.
Nos sistemas multi programáveis os processos são executados concorrentemente, compartilhando o uso do
processador, memória principal e dispositivos de E/S, dentre outros recursos. A partir do momento em que
diversos processos podem estar no estado de pronto, deve-se adotar uma política de escalonamento, ou
seja, deve-se estabelecer critérios que determinarão qual processo será escolhido para fazer o uso do
processador. 
Sendo assim, a gerência de processos é uma das principais funções de um sistema operacional,
possibilitando aos programas alocar recursos, compartilhar dados, trocar informações e sincronizar suas
execuções. 
A política de escalonamento é implementada por uma rotina do sistema operacional (denominada
escalonador) e deve possuir as seguintes funções:
Manter o processador ocupado a maior parte do tempo;
Balancear o uso da CPU entre os processos;
Privilegiar a execução de aplicações críticas;
Maximizar a produtividade do sistema;
13/08/2017 PSSAV - Simulação de Escalonamento de Processos [Artigo]
https://www.vivaolinux.com.br/artigos/impressora.php?codigo=14004 2/7
Oferecer tempos de resposta razoáveis para usuários interativos.
Uma política de escalonamento pode ser classificada de acordo com a sua preempção, ou seja, se o
sistema operacional pode interromper o processo em execução e substituí-lo por outro:
Escalonamento não-preemptivo → Quando um processo está em execução nenhum evento externo
pode ocasionar a perda do uso do processador;
Escalonamento preemptivo → O sistema operacional pode interromper um processo em execução e
passá-lo para o estado de pronto, para poder alocar outro processo na CPU. Este modelo permite
que o sistema priorize a execução certos de processos além de balancear o uso da CPU entre os
processos.
ESCALONAMENTOS: FCFS E ROUND-ROBIN
ESCALONAMENTO FCFS
Escalonamento First Come-First Served (FCFS) adota a política de que o processo que chegar primeiro ao
estado de pronto será selecionado para a execução. 
Possui as seguintes características:
Estrutura → Contém uma fila para armazenar os processos que estão no estado de pronto;
Funcionamento → Quando um processo passa para o estado de pronto, ele entrará no final da fila e
será escalonado quando chegar ao seu início;
Classificação → Não preemptivo, pois um processo não pode ser interrompido quando está sendo
executado;
Deficiência → Impossibilidade de prever quando um processo terá a sua execução iniciada; falta de
uma estrutura para melhorar o tempo médio de espera dos processos; processo CPU-bound tem
vantagem em relação ao processo I/0-bound.
ESCALONAMENTO ROUND-ROBIN
Escalonamento Round-Robin (RR), cuja tradução é escalonamento em ciclo, foi o primeiro modelo a propor
uma implementação que simulasse a multitarefa em tempo real. Esta metodologia propõe que os processos
revezem o uso da CPU através de uma unidade de tempo denominada quantum (“q”), cujo valor é
determinado pela implementação do sistema operacional, podendo ter a duração de 10 a 100
milissegundos. 
Após se encerrar o quantum, o processo escalonado deve ceder o lugar na CPU a outro processo. Portanto,
o comportamento da metodologia ocorrerá em função do valor do quantum:
Elevado valor de quantum → Funcionará semelhante ao FCFS, pois os processos poderão ser
executados até o final;
13/08/2017 PSSAV - Simulação de Escalonamento de Processos [Artigo]
https://www.vivaolinux.com.br/artigos/impressora.php?codigo=14004 3/7
Baixo valor de quantum → Haverá grande sobrecarga ao sistema, pois utilizará a maior parte do
tempo para a troca de contexto.
Neste modelo os processos prontos ficam organizados em uma fila circular do tipo FIFO (primeiro a chegar,
é o primeiro a sair). O escalonador percorrerá a fila e revezará a execução dos processos até que todos
acabem. 
Logo, este escalonamento obterá as seguintes características:
Tempo de retorno e de resposta aumenta de acordo com o número de processos na fila;
Maior complexidade de implementação;
Aumento no custo operacional, devido à mudança constante de contexto de processos;
Preemptivo, pois um processo pode ser interrompido quando está sendo executado;
Menor quantidade de processos finalizados em um determinado intervalo de tempo (throughput);
Melhor tempo de resposta.
ESCALONAMENTOS: SHORTEST JOB NEXT E SHORTEST REMAINING TIME
ESCALONAMENTO SHORTEST JOB NEXT
Escalonamento Shortest Job Next (SJN), também citado em algumas fontes de pesquisa como Shortest Job
First (SJF) ou Shortest Process Next (SPN), o algoritmo seleciona o processo que tiver o menor tempo de
execução que resta para executar. 
Assim sendo, o processo que estiver no estado pronto e que necessitar de menor tempo de UCP,
considerando um mesmo contexto, passa a possuir o estado de execução. Esta metodologia busca priorizar
a uniformização do algoritmo de escalonamento Round-Robin, porém, considera o processo em estado de
execução como não apropriativo. 
A implementação desse paradigma de escalonamento foi utilizada com sistemas operacionais exclusivos
para processamento em lote. A cada novo processo admitido pelo sistema, um tempo de execução era
associado ao contexto do software. 
Como não é possível determinar precisamente esse tempo de execução, uma estimativa era realizada
considerando como base análises estatísticas de execuções passadas (heurística), podendo ser fornecidas
pelo usuário ou incorporadas aos programas. Caso o tempo de execução informado fosse muito inferior ao
tempo real, o sistema operacional poderia interromper a execução do processo. 
O principal problema dessa solução é a impossibilidade de estimar o tempo de execução de processos
interativos, já que a entrada de dados é uma ação imprevisível. 
Em sua concepção inicial, o escalonamento SJN é um escalonamento não-preemptivo. Sua vantagem no
escalonamento FCFS está na redução do tempo médio de turnaround1 dos processos, porém, no SJN é
13/08/2017 PSSAV - Simulação de Escalonamento de Processos [Artigo]
https://www.vivaolinux.com.br/artigos/impressora.php?codigo=14004 4/7
possível haver starvation2 para processos com tempo de processador muito longo, ou do tipo CPU-bound. 
Neste modelo, os processos prontos ficam organizados em uma lista em ordem crescente, baseado no
tempo de execução e o momento de chegada. Em suma, esse paradigma de escalonamento pode ser
classificador por:
Mão apropriativa;
Privilegia os processos I/O-bound;
Possui desempenho médio melhor se comparado ao paradigma FCFS;
Possui uma desvantagem de implementação, já que necessita um algoritmo de heurística eficiente;É pouco previsível;
Não é justo com processos longos.
ESCALONAMENTO SHORTEST REMAINING TIME
O algoritmo de escalonamento Shortest Remaining Time (SRT) ou Shortest Remaining First (SRF) é a
variante preemptiva do escalonamento SJF. A fila de processos a serem executados pelo SRT é organizada
conforme o tempo estimado de execução, ou seja, de forma semelhante ao SJN, sendo processados
primeiro os menores jobs. 
Na entrada de um novo processo, o algoritmo de escalonamento avalia seu tempo de execução incluindo o
job em execução, caso a estimativa de seu tempo de execução seja menor que o processo corrente em
execução, ocorre a substituição do processo em execução pelo processo recém chegado. 
A função de seleção pode ser representada simplificadamente por:
A cada mudança de contexto, o processo suspenso pela UCP deve ser recolocado em uma posição
correspondente apenas ao seu tempo restante de execução e não mais o tempo de execução total;
As sobrecargas impostas pela manutenção dos registros de tempos decorridos e pela troca de
contexto da UCP acabam sendo justificado pelo fato de pequenos processos serem executados
praticamente de imediato, minimizando o tempo médio de espera dentro de um cenário mais amplo
e tornando-se útil para sistemas de tempo repartido.
Este algoritmo também se baseia nas estimativas de tempo de execução dos processos, possuindo as
mesmas deficiências do algoritmo SJN, sendo necessário considerar:
Processos com tempo de execução curtos são priorizados;
Processos de maior duração tem seus tempos de espera variáveis em função de jobs menores que
venham a ser executados primeiramente;
Possibilidade potencial de processos grandes sendo adiados por um tempo indeterminado
(starvation) devido ao excessivo favorecimento de processos de curta duração;
Deve-se incluir um mecanismo extra para evitar que um processo, prestes a ser finalizado, sofre
alguma preempção.
13/08/2017 PSSAV - Simulação de Escalonamento de Processos [Artigo]
https://www.vivaolinux.com.br/artigos/impressora.php?codigo=14004 5/7
SOBRE O PROGRAMA DE SIMULAÇÃO E EXECUÇÃO
ONDE OBTER OS ARQUIVOS DE INSTALAÇÃO DO PSSAV
Para simulação do escalonamento abordado nesse artigo, foi utilizado o simulador PSSAV, encontrado no
repositório do code.google.com e acessível pelo link:
http://code.google.com/p/pssav/ (http://code.google.com/p/pssav/)
A versão utilizada pode ser encontrada na seção download do endereço anteriormente informado. Para as
simulações foi utilizado a versão 201007282301 para GNU/Linux (//www.vivaolinux.com.br/linux/). O PSSAV
é um aplicativo que fornece um processo de simulação de escalonamento no nível da UCP. 
Atualmente, o projeto contempla os seguintes recursos:
Animação os processos executados e na fila de espera;
Demonstração e comparativos de diferentes algoritmos de escalonamento;
Configurações personalizadas de processo;
Simulação de mais de um algoritmo considerando um conjunto de processos;
Os dados de saída são representados em forma de tabelas e gráficos;
Suporte aos algoritmos FCFS, SJF (preemptivo e não-preemptivo), PP e Round-Robin.
INSTALAÇÃO DO PSSAV
O presente artigo não compreende os passos necessários para a instalação do sistema operacional onde
será instalado o ambiente de simulação, tornando o estimado leitor livre para executar o ambiente em
diferentes sistemas operacionais de acordo com as próprias preferências. 
Para execução do ambiente de simulação, o usuário deve possuir a JRE previamente instalada e
configurada, de acordo com o ambiente de execução. Aqueles que estão acostumados com o
desenvolvimento de aplicativos utilizando o NetBeans, encontrarão uma grande familiaridade com o
ambiente de simulação. 
Utilizo a distribuição Fedora como SO principal. Então, para realizar a instalação, foi necessário apenas
baixar o script de instalação na página do projeto e atribuir o direito de execução ao arquivo: 
 chmod u+x pssav-linux.sh 
# sh pssav-linux.sh 
Se tudo correr bem o assistente de instalação do PSSAV entrará em execução, podendo ser mantidas as
definições sugeridas e pressionando "Next" para concluir a instalação. Após concluída essa etapa, basta
digitar o comando pssav em uma shell interativa e o programa logo entra em execução. 
SIMULAÇÃO DO PSSAV
13/08/2017 PSSAV - Simulação de Escalonamento de Processos [Artigo]
https://www.vivaolinux.com.br/artigos/impressora.php?codigo=14004 6/7
Com o ambiente de simulação em execução, deve-se primeiramente configurar os tempos de chegada e
execução de cada processo. Para isso, na janela "Scenario Explorer" deve-se fazer um arranjo, tal como
exibido na Figura 1:
(//img.vivaolinux.com.br/imagens/artigos/comunidade/pssav_001.jpg)
Para simplificar os passos necessários, optei por descrever o algoritmo de escalonamento Shortest
Remaining Time (SRT). Para tal, deve-se executar os seguintes passos:
A. Na janela "Scenario Explorer", selecionar o algoritmo "Preemptive Shortest-Jog-First Scheduler" na
categoria "Schedulers";
B. Na guia que se abre, clicar no botão "Play" para reprodução comportamental do algoritmo.
(//img.vivaolinux.com.br/imagens/artigos/comunidade/pssav_002.jpg)
CONCLUSÃO
Espero, com este artigo, ter exposto as características dos principais algoritmos de escalonamento
juntamente com as funcionalidades do PSSAV. 
Mais do que isso, ter sido capaz de enriquecer a compreensão dos alunos de cursos introdutórios de
sistemas operacionais, que sofrem com a ineficiência e ausência de funcionalidades de outras ferramentas
de simulação mais "badaladas". 
Como adendo, é possível percebem a riqueza da ferramenta de simulação quando utilizado no modo
comparativo com outros algoritmos de escalonamentos. Assim, o aluno terá uma percepção geral dos vários
algoritmos simultaneamente, enquanto que o instrutor pode reservar-se a descrever as características de
cada algoritmo na obtenção de um resultado em especial. 
Um comparativo entre algoritmos, pode ser visualizador nas figuras a seguir:
13/08/2017 PSSAV - Simulação de Escalonamento de Processos [Artigo]
https://www.vivaolinux.com.br/artigos/impressora.php?codigo=14004 7/7
 (//img.vivaolinux.com.br/imagens/artigos/comunidade/pssav_003.jpg) 
 (//img.vivaolinux.com.br/imagens/artigos/comunidade/pssav_004.jpg)
Bom, espero ter contribuído. 
Abraços. 
 Voltar (verArtigo.php?codigo=14004)