कोडिंग साक्षात्कार: एक फेयर, कैंसिलेशन-योग्य सेमाफोर लागू करें

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

कनेक्शन पूल या टास्क एक्ज़ीक्यूटर के लिए एक एसिंक्रोनस सेमाफोर लागू करें। यह क्षमता N से शुरू होता है; कोई परमिट उपलब्ध न होने पर acquire() कतार में लग जाता है, और release() एक वापस करता है। एक वेटर टाइम आउट हो सकता है या रद्द किया जा सकता है। कैंसिलेशन से कोई घोस्ट कतार प्रविष्टि नहीं छूटनी चाहिए या किसी अन्य वेटर की प्रगति में बाधा नहीं आनी चाहिए। डुप्लिकेट रिलीज़, क्लोज़ व्यवहार और निष्पक्षता (fairness) को परिभाषित करें।

यह समवर्तीता (concurrency), रनटाइम और बैकएंड-इन्फ्रास्ट्रक्चर साक्षात्कारों के लिए उपयुक्त है। Oracle का Semaphore API परमिट, वैकल्पिक फेयर FIFO चयन और इंटरप्टिबल अधिग्रहण को परिभाषित करता है। Python का asyncio दस्तावेज़ एक काउंटर का वर्णन करता है जो acquire पर घटता है और release पर बढ़ता है, और सामान्य सेमाफोर को बाउंडेड सेमाफोर से अलग करता है। सार्वजनिक साक्षात्कार चर्चाएं ऑपरेटिंग-सिस्टम साक्षात्कार विषयों के रूप में काउंटिंग सेमाफोर और कॉनकरेंसी सीमाओं को सूचीबद्ध करती हैं। ये स्रोत प्रतिनिधित्व का समर्थन करते हैं, लेकिन किसी निश्चित कंपनी प्रॉम्प्ट या आवृत्ति को स्थापित नहीं करते हैं। श्रेणी coding है क्योंकि मुख्य कौशल स्टेट इनवेरिएंट्स, कतार क्लीनअप, कैंसिलेशन रेस और सत्यापन योग्य समवर्ती कार्यान्वयन हैं।

साक्षात्कारकर्ता क्या मूल्यांकन करते हैं

पहला, क्या उम्मीदवार परमिट के स्वामित्व (ownership) को परिभाषित करता है? एक सफल acquire को एक टोकन बनाना चाहिए जिसे ठीक एक बार वापस किया जा सके। रद्द या टाइम-आउट अनुरोध के पास कोई टोकन नहीं होता है और उसे release को कॉल नहीं करना चाहिए।

दूसरा, क्या निष्पक्षता वास्तविक है? कतार गैर-खाली होने के बाद, एक नई रिलीज़ को बाद के तेज़ पथ (fast path) द्वारा हेड को बायपास करने की अनुमति नहीं देनी चाहिए; अन्यथा उच्च लोड पुराने वेटर को भूखा (starve) रख सकता है। FIFO निष्पक्षता के लिए कतार की जाँच करना, परमिट असाइन करना और एक सिंक्रोनाइज़ेशन सीमा के भीतर वेटर को जगाना आवश्यक है।

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

अंत में, क्या परीक्षण केवल अनुक्रमिक acquire/release के बजाय समवर्ती सीमा, FIFO क्रम, टाइमआउट क्लीनअप, कैंसिलेशन के बाद प्रगति, डुप्लिकेट रिलीज़, क्लोज़ और टास्क विफलता की जाँच करते हैं?

पहले पूछे जाने वाले स्पष्टीकरण प्रश्न

• क्या निष्पक्षता सख्त FIFO है या सर्वोत्तम प्रयास (best effort)? सख्त FIFO भुखमरी (starvation) से बचाता है लेकिन थ्रूपुट का त्याग कर सकता है।
• acquire क्या लौटाता है? एक रिलीज़ टोकन या लीज़ (lease) स्वामित्व को एक सफल अधिग्रहण से बांधता है और आकस्मिक रिलीज़ को कम करता है।
• यदि परमिट असाइन होने के बाद कैंसिलेशन होता है तो क्या होगा? पूर्णता प्राथमिकता को परिभाषित करें; एक बार प्रॉमिस हल हो जाने के बाद, कॉलर लीज़ का मालिक होता है और कैंसिलेशन केवल बाद के काम को प्रभावित करता है।
• क्या acquire से अधिक बार release करना एक त्रुटि है? एक बाउंडेड सेमाफोर को इसे अस्वीकार या रिपोर्ट करना चाहिए; चुपचाप गिनती बढ़ाना क्षमता का उल्लंघन करता है।
• close वेटर्स को कैसे समाप्त करता है? Close नए अनुरोधों को अस्वीकार करता है और कतारबद्ध वेटर्स को एक स्पष्ट Closed त्रुटि के साथ समाप्त करता है; धारित लीज़ अभी भी सुरक्षित रूप से रिलीज़ हो सकती हैं।

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

"मैं available, एक FIFO वेटर कतार और एक क्लोज़्ड स्टेट बनाए रखता हूँ, जिसमें प्रत्येक म्यूटेशन एक क्रिटिकल सेक्शन में होता है। Acquire तेज़ पथ केवल तभी ले सकता है जब कतार खाली हो; वेटर्स मौजूद होने पर बाद के कॉलर कतारबद्ध हो जाते हैं। Release पहले सक्रिय वेटर को ढूंढता है, एक परमिट ट्रांसफर करता है, और इसे एक बार पूरा करता है; केवल तभी जब कोई सक्रिय वेटर मौजूद न हो, यह available को बढ़ाता है। प्रत्येक वेटर के पास कैंसिलेशन स्थिति और वन-शॉट पूर्णता होती है। टाइमआउट और रिलीज़ उसी स्थिति पर रेस करते हैं। सफल acquire एक लीज़ लौटाता है जो एक बार रिलीज़ हो सकती है। परीक्षण FIFO, एक ही सीमा पर कैंसिलेशन और रिलीज़, टाइमआउट के बाद परमिट रिकवरी, डुप्लिकेट रिलीज़, क्लोज़ और समवर्ती सीमा को लागू करते हैं।"

गहन उत्तर

1. मुख्य इनवेरिएंट बताएं

क्षमता N के लिए, available + held + reserved = N बनाए रखें। available को तुरंत सौंपा जा सकता है, held लीज़ के माध्यम से कॉलर्स का है, और reserved उपलब्ध से एक चयनित वेटर के पास चला गया है जिसका कॉलबैक अभी तक पूरा नहीं हुआ है।

प्रत्येक वेटर की ठीक एक अंतिम स्थिति होती है: लंबित (pending), पूर्ण (fulfilled), या रद्द (cancelled)। एक रद्द वेटर के पास कोई परमिट नहीं होता है; एक पूर्ण वेटर को एक लीज़ का उत्पादन करना चाहिए। क्लोज़ करने से धारित लीज़ वापस नहीं ली जाती हैं, लेकिन यह नए अधिग्रहणों को रोकता है।

2. फेयर फ़ास्ट पाथ और कतार

जब waiters खाली हो और सेमाफोर खुला हो, तो acquire सीधे available का उपभोग कर सकता है। जब कतार गैर-खाली होती है, भले ही available > 0 हो, एक नया कॉलर कतार में लग जाता है; अन्यथा यह एक पुराने कॉलर को बायपास कर देता है। Acquire और release को एक ही सिंक्रोनाइज़ेशन सीमा के तहत कतार की जाँच करनी चाहिए।

एक कतार नोड वेटर प्रॉमिस, कैंसिलेशन स्थिति, टाइमर हैंडल और वन-शॉट पूर्णता फ़ंक्शन को संग्रहीत करता है। पूर्ण या रद्द किए गए नोड्स को हटाएं, या टॉम्बस्टोन (tombstones) बनाए रखें जिन्हें release हेड पर लेज़ी तरीके से छोड़ देता है। दोनों में से किसी भी रणनीति को यह साबित करने की आवश्यकता है कि कोई सक्रिय वेटर अमान्य नोड्स के पीछे स्थायी रूप से नहीं रह सकता है।

3. release में परमिट ट्रांसफर करें

Release पहले सत्यापित करता है कि लीज़ पहले से रिलीज़ नहीं की गई है, फिर पहले सक्रिय वेटर को परमिट देता है। परमिट held से reserved में बदल जाता है और वेटर की पूर्णता को इनवोक किया जाता है; available को न बढ़ाएं और एसिंक्रोनस रूप से खोज न करें, क्योंकि एक नया acquire लाइन में आगे आ सकता है।

यदि हेड रद्द हो गया है, तो उसे छोड़ दें और साफ़ करें, और अगले वेटर पर जाएं। केवल तभी जब कोई सक्रिय वेटर मौजूद न हो, available += 1 होना चाहिए। एक बाउंडेड सेमाफोर N से परे रिलीज़ को अस्वीकार करता है ताकि कॉलर बग किसी लीक या दोहरी वापसी को छिपा न सके।

4. कैंसिलेशन और टाइमआउट रेस

कैंसिलेशन और रिलीज़ दोनों एक ही वेटर को पूरा करने का प्रयास कर सकते हैं। वन-शॉट CAS, इन-लॉक स्टेट चेक या समकक्ष तंत्र का उपयोग करें ताकि केवल एक ही जीते। यदि कैंसिलेशन जीतता है, तो available को बदले बिना वेटर को हटा दें क्योंकि उसके पास कभी परमिट नहीं था। यदि release ने पहले ही एक परमिट आरक्षित कर लिया है, तो कैंसिलेशन इसे वापस नहीं कर सकता और release को उसी वेटर को पूरा करने नहीं दे सकता।

एक सरल नियम यह है कि release वेटर को हल (resolve) करने से पहले क्रिटिकल सेक्शन के अंदर fulfilled के रूप में चिह्नित करे। एक बार पूर्ण होने पर, टाइमआउट केवल यह रिकॉर्ड कर सकता है कि कॉलर ने बाद के काम को छोड़ दिया; कॉलर अभी भी प्राप्त लीज़ को रिलीज़ करता है। एक अधिक विस्तृत डिज़ाइन एक बिना डिलीवर किए गए आरक्षण को पुनः प्राप्त कर सकता है, लेकिन वह पुनर्प्राप्ति अस्वीकृत प्रॉमिस से अनुमान लगाने के बजाय उसी स्टेट मशीन से संबंधित होनी चाहिए।

5. लीज़ और डुप्लिकेट रिलीज़

released फ़्लैग के साथ एक लीज़ लौटाएं। lease.release() एक बार false से true में परिवर्तित हो सकता है। एक डुप्लिकेट कॉल एक आइडम्पोटेंट (idempotent) परिणाम या एक स्पष्ट त्रुटि लौटाती है; यह दो परमिट नहीं जोड़ सकती। मनमाने कॉलर्स के लिए एक सामान्य release विधि को उजागर करने से स्वामित्व जुड़ाव खो जाता है जब तक कि API स्पष्ट रूप से कॉलर-स्वामित्व वाले काउंटिंग मॉडल का उपयोग न करे।

6. क्लोज़, विफलता और बैकप्रेशर

क्लोज़ के बाद, नए acquires को अस्वीकार करें और कतारबद्ध वेटर्स को Closed के साथ समाप्त करें। लीज़ रखने वाले कार्य समाप्त हो सकते हैं और रिलीज़ कर सकते हैं; केवल इसलिए कि सेमाफोर बंद है, release को परमिट नहीं छोड़ना चाहिए, अन्यथा held की गिनती अस्पष्ट हो जाती है। टास्क विफलताएं अभी भी finally में रिलीज़ होती हैं।

एक सेमाफोर समवर्तीता को सीमित करता है, कतार की लंबाई को नहीं। एक अनबाउंडेड वेटर कतार बैकप्रेशर को मेमोरी वृद्धि में बदल देती है। प्रोडक्शन कोड को अधिकतम प्रतीक्षा संख्या, टाइमआउट या अस्वीकृति नीति निर्धारित करनी चाहिए, और प्रतीक्षा अवधि, कैंसिलेशन दर और कतार की गहराई को रिकॉर्ड करना चाहिए।

7. शेड्यूलर के साथ रेस को नियंत्रित करें

वास्तविक स्लीप (sleeps) के साथ रेस को साबित न करें। कतार में लगने, वेटर का चयन करने वाले release, और टाइमआउट कॉलबैक के कतारबद्ध होने लेकिन अभी तक निष्पादित नहीं होने पर रुकने के लिए एक मैन्युअल क्लॉक और नियंत्रणीय शेड्यूलर का उपयोग करें। प्रत्येक चरण पर available, held, सक्रिय वेटर गिनती और लीज़ स्वामित्व का दावा (assert) करें।

अमान्य N=0 आरंभीकरण, N=1 के साथ सख्त FIFO, कई परमिट, हेड और मध्य वेटर का कैंसिलेशन, एक ही सीमा पर टाइमआउट और रिलीज़, डुप्लिकेट रिलीज़, क्लोज़ से पहले और बाद में acquire, टास्क विफलता, और लंबे समय से प्रतीक्षा कर रहे कॉलर के लिए भुखमरी की अनुपस्थिति को कवर करें।

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

"मैं परमिट स्वामित्व को एक लीज़ में समाहित (encapsulate) करता हूँ। सेमाफोर available, FIFO वेटर्स और क्लोज़्ड स्थिति को संग्रहीत करता है, और सभी ट्रांज़िशन एक सिंक्रोनाइज़ेशन सीमा साझा करते हैं। Acquire तेज़ पथ केवल तभी लेता है जब कतार खाली हो; एक बार वेटर मौजूद होने पर, बाद के कॉल कतारबद्ध हो जाते हैं।

Release सत्यापित करता है कि लीज़ एक बार रिलीज़ हुई है, पहला सक्रिय वेटर ढूंढता है, held को उस वेटर के आरक्षण में स्थानांतरित करता है, और इसे एक बार पूरा करता है। यह रद्द किए गए हेड्स को छोड़ देता है और साफ़ करता है; केवल सक्रिय वेटर न होने पर ही यह available बढ़ाता है। कैंसिलेशन और टाइमआउट उसी वेटर स्थिति पर release के साथ रेस करते हैं, और एक वन-शॉट ट्रांज़िशन विजेता चुनता है। Acquire से पहले कैंसिलेशन के पास कोई परमिट नहीं होता है, जबकि एक पूर्ण acquire कॉलर को एक लीज़ देता है जिसे कैंसिलेशन प्रतिस्थापित नहीं कर सकता है।

Close नए अनुरोधों को अस्वीकार करता है और कतारबद्ध वेटर्स को समाप्त करता है, जबकि धारित लीज़ अभी भी रिलीज़ हो सकती हैं। परीक्षण FIFO, हेड और मध्य कैंसिलेशन, एक साथ टाइमआउट और रिलीज़, डुप्लिकेट रिलीज़, विफलता के बाद finally क्लीनअप और समवर्ती सीमा को लागू करने के लिए मैन्युअल क्लॉक और शेड्यूलर का उपयोग करते हैं। काउंटर इनवेरिएंट साबित करता है कि कोई परमिट खोया या बनाया नहीं गया है।"

सामान्य गलतियाँ

• कतार गैर-खाली होने पर तेज़ पथ लेना → नए कॉलर पुराने कॉलर को बायपास करते हैं और उन्हें भूखा रखते हैं → वेटर्स मौजूद होने तक प्रत्येक कॉलर को कतारबद्ध करें।
• वेटर रद्द होने पर available बढ़ाना → release ने पहले ही इसका परमिट आरक्षित कर लिया होगा → कैंसिलेशन और release को एक वन-शॉट स्थिति पर रेस कराएं।
• बिना स्वामित्व वाला release उजागर करना → डुप्लिकेट कॉल परमिट बनाती हैं → ऐसी लीज़ लौटाएं जो एक बार रिलीज़ हो सके।
• हेड को जगाने से पहले available बढ़ाना → एक नया कॉलर लाइन में आगे आ सकता है → उसी क्रिटिकल सेक्शन के तहत सीधे ट्रांसफर करें।
• टाइमआउट को डिलीवर की गई लीज़ के रोलबैक के रूप में मानना → टास्क अभी भी चल रहा हो सकता है → प्रतीक्षा कैंसिलेशन को अधिग्रहित परमिट से अलग करें।
• अनबाउंडेड कतार की अनुमति देना → समवर्ती सीमा मेमोरी लीक बन जाती है → कतार सीमा, टाइमआउट या अस्वीकृति नीति सेट करें।
• केवल अनुक्रमिक कॉलों का परीक्षण करना → कैंसिलेशन रेस और डुप्लिकेट रिलीज़ छूट जाती हैं → नियंत्रणीय शेड्यूलर के साथ इंटरलीविंग लागू करें।
• क्लोज़ पर धारित परमिट को छोड़ देना → संसाधन गणना अभिसरित (converge) नहीं हो सकती → धारित लीज़ को finally में रिलीज़ होने दें।

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

क्या FIFO निष्पक्षता हमेशा बेहतर होती है?

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

आप एक साथ कई परमिट कैसे प्राप्त करेंगे?

प्रत्येक वेटर की अनुरोधित संख्या रिकॉर्ड करें और इसे केवल तभी पूरा करें जब available पर्याप्त रूप से बड़ा हो। सख्त FIFO एक मल्टी-परमिट हेड के पीछे एक-परमिट अनुरोधों को प्रतीक्षा करवा सकता है; बायपास की अनुमति देने से निष्पक्षता का त्याग होता है। एक नीति चुनें और इनवेरिएंट में वेटर ऑब्जेक्ट्स के बजाय आरक्षित परमिट गिनें।

क्या होगा यदि कोई कार्य अपने काम के बीच में रद्द हो जाता है?

सेमाफोर परमिट का मालिक है, कार्य रुकावट (task interruption) का नहीं। कॉलर को कैंसिलेशन पर काम बंद करना चाहिए और finally में लीज़ रिलीज़ करनी चाहिए; यदि काम बाधित नहीं किया जा सकता है, तो इसे रिलीज़ करने से पहले समाप्त होना चाहिए। सेमाफोर को उस परमिट को पुनः प्राप्त नहीं करना चाहिए जो अभी भी उपयोग में है।

सेमाफोर और म्यूटेक्स के बीच क्या सीमा है?

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