Round-robin

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Round-robin (algoritmo))
Ir para: navegação, pesquisa

Round-robin (RR) é um dos algoritmos mais simples de agendamento de processos em um sistema operacional, que atribui frações de tempo para cada processo em partes iguais e de forma circular, manipulando todos os processos sem prioridades. Escalonamento Round-Robin é simples e fácil de implementar.

Este escalonamento também pode ser aplicado em outros problemas de agendamento, como agendamento de transmissão de pacotes de dados em redes de computadores. O nome do algoritmo vem do principio de round-robin conhecido em outras areas, aonde cada pessoa compartilha equalitariamente uma determinada tarefa.

Escalonamento de Processos[editar | editar código-fonte]

O algoritmo de escalonamento Round-Robin é um dos mais antigos e simples algoritmos, além de ser totalmente imune a problemas de starvation que são tarefas que nunca são executadas em função de ter prioridade inferior as demais. É usado em projetos de sistemas operacionais multitarefa, e foi projetado especialmente para sistemas time-sharing (tempo compartilhado), pois este algoritmo depende de um temporizador (Timer).

Funcionamento[editar | editar código-fonte]

O funcionamento deste algoritmo acontece da seguinte forma: uma unidade de tempo, denominada quantum, é definida pelo sistema operacional, que determina o período de tempo entre cada sinal de interrupção.

Todos os processos são armazenados em uma fila circular. Como no exemplo abaixo.

Round Robin.gif

O agendamento round-robin geralmente emprega tempo compartilhado, dando a cada tarefa um tempo definido chamado quantum. A tarefa é interrompida se esgotando o quantum e retomara de onde parou no proximo agendamento. Sem o tempo compartilhado, tarefas grandes poderiam ser favorecidas em detrimento de tarefas menores.

Exemplo: Se o quantum é 100 milisegundos e a tarefa leva 250 milisegundos para completar, o agendamento round-robin suspenderá a tarefa após os primeiros 100 milisegundos e dara a outra tarefa da fila, o mesmo tempo. Esse tarefa sera executa portanto após 3 agendamentos a saber (100 ms + 100 ms + 50 ms). A interrupção da tarefa é conhecida como preempção.

  • Tarefa1 = Tempo de execução igual a 250 ms (quantum 100 ms).
  • 1. Primeiro agendamento = excecuta tarefa durante 100 ms.
  • 2. Segundo agendamento = mais 100 ms de execução da tarefa.
  • 3. Terceiro agendamento = 100 ms, mas a tarefa termina após os primeiros 50 ms.
  • 4. Total de tempo que a CPU levou para a tarefa1 = 250 mS

Um melhoramento desse agendamento é dividir todos os processos em numeros iguais de frações de tempo e proporcionais ao tamanho da tarefa, assim todos os processos terminam ao mesmo tempo.

Outro exemplo mais complexo do seu funcionamento.

Round Robin2.gif

Ligações externas[editar | editar código-fonte]

Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.