بخشی از مقاله
تحمل پذيري خطا در سيستم هاي تعبيه شده بلادرنگ
خلاصه : تحمل پذيري خطا يکي از جنبه هاي مهم سيستم هاي تعبيه شده بلادرنگ است . درسيستم هاي بلادرنگ ، فرآيندها به دلايل مختلف دچار خطا مي شوند. فرآيندهاي معيوب اجتناب ناپذيرند و مي توانند کارايي کل سيستم را دچار مشکل کنند و پيامد خطرناکي را به دنبال داشته باشد. در زمان توسعه سيستم تعبيه شده بلادرنگ فراهم کردن ضمانت انجام فرآيندهايي که با محدوديت زماني مواجه مي شوند لازم است .
بنابراين الگوريتم هاي زمانبندي اهميت زيادي دارند. در اين مقاله روش هاي تحمل پذيري خطا در سيستم هاي تعبيه شده شامل DMS، ADM، زمانبندي ايستا و نيمه ايستا را مرور کرده و مزايا و معايب هر روش را بيان مي کنيم . سپس يک روش ترکيبي را که باعث افزايش سرعت الگوريتم نيمه ايستا خواهد شد، پيشنهاد مي دهيم .
کلمات کليدي : تحمل پذيري خطا، الگوريتم هاي زمانبندي، الگوريتم نيمه ايستا و نقاط بازيابي .
١ - مقدمه
برنامه هاي کاريردي ايمني -بحراني بطور صحيح و با در نظر گرفتن محدوديت هاي زماني، حتي در صورت رخداد خطا وظيفه خود را انجام مي دهند. اين خطاها مي تواند پايدار (مثل خرابي ميکروکنترل ها يا خطوط ارتباطي ) يا ناپايدار (مثل اشکالات الکترومغناطيسي ) يا متناوب و دوره اي (ظاهر شدن و ناپديد شدن بطور مکرر) باشند[١]. خطاهاي ناپايدار متداول ترين نوع خطا است و تعدادشان در طول افزايش پيچيدگي، کوچکتر شدن سايز ترانزيستورها و سطوح پايين ولتاژ بيشتر مي شود[١].
نرخ خطاهاي ناپايدار اغلب در مقايسه با خطاهاي پايدار بيشتر است .
نسبت خطاي ناپايدار به پايدار بين ٢:١ و ٠:١ ٠ ١ يا بالاتر باشد. از نقطه تحمل پذيري خطا، خطاهاي ناپايدار و متناوب به صورت مشابه آشکار مي شوند، براي يک لحظه کوتاه اتفاق مي افتند و سپس بدون اينکه موجب خرابي پايدار شوند ناپديد مي شوند. بنابراين تکنيک هاي تحمل پذيري خطا در برابر خطاهاي ناپايدار قابل استفاده براي تحمل پذيري در برابر خطاهاي متناوب نيز مي باشد. در اين مقاله ، ما به هر دو نوع خطا تحت عنوان خطاهاي ناپايدار اشاره خواهيم کرد و درباره تحمل پذيري در برابر خطاهاي ناپايدار (که شامل هر دو خطاي ناپايدار و پايدار است ) صحبت خواهيم کرد.
بطور متداول ، تکرار سخت افزاري ١ براي تحمل پذيري در برابر خطاهاي پايدار استفاده مي شود که اين روش پر هزينه است [٢].
همچنين باعث افزايش ابعادي سيتم تعبيه شده مي گردد، در حاليکه يکي از معيارهاي مقايسه سيستم هاي تعبيه شده کوچکي اندازه آنهاست . از سوي ديگر براي کاهش هزينه ، تکنيک هاي ديگري مثل تکرار نرم افزاري نياز است . استفاده از اجزا سريعتر يا تعداد زيادي از منابع باعث افزايش هزينه مي شود. بنابراين تکنيک هاي طراحي بهينه به در نظر گرفتن محدوديت هاي زماني و هزينه اي براي سيستم هاي تحمل پذير خطا نياز دارد. لذا استفاده از تکرار سخت افزاري عاقلانه به نظر نمي رسد.
در حقيقت براي کاهش هزينه ، تکنيک هاي ديگري مثل تکرار نرم افزاري نياز است . تشخيص خطا و مکانيسم هاي تحمل پذيري خطا قسمتي از معماري نرم افزار هستند.
در اين مقاله به دنبال راهي براي افزايش سرعت اجراي الگوريتم زمانبندي نيمه ايستا هستيم بطوريکه زمان اجراي آن کوتاهتر شود. جنبه هاي اصلي کار مورد بحث در ادامه آورده شده است :
• مروري بر روش هاي تحمل پذيري خطا در سيستم هاي تعبيه شده بلادرنگ
• بيان مزايا و معايب اين روش ها
• ترکيب مناسب تکنيک هاي خطا براي افزايش کارايي .
٢ - مروري بر روش هاي تحمل پذيري خطا در سيستم هاي تعبيه شده بلادرنگ
تشخيص خطا يکي از جنبه هاي مهم تحمل پذيري خطا مي باشد که بطور گسترده اي مورد تحقيق و پژوهش قرار مي گيرد. تعداد زيادي از متدهاي سخت افزاري و نرم افزاري براي تشخيص خطا به وجود آمده و منتشر شده است . قدم بعدي پاسخ به يک خطاي ناپايدار و زودگذر است . که چندين الگوريتم براي اينکار معرفي شده اند.
٢-١ الگوريتم هاي زمانبندي فرجه يکنواخت ١ و فرجه يکنواخت قابل تطبيق ٢
يکي از الگوريتم هاي تحمل پذيري خطا DMS است . DMS مخفف Deadline Monotonic Scheduling، است که محدوديت زماني همه فرآيندها را ضمانت مي کند.
توانايي VBS [٣] در دسته بندي کردن فرآيندها بر مبناي ارزش آنها مي باشد که فرصت تحمل اجراي فرآيندهاي حساس را فراهم مي کند در حالي که مانع اجراي فرآيندها با اهميت کمتر مي شود.
در شکل ١، يک مثال ساده توانايي الگويتم VBS به روشني شرح داده است [٣] . DMS موجب مي شود فرآيندها با ارزش بالاتر دچار خطا شود در حاليکه فرآيند با ارزش پايين تر به موقع انجام ميشود. برعکس ، در VBS فرآيند با ارزش بالاتر را به موقع زمانبندي ميکند در حاليکه پردازش کم ارزش با تاخير روبرو مي شود.
شکل ١: نتايج خطاي ناپايدار: در هنگام وقوع يک خطا ناپايدار، فرآيند t١
مجددا اجرا مي شود فرآيند کم ارزشتر را در زمان زمانبندي مي کند و اين امر موجب تاخير فرآيند حساس و بحراني مي شود فرآيند پر اهميت را در زمان زمانبندي ميکند در حاليکه فرآيند کم ارزشتر دچار تاخير مي شود . جدول سمت راست پارامترهاي فرآيندها را نشان مي دهد[٣].
٢-١-١ زمانبندي بر مبناي ارزش فرآيند
يکي از اين الگوريتم ها ADM است . اجراي به موقع فرآيندهاي حساس در طول خطاي گذرا با استفاده از الگوريتم زمانبندي (ADM) Adaptive Deadline Monotonic انجام مي شود. اين روش کاربردي براي سيستم هاي تعبيه شده است که به سخت افزار اضافي و هزينه اضافي نياز ندارد[٣] .
ما به هر فرآيند يک تابع ارزش اختصاص مي دهيم تا هزينه نسبي يا سود و فايده در مواجه شدن با محدوديت زماني براي فرآيندهاي منحصر بفرد را بدست آورد. هدف زمانبندي بر مبناي ارزش ماکزيمم اجراي سيستم بوسيله انتخاب فرآيندهاي متکي با بالاترين ارزش است حتي اگر لازم است ، مانع فرآيندهايي با ارزش پايين تر مي شود .
اگر چه بهينگي آن کمتر از DMS است اما تعداد زيادي از فرآيندها در زمان کامل شده و اين روش اجراي به موقع فرآيندهاي مهم را پشتيباني مي کند.
براي هر فرآيند τi، يک تابع ارزش تعريف مي شود بطوريکه bi ماکزيمم فايده فرآيند است اگر سر وقت نباشد . ciماکزيمم هزينه مي باشد اگر تاخير داشته باشيم و li اثر دير کرد براي فرآيندهايي با فرجه ٣ نرم (soft) را نشان مي دهد[٣] . در شکل ٢ محور زمان براي يک فرآيند τi نشان داده شده است ، قبل از فرحه اش ( di)، فرآيند ماکزيمم ارزش را دارد (يعني bi). بعد از عبور فرجه اش ارزش فرآيند شروع به کاهش مي کند که بوسيله li نشان داده شده است و ماکزيمم هزينه ci- است .
٢-١-٢ ارزيابي کارايي الگوريتم هاي ADM و DMS
براي ارزيابي کارايي از يک شبيه سازي استفاده مي کنيم که قدرت ADM براي تحمل اجراي فرآيندهاي بحراني در طول خطا ناپايدار را اندازه گيري مي کند . نتايج شبيه سازي در شکل ٢ نشان داده شده است . همانطور که مشاهده مي کنيد الگوريتم ADM در حضور خطا جواب قابل قبول تري نسبت به DMS ارائه کرده است [٣] .
شکل ٢ :الگوريتم هاي ADM و DMS بدون خطا و در حضور خطا[٣]
٢-٢ زمانبندي ايستا و نيمه ايستا
در اينجا روشي از زمانبندي متحمل خطا براي سيستم هاي تعبيه شده با محدوديتهاي زماني بلادرنگ سخت و نرم را بيان مي کنيم . ما علاقمنديم تا فرجه ها را براي فرآيندهاي سخت حتي در مواقع خطا تضمين کنيم . در حاليکه بهره وري کلي سيستم به حداکثر برسد. ما توابع زمان .کارايي را استفاده مي کنيم تا کارايي (بهره وري) فرآيندهاي نرم را بدست آوريم [٤]. براي تحمل خطا از روش اجراي مجدد فرآيند استفاده شده است .
٢-٢-١ مدل برنامه
برنامه اي به نام A را به عنوان گراف قطبي، چرخه اي،مستقيم الگوبرداري مي کنيم . هر گره يک فرآيند رابيان مي کند[٤] .
در شکل ٣ ما برنامه A را داريم که از نمودار فرآيندها g1 با سه فرآيند p1، p2 و p3 تشکيل مي شود. زمانهاي اجرا براي فرآيندها در جدول شکل ٣ نشان داده شده است . ... هزينه بهبود(بازسازي) مي باشد که زمان مورد نظر براي اجراي مجدد از يک فرآيند در حضور خطا را نشان مي دهد. کل فرآيندهايي که به نمودار فرآيند g تعلق دارند که دوره يکسان T=Tg دارند که دوره تناوب نمودار فرآيند مي باشد. در شکل ٣ نمودار فرآيند g دوره دارد.
٢-٢-٢ مدل (تابع ) بهره وري
فرآيندهاي برنامه A سخت يا نرم هستند. H به مجموعه اي از فرآيندهاي سخت و S به مجموعه اي از فرآيندهاي نرم اشاره مي کند.
در شکل ٣ فرآيندهاي P2 و P3 نرم هستند، درحاليکه فرآيند P1 سخت مي باشد. هر فرآيند سخت به يک Deadline سخت مجزاي هر فرآيند نرم di مربوط بوده است Pi با تابع بهره وري (کارايي) تعيين شده است .
٢-٢-٣ تحمل پذيري در برابر خطا
شناسايي خطا و مکانيزم هاي تحمل پذيري خطا بخشي از معماري نرم افزار هستند.
در اين مقاله از کاربرد اجراي مجدد براي تحمل پذيري در برابر خطا استفاده مي کنيم . همانطور که در شکل ٤ مشاهده مي شود.
فرآيندهاي سخت اگر دچار خطا شوند بايد دوباره اجرا شوند. يک فرآيند نرم تنها زماني اجرا خواهد شد که با فرجه هاي سخت افزاري برخورد نداشته باشد و اجراي مجدد آن براي بهره وري کلي سودمند مي باشد.
٢-٢-٤ زمانبندي ثابت در مقابل نيمه ثابت
در اين قسمت توضيح داده خواهد شد که چطور زمانبندي ثابت براي برنامه A در شکل ٣ کار خواهد کرد. برنامه بايد خطاي ١=K را تحمل کند و هزينه بهبود براي کل فرآيندها مي باشد.
