بخشی از مقاله
چکیده - استفاده از سیستمهای نهفته در کاربردهای هوانوردی از اهمیت بسزائی برخوردار است. در اغلب سیستمهای نهفته باید محدودیتهای زمانی و نیازمندیهای بیدرنگی برآورده گردد. نیازمندی بیدرنگی در یک سیستم بدین معناست که پردازش قبل از یک مهلت مشخص تمام گردد. با توجه به اینکه زمان اجرای یک وظیفه بر روی یک سخت افزار مشخص در اجراهای مختلف متفاوت است، زمانبند بیدرنگ برای اطمینان از برآورده شدن مهلت وظایف، باید طولانی-ترین مدت زمان اجرای یک وظیفه یا همان بیشترین زمان اجرای - WCET - آن اطلاع داشته باشد. در این مقاله به بررسی روشهای تخمین بیشترین زمان اجرای برنامهها پرداخته شده است و نقاط قوت و ضعف هر یک از این روشها بررسی گردیده است. روش اندازهگیری گرچه ساده و آسان میباشد اما مقدار تخمینی مطمئن نیست. در مقابل روش تحلیل ایستا روشی مطمئن بوده و تلاش میگردد که مقدار بیشتخمین کم گردد و مقدار تخمینی به مقدار واقعی نزدیک باشد اما موفقیت آن وابسته به تحلیل زمانی سختافزار میباشد. برای کاربردهای اویونیک مطابق با استانداردها روشهای صوری پیشنهاد گردیده است.
استفاده از پردازندههای نهفته1در در کاربردهای مختلفی مانند مخابرات، کاربردهای هستهای، خودرو و ... رو به افزایش است. در میان این سیستمها، سیستمهای نهفته در هوانوردی از اهمیت بیشتری برخوردارند. به عنوان مثال در هواپیمای بوئینگ 777 تعداد 1280 پردازنده و بیش از چهار میلیون خط نرمافزار استفاده شده است.[1] در اغلب سیستمهای نهفته برآورده شدن محدودیتهای زمانی و نیازمندیهای بیدرنگی از اهمیت خاصی برخوردار است. نیازمندی بیدرنگی در یک سیستم بدین معناست که اگر پردازش قبل از یک مهلت2 مشخص تمام نگردد، کارایی سیستم کاهش یافته و یا اینکه دچار خرابی میگردد.[2] بنابراین برای سنجش صحت عملکرد اینگونه از سیستمها، نیاز است که زمان اجرای یک وظیفه معلوم باشد. اما زمان اجرای یک وظیفه بر روی سخت افزار مشخص در اجراهای مختلف، متفاوت بوده و نیاز خواهد بود طولانیترین زمان اجرای وظیفه از لحاظ زمانی در نظر گرفته شود، این زمان، بیشترین زمان اجرا - WCET - نامیده میشود و بدین صورت تعریف میگردد : کران بالای زمان اجرای قطعه کدی از یک نرمافزار که منظور از زمان اجرای قطعه کد مدت زمانیست که طول می کشد تا پردازنده قطعه کد را اجرا نماید.
محاسبه بیشترین زمان اجرای واقعی یک قطعه کد بسادگی میسر نمیباشد زیرا زمان اجرای قطعه کد به سخت افزار - مانند حافظه نهان، خط لوله و ... - و به معنای نرم افزار یا برنامه - مثل یافتن طولانیترنی مسیر اجرایی در برنامه - و تاثیر این دو عامل برهم، وابسته است.[3] بنابراینمعمولاً تلاش میگردد بیشترین زمان اجرای قطعه کد تخمین زده شود. مطلوب، یافتن یک تخمین از بیشترین زمان اجرای قطعه کد میباشد. علاوه بر اینکه بیشترین زمان اجرای تخمینی باید مطمئن4 باشد - تضمین نماید که قیود بیدرنگی برآورده میگردد - ، این تخمین باید نزدیک5 به بیشترین زمان اجرای واقعی باشد. در این مقاله به بررسی روشهای مختلف تخمین بیشترین زمان اجرای برنامهها پرداخته شده است و مزایا و معایب هر یک از روشها مورد بررسی قرار گرفته است.در ادامه این مقاله در بخش 2 کارهای مرتبط در حوزه اویونیک مورد بررسی قرار گرفته است. در بخش 3 مفاهیم پایه بیشترین زمان اجرا بیان شده است. در بخش 4 انواع روشهای تحلیل WCET بررسی گردیده است. در بخش 5 به بحث و بررسی پرداخته و روشها با یکدیگر مقایسه شدهاند. مقاله با بخش نتیجهگیری به پایان رسیده است.
-2 کارهای مرتبط
هواپیماهای امروزی دارای چندین سیستم اویونیک هستند که برای امنیت پرواز بسیار مهم میباشند. این سیستمها معمولا به عنوان سیستمهای بیدرنگ سخت شناخته میشوند. بدین معنی که باید وظیفه و کار خود را در مهلت مشخصی به انجام برسانند در غیر اینصورت یک وضعیت شکست همانگونه در CS-25 ذکر شده بوجود خواهد آمد.[4] برای اطمینان از صحت عملکرد این سیستمها، وارسی و صحتسنجی لازم بر اساس استانداردهای جهانی مانند DO-178 صورت میگیرد که تحلیل WCET یکی از مسائل برای بررسی صحت نیازمندیهای غیرعملکردی این سیستمها میباشد. پژوهشهایی زیادی در حوزه تحلیل WCETو مشخصاً برای سیستمهای اویونیک انجام شده است. در [6] کران تکرار حلقهها برای تخمین WCET محاسبه گردیده است. در این مقاله یک روش صوری6 وارسی تخمین کران تکرار حلقه در کامپایلر ComCert مجتمع گردیده است. ComCert یک کامپایلر برای نرمافزارهای کنترل پرواز میباشد که ایرباس از آن در محیط واقعی استفاده مینماید. در[7] روشی برای تحلیل WCET در نرمافزارهای همروند اویونیک در صنعت هوایی ارائه گردیده است. روش ارائه شده یک روش صوری و مبتنی بر تحلیل ایستاست که عملکرد آن بر روی نرمافزارهای اویونیک ARINC 653 ارزیابی گردیده است. همچنین روشهای [8] و [9] برای تخمین WCET کاربردهای اویونیک اجرا شده بر روی معماریهای چند هستهای ارائه گردیده است.
-3 مفاهیم پایه بیشترین زمان اجرا
هدف از تحلیل بیشترین زمان اجرای یک قطعه کد ارائه تخمینی از بیشترین زمان اجرای آن میباشد. برای سنجش صحت سیستمهای بیدرنگ سخت، WCET تخمینی باید مطمئن باشد، بدین معنی که تضمین گردد تخمین کمتر از WCET واقعی نباشد. همچنین مقدار تخمینی باید به مقدار واقعی WCET نزدیک باشد و فقط تاحدی تخمین بیشتری از مقدار واقعی WCET قابل قبول میباشد. باید به این نکته توجه داشت که تحلیل WCET مربوط به یک برنامه و یا قطعهای از کد یک برنامه میباشد. این بدین معنی است که تحلیل WCET در خصوص تعدادی برنامه یا وظیفه نیست که روی یک سختافزار و سیستم عامل اجرا می-شوند. بررسی اجرای چندین برنامه در سطوح بالاتری از طراحی نرمافزار مانند تحلیل قابلیت زمانبندی صورت میگیرد. عدم ثابت بودن زمان اجرای برنامهها مشکلی است که سبب شده تحلیل WCET برای برنامهها صورت پذیرد. زمان اجرای برنامه بر اساس مسیری است که برنامه از طریق آن اجرا میشود. عوامل موثر بر انتخاب مسیر و همچنین زمان اجرای دستوراتی که روی این مسیر قرار دارد سبب متفاوت بودن زمان اجرای برنامه میگردد. بطور کلی متفاوت بودن زمان اجرای برنامهها در اجراهای مختلف بر روی یک بستر سختافزاری یکسان ناشی از دو عامل میباشد:
رفتار نرم افزار: دلیل استفاده از کامپیوترهای نهفته قابلیت برنامهنویسی آنها میباشد. با طراحی نرمافزار میتوان وظایف جدیدی را تعریف و در یک سیستم نهفته استفاده نمود. برای کدنویسی از حلقههای تودرتو، دستورات شرطی پیچیده و اشاره-گرها استفاده مینمایند. با بکارگیری این ساختارها برای پیاده-سازی منطق برنامه، کد پیچیدهای تولید میگردد که تحلیل آن بسیار مشکل خواهد بود. برای یافتن طولانیترین مسیر از لحاظ زمانی در یک برنامه عواملی که باعث انتخاب این مسیر میشود باید شناسایی و تحلیل گردد. پارامترهای ورودی، تعداد تکرار حلقهها، عمق فراخوانی توابع بازگشتی، مسیرهای اجرا نشدنی و ... از عواملی هستند که بر انتخاب مسیر اجرایی برنامه تاثیر می-گذارند. این عوامل رفتار نرمافزار را نشان میدهد.
جنبههای سخت افزاری: تحلیل زمانی بدون در نظر گرفتن جنبههای سخت افزاری امکانپذیر نیست؛ چون نهایتاً برنامه باید روی این سختافزار اجرا گردد و در حقیقت دنبالهای از دستورات ماشین است که برنامه را میسازند. هر چقدر سختافزارها سومین کنفرانس ملی اویونیک پیچیدهتر شدهاند بهمان نسبت تحلیل زمانی پیچیدهتر و مشکلتر اجرای برنامه گردد. درحقیقت برنامه باید با تمام ورودیهای گردیده است. مهمترین مسئله در تحلیل زمانی سختافزار رفتار ممکن اجرا شود که در عمل امکانپذیر نیست. پردازنده و حافظه میباشد. سایر اجزای یک سیستم کامپیوتری • اندازهگیری اغلب نیاز دارد که کد مستندگذاری گردد،مثل ورودی/خروجی، شبکه و ... تاثیر بسیار کمی در زمان مانند درج نمودن دستوراتی در کد برنامه. اما سیستمهای برنامهها دارند. در پردازندهها قدیمی زمان اجرای هر دستور بحرانی ایمن اغلب بیشترین زمان اجرای همان کدی که در ماشین ثابت بود یا میزان تغییر آن بسادگی قابل محاسبه بود.آخرین محصول تولید شده را میخواهند. چون خط لوله یا حافظه نهان7 استفاده شده بسیار ساده بوده و مهمترین مزیت روشِ اندازهگیری سادگی کار آنست. بیشتر براحتی قابل تحلیل بوده است. اما در پردازندهها مدرن امروزی، در صنایعی استفاده میگردد که سختافزار و یا شبیهساز آن دربه منظور دستیابی به کارایی بالاتر، مجهز به حافظه نهان، خط دسترس میباشد. چون مقدار تخمینی مطمئن نیست همیشه لولههای پیشرفته و امکان پیشبینی انشعابها شدهاند. این میزانی به مقدار اندازهگیری شده اضافه میگردد که سبب بیش امکانات سبب شده که زمان اجرای هر دستور متغیر باشد و برآورد9 میگردد.[3] بطور کلی روش اندازهگیری برای سیستم براحتی محاسبه نگردد.های بیدرنگ نرم مناسب میباشد.
-4 روشهای تخمین بیشترین زمان اجرا
-2-4 تحلیل ایستا بطور کلی تخمین بیشترین زمان اجرای برنامه به سه روش امکانپذیر است:
· روش پویا - اندازه گیری یا تجربی -
· روش ایستا - تحلیل ایستا -
هر یک از روشهای فوق در ادامه شرح داده شده است.
-1-4 روش اندازه گیری8
اندازه گیری یک روش پویا در تخمین زمان اجرای برنامه میباشد. در این روش برنامه بر روی سختافزار واقعی و یا در یک شبیهساز اجرا میگردد و زمان اجرا اندازهگیری میگردد. بعضاً در کد برنامه کدهایی در نقاط مختلف درج شده تا به کمک این کدها زمان اجرای قطعات محصور بین این کدها را محاسبه نماید. نمونه دادههای ورودی به برنامه به نحوی آماده میگردند که سناریویی اجرا گردد تا بیشترین زمان اجرای برنامه قابل اندازهگیری باشد. این روش دارای دو نقص میباشد:
• روش اندازهگیری مطمئن نیست. بعبارت دیگر میزان تخمینی بیشترین زمان اجرا همیشه کمتر یا مساوی مقدار واقعی بیشترین اجرا میباشد. زیرا نمیتوان دادههای ورودی را به نحوی بدست آورد تا منجر به رفتار بیشترین زمان در روش تحلیل ایستا، خصوصیاتی از برنامه که بر رفتار زمانی آن تاثیر میگذارد بصورت ایستا و بدون اجرای برنامه تحلیل میگردد. باید اطلاعاتی از عوامل موثر بر اجرای برنامه، هم رفتار نرمافزار و هم جنبههای سختافزاری، برای تخمین نزدیک و مطمئن WCET بدست آوردمعمولاً. تحلیل ایستای WCET در سه فاز انجام میگردد: فاز تحلیل جریان - تحلیل سطح بالا - ، فاز تحلیل سطح پایین - تحلیل رفتار پردازنده - و فاز محاسبات. این سه فاز را میتوان بصورت مستقل از هم انجام داد که در ادامه این بخش هر فاز شرح داده شده است.
-1-2-4 تحلیل جریان10
هدف از فاز تحلیل جریان، استخراج کرانهایی روی مسیرهای اجرایی ممکن برنامه میباشد تا رفتار پویای برنامه تحت تحلیل را بدون اجرای آن تعیین نماید. بطور خاص تعیین طولانیترین مسیر اجرایی برنامه نیاز به تعداد تکرار حلقهها دارد. تحلیل ایستای حلقها برای یک فضای برنامه حقیقی عموماً تصمیمناپذیر است چون نیاز به اثبات خاتمه دارد.[11] بنابراین تحلیل کامل برنامه بصورت خودکار فقط برای مجموعهی محدودی از برنامهها ممکن است[12] و نیاز است که اطلاعات جریان مانند تعداد تکرار حلقهها بوسیله برنامهنویس بصورت
