ROUND ROBIN,
uma técnica preemptiva de escalonamento.

A seguir, entenderemos o funcionamento do algoritmo de
escalonamento chamado Round Robin, ou Escalonamento Circular.

O que é escalonamento?

Políticas ou técnicas de escalonamento são uma série de técnicas usadas com o objetivo de se obter uma melhor utilização da CPU. As políticas de escalonamento se dividem em duas classes: aquelas que usam preempção e as que não usam preempção.

> Preempção

Preempção é a interrupção forçada de um processo, para que outro processo de maior prioridade possa usar a CPU. A preempção é usada em sistemas multiprogramados para evitar que um processo monopolize a CPU. A preempção é implementada através de um relógio de tempo real que interrompe a CPU a intervalos de tempo regulares, a fim de que o escalonador de tarefas possa fazer uma reavaliação de prioridades e escalonar outro processo. Este intervalo é a unidade básica de alocação de tempo da CPU e é denominado quantum.

Escalonamento circular (Round-Robin)

É o tipo de escalonamento preemptivo mais simples e consiste em repartir uniformemente o tempo da CPU entre todos os processos prontos para a execução. Os processos são organizados numa fila circular, alocando-se a cada um uma fatia de tempo da CPU, igual a um número inteiro de quanta. Caso um processo não termine dentro de sua fatia de tempo, ele é colocado no fim da fila e uma nova fatia de tempo é alocada para o processo no começo da fila, como ilustrado na figura abaixo:

O escalonamento circular é muito simples, mas pode trazer problemas se os tempos de execução são muito discrepantes entre si. Quando existirem muitas tarefas ativas e de longa duração no sistema, as tarefas curtas terão o seu tempo de resposta degradado, pois as tarefas longas reciclarão continuamente na fila circular, compartilhando de maneira equitativa a CPU com tarefas curtas.

Vídeo

O vídeo exemplifica o funcionamendo do código (em linguagem C) encontrado abaixo. Para maior entendimento, pode-se baixar o arquivo para que ele seja executado na sua própria máquina.

Código

O código em linguagem C abaixo associa o escalonamento circular à situação de uma fila em um banco. O caixa é a CPU, e as pessoas na fila são os processos. Cada processo precisa "pagar" um certo número de "contas" para terminar sua execução, ou seja, usar a CPU por um determinado tempo. Porém, o caixa (CPU) só permite que cada pessoa pague X contas de cada vez. Esse valor X é chamado de Quantum. Se o processo terminar sua execução, ou seja, todas as contas forem pagas, a pessoa sai da fila, caso contrário, volta ao final da fila e espera sua vez novamente. O vídeo acima também exemplifica o funcionamento do código a seguir.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//O código foi escrito baseando-se no exemplo mostrado no vídeo para uma compreensão facilitada
//Pessoas pagando contas em um caixa que só permite certo numero de contas
#include <stdlib.h>
#include <stdio.h> 
#define tam 30 //número máximo de pessoas
 
int pessoas[tam];           //Fila de pessoas
int NumEscolhidoPessoas;
int quantum;                //Numero de contas pra pagar no caixa
 
void contas(){       //Para que o usuario possa testar com diferentes quantidades de contas
    int numero;
    int i;
    for (i=1; i<=NumEscolhidoPessoas; i++){
        printf("\nDigite o numero de contas a pagar da pessoa %d:", i);
        scanf("%d", &numero);               //Leitura de valor inserido pelo usuario
        pessoas[i]= numero;                 //cada pessoa recebe o valor informado
    }
}
 
void fila(){
    int contadorFila=NumEscolhidoPessoas;            //contagem de pessoas que estão na fila
    int frenteFila = 1;                 //Primeira posição da fila
    while(contadorFila !=0){
        while(pessoas[frenteFila] <= 0){ //Tira pessoas que não tem contas da primeira posição
            frenteFila++;
            if(frenteFila>= NumEscolhidoPessoas) //Faz a rotação
                frenteFila=0;
        }
        printf("\n\nA pessoa %d vai para o caixa com %d contas", frenteFila , pessoas[frenteFila]);
        printf("\nPaga ate %d contas", quantum);
        pessoas[frenteFila] = pessoas[frenteFila] - quantum;        //Pagamento de quantum contas
        if( pessoas[frenteFila]<=0){
            printf("\nE sai da fila.\n");
            contadorFila--;
        }
        else{
            printf("\nE vai pro final da fila com %d contas restantes.\n", pessoas[frenteFila]);
        }
        frenteFila++;                               //Atualiza primeira posição
            if(frenteFila>NumEscolhidoPessoas)    //Faz a rotação
                frenteFila=0;
        system("PAUSE");
    }
}
 
main(){
    printf("::::::: Programa exemplo sobre round-robin :::::::");
    printf("\nDigite o numero maximo de contas a pagar no caixa (quantum): ");
    scanf("%d", &quantum);
    printf("\nDigite o numero de pessoas na fila: ");
    scanf("%d", &NumEscolhidoPessoas);
    contas();
    fila();
    printf("\n\n::::::::: Fim ::::::::::\n");
    getch();
}