Algoritmo de agendamento Round Robin com exemplo
Nathaniel Brooks
⚡ Resumo Inteligente
O escalonamento Round-Robin é o algoritmo preemptivo de CPU mais antigo e simples, onde cada processo pronto é executado por um período de tempo fixo em uma fila cíclica, garantindo uma execução justa e sem inanição para multitarefas.
O que é agendamento Round-Robin?
O nome desse algoritmo vem do princípio round-robin, onde cada pessoa recebe uma parte igual de algo por sua vez. É o algoritmo de agendamento mais antigo e simples, usado principalmente para multitarefa.
No escalonamento Round-Robin, cada tarefa pronta é executada em sequência, apenas em uma fila cíclica, por um período de tempo limitado. Esse algoritmo também oferece execução de processos sem risco de inanição.
Características do agendamento Round-Robin
Aqui estão as características importantes do agendamento Round-Robin:
- Round robin é um algoritmo preventivo.
- A CPU passa para o próximo processo após um intervalo de tempo fixo, chamado quantum de tempo/fatia de tempo.
- O processo interrompido é adicionado ao final da fila.
- O Round Robin é um modelo híbrido que funciona com base em um relógio.
- O intervalo de tempo deve ser o mínimo necessário para a execução de uma tarefa específica. No entanto, esse valor pode variar de sistema operacional para sistema operacional.
- Trata-se de um algoritmo em tempo real que responde ao evento dentro de um limite de tempo específico.
- O método Round Robin é um dos algoritmos mais antigos, justos e fáceis de usar.
- É um método de agendamento amplamente utilizado em sistemas operacionais tradicionais.
Exemplo de agendamento round-robin
Considere os três processos a seguir:
| Fila de Processo | Tempo de explosão |
|---|---|
| P1 | 4 |
| P2 | 3 |
| P3 | 5 |
Passo 1) A execução começa com o processo P1, que possui tempo de burst 4. Aqui, cada processo é executado por 2 segundos. P2 e P3 ainda estão na fila de espera.
Passo 2) No instante t = 2, P1 é adicionado ao final da fila e P2 começa a ser executado.
Passo 3) No instante t = 4, P2 é preemptado e adicionado ao final da fila. P3 começa a ser executado.
Passo 4) No instante t = 6, P3 é preemptado e adicionado ao final da fila. P1 começa a ser executado.
Passo 5) No instante t = 8, P1 tem um tempo de execução de 4. Sua execução foi concluída. P2 inicia a execução.
Passo 6) P2 tem um tempo de execução de 3. Ele já executou por 2 intervalos. No instante t = 9, P2 completa a execução. Então, P3 inicia a execução até sua conclusão.
Passo 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
Vantagens do Escalonamento Round-Robin
Aqui estão as vantagens/benefícios do método de agendamento Round-robin:
- Não enfrenta os problemas da fome ou do efeito de comboio.
- Todos os trabalhos recebem uma alocação justa de CPU.
- Trata de todos os processos sem qualquer 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 agendamento não depende do tempo de execução. É por isso que é facilmente implementado no sistema.
- Depois que um processo é executado por um determinado período de tempo, o processo é preemptado e outro processo é executado por esse determinado período de tempo.
- Permite que o sistema operacional utilize o método de troca de contexto para salvar o estado de processos interrompidos.
- Oferece o melhor desempenho em termos de tempo médio de resposta.
Desvantagens do agendamento round-robin
Aqui estão as desvantagens/contras de usar o escalonamento Round-robin:
- Se o tempo de processamento do sistema operacional for baixo, a produção do processador será reduzida.
- Este método dedica mais tempo à troca de contexto.
- Seu desempenho depende muito do quantum do tempo.
- Não é possível definir prioridades para os processos.
- O agendamento em rodízio não dá prioridade especial às tarefas mais importantes.
- Isso diminui a compreensão.
- Um quantum de tempo menor resulta em uma sobrecarga maior de troca de contexto no sistema.
- Encontrar o quantum de tempo correto é uma tarefa bastante difícil neste sistema.
Pior caso de latência
Este termo é utilizado para o tempo máximo necessário para a execução de todas as tarefas.
- dt = Indica o tempo de detecção quando uma tarefa é adicionada à lista
- st = Indica o momento de transição de uma tarefa para outra
- et = Indica 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
tISR = sum of all execution times
