सरल ओएस शेड्यूलर मॉडल

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

शेड्यूलर वास्तव में क्या योजना बनाता है?

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

शेड्यूलिंग एल्गोरिदम

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

• फीफो
• सबसे छोटा - आगे बढ़ो!
• सबसे कुशल आगे!

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

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

• चक्रीय
• समय प्राथमिकता
• नामित प्राथमिकता

पहली एल्गोरिथ्म कतार का एक प्रत्यक्ष एनालॉग है, या यों कहें, यह कतार है: पहली बार आया था - पहली बार अपना समय टुकड़ा प्राप्त किया, फिर से कतार के अंत में खड़ा हुआ। केवल एक स्पष्ट, लेकिन बहुत कष्टप्रद माइनस यह है कि एक धारा जो 1/10 समय क्वांटम का उपयोग करती है, उसके पास पूरे प्रोसेसर का उपयोग करते हुए स्ट्रीम के रूप में ज्यादा प्रोसेसर समय होगा।
दूसरा एल्गोरिथ्म इस समस्या को हल करता है: प्रत्येक थ्रेड को क्वांटम के उपयोग किए गए अंश के विपरीत आनुपातिक रूप से प्राथमिकता दी जाती है। उच्च प्राथमिकता वाला एक धागा पहले कतार में है।
तीसरा एल्गोरिथ्म इंटरैक्टिव (सर्वर) ऑपरेटिंग सिस्टम के लिए विशिष्ट है, जिसमें उपयोगकर्ता अनुरोधों को संसाधित करना सबसे आगे है। प्राथमिकता प्रवाह को उनके द्वारा निष्पादित कार्य के आधार पर सौंपा गया है। यहां, उदाहरण के लिए, http अनुरोधों के प्रसंस्करण की सर्वोच्च प्राथमिकता होगी, ऑपरेटर के आदेशों को संसाधित करना थोड़ा कम होगा, आदि। इस एल्गोरिथ्म का उपयोग करते समय, धारा को नियंत्रित करने के लिए इसे एक बड़ा टुकड़ा आवंटित करके धारा के नियंत्रण को फिर से भरना संभव है। तो एक धागा जिसमें प्राथमिकता कम होती है और संभावित रूप से कतार में सबसे लंबे समय तक सबसे प्रोसेसर समय प्राप्त होगा।
प्रीमेप्टिव मल्टीटास्किंग को प्रोग्रामर को शेड्यूलर की पेचीदगियों को समझने की आवश्यकता नहीं होती है, लेकिन इसमें नुकसान भी होते हैं।

महत्वपूर्ण खंड

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

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

गतिरोध

मान लीजिए कि हमारे पास अविभाजित संसाधन A और B हैं और X, Y प्रवाहित करते हैं जो इन संसाधनों का उपयोग करना चाहते हैं। यदि एक निश्चित टेढ़ा-मेढ़ा अपर्याप्त सक्षम प्रोग्रामर इस तरह महत्वपूर्ण कोष्ठक डालता है :
...
स्ट्रीम एक्स
संसाधन ले लो (ए)
संसाधन ले लो (B)
...
संसाधन दें (A)
संसाधन दें (B)
स्ट्रीम वाई
संसाधन ले लो (B)
संसाधन ले लो (ए)
...
संसाधन दें (B)
संसाधन दें (A)

थोड़ी देर बाद, यह स्थिति पैदा होगी:

मीठा

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

procedure EnterCritical(num:TCriticalNum); {   } begin asm cli end; if num<=maxCritical then begin if criticalTable[num]<>0 then begin inc(criticalTableWait[num]); {    } while criticalTable[num]>0 do begin {   -} {       } asm sti end; SwitchThreads; asm cli end; end; dec(criticalTableWait[num]); end; criticalTable[num]:=1; end; asm sti end; end; 

लीव क्रिटिकल () के साथ सब कुछ स्पष्ट प्रतीत होता है:

 procedure LeaveCritical(num:TCriticalNum); {  } begin asm cli end; if num<=maxCritical then criticalTable[num]:=0; asm sti end; if criticalTableWait[num]>0 then { -  } switchThreads; end; 

प्रवाह स्विच करने की प्रक्रिया कोडांतरक आवेषण का उपयोग करके लिखी गई है, इसलिए आप मशीन कमांड की सटीकता के साथ एक से दूसरे में स्विचिंग प्रवाह के क्षण देख सकते हैं:

 procedure TimerHandler(flags,cs,ip,ax,bx,cx,dx,si,di,ds,es,bp:word); interrupt; {         ,            } const ThreadNumber:byte=0; const NumPrev:byte=0; const tsoffset:word=0; mainSP:word=0; mainSS:word=0; begin if not DisableHardwareEvents then begin asm pushf end; oldvec8; {     .    .} end; if preemptiveSwitch or DisableHardwareEvents then if (ThreadsRegistered>1) or (parallelStart) then begin {   } asm cli end; if ParallelStart then begin {     } StepCount:=0; asm mov ParallelFinished,false {  } mov mainsp,bp {      } mov mainss,ss {  } end; end; inc(StepCount); if {ts[ThreadNumber].active and} not ParallelStart then begin {   () .      ParallelStart, .. ,        } {      } tsoffset:=ThreadNumber*sizeof(TThreadStateWord); asm push ds { ,    DS     !} mov ax,seg ts mov es,ax mov di,offset ts add di,tsoffset mov ax,ss mov ds,ax mov si,bp {ds:si   ,   } cld mov cx,12 rep movsw {    ( )} pop ds {es:di   24          } mov ax,bp {BP     12  } add ax,12*2 stosw {SP } mov ax,ss stosw {SS } end; end; {   } NumPrev:=ThreadNumber; repeat ThreadNumber:=(ThreadNumber+1) mod ThreadsRegistered; until (ThreadNumber=NumPrev) or TS[ThreadNumber].active; if ts[ThreadNumber].active and ((ThreadNumber<>NumPrev) or parallelStart) then begin {  ,     .     ParallelStart,       , ..  ,          0} tsOffset:=(ThreadNumber+1)*sizeof(TThreadStateWord) - 3; asm mov dx,ds mov ax,seg TS mov ds,ax mov si,offset TS add si,tsOffset {ds:si     } std lodsw mov ss,ax lodsw mov sp,ax mov bp,ax {    } sub bp,12*2 {       .          ,         } mov cx,12 @m1: lodsw push ax loop @m1 cld mov ds,dx end; end else if (not ts[Threadnumber].active) and (Threadnumber=NumPrev) then begin {  } setintvec($8,@oldvec8); asm mov parallelfinished,true mov ax,mainss mov ss,ax mov bp,mainsp mov sp,bp end; end; parallelstart:=false; end; DisableHardwareEvents:=false; end; 

प्रक्रिया स्वयं को बाधा निर्देश के साथ संकलित की जाती है, अर्थात यह एक बाधा हैंडलर है। जिसे int 08h कहकर हार्डवेयर और सॉफ्टवेयर दोनों को ट्रिगर किया जा सकता है:

 procedure SwitchThreads; begin if not parallelFinished then asm cli mov DisableHardwareEvents,1 int 08h sti end; end; 

स्वयं को पंजीकरण प्रक्रियाओं का वर्णन करना भी आवश्यक है, जिसमें प्रवाह को रोकना और शामिल करना शामिल है। अगर किसी को दिलचस्पी है, तो आप स्रोत प्रक्रियाओं को देख सकते हैं RegistrThread, RunThread, StopThread।
वह सब है! हमारा प्लानर तैयार है।
इस योजना के लिए लिखे गए बहु-सूत्रीय कार्यक्रम का एक उदाहरण और दोसोवस्की टर्बिक को एक साथ डाउनलोड किया जा सकता है । आप चारों ओर खेल सकते हैं और देख सकते हैं कि प्रीमेप्टिव और नॉन-प्रीमेप्टिव मल्टीटास्किंग (ExecuteRegisterThreads (ट्रू / गलत) प्रक्रिया) के साथ अलग-अलग थ्रेड कैसे निष्पादित होंगे, एक गतिरोध की स्थिति का अनुकरण करें और सुनिश्चित करें कि यह हमेशा निदान नहीं होता है (मैं एक मिनट तक इंतजार करता रहता हूं जब तक गतिरोध नहीं होता)।
मैं डॉसबॉक्स के तहत नए Win98 सिस्टम पर चलने की सलाह देता हूं।