कोडिंग इंटरव्यू: एक बाउंडेड SPSC लॉक-फ्री रिंग बफ़र लागू करें

प्रॉम्प्ट और संदर्भ

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

इंटरव्यूअर क्या जांच रहा है

मुख्य बात कॉनक्रेन्सी इनवेरिएंट्स और ट्रेड-ऑफ्स हैं। प्रोड्यूसर को केवल अपना tail लिखना चाहिए और कंज्यूमर को केवल अपना head; प्रत्येक दूसरे इंडेक्स को पढ़ता है और "डेटा लिखें, फिर इंडेक्स प्रकाशित करें" का happens-before संबंध स्थापित करने के लिए एटॉमिक्स का उपयोग करता है। cppreference एक release स्टोर और एक acquire लोड के बीच सिंक्रोनाइज़ेशन संबंध का विवरण देता है; जावा VarHandle भी इसी तरह acquire, release और volatile एक्सेस मोड में अंतर करता है।

पहले पूछने योग्य स्पष्टीकरण प्रश्न

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

30-सेकंड का उत्तर ढांचा

कहें: "मैं मोनोटोनिक रूप से बढ़ने वाले head और tail काउंटरों को बनाए रखता हूँ और मॉड्यूलो का उपयोग करके उन्हें स्लॉट में मैप करता हूँ। प्रोड्यूसर अपने स्थानीय tail और कंज्यूमर के प्रकाशित head को पढ़ता है, स्पेस की जांच करता है, स्लॉट में लिखता है, फिर release के साथ नए tail को प्रकाशित करता है। कंज्यूमर tail को acquire-लोड करता है, गैर-खाली होने की जांच करता है, तत्व को मूव करता है, फिर release के साथ नए head को प्रकाशित करता है। मॉड्यूलो गैर-दो-की-घात क्षमताओं को संभालता है; परीक्षण रैपअराउंड, फुल/एम्प्टी सीमाओं और विजिबिलिटी को कवर करते हैं।"

चरण-दर-चरण गहन विश्लेषण

1. इनवेरिएंट्स को स्पष्ट करें

पर्याप्त रूप से विस्तृत अनसाइंड काउंटरों और प्राकृतिक रैपअराउंड को मानते हुए, भरी हुई प्रविष्टियों की संख्या के रूप में tail - head का उपयोग करें। प्रोड्यूसर को कभी भी अंतर को क्षमता से अधिक नहीं होने देना चाहिए; कंज्यूमर को कभी भी head != tail से बाहर नहीं पढ़ना चाहिए। प्रत्येक स्लॉट को उपभोग किए जाने से पहले प्रोड्यूसर द्वारा एक बार लिखा जाता है।

2. स्थानीय और साझा इंडेक्स को अलग करें

प्रोड्यूसर अक्सर tail को अपडेट करता है, और कंज्यूमर अक्सर head को अपडेट करता है; प्रत्येक अपने इंडेक्स को एक सामान्य स्थानीय वेरिएबल में रख सकता है। थ्रेड्स के बीच दूसरे इंडेक्स को पढ़ने के लिए acquire का उपयोग किया जाता है, जबकि अपने नए इंडेक्स को प्रकाशित करने के लिए release का उपयोग किया जाता है, जिससे एक ही काउंटर पर राइट रेस से बचा जा सकता है।

3. पुश क्रम में प्रकाशित करें

प्रोड्यूसर कंज्यूमर के head को लोड करता है और tail - head < capacity की जांच करता है। यह buffer[tail % capacity] लिखता है, फिर नए tail को release-स्टोर करता है। कंज्यूमर उस स्लॉट को तभी पढ़ सकता है जब एक acquire लोड नए tail को देख ले।

4. पॉप क्रम में रिक्लेम करें

कंज्यूमर प्रोड्यूसर के प्रकाशित tail को लोड करता है और head != tail की जांच करता है। स्लॉट मान को मूव करने के बाद, यह नए head को release-स्टोर करता है। प्रोड्यूसर उस स्लॉट का पुन: उपयोग तभी कर सकता है जब एक acquire लोड नए head को देख ले।

5. क्षमता और रैपअराउंड को संभालें

दो की घात वाली क्षमता बिट मास्क का उपयोग कर सकती है, लेकिन कार्यान्वयन में इसके ओवरफ्लो और चौड़ाई की मान्यताओं को बताया जाना चाहिए। एक सामान्य क्षमता के लिए, % capacity को सत्यापित करना आसान है। लंबे समय तक चलने वाले काउंटरों के लिए, एक विस्तृत अनसाइंड प्रकार का उपयोग करें और इंडेक्स को एक छोटे इंटीजर में काटने के बजाय अंतर की तुलना करें।

6. विफलता, लाइफटाइम और परीक्षणों को परिभाषित करें

फुल होने पर false और एम्प्टी होने पर empty लौटाएं; स्पिन न करें। यदि किसी तत्व को लिखना विफल हो जाता है, तो tail प्रकाशित न करें; किसी तत्व को मूव करने या नष्ट करने के लिए एक स्पष्ट प्रकार की बाधा या रिकवरी नियम की आवश्यकता होती है। क्षमता एक, क्षमता प्लस एक, बार-बार रैपअराउंड, असंतुलित प्रोड्यूसर और कंज्यूमर गति, फुल/एम्प्टी किनारों और शटडाउन पर शेष तत्वों का परीक्षण करें।

उच्च गुणवत्ता वाला नमूना उत्तर

push(x):
  t = tail.load(relaxed)
  h = head.load(acquire)
  if t - h == capacity: return false
  buffer[t % capacity] = x
  tail.store(t + 1, release)
  return true

pop():
  h = head.load(relaxed)
  t = tail.load(acquire)
  if h == t: return empty
  x = move(buffer[h % capacity])
  head.store(h + 1, release)
  return x

head और tail एटॉमिक काउंटर हैं; प्रोड्यूसर केवल tail लिखता है, और कंज्यूमर केवल head लिखता है। साधारण बफ़र राइट tail के release प्रकाशन से पहले होता है (happens-before), इसलिए कंज्यूमर का acquire लोड तत्व को दृश्यमान बनाता है। head का विपरीत release प्रोड्यूसर को सुरक्षित रूप से स्लॉट का पुन: उपयोग करने की अनुमति देता है। गैर-दो-की-घात क्षमता के लिए मॉड्यूलो का उपयोग करें और अतिरिक्त दो की घात और ओवरफ्लो मान्यताओं के साथ ही मास्क का उपयोग करें। यह संस्करण SPSC है, सामान्य मल्टी-राइटर या मल्टी-रीडर क्यू नहीं।

सामान्य गलतियाँ और सुधार

• दोनों थ्रेड एक ही इंडेक्स लिखते हैं: SPSC ओनरशिप बताएं और बाधा बदलने पर समर्पित MPSC/MPMC एल्गोरिदम पर स्विच करें।
• तत्व लिखने से पहले प्रकाशित करना: पहले स्लॉट में लिखें और अंत में इंडेक्स को release-पब्लिश करें।
• हर जगह relaxed का उपयोग करना: Relaxed एटॉमिकिटी देता है, सामान्य डेटा का प्रकाशन नहीं; क्रॉस-थ्रेड इंडेक्स को acquire/release की आवश्यकता होती है।
• यह मान लेना कि प्रत्येक क्षमता दो की घात है: असत्यापित मास्क के बजाय सामान्य क्षमताओं के लिए मॉड्यूलो का उपयोग करें।

फॉलो-अप प्रश्न और उत्तर

स्थानीय इंडेक्स रीड्स relaxed का उपयोग क्यों कर सकते हैं?

प्रोड्यूसर केवल अपने tail को संशोधित करता है और कंज्यूमर केवल अपने head को, इसलिए स्थानीय रीड्स दूसरे थ्रेड के साथ सिंक्रोनाइज़ नहीं होते हैं। दूसरे इंडेक्स को पढ़ने के लिए अभी भी acquire की आवश्यकता होती है क्योंकि यह विजिबिलिटी भी प्रदान करता है।

एक रेफरेंस-वैल्यूड स्लॉट का पुन: उपयोग कब किया जा सकता है?

केवल तब जब कंज्यूमर मान को मूव या नष्ट करना समाप्त कर लेता है और नए head को release-पब्लिश करता है। स्लॉट को ओवरराइट करने से पहले प्रोड्यूसर उस मान को acquire-लोड करता है; कंज्यूमर को शुरू होते देखना पर्याप्त नहीं है।

आप इसे कई प्रोड्यूसर्स के लिए कैसे विस्तारित करेंगे?

कई प्रोड्यूसर्स सीधे एक ही tail पर नहीं लिख सकते हैं। आपको CAS-आधारित अनुक्रम आरक्षण, प्रति-स्लॉट अनुक्रम संख्या, या एक लॉक की आवश्यकता होगी, और आरक्षण, प्रकाशन और रिक्लेमेशन क्रम को फिर से साबित करना होगा। SPSC कोड को एक सामान्य क्यू के रूप में प्रस्तुत न करें।

आपको कैसे पता चलेगा कि अनुकूलन तेज़ है?

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