Round-robin

 Nota: Se procura pelo sistema de competição, veja Competições de todos contra todos.

Round-robin (RR) é um dos algoritmos empregados por escalonadores de processo e de rede, em computação. Como o termo é geralmente usado, fatias de tempo (também conhecidas como quanta de tempo) são atribuídas a cada processo em partes iguais e em ordem circular, manipulando todos os processos sem prioridade (também conhecido como executivo cíclico). O escalonamento Round-robin é simples, fácil de implementar e livre de inanição. O escalonamento Round-robin também pode ser aplicado a outros problemas de escalonamento, como o escalonamento de pacotes de dados em redes de computadores. É um conceito de sistema operacional.

Exemplo da execução de um round-robin com quantum=3.

O nome do algoritmo vem do princípio round-robin conhecido de outros campos, onde cada pessoa pega um compartilhamento de algo igual por vez.

Escalonamento de Processos

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

O funcionamento 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.

O agendamento round-robin geralmente emprega tempo compartilhado, dando a cada tarefa um tempo definido chamado quantum. A tarefa é interrompida se esgotado o quantum e retomará de onde parou no próximo 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. Essa tarefa sera executada 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.

Ligações externas

• Scheduling algorithmem inglês
• Process (computing)em inglês
• Process statesem inglês
• Automated planning and schedulingem inglês
• Dynamic priority schedulingem inglês
• Escalonamento de Processos