mutex, semorphore, spinLock और futex का उपयोग किये बिना थ्रेड सिंक्रनाइज़ेशन कैसे करें?

Question

यह एक साक्षात्कार प्रश्न है, साक्षात्कार किया गया है।

mutex, semorphore, spinLock और futex का उपयोग किए बिना थ्रेड सिंक्रनाइज़ेशन कैसे करें?

5 धागे दिए गए, उनमें से 4 को एक ही बिंदु पर बाएं धागे से सिग्नल की प्रतीक्षा कैसे करें? इसका मतलब है कि जब सभी धागे (1,2,3,4) अपने थ्रेड फ़ंक्शन में किसी बिंदु पर निष्पादित होते हैं, तो वे थ्रेड 5 से सिग्नल भेजते हैं और सिग्नल भेजते हैं अन्यथा वे आगे नहीं बढ़ेंगे।

मेरा विचार:

उपयोग एक ध्वज के रूप में वैश्विक bool चर, अगर धागा 5 यह निर्धारित नहीं करता है सच है, अन्य सभी धागे एक बिंदु पर इंतजार और साथ ही उनका झंडा चर सच निर्धारित किया है। थ्रेड 5 के बाद सभी धागे के ध्वज चर सही हैं, यह इसे ध्वज var true सेट करेगा।

यह एक व्यस्त प्रतीक्षा है।

कोई बेहतर विचार?

धन्यवाद

the pseudo code: 
bool globalflag = false; 
bool a[10] = {false} ; 
int main() 
{ 
    for (int i = 0 ; i < 10; i++) 
    pthread_create(threadfunc, i) ; 

     while(1) 
     { 
     bool b = true; 
     for (int i = 0 ; i < 10 ; i++) 
     { 
       b = a[i] & b ; 
     } 
     if (b) break; 
    } 
    } 
    void threadfunc(i) 
    { 
    a[i] = true; 
    while(!globalflag); 
    } 

Answer 1

धागे इंतजार कर के एक खाली लिंक्ड सूची के साथ शुरू। सिर 0

वेटर्स की सूची के सिर पर धागा डालने के लिए सीएएस, तुलना और स्वैप का उपयोग करें। यदि सिर = -1, तो सम्मिलित या प्रतीक्षा न करें। यदि आप सही करते हैं तो आप एक लिंक्ड सूची के शीर्ष पर आइटम डालने के लिए सुरक्षित रूप से सीएएस का उपयोग कर सकते हैं।

डालने के बाद, प्रतीक्षा थ्रेड SIGUSR1 पर प्रतीक्षा करनी चाहिए। ऐसा करने के लिए sigwait() का प्रयोग करें।

तैयार होने पर, सिग्नलिंग थ्रेड प्रतीक्षा सूची के सिर को -1 तक सेट करने के लिए सीएएस का उपयोग करता है। यह किसी और धागे को प्रतीक्षा सूची में जोड़ने से रोकता है। फिर सिग्नलिंग थ्रेड प्रतीक्षा सूची में धागे को पुन: सक्रिय करता है और प्रत्येक प्रतीक्षा धागे को जागने के लिए pthread_kill (& थ्रेड, SIGUSR1) को कॉल करता है।

अगर SIGUSR1 को कॉल करने से पहले भेजा जाता है, तो सिगवाइट तुरंत वापस आ जाएगा। इस प्रकार, प्रतीक्षा सूची में थ्रेड जोड़ने और सिग्वाइट को कॉल करने के बीच कोई दौड़ नहीं होगी।

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

क्यों कैस तेजी से एक म्युटेक्स से है? लेमेन का जवाब (मैं एक आम आदमी हूं)। कुछ स्थितियों में कुछ चीजों के लिए यह तेज़ है, क्योंकि कोई दौड़ नहीं होने पर इसका निचला ओवरहेड होता है। इसलिए यदि आप अपनी समवर्ती समस्या को कम कर सकते हैं तो 8-16-32-64-128 संगत स्मृति के बिट्स को बदलने की आवश्यकता है, और एक दौड़ अक्सर नहीं होने वाली है, सीएएस जीतता है। सीएएस मूल रूप से थोड़ा अधिक फैंसी/महंगा मूव निर्देश है जहां आप नियमित रूप से "mov" करने जा रहे थे। यह एक "ताला exchng" या ऐसा कुछ है।

दूसरी ओर एक म्यूटेक्स अतिरिक्त सामान का एक पूरा समूह है, जो अन्य कैश लाइनों को गंदे बनाता है और अधिक मेमोरी बाधाओं का उपयोग करता है, आदि। हालांकि सीएएस x86, x64, आदि पर मेमोरी बाधा के रूप में कार्य करता है। फिर निश्चित रूप से आपको म्यूटेक्स को अनलॉक करना होगा जो शायद अतिरिक्त सामान की एक ही राशि के बारे में है।

while (1) 
{ 
    pOldHead = pHead; <-- snapshot of the world. Start of the race. 
    pItem->pNext = pHead; 
    if (CAS(&pHead, pOldHead, pItem)) <-- end of the race if phead still is pOldHead 
    break; // success 
} 

तो तुम कितनी बार लगता है कि आपके कोड सटीक एक ही समय में है कि कैस लाइन पर एक से अधिक थ्रेड के लिए जा रहा है है:

तरीका यहां बताया गया कैस का उपयोग कर एक लिंक्ड सूची में कोई आइटम जोड़ने है? हकीकत में .... अक्सर नहीं। हमने परीक्षण किया है कि एक ही समय में कई धागे के साथ लाखों आइटम जोड़ना पसंद किया है और यह 1% से कम समय से कम होता है। एक असली कार्यक्रम में, यह कभी नहीं हो सकता है।

जाहिर है कि यदि कोई दौड़ है तो आपको वापस जाना होगा और उस लूप को दोबारा करना होगा, लेकिन एक लिंक्ड सूची के मामले में, आपको इसकी क्या कीमत है?

नकारात्मकता यह है कि आप उस लिंक की गई सूची में बहुत जटिल चीजें नहीं कर सकते हैं यदि आप सिर पर आइटम जोड़ने के लिए उस विधि का उपयोग करने जा रहे हैं। एक डबल लिंक्ड सूची को लागू करने का प्रयास करें। क्या मुसीबत है।

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

कोड ऊपर मैं एक मैक्रो कैस का उपयोग करें। यदि आप linux का उपयोग कर रहे हैं, तो CAS = मैक्रो __sync_bool_compare_and_swap का उपयोग कर। gcc atomic builtins देखें। यदि आप इंटरलॉक कॉम्पैयर एक्सचेंज जैसे कुछ का उपयोग कर विंडोज़, सीएएस = मैक्रो का उपयोग कर रहे हैं।

inline bool CAS(volatile WORD* p, const WORD nOld, const WORD nNew) { 
    return InterlockedCompareExchange16((short*)p, nNew, nOld) == nOld; 
} 
inline bool CAS(volatile DWORD* p, const DWORD nOld, const DWORD nNew) { 
    return InterlockedCompareExchange((long*)p, nNew, nOld) == nOld; 
} 
inline bool CAS(volatile QWORD* p, const QWORD nOld, const QWORD nNew) { 
    return InterlockedCompareExchange64((LONGLONG*)p, nNew, nOld) == nOld; 
} 
inline bool CAS(void*volatile* p, const void* pOld, const void* pNew) { 
    return InterlockedCompareExchangePointer(p, (PVOID)pNew, (PVOID)pOld) == pOld; 
} 

Answer 2

1. एक संकेत का उपयोग करने के लिए चुनें, का कहना है कि SIGUSR1: यहाँ क्या खिड़कियों में एक इनलाइन समारोह कैसा लग सकता है।
2. SIGUSR1 को अवरोधित करने के लिए pthread_sigmask का उपयोग करें।
3. धागे बनाएं (वे सिग्नल मास्क का वारिस करते हैं, इसलिए 1 पहले किया जाना चाहिए!)
4. थ्रेड 1-4 कॉल सिग्वाइट, एसआईजीयूएसआर 1 प्राप्त होने तक अवरुद्ध हो रहा है।
5. थ्रेड 5 कॉल SIGUSR1 के साथ 4 बार मार() या pthread_kill। चूंकि POSIX निर्दिष्ट करता है कि संकेत थ्रेड पर वितरित किए जाएंगे जो सिग्नल को अवरुद्ध नहीं कर रहा है, यह सिगवाइट() में प्रतीक्षा किए गए थ्रेड में से एक को वितरित किया जाएगा। इस प्रकार ट्रैक रखने के लिए कोई आवश्यकता नहीं है कि कौन से धागे पहले से ही संकेत प्राप्त कर चुके हैं और जो संबंधित सिंक्रनाइज़ेशन के साथ नहीं हैं।

Answer 3

आप SSE3 के MONITOR और MWAIT निर्देश, _mm_mwait और _mm_monitor intrinsics के माध्यम से उपलब्ध का उपयोग कर ऐसा कर सकते हैं, इंटेल यह here पर एक लेख है। (लॉक विवाद here के लिए स्मृति-मॉनिटर-प्रतीक्षा का उपयोग करने के लिए पेटेंट भी है जो ब्याज का हो सकता है)।

Answer 4

मुझे लगता है कि आप देख रहे हैं Peterson's algorithm या Dekker's algorithm

वे धागे केवल साझा स्मृति के आधार पर समन्वयित किया