सबसे छोटा काम पहले (एसजेएफ): पूर्वनिर्णय, गैर-पूर्वनिर्णय उदाहरण

⚡ स्मार्ट सारांश

शॉर्टेस्ट जॉब फर्स्ट (एसजेएफ) एक सीपीयू शेड्यूलिंग एल्गोरिदम है जो सबसे कम निष्पादन समय वाली प्रक्रिया को अगले चरण में चलाने के लिए चुनता है। यह प्रीएम्प्टिव या नॉन-प्रीएम्प्टिव हो सकता है और प्रक्रियाओं के लिए औसत प्रतीक्षा समय को काफी कम कर देता है।

️ परिभाषा: सबसे कम समय में समाप्त होने वाली प्रक्रिया को अगली बार निष्पादित करने के लिए चुना जाता है।
🔀 दो प्रकार: एसजेएफ गैर-पूर्वव्यापी या पूर्वव्यापी (सबसे कम शेष समय पहले) हो सकता है।
📉 मुख्य लाभ: यह प्रक्रियाओं के एक दिए गए समूह के लिए सबसे कम औसत प्रतीक्षा समय प्रदान करता है।
🏭 सबसे अच्छा उपयोग: यह उन बैच सिस्टमों के लिए आदर्श है जहां जॉब रन टाइम पहले से ज्ञात होते हैं।
❓ मुख्य सीमा: विस्फोट का समय पहले से पता होना चाहिए, जिसकी भविष्यवाणी करना मुश्किल है।
⚠️ जोखिम: यदि छोटे-छोटे काम लगातार आते रहें तो लंबी प्रक्रियाएं ठप हो सकती हैं।

विस्तार में पढ़ें

सबसे छोटी नौकरी पहले शेड्यूलिंग क्या है?

सबसे छोटा काम पहले (एसजेएफ) एक एल्गोरिथ्म है जिसमें सबसे कम निष्पादन समय वाली प्रक्रिया को अगले निष्पादन के लिए चुना जाता है। यह शेड्यूलिंग विधि प्रीमेप्टिव या नॉन-प्रीमेप्टिव हो सकती है। यह निष्पादन की प्रतीक्षा कर रही अन्य प्रक्रियाओं के लिए औसत प्रतीक्षा समय को काफी कम कर देता है। SJF का पूरा नाम शॉर्टेस्ट जॉब फर्स्ट है।

एसजेएफ पद्धतियां मूलतः दो प्रकार की होती हैं:

गैर-निवारक एसजेएफ
पूर्वनिवारक एसजेएफ

एसजेएफ शेड्यूलिंग की विशेषताएं

यह प्रत्येक कार्य को पूरा करने के लिए समय की एक इकाई के रूप में जुड़ा हुआ है।
यह एल्गोरिथम विधि बैच-प्रकार प्रसंस्करण के लिए उपयोगी है, जहां कार्य पूरा होने की प्रतीक्षा करना महत्वपूर्ण नहीं है।
यह सुनिश्चित करके प्रक्रिया की गति को बेहतर बना सकता है कि छोटे कार्य पहले निष्पादित हों, जिससे संभवतः परिणाम प्राप्त होने में कम समय लगे।
यह छोटे-छोटे काम पेश करके कार्य उत्पादन में सुधार करता है, जिन्हें पहले निष्पादित किया जाना चाहिए और जिनका टर्नअराउंड समय आमतौर पर कम होता है।

गैर-निवारक एसजेएफ

नॉन-प्रीएम्प्टिव शेड्यूलिंग में, एक बार सीपीयू साइकिल किसी प्रक्रिया को आवंटित हो जाने के बाद, प्रक्रिया उसे तब तक अपने पास रखती है जब तक कि वह प्रतीक्षा स्थिति में नहीं पहुंच जाती या समाप्त नहीं हो जाती।

निम्नलिखित पांच प्रक्रियाओं पर विचार करें, जिनमें से प्रत्येक का अपना अनूठा विस्फोट समय और आगमन समय होता है।

प्रक्रिया कतार	बर्स्ट टाइम	आने का समय
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

चरण 0) समय = 0 पर, P4 आता है और निष्पादन शुरू करता है।

चरण 1) समय = 1 पर, प्रक्रिया P3 आती है। लेकिन P4 को अभी भी पूरा होने के लिए 2 निष्पादन इकाइयों की आवश्यकता है। यह निष्पादन जारी रखेगी।

चरण 2) समय = 2 पर, प्रक्रिया P1 आती है और प्रतीक्षा कतार में जुड़ जाती है। P4 निष्पादन जारी रखेगा।

चरण 3) समय = 3 पर, प्रक्रिया P4 अपना निष्पादन समाप्त कर लेगी। P3 और P1 के बर्स्ट समय की तुलना की जाती है। प्रक्रिया P1 को निष्पादित किया जाता है क्योंकि इसका बर्स्ट समय P3 की तुलना में कम है।

चरण 4) समय = 4 पर, प्रक्रिया P5 आती है और प्रतीक्षा कतार में जुड़ जाती है। P1 निष्पादन जारी रखेगा।

चरण 5) समय = 5 पर, प्रक्रिया P2 आती है और प्रतीक्षा कतार में जुड़ जाती है। P1 निष्पादन जारी रखेगा।

चरण 6) समय = 9 पर, प्रक्रिया P1 अपना निष्पादन समाप्त कर लेगी। P3, P5 और P2 के बर्स्ट समय की तुलना की जाती है। प्रक्रिया P2 निष्पादित होती है क्योंकि इसका बर्स्ट समय सबसे कम है।

चरण 7) समय = 10 पर, P2 निष्पादित हो रहा है और P3 और P5 प्रतीक्षा कतार में हैं।

चरण 8) समय = 11 पर, प्रक्रिया P2 अपना निष्पादन समाप्त कर लेगी। P3 और P5 के बर्स्ट समय की तुलना की जाती है। प्रक्रिया P5 को निष्पादित किया जाता है क्योंकि इसका बर्स्ट समय कम है।

चरण 9) समय = 15 पर, प्रक्रिया P5 अपना निष्पादन समाप्त कर देगी।

चरण 10) समय = 23 पर, प्रक्रिया P3 अपना निष्पादन समाप्त कर देगी।

चरण 11) आइए उपरोक्त उदाहरण के लिए औसत प्रतीक्षा समय की गणना करें।

Wait time
P4 = 0 - 0 = 0
P1 = 3 - 2 = 1
P2 = 9 - 5 = 4
P5 = 11 - 4 = 7
P3 = 15 - 1 = 14

Average Waiting Time = (0 + 1 + 4 + 7 + 14)/5 = 26/5 = 5.2

पूर्वनिवारक एसजेएफ

प्रीएम्प्टिव एसजेएफ शेड्यूलिंग में, जॉब्स आते ही रेडी क्यू में डाल दिए जाते हैं। सबसे कम बर्स्ट टाइम वाली प्रोसेस का निष्पादन शुरू हो जाता है। यदि इससे भी कम बर्स्ट टाइम वाली कोई दूसरी प्रोसेस आती है, तो मौजूदा प्रोसेस को निष्पादन से हटा दिया जाता है या प्रीएम्प्ट कर दिया जाता है, और कम बर्स्ट टाइम वाली जॉब को सीपीयू साइकिल आवंटित कर दी जाती है।

निम्नलिखित पाँच प्रक्रियाओं पर विचार करें:

प्रक्रिया कतार	बर्स्ट टाइम	आने का समय
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

चरण 0) समय = 0 पर, P4 आता है और निष्पादन शुरू करता है।

प्रक्रिया कतार	बर्स्ट टाइम	आने का समय
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

चरण 1) समय = 1 पर, प्रक्रिया P3 आती है। लेकिन P4 का बर्स्ट टाइम कम है। यह निष्पादन जारी रखेगी।

चरण 2) समय = 2 पर, प्रक्रिया P1 बर्स्ट समय = 6 के साथ आती है। बर्स्ट समय P4 से अधिक है। इसलिए, P4 निष्पादन जारी रखेगा।

चरण 3) समय = 3 पर, प्रक्रिया P4 अपना निष्पादन समाप्त कर लेगी। P3 और P1 के बर्स्ट समय की तुलना की जाती है। प्रक्रिया P1 को निष्पादित किया जाता है क्योंकि इसका बर्स्ट समय कम है।

चरण 4) समय = 4 पर, प्रक्रिया P5 आ जाएगी। P3, P5 और P1 के बर्स्ट समय की तुलना की जाती है। प्रक्रिया P5 को निष्पादित किया जाता है क्योंकि इसका बर्स्ट समय सबसे कम है। प्रक्रिया P1 को रोक दिया जाता है।

प्रक्रिया कतार	बर्स्ट टाइम	आने का समय
P1	5 में से 6 शेष है	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

चरण 5) समय = 5 पर, प्रक्रिया P2 आएगी। P1, P2, P3 और P5 के बर्स्ट टाइम की तुलना की जाती है। प्रक्रिया P2 को निष्पादित किया जाता है क्योंकि इसका बर्स्ट टाइम सबसे कम है। प्रक्रिया P5 को रोक दिया जाता है।

प्रक्रिया कतार	बर्स्ट टाइम	आने का समय
P1	5 में से 6 शेष है	2
P2	2	5
P3	8	1
P4	3	0
P5	3 में से 4 शेष है	4

चरण 6) समय = 6 पर, P2 निष्पादित हो रहा है।

चरण 7) समय = 7 पर, P2 का निष्पादन समाप्त हो जाता है। P1, P3 और P5 के बर्स्ट टाइम की तुलना की जाती है। प्रक्रिया P5 को निष्पादित किया जाता है क्योंकि इसका बर्स्ट टाइम कम है।

प्रक्रिया कतार	बर्स्ट टाइम	आने का समय
P1	5 में से 6 शेष है	2
P2	2	5
P3	8	1
P4	3	0
P5	3 में से 4 शेष है	4

चरण 8) समय = 10 पर, P5 का निष्पादन समाप्त हो जाएगा। P1 और P3 के बर्स्ट टाइम की तुलना की जाती है। प्रक्रिया P1 को निष्पादित किया जाता है क्योंकि इसका बर्स्ट टाइम कम है।

चरण 9) समय = 15 पर, P1 का निष्पादन समाप्त हो जाता है। P3 एकमात्र शेष प्रक्रिया है। यह निष्पादन शुरू करेगी।

चरण 10) समय = 23 पर, P3 अपना निष्पादन समाप्त करता है।

चरण 11) आइए उपरोक्त उदाहरण के लिए औसत प्रतीक्षा समय की गणना करें।

Wait time
P4 = 0 - 0 = 0
P1 = (3 - 2) + 6 = 7
P2 = 5 - 5 = 0
P5 = 4 - 4 + 2 = 2
P3 = 15 - 1 = 14

Average Waiting Time = (0 + 7 + 0 + 2 + 14)/5 = 23/5 = 4.6

एसजेएफ के लाभ

एसजेएफ पद्धति का उपयोग करने के लाभ/फायदे इस प्रकार हैं:

एसजेएफ का प्रयोग अक्सर दीर्घकालिक शेड्यूलिंग के लिए किया जाता है।
यह FIFO (फर्स्ट इन फर्स्ट आउट) एल्गोरिदम की तुलना में औसत प्रतीक्षा समय को कम करता है।
एसजेएफ विधि प्रक्रियाओं के एक विशिष्ट समूह के लिए सबसे कम औसत प्रतीक्षा समय प्रदान करती है।
यह बैच में चलने वाले कार्यों के लिए उपयुक्त है, जहां रन टाइम पहले से ज्ञात होता है।
दीर्घकालिक शेड्यूलिंग की बैच प्रणाली के लिए, कार्य विवरण से बर्स्ट समय अनुमान प्राप्त किया जा सकता है।
अल्पावधि निर्धारण के लिए, हमें अगले बर्स्ट समय के मूल्य का पूर्वानुमान लगाने की आवश्यकता है।
औसत टर्नअराउंड समय के लिहाज से यह संभवतः सर्वोत्तम है।

एसजेएफ के नुकसान/नुकसान

एसजेएफ एल्गोरिदम की कुछ कमियां/खामियां इस प्रकार हैं:

कार्य पूरा होने का समय पहले से ज्ञात होना चाहिए, लेकिन इसका पूर्वानुमान लगाना कठिन है।
इसका प्रयोग अक्सर दीर्घकालिक शेड्यूलिंग के लिए बैच सिस्टम में किया जाता है।
SJF को लागू नहीं किया जा सकता है सीपीयू शेड्यूलिंग अल्पावधि के लिए। ऐसा इसलिए है क्योंकि आने वाले CPU बर्स्ट की लंबाई का अनुमान लगाने के लिए कोई विशिष्ट विधि नहीं है।
यह एल्गोरिथ्म बहुत लंबे समय तक काम पूरा न कर पाने या भुखमरी का कारण बन सकता है।
यह जानना आवश्यक है कि कोई प्रक्रिया या कार्य कितने समय तक चलेगा।
इससे भुखमरी की स्थिति उत्पन्न होती है जिससे औसत टर्नअराउंड समय में कमी नहीं आती है।
आगामी CPU अनुरोध की लंबाई जानना कठिन है।
बीते हुए समय को रिकॉर्ड किया जाना चाहिए, जिसके परिणामस्वरूप प्रोसेसर पर अतिरिक्त भार पड़ता है।

अक्सर पूछे जाने वाले प्रश्न

SRTF (Shortest Remaining Time First) SJF का प्रीएम्प्टिव संस्करण है। SJF में, चल रहे जॉब के समाप्त होने के बाद ही अगले जॉब का चयन होता है। SRTF में, कम शेष समय वाला नया जॉब चल रहे प्रोसेस को प्रीएम्प्ट कर सकता है।

SJF हमेशा सबसे छोटे कार्य को प्राथमिकता देता है। यदि छोटे कार्य लगातार आते रहते हैं, तो एक लंबा कार्य CPU प्राप्त नहीं कर पाता और अनिश्चित काल तक प्रतीक्षा करता रहता है। यही भुखमरी है। प्रतीक्षा कर रहे कार्य की प्राथमिकता को धीरे-धीरे बढ़ाने वाली प्रक्रिया, एजिंग, इसे रोकने के लिए उपयोग की जाती है।

जी हाँ। SJF सिद्ध रूप से इष्टतम है क्योंकि यह प्रक्रियाओं के एक दिए गए समूह के लिए न्यूनतम संभव औसत प्रतीक्षा समय उत्पन्न करता है। हालाँकि, यह तभी सत्य है जब बर्स्ट समय पहले से ज्ञात हो, जो व्यवहार में शायद ही कभी संभव होता है।

कृत्रिम बुद्धिमत्ता और मशीन लर्निंग किसी प्रक्रिया के इतिहास, कोड विशेषताओं और पिछले रन का विश्लेषण करके उसके सीपीयू बर्स्ट टाइम का अनुमान लगा सकते हैं। बेहतर पूर्वानुमान एसजेएफ को अधिक सटीक बनाते हैं, जिससे पारंपरिक घातीय औसत अनुमानों की तुलना में प्रतीक्षा समय कम हो जाता है।

संभवतः। अल्पकालिक शेड्यूलिंग में SJF को कठिनाई होती है क्योंकि अत्यधिक मांग का समय अज्ञात होता है। वास्तविक समय में अत्यधिक मांग का पूर्वानुमान लगाने वाली AI SJF को उपयोगी बना सकती है, लेकिन पूर्वानुमान की लागत और त्रुटियां इतनी कम होनी चाहिए कि शेड्यूलिंग का निर्णय सार्थक बना रहे।

सबसे छोटा काम पहले (एसजेएफ): पूर्वनिर्णय, गैर-पूर्वनिर्णय उदाहरण

सबसे छोटी नौकरी पहले शेड्यूलिंग क्या है?

एसजेएफ शेड्यूलिंग की विशेषताएं

गैर-निवारक एसजेएफ

पूर्वनिवारक एसजेएफ

एसजेएफ के लाभ

एसजेएफ के नुकसान/नुकसान

अक्सर पूछे जाने वाले प्रश्न

इस पोस्ट को संक्षेप में इस प्रकार लिखें:

न्यूज़लैटर के लिए साइन अप करें

सबसे छोटी नौकरी पहले शेड्यूलिंग क्या है?

एसजेएफ शेड्यूलिंग की विशेषताएं

गैर-निवारक एसजेएफ

संबंधित आलेख

पूर्वनिवारक एसजेएफ

एसजेएफ के लाभ

एसजेएफ के नुकसान/नुकसान

अक्सर पूछे जाने वाले प्रश्न

इस पोस्ट को संक्षेप में इस प्रकार लिखें:

न्यूज़लैटर के लिए साइन अप करें