परमाणु संचालन प्रतिस्पर्धा कर सकते हैं एक दूसरे को भूखा?

Question

दो धागे के साथ एक कार्यक्रम की कल्पना करो।

// Visible to both threads 
static int test; 

// Run by thread A 
void foo() 
{ 
    // Check if value is 'test' and swap in 0xdeadbeef 
    while(!CAS(&test, test, 0xdeadbeef)) {} 
} 

// Run by thread B 
void bar() 
{ 
    while(1) { 
     // Perpetually atomically write rand() into the test variable 
     atomic_write(&test, rand()); 
    } 
} 

क्या यह संभव है के लिए धागा सदा ऐसे विफल कि 0xdeadbeef 'परीक्षण' के लिए कभी नहीं लिखा है धागा एक के कैस पैदा करने के लिए: वे निम्नलिखित कोड (कैस Compare and Swap को संदर्भित करता है) चल रहे हैं? या प्राकृतिक शेड्यूलिंग जिटर का मतलब है कि व्यवहार में यह कभी नहीं होता है? क्या होगा अगर धागा ए के दौरान कुछ काम किया गया था?

Answer 1

एक सैद्धांतिक मामले के रूप में, हाँ। यदि आप लॉकस्टेप में चल रहे दो धागे को

 
    time  thread A  thread B 
    ----  --------  -------- 
    ||  CAS 
    ||     atomic_write 
    ||  CAS 
    \/     atomic_write 

फिर सीएएस कभी भी वापस नहीं आएगा।

अभ्यास में ऐसा कभी नहीं होगा जब धागे एक सीपीयू/कोर साझा करते हैं, और ऐसा होने की संभावना नहीं होती है जब थ्रेड विभिन्न CPUs या कोर पर चल रहे हों। अभ्यास में यह अविश्वसनीय रूप से कुछ चक्रों के लिए होने की संभावना नहीं है, और एक शेड्यूलर क्वांटम से अधिक के लिए खगोलीय रूप से असंभव होने की संभावना नहीं है।

और यदि इस कोड

void foo() 
{ 
    // Check if value is 'test' and swap in 0xdeadbeef 
    while(!CAS(&test, test, 0xdeadbeef)) {} 
} 

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

या मूल्य है कि आप के खिलाफ वर्तमान परीक्षण का मूल्य नहीं होगा परीक्षण किया जाएगा, बल्कि अंतिम ज्ञात मूल्य किसी प्रकार का।

दूसरे शब्दों में, यह कोड उदाहरण सिद्धांत का एक परीक्षण है, लेकिन आप अभ्यास में इस तरह सीएएस का उपयोग नहीं करेंगे, इसलिए यदि आप इसे विफल करने के लिए भी प्राप्त कर सकते हैं, तो यह आवश्यक नहीं है कि यह कैसे हो सकता है असली दुनिया एल्गोरिदम में उपयोग करते समय विफल।

Answer 2

निश्चित रूप से ऐसे मामलों में भुखमरी हो सकती है। the wikipedia page का हवाला देते हुए,

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

(गणितीय प्रमाण के लिए प्रश्न में पृष्ठ से लिंक देखें)।