प्रॉम्प्ट और उपयोग के मामले
एक थ्रेड-सुरक्षित रीड-राइट लॉक लागू करें: कई रीडर्स इसे एक साथ रख सकते हैं, जबकि एक राइटर को इसे विशेष रूप से रखना चाहिए। प्रतीक्षा नीति, वेक-अप नियम, री-एंट्रेंसी, और आप अनिश्चितकालीन राइटर भुखमरी को कैसे रोकते हैं, इसकी व्याख्या करें। आप एक म्यूटेक्स और कंडीशन वेरिएबल्स का उपयोग कर सकते हैं, लेकिन बिल्ट-इन रीड-राइट लॉक का नहीं।
यह प्रश्न बैकएंड, इंफ्रास्ट्रक्चर और कॉनक्रेन्सी (concurrency) भूमिकाओं के लिए उपयुक्त है। यह किसी विशेष प्रोग्रामिंग भाषा के बजाय सिंक्रोनाइज़ेशन इनवेरिएंट्स और ट्रेड-ऑफ का परीक्षण करता है।
इंटरव्यूअर क्या मूल्यांकन करता है
- क्या आप पहले इनवेरिएंट्स को परिभाषित करते हैं: अधिकतम एक सक्रिय राइटर, और जब कोई राइटर लॉक रखता है तो कोई सक्रिय रीडर नहीं।
- क्या "निष्पक्षता" (fairness) एक निष्पादन योग्य प्रवेश नियम बन जाती है।
- क्या आप स्पुरियस वेक-अप (spurious wakeups), असाधारण पथों, पुनरावर्ती अधिग्रहण (recursive acquisition), और अपग्रेड डेडलॉक को संभालते हैं।
- क्या आप जटिलता, परीक्षण और प्रोडक्शन स्टैंडर्ड लाइब्रेरी का पुन: उपयोग करने के लिए एक सीमा प्रदान करते हैं।
उत्तर देने से पहले स्पष्टीकरण
पुष्टि करें कि क्या अधिग्रहण इंटरप्टिबल या समयबद्ध (timed) होना चाहिए, क्या कोई थ्रेड पुन: प्रवेश (re-enter) कर सकता है, क्या रीड-टू-राइट अपग्रेड आवश्यक है, और क्या निष्पक्षता का अर्थ सख्त FIFO है या राइटर की अंतिम प्रगति। यदि अनिर्दिष्ट है, तो एक न्यूनतम गैर-पुनःप्रवेशी (non-reentrant), गैर-अपग्रेड करने योग्य, राइटर-प्राथमिकता वाला डिज़ाइन प्रस्तावित करें और उस सीमा को स्पष्ट रूप से बताएं।
30-सेकंड का उत्तर
स्टेट का नाम दें: activeReaders, activeWriter, और waitingWriters। एक रीडर केवल तभी प्रवेश करता है जब कोई राइटर न हो और कोई कतारबद्ध राइटर न हो; एक राइटर केवल तभी प्रवेश करता है जब दोनों सक्रिय गणनाएं खाली हों। प्रत्येक स्टेट परिवर्तन को एक म्यूटेक्स से सुरक्षित रखें, और रिलीज़ होने पर या तो एक राइटर को या एक रीडर समूह को जगाएं। प्रत्येक कंडीशन-वेरिएबल वेक-अप के बाद एक while लूप में प्रेडिकेट्स की पुनः जांच करें। रीड-टू-राइट अपग्रेड को तब तक प्रतिबंधित करें जब तक कि API एक स्पष्ट प्रोटोकॉल को परिभाषित न करे।
चरण-दर-चरण समाधान
स्टेट और इनवेरिएंट्स
activeWriter एक बूलियन है, activeReaders एक गैर-ऋणात्मक गणना है, और waitingWriters कतारबद्ध राइटर्स की गणना करता है। मुख्य इनवेरिएंट यह है कि activeWriter == true का तात्पर्य activeReaders == 0 है; एक राइटर केवल तभी प्रवेश कर सकता है जब दोनों खाली हों। प्रतीक्षा गणना नीति को नियंत्रित करती है और इसका मतलब यह नहीं है कि लॉक अधिग्रहित है।
अधिग्रहण और रिलीज
एक रीडर !activeWriter && waitingWriters == 0 की प्रतीक्षा करता है; एक राइटर !activeWriter && activeReaders == 0 की प्रतीक्षा करता है। स्पुरियस वेक-अप को संभालने के लिए प्रत्येक कंडीशन-वेरिएबल रिटर्न के बाद पुनः जांच करें। राइटर रिलीज पर, यदि कोई कतार में है तो एक राइटर को सिग्नल दें; अन्यथा रीडर्स को ब्रॉडकास्ट करें। जब अंतिम रीडर निकलता है, तो एक राइटर को सिग्नल दें।
~~~text readLock(): mutex.lock() while activeWriter or waitingWriters > 0: readersCondition.wait(mutex) activeReaders += 1 mutex.unlock()
writeLock(): mutex.lock() waitingWriters += 1 while activeWriter or activeReaders > 0: writersCondition.wait(mutex) waitingWriters -= 1 activeWriter = true mutex.unlock()
writeUnlock(): mutex.lock() activeWriter = false if waitingWriters > 0: writersCondition.signal() else: readersCondition.broadcast() mutex.unlock() ~~~
निष्पक्षता और थ्रूपुट
| नीति | रीडर प्रवेश | लाभ | जोखिम |
|---|---|---|---|
| राइटर प्राथमिकता | कोई सक्रिय राइटर नहीं और waitingWriters == 0 | राइटर भुखमरी को सीमित करता है | राइटर बर्स्ट के दौरान रीडर लेटेंसी बढ़ जाती है |
| रीडर प्राथमिकता | कोई सक्रिय राइटर नहीं | उच्च रीड थ्रूपुट | एक राइटर भुखमरी का शिकार हो सकता है |
| अनुमानित FIFO | कतार क्रम में प्रवेश दें | अधिक पूर्वानुमानित लेटेंसी | अधिक स्टेट और कतारबद्ध जटिलता |
Oracle दस्तावेज़ बताता है कि गैर-निष्पक्ष (non-fair) मोड किसी रीडर या राइटर को अनिश्चित काल के लिए स्थगित कर सकता है, जबकि निष्पक्ष (fair) मोड लगभग आगमन-क्रम नीति का उपयोग करता है और आमतौर पर थ्रूपुट का त्याग करता है। साक्षात्कार में "कोई भुखमरी नहीं" और सख्त FIFO के बीच अंतर स्पष्ट करें।
आदर्श उत्तर
मैं एक गैर-पुनःप्रवेशी (non-reentrant), राइटर-प्राथमिकता वाले कार्यान्वयन के साथ शुरुआत करूंगा। एक म्यूटेक्स सभी काउंटरों की सुरक्षा करता है। रीडर्स केवल तभी वृद्धि करते हैं जब कोई सक्रिय या प्रतीक्षारत राइटर न हो; राइटर्स तब तक प्रतीक्षा करते हैं जब तक कि दोनों सक्रिय गणनाएं खाली न हो जाएं। प्रत्येक कंडीशन-वेरिएबल रिटर्न एक while लूप में अपने प्रेडिकेट की पुनः जांच करता है। रिलीज़ पर, जब कोई कतार में हो तो एक राइटर को संकेत दें, अन्यथा रीडर्स को ब्रॉडकास्ट करें। यह एक्सक्लूजन इनवेरिएंट को सुरक्षित रखता है और नए रीडर्स की एक अंतहीन धारा को राइटर से आगे निकलने से रोकता है।
मैं रीड-टू-राइट अपग्रेड को स्पष्ट रूप से अस्वीकार करूंगा: राइट लॉक की प्रतीक्षा कर रहा एक रीडर अन्य रीडर्स को रिलीज़ होने से रोक सकता है और डेडलॉक का कारण बन सकता है। कॉलर को रीड लॉक रिलीज़ करना चाहिए और फिर से प्रतिस्पर्धा करनी चाहिए, या एक अलग कतारबद्ध अपग्रेड प्रोटोकॉल का उपयोग करना चाहिए। रुकावट (interruption), टाइमआउट, री-एंट्रेंसी, डायग्नोस्टिक्स, या सख्त निष्पक्षता के लिए, मैं एक प्रलेखित प्लेटफ़ॉर्म प्रिमिटिव का उपयोग करूंगा और व्यावसायिक कोड में एक अधूरे लॉक की प्रतिलिपि बनाने के बजाय इसके सिमेंटिक्स का परीक्षण करूंगा।
सामान्य गलतियाँ
whileकोifसे बदलना, जिससे एक स्पुरियस वेक-अप प्रेडिकेट को बायपास कर सके।- कतारबद्ध राइटर्स को अनदेखा करना और रीडर्स को हमेशा के लिए प्रवेश देना।
- राइटर रिलीज के बाद केवल एक रीडर को जगाना, या बिना शर्त ब्रॉडकास्ट करना और थंडरिंग हर्ड (thundering herd) की समस्या पैदा करना।
- बिना अपग्रेड कतार के अपग्रेड की अनुमति देना, जिससे दो रीडर्स एक दूसरे का इंतजार करते रहें।
tryLockको निष्पक्षता की गारंटी मानना। Oracle स्पष्ट रूप से नोट करता है कि नॉन-ब्लॉकिंगtryLockबार्ज (barge) कर सकता है।
अनुवर्ती प्रश्न और उत्तर
आप इनवेरिएंट्स का परीक्षण कैसे करते हैं?
एक परमाणु (atomic) परीक्षण स्नैपशॉट रखें: राइटर के प्रवेश पर शून्य रीडर्स और रीडर के प्रवेश पर कोई राइटर न होने का दावा (assert) करें। यादृच्छिक (randomized) रीडर और राइटर थ्रेड्स चलाएं, और जब भी कोई दावा विफल हो तो घटना अनुक्रम रिकॉर्ड करें।
आप राइटर भुखमरी का परीक्षण कैसे करते हैं?
एक राइटर के प्रतीक्षा करने के दौरान लगातार रीडर्स उत्पन्न करें। राइटर के कतार-से-प्रवेश समय और अधिकतम प्रतीक्षा गणना रिकॉर्ड करें। लक्ष्य अंतिम प्रगति है, कोई मनमाना निश्चित मिलीसेकंड वादा नहीं।
एक साधारण म्यूटेक्स का उपयोग क्यों न करें?
एक साधारण म्यूटेक्स सरल होता है और अक्सर इसमें अधिक स्थिर लेटेंसी होती है। एक रीड-राइट लॉक केवल तभी मदद कर सकता है जब रीड्स प्रभावी हों और रीड क्रिटिकल सेक्शन ओवरलैप होने के लिए पर्याप्त लंबे हों। बेंचमार्क के साथ चयन करें, अंतर्ज्ञान से नहीं।
क्या यह पुनःप्रवेशी (reentrant) हो सकता है?
राइटर थ्रेड और होल्ड काउंट, साथ ही प्रति-थ्रेड रीड काउंट को ट्रैक करें। यह अपग्रेड और रिलीज़ नियमों का काफी विस्तार करता है। यदि री-एंट्रेंसी की आवश्यकता नहीं है, तो इसे प्रतिबंधित करने से स्टेट स्पेस छोटा रहता है।
POSIX इस चर्चा में क्या जोड़ता है?
POSIX परिभाषित त्रुटि रिटर्न के साथ अलग-अलग रीड-लॉक और राइट-लॉक संचालन को प्रदर्शित करता है। कार्यान्वयन को अभी भी प्राथमिकता और पुनरावर्ती व्यवहार के लिए प्लेटफ़ॉर्म नियमों का सम्मान करना चाहिए; एक कस्टम नीति को POSIX गारंटी के रूप में प्रस्तुत नहीं किया जाना चाहिए।
आपको इसे स्वयं लिखना कब बंद कर देना चाहिए?
जब रुकावट, टाइमआउट, डायग्नोस्टिक्स, री-एंट्रेंसी, या पोर्टेबिलिटी मायने रखती है, तो जावा ReentrantReadWriteLock या POSIX pthread_rwlock_* जैसे सत्यापित प्रिमिटिव को प्राथमिकता दें, और समीक्षा में निष्पक्षता विकल्प रिकॉर्ड करें।