بدترین زمان اجرا

بیشترین زمان اجرای یک وظیفه روی یک پلتفرم سخت‌افزاری خاص را بدترین زمان اجرای وظیفهٔ محاسباتی می‌گویند.

چه کاربردی دارد؟

بدترین حالت زمان اجرا معمولاً در سیستم عامل بی درنگ کاربرد دارد، جاییکه دانستن بدترین حالت زمانبندی نرم‌افزار برای قابلیت اطمینان و عملکرد صحیح اهمیت دارد.

برای نمونه، یک سیستم کامپیوتری که رفتار موتور را در یک وسیله نقلیه کنترل می‌کند، ممکن است نیاز داشته باشد که به ورودی‌ها در یک بازه مشخصی از زمان پاسخ دهد.

یک بخشی از زمان که زمان پاسخ را تشکیل می‌دهد کل مدت صرف شده برای اجرای نرم‌افزار می‌باشد یعنی از لحظه شروع تا لحظه ای که نرم‌افزار به‌طور کامل اجرا شود اگر مدتی اجرای نرم‌افزار قطع شود بازهم جزو زمان پاسخ آن نرم‌افزار محاسبه می‌شود (بدین ترتیب اگر بدترین زمان اجرای نرم‌افزار مشخص شود طراح سیستم می‌تواند از این مورد با تکنیک‌های دیگر استفاده کند، تکنیک‌هایی مانند سیستم‌های تحلیل زمان‌بندی بی‌درنگ برای اطمینان از اینکه سیستم به اندازه کافی سریع پاسخ می‌دهد.

در حالی که WCET به‌طور بالقوه برای بسیاری از سیستم‌های بی‌درنگ قابل اجراست اما در عمل تضمین WCET توسط سیستم‌های بلادرنگی استفاده می‌شود که در آن‌ها نیاز به قابلیت اطمینان یا ایمنی بالا داریم.

به عنوان نمونه، در نرم‌افزار وسیله‌های هوابرد، مقداری توجه به نرم‌افزار DO178B در بخش ۶٫۳٫۴ مورد نیاز است. استفاده روزافزون از نرم‌افزار در سیستم‌های خودرو نیز نیاز به استفاده از تجزیه و تحلیل نرم‌افزار WCET را افزایش می‌دهد.

WCET اغلب به عنوان یک ورودی برای تجزیه و تحلیل برنامه‌ریزی در طراحی برخی از سیستم‌ها استفاده می‌شود، اگر چه دلیل اینکه استفاده از WCET در سیستم‌های بحرانی بسیار رایج است این است که از نقض نشدن بودجه‌های زمان بندی شده از قبل مشخص شده در یک سیستم برنامه‌ریزی پارتیشن مثل سیستم ARINC 653 اطمینان حاصل شود. (از نقض نشدن ددلاین‌ها در یک سیستم اطمینان حاصل شود)

محاسبه

از روزهای اولیه پردازش نهفته، توسعه دهندگان نرم‌افزار نهفته یا تعبیه شده همچنین از هر دوی موردهای زیر استفاده می‌کنند:

• اندازه‌گیری‌های پایان به پایان از کد، برای نمونه، انجام شده توسط تنظیم یک پین I / O روی دستگاه به بالا در شروع یک وظیفه، و کم در پایان یک وظیفه و با استفاده از یک تجزیه و تحلیل‌کننده منطقی برای اندازه‌گیری طولانی‌ترین پالس عرض، یا با اندازه‌گیری در داخل خود نرم‌افزار با استفاده از ساعت پردازنده یا تعداد آموزش.
• تکنیک‌های تجزیه و تحلیل ایستا دستی مانند شمارش دستورالعمل‌های اسمبلر برای هر تابع، حلقه و غیره و سپس ترکیب آنها.

هر دو تکنیک مطرح شده در بالا دارای محدودیت‌هایی هستند. اندازه‌گیری پایان تا پایان، تست نرم‌افزار برای دست یافتن به طولانی‌ترین مسیر را مجبور به تحمل بار زیادی می‌کند؛ همچنین دستورالعمل‌های شمارش فقط برای نرم‌افزار و سخت‌افزار ساده قابل اجراست. در هر دو مورد، حاشیه خطا اغلب برای کدهای تست نشده، تقریب یا اشتباه عملکرد سخت‌افزاری محاسبه و استفاده می‌شود. اغلب حاشیه ۲۰٪ استفاده می‌شود، اگرچه برای استفاده از این رقم به این شکل توجیه بسیار کمی وجود دارد، صرفاً با توجه به تجارب بدست آمده از مشاهدات پیشین از این رقم استفاده می‌شود ("آخرین بار استفاده از این رقم نتیجه خوبی را نشان داده‌است").

همان‌طور که پیچیدگی نرم‌افزار و سخت‌افزار افزایش یافته‌است، آن‌ها نیاز به پشتیبانی از ابزار دارند. پیچیدگی به‌طور فزاینده ای در تحلیل و اندازه‌گیری‌های ایستا به عنوان یک مشکل مطرح می‌شود. این دشوار است که پیش‌بینی کنیم حاشیه خطا چقدر وسیع می‌شود و آزمایش سیستم نرم‌افزاری چگونه خواهد شد. استدلال‌های ایمنی سیستم بر اساس رسیدن به یک شاخص بالا در طی تست به‌طور گسترده‌ای مورد آزمایش قرار می‌گیرند، اما به ندرت می‌شود این نتایج را به‌طور کامل پذیرفت زیرا نرم‌افزار و سخت‌افزار زیاد قابل پیش‌بینی نیستند.

البته در آینده این احتمال وجود دارد که یک الزام برای ایمنی سیستم‌های بحرانی استفاده شود که آن سیستم‌ها را با استفاده از هر دو روش یعنی روش‌های ایستا و روش‌های مبتنی بر اندازه‌گیری مورد تجزیه و تحلیل قرار دهد.

ملاحظات

مسئله پیدا کردن WCET توسط تجزیه و تحلیل معادل با مسئله توقف است و بنابراین در حالت کلی این مسئله حل نشدنی است. خوشبختانه برای بدست آوردن WCET

در این نوع سیستم‌هایی که مهندسان معمولاً با آن‌ها سروکار دارند نرم‌افزار عمدتاً به خوبی ساختار یافته‌است همچنین این نرم‌افزارها همیشه متوقف می‌شوند و قابل تجزیه و تحلیل هستند.

اکثر روش‌ها برای یافتن یک WCET با یک سری تقریب همراه هستند یا شامل یک سری تقریب هستند (معمولا از روش گرد کردن به سمت بالا، زمانی که عدم قطعیت وجود دارد استفاده می‌شود) و از این رو در عمل مقدار دقیق WCET غالباً غیرقابل دسترس محسوب می‌شود. در عوض تکنیک‌های مختلف که برای پیدا کردن WCET وجود دارند برآوردها یا تخمین‌هایی رو برای مقدار دقیق WCET تولید می‌کنند. این برآوردها معمولاً بدبینانه هستند، به این معنی که WCET تخمین زده شده یا برآورد شده بالاتر از مقدار واقعی WCET (که معمولاً مورد نظر است) می‌باشد. کار زیادی در تجزیه و تحلیل WCET بر روی کاهش این مقدار تخمین زده شده انجام می‌گیرد تا مقدار تخمین زده شده به اندازه کافی پایین باشد که برای طراح سیستم ارزشمند باشد. هدف کم کردن تفاوت بین مقدار اصلی و مقدار تخمین زد شده اولیه است تا به یک مقدار مناسب که به مقدار واقعی نزدک تر است دست یابیم که برای طراح سیستم دارای ارزش باشد.

تحلیل WCET معمولاً به زمان اجرای یک تک نخ، وظیفه یا پردازه اشاره می‌کند. اگر چه، در سخت‌افزارهای مدرن، به خصوص سخت‌افزارهای چند هسته ای، وظایف دیگر در سیستم بر روی WCET یک وظیفه خاص داده شده تأثیر خواهند گذاشت اگر آن‌ها حافظه کش، خطوط حافظه و سایر ویژگی‌های سخت‌افزاری را به اشتراک بگذارند. به علاوه یک سری رویدادهای برنامه‌ریزی وظیفه مثل مسدود کردن یا وقفه‌ها باید در تجزیه و تحلیل WCET در نظر گرفته شوند که ممکن است در یک سیستم مشخص رخ دهند؛ بنابراین، مهم است که زمینه ای را که در آن تحلیل WCET اعمال می‌شود را در نظر داشته باشید.

روش‌های خودکار

روش‌های خودکار بسیاری، فراتر از روش‌های دستی که در بالا مطرح شد برای محاسبه WCET وجود دارند؛ که این روش‌ها شامل:

• تکنیک‌های تحلیلی که باعث بهبود نمونه‌های تست برای افزایش اطمینان در روش اندازه‌گیری پایان تا پایان می‌شوند
• تجزیه و تحلیل ایستا نرم‌افزار ("ایستا یا استاتیک" به معنی بدون اجرای نرم‌افزار).
• ترکیب روش‌ها، اغلب به عنوان "تجزیه و تحلیل ترکیبی" شناخته می‌شود، ترکیبی از اندازه‌گیری و تجزیه و تحلیل ساختاری است.

تکنیک‌های تحلیل ایستا

یک ابزار WCET ایستا تلاش می‌کند تا WCET را با استفاده از بررسی نرم‌افزار کامپیوتری بدون اجرای مستقیم آن بر روی سخت‌افزار، تخمین بزند. تکنیک‌های تجزیه و تحلیل ایستا در اواخر دهه ۱۹۸۰ بخش عمده ای از تحقیقات را به خود اختصاص داده بودند، هرچند در یک محیط صنعتی، روش‌های اندازه‌گیری پایان تا پایان در عمل استاندارد بوده‌است.

ابزارهای تجزیه و تحلیل ایستا در سطح بالا برای تعیین ساختار یک وظیفهٔ برنامه کار می‌کند همچنین این ابزارها بر روی یک تکه کد منبع یا یک تکه کد اجراپذیر دودویی هم کار می‌کند. آن‌ها همچنین در سطح پایین کار می‌کنند، با استفاده از اطلاعات زمانبندی سخت‌افزار واقعی که وظیفه مورد نظر با تمام ویژگی‌های خاص خود بر روی آن اجرا خواهد شد، با ترکیب این دو نوع تجزیه و تحلیل، این ابزار تلاش می‌کند تا یک حد بالای زمانی ارائه دهد که این نشان دهندهٔ حد بالای زمان مورد نیاز برای اجرای یک وظیفه داده شده بر روی یک پلتفرم سخت‌افزاری مشخص است.

در سطح پایین، تجزیه و تحلیل ایستا WCET پیچیده می‌شود حتی با وجود ویژگی‌های معماری که کارایی متوسط پردازنده را بهبود می‌بخشد: دستورالعمل /داده حافظه نهان، پیش‌بینی پرش و دستورالعمل خطوط لوله به عنوان مثال: این شدنی است، اما دشوار می‌شود اگر برای تعیین کردن محدودیت‌های سخت WCET، ویژگی‌های معماری مدرن در مدل زمانبندی بکاررفته در تجزیه و تحلیل، منظور شود. به عنوان مثال، تکنیک‌های قفل حافظه نهان ممکن است برای ساده‌سازی برآورد WCET و ارائه پیش‌بینی استفاده شود.

مسئولین صدور اعتبارنامه مانند آژانس ایمنی هوایی اروپا، به مجموعه‌های اعتبار سنجی مدل تکیه می‌کنند.

جزیه و تحلیل ایستا نتایج خوبی برای سخت‌افزار ساده‌تر به ارمغان آورده‌است، اگرچه محدودیت احتمالی تجزیه و تحلیل ایستا این است که سخت‌افزار (به ویژه CPU) به یک پیچیدگی رسیده باشد که برای مدل کردن بسیار سخت باشد. به‌طور مشخص، فرایند مدل کردن می‌تواند اشتباهات را از چندین منبع ارائه دهد: اشتباهاتی در طراحی تراشه، اشتباهات مرتبط با کمبود اسناد، اشتباهات در اسناد یا سند سازی، اشتباهات در ساخت مدل؛ همه این‌ها منجر به حالاتی می‌شوند که مدل رفتار متفاوتی را با آن که در سخت‌افزار واقعی مشاهده می‌شود پیش‌بینی کند. معمولاً، وقتی که امکان پیش‌بینی کردن دقیق رفتار موردنظر وجود ندارد، از یک نتیجه بدبینانه استفاده می‌شود که می‌تواند WCET را بسیار زیادتر از آن مقداری که در زمان اجرا واقعی بدست می‌آید تخمین بزند یا برآورد کند

به دست آوردن یک تخمین از مقدار WCET ایستا که دارای محدودیت سخت باشد (یعنی اختلاف کمی با مقدار واقعی WCET در عمل داشته باشد) در پردازنده‌های چند هسته ای دشوار است.

تعدادی از ابزارهای تجاری و علمی وجود دارند که انواع و اشکال متفاوتی از تجزیه و تحلیل ایستا را پیاده‌سازی می‌کنند.

اندازه‌گیری و تکنیک‌های ترکیبی

وش‌های مبتنی بر اندازه‌گیری و روش‌های ترکیبی معمولاً تلاش می‌کنند تا زمان اجرای بخش‌های کوتاهی از کد را بر روی سخت‌افزار واقعی اندازه‌گیری کنند، که این‌ها در سطح‌های بالاتر تجزیه و تحلیل، ترکیب می‌شوند. ابزارها در عمل ساختاری از نرم‌افزار (به عنوان نمونه حلقه‌ها، شاخه‌ها) را در نظر می‌گیرند تا یک برآورد یا یک تخمینی از WCET مربوط به یک برنامه بزرگتر را تولید کنند. درحقیقت تست کردن طولانی‌ترین مسیر در یک نرم‌افزار پیچیده، مشکل است، اما تست کردن یا بدست آوردن طولانی‌ترین مسیر در تمامی زیربخش‌های کوچکتر آن نرم‌افزار کار را ساده‌تر می‌کند. اثر بدترین حالت فقط نیاز به یک بار بررسی شدن در طول آزمایش تجزیه و تحلیل دارد تا بتوانیم آن را با سایر بدترین حالت‌ها در تجزیه و تحلیل ترکیب کنیم.

معمولاً، تیکه‌های کوچکی از نرم‌افزار را می‌توان به‌طور خودکار با استفاده از تکنیک‌هایی اندازه‌گیری کرد به عنوان مثال مانند استفاده از ابزار (افزودن نشانگر به نرم‌افزار) یا استفاده از پشتیبانی سخت‌افزاری مانند استفاده از debuggers، و ماژول‌های ردیابی سخت‌افزار CPU. این نشانگرها باعث ردیابی مسیرهای اجرا می‌شوند که این ردیابی‌ها شامل هر دوی این موارد می‌شود هم مسیری که از طریق برنامه اجرا می‌شود را ردیابی می‌کند و هم‌زمانی که نقاط متفاوت اجرا می‌شوند را دربرمیگیرد. پس از این، ردیابی‌های انجام شده تجزیه و تحلیل می‌شوند برای تعیین اینکه حداکثر زمانی که در هر قسمت از برنامه که تا به حال اجرا شده چقدر است و همچنین برای تعیین کردن اینکه حداکثر تکرار زمانی مشاهده شده یرای هر حلقه چقدر است و اینکه آیا بخش‌های از نرم‌افزار وجود دارد که تست نشده (پوشش کد) باشند یا نه؟

تجزیه و تحلیل بر اساس روش‌های مبتنی بر اندازه‌گیری نتایج خوبی را هم برای سخت‌افزار ساده و هم برای سخت‌افزار پیچیده به همراه داشته‌است، اگرچه مثل تجزیه و تحلیل‌های ایستا می‌تواند منجر به تولید مقدار بیش از اندازه بدبینانه WCET در موقعیت‌های چند هسته ای شود، جایی که تعیین کردن تأثیر یک هسته بر روی هسته دیگر مشکل است. یکی از مشکلات یا محدودیت‌هایی که در روش اندازه‌گیری وجود دارد این است که این روش بر مشاهده اثرات بدترین حالت‌ها در طی انجام آزمایش اکتفا می‌کند. اگرچه تشخیص اینکه اثرات بدترین حالت‌ها لزوماً آزمایش شده‌است امی تواند دشوار باشد.

البته تعدادی از ابزارهای تجاری و آموزشی وجود دارند که انواع متفاوتی از تجزیه و تحلیل‌های مبتنی بر اندازه‌گیری را پیاده‌سازی می‌کنند.

پژوهش

فعال‌ترین گروه‌های تحقیقاتی ای که در این زمینه کار می‌کنند در کشورهای زیر مستقر هستند: سوئد (Mälardalen, Linköping)، آلمان (Saarbrücken, Dortmund, Braunschweig)، فرانسه (تولوز، Saclay, Rennes)، اتریش (وین)، بریتانیا (دانشگاه یورک و Rapita Systems Ltd)، ایتالیا (بولونیا)، اسپانیا (کانتابریا، والنسیا) و سوئیس (زوریخ). به تازگی، موضوع تجزیه و تحلیل زمان بندی در سطح کد مورد توجه محققان بسیاری در خارج از اروپا مانند گروه‌های تحقیقاتی در کشورهای ایالات متحده (کارولینای شمالی، فلوریدا)، کانادا، استرالیا، بنگلادش (MBI LAB و RDS)، پادشاهی عربستان سعودی-UQU (HISE LAB) و سنگاپور قرار گرفته‌است.

مسابقه روش‌های WCET

اولین مسابقه بین‌المللی روش‌های تجزیه و تحلیل ابزار WCET در پاییز سال ۲۰۰۶ برگزار شد. این مسابقه توسط دانشگاه Mälardalen برگزار شد و که اسپانسر این مسابقه یک شرکت شبکه ای طراحی سیستم‌های نهفته ARTIST2 بود که از این چالش حمایت کرد. هدف از این چالش بررسی و مقایسه روش‌های مختلف در تجزیه و تحلیل بدترین زمان اجرای نمونه بود. تمام ابزارهای دردسترس و نمونه‌های اولیه که قادر به تعیین مرزهای صحیح برای WCET وظایف بودند شرکت کردند. نتایج نهایی این مسابقه در نوامبر سال ۲۰۰۶ در سمپوزیوم بین‌المللی ISoLA 2006 در پافوس مشخص شد.

مسابقه دوم در سال ۲۰۰۸ برگزار شد.

جستارهای وابسته

• بهترین و بدترین موارد
• نماد بزرگ O
• بهینه‌سازی (علوم کامپیوتری)

منابع

مقالات

• پیش‌بینی زمان اجرای غیرمستقیم توسط تجزیه و تحلیل برنامه استاتیک (PDF)
• تجزیه و تحلیل WCET از سیستمهای سخت‌افزاری سخت‌افزاری (PDF) بایگانی‌شده در ۱۶ فوریه ۲۰۱۲ توسط Wayback Machine
• OTAWA، یک چارچوب برای آزمایش محاسبات WCET (PDF)
• چالش WCET ابزار ۲۰۰۶ تجزیه و تحلیل نتایج آزمون گسترده گزارش نهایی (مقاله مجله در Springer)
• WCET Tool Challenge 2006 گزارش نهایی (PDF)
• چارچوب کامپایلر برای کاهش زمان اجرای بدترین مورد (PDF)

پیوند به بیرون

• CerCo ("پیچیدگی خبره")
• کامپایل WCET-aware / Compiler W CET-aware C WCC