💻 computer science

ReDAG-RT: Global Rate-Priority Scheduling for Real-Time Multi-DAG Execution in ROS 2

यह शोध पत्र ReDAG-RT प्रस्तुत करता है, जो ROS 2 के लिए एक यूजर-स्पेस ग्लोबल शेड्यूलिंग फ्रेमवर्क है जो क्रॉस-ग्राफ प्रायोरिटी इनवर्जन (priority inversion) को समाप्त करने के लिए रेट-प्रायोरिटी ऑर्डरिंग और प्रति-DAG कंकरेंसी बाउंड्स को लागू करता है, जिससे अंतर्निहित मिडलवेयर या ऑपरेटिंग सिस्टम को संशोधित किए बिना रियल-टाइम मल्टी-DAG निष्पादन के लिए डेडलाइन मिस और रिस्पांस टाइम को महत्वपूर्ण रूप से कम किया जा सकता है।

मूल लेखक: Md. Mehedi Hasan, Rafid Mostafiz, Bikash Kumar Paul, Md. Abir Hossain, Ziaur Rahman

प्रकाशित 2026-03-20

📖 4 मिनट में पढ़ें☕ कॉफ़ी ब्रेक में पढ़ें

CC BY 4.0

मूल लेखक: Md. Mehedi Hasan, Rafid Mostafiz, Bikash Kumar Paul, Md. Abir Hossain, Ziaur Rahman

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक व्यस्त, हाई-टेक रेस्टोरेंट किचन के मैनेजर हैं। यह किचन एक साथ होने वाले तीन महत्वपूर्ण कार्यों के लिए जिम्मेदार है:

शेफ (अनुभूति/Perception): यह सुनिश्चित करने के लिए कि सूप एकदम सही है, हर 20 सेकंड में लगातार सूप चखता है।
सू-शेफ (योजना/Planning): हर 50 सेकंड में मेनू की जांच करता है और ऑर्डर्स को व्यवस्थित करता है।
डिशवॉशर (नियंत्रण/Control): हर 100 सेकंड में प्लेटें धोता है।
रोबोटिक्स की दुनिया में, इन कार्यों को DAGs (डायरेक्टेड एसाइक्लिक ग्राफ्स) कहा जाता है, जो बस एक "कदमों की श्रृंखला" का फैंसी नाम है जिसे क्रम में होना चाहिए।

समस्या: "जो पहले आया, उसे पहले मिलेगा" वाला कोलाहल

पेपर बताता है कि रोबोट के दिमाग को चलाने के लिए इस्तेमाल किया जाने वाला मानक सॉफ्टवेयर (जिसे ROS 2 कहा जाता है) एक ऐसे किचन मैनेजर की तरह काम करता है जिसका नियम बहुत बुरा है: "जो भी पहले किचन में कदम रखेगा, उसे ही काम करने दिया जाएगा, चाहे उसका काम कितना भी महत्वपूर्ण क्यों न हो।"

इसे FIFO (First-In, First-Out) क्यू कहा जाता है।

इस अराजक किचन में ऐसा होता है:

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

मानक ROS 2 सिस्टम को इस बात से कोई फर्क नहीं पड़ता कि किसी कार्य को कितनी बार करने की आवश्यकता है; इसे केवल इस बात से फर्क पड़ता है कि वह कब आया। इससे रोबlet का व्यवहार अप्रत्याशित और अस्थिर हो जाता है।

समाधान: ReDAGRT (द "रेट-प्रायोरिटी" मैनेजर)

लेखकों ने एक नया सिस्टम बनाया है जिसे ReDAGRT कहा जाता है। इसे एक बुद्धिमान नए किचन मैनेजर के रूप में सोचें जो एक सख्त नियम का पालन करता है: "आपको जितनी बार काम करने की आवश्यकता है, आपकी प्राथमिकता उतनी ही अधिक होगी।"

यह Rate-Monotonic Scheduling की अवधारणा पर आधारित है।

यहाँ ReDAGRT किचन को कैसे ठीक करता है:

प्राथमिकता सूची (The Priority List): मैनेजर कार्यों को देखता है।
- शेफ (20-सेकंड का चक्र) को प्राथमिकता #1 मिलती है।
- सू-शेफ (50-सेकंड का चक्र) को प्राथमिकता #2 मिलती है।
- डिशवॉशर (100-सेकंड का चक्र) को प्राथमिकता #3 मिलती है।
ग्लोबल क्यू (The Global Queue): एक बिखरी हुई लाइन के बजाय, यहाँ एक व्यवस्थित वेटिंग रूम है। यदि डिशवॉशर पहले से ही काम कर रहा है, लेकिन शेफ आता है, तो मैनेजर तुरंत डिशवॉशर को रोकता है (preemption) और शेफ को चम्मच थमा देता है।
परिणाम: शेफ को डिशवॉशर के लिए इंतजार नहीं करना पड़ता। सूप हमेशा समय पर चखा जाता है। रोबोट सुचारू रूप से और अनुमानित तरीके से चलता है।

यह क्यों मायने रखता है

पेपर साबित करता है कि इस समस्या को ठीक करने के लिए आपको पूरे रोबोट को फिर से बनाने या ऑपरेटिंग सिस्टम (जैसे Linux) को बदलने की आवश्यकता नहीं है। आपको बस "मिडल मैनेजर" (सॉफ्टवेयर लेयर) को काम करने के लिए अधिक स्मार्ट बनाने की आवश्यकता है।

मुख्य निष्कर्ष (द "टेस्ट टेस्ट"):

कम गलतियाँ: इस नए मैनेजर का उपयोग करके, रोबोट ने पहले की तुलना में 29.7% कम बार अपने डेडलाइन मिस किए (जैसे कप गिरा देना)।
तेज़ प्रतिक्रिया: सबसे धीमे कार्य (परफॉरमेंस की "पूंछ") 42.9% तेज़ हो गए।
कोई कोलाहल नहीं: यहाँ तक कि जब किचन बहुत व्यस्त हो जाता है, तब भी सिस्टम ध्वस्त नहीं होता है। यह दबाव को कुशलतापूर्वक संभालता है।

"सीक्रेट सॉस": एसिमेट्रिक लिमिट्स (Asymmetric Limits)

पेपर में एक और दिलचस्प ट्रिक का पता चला। यदि आपके पास दो व्यस्त शेफ हैं, तो दोनों को एक ही समय में पूरी गति से चलने देने से ट्रैफिक जाम हो जाता है। लेकिन यदि आप एक शेफ को एक समय में केवल 2 चीजें करने के लिए सीमित करते हैं और दूसरे को 5 करने देते हैं, तो पूरा किचन अधिक सुचारू रूप से चलता है। इस "एसिमेट्रिक" नियम ने हस्तक्षेप को 40% कम कर दिया।

संक्षेप में

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

यहाँ शोध पत्र "ReDAGRT: Real-Time Multi-DAG Execution के लिए Global Rate-Priority Scheduling हेतु ROS 2" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

आधुनिक रोबोटिक सिस्टम जो ROS 2 का उपयोग करते हैं, वे आमतौर पर धारणा (perception), योजना (planning), और नियंत्रण (control) पाइपलाइनों को कॉलबैक के स्वतंत्र निर्देशित अचक्रीय ग्राफ़ (Directed Acyclic Graphs - DAGs) के रूप में व्यवस्थित करते हैं। ये पाइपलाइनें एक साझा निष्पादन वातावरण (execution environment) साझा करती हैं, जिसे डिफ़ॉल्ट ROS 2 एक्सेक्यूटर्स (SingleThreadedExecutor या MultiThreadedExecutor) द्वारा प्रबंधित किया जाता है।

यह शोध पत्र इन डिफ़ॉल्ट एक्सेक्यूटर्स में एक महत्वपूर्ण संरचनात्मक कमी की पहचान करता है:

Global Priority Ordering का अभाव: डिफ़ॉल्ट एक्सेक्यूटर्स एक First-In-First-Out (FIFO) या ढीले क्रमबद्ध क्यू (queue) का उपयोग करते हैं, जो विभिन्न DAGs के बीच एक वैश्विक प्राथमिकता पदानुक्रम (global priority hierarchy) को लागू करने में विफल रहते हैं।
Cross-DAG Priority Inversion: एक पाइपलाइन से आया कम-आवृत्ति (कम-प्राथमिकता वाला) कॉलबैक, दूसरी पाइपलाइन के उच्च-आवृत्ति (उच्च-प्राथमिकता वाले) कॉलबैक से पहले निष्पादित हो सकता है, केवल इसलिए क्योंकि वह पहले आया या उसने पहले वर्कर थ्रेड प्राप्त कर लिया।
असीमित हस्तक्षेप (Unbounded Interference): यह अनियंत्रित प्रतिस्पर्धा, संरचनात्मक प्राथमिकता उलटाव (structural priority inversion), और रिस्पॉन्स-टाइम की उच्च परिवर्तनशीलता (variability) की ओर ले जाता है।
परिणाम: समवर्ती वर्कलोड (concurrent workloads) के तहत, यह व्यवहार डेडलाइन मिस (deadline misses) और जिटर (jitter) का कारण बनता है, जिससे ROS 2 बिना किसी महत्वपूर्ण संशोधन के समय-महत्वपूर्ण (time-critical) और सुरक्षा-संवेदनशील साइबर-फिजिकल सिस्टम्स (CPS) के लिए अनुपयुक्त हो जाता है।

2. कार्यप्रणाली: ReDAGRT फ्रेमवर्क (Methodology: ReDAGRT Framework)

लेखक ReDAGRT का प्रस्ताव करते हैं, जो एक यूजर-स्पेस ग्लोबल शेड्यूलिंग फ्रेमवर्क है जो ROS 2 API, एप्लिकेशन ग्राफ संरचना, या लिनक्स कर्नेल शेड्यूलर में संशोधन किए बिना पूरी तरह से ROS 2 निष्पादन परत (execution layer) के भीतर कार्य करता है।

मुख्य आर्किटेक्चर (Core Architecture)

Global Ready Queue: सभी समवर्ती DAGs से सभी 'रेडी' कॉलबैक को एक एकल, एकीकृत यूजर-स्पेस प्रायोरिटी क्यू में डाला जाता है।
Rate-Monotonic (RM) Ordering: कार्यों को उनके सक्रियण काल (activation periods - $T_i$ ) के आधार पर स्थिर प्राथमिकताएं दी जाती हैं। कम अवधि (उच्च आवृत्ति) वाले कार्यों को कड़ाई से उच्च प्राथमिकता ( $T_i < T_j \implies P_i > P_j$ ) प्राप्त होती है।
Preemptive Dispatch: शेड्यूलर उच्चतम-प्राथमिकता वाले 'रेडी' कार्य का चयन करता है। यदि एक नया जारी किया गया कार्य वर्तमान में निष्पादित हो रहे कार्य से उच्च प्राथमिकता का है, तो तत्काल प्रीएम्प्शन (preemption) होता है।
Dependency Resolution: एक कार्य को ग्लोबल क्यू में प्रवेश करने से पहले, सिस्टम यह सत्यापित करता है कि उसकी अवधि समाप्त हो गई है और सभी इंट्रा-DAG पूर्वता बाधाएं (intra-DAG precedence constraints - एक ही ग्राफ के भीतर निर्भरताएं) संतुष्ट हैं।
Per-DAG Concurrency Bounds: फ्रेमवर्क प्रत्येक DAG में एक साथ सक्रिय कॉलबैक की अधिकतम संख्या पर सीमाएं लागू करता है ताकि एक पाइपलाइन संसाधनों पर एकाधिकार न कर सके।

औपचारिक मॉडल (Formal Model)

कार्य मॉडल (Task Model): इसे DAGs के एक सेट $G = \{G_1, ..., G_m\}$ के रूप में परिभाषित किया गया है, जहाँ प्रत्येक कार्य $\tau_i$ का एक वर्स्ट-केस एक्जीक्यूशन टाइम (WCET) $C_i$ , अवधि $T_i$ , और डेडलाइन $D_i$ (माना गया कि $D_i = T_i$ ) है।
हस्तक्षेप विश्लेषण (Interference Analysis): शोध पत्र एक कार्य $\tau_i$ के लिए एक औपचारिक हस्तक्षेप सीमा $I_i$ व्युत्पन्न करता है, जो सभी उच्च-प्राथमिकता वाले कार्यों ($hp(i)$) के WCET का योग है। डिफ़ॉल्ट एक्सेक्यूटर्स के विपरीत, यह हस्तक्षेप सीमित और विश्लेषण योग्य है।
शेड्यूलेबिलिटी (Schedulability): सिस्टम वर्स्ट-केस रिस्पॉन्स टाइम के लिए क्लासिकल रेट-मोनोटोनिक रिस्पॉन्स-टाइम विश्लेषण (RTA) का उपयोग करता है, यह सुनिश्चित करते हुए कि यदि $R_i \leq D_i$ , तो कार्य शेड्यूलेबल है।

3. प्रमुख योगदान (Key Contributions)

संरचनात्मक विश्लेषण: डिफ़ॉल्ट ROS 2 एक्सेक्यूटर्स में Cross-DAG Priority Inversion की पहचान और लक्षण वर्णन, यह सिद्ध करते हुए कि FIFO डिस्पैच स्वतंत्र पाइपलाइनों के बीच वास्तविक-समय प्राथमिकता नियमों का उल्लंघन करता है।
औपचारिक हस्तक्षेप मॉडल: रेट-मोनोटोनिक सिद्धांत पर आधारित एक मल्टी-DAG टास्क मॉडल का विकास, जो साझा एक्सेक्यूटर वातावरण में हस्तक्षेप और रिस्पॉन्स-टाइम पुनरावृत्ति (recurrences) के लिए गणितीय सीमाएं प्रदान करता है।
ReDAGRT कार्यान्वयन: एक पूर्णतः कार्यात्मक, ओपन-सोर्स शेड्यूलर जो:
- ग्लोबल रेट-मोनोटोनिक प्राथमिकता लागू करता है।
- DAG सीमाओं के पार प्रीएम्प्शन का समर्थन करता है।
- इसके लिए किसी कर्नेल पैच या API परिवर्तन की आवश्यकता नहीं है।
- रियल-टाइम मेट्रिक्स (लैटनेस, मिस रेट) के लिए एक टाइमिंग मॉनिटर शामिल करता है।

4. प्रयोगात्मक परिणाम (Experimental Results)

इस फ्रेमवर्क का मूल्यांकन ROS 2 Humble वातावरण में मिश्रित अवधियों और क्रिटिकैलिटी वाले सिंथेटिक मल्टी-DAG वर्कलोड के साथ किया गया, जिसमें ReDAGRT की तुलना SingleThreadedExecutor और MultiThreadedExecutor (4 थ्रेड्स) से की गई।

डेडलाइन मिस रेट (Deadline Miss Rate):
- तनावपूर्ण स्थितियों (stress conditions) के तहत, ReDAGRT ने सर्वश्रेष्ठ प्रदर्शन करने वाले बेसलाइन कॉन्फ़िगरेशन की तुलना में संयुक्त डेडलाइन मिस रेट में 29.7% तक की कमी हासिल की।
- तुलनीय उपयोग (utilization) के तहत, MultiThreadedExecutor की तुलना में ReDAGRT ने मिस रेट में 13.7% का सुधार दिखाया।
रिस्पॉन्स टाइम और जिटर (Response Time & Jitter):
- 99वें पर्सेंटाइल रिस्पॉन्स टाइम में 42.9% की कमी आई (49ms से घटकर 28ms)।
- मीडियन (Median) रिस्पॉन्स टाइम 21ms से सुधरकर 14ms हो गया।
- संचयी वितरण फलन (Cumulative Distribution Function - CDF) ने एक महत्वपूर्ण बाईं ओर का बदलाव दिखाया, जो टाइट टेल बाउंड्स (tighter tail bounds) और बेहतर भविष्यवाणी का संकेत देता है।
कन्करेंसी संवेदनशीलता (Concurrency Sensitivity):
- थ्रेड स्केलेबिलिटी: प्रदर्शन 4 से 8 थ्रेड्स तक जाने पर काफी सुधरा (मिस रेट कम हुआ), लेकिन सिंक्रोनाइज़ेशन ओवरहेड के कारण 10 थ्रेड्स पर संतृप्त (saturate) हो गया।
- एसिमेट्रिक बाउंड्स (Asymmetric Bounds): एसिमेट्रिक प्रति-DAG कन्करेंसी बाउंड्स का उपयोग करने से (उदाहरण के लिए, एक DAG को दूसरे की तुलना में अधिक सख्ती से सीमित करना) सममित (symmetric) कॉन्फ़िगरेशन की तुलना में हस्तक्षेप में 40.8% की कमी आई, जो यह सिद्ध करता है कि विशिष्ट DAGs के "फुटप्रिंट" को सीमित करना वैश्विक प्रतिस्पर्धा को कम करने के लिए महत्वपूर्ण है।
ग्रेसफुल डिग्रेडेशन (Graceful Degradation): सख्त डेडलाइन बाधाओं (ओवरलोड स्थितियों) के तहत, ReDAGRT ने ग्रेसफुल डिग्रेडेशन प्रदर्शित किया, जबकि डिफ़ॉल्ट एक्सेक्यूटर्स में लैटनेस (lateness) में विनाशकारी वृद्धि देखी गई (जैसे, SingleThreadedExecutor की लैटनेस में दो क्रमों (orders of magnitude) की वृद्धि हुई)।

5. महत्व और प्रभाव (Significance and Impact)

निश्चित रियल-टाइम ROS 2 (Deterministic Real-Time ROS 2): ReDAGRT यह प्रदर्शित करता है कि पूरी तरह से ROS 2 यूजर-स्पेस लेयर के भीतर निश्चित, विश्लेषण योग्य मल्टी-DAG शेड्यूलिंग प्राप्त की जा सकती है, जो मानक रोबोटिक मिडलवेयर और सुरक्षा-महत्वपूर्ण रियल-टाइम आवश्यकताओं के बीच के अंतर को पाटता है।
कोई कर्नेल निर्भरता नहीं: शेड्यूलिंग समस्या को एक्सेक्यूटर स्तर पर हल करके, यह कर्नेल संशोधनों (जैसे PREEMPT_RT पैच) या विशेष OS कॉन्फ़िगरेशन की जटिलता और रखरखाव के बोझ से बचता है।
सुरक्षा-महत्वपूर्ण परिनियोजन (Safety-Critical Deployment): यह फ्रेमवर्क आवश्यक सैद्धांतिक आधार (शेड्यूलेबिलिटी विश्लेषण) और अनुभवजन्य साक्ष्य प्रदान करता है ताकि ROS 2 को उन सुरक्षा-महत्वपूर्ण CPS में तैनात किया जा सके जहाँ डेडलाइन मिस स्वीकार्य नहीं हैं।
ओपन सोर्स: लेखकों ने पूर्ण कार्यान्वयन और प्रयोगात्मक आर्टिफैक्ट्स जारी किए हैं, जिससे पुनरुत्पादकता (reproducibility) और सामुदायिक अपनाने की सुविधा मिलती है।

निष्कर्षतः, ReDAGRT ROS 2 निष्पादन मॉडल को एक 'बेस्ट-एफर्ट', FIFO-आधारित सिस्टम से बदलकर एक रेट-प्रायोरिटी, प्रीएम्प्टिव और इंटरफेरेंस-बाउंडेड रनटाइम में बदल देता है, जो जटिल, समवर्ती रोबोटिक पाइपलाइनों के लिए मजबूत रियल-टाइम प्रदर्शन को सक्षम बनाता है।