प्रक्रिया, प्रक्रिया का बर्स्ट समय और एक क्वांटम सीमा दी गई है; कार्य प्रीमेप्टिव शॉर्टेस्ट जॉब फर्स्ट शेड्यूलिंग विधि का उपयोग करके प्रतीक्षा समय, टर्नअराउंड समय और उनके संबंधित औसत समय को खोजना और प्रिंट करना है।
शॉर्टेस्ट जॉब फर्स्ट शेड्यूलिंग क्या है?
शॉर्टेस्ट जॉब फर्स्ट शेड्यूलिंग वह जॉब या प्रोसेस शेड्यूलिंग एल्गोरिदम है जो नॉन-प्रीमेप्टिव शेड्यूलिंग अनुशासन का पालन करता है। इसमें, शेड्यूलर वेटिंग कतार से उस प्रक्रिया का चयन करता है जिसका पूरा होने का समय सबसे कम होता है और उस जॉब या प्रोसेस को CPU आवंटित करता है। शॉर्टेस्ट जॉब फर्स्ट FIFO एल्गोरिदम से अधिक वांछनीय है क्योंकि SJF अधिक इष्टतम है क्योंकि यह औसत प्रतीक्षा समय को कम करता है जिससे थ्रूपुट बढ़ता है।
SJF एल्गोरिदम प्रीमेप्टिव के साथ-साथ नॉन-प्रीमेप्टिव भी हो सकता है। प्रीमेप्टिव शेड्यूलिंग को शॉर्टेस्ट-रिमेनिंग-टाइम-फर्स्ट शेड्यूलिंग के रूप में भी जाना जाता है। प्रीमेप्टिव दृष्टिकोण में, नई प्रक्रिया तब उत्पन्न होती है जब पहले से कोई प्रक्रिया निष्पादित हो रही होती है। यदि नई आने वाली प्रक्रिया का बर्स्ट समय निष्पादित प्रक्रिया के बर्स्ट समय से कम है तो शेड्यूलर कम बर्स्ट समय वाली प्रक्रिया के निष्पादन को प्रीमेप्ट करेगा।
टर्नअराउंड समय, प्रतीक्षा समय और पूर्णता समय क्या है?
- पूर्णता समय वह समय है जो प्रक्रिया को अपना निष्पादन पूरा करने के लिए आवश्यक होता है
टर्नअराउंड समय एक प्रक्रिया के सबमिशन और उसके पूरा होने के बीच का समय अंतराल है।
टर्नअराउंड समय = एक प्रक्रिया का पूरा होना - एक प्रक्रिया का सबमिशन
प्रतीक्षा समय टर्नअराउंड समय और बर्स्ट समय का अंतर है
प्रतीक्षा समय = टर्नअराउंड समय - बर्स्ट समय
उदाहरण
हमें प्रक्रियाओं P1, P2, P3, P4 और P5 दिए गए हैं जिनके संबंधित बर्स्ट समय नीचे दिए गए हैं
| प्रक्रिया | बर्स्ट समय | आगमन समय |
|---|---|---|
| P1 | 4 | 0 |
| P2 | 2 | 1 |
| P3 | 8 | 2 |
| P4 | 1 | 3 |
| P5 | 9 | 4 |
चूंकि P1 का आगमन समय 0 है इसलिए यह निष्पादित होने वाली पहली प्रक्रिया होगी जब तक कि दूसरी प्रक्रिया नहीं आ जाती। जब 1 पर प्रक्रिया P2 आती है और P2 का बर्स्ट समय P1 के बर्स्ट समय से कम होता है इसलिए शेड्यूलर CPU को प्रक्रिया P2 के साथ भेजेगा और इसी तरह।
औसत प्रतीक्षा समय गैंट चार्ट के आधार पर गणना की जाती है। P1 को (0+4)4 के लिए इंतजार करना पड़ता है, P2 को 1 के लिए, P3 को 7 के लिए, P4 को 3 के लिए और P5 को 15 के लिए। तो, उनका औसत प्रतीक्षा समय होगा −
एल्गोरिदम
शुरुआत चरण 1-> एक स्ट्रक्चर Process घोषित करें pid, bt, art घोषित करें चरण 2-> फ़ंक्शन findTurnAroundTime(Process proc[], int n, int wt[], int tat[]) में लूप i = 0 से i < n और i++ तक tat[i] = proc[i].bt + wt[i] सेट करें चरण 3-> फ़ंक्शन 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 को 1 से बढ़ाएं जारी रखें rt[shortest] के मान को 1 से घटाएं minm = rt[shortest] सेट करें यदि minm == 0 तो, minm = INT_MAX सेट करें यदि rt[shortest] == 0 तो, complete को 1 से बढ़ाएं check = false सेट करें finish_time = t + 1 सेट करें wt[shortest] = finish_time - proc[shortest].bt -proc[shortest].art सेट करें यदि wt[shortest] < 0 wt[shortest] = 0 सेट करें t को 1 से बढ़ाएं चरण 4-> फ़ंक्शन 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 चरण 5-> फ़ंक्शन 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; // प्रोसेस ID 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 << "प्रक्रियाएं " << " बर्स्ट समय " << " प्रतीक्षा समय " << " टर्नअराउंड समय\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 << "\nऔसत प्रतीक्षा समय = " << (float)total_wt / (float)n; cout << "\nऔसत टर्नअराउंड समय = " << (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; }आउटपुट
