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

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

इस विषय पर लैब का काम यहां पाया जा सकता है:

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

अन्य भागों:

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

आप मेरा चैनल पर भी देख सकते हैं तार =)

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

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

कार्यभार संबंधी धारणाएँ

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

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

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

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

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

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

Tटर्नअराउंड=Tसमापन−टैराइवल

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

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

फर्स्ट इन फर्स्ट आउट (फीफो)

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

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

मानों की गणना करके - 10+20+30 और 3 से विभाजित करने पर, हमें औसत प्रोग्राम निष्पादन समय 20 सेकंड के बराबर मिलता है।
आइए अब अपनी धारणाओं को बदलने का प्रयास करें। विशेष रूप से, धारणा 1 और इस प्रकार हम अब यह नहीं मानेंगे कि प्रत्येक कार्य को निष्पादित करने में समान समय लगता है। इस बार फीफो का प्रदर्शन कैसा रहेगा?

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

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

सबसे छोटा काम सबसे पहले

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

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

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

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

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

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

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

मीट्रिक प्रतिक्रिया समय

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

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

Tresponse=Tfirstrun−tarrival

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

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

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

आवेदनपत्र

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

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

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

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

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

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

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

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

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

I/O के साथ मिश्रण

सबसे पहले, आइए धारणा 4 को हटा दें कि प्रक्रिया केवल सीपीयू का उपयोग करती है; स्वाभाविक रूप से, यह मामला नहीं है और प्रक्रियाएं अन्य उपकरणों तक पहुंच सकती हैं।

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

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

इस उदाहरण में हम STCF शेड्यूलर का उपयोग करेंगे। यदि शेड्यूलर पर ए जैसी कोई प्रक्रिया शुरू की जाती है तो वह कैसा व्यवहार करेगा? वह निम्नलिखित कार्य करेगा: पहले वह पूरी तरह से प्रक्रिया ए पर काम करेगा, और फिर प्रक्रिया बी पर।

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

ओरेकल अब नहीं रहा

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

संपूर्ण

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

स्रोत: www.habr.com