O Round Robin (RR) é um dos algoritmos mais simples de escalonamento de processos em sistemas operacionais. Ele dá a cada processo uma fatia de tempo igual, em ordem circular, sem prioridades. Foi pensado para sistemas de tempo compartilhado, em que vários usuários e programas dividem a CPU.
Como funciona
- Os processos prontos ficam em uma fila circular.
- O sistema define um quantum, o tempo máximo que cada processo usa a CPU de cada vez.
- O primeiro da fila executa. Se terminar dentro do quantum, sai; se não, é interrompido (preempção) e volta para o fim da fila.
- O próximo da fila recebe a CPU, e assim por diante até todos terminarem.
Um temporizador gera a interrupção ao fim de cada quantum.
Exemplo
Quantum de 100 ms e três processos: P1 precisa de 250 ms, P2 de 100 ms e P3 de 150 ms, todos chegando no instante 0.
| Intervalo (ms) | Processo | Restante depois |
|---|---|---|
| 0 a 100 | P1 | 150 |
| 100 a 200 | P2 | 0 (terminou) |
| 200 a 300 | P3 | 50 |
| 300 a 400 | P1 | 50 |
| 400 a 450 | P3 | 0 (terminou) |
| 450 a 500 | P1 | 0 (terminou) |
O tempo total de CPU foi de 500 ms, e cada processo avançou de forma justa.
Simulação em Python
from collections import deque
def round_robin(processos, quantum):
fila = deque(processos.items()) # (nome, tempo restante)
tempo = 0
while fila:
nome, restante = fila.popleft()
usa = min(quantum, restante)
print(f"{tempo:>4} a {tempo + usa:<4} -> {nome}")
tempo += usa
if restante > usa:
fila.append((nome, restante - usa)) # volta ao fim da fila
else:
print(f" {nome} terminou em {tempo} ms")
round_robin({"P1": 250, "P2": 100, "P3": 150}, quantum=100)Vantagens
- Simples de implementar.
- Justo: todos os processos recebem CPU, sem starvation (inanição).
- Bom tempo de resposta para sistemas interativos.
Desvantagens
- A troca de contexto a cada quantum tem custo.
- Não considera prioridades nem a duração dos processos.
- O tempo médio de espera pode ser maior que em algoritmos como SJF.
Como escolher o quantum
Quantum muito pequeno gera troca de contexto em excesso e desperdiça CPU. Quantum muito grande faz o RR se comportar como o FCFS (primeiro a chegar, primeiro a ser atendido) e piora a resposta. Valores típicos ficam na casa de dezenas de milissegundos.