O que é agendamento round-robin?

Question

Em um contexto de sistema operacional multitarefa, às vezes você ouve o termo agendamento round-robin.A que se refere?
Que outro tipo de agendamento existe?

Answer 1

Agendamento Round Robin

Se você for o anfitrião de um grupo de 100 convidados, o agendamento round-robin significaria que você gastaria 1 minuto (um valor fixo) por convidado.Você analisa cada convidado um por um e, após 100 minutos, terá passado 1 minuto com cada convidado.Mais sobre Wikipédia.

Existem muitos outros tipos de agendamento, como o baseado em prioridade (ou seja,pessoas mais importantes primeiro), ordem de chegada, primeiro a chegar, primeiro a servir (ou seja,pessoa que sai mais cedo primeiro), etc.Você pode começar pesquisando algoritmos de agendamento no Google ou dar uma olhada agendamento na Wikipedia

Answer 2

O timeslicing é inerente a qualquer sistema de agendamento round-robin na prática, AFAIK.

Discordo da implicação do InSciTek Jeff de que o seguinte é agendamento round-robin:

Ou seja, cada tarefa com a mesma prioridade na rotação round-robin pode ser executada até atingir uma condição de bloqueio de recursos antes de passar para a próxima tarefa na rotação.

Não vejo como isto poderia ser considerado round-robin.Na verdade, este é um agendamento preventivo.No entanto, é possível ter um algoritmo de agendamento que tenha elementos de agendamento round-robin e preemptivo, o que o VxWorks faz se o agendamento round-robin e a preempção estiverem habilitados (o round-robin está desabilitado por padrão).A maneira de habilitar o escalonamento round-robin é fornecer um valor diferente de zero em kernelTimeSlice.

Eu concordo com esta afirmação:

Portanto, embora o agendamento baseado em divisão temporal implique agendamento round-robin, o agendamento round-robin não requer divisão temporal igual baseada em tempo.

Você está certo ao dizer que não requer tempo igual.A preempção pode atrapalhar isso.E, na verdade, no VxWorks, se uma tarefa for interrompida durante o agendamento round-robin, quando a tarefa obtiver o controle novamente, ela será executada pelo restante do tempo em que foi alocada.

Editar direcionado ao Inscitek Jeff (não tenho privilégios de comentários) Sim, eu estava me referindo ao bloqueio de tarefas/interrupção, embora eu obviamente não tenha me expressado muito bem.Você me antecipou (ha!) Com seu segundo comentário.Espero debater o ponto mais importante, que você acredita que o agendamento round-robin pode existir sem redução de tempo.Ou você quis dizer apenas divisão de tempo baseada em tempo igual?Discordo do primeiro, mas concordo com o segundo.Estou ansioso para aprender.Obrigado.

Edit2 dirigido a Jeff:

O round-robin pode existir sem divisão temporal.Isso é exatamente o que acontece no VxWorks quando o kernelTimeSlice está desabilitado (zero).

Não concordo com esta afirmação.Ver esse documento seção 2.2.3 com o título Agendamento Round-Robin.

A programação de Round-Robin usa o fatiamento do tempo para obter uma alocação justa da CPU para todas as tarefas com a mesma prioridade.Cada tarefa, em um grupo de tarefas com a mesma prioridade, é executada para um intervalo definido ou uma fatia de tempo.O agendamento redondo-robin é ativado ligando para o KerNelTImElice (), que leva um parâmetro para uma fatia de tempo ou intervalo....] Se o agendamento redondo-robin estiver ativado e a preempção estiver ativada para a tarefa de execução, o manipulador de carrapatos do sistema incrementa a contagem de fatias de tempo da tarefa.

O timeslicing é inerente ao agendamento round-robin.Caso contrário, você estará contando com uma tarefa para abrir mão do controle da CPU, que o agendamento round-robin pretende resolver.

Answer 3

As respostas aqui e até mesmo o artigo da Wikipedia descrevem a programação round-robin para incluir inerentemente o timeslicing periódico.Embora isso seja muito comum, acredito que o agendamento Round-Robin e o timeslicing são não exatamente a mesma coisa.Certamente, para que o timeslicing faça sentido, o agendamento round-robin está implícito ao girar para cada tarefa, no entanto, você pode fazer o agendamento round-robin sem ter timeslicing.Ou seja, cada tarefa com a mesma prioridade na rotação round-robin pode ser executada até atingir uma condição de bloco de recursos e só então ter a próxima tarefa na rotação executada.Em outras palavras, quando existem tarefas de igual prioridade, os pontos de reescalonamento são não tempo preventivo.

A ideia acima é realmente realizada especificamente no caso do kernel VxWorks de Wind River.Dentro de seu esquema de prioridade, as tarefas de cada prioridade são executadas em rodízio, mas não são divididas em intervalos de tempo sem ativar especificamente esse recurso no kernel.A razão para essa flexibilidade é evitar a sobrecarga de tarefas de divisão de tempo que já são executadas em um bloco dentro de um tempo bem limitado.

Portanto, embora o agendamento baseado em divisão temporal implique agendamento round-robin, o agendamento round-robin não requer divisão temporal igual baseada em tempo.

Answer 4

Uma opinião.Parece que estamos entrelaçando dois mecanismos em um.Assumindo apenas a afirmação original do OP "Em um contexto de sistema operacional multitarefa", então

1 – Um agendador round robin sempre agenda o próximo item em uma fila circular.

2 - A forma como o escalonador recupera o controle para executar o escalonamento é separada e não relacionada.

Não discordo que o método mais prevalente para 2 seja a redução do tempo/produção de espera pelo recurso, mas como foi observado, existem outros.Se não me engano, os primeiros Macs não utilizavam divisão de tempo, eles usavam rendimento voluntário / rendimento aguardando recursos (células cerebrais de mais de 20 anos podem estar erradas às vezes;).

Answer 5

Round robin é um algoritmo de agendamento simples onde o tempo é dividido igualmente entre tarefas sem prioridade.

Por exemplo - se você tiver 5 processos em execução - cada processo poderá ser executado por 1/5 unidade de tempo antes que outro processo possa ser executado.O round robin normalmente é fácil de implementar em um sistema operacional.

Answer 6

Na verdade, você está ficando confuso com agendamento preventivo e round robin.Infact RR faz parte do agendamento preemptivo.

Answer 7

O agendamento Round Robin é baseado no compartilhamento de tempo, também conhecido como quantum (tempo máximo concedido pela CPU para qualquer processo de uma só vez).Existem vários processos (que requerem tempos diferentes para serem concluídos, também conhecidos como tempo de intermitência) em uma fila e a CPU precisa processá-los todos, de modo que continua alternando entre os processos para dar a cada processo tempo igual com base no valor quântico.Esse tipo de agendamento é conhecido como agendamento Round Robin.Confira este vídeo simples para entender facilmente a programação round robin: https://www.youtube.com/watch?v=9hw-_qJ55K4