O escalonamento de processos computacionais é uma atividade
organizacional feita pelo escalonador (scheduler) da CPU ou de um Sistema
Distribuído, possibilitando executar os processos mais viáveis e concorrentes,
priorizando determinados tipos de processos, como os de I/O Bound e os
computacionalmente intensivos.
O escalonador de processos de 2 níveis escolhe o processo que
tem mais prioridade e menos tempo e coloca-o na memória principal, ficando os
outros alocados em disco; com essa execução o processador evita ficar ocioso.
A cada
instante um ou mais processos podem estar no estado pronto:
·
Processos do sistema e de usuários
·
Processos de vários usuários (sistema time-sharing)
·
Mix de processos interativos e batch (simulação, folha
de pagamento)
Escalonador
é responsável por gerenciar a fila de prontos, e escolher qual dos processos
prontos vai ser o próximo a usar CPU(de acordo com as prioridades dos
processos).
Também é responsável por aumentar/diminuir a prioridade dos
processos.
Objetivos
do Escalonamento
·
Maximizar a taxa de utilização da UCP.
·
Maximizar a vazão (“throughput”) do sistema.
o Minimizar o
tempo de execução (“turnaround”).
·
LPRM/DI/UFES 2 Sistemas Operacionais
·
Minimizar o tempo de execução (“turnaround”).
o Turnaround:
tempo total para executar um processo.
·
Minimizar o tempo de espera (“waiting time”):
o Waiting
time: tempo de espera na fila de prontos.
·
Minimizar o tempo de resposta (“response time”).
o Response
time: tempo entre requisição e resposta.
Algoritmos de Escalonamento
Há três
categorias de algoritmos de escalonamento:
Em lote: sistemas não-interativos.
Preemptivo ou não preemptivo com longos intervalos de tempo para cada processo.
Interativo: preempção é essencial.
Em tempo-real: executam somente processos que
visam o progresso daaplicação (e não, genericamente, qualquer processo, como no
casointerativo).
Exemplos de Algoritmos
Round Robin
Cada
processo é executado por um intervalo de tempo (quantum).
Nofinal
desse tempo, se o processo estiver executando, será suspenso e a CPU, alocada a
outro
processo.
Se o
processo terminar, ou for bloqueado, antes do final do quantum, a
CPU também
é passada para outro processo.
Com Prioridades
Uma
prioridade é associada a cada processo, e processos comprioridade superior
devem ser executados primeiro. O escalonador pode diminuir aprioridade dos
processos, para prevenir que os de maior prioridade executemindefinidamente,
com o aumento do seu respectivo tempo de execução.
Múltiplas Filas
Define
classes com prioridades, permitindo que processos que estão naclasse de menor
prioridade executem por 1 quantum; na classe seguinte, por 2 quanta;na próxima
, por 4 quanta; e assim por diante. Quando um processo é interrompido
porexceder esse tempo, a prioridade de sua classe é diminuída.
Tarefas Pequenas Primeiro
Designado
para aplicações não interativas, em que otempo médio de execução é conhecido a
priori. Como o próprio nome diz, essealgoritmo define que tarefas menores devem
ser executadas primeiro.
Policy-Driven
Particiona
a CPU de forma equânime entre os usuários (não entreprocessos) e define que,
para n usuários ligados ao sistema, cada usuário deverá receber1/n do poder da
CPU.5.1.2
Escalonamento Estático e Dinâmico
A diferença
entre uma operação de escalonamento estático e dinâmico é que, noprimeiro,
todos os jobs são conhecidos de antemão e o objetivo é escalonar estes Jobs apenas
uma vez, sendo este escalonamento fixo, já que não é necessário mudá-lo.
Já emum
escalonamento dinâmico, jobs chegam ao sistema em pontos assíncronos de
tempo,enquanto outros estão executando. A cada chegada ou saída de um job no/do
sistema, oconjunto de jobs conhecidos muda.
Tipos de escalonamentos
Escalonamento
não-preemptivo: o processo que obtiver direito de rodar, rodará
até que
seja bloqueado para E/S ou para esperar por outro processo (semáforo, por
exemplo),
ou até terminar.
Escalonamento preemptivo
Há uma
interrupção e suspensão temporária daexecução de processos não bloqueados após
um tempo máximo fixado.
Existem
vários tipos de escalonamentos, dependendo de algumas de suascaracterísticas,
mas citaremos características de outros três:
Sem delay
Nenhuma
máquina é mantida parada enquanto existem operaçõesdisponíveis para
processamento.
Ativo
Nenhuma
operação pode ser completada mais cedo através da alteração da ordem
de
processamento nas máquinas, sem que essa alteração atrase outras operações.
Semi-ativo
Nenhuma
operação pode ser completada mais cedo sem alterar a ordem deprocessamento nas
máquinas. Um escalonamento ativo é sempre semi-ativo, mas ocontrário não é,
necessariamente, verdadeiro.5.2 Tratador de interrupções de Clock.
/* Simulador de Escalonamento de Processos*/
#include
<stdio.h>
#include
<stdlib.h>
/* Estrutura */
struct processos {
int id; /*
Identifição do processo*/
int surto; /*
Tempo de duração do processo*/
int prioridade;
int execucao; /*
Tempo de execução do processo*/
int espera; /*
Tempo de espera do processo*/
struct processos *prox;
};
/* Declarações de Protótipo de função */
struct processos *init_processos (int id, int surto, int prioridade);
void fcfs (struct processos *proc);
void listprocs (struct processos
*proc);
void prioridade (struct processos
*proc);
void rr (struct processos *proc, int quantum);
void sjf (struct processos *proc);
int main (void) {
struct processos *plist, *ptmp;
plist
= init_processos(1, 10, 3);
plist->prox
= init_processos(2, 1, 1); ptmp = plist->prox;
ptmp->prox =
init_processos(3, 2, 3); ptmp = ptmp->prox;
ptmp->prox =
init_processos(4, 1, 4); ptmp = ptmp->prox;
ptmp->prox =
init_processos(5, 5, 2);
/* Simulações executadas*/
listprocs(plist);
fcfs(plist);
sjf(plist);
prioridade(plist);
rr(plist,0);
while (plist != NULL) {
ptmp
= plist;
plist
= plist->prox;
free(ptmp);
};
return(0);
};
/* Inicialização de entrada da lista de processos*/
struct processos *init_processos (int id, int surto, int prioridade) {
struct processos *proc;
proc =
(struct processos*)malloc(sizeof(struct processos));
if (proc == NULL) {
printf("Erro
Fatal: Falha Alocacao de memoria.\nFinalizar.\n");
exit(1);
};
proc->id = id;
proc->surto = surto;
proc->prioridade =
prioridade;
proc->execucao = 0;
proc->espera = 0;
proc->prox = NULL;
return(proc);
};
/* Escalonamento FCFS - o primeiro que chega
/* é o primeiro a sair, ou seja, será executado
primeiro */
void fcfs (struct processos *proc) {
int tempo = 0, inicio, fim;
struct processos *tmp = proc;
printf("\tEscalonamento
FCFS\n");
printf("\n");
while (tmp != NULL) {
inicio = tempo;
tempo += tmp->surto;
fim = tempo;
printf("Processo:
%d\tSurto: %d\tEspera: %d\tRetorno: %d\n", tmp->id, tempo, inicio,
fim);
tmp = tmp->prox;
};
printf("\n\n");
};
/* Listando Processos */
void listprocs (struct processos *proc) {
struct processos *tmp = proc;
printf("\tListagem de
Processos\n");
printf("\n");
while (tmp != NULL) {
printf("Processo: %d\tPrioridade:
%d\tSurto: %d\n", tmp->id, tmp->prioridade, tmp->surto);
tmp = tmp->prox;
};
printf("\n\n");
};
/* Simulação de Processos por Prioridade
* Obs: O processo de menor valor de
prioridade obtem
* prioridade maior na fila de processos */
void prioridade (struct processos *proc) {
int tempo, inicio, fim, maior;
struct processos *copia, *tmpsrc, *tmp,
*maiorprimeiro;
printf("\tEscalonamento por
Prioridade\n");
printf("\n");
/* Replicando Lista
de Processos */
tmpsrc = proc;
copia
= tmp = NULL;
while (tmpsrc != NULL) {
if (copia == NULL) {
copia = init_processos(tmpsrc->id,
tmpsrc->surto, tmpsrc->prioridade);
tmp = copia;
} else {
tmp->prox =
init_processos(tmpsrc->id, tmpsrc->surto, tmpsrc->prioridade);
tmp =
tmp->prox;
};
tmpsrc
= tmpsrc->prox;
};
/* Programa Principal */
tempo = 0;
while (copia != NULL) {
/*
Localiza o proximo processo */
maiorprimeiro = NULL;
maior =
copia->prioridade;
tmp =
copia->prox;
tmpsrc
= copia;
while (tmp != NULL) {
if (tmp->prioridade < maior) {
maior =
tmp->prioridade;
maiorprimeiro =
tmpsrc;
};
tmpsrc
= tmp;
tmp
= tmp->prox;
};
if (maiorprimeiro == NULL) {
/* Verifica se o primeiro
processo possui maior prioridade */
inicio = tempo;
tempo += copia->surto;
fim = tempo;
printf("Processo:
%d\tSurto: %d\tEspera: %d\tRetorno: %d\n", copia->id, tempo, inicio,
fim);
tmpsrc =
copia->prox;
free(copia);
copia = tmpsrc;
} else {
/* Verifica se o primeiro
processo não possui maior prioridade */
tmp = maiorprimeiro->prox;
inicio = tempo;
tempo += tmp->surto;
fim = tempo;
printf("Processo:
%d\tSurto: %d\tEspera: %d\tRetorno: %d\n", tmp->id, tempo, inicio,
fim);
maiorprimeiro->prox =
tmp->prox;
free(tmp);
};
};
printf("\n\n");
};
/* Escalonamento Round-Robin */
void rr (struct processos *proc, int quantum) {
int jobsremain, passes;
struct processos *copia, *tmpsrc, *tmp, *slot;
printf("\tEscalonamento
Round-Robin - Quantum: %d)\n", quantum);
printf("\n");
tmpsrc
= proc;
copia
= tmp = NULL;
while (tmpsrc != NULL) {
if (copia == NULL) {
copia
= init_processos(tmpsrc->id, tmpsrc->surto, tmpsrc->prioridade);
tmp
= copia;
} else {
tmp->prox =
init_processos(tmpsrc->id, tmpsrc->surto, tmpsrc->prioridade);
tmp =
tmp->prox;
};
tmpsrc
= tmpsrc->prox;
};
/* Programa rotina de análise de
prioridade */
jobsremain = 2;
slot
= NULL;
while (jobsremain) {
jobsremain = 0;
/* Seleciona o próximo
processo efetuando sua alocação */
if (slot == NULL) {
slot
= copia;
jobsremain
= 2;
} else {
passes
= 0;
do {
if (slot->prox == NULL) {
passes++;
slot
= copia;
} else {
slot
= slot->prox;
};
} while (passes <= 3 && slot->surto == slot->execucao);
if (passes <= 3) {
jobsremain = 2;
};
};
/* Executa um ciclo */
tmp = copia;
while (tmp != NULL) {
if (tmp->surto>tmp->execucao) {
if (tmp == slot) {
tmp->execucao
+= quantum;
} else {
tmp->espera
+= quantum;
};
};
tmp
= tmp->prox;
};
};
/* Exibe os resultados e elimina as
replicações */
tmp = copia;
while (tmp != NULL) {
printf("Processo: %d\tSurto:
%d\tEspera: %d\tRetorno: %d\n", tmp->id, tmp->surto, tmp->espera,
tmp->execucao + tmp->espera);
tmpsrc = tmp;
tmp
= tmp->prox;
free(tmpsrc);
};
printf("\n");
};
/*
Escalonamento SJF*/
void sjf (struct processos *proc) {
int tempo, inicio, fim, shortest;
struct processos *copia, *tmpsrc, *tmp, *beforeshortest;
printf("\tEscalonamento
SJF\n");
printf("\n");
/* Lista de processos é replicada */
tmpsrc = proc;
copia
= tmp = NULL;
while (tmpsrc != NULL) {
if (copia == NULL) {
copia = init_processos(tmpsrc->id,
tmpsrc->surto, tmpsrc->prioridade);
tmp = copia;
} else {
tmp->prox =
init_processos(tmpsrc->id, tmpsrc->surto, tmpsrc->prioridade);
tmp =
tmp->prox;
};
tmpsrc
= tmpsrc->prox;
};
tempo = 0;
while (copia != NULL) {
/* Encontra o proximo
processo*/
beforeshortest
= NULL;
shortest
= copia->surto;
tmp
= copia->prox;
tmpsrc
= copia;
while (tmp != NULL) {
if (tmp->surto< shortest) {
shortest
= tmp->surto;
beforeshortest
= tmpsrc;
};
tmpsrc
= tmp;
tmp
= tmp->prox;
};
/* Executa processo e
remove ráplica da lista de processos */
if (beforeshortest == NULL) {
/* Aloca o primeiro
processo caso o mesmo seja menor */
inicio = tempo;
tempo += copia->surto;
fim = tempo;
printf("Processo:
%d\tSurto: %d\tEspera: %d\tRetorno: %d\n", copia->id, tempo, inicio,
fim);
tmpsrc = copia;
copia = copia->prox;
free(tmpsrc);
} else {
/* Aloca o primeiro
processo caso não haja
ocorrencia de outro menor
*/
tmp =
beforeshortest->prox;
inicio = tempo;
tempo += tmp->surto;
fim = tempo;
printf("Processo:
%d\tSurto: %d\tEspera: %d\tRetorno: %d\n", tmp->id, tempo, inicio,
fim);
beforeshortest->prox
= tmp->prox;
free(tmp);
}
}
printf("\n\n\n\tAperte
qualquer tecla para execultar o escalonamento RR\n\n\n");
printf("\n");
system ("pause");
}
ALUNOS: Guilherme Henrique Madalozzo, Murilo Luis Bom, Ubirani de Carvalho Junior, Tiago Henrique dos Santos, Nícolas Kenji
