مرجع
آخر الزيارات

أسوأ وقت للتنفيذ

1٬475 كلمة•0 مشاهدة•🗒️ منذ 5 أيام
باختصار: أسوأ وقت تنفيذ ( WCET : worst-case execution time ) لمهمة حسابية هو أقصى طول للوقت الذي قد تستغرقه المهمة للتنفيذ على منصة أجهزة محددة. تتناول المقالة 8 أقسام، منها «تقنيات التحليل الثابت»، «الاعتبارات» و«القياس والتقنيات الهجينة».
المحتويات
  1. تقنيات التحليل الثابت
  2. الاعتبارات
  3. القياس والتقنيات الهجينة
  4. العملية الحسابي
  5. المقالات
  6. أبحاث علمية
  7. تحدي أداة WCET
  8. النهج الآلي

في البداية، أسوأ وقت تنفيذ ( WCET : worst-case execution time ) لمهمة حسابية هو أقصى طول للوقت الذي قد تستغرقه المهمة للتنفيذ على منصة أجهزة محددة. وفيما يلي تفاصيل أوسع عن ذلك.

وفي السياق ذاته، في تصميم بعض الأنظمة، يُستعمل وقت التنفيذ في أسوأ الحالات (WCET) غالبًا كمدخل لتحليل الجدولة، على الرغم من أن الاستخدام الأكثر شيوعًا لـ WCET في الأنظمة الحرجة هو لضمان عدم تجاوز الميزانيات الزمنية المخصصة مسبقًا في الأنظمة التي تعتمد على الجدولة بالتقسيم، مثل نظام ARINC 653.

ومن ناحية أخرى، على الرغم من أن وقت التنفيذ في أسوأ الحالات (WCET) قابل للتطبيق في الكثير من الأنظمة الزمنية الحقيقية، إلا أنه في الممارسة العملية يُستعمل ضمان WCET بشكل أساسي في الأنظمة الزمنية الحقيقية التي تتعلق بالموثوقية العالية أو السلامة. فمثلًا، يتطلب البرمجيات المستعملة في الطيران اهتمامًا خاصًا بحسب المواصفة DO178C في القسم 6.3.4. كما أن الاستخدام المتزايد للبرمجيات في أنظمة السيارات يدفع كذلك إلى الحاجة لاستخدام تحليل WCET للبرمجيات.

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

لِماذا يُستعمل؟

علاوةً على ذلك، يُستعمل وقت التنفيذ في أسوأ الحالات عادةً في الأنظمة الزمنية الحقيقية الموثوقة، حيث يكون فهم سلوك التوقيت في أسوأ الحالات للبرمجيات أمرًا مهمًا من أجل الموثوقية أو الأداء الوظيفي الصحيح.

تقنيات التحليل الثابت

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

في هذا الإطار، يعد الحصول على تقدير WCET ثابتًا ودقيقًا أمرًا صعبًا بشكل خاص على المعالجات متعددة النواة.

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

من جهة ثانية، هناك عدد من الأدوات التجارية والأكاديمية التي تنفذ أشكالًا مختلفة من التحليل الثابت.

وفي هذا السياق، لذلك، تعتمد هيئات التصديق، مثل وكالة سلامة الطيران الأوروبية ، على مجموعات التحقق من صحة النماذج. [ بحاجة لمصدر ]

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

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

الاعتبارات

علاوةً على ذلك، إن مشكلة إيجاد WCET بالتحليل تُعادل مسألة توقف ، وبالتالي فهي غير قابلة للحل عمومًا. لحسن الحظ، بالنسبة لنوع الأنظمة التي يرغب المهندسون عادةً في إيجاد WCET لها، عادةً ما يكون البرنامج مُهيكلًا جيدًا، ويتوقف دائمًا، وقابلًا للتحليل.

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

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

القياس والتقنيات الهجينة

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

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

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

العملية الحسابي

كذلك، وفي المستقبل، من المرجح أن يكون أحد متطلبات أنظمة السلامة الحرجة هو تحليلها باستخدام كل من الأساليب الثابتة والقياسية. [ بحاجة لمصدر ]

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

من جهة ثانية، كلتا التقنيتين لهما حدود. فالقياسات الشاملة تُثقل كاهل اختبار البرمجيات لتحقيق أطول مسار؛ بينما لا ينطبق عدّ التعليمات إلا على البرمجيات والأجهزة البسيطة. في كلتا الحالتين، يُستعمل هامش الخطأ غالبًا لمراعاة التعليمات البرمجية غير المُختبرة، أو تقديرات أداء الأجهزة، أو الأخطاء. يُستعمل هامش 20% غالبًا، على الرغم من عدم وجود مبرر يُذكر لهذا الرقم، باستثناء الثقة التاريخية ("لقد نجح الأمر في المرة الأخيرة").

وعلى صعيد آخر، منذ بدايات الحوسبة المدمجة، كان مطورو البرمجيات المدمجة يستعملون إما:

وعلى صعيد آخر، تقنيات التحليل الساكن اليدوي مثل عدّ تعليمات المُجمّع (Assembler) لكل دالة أو حلقة وغيرها، ثم دمجها معًا.

علاوةً على ذلك، قياسات شاملة من البداية إلى النهاية للشفرة، مثلًا من خلال ضبط دبوس إدخال/إخراج (I/O) على الجهاز إلى الحالة العالية في بداية المهمة، ثم إلى الحالة المنخفضة في نهايتها، واستخدام محلل منطقي لقياس أوسع عرض نبضة، أو من خلال القياس داخل البرمجية نفسها باستخدام ساعة المعالج أو عدد التعليمات.

المقالات

  • أطر تدفق البيانات لتحليل وقت التنفيذ في أسوأ الحالات
  • التنبؤ بوقت التنفيذ في أسوأ الحالات باستخدام تحليل البرامج الثابتة (PDF)
  • OTAWA، إطار عمل لتجربة حسابات WCET (PDF)

إطار عمل للمترجم لتقليل أوقات التنفيذ في أسوأ الحالات (PDF)

علاوةً على ذلك، تحليل نتائج الاختبار الموسع لتحدي أداة WCET لعام 2006 للتقرير النهائي (مقالة في مجلة Springer)

التقرير النهائي لتحدي أدوات WCET لعام 2006 (PDF)

أبحاث علمية

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

تحدي أداة WCET

مراجع

أقيم التحدي الثاني في سنة 2008.

ومن ناحية أخرى، أُقيم أول تحدي دولي لأدوات WCET في خريف عام 2006. وقد نظمته جامعة مالاردالين ، وبرعاية شبكة ARTIST2 للتميز في تصميم الأنظمة المدمجة. وكان الهدف من التحدي فحص ومقارنة مختلف المناهج المستعملة في تحليل أسوأ زمن تنفيذ. وشاركت جميع الأدوات والنماذج الأولية المتاحة القادرة على تحديد الحدود العليا الآمنة لمهام WCET. وعُرضت النتائج النهائية في نوفمبر 2006 في ندوة ISoLA الدولية لعام 2006 في بافوس ، قبرص.

النهج الآلي

كذلك، تقنيات تحليلية لتحسين حالات الاختبار لزيادة الثقة في القياسات الشاملة

في هذا الإطار، هناك الكثير من الطرق الآلية لحساب WCET، إلى جانب الطرق اليدوية المذكورة أعلاه. وتشمل هذه الطرق:

التحليل الثابت للبرنامج (معنى "ثابت" بدون تنفيذ البرنامج).

من جهة ثانية، الأساليب المشتركة، والتي يشار إليها غالبًا باسم التحليل "الهجين"، وهي عبارة عن مزيج من القياسات والتحليل الهيكلي

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.