تخمین مبتنی بر تطبیق الگوی بیشترین زمان اجرای توابع بازگشتی در کاربردهای نهفته بی درنگ

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

Keywords:

تخمین بیشترین زمان اجرا , تحلیل زمانی , توابع بازگشتی , سیستم های بی درنگ