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) अंकन के बारे में
कलन विधि एक इनपुट पर काम करता है, और उस इनपुट का आकार सामान्यतः इसके चलने का समय निर्धारित करता है। बिग ओ अंकन का उपयोग इनपुट की मात्रा के आधार पर कलन विधि के निष्पादन समय की वृद्धि दर को दर्शाने के लिए किया जाता है। उदाहरण के लिए, जैसे-जैसे इनपुट आकार 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) शेड्यूलर के विकल्प के रूप में अगस्त 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.
बाहरी संबंध
- लिनक्स 2.6.8.1 सीपीयू शेड्यूलर को समझना; जोश आस, 17 फरवरी 2005
- हाइब्रिडथ्रेड्स (एचथ्रेड्स) 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 लिनक्स 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 |
| ||||
| |||||
