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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 مراجع 

 المقالات 

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

 روابط خارجية 

 CerCo ("التعقيد المعتمد")
 التجميع المتوافق مع WCET / مُجمِّع C المتوافق مع WCET WCC
تصنيف:حوسبة في الزمن الحقيقي