PSSAV - Simulação de Escalonamento de Processos

Este artigo tem por objetivo apresentar o escalonamento de processos utilizando a ferramenta "Process Scheduling Simulation, Analyzer and Visualization" (PSSAV). Esta ferramenta é útil para demonstrar de forma didática o comportamento de diferentes escalonamentos, enriquecendo a aprendizagem de estudos introdutórios sobre sistemas operacionais.

[ Hits: 40.929 ]

Por: João Cristiano Monteiro da Silva em 22/01/2013


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 é 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.

Página anterior     Próxima página

Páginas do artigo
   1. Introdução ao escalonamento de processos
   2. Escalonamentos: FCFS e Round-Robin
   3. Escalonamentos: Shortest Job Next e Shortest Remaining Time
   4. Sobre o programa de simulação e execução
Outros artigos deste autor
Nenhum artigo encontrado.
Leitura recomendada

Emacs - Poderoso ambiente de trabalho

KDE4 junto com KDE3 no Debian Lenny

Uso do mkv files creator

iTALC 2.0 - Instalação e Configuração no Ubuntu

StarDict - software de tradução de ótima qualidade!

  
Comentários
[1] Comentário enviado por geekaia em 23/01/2013 - 07:27h

Legal, eu não sabia que este programa existia. Na época que fiz a disciplina de sistemas operacionais o professor utilizava o SOsim "emulado" com o wine.

http://www.training.com.br/sosim/

[2] Comentário enviado por jcristiano em 23/01/2013 - 10:09h

Obrigado pelo comentário, geekaia.

Também usavamos o SOsim, com base no livro Arquiteturas de Sistemas Operacionais.
Depois começamos a usar o EPSOsim ( https://sites.google.com/site/EPSOsim/ ).

Eu acho que o PSSAV possui duas características principais: é multiplaforma e bem mais coerente didaticamente.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts