राउंड-रॉबिन शेड्यूलिंग: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Algorithm employed by process and network schedulers in computing}}
{{Short description|Algorithm employed by process and network schedulers in computing}}
{{About|scheduling in computing|other uses|Round-robin (disambiguation)}}
{{About|कंप्यूटिंग में शेड्यूलिंग|अन्य उपयोग |राउंड-रॉबिन (बहुविकल्पी)}}


[[File:Round Robin Schedule Example.jpg|thumb|350x350px|क्वांटम=3 के साथ राउंड रॉबिन प्रीमेप्टिव शेड्यूलिंग उदाहरण]]राउंड-रॉबिन (आरआर) [[ कम्प्यूटिंग ]] में [[ प्रक्रिया अनुसूचक ]] और [[ नेटवर्क अनुसूचक ]] द्वारा नियोजित एल्गोरिदम में से है।<ref name="ostep-1">{{citation|title=Operating Systems: Three Easy Pieces [Chapter: Scheduling Introduction]|url=http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf|publisher= Arpaci-Dusseau Books|date = 2014|first1 = Remzi H.|last1 =Arpaci-Dusseau|first2=Andrea C.|last2 = Arpaci-Dusseau}}</ref><ref name=Zander>[[Guowang Miao]], Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, {{ISBN|1107143217}}, 2016.</ref>
[[File:Round Robin Schedule Example.jpg|thumb|350x350px|क्वांटम=3 के साथ राउंड रॉबिन प्रीमेप्टिव शेड्यूलिंग उदाहरण]]राउंड-रॉबिन (आरआर) [[ कम्प्यूटिंग |कम्प्यूटिंग]] में [[ प्रक्रिया अनुसूचक |प्रक्रिया अनुसूचक]] और [[ नेटवर्क अनुसूचक |नेटवर्क अनुसूचक]] द्वारा नियोजित एल्गोरिदम में से एक है।<ref name="ostep-1">{{citation|title=Operating Systems: Three Easy Pieces [Chapter: Scheduling Introduction]|url=http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf|publisher= Arpaci-Dusseau Books|date = 2014|first1 = Remzi H.|last1 =Arpaci-Dusseau|first2=Andrea C.|last2 = Arpaci-Dusseau}}</ref><ref name=Zander>[[Guowang Miao]], Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, {{ISBN|1107143217}}, 2016.</ref>
जैसा कि आमतौर पर इस शब्द का इस्तेमाल किया जाता है, प्रीमेशन (कंप्यूटिंग)#टाइम स्लाइस (टाइम क्वांटा के रूप में भी जाना जाता है)<ref>{{Cite book|title=Operating Systems: Internals and Design Principles|last=Stallings|first=William|publisher=Pearson|year=2015|isbn=978-0-13-380591-8|pages=409}}</ref> प्रत्येक प्रक्रिया को समान भागों में और परिपत्र क्रम में सौंपा जाता है, सभी प्रक्रियाओं को बिना :wikt:प्राथमिकता ([[चक्रीय कार्यकारी]] के रूप में भी जाना जाता है) को संभालना। राउंड-रॉबिन शेड्यूलिंग सरल, लागू करने में आसान और [[संसाधन भुखमरी]] से मुक्त है। राउंड-रॉबिन शेड्यूलिंग को अन्य शेड्यूलिंग समस्याओं पर लागू किया जा सकता है, जैसे कंप्यूटर नेटवर्क में डेटा पैकेट शेड्यूलिंग। यह [[ऑपरेटिंग सिस्टम]] अवधारणा है।<ref>{{cite web
जैसा कि सामान्तः इस शब्द का उपयोग किया जाता है, समय स्लाइस (जिसे समय क्वांटा के रूप में भी जाना जाता है)<ref>{{Cite book|title=Operating Systems: Internals and Design Principles|last=Stallings|first=William|publisher=Pearson|year=2015|isbn=978-0-13-380591-8|pages=409}}</ref> प्रत्येक प्रक्रिया को समान भागों में और परिपत्र क्रम में दिया जाता है, सभी प्रक्रियाओं को बिना प्राथमिकता ([[चक्रीय कार्यकारी]] के रूप में भी जाना जाता है) को संभालना राउंड-रॉबिन शेड्यूलिंग सरल, प्रयुक्त करने में सरल और [[संसाधन भुखमरी|संसाधन अप्राप्ति]] से मुक्त किये जाते है। राउंड-रॉबिन शेड्यूलिंग को अन्य शेड्यूलिंग समस्याओं पर प्रचलित किया जा सकता है, जैसे की कंप्यूटर नेटवर्क में डेटा पैकेट शेड्यूलिं की यह [[ऑपरेटिंग सिस्टम]] की अवधारणा मानी जाती है।<ref>{{cite web
|title=Best scheduling software of 2022
|title=Best scheduling software of 2022
|url=https://www.popsci.com/gear/best-scheduling-software/
|url=https://www.popsci.com/gear/best-scheduling-software/
Line 14: Line 14:
}}</ref>
}}</ref>


एल्गोरिदम का नाम [[राउंड-रॉबिन (बहुविकल्पी)]] | राउंड-रॉबिन सिद्धांत से आता है जिसे अन्य क्षेत्रों से जाना जाता है, जहां प्रत्येक व्यक्ति बदले में किसी चीज का बराबर हिस्सा लेता है।
इस प्रकार से एल्गोरिदम का नाम [[राउंड-रॉबिन (बहुविकल्पी)]] | राउंड-रॉबिन सिद्धांत से आता है जिसे अन्य क्षेत्रों से जाना जाता है, जहां प्रत्येक व्यक्ति बदले में किसी वस्तु में सामान रूप से भाग ले सकते है।


== प्रक्रिया निर्धारण ==
== प्रक्रिया निर्धारण ==
शेड्यूलर को निष्पक्ष रूप से प्रोसेस करने के लिए, राउंड-रॉबिन शेड्यूलर आमतौर पर [[ समय बताना ]] को नियोजित करता है, प्रत्येक कार्य को टाइम स्लॉट या क्वांटम देता है।<ref name = "McConnell2004">{{cite book
प्रक्रियाओं को निष्पक्ष रूप से प्रोसेस करने के लिए, राउंड-रॉबिन निर्धारण सामान्तः [[ समय बताना |समय बताना]] को नियोजित करता है, प्रत्येक कार्य को समय स्लॉट या क्वांटम देता है।<ref name = "McConnell2004">{{cite book
  | title = [[Operating System Concepts]]
  | title = [[Operating System Concepts]]
  | last1 = Silberschatz
  | last1 = Silberschatz
Line 33: Line 33:
  | edition = 8th
  | edition = 8th
  | pages = 194
  | pages = 194
}}</ref> (इसकी [[ CPU ]] समय की अनुमति), और यदि यह तब तक पूरा नहीं होता है तो कार्य को बाधित करना। अगली बार जब उस प्रक्रिया को टाइम स्लॉट सौंपा जाता है तो कार्य फिर से शुरू हो जाता है। यदि प्रक्रिया समाप्त हो जाती है या अपनी स्थिति को उसके जिम्मेदार समय क्वांटम के दौरान प्रतीक्षा में बदल देती है, तो अनुसूचक निष्पादित करने के लिए तैयार कतार में पहली प्रक्रिया का चयन करता है। समय-साझाकरण के अभाव में, या यदि क्वांटा नौकरियों के आकार के सापेक्ष बड़े थे, तो  प्रक्रिया जो बड़ी नौकरियों का उत्पादन करती है, अन्य प्रक्रियाओं के पक्ष में होगी।
}}</ref> और (इसकी [[ CPU |सीपीयू]] समय की अनुमति), यदि यह तब तक पूरा नहीं होता है जब तक कार्य को बाधित करना होता है। इस प्रकार से जब उस प्रक्रिया को समय स्लॉट सौंपा जाता है तो कार्य फिर से प्रारंभ हो जाता है। यदि प्रक्रिया समाप्त हो जाती है या अपनी स्थिति को उसके उत्तरदायी समय क्वांटम के अतिरिक्त प्रतीक्षा में बदल देती है, तो अनुसूचक निष्पादित करने के लिए तैयार श्रेणी में प्रथम प्रक्रिया का चयन करता है। और समय-साझाकरण के अभाव में, या यदि क्वांटा सामान्य कार्य के आकार पर सापेक्ष उच्च थे, तब यह प्रक्रिया जो बड़ी सामान्य कार्य का उत्पादन करती है, अन्य प्रक्रियाओं के पक्ष में होती है।


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


उदाहरण के लिए, यदि समय स्लॉट 100 मिलीसेकंड है, और जॉब 1 को पूरा होने में कुल 250 एमएस का समय लगता है, तो राउंड-रॉबिन अनुसूचक 100 एमएस के बाद नौकरी को निलंबित कर देगा और अन्य नौकरियों को सीपीयू पर अपना समय देगा।  बार अन्य नौकरियों में उनकी समान हिस्सेदारी (100 एमएस प्रत्येक) हो जाने के बाद, जॉब 1 को सीपीयू समय का और आवंटन मिलेगा और चक्र दोहराएगा। यह प्रक्रिया तब तक जारी रहती है जब तक कि काम पूरा नहीं हो जाता और सीपीयू पर अधिक समय की आवश्यकता नहीं होती।
उदाहरण के लिए, यदि समय स्लॉट 100 मिलीसेकंड है, और कार्य 1 को पूरा होने में कुल 250 एमएस का समय लगता है, तो राउंड-रॉबिन अनुसूचक 100 एमएस के बाद नौकरी को निलंबित कर देता है और अन्य सामान्य कार्य को सीपीयू पर अपना समय देता है।और अन्य सामान्य कार्य में उनकी समान भागीदारी (100 एमएस प्रत्येक) हो जाने के बाद, कार्य 1 को सीपीयू समय का और आवंटन मिलेगा और चक्र दोहराया जाता है। यह प्रक्रिया तब तक प्रयुक्त रहती है जब तक कि कार्य पूर्ण नहीं हो जाता और सीपीयू पर अधिक समय की आवश्यकता नहीं होती है।


* 'जॉब1 = 250 एमएस पूरा करने का कुल समय (क्वांटम 100 एमएस)'।
* 'कार्य 1 = 250 एमएस पूरा करने का कुल समय (क्वांटम 100 एमएस)'।
# पहला आवंटन = 100 मिसे।
# प्रथम आवंटन = 100 एमएस.
# दूसरा आवंटन = 100 मिसे।
# द्वतीय आवंटन = 100 एमएस.
# तीसरा आवंटन = 100 एमएस लेकिन जॉब 1 50 एमएस के बाद स्वतः समाप्त हो जाता है।
# तीसरा आवंटन = 100 एमएस लेकिन कार्य 1 50 एमएस के बाद स्व-समाप्त हो जाता है।
# जॉब 1 का कुल सीपीयू समय = 250 एमएस
# कार्य 1 का कुल सीपीयू समय = 250 एमएस


राउंड-रॉबिन शेड्यूलिंग को समझने के लिए आगमन समय के साथ निम्न तालिका पर विचार करें और 100 एमएस के क्वांटम समय के साथ प्रक्रिया का समय निष्पादित करें:
इस प्रकार सेराउंड-रॉबिन शेड्यूलिंग को समझने के लिए आगमन समय के साथ निम्नलिखित तालिका पर विचार करें और 100 एमएस के क्वांटम समय के साथ प्रक्रिया के निष्पादन समय पर विचार करें:


{| class="wikitable" style="margin: 1em auto 1em auto;"
{| class="wikitable" style="margin: 1em auto 1em auto;"
|-
|-
! Process name !! Arrival time !! Execute time
! प्रक्रिया नाम !! आगमन समय !! समय निष्पादित करें
|-
|-
| P0 || 0 || 250  
| पी0 || 0 || 250  
|-
|-
| P1 || 50 || 170  
| पी1 || 50 || 170  
|-
|-
| P2 || 130 ||  75
| पी2 || 130 ||  75
|-
|-
| P3 || 190 || 100  
| पी3 || 190 || 100  
|-
|-
| P4 || 210 || 130  
| पी4 || 210 || 130  
|-
|-
| P5 || 350 || 50
| पी5 || 350 || 50
|}
|}


[[File:RoundRobin.jpg|center|400px|राउंड रॉबिन शेड्यूलिंग]]अन्य दृष्टिकोण यह है कि सभी प्रक्रियाओं को समान संख्या में टाइमिंग क्वांटा में विभाजित किया जाए ताकि क्वांटम आकार प्रक्रिया के आकार के समानुपाती हो। इसलिए, सभी प्रक्रियाएं ही समय में समाप्त होती हैं।
[[File:RoundRobin.jpg|center|400px|राउंड रॉबिन शेड्यूलिंग]]अन्य दृष्टिकोण इस प्रकार से है कि सभी प्रक्रियाओं को समान संख्या में समय क्वांटा में विभाजित किया जाए ताकि क्वांटम आकार प्रक्रिया के आकार के समानुपाती हो जाये। इसलिए, सभी प्रक्रियाएं ही समय में समाप्त होती हैं।


== नेटवर्क पैकेट शेड्यूलिंग ==
== नेटवर्क पैकेट शेड्यूलिंग ==
{{Main|Network scheduler}}
{{Main|नेटवर्क शेड्यूलर}}
सर्वोत्तम-प्रयास [[ पैकेट बदली ]] और अन्य [[सांख्यिकीय बहुसंकेतन]] में, राउंड-रॉबिन शेड्यूलिंग को पहले आओ-पहले [[भारित उचित कतार]] के विकल्प के रूप में इस्तेमाल किया जा सकता है।
सर्वोत्तम-प्रयास [[ पैकेट बदली |सबसे अच्छा प्रयास पैकेट स्विचिंग]] और अन्य [[सांख्यिकीय बहुसंकेतन]] में, राउंड-रॉबिन शेड्यूलिंग को पहले आओ-पहले [[भारित उचित कतार|भारित उचित श्रेणी]] के विकल्प के रूप में प्रोयोग किया जा सकता है।


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


राउंड-रॉबिन शेड्यूलिंग का परिणाम [[अधिकतम-न्यूनतम निष्पक्षता]] में होता है यदि डेटा पैकेट समान आकार के होते हैं, क्योंकि सबसे लंबे समय तक प्रतीक्षा करने वाले डेटा प्रवाह को शेड्यूलिंग प्राथमिकता दी जाती है। यह वांछनीय नहीं हो सकता है यदि डेटा पैकेट का आकार कार्य से दूसरे कार्य में व्यापक रूप से भिन्न होता है। उपयोगकर्ता जो बड़े पैकेट का उत्पादन करता है, वह अन्य उपयोगकर्ताओं के पक्ष में होगा। उस मामले में निष्पक्ष कतार बेहतर होगी।
राउंड-रॉबिन शेड्यूलिंग का परिणाम [[अधिकतम-न्यूनतम निष्पक्षता]] में होता है यदि डेटा पैकेट समान आकार के होते हैं, क्योंकि सबसे लंबे समय तक प्रतीक्षा करने वाले डेटा प्रवाह को शेड्यूलिंग प्राथमिकता दी जाती है। यह वांछनीय नहीं हो सकता है यदि डेटा पैकेट का आकार कार्य से दूसरे कार्य में व्यापक रूप से भिन्न होता है। तब उपयोगकर्ता जो बड़े पैकेट का उत्पादन करता है, वह अन्य उपयोगकर्ताओं के पक्ष में होता है। उस विषय में निष्पक्ष श्रेणी सही मानी जाती है।


यदि सेवा की गारंटीकृत या विभेदित गुणवत्ता की पेशकश की जाती है, और न केवल सर्वोत्तम-प्रयास संचार, [[घाटा राउंड रॉबिन]]|डेफिसिट राउंड-रॉबिन (DRR) शेड्यूलिंग, [[भारित राउंड रॉबिन]]|वेटेड राउंड-रॉबिन (WRR) शेड्यूलिंग, या वेटेड [[ उचित कतार ]] (WFQ) ) माना जा सकता है।
यदि सेवा की गारंटीकृत या विभेदित गुणवत्ता की प्रस्तुत की जाती है, और न केवल सर्वोत्तम-प्रयास संचार, [[घाटा राउंड रॉबिन|भारित राउंड रॉबिन]] डेफिसिट राउंड-रॉबिन (डीआरआर) शेड्यूलिंग, [[भारित राउंड रॉबिन]]|वेटेड राउंड-रॉबिन (डब्ल्यूआरआर) शेड्यूलिंग, या वेटेड [[ उचित कतार |उचित श्रेणी]] (डब्ल्यूएफक्यू) ) माना जाता है।


[[ एकाधिक पहुँच ]] | मल्टीपल एक्सेस नेटवर्क में, जहां कई टर्मिनल साझा भौतिक माध्यम से जुड़े होते हैं, राउंड-रॉबिन शेड्यूलिंग [[टोकन पासिंग]] [[ चैनल पहुंच ]] स्कीम जैसे [[ निशानी की अंगूठी ]], या [[ मतदान (कंप्यूटर विज्ञान) ]] या संसाधन आरक्षण द्वारा प्रदान की जा सकती है। केंद्रीय नियंत्रण स्टेशन।
[[ एकाधिक पहुँच | एकाधिक का उपयोग]] मल्टीपल एक्सेस नेटवर्क में, जहां कई टर्मिनल साझा भौतिक माध्यम से जुड़े होते हैं, राउंड-रॉबिन शेड्यूलिंग [[टोकन पासिंग|टोकन पासिंग चैनल का उपयोग]] [[ चैनल पहुंच |चैनल पहुंच]] स्कीम जैसे [[ निशानी की अंगूठी |टोकन की रिंग]] , या [[ मतदान (कंप्यूटर विज्ञान) |मतदान (कंप्यूटर विज्ञान)]] या संसाधन आरक्षण द्वारा प्रदान की जा सकती है। केंद्रीय नियंत्रण स्टेशन से संसाधन आरक्षण आदि।


केंद्रीकृत वायरलेस पैकेट रेडियो नेटवर्क में, जहां कई स्टेशन आवृत्ति चैनल साझा करते हैं, केंद्रीय बेस स्टेशन में शेड्यूलिंग एल्गोरिदम मोबाइल स्टेशनों के लिए राउंड-रॉबिन फैशन में समय स्लॉट आरक्षित कर सकता है और निष्पक्षता प्रदान कर सकता है। हालाँकि, यदि [[लिंक अनुकूलन]] का उपयोग किया जाता है, तो चैनल की स्थिति भिन्न होने के कारण महंगे उपयोगकर्ताओं को निश्चित मात्रा में डेटा संचारित करने में अधिक समय लगेगा। चैनल की स्थितियों में सुधार होने तक प्रसारण के साथ प्रतीक्षा करना या कम खर्चीले उपयोगकर्ताओं को शेड्यूलिंग प्राथमिकता देना अधिक कुशल होगा। राउंड-रॉबिन शेड्यूलिंग इसका उपयोग नहीं करता है। उच्च थ्रूपुट और [[सिस्टम स्पेक्ट्रम दक्षता]] चैनल-निर्भर शेड्यूलिंग द्वारा प्राप्त की जा सकती है, उदाहरण के लिए [[आनुपातिक रूप से उचित]] एल्गोरिदम, या [[अधिकतम थ्रूपुट शेड्यूलिंग]]। ध्यान दें कि उत्तरार्द्ध को अवांछनीय शेड्यूलिंग भुखमरी की विशेषता है। इस प्रकार का शेड्यूलिंग कंप्यूटर में ऑपरेटिंग सिस्टम के लिए बहुत ही बुनियादी एल्गोरिदम में से है जिसे सर्कुलर कतार डेटा संरचना के माध्यम से लागू किया जा सकता है।
केंद्रीकृत वायरलेस पैकेट रेडियो नेटवर्क में, जहां कई स्टेशन आवृत्ति चैनल साझा करते हैं, केंद्रीय बेस स्टेशन में शेड्यूलिंग एल्गोरिदम मोबाइल स्टेशनों के लिए राउंड-रॉबिन फैशन में समय स्लॉट आरक्षित कर सकता है और निष्पक्षता प्रदान कर सकता है। चूँकि , यदि [[लिंक अनुकूलन]] का उपयोग किया जाता है, तो चैनल की स्थिति भिन्न होने के कारण महंगे उपयोगकर्ताओं को निश्चित मात्रा में डेटा संचारित करने में अधिक समय लगता है। चैनल की स्थितियों में सुधार होने तक प्रसारण के साथ प्रतीक्षा करना या कम व्यय उपयोगकर्ताओं को शेड्यूलिंग प्राथमिकता देना अधिक कुशल होता है। और राउंड-रॉबिन शेड्यूलिंग इसका उपयोग नहीं करता है। उच्च थ्रूपुट और [[सिस्टम स्पेक्ट्रम दक्षता]] चैनल-निर्भर शेड्यूलिंग द्वारा प्राप्त की जा सकती है, उदाहरण के लिए [[आनुपातिक रूप से उचित]] एल्गोरिदम, या [[अधिकतम थ्रूपुट शेड्यूलिंग]]। इस प्रकार से यह उत्तरार्द्ध को अवांछनीय शेड्यूलिंग अप्राप्ति की विशेषता है। इस प्रकार का शेड्यूलिंग कंप्यूटर में ऑपरेटिंग सिस्टम के लिए बहुत ही बुनियादी एल्गोरिदम में से है जिसे सर्कुलर श्रेणी डेटा संरचना के माध्यम से प्रचलित किया जा सकता है।


== यह भी देखें ==
== यह भी देखें ==
* [[बहुस्तरीय कतार]]
* [[बहुस्तरीय कतार|बहुस्तरीय श्रेणी]]  


==संदर्भ==
==संदर्भ==
Line 87: Line 87:


{{Queueing theory}}
{{Queueing theory}}
[[Category: प्रोसेसर शेड्यूलिंग एल्गोरिदम]] [[Category: नेटवर्क शेड्यूलिंग एल्गोरिदम]]


 
[[Category:Articles with hatnote templates targeting a nonexistent page]]
 
[[Category:CS1 English-language sources (en)]]
[[Category: Machine Translated Page]]
[[Category:Collapse templates]]
[[Category:Created On 18/06/2023]]
[[Category:Created On 18/06/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:नेटवर्क शेड्यूलिंग एल्गोरिदम]]
[[Category:प्रोसेसर शेड्यूलिंग एल्गोरिदम]]

Latest revision as of 11:33, 30 June 2023

क्वांटम=3 के साथ राउंड रॉबिन प्रीमेप्टिव शेड्यूलिंग उदाहरण

राउंड-रॉबिन (आरआर) कम्प्यूटिंग में प्रक्रिया अनुसूचक और नेटवर्क अनुसूचक द्वारा नियोजित एल्गोरिदम में से एक है।[1][2]

जैसा कि सामान्तः इस शब्द का उपयोग किया जाता है, समय स्लाइस (जिसे समय क्वांटा के रूप में भी जाना जाता है)[3] प्रत्येक प्रक्रिया को समान भागों में और परिपत्र क्रम में दिया जाता है, सभी प्रक्रियाओं को बिना प्राथमिकता (चक्रीय कार्यकारी के रूप में भी जाना जाता है) को संभालना राउंड-रॉबिन शेड्यूलिंग सरल, प्रयुक्त करने में सरल और संसाधन अप्राप्ति से मुक्त किये जाते है। राउंड-रॉबिन शेड्यूलिंग को अन्य शेड्यूलिंग समस्याओं पर प्रचलित किया जा सकता है, जैसे की कंप्यूटर नेटवर्क में डेटा पैकेट शेड्यूलिं की यह ऑपरेटिंग सिस्टम की अवधारणा मानी जाती है।[4]

इस प्रकार से एल्गोरिदम का नाम राउंड-रॉबिन (बहुविकल्पी) | राउंड-रॉबिन सिद्धांत से आता है जिसे अन्य क्षेत्रों से जाना जाता है, जहां प्रत्येक व्यक्ति बदले में किसी वस्तु में सामान रूप से भाग ले सकते है।

प्रक्रिया निर्धारण

प्रक्रियाओं को निष्पक्ष रूप से प्रोसेस करने के लिए, राउंड-रॉबिन निर्धारण सामान्तः समय बताना को नियोजित करता है, प्रत्येक कार्य को समय स्लॉट या क्वांटम देता है।[5] और (इसकी सीपीयू समय की अनुमति), यदि यह तब तक पूरा नहीं होता है जब तक कार्य को बाधित करना होता है। इस प्रकार से जब उस प्रक्रिया को समय स्लॉट सौंपा जाता है तो कार्य फिर से प्रारंभ हो जाता है। यदि प्रक्रिया समाप्त हो जाती है या अपनी स्थिति को उसके उत्तरदायी समय क्वांटम के अतिरिक्त प्रतीक्षा में बदल देती है, तो अनुसूचक निष्पादित करने के लिए तैयार श्रेणी में प्रथम प्रक्रिया का चयन करता है। और समय-साझाकरण के अभाव में, या यदि क्वांटा सामान्य कार्य के आकार पर सापेक्ष उच्च थे, तब यह प्रक्रिया जो बड़ी सामान्य कार्य का उत्पादन करती है, अन्य प्रक्रियाओं के पक्ष में होती है।

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

उदाहरण के लिए, यदि समय स्लॉट 100 मिलीसेकंड है, और कार्य 1 को पूरा होने में कुल 250 एमएस का समय लगता है, तो राउंड-रॉबिन अनुसूचक 100 एमएस के बाद नौकरी को निलंबित कर देता है और अन्य सामान्य कार्य को सीपीयू पर अपना समय देता है।और अन्य सामान्य कार्य में उनकी समान भागीदारी (100 एमएस प्रत्येक) हो जाने के बाद, कार्य 1 को सीपीयू समय का और आवंटन मिलेगा और चक्र दोहराया जाता है। यह प्रक्रिया तब तक प्रयुक्त रहती है जब तक कि कार्य पूर्ण नहीं हो जाता और सीपीयू पर अधिक समय की आवश्यकता नहीं होती है।

  • 'कार्य 1 = 250 एमएस पूरा करने का कुल समय (क्वांटम 100 एमएस)'।
  1. प्रथम आवंटन = 100 एमएस.
  2. द्वतीय आवंटन = 100 एमएस.
  3. तीसरा आवंटन = 100 एमएस लेकिन कार्य 1 50 एमएस के बाद स्व-समाप्त हो जाता है।
  4. कार्य 1 का कुल सीपीयू समय = 250 एमएस

इस प्रकार सेराउंड-रॉबिन शेड्यूलिंग को समझने के लिए आगमन समय के साथ निम्नलिखित तालिका पर विचार करें और 100 एमएस के क्वांटम समय के साथ प्रक्रिया के निष्पादन समय पर विचार करें:

प्रक्रिया नाम आगमन समय समय निष्पादित करें
पी0 0 250
पी1 50 170
पी2 130 75
पी3 190 100
पी4 210 130
पी5 350 50
राउंड रॉबिन शेड्यूलिंग

अन्य दृष्टिकोण इस प्रकार से है कि सभी प्रक्रियाओं को समान संख्या में समय क्वांटा में विभाजित किया जाए ताकि क्वांटम आकार प्रक्रिया के आकार के समानुपाती हो जाये। इसलिए, सभी प्रक्रियाएं ही समय में समाप्त होती हैं।

नेटवर्क पैकेट शेड्यूलिंग

सर्वोत्तम-प्रयास सबसे अच्छा प्रयास पैकेट स्विचिंग और अन्य सांख्यिकीय बहुसंकेतन में, राउंड-रॉबिन शेड्यूलिंग को पहले आओ-पहले भारित उचित श्रेणी के विकल्प के रूप में प्रोयोग किया जा सकता है।

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

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

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

एकाधिक का उपयोग मल्टीपल एक्सेस नेटवर्क में, जहां कई टर्मिनल साझा भौतिक माध्यम से जुड़े होते हैं, राउंड-रॉबिन शेड्यूलिंग टोकन पासिंग चैनल का उपयोग चैनल पहुंच स्कीम जैसे टोकन की रिंग , या मतदान (कंप्यूटर विज्ञान) या संसाधन आरक्षण द्वारा प्रदान की जा सकती है। केंद्रीय नियंत्रण स्टेशन से संसाधन आरक्षण आदि।

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

यह भी देखें

संदर्भ

  1. Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces [Chapter: Scheduling Introduction] (PDF), Arpaci-Dusseau Books
  2. Guowang Miao, Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, ISBN 1107143217, 2016.
  3. Stallings, William (2015). Operating Systems: Internals and Design Principles. Pearson. p. 409. ISBN 978-0-13-380591-8.
  4. Nash, Stacey L. (2022-06-11). "Best scheduling software of 2022". Popular Science (in English). Retrieved 2022-07-07.
  5. 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