सबसे कम काम पहले निर्धारण क्या है?
शॉर्टेस्ट जॉब फर्स्ट (एसजेएफ) एक एल्गोरिथ्म है जिसमें सबसे छोटी निष्पादन समय वाली प्रक्रिया को अगले निष्पादन के लिए चुना जाता है। यह शेड्यूलिंग विधि प्रीमेप्टिव या गैर-प्रीमेप्टिव हो सकती है। यह निष्पादन की प्रतीक्षा कर रही अन्य प्रक्रियाओं के लिए औसत प्रतीक्षा समय को काफी कम कर देता है। एसजेएफ का फुल फॉर्म सबसे छोटा जॉब फर्स्ट है।
मूल रूप से दो प्रकार के एसजेएफ तरीके हैं:
- गैर-निवारक एसजेएफ
- प्रीमेप्टिव एसजेएफ
इस ऑपरेटिंग सिस्टम ट्यूटोरियल में, आप सीखेंगे:
- सबसे कम काम पहले निर्धारण क्या है?
- एसजेएफ निर्धारण के लक्षण
- गैर-निवारक एसजेएफ
- प्रीमेप्टिव एसजेएफ
- एसजेएफ के लाभ
- एसजेएफ के नुकसान / विपक्ष
एसजेएफ निर्धारण के लक्षण
- इसे पूरा करने के लिए समय की एक इकाई के रूप में प्रत्येक कार्य के साथ जुड़ा हुआ है।
- यह एल्गोरिथम विधि बैच-प्रकार प्रसंस्करण के लिए सहायक है, जहां नौकरियों के पूरा होने की प्रतीक्षा करना महत्वपूर्ण नहीं है।
- यह सुनिश्चित करके प्रक्रिया थ्रूपुट में सुधार कर सकता है कि छोटी नौकरियों को पहले निष्पादित किया जाता है, इसलिए संभवतया कम बदलाव का समय होता है।
- यह छोटी नौकरियों की पेशकश करके नौकरी के उत्पादन में सुधार करता है, जिसे पहले निष्पादित किया जाना चाहिए, जिसमें ज्यादातर कम बदलाव का समय होता है।
गैर-निवारक एसजेएफ
नॉन-प्रीमिटिव शेड्यूलिंग में, एक बार सीपीयू चक्र को प्रोसेस करने के लिए आवंटित किया जाता है, प्रक्रिया इसे तब तक रखती है जब तक यह प्रतीक्षा की स्थिति में या समाप्त नहीं हो जाती।
निम्नलिखित पांच प्रक्रियाओं पर विचार करें, जिनमें से प्रत्येक का अपना विशिष्ट समय और आगमन समय हो।
| प्रक्रिया कतार | बर्स्ट टाइम | आने का समय |
| P1 | ६ | २ |
| P2 | २ | ५ |
| पी 3 | । | 1 |
| पी 4 | ३ | ० |
| पी 5 | ४ | ४ |
चरण 0) समय = 0 पर, P4 आता है और निष्पादन शुरू करता है।
चरण 1) समय = 1 पर, प्रक्रिया P3 आता है। लेकिन, P4 को अभी भी पूरा करने के लिए 2 निष्पादन इकाइयों की आवश्यकता है। यह निष्पादन जारी रहेगा।
चरण 2) समय = 2 पर, प्रक्रिया P1 आती है और प्रतीक्षा कतार में जोड़ी जाती है। P4 निष्पादन जारी रखेगा।
चरण 3) समय = 3 पर, प्रक्रिया पी 4 अपना निष्पादन समाप्त कर देगी। पी 3 और पी 1 के फटने के समय की तुलना की जाती है। प्रक्रिया P1 को निष्पादित किया जाता है क्योंकि इसका फटने का समय P3 की तुलना में कम होता है।
चरण 4) समय = 4 पर, प्रक्रिया P5 आती है और प्रतीक्षा कतार में जोड़ी जाती है। P1 निष्पादन जारी रखेगा।
चरण 5) समय = 5 पर, पी 2 आता है और प्रतीक्षा कतार में जोड़ा जाता है। P1 निष्पादन जारी रखेगा।
चरण 6) समय = 9 पर, प्रक्रिया P1 अपने निष्पादन को समाप्त कर देगा। पी 3, पी 5 और पी 2 के फटने के समय की तुलना की जाती है। प्रोसेस पी 2 को निष्पादित किया जाता है क्योंकि इसका फटने का समय सबसे कम है।
चरण 7) समय = 10 पर, पी 2 निष्पादित हो रहा है और पी 3 और पी 5 प्रतीक्षा कतार में हैं।
चरण 8) समय = 11 पर, प्रक्रिया पी 2 इसका निष्पादन समाप्त कर देगी। पी 3 और पी 5 के फटने के समय की तुलना की जाती है। प्रक्रिया P5 को निष्पादित किया जाता है क्योंकि इसका फटने का समय कम है।
चरण 9) समय = 15 पर, प्रक्रिया P5 इसका निष्पादन समाप्त कर देगा।
चरण 10) समय = 23 पर, प्रक्रिया P3 इसका निष्पादन समाप्त कर देगी।
चरण 11) आइए उपरोक्त उदाहरण के लिए औसत प्रतीक्षा समय की गणना करें।
Wait timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
प्रीमेप्टिव एसजेएफ
प्रीजेप्टिव एसजेएफ शेड्यूलिंग में, नौकरियों को तैयार कतार में रखा जाता है जैसे ही वे आते हैं। कम से कम फटने की प्रक्रिया के साथ निष्पादन शुरू होता है। यदि कम फटने वाले समय के साथ भी कोई प्रक्रिया आती है, तो वर्तमान प्रक्रिया को हटा दिया जाता है या निष्पादन से पहले हटा दिया जाता है, और छोटी नौकरी को CPU चक्र आवंटित किया जाता है।
निम्नलिखित पांच प्रक्रिया पर विचार करें:
| प्रक्रिया कतार | बर्स्ट टाइम | आने का समय |
| P1 | ६ | २ |
| P2 | २ | ५ |
| पी 3 | । | 1 |
| पी 4 | ३ | ० |
| पी 5 | ४ | ४ |
चरण 0) समय = 0 पर, P4 आता है और निष्पादन शुरू करता है।
| प्रक्रिया कतार | बर्स्ट टाइम | आने का समय |
| P1 | ६ | २ |
| P2 | २ | ५ |
| पी 3 | । | 1 |
| पी 4 | ३ | ० |
| पी 5 | ४ | ४ |
चरण 1) समय = 1 पर, प्रक्रिया P3 आता है। लेकिन, P4 का समय कम है। यह निष्पादन जारी रहेगा।
चरण 2) समय = 2 पर, प्रक्रिया पी 1 फट समय के साथ आता है = 6. फटने का समय पी 4 की तुलना में अधिक है। इसलिए, P4 निष्पादन जारी रखेगा।
चरण 3) समय = 3 पर, प्रक्रिया पी 4 अपना निष्पादन समाप्त कर देगी। पी 3 और पी 1 के फटने के समय की तुलना की जाती है। प्रक्रिया P1 को निष्पादित किया जाता है क्योंकि इसका फटने का समय कम है।
चरण 4) समय = 4 पर, प्रक्रिया P5 आ जाएगी। P3, P5 और P1 के फटने के समय की तुलना की जाती है। प्रक्रिया P5 को निष्पादित किया जाता है क्योंकि इसका फटने का समय सबसे कम है। प्रक्रिया P1 पूर्वनिर्मित है।
| प्रक्रिया कतार | बर्स्ट टाइम | आने का समय |
| P1 | 6 में से 5 शेष है | २ |
| P2 | २ | ५ |
| पी 3 | । | 1 |
| पी 4 | ३ | ० |
| पी 5 | ४ | ४ |
चरण 5) समय = 5 पर, प्रक्रिया पी 2 आ जाएगी। P1, P2, P3 और P5 के फटने के समय की तुलना की जाती है। प्रक्रिया P2 को निष्पादित किया जाता है क्योंकि इसका फटने का समय कम से कम है। प्रक्रिया P5 पूर्वनिर्मित है।
| प्रक्रिया कतार | बर्स्ट टाइम | आने का समय |
| P1 | 6 में से 5 शेष है | २ |
| P2 | २ | ५ |
| पी 3 | । | 1 |
| पी 4 | ३ | ० |
| पी 5 | 4 में से 3 शेष है | ४ |
चरण 6) समय = 6 पर, पी 2 निष्पादित हो रहा है।
चरण 7) समय = 7 पर, पी 2 ने इसका निष्पादन समाप्त कर दिया। P1, P3 और P5 के फटने के समय की तुलना की जाती है। प्रक्रिया P5 को निष्पादित किया जाता है क्योंकि इसका फटने का समय कम होता है।
| प्रक्रिया कतार | बर्स्ट टाइम | आने का समय |
| P1 | 6 में से 5 शेष है | २ |
| P2 | २ | ५ |
| पी 3 | । | 1 |
| पी 4 | ३ | ० |
| पी 5 | 4 में से 3 शेष है | ४ |
चरण 8) समय = 10 पर, पी 5 इसका निष्पादन समाप्त कर देगा। पी 1 और पी 3 के फटने के समय की तुलना की जाती है। प्रक्रिया P1 को निष्पादित किया जाता है क्योंकि इसके फटने का समय कम होता है।
चरण 9) समय = 15 पर, P1 अपने निष्पादन को पूरा करता है। P3 केवल प्रक्रिया है। इस पर अमल शुरू हो जाएगा।
चरण 10) समय = 23 पर, पी 3 ने इसका निष्पादन समाप्त कर दिया।
चरण 11) आइए उपरोक्त उदाहरण के लिए औसत प्रतीक्षा समय की गणना करें।
Wait timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
एसजेएफ के लाभ
यहाँ SJF विधि का उपयोग करने के लाभ / नियम हैं:
- एसजेएफ का उपयोग अक्सर दीर्घकालिक निर्धारण के लिए किया जाता है।
- यह FIFO (फर्स्ट इन फर्स्ट आउट) एल्गोरिदम पर औसत प्रतीक्षा समय को कम करता है।
- एसजेएफ विधि प्रक्रियाओं के एक विशिष्ट सेट के लिए सबसे कम औसत प्रतीक्षा समय देती है।
- यह बैच में चल रही नौकरियों के लिए उपयुक्त है, जहां पहले से ही रन समय जाना जाता है।
- दीर्घकालिक शेड्यूलिंग के बैच सिस्टम के लिए, नौकरी विवरण से एक फट समय अनुमान प्राप्त किया जा सकता है।
- शॉर्ट-टर्म शेड्यूलिंग के लिए, हमें अगले फटने वाले समय के मूल्य की भविष्यवाणी करने की आवश्यकता है।
- संभवतः औसत टर्नअराउंड समय के संबंध में इष्टतम।
एसजेएफ के नुकसान / विपक्ष
यहाँ एसजेएफ एल्गोरिथ्म के कुछ कमियां / विपक्ष हैं:
- नौकरी पूरा होने का समय पहले से पता होना चाहिए, लेकिन यह भविष्यवाणी करना कठिन है।
- इसका उपयोग अक्सर लंबी अवधि के लिए एक बैच सिस्टम में किया जाता है।
- लघु अवधि के लिए CPU समय-निर्धारण के लिए SJF को लागू नहीं किया जा सकता है। ऐसा इसलिए है क्योंकि आगामी सीपीयू फट की लंबाई का अनुमान लगाने के लिए कोई विशिष्ट विधि नहीं है।
- यह एल्गोरिथ्म बहुत लंबे समय तक बदलाव या भुखमरी का कारण बन सकता है।
- एक प्रक्रिया या नौकरी कब तक चलेगी, इसका ज्ञान आवश्यक है।
- यह भुखमरी की ओर जाता है जो औसत प्रतिवर्तन समय को कम नहीं करता है।
- आगामी CPU अनुरोध की लंबाई जानना कठिन है।
- बीता हुआ समय रिकॉर्ड किया जाना चाहिए, जिसके परिणामस्वरूप प्रोसेसर पर अधिक ओवरहेड हो सकता है।
सारांश
- एसजेएफ एक एल्गोरिथ्म है जिसमें सबसे छोटी निष्पादन समय वाली प्रक्रिया को अगले निष्पादन के लिए चुना जाता है।
- एसजेएफ शेड्यूलिंग प्रत्येक नौकरी के साथ समय की एक इकाई के रूप में जुड़ी है।
- यह एल्गोरिथम विधि बैच-प्रकार प्रसंस्करण के लिए सहायक है, जहां नौकरियों के पूरा होने की प्रतीक्षा करना महत्वपूर्ण नहीं है।
- मूल रूप से दो प्रकार के एसजेएफ तरीके हैं 1) गैर-निवारक एसजेएफ और 2) प्रीमेप्टिव एसजेएफ।
- नॉन-प्रीमिटिव शेड्यूलिंग में, एक बार सीपीयू चक्र को प्रोसेस करने के लिए आवंटित किया जाता है, प्रक्रिया इसे तब तक रखती है जब तक यह प्रतीक्षा की स्थिति में या समाप्त नहीं हो जाती।
- प्रीजेप्टिव एसजेएफ शेड्यूलिंग में, नौकरियों को तैयार कतार में रखा जाता है जैसे ही वे आते हैं।
- हालाँकि, शॉर्ट बर्स्ट टाइम के साथ एक प्रक्रिया शुरू होती है, मौजूदा प्रक्रिया को निष्कासन से हटा दिया जाता है और जो कार्य छोटा होता है उसे 1 निष्पादित किया जाता है।
- एसजेएफ का उपयोग अक्सर दीर्घकालिक निर्धारण के लिए किया जाता है।
- यह FIFO (फर्स्ट इन फर्स्ट आउट) एल्गोरिदम पर औसत प्रतीक्षा समय को कम करता है।
- एसजेएफ शेड्यूलिंग में, नौकरी पूरा होने का समय पहले से पता होना चाहिए, लेकिन यह भविष्यवाणी करना मुश्किल है।
- लघु अवधि के लिए CPU समय-निर्धारण के लिए SJF को लागू नहीं किया जा सकता है। ऐसा इसलिए है क्योंकि आगामी सीपीयू फट की लंबाई का अनुमान लगाने के लिए कोई विशिष्ट विधि नहीं है।