अपरेटिङ सिस्टम को परिचय

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

यस विषयमा प्रयोगशाला काम यहाँ फेला पार्न सकिन्छ:

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

अन्य भागहरू:

• भाग १: परिचय
• भाग २: सार: प्रक्रिया
• भाग ३: प्रक्रिया API को परिचय
• भाग ४: अनुसूचीकर्ताको परिचय

तपाईं मेरो च्यानल मा पनि जाँच गर्न सक्नुहुन्छ टेलीग्राम =)

अनुसूचक को परिचय

समस्याको सार: अनुसूचक नीति कसरी विकास गर्ने
अन्तर्निहित अनुसूचक नीति ढाँचाहरू कसरी डिजाइन गर्नुपर्छ? मुख्य मान्यताहरू के हुनुपर्छ? कुन मेट्रिकहरू महत्त्वपूर्ण छन्? प्रारम्भिक कम्प्युटिङ प्रणालीहरूमा कुन आधारभूत प्रविधिहरू प्रयोग गरिन्थ्यो?

कार्यभार अनुमानहरू

सम्भावित नीतिहरू छलफल गर्नु अघि, पहिले प्रणालीमा चल्ने प्रक्रियाहरूको बारेमा केही सरलीकरण गर्ने विषयहरू बनाउनुहोस्, जसलाई सामूहिक रूपमा भनिन्छ। कामको बोझ। कार्यभार परिभाषित गर्नु नीति निर्माणको एक महत्वपूर्ण भाग हो, र तपाईले कार्यभारको बारेमा जति धेरै जान्नुहुन्छ, तपाईले लेख्न सक्नुहुने राम्रो नीति।

प्रणालीमा चलिरहेको प्रक्रियाहरूको बारेमा निम्न धारणाहरू बनाउनुहोस्, कहिलेकाहीँ पनि भनिन्छ जब (कार्यहरू)। प्रायः यी सबै धारणाहरू यथार्थपरक छैनन्, तर विचारको विकासको लागि आवश्यक छन्।

1. प्रत्येक कार्य समान समयको लागि चल्छ,
2. सबै कार्यहरू एकै साथ सेट गरिएका छन्,
3. तोकिएको कार्य पूरा नभएसम्म काम गर्दछ,
4. सबै कार्यहरूले मात्र CPU प्रयोग गर्दछ,
5. प्रत्येक कार्यको चलिरहेको समय थाहा छ।

अनुसूची मेट्रिक्स

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

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

Tturnaround=Tcompletion-Tarrival

हामीले सबै कार्यहरू एकै समयमा आइपुगेको अनुमान गरेपछि Ta=0 र यसरी Tt=Tc। जब हामीले माथिको मान्यताहरू परिवर्तन गर्छौं तब यो मान स्वाभाविक रूपमा परिवर्तन हुनेछ।

अर्को मेट्रिक - निष्पक्षता (निष्पक्षता, इमानदारी)। उत्पादकता र निष्पक्षता प्रायः योजनामा ​​विरोधी विशेषताहरू हुन्। उदाहरणका लागि, अनुसूचकले कार्यसम्पादनलाई अप्टिमाइज गर्न सक्छ, तर अन्य कार्यहरू चल्नको लागि पर्खने लागतमा, यसरी निष्पक्षता घटाउँछ।

फर्स्ट इन फर्स्ट आउट (FIFO)

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

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

मानहरू गणना गरेर - 10+20+30 र 3 द्वारा विभाजन गर्दा, हामीले 20 सेकेन्ड बराबरको औसत कार्यक्रम कार्यान्वयन समय पाउँछौं।
अब हामी हाम्रो धारणा परिवर्तन गर्ने प्रयास गरौं। विशेष गरी, अनुमान १ र यसरी हामी अब प्रत्येक कार्य कार्यान्वयन गर्न समयको समान मात्रा लिन्छ भनेर मान्न सक्दैनौं। यसपटक फिफोले कस्तो प्रदर्शन गर्छ ?

यो बाहिर जान्छ, विभिन्न कार्य कार्यान्वयन समय FIFO एल्गोरिथ्म को उत्पादकता मा एक अत्यन्त नकारात्मक प्रभाव छ। मानौं कि कार्य A ले पूरा हुन १०० सेकेन्ड लिनेछ, जबकि B र C ले अझै पनि प्रत्येक १० सेकेन्ड लिनेछ।

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

सबैभन्दा छोटो काम पहिलो

के यो सम्भव छ कि हेवीवेट प्रक्रियाहरूसँग समान स्थिति समाधान गर्न? पक्कै पनि। अर्को प्रकारको योजना भनिन्छसबैभन्दा छोटो काम पहिलो (SJF)। यसको एल्गोरिथ्म पनि एकदम आदिम छ - नामले संकेत गरे जस्तै, सबैभन्दा छोटो कार्यहरू एक पछि अर्को सुरु गरिनेछ।

यस उदाहरणमा, समान प्रक्रियाहरू चलाउने परिणाम औसत कार्यक्रम टर्नअराउन्ड समयमा सुधार हुनेछ र यो बराबर हुनेछ Of २ को सट्टा, जुन लगभग 2 गुणा राम्रो छ।

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

कल्पना गरौं कि कार्य A (100c) पहिले आइपुग्छ र कार्यान्वयन गर्न सुरु हुन्छ। t=10 मा, कार्यहरू B र C आइपुग्छन्, जसमध्ये प्रत्येकले 10 सेकेन्ड लिनेछ। त्यसोभए औसत कार्यान्वयन समय (100+(110-10)+(120-10))3 = 103 हो। यसलाई सुधार गर्न अनुसूचकले के गर्न सक्छ?

सबैभन्दा छोटो समय-सम्पन्न पहिलो (STCF)

स्थिति सुधार गर्नको लागि, हामीले कार्यक्रम सुरु भएको र पूरा नभएसम्म चल्ने अनुमान 3 छोड्छौं। थप रूपमा, हामीलाई हार्डवेयर समर्थन चाहिन्छ र, तपाईले अनुमान गर्न सक्नुहुन्छ, हामी प्रयोग गर्नेछौं टाइमर चलिरहेको कार्यमा अवरोध गर्न र सन्दर्भ स्विचिङ। यसरी, अनुसूचकले कार्य B, C आइपुग्दा केही गर्न सक्छ - कार्य A को कार्यान्वयन गर्न रोक्नुहोस् र B र C लाई प्रशोधनमा राख्नुहोस् र तिनीहरूको समाप्ति पछि, प्रक्रिया A कार्यान्वयन गर्न जारी राख्नुहोस्। यस्तो अनुसूचक भनिन्छ। STCFवा प्रिमप्टिव काम पहिले.

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

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

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

प्रतिक्रिया समय निम्नानुसार गणना गरिएको छ:

Tresponse=Tfirstrun-Tarrival

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

र यो बाहिर जान्छ कि STCF एल्गोरिथ्म एकै समयमा 3 कार्यहरू आइपुगेको अवस्थामा त्यति राम्रो छैन - यसले साना कार्यहरू पूर्ण रूपमा पूरा नभएसम्म पर्खनु पर्छ। त्यसैले एल्गोरिदम टर्नअराउंड टाइम मेट्रिकको लागि राम्रो छ, तर अन्तरक्रियात्मकता मेट्रिकको लागि खराब छ। कल्पना गर्नुहोस् यदि तपाइँ टर्मिनलमा बसेर सम्पादकमा क्यारेक्टरहरू टाइप गर्न प्रयास गर्दै हुनुहुन्छ र 10 सेकेन्ड भन्दा बढी पर्खनु परेको छ किनभने केही अन्य कार्यले CPU लिइरहेको थियो। यो धेरै सुखद छैन।

त्यसोभए हामी अर्को समस्याको सामना गरिरहेका छौं - हामी कसरी एक अनुसूचक बनाउन सक्छौं जुन प्रतिक्रिया समयको लागि संवेदनशील छ?

राउन्ड रोबिन

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

एउटा उदाहरण हेरौं: ABC कार्यहरू प्रणालीमा एकैसाथ आइपुग्छन् र तिनीहरूमध्ये प्रत्येक 5 सेकेन्डसम्म चल्न चाहन्छ। SJF एल्गोरिदमले अर्को सुरु गर्नु अघि प्रत्येक कार्य पूरा गर्नेछ। यसको विपरित, आरआर एल्गोरिथ्म लन्च विन्डो = 1s निम्न कार्यहरू मार्फत जान्छ (चित्र 4.3):

(SJF फेरि (प्रतिक्रिया समयको लागि खराब)

(राउण्ड रोबिन (प्रतिक्रिया समयको लागि राम्रो)

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

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

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

अधिक सामान्य सर्तहरूमा, कुनै पनि RR-प्रकार एल्गोरिथ्म उचित छ; यसले CPU समयलाई सबै प्रक्रियाहरू बीच समान रूपमा विभाजित गर्दछ। र यसैले, यी मेट्रिकहरू निरन्तर एक-अर्कासँग विवादित हुन्छन्।

यसरी, हामीसँग धेरै विरोधाभासी एल्गोरिदमहरू छन् र एकै समयमा त्यहाँ अझै धेरै अनुमानहरू बाँकी छन् - कि कार्य समय थाहा छ र त्यो कार्यले मात्र CPU प्रयोग गर्दछ।

I/O संग मिश्रण

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

कुनै पनि प्रक्रियाले I/O सञ्चालनको अनुरोध गर्ने क्षणमा, प्रक्रियाले I/O पूरा हुनको लागि पर्खँदै अवरुद्ध अवस्थामा प्रवेश गर्छ। यदि I/O हार्ड ड्राइभमा पठाइयो भने, त्यस्ता अपरेसनले धेरै एमएस वा लामो समय लिन सक्छ, र प्रोसेसर यस क्षणमा निष्क्रिय हुनेछ। यस समयमा, अनुसूचकले कुनै पनि अन्य प्रक्रियासँग प्रोसेसर कब्जा गर्न सक्छ। अर्को निर्णय अनुसूचकले गर्नुपर्नेछ जब प्रक्रियाले यसको I/O पूरा गर्नेछ। जब यो हुन्छ, एक अवरोध उत्पन्न हुनेछ र OS ले I/O भनिने प्रक्रियालाई तयार अवस्थामा राख्नेछ।

धेरै कार्यहरूको उदाहरण हेरौं। तिनीहरू मध्ये प्रत्येकलाई 50ms CPU समय चाहिन्छ। यद्यपि, पहिलोले प्रत्येक १० मिनेटमा I/O पहुँच गर्नेछ (जसलाई प्रत्येक १० मिनेटमा कार्यान्वयन गरिनेछ)। र प्रक्रिया B ले I/O बिना 10ms प्रोसेसर प्रयोग गर्दछ।

यस उदाहरणमा हामी STCF अनुसूचक प्रयोग गर्नेछौं। यदि A जस्तै प्रक्रिया सुरु भयो भने अनुसूचकले कसरी व्यवहार गर्नेछ? उसले निम्न काम गर्नेछ: पहिले उसले प्रक्रिया A लाई पूर्ण रूपमा काम गर्नेछ, र त्यसपछि B प्रक्रिया गर्नेछ।

यस समस्याको समाधान गर्ने परम्परागत दृष्टिकोण भनेको प्रक्रिया A को प्रत्येक 10 एमएस सबटास्कलाई छुट्टै कार्यको रूपमा व्यवहार गर्नु हो। यसरी, STJF एल्गोरिदमको साथ सुरु गर्दा, 50 ms कार्य र 10 ms कार्य बीचको छनौट स्पष्ट छ। त्यसपछि, जब सबटास्क A पूरा हुन्छ, प्रक्रिया B र I/O सुरु हुनेछ। I/O पूरा भएपछि, प्रक्रिया B को सट्टा फेरि 10ms प्रक्रिया A सुरु गर्ने प्रचलन हुनेछ। यसरी, ओभरल्याप कार्यान्वयन गर्न सम्भव छ, जहाँ CPU अर्को प्रक्रियाद्वारा प्रयोग गरिन्छ जबकि पहिलोको लागि पर्खिरहेको हुन्छ। I/O। र नतिजाको रूपमा, प्रणाली राम्रोसँग प्रयोग गरिन्छ - यस क्षणमा जब अन्तरक्रियात्मक प्रक्रियाहरू I/O को लागि पर्खिरहेका छन्, अन्य प्रक्रियाहरू प्रोसेसरमा कार्यान्वयन गर्न सकिन्छ।

ओरेकल अब छैन

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

परिणाम

हामीले कार्य तालिकाको आधारभूत विचारहरू हेर्यौं र अनुसूचकहरूको 2 परिवारहरू हेर्यौं। पहिलोले सबैभन्दा छोटो कार्य सुरु गर्छ र यसरी टर्नअराउन्ड समय बढाउँछ, जबकि दोस्रोले सबै कार्यहरू बीच समान रूपमा च्यात्छ, प्रतिक्रिया समय बढाउँछ। दुबै एल्गोरिदमहरू खराब छन् जहाँ अर्को परिवारको एल्गोरिदमहरू राम्रो छन्। हामीले CPU र I/O को समानान्तर प्रयोगले कार्यसम्पादनलाई कसरी सुधार गर्न सक्छ भनेर पनि हेर्‍यौं, तर OS clairvoyance सँग समस्या समाधान गरेनौं। र अर्को पाठमा हामी योजनाकारलाई हेर्नेछौं जसले तत्काल भूतलाई हेर्छ र भविष्यको भविष्यवाणी गर्ने प्रयास गर्छ। र यसलाई बहु-स्तर प्रतिक्रिया लाम भनिन्छ।

स्रोत: www.habr.com