फ्यूटेक्स मूल बातें

Futex (futex - "फास्ट यूज़र्सस्पेस म्यूटेक्स" के लिए) 2002 में IBM के लिनक्स डेवलपर्स द्वारा प्रस्तावित एक तंत्र है और 2003 के अंत में कर्नेल में प्रवेश किया। मुख्य विचार ओएस कर्नेल के लिए न्यूनतम संख्या के साथ उपयोगकर्ता थ्रेड को सिंक्रनाइज़ करने के लिए अधिक कुशल तरीका प्रदान करना था।

इस लेख में, हम फ्यूटेक्स की समीक्षा करेंगे, उनके काम के सिद्धांतों को समझने की कोशिश करेंगे, और उन्हें उच्च-स्तरीय (और हमसे परिचित) सिंक्रनाइज़ेशन ऑब्जेक्ट बनाने के लिए ईंटों के रूप में भी उपयोग करेंगे।

एक महत्वपूर्ण बिंदु: फ्यूटेक्स एक बल्कि निम्न-स्तरीय उपकरण है, यह केवल मौलिक पुस्तकालयों को विकसित करने के दौरान इसका उपयोग करने के लायक है, जैसे कि मानक सी / सी ++ पुस्तकालय। यह बहुत संभावना नहीं है कि आपको एक नियमित अनुप्रयोग में फ़्यूटेक्स का उपयोग करने की आवश्यकता होगी।

प्रेरणा

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

OS में "futex" की एक नई अवधारणा को जोड़ने का प्रस्ताव एक साधारण अवलोकन पर आधारित था: ज्यादातर मामलों में, सिंक्रनाइज़ेशन ऑब्जेक्ट को पकड़ने का प्रयास पहली बार सफल होता है। प्रोग्रामर इस तरह से सॉफ्टवेयर लिखते हैं कि लॉक को लॉक करने से लेकर उसे अनलॉक करने में जितना संभव हो उतना कम समय बीतता है, जिसका अर्थ है कि बहुत अधिक संभावनाएं हैं कि दूसरे धागे को पकड़ने का प्रयास बाधाओं का सामना नहीं करेगा। जब कोई धारा ऐसे "मुक्त" सिंक्रनाइज़ेशन ऑब्जेक्ट तक पहुंचती है, तो हम अपेक्षाकृत सस्ते परमाणु संचालन का उपयोग करके सिस्टम कॉल किए बिना इसे कैप्चर कर सकते हैं। और एक बहुत बड़ी संभावना है कि परमाणु ऑपरेशन सफलतापूर्वक काम करेगा।

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

फ्यूटेक्स का सरल उपयोग - उम्मीद और जागृति

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

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

सीधे शब्दों में कहें, एक फूटेक्स एक कर्नेल निर्माण है जो उपयोगकर्ता कोड को कुछ होने पर थ्रेड को सिंक्रनाइज़ करने में मदद करता है। कुछ प्रक्रियाएँ (या थ्रेड्स) FUTEX_WAIT कॉल में घटनाओं की प्रतीक्षा कर सकती हैं, जबकि अन्य इन घटनाओं को FUTEX_WAKE के साथ कॉल कर सकते हैं। प्रतीक्षारत कुशलता से काम करता है - प्रतीक्षा सूत्र कर्नेल द्वारा निलंबित कर दिए जाते हैं और प्रोसेसर संसाधनों का उपयोग नहीं करते हैं जब तक कि वे एक अपेक्षित घटना होने पर जागृत न हों।

प्रलेखन को संपूर्णता में पढ़ने का समय निकालें। खैर, या कम से कम FUTEX_WAIT और FUTEX_WAKE पर अनुभाग पढ़ें।

आइए एक सरल उदाहरण देखें जो दो प्रक्रियाओं के काम को समन्वित करने के लिए फ्यूटेक्स के मूल उपयोग को प्रदर्शित करता है।

बाल प्रक्रिया:

1. सामान्य मेमोरी स्लॉट में 0xA की प्रतीक्षा करता है
2. इस स्लॉट में मान 0xB लिखता है

इस समय की मूल प्रक्रिया:

1. साझा मेमोरी स्लॉट में 0xA मान लिखता है
2. इसमें प्रदर्शित होने के लिए 0xB की प्रतीक्षा करता है

दो प्रक्रियाओं के बीच ऐसा "हैंडशेक"। यहाँ कोड है:

int main(int argc, char** argv) { int shm_id = shmget(IPC_PRIVATE, 4096, IPC_CREAT | 0666); if (shm_id < 0) { perror("shmget"); exit(1); } int* shared_data = shmat(shm_id, NULL, 0); *shared_data = 0; int forkstatus = fork(); if (forkstatus < 0) { perror("fork"); exit(1); } if (forkstatus == 0) { //   printf("child waiting for A\n"); wait_on_futex_value(shared_data, 0xA); printf("child writing B\n"); //  0xB         *shared_data = 0xB; wake_futex_blocking(shared_data); } else { //   printf("parent writing A\n"); //  0xA         *shared_data = 0xA; wake_futex_blocking(shared_data); printf("parent waiting for B\n"); wait_on_futex_value(shared_data, 0xB); // Wait for the child to terminate. wait(NULL); shmdt(shared_data); } return 0; } 

प्रक्रियाओं के बीच साझा मेमोरी को आवंटित करने के लिए POSIX कॉल पर ध्यान दें। हम यहां सामान्य मेमोरी आवंटन का उपयोग नहीं कर सकते हैं, क्योंकि विभिन्न प्रक्रियाओं में संकेत का एक ही पता वास्तव में अलग-अलग मेमोरी ब्लॉक (प्रत्येक प्रक्रिया के लिए अद्वितीय) को इंगित करेगा।

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

और यहाँ Wait_on_futex_value फ़ंक्शन कोड है:

 void wait_on_futex_value(int* futex_addr, int val) { while (1) { int futex_rc = futex(futex_addr, FUTEX_WAIT, val, NULL, NULL, 0); if (futex_rc == -1) { if (errno != EAGAIN) { perror("futex"); exit(1); } } else if (futex_rc == 0) { if (*futex_addr == val) { //    return; } } else { abort(); } } } 

इस फ़ंक्शन का मुख्य कार्य (इसके अलावा, वास्तव में, फ़ुटेक्स सिस्टम कॉल) एक चक्र है जिसमें हम चलाते हैं जब हम झूठे जागते हैं (हम में रुचि नहीं)। यह तब हो सकता है जब एक नया मूल्य, लेकिन हमारे द्वारा अपेक्षित नहीं है, साझा मेमोरी स्लॉट में स्थापित है। ठीक है, या इस मामले में जब हमारी तुलना में एक और प्रक्रिया पहले जागृत हुई थी (यह हमारे विशेष मामले में नहीं हो सकता है, लेकिन अधिक सामान्य तरीके से यह संभव है)।

Futex शब्दार्थ बहुत मुश्किल सामान हैं! FUTEX_WAIT कॉल तुरंत वापस आ जाएगी अगर futex पते पर मान पारित तर्क घाटी के बराबर नहीं है। हमारे मामले में, यह तब हो सकता है जब बच्चे की प्रक्रिया प्रतीक्षा करने से पहले माता-पिता ने स्लॉट में मूल्य 0xA लिखा हो। इस मामले में futex EAGAIN मान लौटाता है।

और यहाँ 'aw_futex_blocking' फ़ंक्शन कोड है:

 void wake_futex_blocking(int* futex_addr) { while (1) { int futex_rc = futex(futex_addr, FUTEX_WAKE, 1, NULL, NULL, 0); if (futex_rc == -1) { perror("futex wake"); exit(1); } else if (futex_rc > 0) { return; } } } 

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

Futexes कस्टम कोड के लिए कर्नेल कतार हैं।

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

यहाँ लेख "एक futex अवलोकन और अद्यतन" से चित्र पर है:



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

FUTEX_WAIT के साथ समय-सीमित प्रतीक्षा करें

फ़ुटेक्स सिस्टम कॉल में एक टाइमआउट पैरामीटर है जो उपयोगकर्ता को यह निर्दिष्ट करने की अनुमति देता है कि वे कितनी देर तक प्रतीक्षा करने के लिए तैयार हैं। यहां एक पूर्ण उदाहरण है जहां इसे लागू किया गया है, लेकिन यहां प्रमुख भाग है:

 printf("child waiting for A\n"); struct timespec timeout = {.tv_sec = 0, .tv_nsec = 500000000}; while (1) { unsigned long long t1 = time_ns(); int futex_rc = futex(shared_data, FUTEX_WAIT, 0xA, &timeout, NULL, 0); printf("child woken up rc=%d errno=%s, elapsed=%llu\n", futex_rc, futex_rc ? strerror(errno) : "", time_ns() - t1); if (futex_rc == 0 && *shared_data == 0xA) { break; } } 

यदि प्रतीक्षा 500 एमएस के लिए देरी हो रही है, तो फ़ुटेक्स फ़ंक्शन समाप्त हो जाएगा, और लूप के अगले पुनरावृत्ति में हम किसी तरह इस पर प्रतिक्रिया कर सकते हैं (स्क्रीन पर कुछ प्रदर्शित करें, लॉग पर लिखें, प्रतीक्षा जारी रखें या रोकें)।

म्यूटेक्स को लागू करने के लिए फ्यूटेक्स का उपयोग करना

हमने इस लेख को इस तथ्य के साथ शुरू किया कि फ़ुटेक्स उच्च-स्तरीय सिंक्रनाइज़ेशन ऑब्जेक्ट के कार्यान्वयन में व्यावहारिक उपयोग के हैं। आइए क्लासिक म्यूटेक्स को लागू करने के लिए उन्हें (साथ ही एटमिक्स) का उपयोग करने का प्रयास करें। नीचे दिए गए कार्यान्वयन उलरिच ड्रेपर द्वारा लिखित लेख "फ्यूटेक्स ट्रिकी" से कोड पर आधारित है।

इस उदाहरण के लिए, मैं C ++ का उपयोग करता हूं, मुख्य रूप से C ++ 11 मानक से एटमिक्स का उपयोग करने की क्षमता के लिए। आप पूर्ण कोड यहां पा सकते हैं, लेकिन सबसे महत्वपूर्ण हिस्सा है:

 class Mutex { public: Mutex() : atom_(0) {} void lock() { int c = cmpxchg(&atom_, 0, 1); // If the lock was previously unlocked, there's nothing else for us to do. // Otherwise, we'll probably have to wait. if (c != 0) { do { // If the mutex is locked, we signal that we're waiting by setting the // atom to 2. A shortcut checks is it's 2 already and avoids the atomic // operation in this case. if (c == 2 || cmpxchg(&atom_, 1, 2) != 0) { // Here we have to actually sleep, because the mutex is actually // locked. Note that it's not necessary to loop around this syscall; // a spurious wakeup will do no harm since we only exit the do...while // loop when atom_ is indeed 0. syscall(SYS_futex, (int*)&atom_, FUTEX_WAIT, 2, 0, 0, 0); } // We're here when either: // (a) the mutex was in fact unlocked (by an intervening thread). // (b) we slept waiting for the atom and were awoken. // // So we try to lock the atom again. We set teh state to 2 because we // can't be certain there's no other thread at this exact point. So we // prefer to err on the safe side. } while ((c = cmpxchg(&atom_, 0, 2)) != 0); } } void unlock() { if (atom_.fetch_sub(1) != 1) { atom_.store(0); syscall(SYS_futex, (int*)&atom_, FUTEX_WAKE, 1, 0, 0, 0); } } private: // 0 means unlocked // 1 means locked, no waiters // 2 means locked, there are waiters in lock() std::atomic<int> atom_; }; 

इस कोड में, cmpxhg फ़ंक्शन परमाणुओं के अधिक सुविधाजनक उपयोग के लिए एक सरल आवरण है:

 // An atomic_compare_exchange wrapper with semantics expected by the paper's // mutex - return the old value stored in the atom. int cmpxchg(std::atomic<int>* atom, int expected, int desired) { int* ep = &expected; std::atomic_compare_exchange_strong(atom, ep, desired); return *ep; } 

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

ग्लिबेक म्यूटेक्स और निम्न-स्तर के ताले

तो हम उस बिंदु पर पहुंच गए जहां glibc POSIX थ्रेड्स को लागू करता है, जिसका एक हिस्सा pthread_mutex_t प्रकार है। जैसा कि मैंने इस लेख की शुरुआत में कहा था, फ्यूटेक्स वह चीज नहीं हैं जिसकी एक साधारण डेवलपर को आवश्यकता होगी। उनका उपयोग रनटाइम लाइब्रेरीज़ या उच्च-स्तरीय सिंक्रोनाइज़ेशन प्राइमेटिव्स को लागू करने के लिए बहुत विशिष्ट विशेष रूप से किया जाता है। इस संदर्भ में, एनपीटीएल के लिए म्यूटेक्स के कार्यान्वयन को देखना दिलचस्प है। Glibc कोड में, यह nptl / pthread_mutex_lock.c फ़ाइल है।

विभिन्न प्रकार के म्यूटेक्स का समर्थन करने की आवश्यकता के कारण कोड काफी जटिल है, लेकिन हम वांछित होने पर काफी परिचित ब्लॉक पा सकते हैं। आप sysdeps / unix / sysv / linux / x86_64 / lowlevellock.h और nptl / lowlevellock.c फाइलों पर भी नज़र डाल सकते हैं। कोड कुछ भ्रामक है, लेकिन फिर भी तुलना-और-विनिमय और फ़ुटेक्स कॉल का संयोजन आसान है।

सिस्टीड्स / nptl / lowlevellock.h फ़ाइल की प्रारंभिक टिप्पणी आपको पहले से ही अच्छी तरह से समझ में आ जानी चाहिए:

 /* Low-level locks use a combination of atomic operations (to acquire and release lock ownership) and futex operations (to block until the state of a lock changes). A lock can be in one of three states: 0: not acquired, 1: acquired with no waiters; no other threads are blocked or about to block for changes to the lock state, >1: acquired, possibly with waiters; there may be other threads blocked or about to block for changes to the lock state. We expect that the common case is an uncontended lock, so we just need to transition the lock between states 0 and 1; releasing the lock does not need to wake any other blocked threads. If the lock is contended and a thread decides to block using a futex operation, then this thread needs to first change the state to >1; if this state is observed during lock release, the releasing thread will wake one of the potentially blocked threads. .. */ 

रनटाइम फ्यूटेक्स

रेंटाइम गो लिबास (ज्यादातर मामलों में) का उपयोग नहीं करता है। इस प्रकार, यह पोसिक्स थ्रेड्स के कार्यान्वयन पर भरोसा नहीं कर सकता है। इसके बजाय, यह सीधे तौर पर निचले स्तर की सिस्टम कॉल करता है। यह इसे फ्यूटेक्स के उपयोग का एक अच्छा उदाहरण बनाता है। चूंकि pthread_mutex_t को कॉल करने का कोई तरीका नहीं है, इसलिए आपको अपना प्रतिस्थापन लिखना होगा। आइए देखें कि यह कैसे किया जाता है, आइए सिंक से शुरू करें। म्यूटेक्स प्रकार उपयोगकर्ता को दिखाई देता है (src / sync / mutex .go) में।

इस प्रकार का लॉक तरीका लॉक को जल्दी पकड़ने के लिए परमाणु स्वैप ऑपरेशन का उपयोग करने का प्रयास करता है। यदि यह पता चला है कि आपको प्रतीक्षा करने की आवश्यकता है, तो यह runtime_SemacquireMutex कहता है, जो रनटाइम कॉल करता है। यह फ़ंक्शन src / runtime / lock_futex.go में परिभाषित किया गया है और यह कई स्थिरांक की घोषणा करता है जो आपके लिए परिचित हो सकते हैं:

 const ( mutex_unlocked = 0 mutex_locked = 1 mutex_sleeping = 2 ... ) // Possible lock states are mutex_unlocked, mutex_locked and mutex_sleeping. // mutex_sleeping means that there is presumably at least one sleeping thread. 

runtime.lock भी परमाणु कार्य का उपयोग करके लॉक को पकड़ने की कोशिश कर रहा है। यह समझ में आता है, चूंकि रनटाइम.लॉक को गो रनटाइम के कई स्थानों में कहा जाता है, लेकिन मुझे ऐसा लगता है कि किसी भी तरह से परमाणु फ़ंक्शन के दो लगातार कॉल को हटाकर कोड को ऑप्टिमाइज़ करना संभव होगा, जब रनटाइम कॉल करें। Mutex .lock से।

यदि यह पता चला है कि आपको प्रतीक्षा करने की आवश्यकता है, तो प्लेटफ़ॉर्म-आश्रित फ़ंक्शन futexsleep को कहा जाता है, जिसे src / runtime / os_linux.go फ़ाइल में लिनक्स के लिए परिभाषित किया गया है। यह फ़ंक्शन FUTEX_WAIT_PRIVATE कोड के साथ एक futex सिस्टम कॉल करता है (इस मामले में, यह उपयुक्त है, क्योंकि गो रनटाइम एक प्रक्रिया में रहता है)।