O(1) शेड्यूलर: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Historical Linux 2.6 kernel process scheduler}} thumb|[[लिनक्स कर्नेल की...")
 
(text)
Line 1: Line 1:
{{Short description|Historical Linux 2.6 kernel process scheduler}}
{{Short description|Historical Linux 2.6 kernel process scheduler}}
[[File:Simplified_Structure_of_the_Linux_Kernel.svg|thumb|[[लिनक्स कर्नेल]] की सरलीकृत संरचना में O(1) शेड्यूलर (एक प्रक्रिया शेड्यूलर) का स्थान।]]एक O(1[[ओ(एन) शेड्यूलर]] (1 शेड्यूलर का उच्चारण O, 1 शेड्यूलर का बड़ा O, या निरंतर समय शेड्यूलर) एक [[कर्नेल ([[ऑपरेटिंग सिस्टम]])]] [[शेड्यूलिंग (कंप्यूटिंग)]] डिज़ाइन है जो निरंतर समय के भीतर [[प्रक्रिया (कंप्यूटिंग)]] को शेड्यूल कर सकता है, चाहे ऑपरेटिंग सिस्टम पर कितनी भी प्रक्रियाएँ चल रही हों। यह पहले इस्तेमाल किए गए O(n) शेड्यूलर|O(n) शेड्यूलर की तुलना में एक सुधार है, जो इनपुट की मात्रा के आधार पर [[स्केलिंग (ज्यामिति)]] के समय में प्रक्रियाओं को शेड्यूल करता है।
[[File:Simplified_Structure_of_the_Linux_Kernel.svg|thumb|[[लिनक्स कर्नेल]] की सरलीकृत संरचना में O(1) शेड्यूलर (एक प्रक्रिया शेड्यूलर) का स्थान।]]एक '''O(1) शेड्यूलर''' (1 शेड्यूलर का उच्चारण O, 1 शेड्यूलर का बड़ा O, या निरंतर समय शेड्यूलर) एक [[कर्नेल ([[ऑपरेटिंग सिस्टम]])]] [[शेड्यूलिंग (कंप्यूटिंग)]] अभिकल्पना है जो निरंतर समय के भीतर [[प्रक्रिया (कंप्यूटिंग)|प्रोसेसेज (कंप्यूटिंग)]] को नियोजित कर सकता है, चाहे ऑपरेटिंग सिस्टम पर कितनी भी प्रक्रियाएँ चल रही हों। यह पहले इस्तेमाल किए गए O(n) शेड्यूलर की तुलना में एक सुधार है, जो इनपुट की मात्रा के आधार पर [[स्केलिंग (ज्यामिति)]] के समय में प्रक्रियाओं को नियोजित करता है।


[[वास्तविक समय ऑपरेटिंग सिस्टम]] के दायरे में, नियतात्मक निष्पादन महत्वपूर्ण है, और एक O(1) अनुसूचक निष्पादन समय पर एक निश्चित ऊपरी सीमा के साथ शेड्यूलिंग सेवाएं प्रदान करने में सक्षम है।
[[वास्तविक समय ऑपरेटिंग सिस्टम|रियल-टाइम ऑपरेटिंग सिस्टम]] के क्षेत्र में, नियतात्मक निष्पादन महत्वपूर्ण है, और एक O(1) अनुसूचक निष्पादन समय पर एक निश्चित ऊपरी सीमा के साथ अनुसूचीयन सेवाएं प्रदान करने में सक्षम है।


O(1) शेड्यूलर का उपयोग Linux रिलीज़ 2.6.0 से 2.6.22 (2003-2007) में किया गया था, जिस बिंदु पर इसे [[ पूर्णतया निष्पक्ष अनुसूचक ]] द्वारा प्रतिस्थापित कर दिया गया था।
O(1) शेड्यूलर का उपयोग लिनक्स विमोचन 2.6.0 से 2.6.22 (2003-2007) में किया गया था, जिस बिंदु पर इसे [[ पूर्णतया निष्पक्ष अनुसूचक ]]द्वारा प्रतिस्थापित कर दिया गया था।


== सिंहावलोकन ==
== समीक्षा ==
2003 में कर्नेल 2.6 के रिलीज़ के साथ लिनक्स शेड्यूलर को पूरी तरह से बदल दिया गया था।<ref>{{Cite web|url=https://www.linuxjournal.com/article/6530|title=Introducing the 2.6 Kernel {{!}} Linux Journal|website=www.linuxjournal.com|access-date=2019-07-19}}</ref><ref>{{cite web|url=http://www.linuxjournal.com/magazine/completely-fair-scheduler|title=पूर्णतया निष्पक्ष अनुसूचक|author=Chandandeep Singh Pabla|date=August 1, 2009|website=linux journal|access-date=2014-09-09}}</ref> नए शेड्यूलर को O(1) शेड्यूलर कहा गया। O(1) शेड्यूलर द्वारा उपयोग किया जाने वाला एल्गोरिदम निरंतर शेड्यूलिंग समय प्राप्त करने के लिए प्रक्रियाओं के सक्रिय और समाप्त हो चुके सरणियों पर निर्भर करता है। प्रत्येक प्रक्रिया को एक निश्चित समय क्वांटम दिया जाता है, जिसके बाद इसे प्रीएम्प्शन (कंप्यूटिंग) किया जाता है और समाप्त सरणी में ले जाया जाता है। एक बार जब सक्रिय सरणी से सभी कार्य अपना समय समाप्त कर लेते हैं और समाप्त सरणी में चले जाते हैं, तो एक सरणी स्विच होता है। क्योंकि ऐरे को केवल पॉइंटर के माध्यम से एक्सेस किया जाता है, उन्हें स्विच करना दो पॉइंटर्स को स्वैप करने जितना तेज़ है।<ref>{{cite web
2003 में कर्नेल 2.6 के विमोचन के साथ लिनक्स शेड्यूलर को पूरी तरह से बदल दिया गया था। <ref>{{Cite web|url=https://www.linuxjournal.com/article/6530|title=Introducing the 2.6 Kernel {{!}} Linux Journal|website=www.linuxjournal.com|access-date=2019-07-19}}</ref><ref>{{cite web|url=http://www.linuxjournal.com/magazine/completely-fair-scheduler|title=पूर्णतया निष्पक्ष अनुसूचक|author=Chandandeep Singh Pabla|date=August 1, 2009|website=linux journal|access-date=2014-09-09}}</ref> नए शेड्यूलर को O(1) शेड्यूलर कहा गया। O(1) शेड्यूलर द्वारा उपयोग किया जाने वाला कलन विधि निरंतर शेड्यूलिंग समय प्राप्त करने के लिए प्रक्रियाओं के सक्रिय और समाप्त हो चुके सरणियों पर निर्भर करता है। प्रत्येक प्रक्रिया को एक निश्चित समय परिमाण दिया जाता है, जिसके बाद इसे प्रीएम्प्शन (कंप्यूटिंग) किया जाता है और समाप्त सरणी में ले जाया जाता है। एक बार जब सक्रिय सरणी से सभी कार्य अपना समय समाप्त कर लेते हैं और समाप्त सरणी में चले जाते हैं, तो एक सरणी स्थानांतरित होता है। क्योंकि ऐरे को केवल पॉइंटर के माध्यम से एक्सेस किया जाता है, उन्हें स्थानांतरित करना दो पॉइंटर्स को विनिमय करने जितना तीव्र है। <ref>{{cite web
|author = Robert Love
|author = Robert Love
|url = http://www.informit.com/articles/article.aspx?p=101760&seqNum=2
|url = http://www.informit.com/articles/article.aspx?p=101760&seqNum=2
|title = The Linux Process Scheduler
|title = The Linux Process Scheduler
|access-date = 2014-09-09
|access-date = 2014-09-09
}}</ref> यह स्विच सक्रिय सरणी को नया खाली समाप्त सरणी बनाता है, जबकि समाप्त सरणी सक्रिय सरणी बन जाती है।
}}</ref> यह स्थानांतरित सक्रिय सरणी को नया खाली समाप्त सरणी बनाता है, जबकि समाप्त सरणी सक्रिय सरणी बन जाती है।


==ओ(1) अंकन के बारे में ==
==ओ(1) अंकन के बारे में ==
{{Main|Big O notation}}
{{Main|बिग O संकेत पद्धति }}
एक [[कलन विधि]] एक इनपुट पर काम करता है, और उस इनपुट का आकार आमतौर पर इसके चलने का समय निर्धारित करता है। [[ बिग ओ अंकन ]] का उपयोग इनपुट की मात्रा के आधार पर एल्गोरिदम के निष्पादन समय की वृद्धि दर को दर्शाने के लिए किया जाता है। उदाहरण के लिए, जैसे-जैसे इनपुट आकार n बढ़ता है, O(n) एल्गोरिदम का चलने का समय रैखिक रूप से बढ़ता है।<ref>{{cite web
 
[[कलन विधि]] एक इनपुट पर काम करता है, और उस इनपुट का आकार सामान्यतः इसके चलने का समय निर्धारित करता है। [[ बिग ओ अंकन ]] का उपयोग इनपुट की मात्रा के आधार पर कलन विधि के निष्पादन समय की वृद्धि दर को दर्शाने के लिए किया जाता है। उदाहरण के लिए, जैसे-जैसे इनपुट आकार n बढ़ता है, O(n) कलन विधि का चलने का समय रैखिक रूप से बढ़ता है। <ref>{{cite web
|author = dws
|author = dws
|url = http://www.perlmonks.org/?node_id=227909
|url = http://www.perlmonks.org/?node_id=227909
|title = An informal introduction to O(N) notation
|title = An informal introduction to O(N) notation
|access-date = 2014-09-09
|access-date = 2014-09-09
}}</ref> बिग ओ नोटेशन का चलने का समय#सामान्य कार्यों के आदेश|ओ(एन)।{{sup|2}}) एल्गोरिदम [[द्विघात समय]] बढ़ाता है। यदि किसी एल्गोरिदम के चलने के समय पर एक स्थिर ऊपरी सीमा स्थापित करना संभव है, तो इसे O(1) माना जाता है (कोई कह सकता है कि यह निरंतर समय में चलता है)। अर्थात्, O(1) एल्गोरिदम को इनपुट के आकार की परवाह किए बिना एक निश्चित समय में पूरा करने की गारंटी दी जाती है।<ref>{{cite web
}}</ref> बिग O नोटेशन का चलने का समय O(N)।{{sup|2}}) कलन विधि [[द्विघात समय]] बढ़ाता है। यदि किसी कलन विधि के चलने के समय पर एक स्थिर ऊपरी सीमा स्थापित करना संभव है, तो इसे O(1) माना जाता है (कोई कह सकता है कि यह निरंतर समय में चलता है)। अर्थात्, O(1) कलन विधि को इनपुट के आकार की चिंता किए बिना एक निश्चित समय में पूरा करने की प्रत्याभुति दी जाती है। <ref>{{cite web
|author = Rob Bell
|author = Rob Bell
|url = http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
|url = http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
Line 30: Line 31:


== लिनक्स शेड्यूलर प्रदर्शन में सुधार ==
== लिनक्स शेड्यूलर प्रदर्शन में सुधार ==
Linux 2.6.8.1 शेड्यूलर में कोई भी एल्गोरिदम शामिल नहीं था जो O(1) समय से भी खराब समय में चलता हो।<ref>{{cite web
लिनक्स 2.6.8.1 शेड्यूलर में कोई भी कलन विधि सम्मिलित नहीं था जो O(1) समय से भी खराब समय में चलता हो। <ref>{{cite web
|author = Josh Aas
|author = Josh Aas
|url = https://github.com/bdaehlie/linux-cpu-scheduler-docs/blob/master/linux_cpu_scheduler.pdf
|url = https://github.com/bdaehlie/linux-cpu-scheduler-docs/blob/master/linux_cpu_scheduler.pdf
Line 36: Line 37:
|website = [[GitHub]]
|website = [[GitHub]]
|access-date = 2014-09-09
|access-date = 2014-09-09
}}</ref> अर्थात्, शेड्यूलर के प्रत्येक भाग को एक निश्चित निश्चित समय के भीतर निष्पादित करने की गारंटी दी जाती है, भले ही सिस्टम पर कितने भी कार्य हों। यह लिनक्स कर्नेल को कार्यों की संख्या बढ़ने पर ओवरहेड लागत में वृद्धि किए बिना बड़ी संख्या में कार्यों को कुशलतापूर्वक संभालने की अनुमति देता है। लिनक्स 2.6.8.1 शेड्यूलर में दो प्रमुख डेटा संरचनाएं हैं जो इसे O(1) समय में अपने कर्तव्यों को पूरा करने की अनुमति देती हैं, और इसका डिज़ाइन उनके चारों ओर घूमता है: रन कतार और प्राथमिकता सरणी।
}}</ref> अर्थात्, शेड्यूलर के प्रत्येक भाग को एक निश्चित निश्चित समय के भीतर निष्पादित करने की प्रत्याभुति दी जाती है, भले ही सिस्टम पर कितने भी कार्य हों। यह लिनक्स कर्नेल को कार्यों की संख्या बढ़ने पर ओवरहेड लागत में वृद्धि किए बिना बड़ी संख्या में कार्यों को कुशलतापूर्वक संभालने की अनुमति देता है। लिनक्स 2.6.8.1 शेड्यूलर में दो प्रमुख डेटा संरचनाएं हैं जो इसे O(1) समय में अपने कर्तव्यों को पूरा करने की अनुमति देती हैं, और इसका अभिकल्पना उनके चारों ओर घूमता है: रन कतार और प्राथमिकता सरणी।


== मुद्दे ==
== स्तिथि ==
इस एल्गोरिदम के साथ मुख्य मुद्दा किसी कार्य को [[इंटरैक्टिव कंप्यूटिंग]] या गैर-इंटरैक्टिव के रूप में चिह्नित करने के लिए उपयोग की जाने वाली जटिल अनुमान है। एल्गोरिदम औसत नींद के समय (प्रक्रिया द्वारा इनपुट के इंतजार में बिताया गया समय) का विश्लेषण करके इंटरैक्टिव प्रक्रियाओं की पहचान करने का प्रयास करता है। जो प्रक्रियाएँ लंबे समय तक निष्क्रिय रहती हैं वे संभवतः उपयोगकर्ता इनपुट की प्रतीक्षा कर रही होती हैं, इसलिए शेड्यूलर मानता है कि वे इंटरैक्टिव हैं। शेड्यूलर इंटरैक्टिव कार्यों को प्राथमिकता बोनस देता है (बेहतर थ्रूपुट के लिए) जबकि गैर-इंटरैक्टिव कार्यों को उनकी प्राथमिकताओं को कम करके दंडित करता है। कार्यों की अन्तरक्रियाशीलता निर्धारित करने के लिए सभी गणनाएँ जटिल हैं और संभावित ग़लत अनुमानों के अधीन हैं,{{citation needed|date=July 2016}} एक इंटरैक्टिव प्रक्रिया से गैर-इंटरैक्टिव व्यवहार उत्पन्न करना।
इस कलन विधि के साथ मुख्य स्तिथि किसी कार्य को [[इंटरैक्टिव कंप्यूटिंग]] या गैर-इंटरैक्टिव के रूप में चिह्नित करने के लिए उपयोग की जाने वाली जटिल अनुमान है। कलन विधि औसत नींद के समय (प्रक्रिया द्वारा इनपुट के इंतजार में बिताया गया समय) का विश्लेषण करके इंटरैक्टिव प्रक्रियाओं की पहचान करने का प्रयास करता है। जो प्रक्रियाएँ लंबे समय तक निष्क्रिय रहती हैं वे संभवतः उपयोगकर्ता इनपुट की प्रतीक्षा कर रही होती हैं, इसलिए शेड्यूलर मानता है कि वे इंटरैक्टिव हैं। शेड्यूलर इंटरैक्टिव कार्यों को प्राथमिकता बोनस देता है (बेहतर थ्रूपुट के लिए) जबकि गैर-इंटरैक्टिव कार्यों को उनकी प्राथमिकताओं को कम करके दंडित करता है। कार्यों की अन्तरक्रियाशीलता निर्धारित करने के लिए सभी गणनाएँ जटिल हैं और संभावित ग़लत अनुमानों के अधीन हैं, एक इंटरैक्टिव प्रक्रिया से गैर-इंटरैक्टिव व्यवहार उत्पन्न करना।


== प्रतिस्थापन ==
== प्रतिस्थापन ==
2.6.23 (अक्टूबर 2007) में, ओ(1) शेड्यूलर के स्थान पर कम्पलीटली फेयर शेड्यूलर पेश किया गया था। सीएफएस के लेखक इंगो मोल्नार के अनुसार, इसके मूल डिजाइन को एक वाक्य में संक्षेपित किया जा सकता है: सीएफएस मूल रूप से वास्तविक हार्डवेयर पर एक 'आदर्श, सटीक मल्टीटास्किंग सीपीयू' मॉडल करता है।<ref>{{Cite web|url=http://lkml.iu.edu/hypermail/linux/kernel/0705.1/3017.html|title=Linux-Kernel Archive: Re: fair clock use in CFS|last=<mingo@elte.hu>|first=Ingo Molnar|website=lkml.iu.edu|access-date=2018-08-30}}</ref>
2.6.23 (अक्टूबर 2007) में, ओ(1) शेड्यूलर के स्थान पर कम्पलीटली फेयर शेड्यूलर प्रस्तुत किया गया था। सीएफएस के लेखक इंगो मोल्नार के अनुसार, इसके मूल अभिकल्पना को एक वाक्य में संक्षेपित किया जा सकता है: सीएफएस मूल रूप से वास्तविक हार्डवेयर पर एक 'आदर्श, सटीक मल्टीटास्किंग सीपीयू' प्रतिरूप करता है।<ref>{{Cite web|url=http://lkml.iu.edu/hypermail/linux/kernel/0705.1/3017.html|title=Linux-Kernel Archive: Re: fair clock use in CFS|last=<mingo@elte.hu>|first=Ingo Molnar|website=lkml.iu.edu|access-date=2018-08-30}}</ref>




Line 48: Line 49:
{{Portal|Linux}}
{{Portal|Linux}}
*[[समय की जटिलता]]
*[[समय की जटिलता]]
*[[ब्रेन बकवास शेड्यूलर]] (बीएफएस) - सीएफएस और ओ(1) शेड्यूलर के विकल्प के रूप में अगस्त 2009 में लिनक्स कर्नेल के लिए डिज़ाइन किया गया एक प्रोसेस शेड्यूलर
*[[ब्रेन बकवास शेड्यूलर]] (बीएफएस) - सीएफएस और ओ(1) शेड्यूलर के विकल्प के रूप में अगस्त 2009 में लिनक्स कर्नेल के लिए अभिकल्पना किया गया एक प्रोसेस शेड्यूलर


==संदर्भ==
==संदर्भ==
Line 55: Line 56:


== बाहरी संबंध ==
== बाहरी संबंध ==
* [https://web.archive.org/web/20131230235336/http://joshaas.net/linux/ Understanding the Linux 2.6.8.1 CPU Scheduler]; Josh Aas, 17 February 2005
* [https://web.archive.org/web/20131230235336/http://joshaas.net/linux/ Understanding the लिनक्स 2.6.8.1 CPU Scheduler]; Josh Aas, 17 February 2005
* [http://www.ittc.ku.edu/hybridthreads HybridThreads (Hthreads)] {{Webarchive|url=https://web.archive.org/web/20080511154918/http://www.ittc.ku.edu/hybridthreads |date=2008-05-11 }}; A HW/SW co-designed POSIX-compatible OS featuring an O(1) scheduler implemented in hardware
* [http://www.ittc.ku.edu/hybridthreads HybridThreads (Hthreads)] {{Webarchive|url=https://web.archive.org/web/20080511154918/http://www.ittc.ku.edu/hybridthreads |date=2008-05-11 }}; A HW/SW co-designed POSIX-compatible OS featuring an O(1) scheduler implemented in hardware
* [https://www.ibm.com/developerworks/library/l-scheduler/index.html Inside the Linux scheduler]; Written by M. Tim Jones, an IBM developerWorks article
* [https://www.ibm.com/developerworks/library/l-scheduler/index.html Inside the लिनक्स scheduler]; Written by M. Tim Jones, an IBM developerWorks article
* {{cite web |author=David Mosberger |title=A closer look at the Linux O(1) scheduler |publisher=HP Research Labs |url=http://www.hpl.hp.com/research/linux/kernel/o1.php |archive-url=https://web.archive.org/web/20120316072525/http://www.hpl.hp.com/research/linux/kernel/o1.php |archive-date=16 March 2012 }}
* {{cite web |author=David Mosberger |title=A closer look at the Linux O(1) scheduler |publisher=HP Research Labs |url=http://www.hpl.hp.com/research/linux/kernel/o1.php |archive-url=https://web.archive.org/web/20120316072525/http://www.hpl.hp.com/research/linux/kernel/o1.php |archive-date=16 March 2012 }}


Revision as of 00:30, 17 July 2023

लिनक्स कर्नेल की सरलीकृत संरचना में O(1) शेड्यूलर (एक प्रक्रिया शेड्यूलर) का स्थान।

एक O(1) शेड्यूलर (1 शेड्यूलर का उच्चारण O, 1 शेड्यूलर का बड़ा O, या निरंतर समय शेड्यूलर) एक [[कर्नेल (ऑपरेटिंग सिस्टम)]] शेड्यूलिंग (कंप्यूटिंग) अभिकल्पना है जो निरंतर समय के भीतर प्रोसेसेज (कंप्यूटिंग) को नियोजित कर सकता है, चाहे ऑपरेटिंग सिस्टम पर कितनी भी प्रक्रियाएँ चल रही हों। यह पहले इस्तेमाल किए गए O(n) शेड्यूलर की तुलना में एक सुधार है, जो इनपुट की मात्रा के आधार पर स्केलिंग (ज्यामिति) के समय में प्रक्रियाओं को नियोजित करता है।

रियल-टाइम ऑपरेटिंग सिस्टम के क्षेत्र में, नियतात्मक निष्पादन महत्वपूर्ण है, और एक O(1) अनुसूचक निष्पादन समय पर एक निश्चित ऊपरी सीमा के साथ अनुसूचीयन सेवाएं प्रदान करने में सक्षम है।

O(1) शेड्यूलर का उपयोग लिनक्स विमोचन 2.6.0 से 2.6.22 (2003-2007) में किया गया था, जिस बिंदु पर इसे पूर्णतया निष्पक्ष अनुसूचक द्वारा प्रतिस्थापित कर दिया गया था।

समीक्षा

2003 में कर्नेल 2.6 के विमोचन के साथ लिनक्स शेड्यूलर को पूरी तरह से बदल दिया गया था। [1][2] नए शेड्यूलर को O(1) शेड्यूलर कहा गया। O(1) शेड्यूलर द्वारा उपयोग किया जाने वाला कलन विधि निरंतर शेड्यूलिंग समय प्राप्त करने के लिए प्रक्रियाओं के सक्रिय और समाप्त हो चुके सरणियों पर निर्भर करता है। प्रत्येक प्रक्रिया को एक निश्चित समय परिमाण दिया जाता है, जिसके बाद इसे प्रीएम्प्शन (कंप्यूटिंग) किया जाता है और समाप्त सरणी में ले जाया जाता है। एक बार जब सक्रिय सरणी से सभी कार्य अपना समय समाप्त कर लेते हैं और समाप्त सरणी में चले जाते हैं, तो एक सरणी स्थानांतरित होता है। क्योंकि ऐरे को केवल पॉइंटर के माध्यम से एक्सेस किया जाता है, उन्हें स्थानांतरित करना दो पॉइंटर्स को विनिमय करने जितना तीव्र है। [3] यह स्थानांतरित सक्रिय सरणी को नया खाली समाप्त सरणी बनाता है, जबकि समाप्त सरणी सक्रिय सरणी बन जाती है।

ओ(1) अंकन के बारे में

Main article: बिग O संकेत पद्धति

कलन विधि एक इनपुट पर काम करता है, और उस इनपुट का आकार सामान्यतः इसके चलने का समय निर्धारित करता है। बिग ओ अंकन का उपयोग इनपुट की मात्रा के आधार पर कलन विधि के निष्पादन समय की वृद्धि दर को दर्शाने के लिए किया जाता है। उदाहरण के लिए, जैसे-जैसे इनपुट आकार n बढ़ता है, O(n) कलन विधि का चलने का समय रैखिक रूप से बढ़ता है। [4] बिग O नोटेशन का चलने का समय O(N)।2) कलन विधि द्विघात समय बढ़ाता है। यदि किसी कलन विधि के चलने के समय पर एक स्थिर ऊपरी सीमा स्थापित करना संभव है, तो इसे O(1) माना जाता है (कोई कह सकता है कि यह निरंतर समय में चलता है)। अर्थात्, O(1) कलन विधि को इनपुट के आकार की चिंता किए बिना एक निश्चित समय में पूरा करने की प्रत्याभुति दी जाती है। [5]


लिनक्स शेड्यूलर प्रदर्शन में सुधार

लिनक्स 2.6.8.1 शेड्यूलर में कोई भी कलन विधि सम्मिलित नहीं था जो O(1) समय से भी खराब समय में चलता हो। [6] अर्थात्, शेड्यूलर के प्रत्येक भाग को एक निश्चित निश्चित समय के भीतर निष्पादित करने की प्रत्याभुति दी जाती है, भले ही सिस्टम पर कितने भी कार्य हों। यह लिनक्स कर्नेल को कार्यों की संख्या बढ़ने पर ओवरहेड लागत में वृद्धि किए बिना बड़ी संख्या में कार्यों को कुशलतापूर्वक संभालने की अनुमति देता है। लिनक्स 2.6.8.1 शेड्यूलर में दो प्रमुख डेटा संरचनाएं हैं जो इसे O(1) समय में अपने कर्तव्यों को पूरा करने की अनुमति देती हैं, और इसका अभिकल्पना उनके चारों ओर घूमता है: रन कतार और प्राथमिकता सरणी।

स्तिथि

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

प्रतिस्थापन

2.6.23 (अक्टूबर 2007) में, ओ(1) शेड्यूलर के स्थान पर कम्पलीटली फेयर शेड्यूलर प्रस्तुत किया गया था। सीएफएस के लेखक इंगो मोल्नार के अनुसार, इसके मूल अभिकल्पना को एक वाक्य में संक्षेपित किया जा सकता है: सीएफएस मूल रूप से वास्तविक हार्डवेयर पर एक 'आदर्श, सटीक मल्टीटास्किंग सीपीयू' प्रतिरूप करता है।[7]


यह भी देखें

संदर्भ

  1. ↑ "Introducing the 2.6 Kernel | Linux Journal". www.linuxjournal.com. Retrieved 2019-07-19.
  2. ↑ Chandandeep Singh Pabla (August 1, 2009). "पूर्णतया निष्पक्ष अनुसूचक". linux journal. Retrieved 2014-09-09.
  3. ↑ Robert Love. "The Linux Process Scheduler". Retrieved 2014-09-09.
  4. ↑ dws. "An informal introduction to O(N) notation". Retrieved 2014-09-09.
  5. ↑ Rob Bell. "A Beginner's Guide to Big O Notation". Retrieved 2014-09-09.
  6. ↑ Josh Aas. "Understanding the Linux 2.6.8.1 CPU Scheduler" (PDF). GitHub. Retrieved 2014-09-09.
  7. ↑ <mingo@elte.hu>, Ingo Molnar. "Linux-Kernel Archive: Re: fair clock use in CFS". lkml.iu.edu. Retrieved 2018-08-30.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=O(1)_शेड्यूलर&oldid=227432’