โปรแกรม C สำหรับ Round Robin Scheduling (การจัดตารางเวลาแบบรอบรอบ)

กำหนด n กระบวนการ พร้อม burst time และ time quantum หา average waiting time และ average turnaround time

Round Robin Scheduling คืออะไร?

CPU scheduling algorithm สำหรับ time-sharing systems คล้าย FCFS แต่มี quantum time หน่วยเวลาเล็ก (Time Quantum/Slice) 10-100 ms CPU จัดการ ready queue แบบ circular queue จัดสรร CPU ให้กระบวนการตาม time slice แบบ preemptive ข้อเสีย: overhead ของ context switching

สิ่งที่ต้องคำนวณ:

• Completion Time - เวลาที่กระบวนการเสร็จสิ้น
• Turnaround Time - ช่วงเวลาระหว่างส่งกระบวนการจนเสร็จ = Completion - Submission
• Waiting Time - Turnaround Time - Burst Time

ตัวอย่าง

3 กระบวนการ P1, P2, P3 burst time: 24, 3, 3 time quantum = 4 ms

P1 ใช้ 4 ms แล้วถูก preempt P2 ใช้ 3 ms (น้อยกว่า quantum) เสร็จ P3 ใช้ 3 ms เสร็จ ...

Average waiting time = 17/3 = 5.66 ms

อัลกอริทึม

waitingtime(processes, n, bt, wt, quantum):
    rem_bt = copy of bt
    t = 0
    while true:
        done = true
        for each process i:
            if rem_bt[i] > 0:
                done = false
                if rem_bt[i] > quantum:
                    t += quantum
                    rem_bt[i] -= quantum
                else:
                    t += rem_bt[i]
                    wt[i] = t - bt[i]
                    rem_bt[i] = 0
        if done: break

turnarroundtime(processes, n, bt, wt, tat):
    tat[i] = bt[i] + wt[i]

findavgTime(processes, n, bt, quantum):
    เรียก waitingtime, turnarroundtime
    แสดงผล และคำนวณ average

ตัวอย่างโค้ด

#include <stdio.h>
#include <stdbool.h>

int turnarroundtime(int processes[], int n, int bt[], int wt[], int tat[]) {
    for (int i = 0; i < n; i++) tat[i] = bt[i] + wt[i];
    return 1;
}

int waitingtime(int processes[], int n, int bt[], int wt[], int quantum) {
    int rem_bt[n];
    for (int i = 0; i < n; i++) rem_bt[i] = bt[i];
    int t = 0;
    while (1) {
        bool done = true;
        for (int i = 0; i < n; i++) {
            if (rem_bt[i] > 0) {
                done = false;
                if (rem_bt[i] > quantum) {
                    t += quantum;
                    rem_bt[i] -= quantum;
                } else {
                    t += rem_bt[i];
                    wt[i] = t - bt[i];
                    rem_bt[i] = 0;
                }
            }
        }
        if (done) break;
    }
    return 1;
}

int findavgTime(int processes[], int n, int bt[], int quantum) {
    int wt[n], tat[n], total_wt = 0, total_tat = 0;
    waitingtime(processes, n, bt, wt, quantum);
    turnarroundtime(processes, n, bt, wt, tat);
    printf("Processes  Burst Time  Waiting Time  Turnaround Time\n");
    for (int i = 0; i < n; i++) {
        total_wt += wt[i];
        total_tat += tat[i];
        printf("%d\t\t%d\t\t%d\t\t%d\n", i+1, bt[i], wt[i], tat[i]);
    }
    printf("Average waiting time = %f\n", (float)total_wt / n);
    printf("Average turnaround time = %f\n", (float)total_tat / n);
    return 1;
}

int main() {
    int processes[] = {1, 2, 3};
    int n = sizeof(processes) / sizeof(processes[0]);
    int burst_time[] = {8, 6, 12};
    int quantum = 2;
    findavgTime(processes, n, burst_time, quantum);
    return 0;
}

เอาต์พุต

ตารางแสดง Process, Burst Time, Waiting Time, Turnaround Time พร้อมค่าเฉลี่ย