انجمن کامپیوتر ایران

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