O(1) शेड्यूलर
एक O(1ओ(एन) शेड्यूलर (1 शेड्यूलर का उच्चारण O, 1 शेड्यूलर का बड़ा O, या निरंतर समय शेड्यूलर) एक [[कर्नेल (ऑपरेटिंग सिस्टम)]] शेड्यूलिंग (कंप्यूटिंग) डिज़ाइन है जो निरंतर समय के भीतर प्रक्रिया (कंप्यूटिंग) को शेड्यूल कर सकता है, चाहे ऑपरेटिंग सिस्टम पर कितनी भी प्रक्रियाएँ चल रही हों। यह पहले इस्तेमाल किए गए O(n) शेड्यूलर|O(n) शेड्यूलर की तुलना में एक सुधार है, जो इनपुट की मात्रा के आधार पर स्केलिंग (ज्यामिति) के समय में प्रक्रियाओं को शेड्यूल करता है।
वास्तविक समय ऑपरेटिंग सिस्टम के दायरे में, नियतात्मक निष्पादन महत्वपूर्ण है, और एक O(1) अनुसूचक निष्पादन समय पर एक निश्चित ऊपरी सीमा के साथ शेड्यूलिंग सेवाएं प्रदान करने में सक्षम है।
O(1) शेड्यूलर का उपयोग Linux रिलीज़ 2.6.0 से 2.6.22 (2003-2007) में किया गया था, जिस बिंदु पर इसे पूर्णतया निष्पक्ष अनुसूचक द्वारा प्रतिस्थापित कर दिया गया था।
सिंहावलोकन
2003 में कर्नेल 2.6 के रिलीज़ के साथ लिनक्स शेड्यूलर को पूरी तरह से बदल दिया गया था।[1][2] नए शेड्यूलर को O(1) शेड्यूलर कहा गया। O(1) शेड्यूलर द्वारा उपयोग किया जाने वाला एल्गोरिदम निरंतर शेड्यूलिंग समय प्राप्त करने के लिए प्रक्रियाओं के सक्रिय और समाप्त हो चुके सरणियों पर निर्भर करता है। प्रत्येक प्रक्रिया को एक निश्चित समय क्वांटम दिया जाता है, जिसके बाद इसे प्रीएम्प्शन (कंप्यूटिंग) किया जाता है और समाप्त सरणी में ले जाया जाता है। एक बार जब सक्रिय सरणी से सभी कार्य अपना समय समाप्त कर लेते हैं और समाप्त सरणी में चले जाते हैं, तो एक सरणी स्विच होता है। क्योंकि ऐरे को केवल पॉइंटर के माध्यम से एक्सेस किया जाता है, उन्हें स्विच करना दो पॉइंटर्स को स्वैप करने जितना तेज़ है।[3] यह स्विच सक्रिय सरणी को नया खाली समाप्त सरणी बनाता है, जबकि समाप्त सरणी सक्रिय सरणी बन जाती है।
ओ(1) अंकन के बारे में
एक कलन विधि एक इनपुट पर काम करता है, और उस इनपुट का आकार आमतौर पर इसके चलने का समय निर्धारित करता है। बिग ओ अंकन का उपयोग इनपुट की मात्रा के आधार पर एल्गोरिदम के निष्पादन समय की वृद्धि दर को दर्शाने के लिए किया जाता है। उदाहरण के लिए, जैसे-जैसे इनपुट आकार n बढ़ता है, O(n) एल्गोरिदम का चलने का समय रैखिक रूप से बढ़ता है।[4] बिग ओ नोटेशन का चलने का समय#सामान्य कार्यों के आदेश|ओ(एन)।2) एल्गोरिदम द्विघात समय बढ़ाता है। यदि किसी एल्गोरिदम के चलने के समय पर एक स्थिर ऊपरी सीमा स्थापित करना संभव है, तो इसे O(1) माना जाता है (कोई कह सकता है कि यह निरंतर समय में चलता है)। अर्थात्, O(1) एल्गोरिदम को इनपुट के आकार की परवाह किए बिना एक निश्चित समय में पूरा करने की गारंटी दी जाती है।[5]
लिनक्स शेड्यूलर प्रदर्शन में सुधार
Linux 2.6.8.1 शेड्यूलर में कोई भी एल्गोरिदम शामिल नहीं था जो O(1) समय से भी खराब समय में चलता हो।[6] अर्थात्, शेड्यूलर के प्रत्येक भाग को एक निश्चित निश्चित समय के भीतर निष्पादित करने की गारंटी दी जाती है, भले ही सिस्टम पर कितने भी कार्य हों। यह लिनक्स कर्नेल को कार्यों की संख्या बढ़ने पर ओवरहेड लागत में वृद्धि किए बिना बड़ी संख्या में कार्यों को कुशलतापूर्वक संभालने की अनुमति देता है। लिनक्स 2.6.8.1 शेड्यूलर में दो प्रमुख डेटा संरचनाएं हैं जो इसे O(1) समय में अपने कर्तव्यों को पूरा करने की अनुमति देती हैं, और इसका डिज़ाइन उनके चारों ओर घूमता है: रन कतार और प्राथमिकता सरणी।
मुद्दे
इस एल्गोरिदम के साथ मुख्य मुद्दा किसी कार्य को इंटरैक्टिव कंप्यूटिंग या गैर-इंटरैक्टिव के रूप में चिह्नित करने के लिए उपयोग की जाने वाली जटिल अनुमान है। एल्गोरिदम औसत नींद के समय (प्रक्रिया द्वारा इनपुट के इंतजार में बिताया गया समय) का विश्लेषण करके इंटरैक्टिव प्रक्रियाओं की पहचान करने का प्रयास करता है। जो प्रक्रियाएँ लंबे समय तक निष्क्रिय रहती हैं वे संभवतः उपयोगकर्ता इनपुट की प्रतीक्षा कर रही होती हैं, इसलिए शेड्यूलर मानता है कि वे इंटरैक्टिव हैं। शेड्यूलर इंटरैक्टिव कार्यों को प्राथमिकता बोनस देता है (बेहतर थ्रूपुट के लिए) जबकि गैर-इंटरैक्टिव कार्यों को उनकी प्राथमिकताओं को कम करके दंडित करता है। कार्यों की अन्तरक्रियाशीलता निर्धारित करने के लिए सभी गणनाएँ जटिल हैं और संभावित ग़लत अनुमानों के अधीन हैं,[citation needed] एक इंटरैक्टिव प्रक्रिया से गैर-इंटरैक्टिव व्यवहार उत्पन्न करना।
प्रतिस्थापन
2.6.23 (अक्टूबर 2007) में, ओ(1) शेड्यूलर के स्थान पर कम्पलीटली फेयर शेड्यूलर पेश किया गया था। सीएफएस के लेखक इंगो मोल्नार के अनुसार, इसके मूल डिजाइन को एक वाक्य में संक्षेपित किया जा सकता है: सीएफएस मूल रूप से वास्तविक हार्डवेयर पर एक 'आदर्श, सटीक मल्टीटास्किंग सीपीयू' मॉडल करता है।[7]
यह भी देखें
- समय की जटिलता
- ब्रेन बकवास शेड्यूलर (बीएफएस) - सीएफएस और ओ(1) शेड्यूलर के विकल्प के रूप में अगस्त 2009 में लिनक्स कर्नेल के लिए डिज़ाइन किया गया एक प्रोसेस शेड्यूलर
संदर्भ
- ↑ "Introducing the 2.6 Kernel | Linux Journal". www.linuxjournal.com. Retrieved 2019-07-19.
- ↑ Chandandeep Singh Pabla (August 1, 2009). "पूर्णतया निष्पक्ष अनुसूचक". linux journal. Retrieved 2014-09-09.
- ↑ Robert Love. "The Linux Process Scheduler". Retrieved 2014-09-09.
- ↑ dws. "An informal introduction to O(N) notation". Retrieved 2014-09-09.
- ↑ Rob Bell. "A Beginner's Guide to Big O Notation". Retrieved 2014-09-09.
- ↑ Josh Aas. "Understanding the Linux 2.6.8.1 CPU Scheduler" (PDF). GitHub. Retrieved 2014-09-09.
- ↑ <mingo@elte.hu>, Ingo Molnar. "Linux-Kernel Archive: Re: fair clock use in CFS". lkml.iu.edu. Retrieved 2018-08-30.
बाहरी संबंध
- Understanding the Linux 2.6.8.1 CPU Scheduler; Josh Aas, 17 February 2005
- HybridThreads (Hthreads) Archived 2008-05-11 at the Wayback Machine; A HW/SW co-designed POSIX-compatible OS featuring an O(1) scheduler implemented in hardware
- Inside the Linux scheduler; Written by M. Tim Jones, an IBM developerWorks article
- David Mosberger. "A closer look at the Linux O(1) scheduler". HP Research Labs. Archived from the original on 16 March 2012.
| Organization |
| ||||
|---|---|---|---|---|---|
| Technical | |||||
| Adoption |
| ||||
| |||||
