एक थ्रेड-सुरक्षित बाउंडेड ब्लॉकिंग कतार (Thread-Safe Bounded Blocking Queue) लागू करें

समस्या और यह कब लागू होती है

BoundedBlockingQueue<E> लागू करें। इसका कंस्ट्रक्टर एक सकारात्मक क्षमता (positive capacity) स्वीकार करता है। put(item) FIFO क्रम में जोड़ता है और कतार भरी होने पर प्रतीक्षा करता है। take() हेड से हटाता है और कतार खाली होने पर प्रतीक्षा करता है। कई प्रोड्यूसर्स और कंज्यूमर्स दोनों मेथड्स को समवर्ती रूप से कॉल कर सकते हैं। कोई भी एलिमेंट खोना नहीं चाहिए, दो बार वापस नहीं आना चाहिए, या पहले दर्ज किए गए एलिमेंट के बाद वापस नहीं आना चाहिए। यदि लॉक प्राप्त करते समय या किसी कंडीशन पर प्रतीक्षा करते समय कोई थ्रेड इंटरप्ट हो जाता है, तो मेथड InterruptedException थ्रो करता है।

यह अभ्यास ArrayBlockingQueue को रैप करने की अनुमति नहीं देता है। बेस API नॉन-ब्लॉकिंग offer/poll, टाइमआउट्स, बल्क रिमूवल और शटडाउन सेमेंटिक्स को बाहर रखता है, और यह प्रतीक्षारत थ्रेड्स के बीच सख्त निष्पक्षता (strict fairness) का वादा नहीं करता है। वे फॉलो-अप प्रश्न हैं। Java के BlockingQueue की तरह, यह कार्यान्वयन null को अस्वीकार करता है, क्योंकि कतार API अक्सर यह दर्शाने के लिए null का उपयोग करते हैं कि कोई एलिमेंट उपलब्ध नहीं है।

यह एक समवर्ती डेटा-संरचना (concurrent data-structure) कोडिंग समस्या है। ऐरे इंडेक्सिंग आसान हिस्सा है। असली परीक्षा यह है कि क्या उम्मीदवार एक ऑडिट योग्य अनुबंध (auditable contract) बता सकता है: कौन सा सिंक्रोनाइज़ेशन साझा स्थिति की रक्षा करता है, सूचनाएं (notifications) क्यों नहीं खो सकती हैं, एक जागे हुए थ्रेड को अपनी स्थिति की दोबारा जांच क्यों करनी चाहिए, और किस क्षण कोई ऑपरेशन अन्य थ्रेड्स के लिए प्रभावी होता है।

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

पहला संकेत यह है कि क्या उम्मीदवार सुरक्षा (safety) को सजीवता (liveness) से अलग करता है। सुरक्षा के लिए आवश्यक है कि साइज़ [0, capacity] में रहे, प्रत्येक एलिमेंट को अधिक से अधिक एक बार हटाया जाए, और हटाने का क्रम इंसर्शन क्रम से मेल खाता हो। सजीवता के लिए आवश्यक है कि जब कोई भरी हुई कतार नॉन-फुल हो जाए तो प्रोड्यूसर को आगे बढ़ने का मौका मिले और जब कोई खाली कतार नॉन-एम्प्टी हो जाए तो कंज्यूमर को मौका मिले। इंटरप्शन को प्रतीक्षा रद्द करने में भी सक्षम होना चाहिए।

दूसरा संकेत यह है कि क्या सिंक्रोनाइज़ेशन प्रिमिटिव्स स्थिति विधेय (state predicates) के अनुरूप हैं। एक लॉक ऐरे, हेड, टेल और साइज़ की सुरक्षा करता है, इसलिए किसी कंडीशन की जांच करना और स्थिति बदलना एक ही क्रिटिकल सेक्शन में होता है। notFull, size < capacity का प्रतिनिधित्व करता है; notEmpty, size > 0 का प्रतिनिधित्व करता है। प्रोड्यूसर्स केवल पूर्व की प्रतीक्षा करते हैं, कंज्यूमर्स केवल बाद वाले की प्रतीक्षा करते हैं, और एक सीमा पार करने वाला स्थिति परिवर्तन विपरीत भूमिका को संकेत देता है।

तीसरा संकेत यह है कि क्या उम्मीदवार while को रटे-रटाए पैटर्न के रूप में उपयोग करने के बजाय समझा सकता है। Condition स्पूरियस वेकअप्स (spurious wakeups) की अनुमति देता है। एक वास्तविक signal के बाद भी, दूसरा प्रतिस्पर्धी थ्रेड पहले लॉक को फिर से प्राप्त कर सकता है और कतार को फिर से भर या खाली कर सकता है। एक बार जब जागा हुआ थ्रेड लॉक को फिर से प्राप्त कर लेता है, तो उसे विधेय का पुनः परीक्षण करना चाहिए। सूचित किए जाने से यह साबित नहीं होता कि कंडीशन अभी भी मान्य है।

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

उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न

• कौन सी क्षमताएं और एलिमेंट्स मान्य हैं? क्षमता शून्य से अधिक होनी चाहिए, और null एलिमेंट्स को अस्वीकार कर दिया जाता है।
• क्या फुल या एम्प्टी प्रतीक्षाओं को स्पिन करना चाहिए? नहीं। एक प्रतीक्षारत थ्रेड को लॉक छोड़ना चाहिए और एक कंडीशन पर प्रतीक्षा करनी चाहिए। इसे न तो स्पिन लूप में CPU की खपत करनी चाहिए और न ही लॉक बनाए रखते हुए सोना चाहिए।
• इंटरप्शन को कैसा व्यवहार करना चाहिए? put और take दोनों InterruptedException को प्रसारित (propagate) करते हैं। वे इंटरप्शन को निगलते नहीं हैं या इंटरप्टेड ऑपरेशन के विफल होने के बाद कतार को बदलते नहीं हैं।
• क्या सख्त निष्पक्षता की आवश्यकता है? बेस समस्या में नहीं। डिफ़ॉल्ट गैर-निष्पक्ष ReentrantLock बाद के थ्रेड को पहले लॉक प्राप्त करने की अनुमति दे सकता है। एक निष्पक्ष लॉक थ्रूपुट और शेड्यूलिंग व्यवहार को बदल देता है।
• क्या कतार को शटडाउन की आवश्यकता है? बेस समस्या में नहीं। यदि ऐसा है, तो परिभाषित करें कि क्या मौजूदा आइटम्स को ड्रेन किया जा सकता है, क्या वेटर्स को कोई अपवाद या विशेष परिणाम मिलता है, और सभी वेटर्स को कौन जगाता है।
• क्या लीनियरकृत एलिमेंट FIFO और वेटर FIFO एक ही गारंटी हैं? नहीं। एलिमेंट्स सफल puts के लीनियराइजेशन क्रम में बाहर निकलते हैं। इसका मतलब यह नहीं है कि ब्लॉक किए गए प्रोड्यूसर्स या कंज्यूमर्स को आगमन क्रम में भर्ती किया जाता है।
• क्या एक मानक लाइब्रेरी क्लास का उपयोग किया जा सकता है? प्रोडक्शन कोड को आमतौर पर एक परीक्षण किए गए ArrayBlockingQueue को प्राथमिकता देनी चाहिए। यहाँ हाथ से कार्यान्वयन विशेष रूप से समवर्ती इनवेरिएंट्स और कंडीशन-वेट सेमेंटिक्स का मूल्यांकन करने के लिए है।

30-सेकंड उत्तर रूपरेखा

"मैं एक रिंग बफ़र के रूप में एक निश्चित ऐरे का उपयोग करूँगा, जिसमें head, tail, और size अगली रीड स्थिति, अगली राइट स्थिति और वर्तमान एलिमेंट गणना का प्रतिनिधित्व करते हैं। एक ReentrantLock सभी साझा स्थिति की सुरक्षा करता है, और दो Condition ऑब्जेक्ट्स नॉन-एम्प्टी और नॉन-फुल का प्रतिनिधित्व करते हैं। put, while (size == capacity) के अंदर प्रतीक्षा करता है, इन्सर्ट करता है और size को बढ़ाता है, फिर एक कंज्यूमर को संकेत देता है। take सममित रूप से नॉन-एम्प्टी की प्रतीक्षा करता है, हेड को साफ़ करता है और size को घटाता है, फिर एक प्रोड्यूसर को संकेत देता है। प्रत्येक जांच और ट्रांज़िशन एक ही लॉक के तहत होता है। चूँकि await परमाणु रूप से लॉक जारी करता है और वापस लौटने से पहले इसे फिर से प्राप्त करता है, इसलिए जांचने और सोने के बीच कोई खोई हुई अधिसूचना विंडो (lost-notification window) नहीं होती है। प्रत्येक सफल ऑपरेशन O(1) स्पेस के साथ O(capacity) है।"

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

सरल बाधा (naive bottleneck) से निरूपण निकालें। एक सादा ऐरे जो प्रत्येक निष्कासन के बाद शेष एलिमेंट्स को स्थानांतरित करता है, take को O(n) बनाता है। केवल बढ़ने वाले रीड इंडेक्स को बनाए रखने से रिलीज़ किए गए प्रीफिक्स की बर्बादी होती है। एक निश्चित रिंग ऐरे जारी किए गए स्लॉट्स का पुन: उपयोग करता है: head अगली रीड स्थिति को इंगित करता है, tail अगली राइट स्थिति को इंगित करता है, और size वर्तमान एलिमेंट गणना है। अंत तक पहुँचने के बाद एक इंडेक्स शून्य पर आ जाता है, इसलिए न तो इंसर्शन और न ही रिमूवल मौजूदा एलिमेंट्स को स्थानांतरित करता है।

कार्यान्वयन चार इनवेरिएंट्स को बनाए रखता है:

1. 0 <= size <= items.length.
2. head से शुरू होकर, रिंग क्रम में पहले size स्लॉट्स में अनकंज्यूम्ड FIFO अनुक्रम होता है।
3. tail == (head + size) % items.length. जब कतार भरी होती है, head == tail, इसलिए size भरे हुए को खाली से अलग करता है।
4. items, head, tail, और size का प्रत्येक रीड या राइट एक ही लॉक को होल्ड करते समय होता है।

यहाँ मुख्य कार्यान्वयन दिया गया है:

import java.util.Objects;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

public final class BoundedBlockingQueue<E> {
  private final Object[] items;
  private final ReentrantLock lock = new ReentrantLock();
  private final Condition notEmpty = lock.newCondition();
  private final Condition notFull = lock.newCondition();

  private int head;
  private int tail;
  private int size;

  public BoundedBlockingQueue(int capacity) {
    if (capacity <= 0) {
      throw new IllegalArgumentException("capacity must be positive");
    }
    items = new Object[capacity];
  }

  public void put(E item) throws InterruptedException {
    Objects.requireNonNull(item, "item");
    lock.lockInterruptibly();
    try {
      while (size == items.length) {
        notFull.await();
      }

      items[tail] = item;
      tail = (tail + 1) % items.length;
      size++;
      notEmpty.signal();
    } finally {
      lock.unlock();
    }
  }

  @SuppressWarnings("unchecked")
  public E take() throws InterruptedException {
    lock.lockInterruptibly();
    try {
      while (size == 0) {
        notEmpty.await();
      }

      E item = (E) items[head];
      items[head] = null;
      head = (head + 1) % items.length;
      size--;
      notFull.signal();
      return item;
    } finally {
      lock.unlock();
    }
  }
}

Objects.requireNonNull लॉकिंग से पहले चलता है क्योंकि यह केवल एक तर्क की जाँच करता है और साझा स्थिति पर निर्भर नहीं करता है। lockInterruptibly() लॉक प्राप्त करने की प्रतीक्षा को ही इंटरप्टिबल बनाता है। मेथड द्वारा try में प्रवेश करने के बाद, finally सामान्य रिटर्न, कंडीशन वेट के दौरान इंटरप्शन, या रनटाइम अपवाद पर वर्तमान थ्रेड द्वारा धारित लॉक को रिलीज़ करता है।

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

while दो अलग-अलग मामलों को संभालता है। एक विनिर्देश द्वारा अनुमत स्पूरियस वेकअप है। दूसरा सामान्य प्रतिस्पर्धा है: दो कंज्यूमर्स को जगाया जा सकता है, एक पहले लॉक को फिर से प्राप्त करता है और एकमात्र एलिमेंट को हटा देता है, और दूसरा अंततः लॉक मिलने पर एक खाली कतार पाता है। कंडीशन नोटिफिकेशन केवल यह बताता है कि स्थिति बदल गई होगी; आगे बढ़ने के लिए स्थिति विधेय ही अधिकार है।

एक सफल put का लीनियराइजेशन पॉइंट वह लॉक्ड ट्रांज़िशन है जो एलिमेंट को जोड़ता है और size को k से k + 1 में ले जाता है। take के लिए, यह संबंधित निष्कासन और k से k - 1 में ट्रांज़िशन है। लॉक यह सुनिश्चित करता है कि कोई अन्य थ्रेड या तो ट्रांज़िशन से पहले की पूरी स्थिति या उसके बाद की पूरी स्थिति का निरीक्षण कर सकता है, कभी भी इसके मिलान साइज़ अपडेट के बिना ऐरे राइट नहीं देख सकता। अनलॉक करना और बाद में उसी लॉक को प्राप्त करना मेमोरी विजिबिलिटी भी स्थापित करता है, जो मानक समवर्ती कतारों के माध्यम से एलिमेंट्स को पास करने के लिए निर्दिष्ट हैपन्स-बिफ़ोर (happens-before) लक्ष्य से मेल खाता है।

दो कंडीशंस का उपयोग क्यों करें? एक वेटिंग सेट के साथ, एक take दूसरे कंज्यूमर को जगा सकता है, भले ही कतार खाली रहे, जबकि एक प्रोड्यूसर जो नए स्लॉट का उपयोग कर सकता था, सोता रहता है। notEmpty और notFull को अलग करने से प्रत्येक ट्रांज़िशन केवल उस भूमिका को सूचित करता है जो अब आगे बढ़ सकती है। एक बेस सिंगल-एलिमेंट put या take केवल एक नया एलिमेंट या स्लॉट बनाता है, इसलिए signal() पर्याप्त है; जगाया गया थ्रेड अभी भी while में फिर से जाँच करता है। यदि कोई ऑपरेशन कई स्लॉट्स को बदलता है, या शटडाउन के लिए प्रत्येक वेटर को एक नई स्थिति का निरीक्षण करने की आवश्यकता होती है, तो signalAll() पर पुनर्विचार करें।

शुद्धता इनवेरिएंट्स पर आगमन (induction) द्वारा सिद्ध होती है। प्रारंभ में, head = tail = size = 0। एक इंसर्शन केवल तब चलता है जब size < capacity; यह tail पर लिखता है, टेल को आगे बढ़ाता है, और साइज़ को ठीक एक बार बढ़ाता है, इसलिए यह क्षमता के भीतर रहता है और सभी अनकंज्यूम्ड एलिमेंट्स के बाद जुड़ता है। निष्कासन केवल तब चलता है जब size > 0; यह head पर पढ़ता है, स्लॉट को साफ़ करता है, हेड को आगे बढ़ाता है, और साइज़ को ठीक एक बार घटाता है, इसलिए यह सबसे शुरुआती अनकंज्यूम्ड एलिमेंट को लौटाता है। लॉक इन ट्रांज़िशन्स को क्रमबद्ध करता है, जिससे कई प्रोड्यूसर्स और कंज्यूमर्स का प्रत्येक शेड्यूल किसी कानूनी अनुक्रमिक निष्पादन के समकक्ष बन जाता है।

प्रत्येक सफल put या take एक निश्चित संख्या में ऐरे, पूर्णांक और सिंक्रोनाइज़ेशन ऑपरेशन्स करता है, इसलिए प्रतीक्षा समय को छोड़कर इसका कार्य O(1) है। निश्चित ऐरे O(capacity) स्पेस का उपयोग करता है। कंटेंशन (contention) के तहत, लॉक वेटिंग और कॉन्टेक्स्ट स्विच लेटेंसी पर हावी हो सकते हैं; एसिम्प्टोटिक नोटेशन उस लागत को कैप्चर नहीं करता है। वन-लॉक डिज़ाइन में कोई मल्टी-लॉक चक्र नहीं होता है, लेकिन कॉलर अभी भी एक बड़ी लॉक-ऑर्डर समस्या पैदा कर सकते हैं यदि वे किसी अन्य लॉक को होल्ड करते हुए ब्लॉकिंग मेथड को इनवोक करते हैं।

परीक्षण सिंगल-थ्रेडेड उदाहरण पर नहीं रुक सकता। क्षमता-एक फुल/एम्प्टी प्रत्यावर्तन, कई रिंग रैपअराउंड्स, अलग से संग्रहीत और हटाए जाने वाले समान दोहराए गए एलिमेंट्स, null को अस्वीकार करते समय एक खाली स्ट्रिंग को स्वीकार किया जाना, कई प्रोड्यूसर्स द्वारा उत्पादित और कई कंज्यूमर्स द्वारा निकाले गए अद्वितीय मान, अंतिम सेट में कोई गायब या डुप्लिकेट मान नहीं, प्रत्येक व्यक्तिगत प्रोड्यूसर स्ट्रीम के भीतर संरक्षित क्रम, और ब्लॉक किए गए पुट और ब्लॉक किए गए टेक दोनों का इंटरप्शन शामिल करें। एक बड़ी क्षमता कंस्ट्रक्टर में समान रूप से बड़े ऐरे को आवंटित करती है और मेमोरी की कमी के कारण विफल हो सकती है; बेस कार्यान्वयन लेज़ी नहीं है और आवंटन विफलता को खाली कतार के रूप में प्रच्छन्न नहीं करना चाहिए। समवर्ती परीक्षणों को बैरियर या लैच के साथ शुरुआत का समन्वय करना चाहिए और स्थायी ब्लॉकिंग का पता लगाने के लिए टेस्ट-रनर समय सीमा (deadline) का उपयोग करना चाहिए। एक छोटा sleep इस बात का प्रमाण नहीं है कि कोई थ्रेड अपनी प्रतीक्षा स्थिति में पहुँच गया है।

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

"मैं पहले बेस अनुबंध को सकारात्मक क्षमता, गैर-नल एलिमेंट्स, ब्लॉकिंग put/take, FIFO, कई प्रोड्यूसर्स और कंज्यूमर्स, और इंटरप्टिबल प्रतीक्षाओं तक सीमित करूँगा। टाइमआउट्स, शटडाउन और सख्त निष्पक्षता के लिए अतिरिक्त रिटर्न मान और स्थिति सेमेंटिक्स की आवश्यकता होती है, इसलिए मैं उन्हें मुख्य कार्यान्वयन से बाहर रखूँगा।

प्रतिनिधित्व एक निश्चित रिंग ऐरे है। head अगली रीड स्थिति है, tail अगली राइट स्थिति है, और size तब फुल-बनाम-एम्प्टी अस्पष्टता को दूर करता है जब head == tail। एक ReentrantLock सभी चार साझा फ़ील्ड्स की सुरक्षा करता है। notEmpty के लिए विधेय size > 0 है, और notFull के लिए विधेय size < capacity है।

put इंटरप्टिबल रूप से लॉक प्राप्त करता है, while के अंदर नॉन-फुल की प्रतीक्षा करता है, टेल पर लिखता है और size को बढ़ाता है, फिर एक कंज्यूमर को संकेत देता है। take सममित रूप से नॉन-एम्प्टी की प्रतीक्षा करता है, हेड को हटाता है, संदर्भ को साफ़ करता है और size को घटाता है, फिर एक प्रोड्यूसर को संकेत देता है। लूप की आवश्यकता है क्योंकि कंडीशन वेट्स स्पूरियस रूप से जाग सकते हैं और क्योंकि दूसरा थ्रेड विधेय को फिर से गलत बना सकता है जबकि जागा हुआ थ्रेड लॉक को फिर से प्राप्त करने के लिए प्रतिस्पर्धा कर रहा है।

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

ब्लॉकिंग समय को छोड़कर, दोनों मेथड्स O(1) हैं, और स्पेस O(capacity) है। मैं कई प्रोड्यूसर्स और कंज्यूमर्स को एक लैच के साथ शुरू करूँगा, विशिष्ट पहचानकर्ताओं के सेट और प्रति-प्रोड्यूसर क्रम को सत्यापित करूँगा, और फुल, एम्प्टी और इंटरप्शन पथों का अलग से परीक्षण करूँगा।"

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

• if के साथ फुल या एम्प्टी की जाँच करना → स्पूरियस वेकअप या लॉक प्रतिस्पर्धा के बाद स्थिति अभी भी गलत हो सकती है → while में स्थिति विधेय का पुनः परीक्षण करें।
• जाँच के बाद मैन्युअल रूप से अनलॉक करना और फिर प्रतीक्षा करना → वेटर पंजीकरण से पहले स्थिति में बदलाव हो सकता है, जिससे अधिसूचना खो सकती है → उसी लॉक से जुड़े Condition.await() का उपयोग करें।
• ऐरे, इंडेक्स और size को अलग से सिंक्रोनाइज़ करना → दूसरा थ्रेड एक विरोधाभासी मध्यवर्ती स्थिति देख सकता है → पूरी जाँच और ट्रांज़िशन को एक लॉक से सुरक्षित करें।
• एक मनमाने signal के साथ एक वेट सेट का उपयोग करना → सिग्नल उसी भूमिका वाले थ्रेड को जगा सकता है जो प्रगति नहीं कर सकता है → अलग-अलग notEmpty और notFull कंडीशंस बनाए रखें।
• लॉक होल्ड करते समय स्पिन करना या सोना → वह थ्रेड जो स्थिति को बदल सकता है उसे प्राप्त नहीं कर सकता है → कंडीशन वेट को लॉक रिलीज़ करना चाहिए।
• InterruptedException को निगलना → कॉलर काम रद्द नहीं कर सकते हैं और थ्रेड अनिश्चित काल तक बना रह सकता है → इंटरप्शन घोषित और प्रचारित करें, और finally में अनलॉक करें।
• दोनों स्थितियों का पता लगाने के लिए केवल head == tail का उपयोग करना → पूर्ण और खाली रिंग स्थितियां अप्रभेद्य हैं → एक लॉक-सुरक्षित size बनाए रखें।
• हटाए गए संदर्भ को ऐरे में छोड़ना → ऐरे उपभोग की गई वस्तु को आवश्यकता से अधिक समय तक बनाए रखता है → इसे पढ़ने के बाद स्लॉट को null पर सेट करें।
• एलिमेंट FIFO को थ्रेड निष्पक्षता के साथ जोड़ना → डिफ़ॉल्ट लॉक आगमन क्रम में प्रतीक्षारत कॉल्स को पूरा नहीं करता है → एलिमेंट ऑर्डरिंग और शेड्यूलिंग नीति का अलग से वर्णन करें।
• बेस कार्यान्वयन में शटडाउन समर्थन का दावा करना → वेटर्स के पास कोई देखने योग्य बंद स्थिति नहीं है और वे कभी नहीं जाग सकते हैं → स्थिति और ब्रॉडकास्ट अधिसूचना जोड़ने से पहले शटडाउन अनुबंध को परिभाषित करें।

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

फॉलो-अप 1: आप टाइम्ड offer और poll कैसे जोड़ेंगे?

शेष अवधि को नैनोसेकंड में बदलें और उसी विधेय awaitNanos(remaining) लूप के अंदर while को कॉल करें। प्रत्येक रिटर्न के बाद, इसके द्वारा रिपोर्ट किए गए शेष समय के साथ जारी रखें। यदि मान गैर-सकारात्मक है और विधेय अभी भी गलत है, तो विफलता लौटाएं। प्रत्येक स्पूरियस वेकअप के बाद पूर्ण टाइमआउट का पुन: उपयोग करने से वास्तविक प्रतीक्षा अनिश्चित काल तक बढ़ सकती है। API को टाइमआउट को शून्य एलिमेंट से भी अलग करना चाहिए, null को अस्वीकार करने का एक और कारण।

फॉलो-अप 2: आप shutdown() कैसे लागू करेंगे?

पहले स्टेट मशीन को परिभाषित करें। उदाहरण के लिए, बंद होने के बाद नए पुट्स को अस्वीकार करें लेकिन मौजूदा आइटम्स को ड्रेन होने दें; बंद और खाली होने पर, take एक समर्पित अपवाद थ्रो करता है या एक स्पष्ट परिणाम देता है। shutdown को एक ही लॉक के तहत क्लोज्ड फ्लैग को बदलना होगा और दोनों कंडीशंस पर signalAll() को कॉल करना होगा ताकि प्रत्येक वेटर लॉक को फिर से प्राप्त कर सके और क्लोजर का निरीक्षण कर सके। प्रत्येक वेट-लूप विधेय को एक क्लोज्ड-स्टेट शाखा की आवश्यकता होती है; केवल एक बूलियन फ़ील्ड जोड़ना अपर्याप्त है।

फॉलो-अप 3: यहाँ signal() का उपयोग क्यों करें, और आप signalAll() का उपयोग कब करेंगे?

एक बेस इंसर्शन एक उपभोज्य एलिमेंट बनाता है, और एक निष्कासन एक खाली स्लॉट बनाता है। एक विपरीत भूमिका वाले थ्रेड को जगाना प्रगति करने के लिए पर्याप्त है और व्यर्थ प्रतिस्पर्धा को कम करता है। बल्क इंसर्शन, बल्क रिमूवल, डायनेमिक क्षमता परिवर्तन, या शटडाउन एक साथ कई वेटर्स को पात्र बना सकते हैं, इसलिए उन्हें आमतौर पर signalAll() या स्थिति परिवर्तन से मेल खाने वाले अधिसूचना काउंट की आवश्यकता होती है। जगाए गए लोगों की संख्या की परवाह किए बिना, while पुनः जाँच अनिवार्य रहती है।

फॉलो-अप 4: आप निष्पक्षता कैसे प्रदान करेंगे?

new ReentrantLock(true) लॉक अधिग्रहण को सबसे लंबे समय तक प्रतीक्षारत थ्रेड के पक्ष में बनाता है, लेकिन यह अभी भी put/take के लिए एक पूर्ण वास्तविक समय पूर्णता क्रम प्रदान नहीं करता है; इंटरप्शन और शेड्यूलिंग भी मायने रखते हैं। एक निष्पक्ष नीति आमतौर पर बार्जिंग और भुखमरी के जोखिम को कम करती है लेकिन थ्रूपुट को कम कर सकती है। उस लागत का भुगतान और सत्यापन केवल तभी करें जब कॉलर अनुबंध को वास्तव में वेटर ऑर्डरिंग की आवश्यकता हो।

फॉलो-अप 5: क्या यह लॉक-मुक्त कतार हो सकती है?

एक लॉक-मुक्त बाउंडेड MPMC कतार को आमतौर पर परमाणु अनुक्रम संख्या (atomic sequence numbers), CAS, और बहुत अधिक जटिल मेमोरी-ऑर्डर प्रमाण की आवश्यकता होती है। इसके "ब्लॉकिंग" व्यवहार को अभी भी एक पार्किंग और वेकअप तंत्र की आवश्यकता है; केवल CAS स्पिनिंग एक ब्लॉकिंग कतार नहीं है। डिज़ाइन ABA, फॉल्स शेयरिंग, प्रगति गारंटी और प्लेटफ़ॉर्म मेमोरी-मॉडल चिंताओं को जोड़ता है। जब तक माप यह नहीं दिखाते कि सिंगल लॉक अड़चन है और टीम प्रमाण और तनाव परीक्षणों को बनाए रख सकती है, एक मानक लाइब्रेरी क्लास या स्पष्ट लॉक-आधारित कार्यान्वयन अधिक सुरक्षित है।

फॉलो-अप 6: सीधे दो सेमाफोर का उपयोग क्यों न करें?

एक काउंटिंग सेमाफोर खाली स्लॉट और दूसरा उपलब्ध तत्वों का प्रतिनिधित्व कर सकता है, लेकिन रिंग के head/tail के अपडेट के लिए अभी भी पारस्परिक अपवर्जन (mutual exclusion) की आवश्यकता होती है। कई सिंक्रोनाइज़ेशन प्रिमिटिव्स प्राप्त करने के लिए सावधानीपूर्वक अपवाद, इंटरप्शन और परमिट-रोलबैक हैंडलिंग की भी आवश्यकता होती है। सेमाफोर समाधान सही हो सकता है, लेकिन यह स्वचालित रूप से एक लॉक प्लस दो स्थितियों से छोटा नहीं है। किसी भी डिज़ाइन को यह साबित करना होगा कि परमिट काउंट और वास्तविक ऐरे स्थिति कभी अलग नहीं होते हैं।