मेमोरी बाधाएं बनाम इंटरलॉक ऑपरेशंस

Question

मैं स्मृति बाधाओं की मेरी समझ में सुधार करने की कोशिश कर रहा हूं। मान लें कि हमारे पास एक कमजोर स्मृति मॉडल है और हम Dekker's algorithm अनुकूलित करते हैं। मेमोरी बाधाओं को जोड़कर कमजोर मेमोरी मॉडल के तहत इसे सही तरीके से काम करना संभव है?

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

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

मुझे एहसास है कि x86 सहित लोकप्रिय प्रोसेसर, कमजोर स्मृति मॉडल की तुलना में मेमोरी मॉडल को अधिक मजबूत प्रदान करते हैं। कमजोर स्मृति मॉडल पर चर्चा पर ध्यान केंद्रित करें।

(यदि डेकर एल्गोरिथ्म एक गरीब विकल्प है, एक और पारस्परिक अपवर्जन एल्गोरिथ्म जहां स्मृति बाधाओं को सफलतापूर्वक सही तुल्यकालन प्राप्त कर सकते हैं का चयन यदि संभव हो तो।)

Answer 1

आप सही हैं कि एक स्मृति बाधा यह सुनिश्चित नहीं कर सकती है कि एक रीड-अप-डेट मान देखता है। यह क्या करता है संचालन के बीच एक एकल थ्रेड, और धागे के बीच एक आदेश लागू करता है।

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

// initially x=y=z=flag=0 

// thread A 
x=1; 
y=2; 
z=3; 
release_barrier(); 
flag=1; 

// thread B 
while(flag==0) ; // loop until flag is 1 
acquire_barrier(); 
assert(x==1); // asserts will not fire 
assert(y==2); 
assert(z==3); 

बेशक

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

इस प्रकार बाड़ का उपयोग डेकर के एल्गोरिदम में सिंक्रनाइज़ेशन को लागू करने के लिए किया जा सकता है।

यहाँ सी में एक उदाहरण दिया गया ++ (C++ 0x परमाणु वैरिएबल का उपयोग) है:

std::atomic<bool> flag0(false),flag1(false); 
std::atomic<int> turn(0); 

void p0() 
{ 
    flag0.store(true,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_seq_cst); 

    while (flag1.load(std::memory_order_relaxed)) 
    { 
     if (turn.load(std::memory_order_relaxed) != 0) 
     { 
      flag0.store(false,std::memory_order_relaxed); 
      while (turn.load(std::memory_order_relaxed) != 0) 
      { 
      } 
      flag0.store(true,std::memory_order_relaxed); 
      std::atomic_thread_fence(std::memory_order_seq_cst); 
     } 
    } 
    std::atomic_thread_fence(std::memory_order_acquire); 

    // critical section 


    turn.store(1,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_release); 
    flag0.store(false,std::memory_order_relaxed); 
} 

void p1() 
{ 
    flag1.store(true,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_seq_cst); 

    while (flag0.load(std::memory_order_relaxed)) 
    { 
     if (turn.load(std::memory_order_relaxed) != 1) 
     { 
      flag1.store(false,std::memory_order_relaxed); 
      while (turn.load(std::memory_order_relaxed) != 1) 
      { 
      } 
      flag1.store(true,std::memory_order_relaxed); 
      std::atomic_thread_fence(std::memory_order_seq_cst); 
     } 
    } 
    std::atomic_thread_fence(std::memory_order_acquire); 

    // critical section 


    turn.store(0,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_release); 
    flag1.store(false,std::memory_order_relaxed); 
} 

के लिए एक पूर्ण विश्लेषण देखें कि क्या एक और सीपीयू को स्पर्श करने http://www.justsoftwaresolutions.co.uk/threading/implementing_dekkers_algorithm_with_fences.html

Answer 2

कुछ (जैसे PowerPC isync के रूप में बाधाओं, और पर एक .acq लोड ia64) भी बाद के भार पर असर पड़ता है। यानी: अगर prefetching के कारण isync से पहले एक लोड उपलब्ध था तो इसे त्याग दिया जाना चाहिए। जब उचित रूप से उपयोग किया जाता है तो शायद कमजोर स्मृति मॉडल पर डेकर के एल्गोरिदम काम करने के लिए पर्याप्त है।

आपको कैश अमान्यता तर्क भी आपके लिए काम कर रहा है। यदि आप जानते हैं कि आपका लोड एक isync की तरह कुछ के कारण चालू है और डेटा के कैश किए गए संस्करण को अमान्य कर दिया गया है यदि कोई अन्य सीपीयू इसे छूता है, तो क्या वह पर्याप्त है?

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

Answer 3

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

http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html

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

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

बीटीडब्ल्यू, कोरेंसिक, जिस कंपनी के लिए मैं काम करता हूं, कंसुरेंसी मुद्दों को डीबग करने के लिए कूल टूल्स लिखता है। http://www.corensic.com देखें।