प्रॉम्प्ट और संदर्भ
निश्चित N वर्कर्स के साथ एक शेड्यूलर लागू करें। इसका सार्वजनिक API submit(task), shutdown(), और awaitTermination() है। प्रत्येक वर्कर के पास एक deque होता है: ओनर LIFO क्रम में लोकल काम लेता है, जबकि एक निष्क्रिय वर्कर FIFO क्रम में विपरीत छोर से काम स्टील (चोरी) करता है। टास्क और अधिक टास्क बना सकते हैं, लेकिन शटडाउन शुरू होने के बाद नए रूट सबमिशन अस्वीकार कर दिए जाते हैं।
आप म्यूटेक्स-संरक्षित शुद्धता बेसलाइन के साथ शुरुआत कर सकते हैं और फिर समझा सकते हैं कि Chase–Lev-शैली का लॉक-फ्री deque इसे कैसे बदलेगा। शेड्यूलर को किसी टास्क को खोना नहीं चाहिए और न ही दो बार निष्पादित करना चाहिए। टास्क की विफलता से वर्कर लूप बंद नहीं होना चाहिए। खाली कतारों, कोई स्टील विक्टिम न होने, शटडाउन रेस और ब्लॉकिंग वर्कर्स को कवर करें।
इंटरव्यूअर क्या जांच रहा है
एक मजबूत उत्तर केवल "थ्रेड पूल का उपयोग करें" कहने के बजाय ओनर ऑपरेशन्स और स्टील्स के बीच कॉनकरेंसी सीमा को स्पष्ट करता है। लोकल LIFO लोकैलिटी और डेप्थ-फर्स्ट व्यवहार को बनाए रखता है; रिमोट FIFO एक चोर (thief) को पुराना, अक्सर बड़ा काम देता है। इंटरव्यूअर यह भी जांचता है कि क्या सबमिशन, स्वीकृति रोकना, ड्रेनिंग और वर्कर का बाहर निकलना एक स्पष्ट स्टेट मशीन बनाते हैं, और क्या आप उस लीनियराइजेशन पॉइंट की पहचान कर सकते हैं जो टास्क क्लेमिंग को अद्वितीय बनाता है।
स्पष्टीकरण के लिए प्रश्न
- क्या टास्क I/O पर ब्लॉक हो सकते हैं? यदि हाँ, तो एक अलग I/O पूल या काउंटेड ब्लॉकिंग कंपनसेशन का उपयोग करें; जब प्रत्येक वर्कर ब्लॉक हो, तो अधिक स्टीलिंग मदद नहीं कर सकती।
- क्या
submitएक future लौटाता है? यदि हाँ, तो अपवाद प्रसार (exception propagation) और रद्दीकरण को परिभाषित करें; यह उत्तर एक future लौटाता है, जबकि रद्दीकरण केवल यह गारंटी देता है कि जो काम अभी तक क्लेम नहीं किया गया है वह नहीं चलेगा। - क्या deque का लॉक-फ्री और अनबाउंडेड होना आवश्यक है? यदि नहीं, तो पहले लॉक किए गए deque को लागू करें और केवल तभी अपग्रेड करें जब कंटेंशन और रिक्लेमेशन आवश्यकताएं सिद्ध हो जाएं।
- क्या शटडाउन तात्कालिक है या ग्रेसफुल? यह उत्तर ग्रेसफुल है: नए रूट्स को अस्वीकार करें, स्वीकृत काम को ड्रेन करें, फिर बाहर निकलें।
30-सेकंड का उत्तर
मैं प्रत्येक वर्कर को एक deque देता हूँ और ओनर छोर पर LIFO और स्टील छोर पर FIFO का उपयोग करता हूँ। मैं पहले एक लॉक किया हुआ बेसलाइन बनाता हूँ: submit एक कतार का चयन करता है और एक वर्कर को जगाता है; एक वर्कर लोकल काम को पॉप करता है, फिर खाली होने पर अन्य कतारों से स्टील करता है। एक टास्क केवल एक ऑपरेशन द्वारा सफलतापूर्वक हटाए जाने के बाद ही निष्पादित होता है, इसलिए इसे दो बार क्लेम नहीं किया जा सकता है। शटडाउन नए सबमिशन को रोकता है, और वर्कर केवल तभी बाहर निकलते हैं जब शेड्यूलर ड्रेनिंग स्थिति में हो, बकाया काम शून्य हो, और सभी कतारें खाली हों। परीक्षण समवर्ती सबमिट, स्टील रेस, चाइल्ड-टास्क निर्माण, अपवाद, शटडाउन और निष्क्रिय प्रतीक्षा को कवर करते हैं।
चरण-दर-चरण गहन विश्लेषण
अवस्थाएं accepting, draining, और terminated परिभाषित करें। accepting के दौरान, submit हल्के लोड वाले deque पर काम डालता है, बकाया काउंटर को एटॉमिक रूप से बढ़ाता है, और एक वर्कर को जगाता है। draining के दौरान, क्या चल रहे टास्क चिल्ड्रेन बना सकते हैं यह अनुबंध का हिस्सा है; यह संस्करण चिल्ड्रेन की अनुमति देता है और गिनती शून्य तक पहुंचने तक ड्रेन करना जारी रखता है।
type Task = () => void;
class WorkStealingScheduler {
private readonly queues: Array<Deque<Task>>;
private accepting = true;
private outstanding = 0;
submit(task: Task): void {
if (!this.accepting) throw new Error("scheduler is shutting down");
const queue = this.chooseQueue();
queue.pushBottom(task);
this.outstanding += 1;
this.wakeOneWorker();
}
run(workerId: number): void {
while (true) {
const task = this.queues[workerId].popBottom()
?? this.stealFromOtherQueues(workerId);
if (!task) {
if (!this.accepting && this.outstanding === 0) return;
this.parkBriefly();
continue;
}
try { task(); } finally { this.outstanding -= 1; }
}
}
}यह स्निपेट जानबूझकर स्टेट ट्रांजिशन के लिए सिंगल-थ्रेडेड स्यूडोकोड है। एक वास्तविक कार्यान्वयन में submit, outstanding, शटडाउन और वेकअप के लिए एक सिंक्रोनाइज़ेशन प्रोटोकॉल का उपयोग किया जाना चाहिए। लॉस्ट-वेकअप रेस से बचने के लिए, जहाँ खाली चेक के ठीक बाद एक टास्क आता है, रॉ स्लीप के बजाय कंडीशन वेरिएबल, सेमाफोर, या काउंटेड इवेंट का उपयोग करें।
लॉक किया गया बेसलाइन तीन इनवेरिएंट्स को बनाए रखता है: एक टास्क deque से सफल निष्कासन के बाद ही चलता है; कोई भी दो ऑपरेशन एक ही टास्क को नहीं हटा सकते; और outstanding स्वीकृत लेकिन अधूरे काम के बराबर है। जब कोई चल रहा टास्क चिल्ड्रेन बनाता है, तो पैरेंट को घटाने से पहले चिल्ड्रेन को रजिस्टर करें, अन्यथा एक क्षणिक शून्य समय से पहले समाप्ति को ट्रिगर कर सकता है।
फेयरनेस विक्टिम चयन और स्टील बैच आकार पर निर्भर करती है। शुद्ध यादृच्छिकता लंबे समय तक विषम हो सकती है; फिक्स्ड राउंड-रॉबिन एक ही व्यस्त कतार पर कई चोरों को सिंक्रोनाइज़ कर सकता है। यादृच्छिक शुरुआत, विफल-स्टील बैकऑफ, और बाउंडेड बैचों का उपयोग करें। छोटे समान टास्क एकल या छोटे स्टील्स के पक्ष में होते हैं; पुनरावर्ती (recursive) वर्कलोड को अक्सर पुराने, बड़े हिस्से को लेने से लाभ होता है।
लॉक-फ्री एक ऑप्टिमाइजेशन है, डिफ़ॉल्ट उत्तर नहीं। Oracle का ForkJoinPool वर्क स्टीलिंग का उपयोग करता है और ट्यूनिंग के लिए स्टील काउंट्स को प्रदर्शित करता है। Chase–Lev deque को अतिरिक्त रूप से एटॉमिक इंडेक्स, मेमोरी ऑर्डरिंग, ग्रोथ, और सुरक्षित रिक्लेमेशन की आवश्यकता होती है। एक स्पष्ट सिंगल-ओनर/मल्टीपल-थीफ मॉडल और रिक्लेमेशन योजना के बिना, हाथ से लिखे गए "लॉक-फ्री" कोड द्वारा काम को डुप्लिकेट करने या मुक्त किए गए स्टोरेज का उपयोग करने की संभावना लॉक किए गए बेसलाइन की तुलना में अधिक होती है।
अपेक्षित लोकल push/pop लागत O(1) है; एक स्टील O(1) या O(batch) है, जबकि V विक्टिम्स को स्कैन करने की सामान्य लागत O(V) होती है। स्पेस O(T + N) है, जहाँ T अधूरा काम है और N वर्कर की संख्या है। ब्लॉकिंग I/O इस धारणा को अमान्य करता है कि एक निष्क्रिय वर्कर हमेशा स्टील कर सकता है, इसलिए ब्लॉकिंग काम को अलग करें या इसे सीमित करें।
उच्च-गुणवत्ता वाला नमूना उत्तर
मैं पहले एक लॉक किया हुआ सही संस्करण दूंगा और फिर लॉक-फ्री अपग्रेड पर चर्चा करूंगा। प्रत्येक वर्कर के पास एक प्राइवेट deque होता है; ओनर बॉटम में LIFO का उपयोग करता है और चोर टॉप पर FIFO का उपयोग करते हैं, जिसमें अलग ओनर और स्टील सिंक्रोनाइज़ेशन होता है। एक टास्क केवल एक सफल पॉप या स्टील के बाद ही निष्पादन में प्रवेश करता है, जो इसका क्लेमिंग लीनियराइजेशन पॉइंट है।
सबमिशन और शटडाउन अलग-अलग चिंताएं हैं। शटडाउन नए रूट्स को अस्वीकार करता है, फिर बकाया काम के शून्य होने की प्रतीक्षा करता है। यदि चल रहे टास्क चिल्ड्रेन बना सकते हैं, तो ड्रेनिंग अनुबंध को स्पष्ट रूप से उनकी अनुमति देनी चाहिए और उनकी गणना करनी चाहिए; अन्यथा उन्हें अस्वीकार करें और टास्क को त्रुटि संभालने दें। वर्कर स्पिन करने के बजाय एक कंडीशन वेरिएबल या सेमाफोर पर प्रतीक्षा करते हैं, और टास्क के अपवाद वर्कर लूप से बाहर निकलने के बजाय फ्यूचर्स और मेट्रिक्स में कैप्चर किए जाते हैं।
मैं एक बैरियर के साथ एक साथ छोटे और लंबे टास्क जारी करूंगा, बिल्कुल-एक-बार निष्पादन और वास्तविक स्टील्स की पुष्टि करूंगा, और सत्यापित करूंगा कि कतारें ड्रेन होती हैं। फिर मैं चाइल्ड निर्माण, स्टील के दौरान शटडाउन, ब्लॉकिंग काम, टास्क अपवाद, और बार-बार शटडाउन कॉल इंजेक्ट करूंगा। केवल अगर कंटेंशन और माप इसे सही ठहराते हैं, तो मैं बेसलाइन को एक Chase–Lev deque से बदलूंगा जिसके मेमोरी ऑर्डरिंग और रिक्लेमेशन निर्दिष्ट हैं।
सामान्य गलतियाँ
- एक ग्लोबल कतार → प्रत्येक वर्कर एक लॉक पर प्रतिस्पर्धा करता है → प्रति-वर्कर deques का उपयोग करें और स्टीलिंग को असंतुलन संभालने दें।
- गैर-खाली की जांच करना और अलग से पॉप करना → ऑपरेशन्स के बीच एक अन्य चोर कतार को बदल देता है → सफल निष्कासन को एटॉमिक क्लेम बनाएं।
- शटडाउन के दौरान कतारें खाली दिखने पर बाहर निकलना → एक चल रहा पैरेंट ठीक बाद में चिल्ड्रेन बना सकता है → ड्रेनिंग स्थिति और बकाया इनवेरिएंट का उपयोग करें।
- टास्क के अपवाद को वर्कर लूप से बाहर निकलने देना → एक खराब टास्क पैरेललिज्म को कम करता है → इसे एक future में कैप्चर करें और शेड्यूलिंग जारी रखें।
- मेमोरी या रिक्लेमेशन नियमों के बिना लॉक-फ्री कोड हाथ से लिखना → डुप्लिकेट काम या use-after-free → पहले लॉक किए गए सेमेंटिक्स को मान्य करें और एक सिद्ध एल्गोरिदम का पालन करें।
- हमेशा एक ही विक्टिम से स्टील करना → एक व्यस्त कतार में कंटेंशन बना रहता है → मेट्रिक्स के साथ यादृच्छिक शुरुआत, बैकऑफ और बाउंडेड बैचों को मिलाएं।
फॉलो-अप प्रश्न और उत्तर
आप ब्लॉकिंग काम को प्रत्येक वर्कर को रोकने से कैसे बचाते हैं?
आप कैसे साबित करते हैं कि शटडाउन चाइल्ड टास्क को नहीं खो सकता है?
सिंगल-टास्क स्टीलिंग की तुलना में बैच स्टीलिंग कब बेहतर होती है?
ब्लॉकिंग I/O एक अलग पूल या एक काउंटेड प्रबंधित-ब्लॉकिंग तंत्र से संबंधित है; स्टीलिंग केवल प्रतीक्षारत काम को स्थानांतरित करती है। शटडाउन प्रमाण स्टेट मशीन और काउंटर इनवेरिएंट का उपयोग करता है: नए रूट्स को रोकें, पैरेंट्स को पूरा करने से पहले चिल्ड्रेन को रजिस्टर करें, और केवल शून्य बकाया काम के साथ ड्रेनिंग में समाप्त करें। बैच स्टीलिंग तब मदद करती है जब टास्क निर्माण सघन हो और प्रत्येक सिंक्रोनाइज़ेशन महंगा हो; छोटी कतारों या छोटे टास्क के लिए, मूवमेंट और फेयरनेस की लागत बचत से अधिक हो सकती है।