Escalonamento de processos SO

[pic 1][pic 2][pic 3][pic 4]

Políticas de escalonamento de processos clássicas usando experimentação por simulação

Fabrício Daniel Freitas

1Ciência da Computação /IFMG
Bairro São Luiz - Rua Padre Alberico, 440
Formiga – MG – Brasil
Caixa Postal 35570-000 – Formiga – MG – Brasil
IFMG Campos Formiga – Instituto Federal de Minas Gerais

[e-mail]

Resumo:     Este trabalho irá verificar hipóteses sobre algoritmos de escalona- mentos e verificar suas principais vantagens e desvantagens de um sobre o outro, acerca de certos parâmetros.
"O tema deste trabalho prático é tema avaliação de políticas de escalonamento de processos clássicas usando experimentação."(SILVA, 2014, p.3).

A pedido do professor, neste trabalho são criado hipóteses nas quais o simula- dor irá determinar se esta condizem com sua veracidade ou não.

1. Grupo:

O trabalho foi exigido que fosse feito individualmente.

2. Introdução:

Este trabalho é consiste na construção de uma hipótese acerca de políticas de escalona- mento de processos, em seguinte testar a hipótese dos algoritmos FCFS( First-Come/First- Served) e (SJF) Shortest Job First pois são algoritmos que não necessitam determinar o quantum de tempo, porém ressalta-se que o o simulador também aceita o algoritmo RR (Round Robin), porém este deveria ser determinado o quantum de tempo dos processos.

No final deste documento existe os principais documentos de pesquisa para o auxílio deste trabalho.

2.1. Tema:

Escalonamento de processos.

2.2. Objetivo do Projeto:

O objetivo deste documento é fornecer um relatório de forma detalhada das simulações bem como objetivo e dificuldades na obtenção de dados, utilizando simulador de escalona- mento concernente ao Trabalho Prático 02 da disciplina de Matemática Discreta, proposto pelo professor Diego Mello da Silva.

3. Delimitação do Problema:

O simulador que será utilizado tem capacidade de testar os algortimos First-Come/First- Served (FCFS), Shortest Job First (SJF), Round Robin (RR), Preemptive Shortest Job First (PSJF), Shortest Job First Approximation (SJFA).

Como na disciplina de Sistemas Operacionais foram vistos FCFS, SJF, PSJF e RR estarei me atentando apenas aos FCFS, SJF e por final farei um pequeno teste com o PSJF, excluindo dos testes os algotimos RR (este foi estudado porém nele exige o quantum o que diferencia bastante dos demais) e o SJFA que não foi estudado e também exige um parâmetro extra do alfa.

4. Justificativa da Escolha do Tema:

O tema foi escolhido pelo professor Diego Silva para aplicarmos os conhecimentos já obtidos na disciplina de Sistemas Operacionais do curso de Ciência da Computação do IFMG - Campus Formiga.

5. Metodologia:

Este trabalho será utilizado o simulador Process (CPU) Scheduling da Universidade do Texas, sendo o desenvolvimento do relatório feito no motor MacTex e editado no editor de texto Tex Maker em um sistema operacional MacOS X 10.9 (Mavericks), processador i7, 16gb de ram e versão do Maquina Virtual Java versão 1.6.0.5.

6. Sistemas em lote:

Apesar de atualmente não serem tão populares sistemas em lote os programas a executar são colocados em uma fila, fazendo com que o processador receba um programa após o outro, processando-os em sequência, o que permitia um alto grau de utilização do sistema. O termo lote ainda é utilizado para definir um conjunto de comandos que rodam sem interferência do usuário final, por isso foi escolhido estes dois algoritmos, não preemptivos, o FCFS, e SJF para serem feito os testes.

6.1. Principais critérios de escalonamento:

•        Utilização da CPU, sendo esta deve ser mantida ocupada ao máximo;

•        Throghput - É a taxa de término dos processos, este deve ser maximizado;

•        Turnaround-É o tempo para se completar um processo, este deve ser minimizado;

•        Tempo de Espera - É o tempo gasto na fila de prontos, este também deve ser minimizado;

6.2. Algoritmo FCFS: First-Come, First-Served (Primeiro a chegar é o primeiro a ser servido):

Como já dito, é um algoritmo Não-Preemptivo sendo assim a na CPU é atribuída aos processos (jobs) na ordem em que chegam na FIFO existindo uma única fila de processos prontos (FIFO) sendo que o primeiro job da fila é executado até encerrar ou ser bloqueado. Quando acontece de o job fica bloqueado, executa-se o próximo da fila de prontos e quando job bloqueado torna-se pronto, este vai para o final da FIFO.
Ele possui como vantagens a facilidade de se compreender e implementar e é justo pois quem chega primeiro é atendido antes, porém possui suas desvantagens pois o Tempo Médio de Espera é longo e sensível à variação dos intervalos de picos de CPU e picos de I/O .

6.3. Outras considerações importantes:

Segundo Silberschatz,Galvinand Gagne 2002, O tempo médio de espera é, por vezes, bastante elevado, mas isto depende muito da duração e frequência dos bursts.

6.4. SJF: Shortest Job First (Menor Job Primeiro):

Este também é um algoritmo Não-Preemptivo porém é CPU é atribuída aos jobs que tem o próximo pico de CPU mais curto, utilizando a previsão do próximo pico de CPU dos jobs. Ele associa a cada job o intervalo de seu próximo pico de CPU, fazendo com que a CPU disponível receba o job com próximo pico de CPU mais curto sendo que o critério de desempate é feito pela política FCFS, quando necessário.

Ele possui algumas desvantagens como a dificuldade em saber exatamente a duração do próximo pico de CPU, fazendo com que este não possa ser implementado no escalonador de curto prazo pois não há como estimar a duração do próximo pico de CPU.

6.5. Considerações importantes:

Segundo Silberschatz, apud Melo 2014, a grande vantagem do uso deste algoritmo ele é considerado ótimo para o critério de Tempo Médio de Espera”, bem como Boccardo 2008 diz que o "SJF é ótimo acerca um tempo de espera médio para um dado conjunto de processos”.