C प्रोग्राम फॉर राउंड रॉबिन शेड्यूलिंग (Round Robin Scheduling)

हमें n प्रक्रियाएं उनके संबंधित बर्स्ट टाइम और टाइम क्वांटम के साथ दी गई हैं और कार्य औसत प्रतीक्षा समय और औसत टर्नअराउंड समय ढूंढना और परिणाम प्रदर्शित करना है।

राउंड रॉबिन शेड्यूलिंग क्या है?

राउंड रॉबिन एक CPU शेड्यूलिंग एल्गोरिदम है जिसे विशेष रूप से टाइम-शेयरिंग सिस्टम के लिए डिज़ाइन किया गया है। यह FCFS शेड्यूलिंग एल्गोरिदम की तरह है एक परिवर्तन के साथ कि राउंड रॉबिन में प्रक्रियाएं एक क्वांटम टाइम साइज से बंधी होती हैं। समय की एक छोटी इकाई को टाइम क्वांटम या टाइम स्लाइस के रूप में जाना जाता है। टाइम क्वांटम 10 से 100 मिलीसेकंड तक हो सकता है। CPU दिए गए टाइम स्लाइस के साथ प्रक्रियाओं को निष्पादित करने के लिए रेडी क्यू को एक सर्कुलर क्यू के रूप में मानता है। यह प्रीमेप्टिव दृष्टिकोण का पालन करता है क्योंकि प्रक्रियाओं को निश्चित समय आवंटित किया जाता है। इसका एकमात्र नुकसान कॉन्टेक्स्ट स्विचिंग का ओवरहेड है।

हमें क्या गणना करने की आवश्यकता है?

कंप्लीशन टाइम प्रक्रिया द्वारा अपना निष्पादन पूरा करने के लिए आवश्यक समय है।

टर्नअराउंड टाइम एक प्रक्रिया के सबमिशन और उसके पूरा होने के बीच का समय अंतराल है।

टर्नअराउंड टाइम = प्रक्रिया का पूरा होना - प्रक्रिया का सबमिशन

वेटिंग टाइम टर्नअराउंड टाइम और बर्स्ट टाइम के बीच का अंतर है।

वेटिंग टाइम = टर्नअराउंड टाइम - बर्स्ट टाइम

उदाहरण

हमें 3 प्रक्रियाएं P1, P2 और P3 दी गई हैं जिनके संबंधित बर्स्ट टाइम 24, 3 और 3 हैं।

चूंकि टाइम क्वांटम 4 मिलीसेकंड का है, प्रक्रिया P1 को पहले 4 मिलीसेकंड मिलते हैं लेकिन इसे अपना निष्पादन पूरा करने के लिए और 20 मिलीसेकंड की आवश्यकता होती है लेकिन CPU पहले टाइम क्वांटम के बाद इसे प्रीमेप्ट कर देगा और CPU को अगली प्रक्रिया P2 को आवंटित किया जाएगा। जैसा कि तालिका में दिखाया गया है, प्रक्रिया P2 को अपना निष्पादन पूरा करने के लिए केवल 3 मिलीसेकंड की आवश्यकता होती है इसलिए CPU को 4 मिलीसेकंड के बजाय केवल 3 मिलीसेकंड के टाइम क्वांटम के लिए आवंटित किया जाएगा।

गैंट चार्ट का उपयोग करके, औसत प्रतीक्षा समय की गणना नीचे दी गई है -

औसत प्रतीक्षा समय = 17/3 = 5.66 मिलीसेकंड

एल्गोरिदम

Start
Step 1 -> 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 -> 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 -> 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 int main()
    Declare and initialize processes[] = {1, 2, 3}
    Declare and initialize n = sizeof processes / sizeof processes[0]
    Declare and initialize burst_time[] = {8, 6, 12}
    Set quantum = 2
    Call function findavgTime(processes, n, burst_time, quantum)

उदाहरण

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

// टर्नअराउंड टाइम गणना करने का फंक्शन
int turnarroundtime(int processes[], int n, int bt[], int wt[], int tat[]) {
    // bt[i] + wt[i] जोड़कर टर्नअराउंड टाइम की गणना
    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) {
    // शेष बर्स्ट टाइम स्टोर करने के लिए bt[] की कॉपी बनाएं
    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++) {
            // यदि प्रक्रिया का बर्स्ट टाइम 0 से अधिक है तो केवल आगे प्रोसेस करने की आवश्यकता है
            if (rem_bt[i] > 0) {
                done = false; // एक लंबित प्रक्रिया है
                if (rem_bt[i] > quantum) {
                    // t के मान को बढ़ाएं यानी दिखाता है कि एक प्रक्रिया कितने समय तक प्रोसेस हुई
                    t += quantum;
                    // वर्तमान प्रक्रिया के बर्स्ट_टाइम को क्वांटम से घटाएं
                    rem_bt[i] -= quantum;
                } else {
                    // यदि बर्स्ट टाइम क्वांटम से छोटा या बराबर है। इस प्रक्रिया के लिए अंतिम चक्र
                    t = t + rem_bt[i];
                    // प्रतीक्षा समय वर्तमान समय घटा इस प्रक्रिया द्वारा उपयोग किया गया समय
                    wt[i] = t - bt[i];
                    // चूंकि प्रक्रिया पूरी तरह से निष्पादित हो जाती है
                    // इसका शेष बर्स्ट टाइम = 0 बनाएं
                    rem_bt[i] = 0;
                }
            }
        }
        // यदि सभी प्रक्रियाएं पूर्ण हो गईं
        if (done == true)
            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 = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        printf("\t%d\t\t\t%d\t\t\t%d\t\t\t%d\n", i+1, bt[i], wt[i], tat[i]);
    }
    printf("Average waiting time = %f", (float)total_wt / (float)n);
    printf("\nAverage turnaround time = %f\n", (float)total_tat / (float)n);
    return 1;
}

// मुख्य फंक्शन
int main() {
    // प्रोसेस IDs
    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;
}

आउटपुट