Escalonamento de Processos, com ênfase no sistema Round Robin

Escalonamento de Processos, com ênfase no sistema Round Robin

Em sistemas de tempo compartilhado, o kernel aloca a CPU a um processo por um período de tempo chamado "fatia de tempo"ou "quantum"; interrompe o processo e escalona outro quando o tempo atribuído expira e reescalona-o para continuar a execução tempo depois. A parte do sistema operacional com as funções acima descritas é chamada de escalonador e o algoritmo utilizado em sua programação é chamado algoritmo de escalonamento.

Os algoritmos de escalonamento se subdividem em três níveis:

• Escalonamento a curto prazo;

- Decide quem vai ganhar a CPU:

 Round robin;

 Escalonamento com prioridade;

 Filas Múltiplas.

• Escalonamento a médio prazo;

- Decide quem vai ocupar a memória:

 Escalonamento Em Dois Níveis.

• Escalonamento a longo prazo.

- Decide quem vai virar processo. Usado em programas do tipo batch.

 Menor Job Primeiro;

 Escalonamento Garantido.

3.5.6 Escalonamento RR (Round-Robin)

No escalonamento RR (Round Robin) ou circular os processos tamb´em s˜ao

organizados numa fila segundo sua ordem de chegada, sendo ent˜ao despachados

para execu¸c˜ao. No entanto, ao inv´es de serem executados at´e o fim

(completion), a cada processo ´e concedido apenas um pequeno intervalo de

tempo (time slice ou quantum). Caso o processo n˜ao seja finalizado neste

intervalo de tempo, ocorre sua substitui¸c˜ao pelo pr´oximo processo na fila de

processos ativos, sendo o processo em execu¸c˜ao interrompido e novamente

colocado na fila de processos prontos, mas em seu fim. Isto significa que ao final

de seu intervalo de tempo, isto ´e, de seu quantum, ocorre a preemp¸c˜ao do

processador, ou seja, o processador ´e designado para outro processo, sendo salvo o contexto do processo interrompido para permitir a continuidade da sua execução quando sua vez chegar novamente.

O escalonamento RR se baseia na utiliza¸c˜ao de temporizadores, constituindo

um algoritmo preemptivo bastante adequado para ambiente interativos,

ou seja, em sistemas em tempo repartido onde coexistem m´ultiplos

usu´arios simultˆaneos sendo, portanto, necess´ario garantir-se tempos de resposta

razo´aveis. A sobrecarga (overhead) imposta pela troca de contexto

representa um investimento para atingir-se um bom n´ıvel de eficiˆencia, pois

com diversos processos em execu¸c˜ao simultˆanea (pseudoparalelismo) ´e poss

´ıvel manter ocupados todos os recursos do sistema.

A determina¸c˜ao do tamanho do intervalo de tempo (quantum) ´e extremamente

importante, pois relaciona-se com a sobrecarga imposta ao sistema

pelas trocas de contexto dos processos ativos. Na Figura 2.5, onde

ilustramos o escalonamento de processos, podemos observar o quantum de

processamento concedido para cada processo e os tempos de preserva¸c˜ao de

recupera¸c˜ao de contexto a cada preemp¸c˜ao. Para cada processo despachado

para execu¸c˜ao ocorre:

1. a recupera¸c˜ao do contexto do processo, que toma um tempo que denominaremos

(trc),

2. a execu¸c˜ao do processo pela dura¸c˜ao do quantum e

3. a preserva¸c˜ao do processo ap´os o t´ermino de seu quantum, a qual

tamb´em toma um intervalo de tempo denotado por (tpc).

Como o tempo tomado para a troca de contexto (ttc) n˜ao ´e ´util do ponto

de vista de processamento de processos dos usu´arios, temos que para cada

janela de tempo concedida aos processos a troca de contexto representa uma

sobrecarga, pois somente o quantum de processamento ´e efetivamente ´util.

Dado que a troca de contexto toma um tempo aproximadamente constante

temos que a sobrecarga pode ser calculada atrav´es da rela¸c˜ao a seguir:

ttc = trc + tpc

sobrecarga = ttc

ttc + quantum

(3.5)

Por exemplo, se o tempo para troca de contexto (ttc) toma 2 ms e o

quantum ´e de 8 ms, temos que apenas 80% do tempo de processamento ´e

´util, ou seja, a sobrecarga imposta pela troca de contexto representa 20%

do processamento.

Podemos tamb´em medir o rendimento proporcionado pelo escalonamento

RR considerando quanto do tempo alocado para cada processo ´e efetivamente

usado para o processamento, ou seja, a rela¸c˜ao entre o quantum

(usado para o processamento) e a soma deste com o tempo para troca de

contexto (tomada para cada processo), como