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

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

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

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

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

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

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

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

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

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

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

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

सारांश

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