एकाधिक म्यूटेक्स लॉकिंग रणनीतियों और क्यों पुस्तकालय पता तुलना का उपयोग नहीं करते

Question

एकाधिक ताले लॉक करने का व्यापक रूप से ज्ञात तरीका है, जो इस क्रम के अनुसार निश्चित रैखिक क्रम और एक्वायरिंग ताले चुनने पर निर्भर करता है।

उदाहरण के लिए, "Acquire a lock on two mutexes and avoid deadlock" के उत्तर में प्रस्तावित किया गया था। विशेष रूप से, पर आधारित समाधान पता लगाना काफी सुरुचिपूर्ण और स्पष्ट लगता है।

जब मैंने यह जांचने की कोशिश की कि यह वास्तव में कैसे कार्यान्वित किया जाता है, तो मुझे आश्चर्य हुआ कि यह समाधान व्यापक रूप से उपयोग नहीं किया जाता है।

के शब्दों में Kernel Docs - Unreliable Guide To Locking:

पाठ्यपुस्तकें आपको बता देंगे कि अगर आप हमेशा एक ही क्रम में बंद है, तो आप गतिरोध के इस प्रकार प्राप्त कभी नहीं होगा। प्रैक्टिस आपको बताएगा कि यह दृष्टिकोण स्केल नहीं करता है: जब मैं एक नया लॉक बनाता हूं, तो मुझे समझ में नहीं आता है कि 5000 लॉक पदानुक्रम में फिट होगा।

pthreads प्रतीत नहीं होता है ऐसे तंत्र बिल्कुल में बनाया गया है।

Boost.Thread की कोशिश कर रहा है और के रूप में कई mutexes ताला लगा के रूप में यह इस समय संभव है पर आधारित है पूरी तरह से अलग समाधान, lock() कई (2 से 5) mutexes के लिए के साथ आया था।

यह Boost.Thread स्रोत कोड के टुकड़ा (: 1291 बूस्ट 1.48.0, बढ़ावा/धागा/locks.hpp): है

template<typename MutexType1,typename MutexType2,typename MutexType3> 
void lock(MutexType1& m1,MutexType2& m2,MutexType3& m3) 
{  
    unsigned const lock_count=3; 
    unsigned lock_first=0; 
    for(;;) 
    {  
     switch(lock_first) 
     {  
     case 0: 
      lock_first=detail::lock_helper(m1,m2,m3); 
      if(!lock_first) 
       return; 
      break; 
     case 1: 
      lock_first=detail::lock_helper(m2,m3,m1); 
      if(!lock_first) 
       return; 
      lock_first=(lock_first+1)%lock_count; 
      break; 
     case 2: 
      lock_first=detail::lock_helper(m3,m1,m2); 
      if(!lock_first) 
       return; 
      lock_first=(lock_first+2)%lock_count; 
      break; 
     }  
    }  
}  

जहां सफलता और mutexes की संख्या पर lock_helper रिटर्न 0 कि अन्यथा सफलतापूर्वक बंद नहीं किया गया था।

यह समाधान पते या किसी अन्य प्रकार की आईडी की तुलना में बेहतर क्यों है? मुझे पॉइंटर तुलना के साथ कोई समस्या नहीं दिखाई देती है, जिसे इस तरह के "अंधे" लॉकिंग का उपयोग करके टाला जा सकता है।

क्या लाइब्रेरी स्तर पर इस समस्या को हल करने के बारे में कोई अन्य विचार है?

Answer 1

इनाम पाठ से:

मैं भी यकीन है कि अगर मैं प्रस्तुत बूस्ट समाधान है, जो रैखिक आदेश के साथ एक से अधिक मुश्किल लगता है की सत्यता साबित कर सकते हैं नहीं कर रहा हूँ।

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

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

कोशिश-लॉक-आधारित समाधान की कमी यह है कि इससे आजीविका हो सकती है, और चरम मामलों में पूरी प्रणाली कम से कम कुछ समय तक फंस सकती है। इसलिए कुछ बैक-ऑफ स्कीमा होना महत्वपूर्ण है जो समय के साथ लॉकिंग प्रयासों के बीच विराम बनाता है, और शायद यादृच्छिक।

Answer 2

कभी-कभी लॉक बी को लॉक करने से पहले लॉक ए को हासिल करने की आवश्यकता होती है। लॉक बी में या तो कम या उच्च पता हो सकता है, इसलिए आप इस मामले में पता तुलना का उपयोग नहीं कर सकते हैं।

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

आप केवल पता तुलना का उपयोग कर सकते हैं यदि इससे पहले कोई फर्क नहीं पड़ता कि लॉक पहले अधिग्रहण किया जाता है। यदि ऐसा है, तो पता तुलना एक अच्छा समाधान है। लेकिन अगर ऐसा नहीं है तो आप इसे नहीं कर सकते हैं।

मुझे लगता है कि लिनक्स कर्नेल को कुछ उपप्रणाली को दूसरों के सामने लॉक होने की आवश्यकता है। यह पता तुलना का उपयोग करके नहीं किया जा सकता है।

Answer 3

पता लगाने पर एक परिदृश्य विफल हो जाएगा यदि आप प्रॉक्सी पैटर्न का उपयोग करते हैं। आप ताले को उसी ऑब्जेक्ट में प्रतिनिधि कर सकते हैं और पते अलग होंगे।

निम्न उदाहरण

template<typename MutexType> 
class MutexHelper 
{ 
    MutexHelper(MutexType &m) : _m(m) {} 
    void lock() 
    { 
    std::cout <<"locking "; 
    m.lock(); 
    } 

    void unlock() 
    { 
    std::cout <<"unlocking "; 
    m.unlock(); 
    } 

    MutexType &_m; 
}; 

पर विचार करता है, तो समारोह

template<typename MutexType1,typename MutexType2,typename MutexType3> 
void lock(MutexType1& m1,MutexType2& m2,MutexType3& m3); 

वास्तव में पते का उपयोग तुलना निम्नलिखित कोड एक गतिरोध

Mutex m1; 
Mutex m1; 

thread1

उत्पादन ca होगा

thread2:

MutexHelper hm2(m2); 
MutexHelper hm1(m1); 
lock(hm1, hm2); 

संपादित करें:

इस एक दिलचस्प बात यह है कि बढ़ावा :: ताला कार्यान्वयन पर कुछ प्रकाश का हिस्सा है thread-best-practice-to-lock-multiple-mutexes

पता तुलना अंतर के लिए काम नहीं करता है साझा mutexes (नाम सिंक्रनाइज़ेशन ऑब्जेक्ट्स) प्रक्रिया।

Answer 4

"पता तुलना" और इसी तरह के दृष्टिकोण, हालांकि अक्सर उपयोग किए जाते हैं, विशेष मामले हैं।वे ठीक काम करता है अगर आप

1. एक ताला मुक्त तंत्र है
2. दो (या अधिक) एक ही तरह या पदानुक्रम स्तर
3. किसी भी स्थिर आदेश स्कीमा की "आइटम" पाने के लिए उन वस्तुओं के बीच

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

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

1. लॉक कर देना चाहिए फ़ाइल inode,
2. ताला प्रक्रिया तालिका
3. ताला गंतव्य स्मृति लोड करने के लिए

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

बूस्ट लाइब्रेरी एक ही स्थिति में है: यह जेनेरिक समाधान प्रदान करने का प्रयास करता है। इसलिए वे ऊपर से अंक नहीं ले सकते हैं और एक और जटिल रणनीति पर वापस आना चाहिए।