শর্টেস্ট জব ফার্স্ট (SJF) শিডিউলিং (প্রি-এম্পটিভ) C++ প্রোগ্রাম

প্রসেস, তাদের 버স্ট টাইম এবং কোয়ান্টাম লিমিট দেওয়া আছে; কাজ হলো শর্টেস্ট জব ফার্স্ট শিডিউলিং প্রি-এম্পটিভ পদ্ধতিতে ওয়েটিং টাইম, টার্নআরাউন্ড টাইম এবং তাদের গড় মান বের করে প্রিন্ট করা।

শর্টেস্ট জব ফার্স্ট শিডিউলিং কী?

শর্টেস্ট জব ফার্স্ট শিডিউলিং হলো একটি প্রসেস শিডিউলিং অ্যালগরিদম যা নন-প্রি-এম্পটিভ শিডিউলিং ডিসিপ্লিন মেনে চলে। এতে শিডিউলার ওয়েটিং কিউ থেকে সবচেয়ে কম কমপ্লিশন টাইম বালা প্রসেস সিলেক্ট করে সেটি সিপিইউ alok করে। SJF FIFO অ্যালগরিদমের চেয়ে বেশি উপযোগী কারণ এটি গড় ওয়েটিং টাইম কমায় এবং থ্রুপুট বাড়ায়।

SJF অ্যালগরিদম প্রি-এম্পটিভ এবং নন-প্রি-এম্পটিভ উভয় হতে পারে। প্রি-এম্পটিভ শিডিউলিংকে শর্টেস্ট-রিমেইনিং-টাইম-ফার্স্ট শিডিউলিং ও বলা হয়। প্রি-এম্পটিভ পদ্ধতিতে, নতুন প্রসেস তখন আসে যখন ইতিমধ্যে একটি প্রসেস এক্সিকিউট হচ্ছে। যদি নতুন প্রসেসের burst time এক্সিকিউট হচ্ছে প্রসেসের চেয়ে কম হয়, তবে শিডিউলার কম burst time বালা প্রসেস এক্সিকিউট করতে সিপিইউকে প্রি-এম্পট করে।

টার্নআরাউন্ড টাইম, ওয়েটিং টাইম এবং কমপ্লিশন টাইম কী?

• কমপ্লিশন টাইম হলো প্রসেস তার এক্সিকিউশন কমপ্লিট করতে যায় সময়।

• টার্নআরাউন্ড টাইম হলো প্রসেস সাবমিশন থেকে কমপ্লিশন পর্যন্ত সময় अन्तর।

  টার্নআরাউন্ড টাইম = প্রসেসের কমপ্লিশন - প্রসেসের সাবমিশন

• ওয়েটিং টাইম হলো টার্নআরাউন্ড টাইম এবং burst time-এর পার্থক্য।

  ওয়েটিং টাইম = টার্নআরাউন্ড টাইম - burst time

উদাহরণ

প্রসেস P1, P2, P3, P4, P5 এবং তাদের burst time ও arrival time নিচে দেওয়া হলো:

P1-এর arrival time ০, তাই এটি প্রথমে এক্সিকিউট হবে অন্য প্রসেস আসা পর্যন্ত। সময় ১-এ P2 আসে এবং এর burst time P1-এর চেয়ে কম, তাই শিডিউলার সিপিইউকে P2-র সাথে ডিসপ্যাচ করবে এবং এভাবে চলবে।

গ্যান্ট চার্টের ভিত্তিতে গড় ওয়েটিং টাইম বের করা হয়। P1 অপেক্ষা করল (0+4)=৪, P2 অপেক্ষা করল ১, P3 অপেক্ষা করল ৭, P4 অপেক্ষা করল ৩ এবং P5 অপেক্ষা করল ১৫। তাই গড় ওয়েটিং টাইম:

অ্যালগরিদম

শুরু
ধাপ ১ -> struct Process ঘোষণা
    pid, bt, art ঘোষণা
ধাপ ২ -> findTurnAroundTime(Process proc[], int n, int wt[], int tat[]) ফাংশনে
    লুপ i = 0 থেকে i < n এবং i++
        tat[i] = proc[i].bt + wt[i] সেট
ধাপ ৩ -> findWaitingTime(Process proc[], int n, int wt[]) ফাংশনে
    rt[n] ঘোষণা
    লুপ i = 0 থেকে i < n এবং i++
        rt[i] = proc[i].bt সেট
        complete = 0, t = 0, minm = INT_MAX সেট
        shortest = 0, finish_time সেট
        bool check = false সেট
        লুপ যতক্ষণ (complete != n)
            লুপ j = 0 থেকে j < n এবং j++
                যদি (proc[j].art <= t) && (rt[j] < minm) && rt[j] > 0 হয়, তবে
                    minm = rt[j] সেট
                    shortest = j সেট
                    check = true সেট
                শেষ
            যদি check == false হয়, তবে
                t ১ বাড়াও
                কন্টিনিউ
            শেষ
            rt[shortest] ১ কমাও
            minm = rt[shortest] সেট
            যদি minm == 0 হয়, তবে
                minm = INT_MAX সেট
            যদি rt[shortest] == 0 হয়, তবে
                complete ১ বাড়াও
                check = false সেট
                finish_time = t + 1 সেট
                wt[shortest] = finish_time - proc[shortest].bt - proc[shortest].art সেট
                যদি wt[shortest] < 0 হয়, তবে
                    wt[shortest] = 0 সেট
                শেষ
            t ১ বাড়াও
ধাপ ৪ -> findavgTime(Process proc[], int n) ফাংশনে
    wt[n], tat[n], total_wt = 0, total_tat = 0 ঘোষণা এবং সেট
    findWaitingTime(proc, n, wt) কল
    findTurnAroundTime(proc, n, wt, tat) কল
    লুপ i = 0 থেকে i < n এবং i++
        total_wt = total_wt + wt[i] সেট
        total_tat = total_tat + tat[i] সেট
        proc[i].pid, proc[i].bt, wt[i], tat[i] প্রিন্ট
        গড় ওয়েটিং টাইম: total_wt / n প্রিন্ট
        গড় টার্ন আরাউন্ড টাইম: total_tat / n প্রিন্ট
    শেষ
ধাপ ৫ -> int main() ফাংশনে
    Process proc[] = { { 1, 5, 1 }, { 2, 3, 1 }, { 3, 6, 2 }, { 4, 5, 3 } } ঘোষণা এবং সেট
    n = sizeof(proc) / sizeof(proc[0]) সেট
    findavgTime(proc, n) কল
শেষ

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
// প্রতিটি প্রসেসের জন্য স্ট্রাকচার
struct Process {
    int pid; // প্রসেস আইডি
    int bt;  // বার্স্ট টাইম
    int art; // আরাইভাল টাইম
};
void findTurnAroundTime(Process proc[], int n, int wt[], int tat[]) {
    for (int i = 0; i < n; i++)
        tat[i] = proc[i].bt + wt[i];
}
// সব প্রসেসের ওয়েটিং টাইম
void findWaitingTime(Process proc[], int n, int wt[]) {
    int rt[n];
    for (int i = 0; i < n; i++)
        rt[i] = proc[i].bt;
    int complete = 0, t = 0, minm = INT_MAX;
    int shortest = 0, finish_time;
    bool check = false;
    while (complete != n) {
        for (int j = 0; j < n; j++) {
            if ((proc[j].art <= t) && (rt[j] < minm) && rt[j] > 0) {
                minm = rt[j];
                shortest = j;
                check = true;
            }
        }
        if (check == false) {
            t++;
            continue;
        }
        // রিমেইনিং টাইম ডিক্রিমেন্ট
        rt[shortest]--;
        minm = rt[shortest];
        if (minm == 0)
            minm = INT_MAX;
        // যদি প্রসেস সম্পূর্ণ এক্সিকিউট হয়
        if (rt[shortest] == 0) {
            complete++;
            check = false;
            finish_time = t + 1;
            // ওয়েটিং টাইম ক্যালকুলেট
            wt[shortest] = finish_time -
                proc[shortest].bt -
                proc[shortest].art;
            if (wt[shortest] < 0)
                wt[shortest] = 0;
        }
        // টাইম ইনক্রিমেন্ট
        t++;
    }
}
// গড় টাইম ক্যালকুলেট করার ফাংশন
void findavgTime(Process proc[], int n) {
    int wt[n], tat[n], total_wt = 0,
    total_tat = 0;
    // সব প্রসেসের ওয়েটিং টাইম বের করা
    findWaitingTime(proc, n, wt);
    // সব প্রসেসের টার্ন আরাউন্ড টাইম বের করা
    findTurnAroundTime(proc, n, wt, tat);
    cout << "Processes " << " Burst time " << " Waiting time " << " Turn around time\n";
    for (int i = 0; i < n; i++) {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        cout << " " << proc[i].pid << "\t\t" << proc[i].bt << "\t\t " << wt[i] << "\t\t " << tat[i] << endl;
    }
    cout << "\nAverage waiting time = " << (float)total_wt / (float)n;
    cout << "\nAverage turn around time = " << (float)total_tat / (float)n;
}
// মেইন ফাংশন
int main() {
    Process proc[] = { { 1, 5, 1 }, { 2, 3, 1 }, { 3, 6, 2 }, { 4, 5, 3 } };
    int n = sizeof(proc) / sizeof(proc[0]);
    findavgTime(proc, n);
    return 0;
}

আউটপুট