प्रॉम्प्ट और संदर्भ
मल्टीपल प्रोड्यूसर्स और कंज्यूमर्स एक निश्चित क्षमता वाली इन-मेमोरी कतार साझा करते हैं। प्रोड्यूसर्स को अनकंज्यूम्ड आइटम्स को ओवरराइट नहीं करना चाहिए, और कंज्यूमर्स को अनपब्लिश्ड आइटम्स को रीड नहीं करना चाहिए। फास्ट पाथ को म्यूटेक्स से बचना चाहिए, जबकि फुल और एम्प्टी स्थितियां प्रतीक्षा कर सकती हैं। स्लॉट लेआउट, एन्कतार/डीकतार पोजीशन्स, मेमोरी ऑर्डर्स और क्लोज़ व्यवहार को डिज़ाइन करें।
इंटरव्यूअर क्या मूल्यांकन करता है
- क्या आप एम्प्टी, रिज़र्व्ड, पब्लिश्ड और कंज्यूम्ड स्थितियों में अंतर करने के लिए मोनोटोनिक पोजीशन्स और प्रति-स्लॉट सीक्वेंसेस का उपयोग करते हैं।
- क्या CAS और acquire/release नॉन-एटॉमिक पेलोड डेटा को सही ढंग से दृश्यमान बनाते हैं।
- क्या आप गैर-दो-की-घात (non-power-of-two) क्षमताओं, प्रोड्यूसर और कंज्यूमर कंटेंशन, और फॉल्स शेयरिंग को संभालते हैं।
- क्या आप वेटिंग, टाइमआउट, क्लोज़, रिक्लेमेशन और ABA सीमाओं की व्याख्या करते हैं।
स्पष्टीकरण के प्रश्न
- क्या एलिमेंट्स निश्चित आकार के हैं, मूवेबल ऑब्जेक्ट्स हैं, या बाहरी ओनरशिप वाले पॉइंटर्स हैं?
- क्या फुल और एम्प्टी को तुरंत लौटना चाहिए, ब्लॉक होना चाहिए, या टाइमआउट होना चाहिए?
closeके बाद, क्या कंज्यूमर्स पहले से कतारबद्ध एलिमेंट्स को ड्रेन कर सकते हैं?- क्या रनटाइम C++20
atomic::waitऔरnotifyप्रदान करता है? - क्या कतार प्रोसेस-लोकल है या सभी प्रोसेस में शेयर्ड है?
30-सेकंड का उत्तर
मैं मोनोटोनिक रूप से बढ़ती हुई एन्कतार और डीकतार पोजीशन्स रखूँगा, जिसमें प्रत्येक स्लॉट में पूर्ण स्थिति से जुड़ा एक सीक्वेंस होगा। एक प्रोड्यूसर CAS द्वारा एक पोजीशन रिज़र्व करता है, नॉन-एटॉमिक पेलोड लिखता है, और एक पब्लिश्ड सीक्वेंस को release-store करता है। एक कंज्यूमर उस सीक्वेंस को acquire-load करता है, पेलोड रीड करता है, और फिर अगले राइटेबल सीक्वेंस को release-store करता है। सीक्वेंस का अंतर फुल और एम्प्टी स्थितियों को अलग करता है। विफल फास्ट पाथ atomic::wait या बाउंडेड बैकऑफ के साथ प्रतीक्षा करते हैं, और क्लोज़ स्थिति परिणाम अनुबंध (result contract) का हिस्सा होती है।
गहन-विश्लेषण उत्तर
चरण 1: स्लॉट्स और पोजीशन्स डिज़ाइन करें
क्षमता N के लिए, मोनोटोनिक enqueuePos और dequeuePos बनाए रखें; मॉड्यूलो के साथ एक पोजीशन को स्लॉट में मैप करें। प्रत्येक स्लॉट में एक sequence और पेलोड होता है। सीक्वेंस स्लॉट के राउंड को वहन करता है, ताकि केवल एक इंडेक्स पुराने डेटा को नए आइटम के रूप में गलत न समझ ले। बिट मास्क के बजाय गैर-दो-की-घात क्षमताओं के लिए सुरक्षित मॉड्यूलो अंकगणित का उपयोग करें।
चरण 2: प्रोड्यूसर पोजीशन रिज़र्व करें
प्रोड्यूसर अपनी उम्मीदवार स्थिति के लिए सीक्वेंस को रीड करता है। यदि यह अपेक्षित राइटेबल मान के बराबर है, तो स्लॉट उपलब्ध है और प्रोड्यूसर CAS के साथ enqueuePos के लिए प्रतिस्पर्धा करता है। CAS विफलता पर, पुनः लोड करें और पुनः प्रयास करें। यदि सीक्वेंस अपेक्षित मान से पीछे है, तो कतार भरी हो सकती है; भविष्य के पदों में आगे बढ़ने के बजाय फुल रिटर्न करें, प्रतीक्षा करें, या टाइमआउट करें।
चरण 3: पेलोड पब्लिश करें
एक पोजीशन रिज़र्व करने के बाद, प्रोड्यूसर के पास विशेष रूप से उस स्लॉट का स्वामित्व होता है और वह पेलोड लिखता है। इसके बाद वह "इस स्थिति पर पब्लिश्ड" अर्थ वाला एक सीक्वेंस release-store करता है। एक कंज्यूमर को नॉन-एटॉमिक पेलोड पढ़ने से पहले सीक्वेंस को acquire-load करना होगा; केवल एक एटॉमिक इंडेक्स यह साबित नहीं करता है कि ऑब्जेक्ट इनिशियलाइज़ेशन दृश्यमान है।
चरण 4: कंज्यूम और रिलीज़ करें
कंज्यूमर भी इसी तरह CAS द्वारा dequeuePos रिज़र्व करता है। यह केवल तभी पढ़ सकता है जब स्लॉट सीक्वेंस अपेक्षित पब्लिश्ड मान के बराबर हो। पढ़ने के बाद, यह अगले राइटेबल राउंड के लिए सीक्वेंस को release-store करता है। अगला प्रोड्यूसर स्लॉट को ओवरराइट करने से पहले उस मान को acquire-load करता है।
चरण 5: मेमोरी ऑर्डर और फॉल्स शेयरिंग परिभाषित करें
पोजीशन CAS एटॉमिक इंडेक्स अपडेट प्रदान करता है; पब्लिश और रिलीज़ सीक्वेंस पर release/acquire पेलोड के लिए happens-before संबंध बनाते हैं। अकेले रिलैक्स्ड ऑपरेशन्स अनपब्लिश्ड डेटा को उजागर कर सकते हैं। राइट इनवैलिडेशन को कम करने के लिए प्रोड्यूसर और कंज्यूमर पोजीशन्स, और हॉट सीक्वेंसेस को अलग-अलग कैश लाइनों पर रखें।
चरण 6: वेटिंग और क्लोज़ को संभालें
जब फास्ट पाथ आगे नहीं बढ़ सकता है, तो atomic::wait के साथ किसी पोजीशन या सीक्वेंस पर प्रतीक्षा करें; सफल एन्कतार या डीकतार notify_one या notify_all को कॉल करता है। लूप को टाइमआउट और स्पुरियस वेकअप को संभालना होगा। क्लोज़ को एटॉमिक रूप से पब्लिश करें: प्रोड्यूसर्स नए आइटम्स को अस्वीकार करते हैं, जबकि कंज्यूमर्स या तो पब्लिश्ड स्लॉट्स को ड्रेन करते हैं या अनुबंध के अनुसार क्लोज्ड रिटर्न करते हैं।
चरण 7: कंटेंशन और लाइफटाइम का परीक्षण करें
क्षमता एक, गैर-दो-की-घात क्षमता, स्लॉट से अधिक प्रोड्यूसर्स या कंज्यूमर्स, लंबे समय तक फुल/एम्प्टी प्रत्यावर्तन और यादृच्छिक देरी का परीक्षण करें। कोई नुकसान नहीं, कोई डुप्लिकेट नहीं, FIFO स्कोप और ड्रेन-ऑन-क्लोज़ की जांच के लिए सीक्वेंस नंबरों का उपयोग करें। डेटा रेस के लिए ThreadSanitizer और स्ट्रेस टेस्ट चलाएं। यदि पेलोड पॉइंटर्स हैं, तो ओनरशिप और रिक्लेमेशन समय निर्दिष्ट करें।
मॉडल उत्तर
प्रत्येक स्लॉट एक पेलोड और मोनोटोनिक सीक्वेंस संग्रहीत करता है; कतार मोनोटोनिक एन्कतार और डीकतार पोजीशन्स संग्रहीत करती है। एक प्रोड्यूसर केवल तभी CAS-रिज़र्व करता है जब सीक्वेंस वर्तमान राइटेबल मान के बराबर होता है, पेलोड लिखता है, फिर सीक्वेंस को release-publish करता है। एक कंज्यूमर पब्लिश्ड मान को acquire-observe करता है, पेलोड रीड करता है, और अगले राइटेबल मान को release-store करता है। सीक्वेंस राउंड एम्प्टी, फुल और पुन: उपयोग किए गए स्लॉट्स में अंतर करते हैं; मॉड्यूलो गैर-दो-की-घात क्षमता को संभालता है। अलग-अलग कैश लाइनें फॉल्स शेयरिंग को कम करती हैं। विफल फास्ट पाथ टाइमआउट और स्पुरियस-वेकअप लूप्स के साथ atomic::wait का उपयोग करते हैं। क्लोज़ नए प्रोड्यूसर्स को अस्वीकार करता है और अनुबंध के अनुसार पब्लिश्ड आइटम्स को ड्रेन करता है। स्ट्रेस टेस्ट, ThreadSanitizer और सीक्वेंस जांच कंटेंशन और लाइफटाइम को कवर करते हैं।
सामान्य गलतियाँ
- केवल हेड और टेल इंडेक्स का उपयोग करना, जो स्लॉट राउंड और पुराने डेटा में अंतर नहीं कर सकते।
- किसी प्रोड्यूसर द्वारा रिज़र्व करने के बाद लेकिन पेलोड पब्लिश करने से पहले कंज्यूमर को पढ़ने की अनुमति देना।
- पेलोड के लिए acquire/release दृश्यता के बिना रिलैक्स्ड पब्लिकेशन का उपयोग करना।
- कतार भर जाने के बाद भी पोजीशन्स रिज़र्व करना जारी रखना और अनकंज्यूम्ड डेटा को ओवरराइट करना।
atomic::waitलूप में स्पुरियस वेकअप, टाइमआउट और क्लोज़ को अनदेखा करना।- गैर-दो-की-घात क्षमता, फॉल्स शेयरिंग, या पॉइंटर रिक्लेमेशन को भूल जाना।
फॉलो-अप प्रश्न
फॉलो-अप 1: प्रत्येक स्लॉट को एक सीक्वेंस की आवश्यकता क्यों होती है?
एक इंडेक्स को राउंड्स में पुन: उपयोग किया जाता है। सीक्वेंस एक स्लॉट को एक पूर्ण स्थिति से बांधता है और राइटेबल, पब्लिश्ड और अगले राउंड की स्थितियों में अंतर करता है, जिससे पुराने मानों को स्वीकार किए जाने से रोका जा सकता है।
फॉलो-अप 2: केवल पेलोड को ही एटॉमिक क्यों न बनाया जाए?
पेलोड कंपोजिट ऑब्जेक्ट्स हो सकते हैं; एक एटॉमिक इंडेक्स का मतलब यह नहीं है कि इनिशियलाइज़ेशन दृश्यमान है। रिलीज़ पब्लिकेशन और एक्वायर ऑब्जर्वेशन पूर्ण नॉन-एटॉमिक पेलोड के लिए दृश्यता स्थापित करते हैं।
फॉलो-अप 3: एक विफल CAS को कितनी देर तक स्पिन करना चाहिए?
कोई सार्वभौमिक मान नहीं है। कम कंटेंशन के लिए संक्षेप में स्पिन करें, फिर यील्ड करें या नोटिफिकेशन की प्रतीक्षा करें। कोर काउंट, क्षमता और लेटेंसी-टारगेट लोड टेस्ट के साथ पॉलिसी को ट्यून करें।
फॉलो-अप 4: आप बिना आइटम खोए कैसे क्लोज़ करते हैं?
पहले नए प्रोड्यूसर्स को रोकें, फिर पब्लिश्ड स्लॉट्स को acquire-observe और ड्रेन करें। कंज्यूमर्स केवल पोजीशन्स के अभिसरण (converge) के बाद ही क्लोज्ड रिटर्न करते हैं और कोई भी प्रोड्यूसर अब रिज़र्व्ड स्लॉट का मालिक नहीं होता है।
फॉलो-अप 5: क्या यह हमेशा लॉक-फ्री होता है?
फास्ट पाथ एक म्यूटेक्स से बचता है, लेकिन atomic::wait एक रनटाइम थ्रेड को ब्लॉक कर सकता है। प्रत्येक पाथ के लॉक-फ्री होने का वादा करने के बजाय इसे वैकल्पिक ब्लॉकिंग वेट्स के साथ एक लॉक-फ्री डेटा संरचना के रूप में सटीक रूप से वर्णित करें।
फॉलो-अप 6: आप ABA जोखिम का परीक्षण कैसे करते हैं?
मोनोटोनिक पोजीशन्स और प्रत्येक स्लॉट में एक राउंड सीक्वेंस का उपयोग करें, फिर रैपअराउंड, विलंबित थ्रेड्स और बार-बार CAS का स्ट्रेस टेस्ट करें। स्लॉट के राउंड आगे बढ़ने के बाद किसी पुराने ऑब्जर्वेशन को दोबारा पात्रता प्राप्त नहीं करनी चाहिए।