Algoritmo de programação Round Robin com Exemplo

O que é a programação de Round-Robin?

O nome desse algoritmo vem do princípio round-robin, em que cada pessoa recebe uma parte igual de algo em turnos. É o algoritmo de escalonamento mais antigo e simples, usado principalmente para multitarefa.

No agendamento round-robin, cada tarefa pronta é executada turno a turno apenas em uma fila cíclica por um intervalo de tempo limitado. Este algoritmo também oferece execução de processos sem privação.

Neste tutorial do sistema operacional, você aprenderá:

Características da programação Round-Robin

Aqui estão as características importantes da programação Round-Robin:

  • Round robin é um algoritmo preventivo
  • A CPU é deslocada para o próximo processo após um intervalo de tempo fixo, que é chamado de quantum de tempo / fração de tempo.
  • O processo que é interrompido é adicionado ao final da fila.
  • Round robin é um modelo híbrido que é movido por relógio
  • A fração de tempo deve ser mínima, que é atribuída a uma tarefa específica que precisa ser processada. No entanto, pode ser diferente de sistema operacional para sistema operacional.
  • É um algoritmo de tempo real que responde ao evento dentro de um limite de tempo específico.
  • Round robin é um dos algoritmos mais antigos, justos e fáceis.
  • Método de programação amplamente utilizado no sistema operacional tradicional.

Exemplo de programação round-robin

Considere os três processos a seguir

Fila de processamentoTempo de explosão
P14
P23
P35

Passo 1) A execução começa com o processo P1, que possui tempo de burst 4. Aqui, todo processo é executado por 2 segundos. P2 e P3 ainda estão na fila de espera.

Passo 2 ) No tempo = 2, P1 é adicionado ao final da Fila e P2 começa a executar

Etapa 3) No tempo = 4, P2 é antecipado e adicionado no final da fila. P3 começa a executar.

Passo 4) No tempo = 6, P3 é antecipado e adicionado no final da fila. P1 começa a executar.

Etapa 5) No tempo = 8, P1 tem um burst time de 4. A execução foi concluída. P2 inicia a execução

Etapa 6) P2 tem um tempo de burst de 3. Já foi executado por 2 intervalos. No tempo = 9, P2 conclui a execução. Em seguida, P3 inicia a execução até que seja concluída.

Etapa 7) Vamos calcular o tempo médio de espera para o exemplo acima.

 Wait time P1= 0+ 4= 4 P2= 2+4= 6 P3= 4+3= 7 

Vantagem da programação round-robin

Aqui, estão os prós / benefícios do método de programação round-robin:

  • Ele não enfrenta os problemas de fome ou efeito de comboio.
  • Todos os trabalhos recebem uma alocação justa de CPU.
  • Lida com todo o processo sem nenhuma prioridade
  • Se você souber o número total de processos na fila de execução, também poderá assumir o tempo de resposta do pior caso para o mesmo processo.
  • Este método de programação não depende do tempo de burst. É por isso que é facilmente implementável no sistema.
  • Depois que um processo é executado para um conjunto específico de período, o processo é interrompido e outro processo é executado para aquele determinado período de tempo.
  • Permite que o sistema operacional use o método de comutação de contexto para salvar estados de processos antecipados.
  • Ele oferece o melhor desempenho em termos de tempo médio de resposta.

Desvantagens da programação round-robin

Aqui estão as desvantagens / contras de usar o agendamento round-robin:

  • Se o tempo de divisão do sistema operacional for baixo, a saída do processador será reduzida.
  • Este método gasta mais tempo na troca de contexto
  • Seu desempenho depende muito do quantum de tempo.
  • As prioridades não podem ser definidas para os processos.
  • A programação round-robin não dá prioridade especial a tarefas mais importantes.
  • Diminui a compreensão
  • Menor quantum de tempo resulta em maior sobrecarga de troca de contexto no sistema.
  • Encontrar um quantum de tempo correto é uma tarefa bastante difícil neste sistema.

Latência de pior caso

Este termo é usado para o tempo máximo gasto para a execução de todas as tarefas.

  • dt = Denota o tempo de detecção quando uma tarefa é trazida para a lista
  • st = Denota o tempo de troca de uma tarefa para outra
  • et = Denota o tempo de execução da tarefa

Fórmula:

 Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti + eti) N} + tISR t,SR = sum of all execution times 

Resumo:

  • O nome desse algoritmo vem do princípio round-robin, em que cada pessoa recebe uma parte igual de algo em turnos.
  • Round robin é um dos algoritmos mais antigos, justos e fáceis e métodos de agendamento amplamente usados ​​no sistema operacional tradicional.
  • Round robin é um algoritmo preventivo
  • A maior vantagem do método de agendamento round-robin é que, se você souber o número total de processos na fila de execução, também poderá presumir o pior caso de tempo de resposta para o mesmo processo.
  • Este método gasta mais tempo na troca de contexto
  • A latência de pior caso é um termo usado para o tempo máximo gasto para a execução de todas as tarefas.