Round robin – Operating Systems Exercise with Solution

The processes run by round robin with time quantum q. The process at the front of the ready queue runs for q units, or less if it finishes sooner. If it is not finished, it goes to the back of the queue. Processes that arrive while it runs, or at the very moment it stops, join the queue before it. If the queue is empty, the CPU idles until the next process arrives.

Input

The first line has n and q (1 ≤ n ≤ 20, 1 ≤ q ≤ 10). Each of the next n lines has the arrival time and burst time of P1, P2, ... (0 ≤ arrival ≤ 100, 1 ≤ burst ≤ 50). They are listed in order of arrival; processes that arrive together join the queue in that order.

Output

For each process, in order P1, P2, ...: Pi CT WT (completion time and waiting time). Then average waiting W with 2 decimal places.

Examples

Example 1 · Input

Expected output

P1 11 6
P2 10 6
P3 5 2
P4 9 4
average waiting 4.50

Example 2 · Input

Expected output

P1 30 6
P2 7 4
P3 10 7
average waiting 5.67

Hints

Hint 1

Keep the ready queue in an array used as a circular queue.

Hint 2

After a process runs for min(quantum, time left), first add every process that has arrived by now, then put the stopped process at the back.

Hint 3

When the queue is empty, move the clock to the next arrival.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>

#define CAP 32

int queue[CAP], head = 0, size = 0;

void push(int p) { queue[(head + size) % CAP] = p; size++; }
int pop(void) { int p = queue[head]; head = (head + 1) % CAP; size--; return p; }

int main(void) {
    int n, q, arrival[20], burst[20], left[20], finish[20];
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &arrival[i], &burst[i]);
        left[i] = burst[i];
    }
    int time = 0, next = 0, done = 0;
    while (done < n) {
        if (size == 0) {
            if (time < arrival[next]) time = arrival[next];
            while (next < n && arrival[next] <= time) push(next++);
        }
        int p = pop();
        int run = left[p] < q ? left[p] : q;
        time += run;
        left[p] -= run;
        while (next < n && arrival[next] <= time) push(next++);
        if (left[p] > 0) {
            push(p);
        } else {
            finish[p] = time;
            done++;
        }
    }
    int total_wait = 0;
    for (int i = 0; i < n; i++) {
        int wait = finish[i] - arrival[i] - burst[i];
        total_wait += wait;
        printf("P%d %d %d\n", i + 1, finish[i], wait);
    }
    printf("average waiting %.2f\n", (double)total_wait / n);
    return 0;
}

Lesson: Round robin, SRTF and priority →