💻 computer science

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

تقدم هذه الورقة ReDAG-RT، وهو إطار عمل لجدولة عالمية في مساحة المستخدم لنظام ROS 2 يفرض ترتيب الأولوية والمعدل وحدود التزامن لكل رسم بياني موجه (DAG) للقضاء على انقلاب الأولوية عبر الرسوم البيانية، مما يقلل بشكل كبير من فوات المواعلات النهائية وأوقات الاستجابة للتنفيذ متعدد الرسوم البيانية الموجهة في الوقت الفعلي دون تعديل الوسيط الأساسي أو نظام التشغيل.

المؤلفون الأصليون: Md. Mehedi Hasan, Rafid Mostafiz, Bikash Kumar Paul, Md. Abir Hossain, Ziaur Rahman

نُشر 2026-03-20

📖 3 دقيقة قراءة☕ قراءة في استراحة قهوة

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/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك مدير مطبخ تقني عالي التطور ومزدحم للغاية. هذا المطبخ مسؤول عن ثلاث مهام حيوية تحدث في نفس الوقت:

الشيف (الإدراك): يتذوق الحساء باستمرار كل 20 ثانية للتأكد من أنه مثالي.
مساعد الشيف (التخطيط): يراجع القائمة وينظم الطلبات كل 50 ثانية.
غاسل الأطباق (التحكم): يغسل الأطباق كل 100 ثانية.

في عالم الروبوتات، تسمى هذه المهام DAGs (الرسوم البيانية الموجهة غير الحلقية)، وهي مجرد طريقة معقدة لقول "سلسلة من الخطوات التي يجب أن تحدث بالترتيب".

المشكلة: فوضى "من يأتي أولاً يُخدم أولاً"

يشرح البحث أن البرامج القياسية المستخدمة لتشغيل عقول الروبوتات (المعروفة باسم ROS 2) تعمل مثل مدير مطبخ لديه قاعدة سيئة للغاية: "من يدخل المطبخ أولاً يبدأ العمل، بغض النظر عن مدى أهمية وظيفته".

هذا ما يسمى بـ FIFO (الداخل أولاً، يخرج أولاً)، أي طابور "من يأتي أولاً يُخدم أولاً".

إليك ما يحدث في هذا المطبخ الفوضوي:

غاسل الأطباق (مهمة بطيئة ومنخفضة الأولوية) يدخل المطبخ أولاً.
الشيف (مهمة سريعة وعالية الأولوية) يدخل بعده بلحظة بسيطة.
ولأن غاسل الأطباق كان الأول، يسمح له المدير بالبدء في غسل الأطباق.
يضطر الشيف للانتظار.
الكارثة: يحترق الحساء لأن الشيف تأخر بسبب غاسل الأطباق. في مصطلحات الروبوتات، يسمى هذا انعكاس الأولوية (Priority Inversion). مهمة بطيئة وغير مهمة أعاقت مهمة سريعة وحرجة، مما تسبب في جعل الروبوت يفقد "الموعد النهائي" (مثل الاصطدام أو إسقاط شيء ما).

نظام ROS 2 القياسي لا يهتم بـ كم مرة تحتاج المهمة أن تحدث؛ هو يهتم فقط بـ متى وصلت. وهذا يؤدي إلى سلوك غير متوقع ومتذبذب، وأحياناً خطير، للروبوت.

الحل: ReDAGRT (مدير "الأولوية بناءً على المعدل")

قام المؤلفون ببناء نظام جديد يسمى ReDAGRT. تخيل هذا كتوظيف مدير مطبخ جديد وعبقري يتبع قاعدة صارمة: "كلما كنت بحاجة للقيام بمهمة بشكل أكثر تكراراً، زادت أولويتك".

هذا يعتمد على مفهوم يسمى الجدولة أحادية الرتابة (Rate-Monotonic Scheduling).

إليك كيف يقوم ReDAGRT بإصلاح المطبخ:

قائمة الأولويات: ينظر المدير إلى المهام.
- الشيف (دورة 20 ثانية) يحصل على الأولوية رقم 1.
- مساعد الشيف (دورة 50 ثانية) يحصل على الأولوية رقم 2.
- غاسل الأطباق (دورة 100 ثانية) يحصل على الأولوية رقم 3.
الطابور العالمي: بدلاً من الطابور الفوضوي، هناك غرفة انتظار واحدة منظمة. إذا كان غاسل الأطباق يعمل بالفعل، ولكن الشيف دخل للتو، فإن المدير يوقف غاسل الأطباق فوراً (الاستباق/Preemption) ويسلم الشيف الملعقة.
النتيجة: لا ينتظر الشيف غاسل الأطباق أبداً. يتم تذوق الحساء دائماً في وقته المحدد. يتحرك الروبوت بسلاسة وتوقع.

لماذا هذا مهم؟

يثبت البحث أنك لست بحاجة لإعادة بناء الروبوت بالكامل أو تغيير نظام التشغيل (مثل Linux) لإصلاح الأمر. أنت فقط بحاجة لترقية "المدير الأوسط" (طبقة البرمجيات) ليكون أكثر ذكاءً في تحديد من يبدأ العمل أولاً.

النتائج الرئيسية (اختبار المذاق):

أخطاء أقل: باستخدام هذا المدير الجديد، قل عدد المرات التي فات فيها الروبوت مواعيده النهائية (مثل إسقاط كوب) بنسبة 29.7% مقارنة بالسابق.
استجابة أسرع: المهام الأبطأ (ذيل الأداء) أصبحت أسرع بنسبة 42.9%.
لا مزيد من الفوضى: حتى عندما يصبح المطبخ شديد الازدحام، لا ينهار النظام؛ بل يتعامل مع الضغط بسلاسة.

"الخلطة السرية": الحدود غير المتماثلة

اكتشف الورقة أيضاً خدعة رائعة. إذا كان لديك شيفان مشغولان، فإن السماح لكليهما بالعمل بالسرعة القصوى في نفس الوقت يسبب ازدحاماً مرورياً. ولكن إذا قمت بتحديد أحدهما ليقوم بشيئين فقط في وقت واحد وسمحت للآخر بالقيام بخمسة، فإن المطبخ بأكمله سيعمل بسلاسة أكبر. هذه القاعدة "غير المتماثلة" قللت من التداخل بنسبة 40%.

باختصار

ReDAGRT هو شرطي مرور ذكي لعقول الروبوتات. إنه يمنع المهام البطيئة والمملة من حجب المهام السريعة والمنقذة للحياة. إنه يضمن بقاء "نبض قلب" الروبوت (الإدراك والتحكم) مستقراً وآمناً، حتى عندما يقوم الروبوت بأشياء كثيرة في آن واحد. إنه يحول مطبخاً فوضوياً وغير متوقع إلى آلة دقيقة ومنظمة للغاية.

إليك ملخص تقني مفصل لورقة البحث بعنوان: "ReDAGRT: جدولة معدل الأولوية العالمية لتنفيذ الرسوم البيانية الموجهة غير الحلقية (DAG) متعددة المهام في الوقت الحقيقي ضمن ROS 2".

1. بيان المشكلة

تعتمد الأنظمة الروبوتية الحديثة التي تستخدم ROS 2 عادةً على هيكلة خطوط أنابيب الإدراك، والتخطيط، والتحكم كرسوم بيانية موجهة غير حلقية (DAGs) مستقلة من عمليات الاستدعاء (callbacks). وتتشارك هذه الخطوط في بيئة تنفيذ مشتركة تديرها المنفذات الافتراضية لـ ROS 2 (مثل SingleThreadedExecutor أو MultiThreadedExecutor).

تحدد الورقة خللاً هيكلياً حرجاً في هذه المنفذات الافتراضية:

الافتقار إلى ترتيب أولوية عالمي: تستخدم المنفذات الافتراضية طابور "الداخل أولاً يخرج أولاً" (FIFO) أو ترتيباً فضفاضاً دون فرض هرمية أولوية عالمية عبر مختلف الـ DAGs.
انعكاس الأولوية عبر الـ DAGs (Cross-DAG Priority Inversion): يمكن لعملية استدعاء ذات تردد منخفض (أولوية منخفضة) من خط أنابيب واحد أن تُنفذ قبل عملية استدعاء ذات تردد عالٍ (أولوية عالية) من خط أنابيب آخر، لمجرد أنها وصلت أولاً أو استحوذت على خيط معالجة (worker thread) أولاً.
التداخل غير المحدود: يؤدي هذا إلى نزاع غير منضبط، وانعكاس في الأولوية الهيكلية، وتباين عالٍ في زمن الاستجابة.
النتيجة: يتسبب هذا السلوك، تحت أعباء العمل المتزامنة، في تجاوز المواعيد النهائية (deadlines) والارتجاف (jitter)، مما يجعل ROS 2 غير مناسب للأنظمة السيبرانية الفيزيائية (CPS) ذات الزمن الحقيقي والحساسة للسلامة دون تعديلات جوهرية.

2. المنهجية: إطار عمل ReDAGRT

يقترح المؤلفون ReDAGRT، وهو إطار عمل عالمي لجدولة المهام يعمل في مساحة المستخدم (user-space)، ويعمل بالكامل ضمن طبقة التنفيذ الخاصة بـ ROS 2 دون تعديل واجهة برمجة تطبيقات (API) الخاصة بـ ROS 2، أو هيكل الرسم البياني للتطبيق، أو جدولة نواة لينكس (Linux kernel).

البنية الأساسية

طابور الاستعداد العالمي (Global Ready Queue): يتم إدراج جميع عمليات الاستدعاء الجاهزة من جميع الـ DAGs المتزامنة في طابور أولوية موحد واحد في مساحة المستخدم.
ترتيب معدل مونوتون (Rate-Monotonic Ordering): تُخصص المهام أولويات ثابتة بناءً حصرياً على فترات تنشيطها ( $T_i$ ). الفترات الأقصر (التردد الأعلى) تحصل على أولويات أعلى بصرامة ( $T_i < T_j \implies P_i > P_j$ ).
التوزيع الاستباقي (Preemptive Dispatch): يختار المجدول المهمة الجاهزة ذات الأولوية الأعلى. إذا كانت المهمة التي تم إصدارها حديثاً ذات أولوية أعلى من المهمة التي يتم تنفيذها حالياً، يحدث الاستباق (preemption) فوراً.
حل التبعيات: قبل دخول المهمة إلى الطابور العالمي، يتحقق النظام من انقضاء فترتها واستيفاء جميع قيود الترتيب داخل الـ DAG (التبعيات داخل نفس الرسم البياني).
حدود التزامن لكل DAG: يفرض إطار العمل قيوداً على الحد الأقصى لعدد عمليات الاستدعاء النشطة في آن واحد لكل DAG لمنع أي خط أنابيب من احتكار الموارد.

النموذج الرسمي

نموذج المهمة: يُعرف كمجموعة من الـ DAGs $G = \{G_1, ..., G_m\}$ ، حيث لكل مهمة $\tau_i$ وقت تنفيذ أسوأ حالة (WCET) يرمز له بـ $C_i$ ، وفترة $T_i$ ، وموعد نهائي $D_i$ (يُفترض ضمناً أن $D_i = T_i$ ).
تحليل التداخل: تشتق الورقة حداً رسمياً للتداخل $I_i$ للمهمة $\tau_i$ ، وهو مجموع أوقات تنفيذ أسوأ حالة (WCET) لجميع المهام ذات الأولوية الأعلى ($hp(i)$). بخلاف المنفذات الافتراضية، يكون هذا التداخل محدوداً وقابلاً للتحليل.
قابلية الجدولة: يستخدم النظام تحليل زمن الاستجابة (RTA) الكلاسيكي لـ Rate-Monotonic لاستخلاص علاقات تكرارية لأوقات الاستجابة في أسوأ حالة، مما يضمن أنه إذا كان $R_i \leq D_i$ ، فإن المهمة قابلة للجدولة.

3. المساهمات الرئيسية

التحليل الهيكلي: تحديد وتوصيف انعكاس الأولوية عبر الـ DAGs كخلل جوهري في منفذات ROS 2 الافتراضية، وإثبات أن توزيع FIFO ينتهك دلالات أولوية الزمن الحقيقي عبر خطوط الأنابيب المستقلة.
النموذج الرسمي للتداخل: تطوير نموذج مهام متعدد الـ DAGs يستند إلى نظرية Rate-Monotonic، مما يوفر حدوداً رياضية للتداخل وعلاقات تكرارية لزمن الاستجابة في بيئة منفذ مشترك.
تنفيذ ReDAGRT: مُجدول يعمل في مساحة المستخدم، كامل الوظائف، يضمن:
- فرض أولوية Rate-Monotonic عالمية.
- دعم الاستباق عبر حدود الـ DAGs.
- لا يتطلب تعديلات في النواة (kernel) أو تغييرات في واجهة برمجة التطبيقات (API).
- يتضمن مراقباً زمنياً للمقاييس الزمنية (التأخر، معدل تجاوز المواعيد النهائية).

4. النتائج التجريبية

تم تقييم إطار العمل في بيئة ROS 2 Humble باستخدام أعباء عمل متعددة الـ DAGs اصطناعية ذات فترات وتدرجات حرجية مختلطة، مقارنة بـ SingleThreadedExecutor و MultiThreadedExecutor (4 خيوط معالجة).

معدل تجاوز المواعيد النهائية (Deadline Miss Rate):
- حقق ReDAGRT انخفاضاً يصل إلى 29.7% في إجمالي معدل تجاوز المواعيد النهائية مقارنة بأفضل تكوينات الخطوط المرجعية تحت الضغط.
- مقارنة بـ MultiThreadedExecutor، أظهر ReDAGRT تحسناً بنسبة 13.7% في معدل التجاوز تحت نفس مستوى الاستغلال.
زمن الاستجابة والارتجاف (Jitter):
- تم ضغط زمن الاستجابة عند المئوية 99 بنسبة 42.9% (انخفض من 49 مللي ثانية إلى 28 مللي ثانية).
- تحسن متوسط زمن الاستجابة من 21 مللي ثانية إلى 14 مللي ثانية.
- أظهر دالة التوزيع التراكمي (CDF) إزاحة كبيرة نحو اليسار، مما يشير إلى حدود ذيل أكثر إحكاماً وقابلية أكبر للتنبؤ.
الحساسية للتزامن:
- قابلية توسع الخيوط: تحسن الأداء بشكل ملحوظ من 4 إلى 8 خيوط (مما قلل معدل التجاوز)، لكنه وصل إلى مرحلة التشبع عند 10 خيوط بسبب عبء التزامن (synchronization overhead).
- الحدود غير المتماثلة: استخدام حدود التزامن غير المتماثلة لكل DAG (على سبيل المثال، تقييد أحد الـ DAGs بصرامة أكبر من الآخر) قلل التداخل بنسبة 40.8% مقارنة بالتكوينات المتماثلة، مما يثبت أن تحديد "البصمة" (footprint) لـ DAGs معينة أمر حاسم لتقليل النزاع العالمي.
التدهور التدريجي (Graceful Degradation): تحت قيود المواعيد النهائية الصارمة (حالات التحميل الزائد)، أظهر ReDAGRT تدهوراً تدريجياً، بينما عانت المنفذات الافتراضية من زيادة كارثية في التأخير (على سبيل المثال، زاد تأخير SingleThreadedExecutor بمقدار رتبتين عشريتين).

5. الأهمية والأثر

الزمن الحقيقي الحتمي لـ ROS 2: يثبت ReDAGRT أن الجدولة المحددة والقابلة للتحليل لمتعدد الـ DAGs ممكنة تماماً ضمن طبقة مساحة المستخدم لـ ROS 2، مما يسد الفجوة بين البرمجيات الوسيطة الروبوتية القياسية ومتطلبات الزمن الحقيقي الحساسة للسلامة.
عدم الاعتماد على النواة: من خلال حل مشكلة الجدولة على مستوى المنفذ، يتجنب الإطار تعقيد وأعباء صيانة تعديلات النواة (مثل رقع PREEMPT_RT) أو تكوينات نظام التشغيل المتخصصة.
النشر في الأنظمة الحساسة للسلامة: يوفر إطار العمل الأساس النظري اللازم (تحليل قابلية الجدولة) والأدلة التجريبية للنشر في الأنظمة السيبرانية الفيزيائية (CPS) التي يكون فيها تجاوز المواعيد النهائية أمراً غير مقبول.
مفتوح المصدر: أصدر المؤلفون التنفيذ الكامل والآثار التجريبية، مما يسهز إعادة الإنتاج والتبني المجتمعي.

في الختام، يحول ReDAGRT نموذج تنفيذ ROS 2 من نظام يعتمد على "أفضل جهد" (best-effort) ونظام FIFO، إلى وقت تشغيل يعتمد على المعدل والأولوية (Rate-Priority)، ويكون استباقياً ومحدود التداخل، مما يتيح أداءً قوياً في الزمن الحقيقي لخطوط الأنابيب الروبوتية المعقدة والمتزامنة.