تحسين تصميم وتحليل التطبيق لخوارزمية الجدولة على متن الطائرة

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

“

1 المقدمة

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

2 جدولة تحليل الخوارزمية

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

2.1 خوارزمية جدولة RMS

تم تقديم خوارزمية RMS في عام 1973 بواسطة C. L. Liu و J. مقترح من قبل Layland. الخوارزمية هي طريقة جدولة مهمة تعتمد على إحصائيات تكرار تنفيذ المهام. تقوم خوارزمية RMS بتعيين الأولوية القصوى للمهمة ذات أعلى تردد تنفيذ ، وتخصيص الأولوية للمهام المتبقية بترتيب رتيب. في التحليل ، تضع خوارزمية RMS الافتراضات التالية:
جميع المهام دورية.
ليست هناك حاجة للتزامن بين المهام ، ولا توجد موارد مشتركة ، ولا يوجد تبادل بيانات بين المهام ؛
يجب أن تقوم وحدة المعالجة المركزية دائمًا بتنفيذ المهمة ذات الأولوية القصوى وفي حالة الاستعداد ، أي يجب استخدام طريقة جدولة kernel الوقائية.

نظرًا للأسلوب الوقائي ، تستبق المهمة ذات الأولوية العالية المهمة قيد التشغيل ذات الأولوية الأقل بمجرد أن تصبح جاهزة. بافتراض وجود مهام مختلفة في النظام ، نظرًا لأن خوارزمية RMS تتطلب أن تفي المهام الدورية المستقلة المجدولة دائمًا بمواعيدها النهائية ، أي أن جميع المهام في النظام يجب أن تفي بشروط الوقت الفعلي الصعبة ، وبالتالي فإن أوجه عدم المساواة التالية هي أنشئت:

في الصيغة: المملكة المتحدة هي أطول وقت تنفيذ للمهمة k ، Tk هي دورة تنفيذ المهمة k ، و Vk / Tk هو معدل استخدام وقت وحدة المعالجة المركزية الذي تتطلبه المهمة k. عندما يميل عدد المهام n في النظام إلى اللانهاية ، تكون قيمة S (n) هي Ln2 ، أي 0.693. لذلك ، لجعل جميع المهام تلبي متطلبات الوقت الفعلي الصعبة ، لدينا:

أي أن إجمالي استخدام وقت وحدة المعالجة المركزية لجميع المهام المحددة زمنياً يجب أن يكون أقل من 70٪. في الواقع ، في تصميم النظام ، ليس من الجيد جعل استخدام وقت وحدة المعالجة المركزية يصل إلى 100٪. في هذه الحالة ، لا يوجد مجال لتعديل البرنامج ، ولا يمكن إضافة وظائف جديدة. من الناحية العملية ، يجب أن يكون استخدام الوقت لوحدة المعالجة المركزية أقل من 60٪ إلى 70٪. تتمثل مزايا خوارزمية RMS في المرونة القوية ، وانخفاض النفقات العامة ، والاختبار البسيط للمكونات القابلة للجدولة. لكن في بعض الحالات. المهام التي يتم إجراؤها بشكل متكرر ليست هي المهام الأكثر أهمية.

2.2 خوارزمية جدولة EDF

تعد خوارزمية جدولة EDF الوقائية عبارة عن خوارزمية جدولة ديناميكية تعتمد على الأولوية تعتمد فيها الأولوية المعينة لكل مهمة على متطلباتها الحالية للموعد النهائي. المهمة ذات الموعد النهائي الأقرب للطلب الحالي لها الأولوية القصوى ، بينما يتم تعيين الأولوية الأقل للمهمة ذات الموعد النهائي للطلب الأبعد. تضمن هذه الخوارزمية عدم وجود وقت خمول للمعالج حتى يتعذر الوفاء بالموعد النهائي للمهمة.

ج. ل. ليو وج. أثبت Layland أنه بالنسبة لمجموعة من المهام n ، فإن الشروط الممكنة لخوارزمية الجدولة المدفوعة بالموعد النهائي هي:

يمكن قياس أطول وقت استجابة Tr للمهمة ، ولا يمكن جدولة المهمة إلا إذا كانت Tr أقل من الموعد النهائي. بالنسبة لـ Tr يمكن التعبير عنها على النحو التالي:

حيث Trun_i هو وقت تنفيذ المهمة i ؛ Tlok_i هو وقت الحظر للمهمة i ؛ Tspd_i هو الوقت الزائد لجدولة المهمة i ؛ Trdy_j هو الوقت الذي تكون فيه المهمة j جاهزة مرة أخرى ؛ max {Tr / Trdy_j} ・ Trun_j هو مهمة ذات أولوية منخفضة إجمالي الوقت الذي تشغله المهام ذات الأولوية العالية بعد حرمان i من المهمة ذات الأولوية العالية j.

أكبر ميزة لخوارزمية جدولة EDF الوقائية هي أنها فعالة للغاية عندما يكون الحمل على النظام منخفضًا نسبيًا. بالنسبة لمجموعة مهام معينة ، طالما أن استخدام المعالج لا يتجاوز 100٪ ، يمكن ضمان جدولة . عيب EDF هو أنه لا يمكنه حل مشكلة التحميل الزائد. عندما يكون حمل النظام ثقيلًا ، فقد يتسبب ذلك في تفويت عدد كبير من المهام للموعد النهائي ، مما يؤدي إلى قضاء الكثير من وقت وحدة المعالجة المركزية في الجدولة ، ويكون أداء النظام كبيرًا جدًا قليل.

2.3 خوارزمية جدولة محسنة

في نظام الوقت الحقيقي المضمن ، تكون الموارد محدودة للغاية ، لذا يجب تقليل النفقات العامة قدر الإمكان ؛ وتكمن مشكلة خوارزميات جدولة RMS و EDF في النفقات العامة – تشغيل النفقات العامة وجدولة النفقات العامة. في هذا البحث ، مع أخذ uC / OS-II كمثال ، جنبًا إلى جنب مع خوارزمية جدولة Linux ، تم تحسين خوارزمية جدولة المهام لنواة uC / OS-II. إنها خوارزمية جدولة تجمع بين الجدولة الوقائية والجدولة الزمنية لشريحة زمنية دائرية ، ولا يتغير حمل النظام كثيرًا.

بأخذ مهمة الحصول على البيانات المشتركة في نظام السيارة كمثال ، يمكن تعيين العمليات الثمانية في الجدول الجاهز uC / OS-II كعملية مخصصة للحصول على البيانات. بالنسبة لهذه العمليات الثماني ، يتم استخدام خوارزمية جدولة مهمة تدوير الشريحة الزمنية ، ويتم إضافة عداد متغير إلى كتلة التحكم TCB كوزن لجدولة المهام. إذا كانت هناك مهمة ذات أولوية أعلى من هذه العمليات الثمانية في قائمة الانتظار الجاهزة ، فسيتم التخلي عن حق استخدام وحدة المعالجة المركزية دون قيد أو شرط ، وينفذ النظام إجراء تبديل المهام. إذا كانت العملية ذات الأولوية القصوى في قائمة الانتظار الجاهزة الحالية تنتمي إلى إحدى العمليات الثمانية المخصصة لجمع البيانات ، فسيتم اجتياز جميع العمليات المخصصة لجمع البيانات الجاهزة بالتسلسل ، ويتم حساب قيمة عداد شريحة الوقت ، ويتم إخراج العملية ذات أكبر شريحة زمنية للتشغيل. إذا تمت مصادفة عملية بنفس حجم شريحة الوقت ، فسيتم إخراج العملية ذات الأولوية الأعلى للتشغيل. خوارزمية جدولة المهام المحسنة كما يلي:

3 قضايا أخرى يجب ملاحظتها

(1) التصغير

الموارد التي توفرها الأجهزة داخل السيارة محدودة ، لذا يجب أن يكون نظام التشغيل داخل السيارة صغيرًا لتلبية قيود أجهزة النظام. Microkernel هي فكرة تصميم مفتوحة تفصل بين الآلية والاستراتيجية ، وقد حلت تدريجياً محل المفهوم الأصلي أحادي النواة وأصبحت الاتجاه السائد لتصميم هيكل نظام التشغيل. تعد الوحدات النمطية وقابلية التكوين التي توفرها فكرة microkernel مناسبة لاحتياجات بيئة التطبيق المضمنة.

(2) أداء قوي في الوقت الحقيقي

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

(3) ثبات عالي

بمجرد تشغيل المعدات الموجودة في السيارة ، لا يلزم التدخل البشري. في ظل هذه الحالة ، يجب أن يتمتع نظام التشغيل داخل السيارة المسؤول عن إدارة النظام بدرجة عالية من الثبات.

(4) يمكن قصها

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

4. الخلاصة

تم تصميم إستراتيجية جدولة kernel لنظام التشغيل داخل السيارة لبيئة التطبيق الخاصة بالنظام داخل السيارة ، وتفي بمتطلبات التصميم الخاصة بمزيج من جدولة استباق المهام وجدولة الوقت المستدير. في الوقت الحالي ، دخل النظام في مرحلة التعديل والتصميم التفصيليين ، وستكون الخطوة التالية هي إجراء المزيد من اختبارات الزرع لنظام التشغيل لجعله يلبي بشكل أفضل متطلبات المعدات الموجودة في السيارة.