प्रॉम्प्ट और संदर्भ
आपके पास एक उच्च-प्रतिस्पर्धा (high-contention) वाला लॉक-फ्री स्टैक है जिसके नोड्स एक एटॉमिक पॉइंटर द्वारा जुड़े हुए हैं। एक थ्रेड हेड को पढ़ता है और CAS के माध्यम से हटाता है जबकि दूसरा थ्रेड इसे मुक्त कर सकता है। स्टैक के चारों ओर ग्लोबल लॉक के बिना समवर्ती रीडर्स की अनुमति देते हुए, C++26 hazard_pointer मॉडल का उपयोग करके सुरक्षित रिक्लेमेशन डिज़ाइन करें।
साक्षात्कारकर्ता क्या परीक्षण कर रहा है
हैज़र्ड पॉइंटर्स उस पते की सुरक्षा करते हैं जिसे वर्तमान में पढ़ा जा रहा है; वे किसी नोड को हमेशा के लिए जीवित नहीं रखते हैं। एक रीडर एक हैज़र्ड प्रकाशित करता है, पुनः जाँचता है कि एटॉमिक हेड अभी भी उसी नोड को इंगित करता है, और उसके बाद ही इसे डिरेफ़रेंस करता है। हटाया गया नोड एक रिटायर्ड लिस्ट में जाता है और प्रत्येक हैज़र्ड को स्कैन करने के बाद ही रिक्लेम किया जाता है। acquire/release, रजिस्ट्रेशन और एग्जिट, स्कैन लागत, और इस तथ्य को कवर करें कि ABA को अलग सुरक्षा की आवश्यकता होती है।
पहले पूछे जाने वाले स्पष्टीकरण प्रश्न
डेटा संरचना और प्रगति की गारंटी
पुष्टि करें कि क्या यह Treiber स्टैक, लिंक्ड लिस्ट, या हैश बकेट है, क्या लॉक-फ्री या वेट-फ्री प्रगति की आवश्यकता है, और क्या थ्रेड-लोकल रिटायर्ड सूचियाँ स्वीकार्य हैं।
थ्रेड का जीवनकाल
पूछें कि थ्रेड्स हैज़र्ड स्लॉट कैसे प्राप्त करते हैं और एग्जिट सुरक्षा को कैसे साफ़ करता है और रिटायर्ड नोड्स को कैसे स्थानांतरित करता है। क्रैश हुए थ्रेड को स्थायी रूप से गैर-पुनर्प्राप्ति योग्य रिकॉर्ड नहीं छोड़ना चाहिए।
ABA और टैगिंग नीति
निर्धारित करें कि क्या पते पुनः उपयोग किए जा सकते हैं और क्या कोई वर्ज़न काउंटर या टैग किया गया पॉइंटर उपलब्ध है। हैज़र्ड पॉइंटर्स एक संरक्षित नोड को मुक्त होने से रोकते हैं, लेकिन वे स्वयं ABA को गलत तरीके से CAS सफल बनाने से नहीं रोकते हैं।
30-सेकंड उत्तर ढांचा
"रीडर एटॉमिक रूप से head लोड करता है, उस पते को अपने हैज़र्ड स्लॉट में प्रकाशित करता है, और head को फिर से लोड करता है; केवल एक अपरिवर्तित मान को ही डिरेफ़रेंस किया जा सकता है। एक सफल CAS के बाद, पुराना नोड डिलीट होने के बजाय एक रिटायर्ड लिस्ट में चला जाता है। एक स्कैन सभी हैज़र्ड पतों को एकत्र करता है और केवल उस सेट में अनुपस्थित रिटायर्ड नोड्स को रिक्लेम करता है। मेल खाने वाले acquire/release सिमेंटिक्स का उपयोग करें, थ्रेड एग्जिट से पहले स्लॉट को साफ़ करें, और ABA को वर्ज़न या टैग के साथ अलग से संभालें।"
चरण-दर-चरण विस्तृत उत्तर
चरण 1: हैज़र्ड स्लॉट और रिटायर्ड सूचियों को परिभाषित करें
प्रत्येक थ्रेड जो साझा नोड्स को डिरेफ़रेंस कर सकता है, उसके पास एक हैज़र्ड स्लॉट होता है। एक रिटायर्ड लिस्ट डेटा संरचना से हटाए गए नोड्स को रखती है जिन्हें अभी रिक्लेम करना सुरक्षित नहीं है। रजिस्ट्रेशन और स्लॉट का स्वामित्व स्पष्ट होना चाहिए ताकि कोई अस्थायी रॉ पॉइंटर सुरक्षा को बायपास न कर सके।
चरण 2: पब्लिश-एंड-वैलिडेट विंडो स्थापित करें
head लोड करें, इसे release या समकक्ष ऑर्डरिंग के साथ हैज़र्ड स्लॉट में प्रकाशित करें, फिर acquire के साथ head को पुनः लोड करें। फ़ील्ड्स को केवल तभी डिरेफ़रेंस करें जब दोनों मान मेल खाते हों; अन्यथा स्लॉट साफ़ करें और पुनः प्रयास करें। यह उस अंतर को बंद कर देता है जिसमें कोई अन्य थ्रेड नोड को हटा और रिक्लेम कर सकता है।
चरण 3: CAS और रिक्लेमेशन को टालना
next पढ़ें और head पर compare-exchange करें। CAS विफल होने पर, हैज़र्ड साफ़ करें और पुनः प्रयास करें। सफलता पर, पुराने नोड को रिटायर्ड लिस्ट में जोड़ें और स्लॉट को केवल तभी साफ़ करें जब रीडर को नोड की आवश्यकता न रहे। कोई भी पाथ सीधे किसी साझा नोड को डिलीट नहीं कर सकता।
चरण 4: स्कैन और रिक्लेम करें
प्रत्येक थ्रेड के हैज़र्ड स्लॉट को एक संरक्षित-पता सेट में स्कैन करें। रिटायर्ड लिस्ट को ट्रैवर्स करें और केवल उसी नोड्स को रिक्लेम करें जो उस सेट से अनुपस्थित हैं। स्लॉट संख्या और रिटायर्ड-लिस्ट की लंबाई से स्कैन थ्रेशोल्ड को ट्यून करें। एक अनुपालनकारी रीडर का पब्लिश-एंड-वैलिडेट प्रोटोकॉल यह सुनिश्चित करता है कि स्कैन द्वारा उसके हैज़र्ड को देखने से पहले कोई नोड असुरक्षित न हो जाए।
चरण 5: ABA और मेमोरी ऑर्डरिंग को संभालें
आस्थगित रिक्लेमेशन पते के पुनः उपयोग को कम करता है लेकिन ABA को समाप्त नहीं करता है। यदि किसी नोड को जल्दी से हटाया और पुनः डाला जा सकता है, तो वर्ज़न काउंटर, टैग्ड पॉइंटर, या किसी अन्य ABA रक्षा का उपयोग करें। एटॉमिक head, हैज़र्ड स्लॉट्स और नोड फ़ील्ड्स के लिए happens-before संबंध परिभाषित करें; बिना प्रमाण के केवल गति के लिए relaxed ऑपरेशनों का उपयोग नहीं किया जाना चाहिए।
चरण 6: थ्रेड एग्जिट और अपवादों को संभालें
रीडिंग रोकने से पहले हैज़र्ड को साफ़ करें, फिर रिटायर्ड नोड्स को एक लाइव रिक्लेमर या साझा डोमेन में स्थानांतरित करें। रजिस्ट्री को एक स्वामी स्थिति (owner state) की आवश्यकता होती है जो एग्जिट का पता लगा सके और परित्यक्त स्लॉट्स से बच सके। विनाश केवल तभी चलता है जब कोई रीडर नोड तक नहीं पहुँच सकता; सामान्य ऑब्जेक्ट-लाइफटाइम धारणाएं अपर्याप्त हैं।
चरण 7: सुरक्षा और प्रदर्शन का परीक्षण करें
CAS विफलता, समवर्ती स्कैन, थ्रेड एग्जिट, पुनः उपयोग और अपवादों के लिए ThreadSanitizer, रैंडमाइज्ड शेड्यूलिंग और स्ट्रेस टेस्ट का उपयोग करें। use-after-free का पता लगाने के लिए विलंबित-मुक्त सेंटिनल्स जोड़ें। स्कैन समय, रिटायर्ड-लिस्ट पीक, थ्रूपुट और टेल लेटेंसी को मापें, फिर ग्लोबल लॉक जोड़ने के बजाय बैच थ्रेशोल्ड को ट्यून करें।
उच्च गुणवत्ता वाला नमूना उत्तर
मैं प्रत्येक रीडर को एक हैज़र्ड स्लॉट दूंगा। pop head लोड करता है, हैज़र्ड प्रकाशित करता है, head को पुनः लोड करता है, और केवल तभी next पढ़ता है और CAS का प्रयास करता है; बदला हुआ मान स्लॉट को साफ़ करता है और पुनः प्रयास करता है। एक सफल निष्कासन एक रिटायर्ड लिस्ट में प्रवेश करता है, और सभी हैज़र्ड पतों का एक स्कैन केवल असुरक्षित नोड्स को पुनः प्राप्त करता है। थ्रेड एग्जिट अपने स्लॉट को साफ़ और स्थानांतरित करता है। ABA अलग से एक वर्ज़न या टैग किए गए पॉइंटर का उपयोग करता है। परीक्षण use-after-free और स्कैन लागत की जाँच करते हुए विवाद (contention), CAS विफलताओं, पुनः उपयोग, निकास और अपवादों को कवर करते हैं।
सामान्य गलतियाँ
- गलती: पहले लोड के तुरंत बाद head को डिरेफ़रेंस करना। → यह क्यों विफल होता है: सुरक्षा प्रकाशित होने से पहले नोड को रिक्लेम किया जा सकता है। → समाधान: हैज़र्ड प्रकाशित करें और head को फिर से सत्यापित करें।
- गलती: सफल CAS के बाद डिलीट करना। → यह क्यों विफल होता है: कोई अन्य रीडर अभी भी अपनी सुरक्षा विंडो में हो सकता है। → समाधान: पहले रिटायर करें, स्कैन करें, फिर रिक्लेम करें।
- गलती: यह मान लेना कि हैज़र्ड पॉइंटर्स ABA को हल करते हैं। → यह क्यों विफल होता है: विलंबित रिक्लेमेशन लॉजिकल वर्ज़न स्थिरता की गारंटी नहीं देता है। → समाधान: एक वर्ज़न काउंटर या टैग्ड पॉइंटर जोड़ें।
- गलती: केवल relaxed एटॉमिक्स का उपयोग करना। → यह क्यों विफल होता है: प्रकाशन और सत्यापन आवश्यक क्रम में दिखाई नहीं दे सकते हैं। → समाधान: acquire/release और happens-before संबंधों को सिद्ध करें।
फॉलो-अप प्रश्न और उत्तर
फॉलो-अप 1: प्रकाशित करने के बाद head को पुनः लोड क्यों करें?
पहले लोड और हैज़र्ड प्रकाशित करने के बीच एक विंडो होती है जिसमें कोई अन्य थ्रेड नोड को हटा और रिक्लेम कर सकता है। पुनः लोड यह साबित करता है कि नोड अभी भी सुरक्षा के तहत वर्तमान head है; अन्यथा पुनः प्रयास करें।
फॉलो-अप 2: क्या कोई स्कैन, स्कैन के दौरान प्रकाशित हैज़र्ड को छोड़ सकता है?
प्रोटोकॉल के लिए आवश्यक है कि रीडर सत्यापन से पहले प्रकाशित करे और सत्यापन विफल होने पर पुनः प्रयास करे। उस प्रोटोकॉल के साथ, संरक्षित सेट में अनुपस्थित केवल रिटायर्ड नोड्स को ही रिक्लेम किया जाता है; एक असुरक्षित रॉ-पॉइंटर रीडर गारंटी से बाहर है।
फॉलो-अप 3: क्या रिटायर्ड लिस्ट असीमित रूप से बढ़ सकती है?
यह तब बढ़ सकती है जब रीडर्स लंबे समय तक हैज़र्ड बनाए रखते हैं, कोई थ्रेड रुक जाता है, या स्कैन बहुत कम होते हैं। थ्रेशोल्ड सेट करें, पीक की निगरानी करें, एग्जिट पर क्लीनअप करें, और आवश्यकता पड़ने पर रिक्लेमर को सक्रिय रूप से स्कैन करने दें।
फॉलो-अप 4: epoch-based reclamation की तुलना में हैज़र्ड पॉइंटर्स को कब चुनें?
हैज़र्ड पॉइंटर्स सटीक रूप से कम संख्या में पतों की सुरक्षा करते हैं और डायनामिक रीड पाथ के अनुकूल होते हैं, लेकिन स्लॉट को स्कैन करने में CPU खर्च होता है। Epoch रिक्लेमेशन कुशलतापूर्वक बैच करता है लेकिन एक रुके हुए थ्रेड द्वारा रोका जा सकता है। रीडर काउंट, स्टाल टॉलरेंस और मेमोरी सीमाओं के आधार पर चयन करें।