कोडिंग इंटरव्यू: एक कैंसिलेबल प्रायोरिटी टास्क शेड्यूलर कैसे लागू करें?

प्रॉम्प्ट और दायरा

schedule(taskId, runAt, priority, fn), cancel(taskId), और next() के साथ एक सिंगल-नोड Scheduler लागू करें। सबसे पहले runAt, फिर उच्चतम priority, फिर सबमिशन अनुक्रम (sequence) का चयन करें। taskId का केवल एक संस्करण ही मान्य होता है। एक रद्द किया गया कार्य शुरू नहीं होना चाहिए; जब कुछ भी देय न हो, तो next() एक प्रतीक्षा संकेत या एक खाली परिणाम लौटाता है। लेज़ी डिलीशन, वर्कर समवर्तीता, क्लॉक चयन और शटडाउन रेस की व्याख्या करें।

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

इंटरव्यूअर क्या परीक्षण कर रहा है

अवैध संक्रमणों के बिना pending, running, cancelled, और completed के लिए एक स्टेट मशीन।
एक निर्धारक की (key) (runAt, -priority, sequence) जो कभी भी टास्क ऑब्जेक्ट्स की तुलना नहीं करती है।
संस्करण जाँच या लेज़ी डिलीशन ताकि रिप्लेसमेंट और कैंसिलेशन पुराने कार्य को लीक न कर सकें।
कतारबद्ध कार्य को रद्द करने और चल रहे फ़ंक्शन को रोकने के बीच एक सटीक अंतर।
एक प्रमाण कि वर्कर सीमाएं, शटडाउन क्रम और क्लॉक चयन अनुबंध को बनाए रखते हैं।

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

क्या runAt एक मोनोटोनिक सापेक्ष डेडलाइन है या वॉल-क्लॉक समय? प्रतीक्षा के लिए एक मोनोटोनिक क्लॉक मान लें।
क्या fn को कैंसिलेशन प्राप्त होता है? केवल सहयोगात्मक (cooperative) रोक के साथ, एक AbortSignal मान लें।
क्या डुप्लिकेट taskId बदल दिया जाता है या विफल हो जाता है? यह संस्करण पुराने संस्करण को बदल देता है।
क्या cancel चल रहे फ़ंक्शन को तुरंत रोक देता है? नहीं; यह अभी तक शुरू न हुए रन को रोकता है और चल रहे रन को संकेत देता है।
क्या close चल रहे काम की प्रतीक्षा करता है? मान लें कि यह नए काम को अस्वीकार करता है और वर्कर्स के समाप्त होने की प्रतीक्षा करता है।

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

मैं एक min-heap में (runAt, -priority, sequence, taskId, version) रखूँगा और एक मैप में प्रत्येक टास्क आईडी के लिए वर्तमान संस्करण संग्रहीत करूँगा। शेड्यूलिंग या कैंसिलेशन मैप को अपडेट करता है और पुरानी हीप प्रविष्टियों को अमान्य करता है; next() एक देय कार्य को running में ले जाने से पहले संस्करण और स्थिति को बार-बार मान्य करता है। एक डिस्पैचर हीप हेड की प्रतीक्षा करने के लिए एक मोनोटोनिक क्लॉक का उपयोग करता है, फिर एक निश्चित आकार के वर्कर पूल को काम सौंपता है। कतारबद्ध कैंसिलेशन एक मजबूत गारंटी है; चल रहे कोड का कैंसिलेशन सहयोगात्मक है। शटडाउन नए सबमिशन को अस्वीकार करता है, डिस्पैचर को जगाता है, और क्लीनअप की प्रतीक्षा करता है।

चरण-दर-चरण विस्तृत विश्लेषण

चरण 1: की (Key) और इनवेरिएंट्स को परिभाषित करें

हीप की के रूप में (runAt, -priority, sequence) का उपयोग करें। एक मोनोटोनिक अनुक्रम समान टाइमस्टैम्प और प्राथमिकताओं को निर्धारक बनाता है। current[taskId] केवल नवीनतम संस्करण संग्रहीत करता है। पुराने संस्करण अस्थायी रूप से हीप में रह सकते हैं, लेकिन वे कभी भी pending से running में स्थानांतरित नहीं हो सकते।

चरण 2: schedule में रिप्लेसमेंट को परिभाषित करें

प्रत्येक schedule एक नया संस्करण बनाता है, इसे मैप में संग्रहीत करता है, और एक नई हीप प्रविष्टि को पुश करता है। ऐरे के माध्यम से कोई रैखिक खोज नहीं होती है। जब कोई प्रविष्टि पॉप की जाती है, तो उसके संस्करण की तुलना मैप से की जाती है। प्रविष्टि O(log n) है और डुप्लिकेट आईडी दो मान्य निष्पादन उत्पन्न नहीं कर सकते हैं।

text

schedule(id, runAt, priority, fn):
    version = nextVersion(id)
    current[id] = {version, state: pending, fn, runAt, priority}
    heappush(heap, (runAt, -priority, nextSequence(), id, version))

चरण 3: cancel और हेड क्लीनअप लागू करें

कैंसिलेशन वर्तमान लंबित कार्य को cancelled के रूप में चिह्नित करता है और एक वेटर को जगाता है। जब next() हेड को पॉप करता है, तो यह जाँचता है कि मैप अभी भी उसी संस्करण की ओर इशारा कर रहा है और स्थिति pending है। पुरानी, रद्द और प्रतिस्थापित प्रविष्टियों को त्याग दिया जाता है। लेज़ी डिलीशन O(n) स्कैन से बचाता है, लेकिन पुरानी प्रविष्टि के अनुपात की निगरानी की जानी चाहिए और समय-समय पर पुनर्निर्माण किया जाना चाहिए।

चरण 4: वर्कर सीमा के साथ देय कार्य को नियंत्रित करें

डिस्पैचर को वर्कर्स को भविष्य का काम नहीं सौंपना चाहिए। यह मोनोटोनिक क्लॉक के साथ हीप हेड के लिए विलंब की गणना करता है। देय होने पर, यह परमाणु रूप से pending को running में बदलता है और कार्य को एक निश्चित आकार की वर्कर कतार में डालता है। वर्कर संख्या या एक सेमाफोर समवर्ती सीमा लागू करता है।

चरण 5: फ़ंक्शन समाप्ति से कैंसिलेशन को अलग करें

यदि कतारबद्ध कार्य को स्थिति संक्रमण से पहले रद्द कर दिया जाता है, तो fn को कभी नहीं बुलाया जाता है। एक चल रहा कार्य केवल AbortSignal प्राप्त कर सकता है; फ़ंक्शन को इसे जाँचना चाहिए या इसे कैंसिलेबल I/O को पास करना चाहिए। cancelRequested रिकॉर्ड करें, और जब तक फ़ंक्शन वास्तव में वापस नहीं आ जाता, तब तक पूर्णता की रिपोर्ट न करें।

चरण 6: रेस के विरुद्ध क्लोज़ को व्यवस्थित करें

close पहले closing में प्रवेश करता है और नए शेड्यूल को अस्वीकार करता है, फिर टाइमर रद्द करता है और डिस्पैचर को जगाता है। डिस्पैचर नए कार्यों पर दावा करना बंद कर देता है जबकि वर्कर्स पहले से दावा किए गए काम को पूरा करते हैं; केवल तभी शेड्यूलर closed बन जाता है। यदि कतारबद्ध कार्य को तुरंत त्याग दिया जाना चाहिए, तो केवल हीप को साफ़ करने के बजाय मैप प्रविष्टियों को रद्द के रूप में चिह्नित करें।

चरण 7: जटिलता और स्पेस सीमाओं को सिद्ध करें

सामान्य schedule O(log n) है, cancel एक O(1) स्थिति अपडेट है, और next O(log n) हीप कार्य करता है। प्रत्येक पुरानी प्रविष्टि को अधिकतम एक बार पॉप किया जाता है, इसलिए क्लीनअप को उस अपडेट या कैंसिलेशन पर परिशोधित (amortized) किया जाता है जिसने इसे बनाया था। जब हीप का आकार सक्रिय कार्यों के एक निश्चित गुणक से अधिक हो जाए, तो वर्तमान मैप प्रविष्टियों से पुनर्निर्माण करें।

चरण 8: महत्वपूर्ण इंटरलीविंग्स का परीक्षण करें

समान कीज़ के लिए स्थिर क्रम, पुरानी प्रविष्टि के हेड तक पहुँचने से पहले प्रतिस्थापन, दावा करने से तुरंत पहले और बाद में कैंसिलेशन, प्रतीक्षा को बाधित करने वाला पहले का कार्य, वर्कर सीमा, फ़ंक्शन विफलता, क्लोज़ के दौरान सबमिशन, और मोनोटोनिक-क्लॉक जंप का परीक्षण करें। एक क्रमबद्ध संदर्भ मॉडल के विरुद्ध next() का विभेदक-परीक्षण करें और पीक सक्रिय वर्कर्स को रिकॉर्ड करें।

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

मैं स्थिति को हीप से अलग रखूँगा: एक मैप प्रत्येक taskId के लिए नवीनतम संस्करण संग्रहीत करता है, जबकि एक min-heap (runAt, -priority, sequence, taskId, version) संग्रहीत करता है। रिप्लेसमेंट एक नया संस्करण लिखता है और कैंसिलेशन स्थिति को चिह्नित करता है; दोनों में से कोई भी हीप ऐरे को म्यूटेट नहीं करता है। डिस्पैचर केवल देय कार्यों पर दावा करता है और उन्हें एक निश्चित आकार की वर्कर कतार में डालता है। संस्करण सत्यापन रद्द और पुरानी प्रविष्टियों को चलने से रोकता है, जबकि AbortSignal चल रहे फ़ंक्शंस को सहयोगात्मक कैंसिलेशन प्रदान करता है। शटडाउन नए काम को अस्वीकार करता है, दावा करना बंद करता है, वेटर्स को जगाता है, और दावा किए गए काम के पूरा होने की प्रतीक्षा करता है। मेट्रिक्स हीप आकार के मुकाबले लाइव प्रविष्टियों को ट्रैक करते हैं ताकि लेज़ी डिलीशन बिना किसी सीमा के न बढ़े।

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

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

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

आप कम प्राथमिकता वाले कार्य की भुखमरी (starvation) को कैसे रोकते हैं?

बताएं कि सख्त प्राथमिकता डिफ़ॉल्ट है और कम प्राथमिकता वाले कार्यों को भूखा रख सकती है। यदि निष्पक्षता की आवश्यकता है, तो प्रतीक्षा समय के साथ प्रभावी प्राथमिकता बढ़ाएं या भारित कोटा (weighted quotas) का उपयोग करें। दोनों विकल्प ऑर्डरिंग की और लेटेंसी प्रूफ को बदलते हैं, इसलिए मेट्रिक्स और परीक्षण जोड़ें।

आप एक आवर्ती (recurring) कार्य के लिए ओवरलैपिंग रन को कैसे रोकते हैं?

कार्य स्थिति में एक रनिंग लॉक या जेनरेशन जोड़ें। यदि अगला ट्रिगर तब आता है जब यह चल रहा हो, तो स्पष्ट रूप से छोड़ना (skip), एक लंबित रन को संयोजित (coalesce) करना, या एक नया संस्करण कतारबद्ध करना चुनें। ओवरलैप निषिद्ध होने पर कभी भी बिना शर्त सबमिट न करें।

प्रोसेस क्रैश के बाद आप कैसे रिकवर करेंगे?

एक इन-मेमोरी हीप केवल प्रक्रिया के जीवनकाल को कवर करता है। संस्करण, स्थिति और अगले रन समय को स्थायी करें, स्टार्टअप पर हीप का पुनर्निर्माण करें, और सशर्त अपडेट या लीज के साथ दावा करें। रिकवरी सामान्य रूप से एट-लीस्ट-वन्स (at-least-once) निष्पादन प्रदान करती है, इसलिए टास्क फ़ंक्शंस को इडेम्पोटेंट होना चाहिए।

आप इसे एकाधिक नोड्स तक कैसे विस्तारित करेंगे?

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