Chương trình C cho thuật toán lập lịch Round Robin

Cho n tiến trình với burst time và time quantum. Tìm average waiting time và average turnaround time.

Round Robin Scheduling là gì?

Thuật toán lập lịch CPU dành cho hệ thống chia sẻ thời gian (time-sharing). Giống FCFS nhưng mỗi tiến trình bị giới hạn bởi Time Quantum (Time Slice) - đơn vị thời gian nhỏ (10-100ms). CPU xem hàng đợi sẵn sàng (ready queue) như hàng đợi vòng (circular queue). Theo cách preemptive (chiếm quyền) vì cấp thời gian cố định. Nhược điểm: chi phí context switching.

Cần tính gì?

• Completion Time: thời gian tiến trình hoàn thành.
• Turnaround Time: khoảng thời gian từ nộp tiến trình đến hoàn thành. = Completion - Submission.
• Waiting Time: Turnaround Time - Burst Time.

Ví dụ

3 tiến trình P1, P2, P3 với burst time: 24, 3, 3. Time quantum = 4ms.

P1 chạy 4ms đầu, còn 20ms nhưng bị preempt. P2 chỉ cần 3ms → chạy 3ms. P3 tương tự.

Average waiting time = 17/3 = 5.66 ms

Thuật toán

turnarroundtime(processes, n, bt, wt, tat):
  for i = 0 đến n-1: tat[i] = bt[i] + wt[i]

waitingtime(processes, n, bt, wt, quantum):
  rem_bt[i] = bt[i] (copy burst time)
  t = 0
  while true:
    done = true
    for i = 0 đến n-1:
      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

findavgTime(processes, n, bt, quantum):
  wt[n], tat[n], total_wt = 0, total_tat = 0
  waitingtime(...)
  turnarroundtime(...)
  In bảng: Process, Burst, Waiting, Turnaround
  Tính total_wt, total_tat
  In Average waiting time = total_wt / n
  In Average turnaround time = total_tat / n

Ví dụ mã nguồn

#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 = %.2f\n", (float)total_wt / n);
    printf("Average turnaround time = %.2f\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;
}

Kết quả đầu ra