WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C

Round-Robin-Verfahren

Beim Round-Robin-Verfahren erhält jeder bereite Job der Reihe nach höchstens ein Zeitquantum Prozessorzeit. Das C-Beispiel simuliert diese Strategie und berechnet Warte- und Durchlaufzeit anhand einer ausdrücklich festgelegten Reihenfolge der Ankünfte.

Version: C23; repository compiler flag, production runtime not attested

Syntax

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

Round-Robin-Scheduling (RR) bedient eine Warteschlange bereiter Jobs. Der Job an der Spitze läuft höchstens für ein Quantum, also ein positives Zeitintervall. Ist er danach noch bereit und nicht abgeschlossen, kommt er ans Ende der Warteschlange; abgeschlossene Jobs scheiden aus, blockierte warten außerhalb der Bereitschaftswarteschlange. Ein kürzeres Quantum verbessert die Reaktionsfähigkeit, erhöht aber den Umschaltaufwand; RR minimiert im Allgemeinen nicht die durchschnittliche Durchlaufzeit.

Für die Reihenfolge der Ankünfte ist eine ausdrückliche Regel nötig: Neue Jobs werden hinten an die Warteschlange angefügt, Gleichstände deterministisch aufgelöst. Eine Ankunft während eines Quantums unterbricht dieses nicht von selbst. Für Ereignisse an Quantum-Grenzen muss festgelegt werden, ob neue Jobs oder das erneute Einreihen des aktuellen Jobs zuerst verarbeitet werden. Hier treffen alle Jobs zum Zeitpunkt 0 in der Reihenfolge P1, P2, P3 ein; das zyklische Durchlaufen des Arrays reicht nur für diese Vereinfachung.

Die Durchlaufzeit ist completion - arrival. Die Wartezeit umfasst die gesamte Zeit in der Bereitschaftswarteschlange, nicht nur die Verzögerung vor dem ersten Lauf. Im angenommenen Modell ohne I/O und Zusatzaufwand entspricht sie turnaround - burst. Das Beispiel verwendet quantum = 2 und CPU-Bedarf 5, 3, 1; die Abschlusszeiten sind entsprechend 9, 8, 5.

Dies ist eine deterministische Simulation eines einzelnen Prozessors in abstrakten Zeiteinheiten, keine Konfiguration eines Betriebssystem-Planers und kein Nachweis des Verhaltens von C-Threads. Versionsumfang: C23; repository compiler flag, production runtime not attested. Eine Ausführung in einer Produktionsumgebung ist nicht bestätigt.

Beispiele

#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;
}

Ergebnis

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

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen