Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C

Escalonamento round-robin

O escalonamento round-robin atribui tempo de CPU, à vez, aos trabalhos prontos, durante no máximo um quantum cada. O exemplo em C simula esta política e calcula o tempo de espera e o tempo de retorno segundo uma regra explícita para a ordem de chegada.

Versão: C23; repository compiler flag, production runtime not attested

Sintaxe

slice = min(remaining, quantum); turnaround = completion - arrival; waiting = turnaround - burst

O escalonamento round-robin (RR) serve uma fila de trabalhos prontos. O trabalho no início executa durante, no máximo, um quantum, ou seja, um intervalo de tempo positivo. Se continuar pronto e não tiver terminado, passa para o fim da fila; os trabalhos concluídos saem, enquanto os bloqueados aguardam fora da fila de prontos. Um quantum mais curto favorece a capacidade de resposta, mas aumenta o custo das mudanças de contexto; em geral, RR não minimiza o tempo médio de retorno.

A ordem de chegada exige uma regra explícita: acrescentar os novos trabalhos ao fim da fila e resolver os empates de forma determinística. Uma chegada durante um quantum não interrompe, por si só, esse intervalo. Nos limites do quantum, é necessário especificar se são processadas primeiro as novas chegadas ou a reinserção do trabalho atual. Aqui, todos os trabalhos chegam no instante 0, pela ordem P1, P2, P3; percorrer o array ciclicamente só é suficiente para esta simplificação.

O tempo de retorno é completion - arrival. O tempo de espera totaliza o tempo passado na fila de prontos, não apenas a espera antes da primeira execução. No modelo considerado, sem E/S nem sobrecarga, equivale a turnaround - burst. O exemplo usa quantum = 2 e necessidades de CPU de 5, 3, 1; os tempos de conclusão são, respetivamente, 9, 8, 5.

Esta é uma simulação determinística de um único processador em unidades de tempo abstratas, não uma configuração do escalonador de um sistema operativo nem uma prova do comportamento das threads C. Âmbito da versão: C23; repository compiler flag, production runtime not attested. A execução num ambiente de produção não está atestada.

Exemplos

#include <stdio.h>

int main(void)
{
    const int quantum = 2;
    const int burst[3] = {5, 3, 1};
    int remaining[3] = {5, 3, 1};
    int completion[3] = {0};
    int time = 0;
    int unfinished = 3;

    while (unfinished > 0) {
        for (int i = 0; i < 3; ++i) {
            if (remaining[i] == 0) {
                continue;
            }
            int slice = remaining[i] < quantum
                      ? remaining[i] : quantum;
            printf("P%d [%d,%d)\n", i + 1, time, time + slice);
            time += slice;
            remaining[i] -= slice;
            if (remaining[i] == 0) {
                completion[i] = time;
                --unfinished;
            }
        }
    }

    puts("job waiting turnaround");
    for (int i = 0; i < 3; ++i) {
        int turnaround = completion[i]; /* arrival = 0 */
        int waiting = turnaround - burst[i];
        printf("P%d %d %d\n", i + 1, waiting, turnaround);
    }
    return 0;
}

Resultado

P1 [0,2)
P2 [2,4)
P3 [4,5)
P1 [5,7)
P2 [7,8)
P1 [8,9)
job waiting turnaround
P1 4 9
P2 5 8
P3 4 5

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes