नींद के पीछे एल्गोरिदम क्या है()?

Question

अब कुछ ऐसा है जो मैंने हमेशा सोचा: नींद() कैसे लागू होती है?

यदि यह ओएस से एपीआई का उपयोग करने के बारे में है, तो एपीआई कैसे बनाई जाती है?

क्या यह सब सीपीयू पर विशेष मशीन-कोड का उपयोग करने के लिए उबालता है? क्या उस सीपीयू को एक विशेष सह-प्रोसेसर या अन्य gizmo चाहिए जिसके बिना आप सो नहीं सकते()?

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

संपादित करें: कुछ उत्तरों पढ़ने के बाद, मुझे लगता है कि प्रक्रिया प्रतीक्षा कतार में रखी गई है। वहाँ से, मैं दो विकल्प हैं, या तो

1. एक टाइमर सेट कर दिया जाता है, ताकि गिरी कारण समय पर प्रक्रिया उठता अनुमान लगा सकते हैं, या
2. गिरी एक समय टुकड़ा अनुमति दी है जब भी, यह करने के लिए चुनाव घड़ी जांचें कि क्या यह प्रक्रिया जागने का समय है या नहीं।

जवाब केवल 1. इसलिए विकल्प का उल्लेख है, मैं पूछता हूँ: कैसे इस टाइमर व्यवहार करता है? यदि कर्नेल प्रक्रिया को जागृत करने में यह एक साधारण बाधा है, तो कर्नेल टाइमर से "मुझे मिली मिलीसेकंड में उठाने के लिए कैसे कह सकता है ताकि मैं प्रक्रिया को राज्य चलाने में डाल सकूं"?

Answer 1

प्रश्न के लिए "अद्यतन" आधुनिक ओएस कैसे काम करता है इस बारे में कुछ गलतफहमी दिखाता है।

कर्नेल को एक समय स्लाइस "अनुमति" नहीं है। कर्नेल वह चीज है जो उपयोगकर्ता प्रक्रियाओं में समय स्लाइस देता है। "टाइमर" नींद की प्रक्रिया को जागृत करने के लिए सेट नहीं है - यह वर्तमान में चल रही प्रक्रिया को रोकने के लिए सेट है।

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

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

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

Answer 2

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

(मनोरंजक सामान्य ज्ञान:। जिसके लिए बच्चे प्रक्रिया बनाई नहीं किया गया था पुराने यूनिक्स कार्यान्वयन में, वहाँ जो कांटा के लिए() कहा जाता है किया गया था प्रक्रियाओं के लिए एक कतार थी, लेकिन यह निश्चित रूप से था कांटा कतार बुलाया।)

एचटीएच!

Answer 3

एक मल्टीटास्किंग ऑपरेटिंग सिस्टम में शेड्यूलर नामक एक घटक होता है, यह घटक थ्रेड के लिए CPU समय देने के लिए ज़िम्मेदार है, नींद को बुलाते हुए ओएस को कुछ समय के लिए इस थ्रेड में CPU समय नहीं देना है।

पूर्ण विवरण के लिए http://en.wikipedia.org/wiki/Process_states देखें।

Answer 4

मुझे लिनक्स के बारे में कुछ भी पता नहीं है, लेकिन मैं आपको बता सकता हूं कि विंडोज पर क्या होता है।

नींद() प्रक्रिया का समय-टुकड़ा तुरंत ओएस पर नियंत्रण वापस करने के लिए समाप्त होता है। ओएस तब एक टाइमर कर्नेल ऑब्जेक्ट सेट करता है जो समय बीतने के बाद संकेत मिलता है। तब ओएस तब तक उस प्रक्रिया को तब तक नहीं देगा जब तक कि कर्नेल ऑब्जेक्ट संकेत न हो जाए। फिर भी, यदि अन्य प्रक्रियाओं में उच्च या समान प्राथमिकता है, तो प्रक्रिया को जारी रखने से पहले यह थोड़ी देर प्रतीक्षा कर सकता है।

ओएस द्वारा प्रोसेस स्विचिंग करने के लिए विशेष सीपीयू मशीन कोड का उपयोग किया जाता है। उन कार्यों को उपयोगकर्ता-मोड कोड द्वारा एक्सेस नहीं किया जा सकता है, इसलिए उन्हें ओएस में एपीआई कॉल द्वारा सख्ती से उपयोग किया जाता है।

Answer 5

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

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

2. कर्नेल स्तर। जब ओएस के पास अभी कुछ करने की ज़रूरत नहीं है, तो यह 'एचएलटी' निर्देश निष्पादित करता है। यह निर्देश कुछ भी नहीं करता है, लेकिन यह कभी भी खत्म नहीं होता है। बेशक, एक हार्डवेयर बाधा सामान्य रूप से सेवा दी जाती है। बस रखो, एक OS का मुख्य पाश (बहुत बहुत दूर से) इस तरह दिखता है:

    
   allow_interrupts(); 
   while (true) { 
       hlt; 
       check_todo_queues(); 
   } 
   

   बाधा संचालकों simpy कार्य करने की कतारों के लिए चीजों जोड़ें। वास्तविक समय घड़ी को समय-समय पर (निश्चित दर पर), या भविष्य में कुछ निश्चित समय के लिए इंटरप्ट उत्पन्न करने के लिए प्रोग्राम किया जाता है जब अगली प्रक्रिया जागृत होती है।

Answer 6

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

क्या एक प्रक्रिया है:

एक प्रक्रिया में सोचें - सिर्फ प्रक्रियाओं के बारे में बात करते हैं, और बाद में धागे को मिलता है - के रूप में "। ऑपरेटिंग सिस्टम शेड्यूल "। एक प्रक्रिया में एक आईडी होती है - एक पूर्णांक सोचें - और आप उस पूर्णांक को उस तालिका के सूचकांक के रूप में सोच सकते हैं जिसमें उस प्रक्रिया के सभी संदर्भ शामिल हैं।

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

प्रक्रियाओं समय की एक बहुत खर्च करते हैं (यानी इंतजार) सो

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

प्रक्रियाएं अन्य चीजों के लिए प्रतीक्षा कर रही हैं: नेटवर्क पैकेट आने के लिए, खिड़की चयन घटनाओं, या समय समाप्त होने के लिए टाइमर, उदाहरण के लिए।

प्रक्रियाओं और निर्धारण

प्रक्रियाओं है कि इंतजार कर रहे हैं होने के लिए गैर runnable कहा जाता है। वे ऑपरेटिंग सिस्टम की रन कतार में नहीं जाते हैं।लेकिन जब घटना होती है जिसकी प्रक्रिया की प्रतीक्षा है, तो यह ऑपरेटिंग सिस्टम को चलने योग्य स्थिति तक गैर-चलाने योग्य प्रक्रिया से स्थानांतरित करने का कारण बनता है। साथ ही, ऑपरेटिंग सिस्टम रन कतार पर प्रक्रिया रखता है, जो वास्तव में एक कतार नहीं है - यह सभी प्रक्रियाओं का ढेर है, ऑपरेटिंग सिस्टम ऐसा करने का निर्णय लेता है, चला सकता है।

निर्धारण:

ऑपरेटिंग सिस्टम का फैसला करता है, नियमित अंतराल है, जो प्रक्रियाओं चलाना चाहिए पर। एल्गोरिदम जिसके द्वारा ऑपरेटिंग सिस्टम ऐसा करने का निर्णय लेता है, कुछ हद तक आश्चर्यजनक रूप से, शेड्यूलिंग एल्गोरिदम कहा जाता है। शेड्यूलिंग एल्गोरिदम मृत-सरल से है ("सभी को 10 एमएस के लिए दौड़ना पड़ता है, और फिर कतार पर अगला व्यक्ति चलाने के लिए चला जाता है") कहीं अधिक जटिल (खाता प्रक्रिया प्राथमिकता, निष्पादन की आवृत्ति, रन-टाइम समय सीमा, अंतर-प्रक्रिया निर्भरता, जंजीर ताले और अन्य जटिल विषय वस्तु के सभी प्रकार)।

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

प्रत्येक टिक ऑपरेटिंग सिस्टम में बाधा उत्पन्न करती है।

जब ओएस इस टाइमर को बाधित करता है, तो यह सिस्टम के समय के बारे में 10 एमएस तक अपना विचार बढ़ाता है। फिर, यह टाइमर कतार को देखता है और तय करता है कि उस कतार पर कौन सी घटनाओं का सामना करना पड़ता है।

टाइमर कतार वास्तव में "चीजों के साथ निपटाए जाने की आवश्यकता" की एक कतार है, जिसे हम ईवेंट करेंगे। इस कतार का समय समाप्ति के समय, जल्द से जल्द घटनाओं द्वारा आदेश दिया जाता है।

एक "घटना" कुछ "हो सकता है प्रक्रिया" एक्स, या "वहां पर किक डिस्क I/O जाओ, क्योंकि यह अटक गया हो सकता है", या "उस फाइब्रैंचनल लिंक पर एक रखरखाव पैकेट भेजें वहॉ पर"। जो भी ऑपरेटिंग सिस्टम करने की जरूरत है।

जब आपके पास इस तरह से कतार का आदेश दिया जाता है, तो इसे हटाने का आसान प्रबंधन होता है। ओएस बस कतार के सिर को देखता है, और प्रत्येक टिक पर 10 एमएस द्वारा "समाप्ति का समय" घटना को कम करता है। जब समाप्ति समय शून्य हो जाता है, तो ओएस उस घटना को रद्द कर देता है, और जो कुछ भी कहलाता है उसे करता है।

नींद की प्रक्रिया के मामले में, यह प्रक्रिया को फिर से चलाने योग्य बनाता है।

सरल, हुह?

Answer 7

अनिवार्य रूप से, हाँ, एक "विशेष gizmo" है - और यह केवल नींद() से बहुत अधिक के लिए महत्वपूर्ण है।

क्लासिकल, x86 पर यह इंटेल 8253 या 8254 "प्रोग्राम करने योग्य अंतराल टाइमर" था। शुरुआती पीसी में, यह मदरबोर्ड पर एक अलग चिप था जिसे सीपीयू द्वारा प्रीसेट समय अंतराल के बाद एक इंटरप्ट ("प्रोग्रेमेबल इंटरप्ट कंट्रोलर", एक और अलग चिप) के माध्यम से प्रोग्राम करने के लिए प्रोग्राम किया जा सकता था। कार्यक्षमता अभी भी मौजूद है, हालांकि यह अब मदरबोर्ड सर्किटरी के एक बड़े हिस्से का एक छोटा सा हिस्सा है।

ओएस आज भी नियमित रूप से इसे उठाने के लिए पीआईटी प्रोग्राम करता है (लिनक्स के हाल के संस्करणों में, डिफ़ॉल्ट रूप से प्रत्येक मिलीसेकंड में), और इस प्रकार कर्नेल पूर्व-खाली मल्टीटास्किंग को कार्यान्वित करने में सक्षम है।

Answer 8

glibc 2.21 लिनक्स

nanosleep सिस्टम कॉल करने के लिए अग्रेषित करता है।

ग्लिबैक अधिकांश लिनक्स डेस्कटॉप डिस्ट्रोज़ पर सी stdlib के लिए डिफ़ॉल्ट कार्यान्वयन है।

इसे कैसे खोजें: पहला पलटा है:

git ls-files | grep sleep 

यह शामिल हैं:

sysdeps/unix/sysv/linux/sleep.c 

और हम जानते हैं कि:

sysdeps/unix/sysv/linux/ 

लिनक्स बारीकियों में शामिल है।

उस फ़ाइल हम देखते हैं के शीर्ष पर:

/* We are going to use the `nanosleep' syscall of the kernel. But the 
    kernel does not implement the stupid SysV SIGCHLD vs. SIG_IGN 
    behaviour for this syscall. Therefore we have to emulate it here. */ 
unsigned int 
__sleep (unsigned int seconds) 

तो अगर आप टिप्पणियों पर भरोसा है, हम मूल रूप से किया जाता है।

तल में

:

weak_alias (__sleep, sleep) 

जो मूल रूप से कहते हैं __sleep == sleep।समारोह का उपयोग करता है nanosleep के माध्यम से:

result = __nanosleep (&ts, &ts); 

greppingg के बाद:

git grep nanosleep | grep -v abilist 

हम दिलचस्प घटनाओं की एक छोटी सूची मिलता है, और मुझे लगता है कि __nanosleep में परिभाषित किया गया है: लाइन पर

sysdeps/unix/sysv/linux/syscalls.list 

:

nanosleep - nanosleep Ci:pp __nanosleep nanosleep 

है जो कुछ सुपर सूखी जादू प्रारूप द्वारा पार्स:

grep -r __nanosleep 

करने के लिए हमें लीड:: /sysd-syscalls है जो make-syscalls.sh उत्पन्न करता है और शामिल हैं:

sysdeps/unix/make-syscalls.sh 

फिर निर्माण निर्देशिका से

#### CALL=nanosleep NUMBER=35 ARGS=i:pp SOURCE=- 
ifeq (,$(filter nanosleep,$(unix-syscalls))) 
unix-syscalls += nanosleep 
$(foreach p,$(sysd-rules-targets),$(foreach o,$(object-suffixes),$(objpfx)$(patsubst %,$p,nanosleep)$o)): \ 
     $(..)sysdeps/unix/make-syscalls.sh 
    $(make-target-directory) 
    (echo '#define SYSCALL_NAME nanosleep'; \ 
    echo '#define SYSCALL_NARGS 2'; \ 
    echo '#define SYSCALL_SYMBOL __nanosleep'; \ 
    echo '#define SYSCALL_CANCELLABLE 1'; \ 
    echo '#include <syscall-template.S>'; \ 
    echo 'weak_alias (__nanosleep, nanosleep)'; \ 
    echo 'libc_hidden_weak (nanosleep)'; \ 
    ) | $(compile-syscall) $(foreach p,$(patsubst %nanosleep,%,$(basename $(@F))),$($(p)CPPFLAGS)) 
endif 

यह मेकफ़ाइल का हिस्सा दिखता है। git grep sysd-syscalls से पता चलता है कि यह शामिल है:

sysdeps/unix/Makefile:23:-include $(common-objpfx)sysd-syscalls 

compile-syscall महत्वपूर्ण हिस्सा की तरह लग रहा है, तो हम पाते हैं:

# This is the end of the pipeline for compiling the syscall stubs. 
# The stdin is assembler with cpp using sysdep.h macros. 
compile-syscall = $(COMPILE.S) -o $@ -x assembler-with-cpp - \ 
        $(compile-mkdep-flags) 

ध्यान दें कि -x assembler-with-cpp एक gcc विकल्प है। जैसे

यह #define रों पैरामीटर:

#define SYSCALL_NAME nanosleep 

और उसके बाद उन पर का उपयोग करें:

#include <syscall-template.S> 

ठीक है, यह जहाँ तक मैं अब के लिए मैक्रो विस्तार खेल पर जाना होगा है।

मुझे लगता है कि यह posix/nanosleep.o फ़ाइल उत्पन्न करता है जिसे सब कुछ के साथ एक साथ जोड़ा जाना चाहिए।

लिनक्स 4.2 x86_64 नैनोस्लीप syscall

अनुसूचक उपयोग करता है: यह एक व्यस्त नींद नहीं है।

खोजें ctags:

sys_nanosleep 

kernel/time/hrtimer.c करने के लिए हमें लीड: उच्च रिज़ॉल्यूशन टाइमर के लिए

SYSCALL_DEFINE2(nanosleep, struct timespec __user *, rqtp, 

hrtimer खड़ा है।वहां से मुख्य लाइन की तरह दिखता है:

• hrtimer_nanosleep
• do_nanosleep
  • set_current_state(TASK_INTERRUPTIBLE); जो व्यवधान कारक नींद है
  • freezable_schedule(); जो schedule() कॉल और अन्य प्रक्रियाओं को चलाने के लिए अनुमति देता है
• hrtimer_start_expires
• hrtimer_start_range_ns
• कार्यसूची: तक पहुँचने arch/x86 समय स्तर

इसके बारे में कुछ लेख:

• https://geeki.wordpress.com/2010/10/30/ways-of-sleeping-in-linux-kernel/
• http://www.linuxjournal.com/article/8144