C প্রোগ্রামিং-এ রাউন্ড রবিন শিডিউলিং (Round Robin Scheduling)

আমাদের nটি প্রসেস দেওয়া আছে তাদের বার্স্ট টাইম (burst time) এবং টাইম কোয়ান্টাম (time quantum) সহ এবং টাস্ক হলো অয়েরেজ ওয়েটিং টাইম (average waiting time) এবং অয়েরেজ টার্নআরাউন্ড টাইম (average turnaround time) বের করে ডিসপ্লে করা।

রাউন্ড রবিন শিডিউলিং (Round Robin Scheduling) কী?

রাউন্ড রবিন একটি CPU শিডিউলিং অ্যালগরিদম যা খাসভাবে টাইম শেয়ারিং সিস্টেম (time sharing systems) এর জন্য ডিজাইন করা। এটি FCFS শিডিউলিং অ্যালগরিদমের মতো কিন্তু একটি পরিবর্তন আছে: রাউন্ড রবিনে প্রসেসগুলো একটি কোয়ান্টাম টাইম সাইজ (quantum time size) দিয়ে বাউন্ডেড (bounded) থাকে। একটি ছোট টাইম ইউনিট কে টাইম কোয়ান্টাম (Time Quantum) বা টাইম স্লাইস (Time Slice) বলা হয়। টাইম কোয়ান্টাম ১০ থেকে ১০০ মিলিসেকেন্ড পর্যন্ত হতে পারে। CPU রেডি কিউ (ready queue)-কে একটি সার্কুলার কিউ (circular queue) হিসেবে বিবেচনা করে দেয়া টাইম স্লাইস অনুযায়ী প্রসেসগুলো এক্সিকিউট করে। এটি প্রিপ্টিভ (preemptive) অ্যাপ্রোচ ফলো করে কারণ ফিক্সড টাইম প্রসেসগুলোকে অ্যালোকেট করা হয়। এর একমাত্র ডিসঅ্যাডভান্টেজ হলো কনটেক্সট সুইচিং (context switching)-এর ওভারহেড (overhead)।

আমাদের কী ক্যালকুলেট করতে হবে?

• কমপ্লিশন টাইম (Completion Time) হল প্রসেসটি এক্সিকিউশন কমপ্লিট করতে যে টাইম লাগে।
• টার্নআরাউন্ড টাইম (Turnaround Time) হল একটি প্রসেস সাবমিশন (submission) এবং এর কমপ্লিশন (completion) এর মাঝপথের টাইম ইন্টারভাল।
  Turnaround Time = completion of a process − submission of a process
• ওয়েটিং টাইম (Waiting Time) হল টার্নআরাউন্ড টাইম এবং বার্স্ট টাইম (burst time)-এর পার্থক্য।
  Waiting Time = turnaround time − burst time

উদাহরণ (Example)

আমাদের ৩টি প্রসেস দেওয়া আছে P1, P2 এবং P3 তাদের বার্স্ট টাইম যথাক্রমে ২৪, ৩ এবং ৩।

যেহেতু টাইম কোয়ান্টাম ৪ মিলিসেকেন্ড, প্রসেস P1 প্রথম ৪ মিলিসেকেন্ড পায় কিন্তু এটিকে আরও ২০ মিলিসেকেন্ড লাগবে এক্সিকিউশন কমপ্লিট করতে কিন্তু CPU এটিকে প্রথম টাইম কোয়ান্টামের পর প্রিপ্ট (preempt) করবে এবং CPU পরবর্তী প্রসেস P2-কে অ্যালোকেট করবে। টেবিলে দেখানো হয়েছে, প্রসেস P2 শুধু ৩ মিলিসেকেন্ডে কমপ্লিট হয় তাই CPU ৪ মিলিসেকেন্ডের বদলে ৩ মিলিসেকেন্ডের জন্য অ্যালোকেট করবে।

গ্যান্ট চার্ট (Gantt chart) ব্যবহার করে অয়েরেজ ওয়েটিং টাইম নিচের মতো ক্যালকুলেট করা হয় −

অয়েরেজ ওয়েটিং টাইম = 17/3 = 5.66 মিলিসেকেন্ড

আলগরিদম (Algorithm)

Start
Step 1 → In function int turnarroundtime(int processes[], int n, int bt[], int wt[], int tat[])
    Loop For i = 0 and i < n and i++
        Set tat[i] = bt[i] + wt[i]
    return 1

Step 2 → In function int waitingtime(int processes[], int n, int bt[], int wt[], int quantum)
    Declare rem_bt[n]
    Loop For i = 0 and i < n and i++
        Set rem_bt[i] = bt[i]
        Set t = 0
    Loop While (1)
        Set done = true
        Loop For i = 0 and i < n and i++
            If rem_bt[i] > 0 then,
                Set done = false
                If rem_bt[i] > quantum then,
                    Set t = t + quantum
                    Set rem_bt[i] = rem_bt[i] - quantum
                Else
                    Set t = t + rem_bt[i]
                    Set wt[i] = t - bt[i]
                    Set rem_bt[i] = 0
            If done == true then,
                Break

Step 3 → In function int findavgTime(int processes[], int n, int bt[], int quantum)
    Declare and initialize wt[n], tat[n], total_wt = 0, total_tat = 0
    Call function waitingtime(processes, n, bt, wt, quantum)
    Call function turnarroundtime(processes, n, bt, wt, tat)
    Print "Processes Burst Time Waiting Time turnaround time"
    Loop For i=0 and i

উদাহরণ (C প্রোগ্রাম)
#include <stdio.h>
#include <stdbool.h>

// Function to calculate turn around time
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;
}

// Function to find the waiting time for all processes
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; // Current time

    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 = t + rem_bt[i];
                    wt[i] = t - bt[i];
                    rem_bt[i] = 0;
                }
            }
        }
        if (done == true)
            break;
    }
    return 1;
}

// Function to calculate average time
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\tBurst Time\tWaiting Time\tTurnaround Time\n");
    for (int i = 0; i < n; i++) {
        total_wt = total_wt + wt[i];
        total_tat = 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 / (float)n);
    printf("Average turnaround time = %f\n", (float)total_tat / (float)n);
    return 1;
}

// main function
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;
}


আউটপুট


ব্যাখ্যা: রাউন্ড রবিন একটি ফেয়ার (fair) শিডিউলিং অ্যালগরিদম। প্রতিটি প্রসেসকে সমান টাইম স্লাইস (quantum) দেওয়া হয়। ছোট প্রসেসগুলো দ্রুত কমপ্লিট হয়, বড় প্রসেসগুলো মাল্টিপল কোয়ান্টাম নেয়। কনটেক্সট সুইচিং ওভারহেড এর কারণ বড় কোয়ান্টাম দিলে FCFS-এর মতো হয়, ছোট দিলে ওভারহেড বাড়ে।