राउंड-रॉबिन शेड्यूलिंग
राउंड-रॉबिन (आरआर) कम्प्यूटिंग में प्रक्रिया अनुसूचक और नेटवर्क अनुसूचक द्वारा नियोजित एल्गोरिदम में से एक है।[1][2]
जैसा कि आमतौर पर इस शब्द का इस्तेमाल किया जाता है, प्रीमेशन (कंप्यूटिंग)#टाइम स्लाइस (टाइम क्वांटा के रूप में भी जाना जाता है)[3] प्रत्येक प्रक्रिया को समान भागों में और परिपत्र क्रम में सौंपा जाता है, सभी प्रक्रियाओं को बिना :wikt:प्राथमिकता (चक्रीय कार्यकारी के रूप में भी जाना जाता है) को संभालना। राउंड-रॉबिन शेड्यूलिंग सरल, लागू करने में आसान और संसाधन भुखमरी से मुक्त है। राउंड-रॉबिन शेड्यूलिंग को अन्य शेड्यूलिंग समस्याओं पर लागू किया जा सकता है, जैसे कंप्यूटर नेटवर्क में डेटा पैकेट शेड्यूलिंग। यह एक ऑपरेटिंग सिस्टम अवधारणा है।[4] एल्गोरिदम का नाम राउंड-रॉबिन (बहुविकल्पी) | राउंड-रॉबिन सिद्धांत से आता है जिसे अन्य क्षेत्रों से जाना जाता है, जहां प्रत्येक व्यक्ति बदले में किसी चीज का बराबर हिस्सा लेता है।
प्रक्रिया निर्धारण
शेड्यूलर को निष्पक्ष रूप से प्रोसेस करने के लिए, एक राउंड-रॉबिन शेड्यूलर आमतौर पर समय बताना को नियोजित करता है, प्रत्येक कार्य को टाइम स्लॉट या क्वांटम देता है।[5] (इसकी CPU समय की अनुमति), और यदि यह तब तक पूरा नहीं होता है तो कार्य को बाधित करना। अगली बार जब उस प्रक्रिया को एक टाइम स्लॉट सौंपा जाता है तो कार्य फिर से शुरू हो जाता है। यदि प्रक्रिया समाप्त हो जाती है या अपनी स्थिति को उसके जिम्मेदार समय क्वांटम के दौरान प्रतीक्षा में बदल देती है, तो अनुसूचक निष्पादित करने के लिए तैयार कतार में पहली प्रक्रिया का चयन करता है। समय-साझाकरण के अभाव में, या यदि क्वांटा नौकरियों के आकार के सापेक्ष बड़े थे, तो एक प्रक्रिया जो बड़ी नौकरियों का उत्पादन करती है, अन्य प्रक्रियाओं के पक्ष में होगी।
राउंड-रॉबिन एल्गोरिथ्म एक पूर्व-खाली एल्गोरिथ्म है क्योंकि समय कोटा समाप्त होने के बाद अनुसूचक प्रक्रिया को सीपीयू से बाहर कर देता है।
उदाहरण के लिए, यदि समय स्लॉट 100 मिलीसेकंड है, और जॉब 1 को पूरा होने में कुल 250 एमएस का समय लगता है, तो राउंड-रॉबिन अनुसूचक 100 एमएस के बाद नौकरी को निलंबित कर देगा और अन्य नौकरियों को सीपीयू पर अपना समय देगा। एक बार अन्य नौकरियों में उनकी समान हिस्सेदारी (100 एमएस प्रत्येक) हो जाने के बाद, जॉब 1 को सीपीयू समय का एक और आवंटन मिलेगा और चक्र दोहराएगा। यह प्रक्रिया तब तक जारी रहती है जब तक कि काम पूरा नहीं हो जाता और सीपीयू पर अधिक समय की आवश्यकता नहीं होती।
- 'जॉब1 = 250 एमएस पूरा करने का कुल समय (क्वांटम 100 एमएस)'।
- पहला आवंटन = 100 मिसे।
- दूसरा आवंटन = 100 मिसे।
- तीसरा आवंटन = 100 एमएस लेकिन जॉब 1 50 एमएस के बाद स्वतः समाप्त हो जाता है।
- जॉब 1 का कुल सीपीयू समय = 250 एमएस
राउंड-रॉबिन शेड्यूलिंग को समझने के लिए आगमन समय के साथ निम्न तालिका पर विचार करें और 100 एमएस के क्वांटम समय के साथ प्रक्रिया का समय निष्पादित करें:
Process name | Arrival time | Execute time |
---|---|---|
P0 | 0 | 250 |
P1 | 50 | 170 |
P2 | 130 | 75 |
P3 | 190 | 100 |
P4 | 210 | 130 |
P5 | 350 | 50 |
एक अन्य दृष्टिकोण यह है कि सभी प्रक्रियाओं को समान संख्या में टाइमिंग क्वांटा में विभाजित किया जाए ताकि क्वांटम आकार प्रक्रिया के आकार के समानुपाती हो। इसलिए, सभी प्रक्रियाएं एक ही समय में समाप्त होती हैं।
नेटवर्क पैकेट शेड्यूलिंग
सर्वोत्तम-प्रयास पैकेट बदली और अन्य सांख्यिकीय बहुसंकेतन में, राउंड-रॉबिन शेड्यूलिंग को पहले आओ-पहले भारित उचित कतार के विकल्प के रूप में इस्तेमाल किया जा सकता है।
एक मल्टीप्लेक्सर, स्विच या राउटर जो राउंड-रॉबिन समयबद्धन भुखमरी करता है, प्रत्येक डेटा प्रवाह के लिए एक अलग कतार होती है, जहां डेटा प्रवाह को उसके स्रोत और गंतव्य पते से पहचाना जा सकता है। एल्गोरिथ्म प्रत्येक सक्रिय डेटा प्रवाह की अनुमति देता है जिसमें समय-समय पर दोहराए गए क्रम में एक साझा चैनल पर पैकेट स्थानांतरित करने के लिए कतार में डेटा पैकेट होते हैं। शेड्यूलिंग कार्य-संरक्षण है, जिसका अर्थ है कि यदि एक प्रवाह पैकेट से बाहर है, तो अगला डेटा प्रवाह उसकी जगह ले लेगा। इसलिए, शेड्यूलिंग लिंक संसाधनों को अप्रयुक्त होने से रोकने का प्रयास करता है।
राउंड-रॉबिन शेड्यूलिंग का परिणाम अधिकतम-न्यूनतम निष्पक्षता में होता है यदि डेटा पैकेट समान आकार के होते हैं, क्योंकि सबसे लंबे समय तक प्रतीक्षा करने वाले डेटा प्रवाह को शेड्यूलिंग प्राथमिकता दी जाती है। यह वांछनीय नहीं हो सकता है यदि डेटा पैकेट का आकार एक कार्य से दूसरे कार्य में व्यापक रूप से भिन्न होता है। एक उपयोगकर्ता जो बड़े पैकेट का उत्पादन करता है, वह अन्य उपयोगकर्ताओं के पक्ष में होगा। उस मामले में निष्पक्ष कतार बेहतर होगी।
यदि सेवा की गारंटीकृत या विभेदित गुणवत्ता की पेशकश की जाती है, और न केवल सर्वोत्तम-प्रयास संचार, घाटा राउंड रॉबिन|डेफिसिट राउंड-रॉबिन (DRR) शेड्यूलिंग, भारित राउंड रॉबिन|वेटेड राउंड-रॉबिन (WRR) शेड्यूलिंग, या वेटेड उचित कतार (WFQ) ) माना जा सकता है।
एकाधिक पहुँच | मल्टीपल एक्सेस नेटवर्क में, जहां कई टर्मिनल एक साझा भौतिक माध्यम से जुड़े होते हैं, राउंड-रॉबिन शेड्यूलिंग टोकन पासिंग चैनल पहुंच स्कीम जैसे निशानी की अंगूठी , या मतदान (कंप्यूटर विज्ञान) या संसाधन आरक्षण द्वारा प्रदान की जा सकती है। केंद्रीय नियंत्रण स्टेशन।
एक केंद्रीकृत वायरलेस पैकेट रेडियो नेटवर्क में, जहां कई स्टेशन एक आवृत्ति चैनल साझा करते हैं, एक केंद्रीय बेस स्टेशन में शेड्यूलिंग एल्गोरिदम मोबाइल स्टेशनों के लिए राउंड-रॉबिन फैशन में समय स्लॉट आरक्षित कर सकता है और निष्पक्षता प्रदान कर सकता है। हालाँकि, यदि लिंक अनुकूलन का उपयोग किया जाता है, तो चैनल की स्थिति भिन्न होने के कारण महंगे उपयोगकर्ताओं को एक निश्चित मात्रा में डेटा संचारित करने में अधिक समय लगेगा। चैनल की स्थितियों में सुधार होने तक प्रसारण के साथ प्रतीक्षा करना या कम खर्चीले उपयोगकर्ताओं को शेड्यूलिंग प्राथमिकता देना अधिक कुशल होगा। राउंड-रॉबिन शेड्यूलिंग इसका उपयोग नहीं करता है। उच्च थ्रूपुट और सिस्टम स्पेक्ट्रम दक्षता चैनल-निर्भर शेड्यूलिंग द्वारा प्राप्त की जा सकती है, उदाहरण के लिए आनुपातिक रूप से उचित एल्गोरिदम, या अधिकतम थ्रूपुट शेड्यूलिंग। ध्यान दें कि उत्तरार्द्ध को अवांछनीय शेड्यूलिंग भुखमरी की विशेषता है। इस प्रकार का शेड्यूलिंग कंप्यूटर में ऑपरेटिंग सिस्टम के लिए बहुत ही बुनियादी एल्गोरिदम में से एक है जिसे एक सर्कुलर कतार डेटा संरचना के माध्यम से लागू किया जा सकता है।
यह भी देखें
संदर्भ
- ↑ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces [Chapter: Scheduling Introduction] (PDF), Arpaci-Dusseau Books
- ↑ Guowang Miao, Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, ISBN 1107143217, 2016.
- ↑ Stallings, William (2015). Operating Systems: Internals and Design Principles. Pearson. p. 409. ISBN 978-0-13-380591-8.
- ↑ Nash, Stacey L. (2022-06-11). "Best scheduling software of 2022". Popular Science (in English). Retrieved 2022-07-07.
- ↑ Silberschatz, Abraham; Galvin, Peter B.; Gagne, Greg (2010). "Process Scheduling". Operating System Concepts (8th ed.). John Wiley & Sons (Asia). p. 194. ISBN 978-0-470-23399-3.
5.3.4 Round Robin Scheduling