ऑपरेटिंग सिस्टम का परिचय

नमस्कार, हेब्र! मैं आपके ध्यान में एक दिलचस्प साहित्य के लेख-अनुवाद की एक श्रृंखला लाना चाहता हूं - OSTEP। यह लेख यूनिक्स जैसे ऑपरेटिंग सिस्टम के काम पर गहराई से चर्चा करता है, अर्थात्, प्रक्रियाओं के साथ काम करते हैं, विभिन्न शेड्यूलर, मेमोरी, और अन्य समान घटक जो आधुनिक ओएस बनाते हैं। सभी सामग्रियों का मूल आप यहां देख सकते हैं। कृपया ध्यान दें कि अनुवाद अनप्रोफेशनली (काफी स्वतंत्र रूप से) किया गया था, लेकिन मुझे आशा है कि मैंने सामान्य अर्थ को बरकरार रखा।

इस विषय पर प्रयोगशाला का काम यहां पाया जा सकता है:

• मूल
• मूल
• मेरा व्यक्तिगत अनुकूलन

अन्य भागों:

• भाग 1: परिचय
• भाग 2: अमूर्त: प्रक्रिया
• भाग 3: प्रक्रिया एपीआई का परिचय
• भाग 4: अनुसूचक का परिचय
• भाग 5: MLFQ समयबद्धक

और आप टेलीग्राम में मेरे चैनल को देख सकते हैं =)

शेड्यूलर का परिचय

समस्या का सार: एक योजनाकार नीति कैसे विकसित की जाए
बुनियादी अनुसूचक नीति ढांचे को कैसे विकसित किया जाना चाहिए? प्रमुख धारणाएं क्या होनी चाहिए? क्या मैट्रिक्स महत्वपूर्ण हैं? शुरुआती कंप्यूटिंग में कौन सी बुनियादी तकनीकों का उपयोग किया गया था?

काम का बोझ

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

हम सिस्टम में चल रही प्रक्रियाओं के बारे में निम्नलिखित धारणाएँ बनाते हैं, जिन्हें कभी-कभी नौकरी (कार्य) भी कहा जाता है। इनमें से लगभग सभी धारणाएं यथार्थवादी नहीं हैं, लेकिन विचार के विकास के लिए आवश्यक हैं।

1. प्रत्येक कार्य समय की एक ही राशि चलाता है,
2. सभी कार्य एक ही समय पर निर्धारित किए जाते हैं,
3. पूरा होने तक हाथ में काम,
4. सभी कार्य केवल CPU का उपयोग करते हैं,
5. प्रत्येक कार्य का रनिंग टाइम ज्ञात है।

शेड्यूलर मेट्रिक्स

लोड के बारे में कुछ मान्यताओं के अलावा, विभिन्न नियोजन नीतियों: शेड्यूलर मेट्रिक्स की तुलना के लिए अभी भी कुछ टूल की आवश्यकता है। एक मीट्रिक सिर्फ कुछ का एक उपाय है। कई मैट्रिक्स हैं जिनका उपयोग योजनाकारों की तुलना करने के लिए किया जा सकता है।

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

टटर्नअर्शन = तुच्छता - गुणात्मक

चूंकि हमने यह मान लिया था कि सभी कार्य एक ही समय में आते हैं, फिर ता = 0 और इस प्रकार टीटी = टीसी। जब हम उपरोक्त धारणाओं को बदलेंगे तो यह मूल्य स्वाभाविक रूप से बदल जाएगा।

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

सबसे पहले (एफआईएफओ) में पहले

सबसे बुनियादी एल्गोरिथ्म जिसे हम लागू कर सकते हैं, उसे एफआईएफओ कहा जाता है या पहले आओ (इन), पहले सेवा (बाहर) । इस एल्गोरिथ्म के कई फायदे हैं: इसे लागू करना बहुत सरल है और यह हमारी सभी धारणाओं को पूरा करता है, काम को बहुत अच्छा कर रहा है।

एक साधारण उदाहरण पर विचार करें। मान लीजिए कि एक ही समय में 3 कार्य निर्धारित किए गए थे। लेकिन मान लीजिए टास्क ए बाकी सभी की तुलना में थोड़ा पहले आया था, इसलिए यह बी की तुलना में बी की तरह निष्पादन सूची में होगा, सी। के सापेक्ष बी मान लें कि उनमें से प्रत्येक को 10 सेकंड लगते हैं। इन कार्यों को पूरा करने के लिए औसत समय क्या होगा?



मानों की गणना - 10 + 20 + 30 और 3 से विभाजित करके, हमें कार्यक्रम का औसत निष्पादन समय 20 सेकंड के बराबर मिलता है।

अब हम अपनी मान्यताओं को बदलने की कोशिश करते हैं। विशेष रूप से, अनुमान 1, और इस प्रकार अब हम यह नहीं मानेंगे कि प्रत्येक कार्य में समान समय लगता है। इस बार FIFO खुद को कैसे दिखाएगा?

जैसा कि यह पता चला है, कार्यों के विभिन्न निष्पादन समय का फीफो एल्गोरिथ्म की उत्पादकता पर बेहद नकारात्मक प्रभाव पड़ता है। मान लें कि कार्य A को 100 सेकंड के लिए निष्पादित किया जाएगा, जबकि B और C अभी भी 10 प्रत्येक होंगे।



जैसा कि आंकड़े से देखा जा सकता है, सिस्टम का औसत समय (100 + 110 + 120) / 3 = 110 है। इस प्रभाव को काफिला प्रभाव कहा जाता है , जब एक संसाधन के कुछ अल्पकालिक उपभोक्ता भारी उपभोक्ता के बाद कतार में होंगे। यह एक किराने की दुकान की तरह दिखता है जब एक पूर्ण ट्रॉली वाला ग्राहक आपके सामने होता है। समस्या का सबसे अच्छा समाधान कैशियर को बदलने या आराम करने और गहरी सांस लेने की कोशिश करना है।

सबसे छोटी नौकरी पहले

क्या भारी प्रक्रियाओं के साथ किसी तरह की स्थिति को हल करना संभव है? बेशक। एक अन्य प्रकार के शेड्यूलिंग को शॉर्टेस्ट जॉब फर्स्ट (एसजेएफ) कहा जाता है। इसका एल्गोरिथ्म भी काफी आदिम है - जैसा कि नाम से पता चलता है, सबसे छोटे कार्यों को पहले एक के बाद एक लॉन्च किया जाएगा।



इस उदाहरण में, समान प्रक्रियाओं को शुरू करने का परिणाम कार्यक्रमों के औसत बदलाव समय में सुधार होगा और यह 110 के बजाय 50 होगा, जो लगभग 2 गुना बेहतर है।

इस प्रकार, इस धारणा के लिए कि सभी कार्य एक ही समय में आते हैं, एसजेएफ एल्गोरिथ्म सबसे इष्टतम एल्गोरिथ्म लगता है। हालांकि, हमारी धारणाएं अभी भी यथार्थवादी नहीं हैं। इस बार, हम धारणा 2 को बदलते हैं और इस बार कल्पना करते हैं कि कार्य किसी भी समय रह सकते हैं, और सभी एक ही समय में नहीं। इससे क्या समस्याएं हो सकती हैं?



कल्पना कीजिए कि कार्य A (100s) बहुत पहले आता है और निष्पादित होना शुरू होता है। समय पर t = 10, कार्य B, C आते हैं, जिनमें से प्रत्येक में 10 सेकंड लगेंगे। इस प्रकार, औसत निष्पादन का समय (100+ (110-10) + (120-10)) \ 3 = 103 है। स्थिति को सुधारने के लिए योजनाकार क्या कर सकता है?

सबसे कम समय-से-पूरा करने का पहला (STCF)

स्थिति को सुधारने के लिए, हमने धारणा 3 को छोड़ दिया कि कार्यक्रम पूरा होने तक चल रहा है। इसके अलावा, हमें हार्डवेयर समर्थन की आवश्यकता होगी, और जैसा कि आपने अनुमान लगाया होगा, हम एक टाइमर का उपयोग एक काम के कार्य को बाधित करने और संदर्भों को स्विच करने के लिए करेंगे । इस प्रकार, शेड्यूलर B और C के आने के समय के कार्यों में कुछ कर सकता है - कार्य A के निष्पादन को रोक सकता है और कार्य B और C को प्रसंस्करण में लगा सकता है और, समाप्त होने के बाद, प्रक्रिया को जारी रखता है। इस अनुसूचक को STCF या Preemptive Job First कहा जाता है।



इस अनुसूचक का परिणाम यह परिणाम होगा: ((120-0) + (20-10) + (30-10) + / 3 = 50। इस प्रकार, इस तरह के एक अनुसूचक हमारे कार्यों के लिए और भी अधिक इष्टतम हो जाता है।

मीट्रिक रिस्पांस टाइम

इस प्रकार, यदि हम कार्यों के रन समय को जानते हैं और ये कार्य केवल CPU का उपयोग करते हैं, तो STCF सबसे अच्छा समाधान होगा। और शुरुआती दिनों में एक बार, इन एल्गोरिदम ने काम किया और बहुत अच्छी तरह से। हालाँकि, अब उपयोगकर्ता ज्यादातर समय टर्मिनल में बिताता है और उससे उत्पादक इंटरएक्टिव बातचीत की उम्मीद करता है। तो एक नया मीट्रिक पैदा हुआ था - प्रतिक्रिया समय (प्रतिक्रिया)।

प्रतिक्रिया समय की गणना निम्न प्रकार से की जाती है:

ट्रैप्सन = टफस्ट्रून - टारिगुल

इस प्रकार, पिछले उदाहरण के लिए, प्रतिक्रिया समय इस प्रकार होगा: A = 0, B = 0, B = 10 (abg = 3.33)।

और यह पता चला है कि एसटीसीएफ एल्गोरिथ्म एक स्थिति में इतना अच्छा नहीं है जब एक ही समय में 3 कार्य आते हैं - यह तब तक इंतजार करना होगा जब तक कि छोटे कार्य पूरी तरह से पूरा नहीं हो जाते। इस प्रकार, एल्गोरिथ्म टर्नअराउंड समय मीट्रिक के लिए अच्छा है, लेकिन अन्तरक्रियाशीलता मीट्रिक के लिए बुरा है। कल्पना करें कि संपादक में पात्रों को टाइप करने के प्रयास में टर्मिनल पर बैठे, आपको 10 सेकंड से अधिक इंतजार करना होगा, क्योंकि कुछ अन्य कार्य प्रोसेसर द्वारा कब्जा कर लिया गया है। यह बहुत सुखद नहीं है।



इसलिए हमें एक और समस्या का सामना करना पड़ रहा है - हम एक अनुसूचक कैसे बना सकते हैं जो प्रतिक्रिया समय के प्रति संवेदनशील हो?

राउंड रॉबिन

इस समस्या को हल करने के लिए, राउंड रॉबिन (आरआर) एल्गोरिदम विकसित किया गया था। मूल विचार काफी सरल है: कार्यों को पूरा करने के लिए शुरू करने के बजाय, हम समय की एक निश्चित अवधि के लिए कार्य शुरू करेंगे (एक समय क्वांटम कहा जाता है) और फिर कतार से किसी अन्य कार्य पर स्विच करें। एल्गोरिथ्म अपने काम को तब तक दोहराता है जब तक कि सभी कार्य पूरे न हो जाएं। इस स्थिति में, प्रोग्राम चलाने का समय एक से अधिक होना चाहिए जिसके बाद टाइमर प्रक्रिया को बाधित करता है। उदाहरण के लिए, यदि टाइमर हर x = 10ms की प्रक्रिया को बाधित करता है, तो प्रक्रिया निष्पादन विंडो का आकार 10 से अधिक होना चाहिए और 10.20 या x * 10 होना चाहिए।

आइए एक उदाहरण देखें: एबीवी के कार्य प्रणाली में एक साथ आते हैं और उनमें से प्रत्येक 5 सेकंड के लिए काम करना चाहता है। एसजेएफ एल्गोरिथ्म एक दूसरे को शुरू करने से पहले प्रत्येक कार्य को अंत तक पूरा करेगा। इसके विपरीत, लॉन्च विंडो = 1 एस के साथ आरआर एल्गोरिथ्म निम्नानुसार कार्यों से गुजरेंगे (छवि। 4.3)।


(एसजेएफ अगेन (खराब प्रतिक्रिया समय के लिए)


(राउंड रॉबिन (प्रतिक्रिया समय के लिए अच्छा)

एल्गोरिदम के लिए औसत प्रतिक्रिया समय आरआर (0 + 1 + 2) / 3 = 1 है, जबकि एसजेएफ (0 + 5 + 10) / 3 = 5 के लिए।

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

आरआर एक महान योजनाकार है अगर यह केवल एक प्रतिक्रिया समय मीट्रिक था। लेकिन टास्क के टर्नअराउंड समय का मीट्रिक इस एल्गोरिथम के साथ कैसे व्यवहार करेगा? ऊपर दिए गए उदाहरण पर विचार करें, जब ऑपरेटिंग समय ए, बी, सी = 5 एस और एक ही समय में आते हैं। टास्क ए 13 में समाप्त होगा, बी 14 में, सी 15 बजे और औसत बदलाव का समय 14 एस होगा। इस प्रकार, आरआर टर्नओवर मेट्रिक्स के लिए सबसे खराब एल्गोरिदम है।

आम तौर पर, कोई भी एल्गोरिथ्म जैसे आरआर ईमानदार होता है, यह सीपीयू पर खर्च किए गए समय को सभी प्रक्रियाओं के बीच समान रूप से विभाजित करता है। और इस प्रकार, ये मीट्रिक लगातार एक दूसरे के साथ संघर्ष करते हैं।

इस प्रकार, हमारे पास कई विरोधी एल्गोरिदम हैं और एक ही समय में कई धारणाएं बनी हुई हैं - कि कार्य समय ज्ञात है और कार्य केवल CPU का उपयोग करता है।

I / O के साथ मिलाना

सबसे पहले, हम यह धारणा 4 हटाते हैं कि प्रक्रिया केवल सीपीयू का उपयोग करती है, निश्चित रूप से ऐसा नहीं है, और प्रक्रिया अन्य उपकरणों की ओर मुड़ सकती है।

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

कई कार्यों के एक उदाहरण पर विचार करें। उनमें से प्रत्येक को 50ms प्रोसेसर समय की आवश्यकता होती है। हालांकि, पहले वाला प्रत्येक 10ms (जिसे 10ms के लिए भी निष्पादित किया जाएगा) I / O का उपयोग करेगा। और प्रक्रिया B केवल I / O के बिना 50ms प्रोसेसर का उपयोग करता है।



इस उदाहरण में, हम एसटीसीएफ अनुसूचक का उपयोग करेंगे। यदि आप उस पर A जैसी प्रक्रिया चलाते हैं, तो शेड्यूलर कैसे व्यवहार करता है? वह इस प्रकार आगे बढ़ेगा - पहले पूरी तरह से प्रक्रिया ए, और फिर प्रक्रिया बी।



इस समस्या को हल करने के लिए पारंपरिक दृष्टिकोण प्रक्रिया के प्रत्येक 10-एमएस उप-कार्य को एक अलग कार्य के रूप में व्याख्या करना है। इस प्रकार, जब एसटीजेएफ एल्गोरिथ्म के साथ शुरू होता है, तो 50 एमएस कार्य और 10 एमएस कार्य के बीच का विकल्प स्पष्ट होता है। फिर, जब सबकास्क ए पूरा हो जाता है, तो बी और आई / ओ की प्रक्रिया शुरू कर दी जाएगी। I / O पूरा होने के बाद, यह प्रक्रिया B. के बजाय 10-ms प्रक्रिया को फिर से शुरू करने के लिए प्रथागत होगा। इस प्रकार, जब सीपीयू किसी अन्य प्रक्रिया द्वारा उपयोग किया जाता है, तो यह ओवरलैप का एहसास करना संभव है, जबकि पहला I / O का इंतजार कर रहा है। और परिणामस्वरूप, सिस्टम का बेहतर उपयोग किया जाता है - उस समय जब इंटरैक्टिव प्रक्रिया I / O की प्रतीक्षा कर रहे हैं, प्रोसेसर पर अन्य प्रक्रियाओं को निष्पादित किया जा सकता है।

ओरेकल नहीं है

अब आइए इस धारणा से छुटकारा पाने की कोशिश करें कि कार्य का समय ज्ञात है। यह आम तौर पर पूरी सूची से सबसे खराब और सबसे अवास्तविक धारणा है। वास्तव में, औसत मानक ओएस में, ओएस आमतौर पर कार्यों को पूरा करने में लगने वाले समय के बारे में आमतौर पर बहुत कम जानता है, इसलिए आप यह जानने के बिना एक अनुसूचक का निर्माण कैसे कर सकते हैं कि कार्य कितना समय लेगा? शायद हम इस समस्या को हल करने के लिए आरआर के कुछ सिद्धांतों का उपयोग कर सकते हैं?

परिणाम

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