3-5 نتیجه گیری54
فصل چهارم : الگوریتم پیشنهادی
4-1 مقدمه55
4-2 ذخیره ساز انرژی56
4-2-1 مزایای ابرخازن در برابر باطری با قابلیت شارژ مجدد56
4-2-2 معایب ابرخازن در برابر باطری با قابلیت شارژ مجدد57
4-3 مدل سیستم61
4-3-1 مدل برداشتگر انرژی61
4-3-2 مدل پردازنده61
4-3-3 مدل ذخیره ساز انرژی62
4-3-4 مدل وظیفه63
4-4 الگوریتم زمانبندی بیدرنگ63
4-4-1 انتخاب بازه زمانی65
4-4-2 محاسبه انرژی مورد نیاز برای اجرای وظایف موجود در بازه65
4-4-3 محاسبه موجودیت انرژی66
4-5 نتیجه گیری74
فصل پنجم : شبیه سازی و نتیجه گیری
5-1 مقدمه75
5-2 تنظیمات اولیه75
5-3 مقایسه نرخ خطای سررسید78
5-4 کمترین ظرفیت ذخیره سازی برای داشتن نرخ خطای سررسید صفر85
5-5 سودمندی انرژی87
5-6 نرخ خطای سررسید در حالت عدم وجود واحد ذخیره ساز انرژی89
5-7 : بررسی سربار زمانبندی89
5-8 نتیجه گیری90
5-9 پیشنهادات91
مراجع92
فهرست شکلها
شکل 1-1 : نمودار مشخصات یک وظیفه11
شکل 2-1 : نوع اول سیستم برداشتگر انرژی16
شکل3-1 : منحنی توان در روش LSA26
شکل 3-2 : مدل سیستم روش LM-APM36
شکل 3-3 : شبه کد الگوریتم HA_DVFS قسمت تنظیم بارکاری پردازنده و انتخاب پویای ولتاژ و فرکانس44
شکل 3-4 : زمانبندی دو وظیفه45
شکل 3-5 : شبه کد الگوریتم بهره وری از انرژی سرریز شده46
شکل 4-1 : اتصال دو باطری برای جداسازی فازهای شارژ و دشارژ59
شکل 4-2: مدل سیستم پیشنهادی61
شکل 4-3: محاسبه dl در حالت Edemand = EH(tc , Dmax) + ES(tc)68
شکل 4-4 : شبه کد الگوریتم پیشنهادی73
شکل 5-1 : نمودار توان برداشت PH(t)76

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

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

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

شکل 5-2 : مقایسه نرخ خطای سررسید الگوریتم پیشنهادی با سایر الگوریتم ها79
شکل 5-3 نمودار خطی تغییرات نرخ خطای سررسید الگوریتم ها در مقادیر متفاوت بهره وری80
شکل 5-4 : 4 نمونه گیری از انرژی خورشیدی80
شکل 5-5 : مقایسه نرخ خطای سررسید برای 5000 مجموعه وظیفه81
شکل 5-6 : مقایسه نرخ خطای الگوریتم ها در مقادیر مختلف ظرفیت باطری و بهره وری83
شکل 5-7 : مقایسه نرخ خطای سررسید در حالت ذخیره ساز دوگانه و باطری84
شکل 5-8 : مقایسه نرخ خطای سررسید در مقادیر مختلف ذخیره سازی باطری و ابرخازن85
شکل 5-9 : مقایسه حداقل ظرفیت واحد ذخیره سازی برای داشتن خطای سررسید صفر86
شکل 5-10: نمودار کارایی انرژی در مقادیر مختلف بهره وری88
شکل 5-11 : مقایسه نرخ خطای سررسید در دو حالت صحت و حذف واحد ذخیره ساز انرژی89
فهرست جدولها
جدول 4-1 : مقایسه باطری و ابرخازن58
جدول 4-2 : حالات کاری باطری های شکل4-159

جدول 5-1 : مشخصات پردازنده XScale اینتل76
جدول 5-2: نرخ خطای سررسید الگوریتم HA-DVFS براساس شکل 5-480
جدول 5-3 : محاسبه سربار زمانبندی الگوریتم ها90
چکیده
با رشد و توسعه تکنولوژی در زندگی بشر، نیاز به رشد و توسعه سیستمهای تعبیهشده که بخش عمدهای از سیستمهای دیجیتال را شامل میشوند هم بیشتر میشود.ازجمله مشخصههای اصلی یک سیستم تعبیه شده، بیدرنگ بودن و مصرف انرژی مناسب میباشد بعلاوه اجرای یک برنامه شامل وظایف مختلفی است که هرکدام منابع خاص خود را از سیستم میطلبند حال اگر این منابع در زمان مناسب در اختیار وظایف قرار نگیرد، سیستم نمیتواند بازده و کارایی مناسبی داشته باشد بنابراین وجود یک زمانبند مناسب برای چنین سیستمهایی از اهمیت ویژهای برخوردار است. محدودیت مصرف انرژی در سیستمهای تعبیه شده، بسیار حائز اهمیت است این اهمیت از آنجا ناشی میشود که بسیاری از این سیستمها، مبتنی بر باطری هستند و اغلب مواقع امکان شارژ مجدد باطری وجود ندارد و درصورت اتمام انرژی موجود در باطری، سیستم از کار خواهد افتاد در چنین مواقعی استفاده از برداشتگرهای انرژی میتواند راهکار مناسبی برای غلبه بر محدودیت انرژی سیستم باشد. الگوریتمهای زمانبندی زیادی در زمینه بیدرنگ بودن و بهبود مصرف انرژی ارائه شده است اما هرکدام دارای محدودیتها و نواقصی میباشند در اغلب مطالعات انجام شده از باطری ایده آل بعنوان منبع انرژی که مقدار معین انرژی را در یک ولتاژ خروجی ثابت، ذخیره یا پخش میکند استفاده شده است و از تاثیر ضریب شارژ/دشارژ باطری در میزان انرژی منتقل شده، صرفنظر شده است لیکن این امر همیشه صحیح نیست و طراحی بر مبنای این مدل ساده و حداقل کردن میانگین مصرف انرژی لزوما منجر به بهینه شدن طول عمر باطری نمیشود. در این راستا در این پایان نامه روشی را برای زمانبندی سیستمهای تعبیه شده مبتنی بر برداشت انرژی و باطری غیرایدهآل با هدف بهبود انرژی مصرفی درحین اجرای بیدرنگ وظایف سیستم و کاهش نرخ خطای سررسید مجموعه وظایف، پیشنهاد میدهیم در این روش با انتخاب بازه مناسب برای برداشت انرژی از محیط، به بررسی موجودیت انرژی سیستم و میزان انرژی مورد نیاز برای اجرای بیدرنگ وظایف در آن بازه پرداخته و با توجه به پارامترهای موجود، انرژی مورد نیاز برای اجرای وظیفه و سطح فرکانس مناسب برای پردازنده را اختصاص میدهیم. نتایج حاصل از شبیهسازی نشان میدهد که روش پیشنهادی در مقایسه با روشهای موجود، نرخ خطای سررسید را کمتر میکند همچنین در روش پیشنهادی، تعداد دفعات رجوع به باطری کمتر شده که در نتیجه باعث اتلاف کمتر انرژی حاصل از شارژ/دشارژ باطری و افزایش طول عمر آن و در نهایت افزایش طول عمر سیستم میشود.
کلمات کلیدی : سیستمهای تعبیه شده، برداشتگر انرژی، زمانبندی بیدرنگ، ذخیرهساز انرژی غیرایدهآل
فصل اول
فصل اول: توصیف مسئله
1-1 مقدمه
در سالهای اخیر با رشد و توسعه کامپیوترها در همه جنبههای زندگی بشر و افزایش نیازهای روزمره و گسترش برنامه‌های کاربردی1، نیاز به طراحی و توسعه سیستمهای تعبیهشده2 بیش از پیش مورد توجه قرار گرفته است. سیستم‌های تعبیه‌شده، ابزارهای محاسباتی هستند که درون بخش عظیمی از محصولات و کاربردهای روزمره جاسازی شدهاند. سیستمهای پردازش اطلاعات در تجهیزات ارتباط از راه دور، سیستمهای حمل و نقل، تلفن همراه، اسباب بازی، دوربین و… مثالهایی از سیستم‌های تعبیه‌شده میباشند. این سیستمها به دلیل خاصمنظوره بودن، جایگزین تجاری مناسب و ماندنی برای کامپیوترها و یا ابزارهای همه منظوره نیستند. همانطورکه برنامه‌های کاربردی بصورت تصاعدی پیچیده میشوند با پیچیدگی ابزارهای محاسباتی تعبیه‌شده نیز مواجه می‌شویم. اکثر این سیستمها دارای محدودیتهای زمانی بوده و نیازمند اجرای وظایف3 در بازه زمانی خاص میباشند بنابراین وجود یک زمانبند4 مناسب برای سیستمهای بیدرنگ5 تعبیه شده، امری ضروری است. الگوریتم زمانبندی مناسب، یکی از قسمتهای مهم سیستمهای بیدرنگ میباشد تا بتواند منابع مورد نیاز وظایف را در زمان مناسب در اختیار آنها قرار داده و وظایف بتوانند در زمان مناسب اجرا شوند. علاوه براین، محیطهای کاری این سیستمها، ضرورت استفاده از منبع انرژی مناسب را برای کاربردهای بیدرنگ ایجاب میکند بنابراین در کنار محدودیت زمانی بحث مدیریت انرژی6 و منبع انرژی نیز بسیار حائز اهمیت است. اغلب سیستمهای تعبیه شده، مبتنی بر باطری هستند و طول عمر این سیستمها نیز وابسته به طول عمر باطری میباشد بنابراین در بسیاری از مواقع که منبع انرژی دائمی در دسترس نیست استفاده از منابع تجدیدپذیر انرژی7 میتواند مورد توجه قرار گیرد. بنابراین یکی از راهکارهای موجود پیش پای طراحان سیستمهای تعبیهشده بیدرنگ، استفاده از منابع انرژی محیطی و برداشتگرهای انرژی8 است. این منابع میتوانند شامل انرژی خورشیدی، حرارتی و شیمیایی باشند و یا حتی انرژی جنبشی حاصل از امواج دریا و یا حرکت دست و پای انسان و سایر موجودات زنده نیز میتواند بعنوان منبع انرژی در اختیار سیستمهای تعبیهشده قرار گیرد. در این سیستمها برخلاف سیستمهای مبتنی بر باطری سنتی که سیستم، بعد از اتمام انرژی موجود در باطری، دیگر قادر به ادامه عملیات خود نیست، میتوانند با استفاده از باطری با قابلیت شارژ مجدد9، انرژی را از محیط پیرامون خود دریافت کرده و در باطری و یا سایر ذخیرهسازهای انرژی همچون خازن، ذخیره و در اختیار سیستم قرار دهند. از جمله سیستمهای تعبیهشده بیدرنگ که استفاده از انرژی محیطی میتواند نقش بسیار مهمی در جهت افزایش کارایی این سیستمها داشته باشد عبارتند از : دستگاههای خودپرداز، سیستمهای تعبیهشده موجود در اتوموبیلها (سیستم ضد قفل و دزدگیر و …)، سیستمهای تعبیهشده موجود در اتاق عمل و موارد پزشکی، شبکههای حسگر ، سیستمهای کنترل از راه دور و رباتها خصوصا رباتهای مینیاب و امداد و نجات و … که در همه این موارد اجرای به موقع و صحیح عملیات سیستم بسیار مهم میباشد. بنابراین طول عمر، پیوستگی عملیات و کارایی این سیستمها بسیار حائز اهمیت است که استفاده از تکنیک برداشت انرژی محیطی درجهت بهبود موارد گفته شده میتواند نقش موثری داشته باشد.
امروزه برداشتگرهای انرژی، بسیار مورد توجه قرار گرفتهاند و ازجمله چالشهای موجود در این سیستمها، تکنیکهای مدیریت توان10 خوب در کنار الگوریتمهای زمانبندی مناسب میباشد. در دهه گذشته محققان بدنبال مسئله توان و انرژی و زمانبندی با هدف کاهش توان مصرفی تحت محدودیتهای انرژی بودند اما در بیشتر کارهای انجام شده بدنبال قابلیت شارژ مجدد باطریها نبودند. ایدهی اکثر کارهای پیشین، ذخیره توان، توسط کاهش سرعت پردازنده بود و از دید آنها این مسئله برای تأمین محدودیتهای زمانی سیستم کافی بود. اما امروزه بکار بردن این تکنیکها به تنهایی در سیستمهای مبتنی بر برداشت انرژی، موجب بروز محدودیتهایی در این سیستمها میشود چراکه آنها توان پردازشی را بجای مدیریت پویای توان11، برطبق انرژی موجود و بارکاری12 پردازنده، کمینه میکنند. به عبارتی چالشهای تکنیکی زیادی باید حل شوند تا بتوان به سیستم تعبیهشده کارا رسید. منبع انرژی، ناپایدار است و موجودیت انرژی محیط، از زمانی به زمان دیگر دائما درحال تغییر است بنابراین باید مدلی از برداشت انرژی و توان متناظر بصورت یک متغیر زمانی داشته باشیم تا بتوانیم براساس اطلاعاتی که از موجودیت انرژی در هر لحظه داریم به زمانبندی وظایف بپردازیم. در سیستمهای برداشتگر انرژی، هدف از زمانبندی بیدرنگ این است که وظایف، مادامیکه انرژی در منبع ذخیرهساز موجود است، در سررسید13 متناظرشان اجرا شوند.
در این راستا در این پایان نامه ابتدا به معرفی مدلی برای ذخیرهساز انرژی در سیستم برداشتگر انرژی پرداخته و سپس متناسب با مدل بیان شده، الگوریتمی برای اجرای بیدرنگ وظایف ارائه میدهیم. سیستم تعبیهشده روش پیشنهادی مبتنی بر پردازنده با قابلیت انتخاب پویای ولتاژ و فرکانس14 میباشد و بدین ترتیب، میتوان بهازای هر وظیفه و موجودیت انرژی در محیط و ذخیرهساز انرژی، سطح فرکانس مناسب را برای اجرای وظیفه به پردازنده اختصاص داد و درنهایت از طریق زمانبندی به مدیریت انرژی در سیستمهای بیدرنگ تعبیه شده مبتنی بر برداشت انرژی خواهیم پرداخت.
1-2 ساختار پایان نامه
فصلها در این پایان نامه بدین ترتیب سامان یافتهاند:
در فصل اول به تعریف و بیان مسئله پرداختیم. در فصل دوم بطور کامل به معرفی سیستمهای تعبیهشده و مشخصات آنها میپردازیم. سیستم‌های تعبیهشده (نهفته یا توکار نیز گفته می شوند) سیستم‌هایی کامپیوتری هستند که به عنوان بخشی از یک سیستم بزرگتر که خود شامل اجزای الکترونیکی و یا مکانیکی است، می‌باشند و وظیفه‌ی کنترل عملکرد و پردازش درست سیستم را بر عهده دارند. بر خلاف کامپیوترهای همه منظوره ( به عنوان مثال کامپیوترهای شخصی) که برای رفع نیازهای عمومی طراحی شده‌اند، سیستم‌های نهفته به گونه‌ای طراحی می‌شوند که برای یک کاربرد خاص با کمترین هزینه بهترین کارایی را از خود نشان دهند. امروزه درون اکثر وسایل و دستگاه‌های پیرامون ما (خودپرداز، تلفن‌همراه، اتومبیل و ماشین لباسشویی) سیستم نهفته‌ای قرار دارد. مشخصه‌ی کلیدی این سیستم‌ها، طراحی اختصاصی برای انجام یک کار مشخص است. به این دلیل که سیستم‌های نهفته برای یک کار مشخص اختصاص یافته‌اند، مهندسین طراح می‌توانند محصول را برای کاهش اندازه و قیمت بهینه کرده و اطمینان پذیری و کارایی آن را بالا ببرند. امروزه، انواع باطری، نقش اساسی را در جهت تأمین انرژی سیستمها برعهده دارند. این مسئله باعث بروز مشکلاتی همچون کاهش طول عمر سیستمها و عدم پیوستگی عملیات آنها میشود. که برای غلبه بر این مشکلات راهکاری که معرفی میشود، استفاده از تکنیک برداشت انرژی از محیط با استفاده از برداشتگرهای انرژی است. با استفاده از این روش، انرژی همواره در اختیار سیستم قرار گرفته و مشکلات ناشی از عدم وجود انرژی کافی و سایر مشکلات، مرتفع میشود. سیستمهای تعبیه شدهای که انرژی مورد نیاز خود را از محیط پیرامون تأمین میکنند به سیستمهای تعبیهشده مبتنی بر برداشتگر انرژی15 معروفند. مسائل مهمی که در این نوع از سیستمها مطرح است، بحث زمانبندی وظایف یک برنامه با درنظر گرفتن محدودیت انرژی و محدودیت زمانی خاص وظایف، کارایی ذخیره سازی انرژی و البته کارایی تمام بخشهای یک سیستم تعبیهشده مبتنی بر برداشتگر انرژی و … میباشد. که این مسائل در کنار انواع سیستمهای برداشتگر انرژی و الگوریتمهای اولیه زمانبندی در سیستمهای تعبیهشده همچنین معرفی روشهای مدیریت توان در سیستمهای تعبیهشده بیدرنگ نیز در فصل دوم بیان خواهند شد.
در ادامه در فصل سوم به معرفی کارهای انجام شده در زمینه زمانبندی سیستمهای تعبیهشده بیدرنگ مبتنی بر باطری و همینطور مبتنی بر برداشت انرژی، خواهیم پرداخت و نواقص کارهای انجام شده نیز در این فصل بررسی خواهند شد. بطورکلی منابعی که در زمینه زمانبندی این نوع سیستمها معرفی شدهاند به دو دسته کلی روشهای تحلیلی بر پایه مسائل ریاضی و روابط آن و روشهای مبتنی بر الگوریتم و شبیهسازی و پیادهسازی قابل تقسیماند. در فصل سوم در ابتدا به معرفی چند روش ابتدایی که وظایف را در سیستمهای مبتنی بر باطری و بدون در نظر گرفتن تکنیک برداشت انرژی، زمانبندی میکنند میپردازیم و در ادامه برخی روشهای زمانبندی که مبتنی بر تکنیک برداشت انرژی میباشند را معرفی و بررسی خواهیم کرد. بطور خاص در این بخش از فصل سوم، الگوریتمهایی را که در روش پیشنهادی این گزارش، از آنها استفاده شده است را معرفی و مقایسه میکنیم. لازم به ذکر است که ترتیب معرفی این روشها بدین صورت است که هر الگوریتمی که در ادامه الگوریتم (ها)ی قبلی معرفی شده است، سعی در رفع نواقص روش(ها)ی قبلی دارد و روش پیشنهادی ما نیز که در فصل چهارم آورده شده است در ادامه این روشها میباشد. در انتهای فصل نیز برخی الگوریتمهای زمانبندی دیگر که لزوما نقشی در روش پیشنهادی این گزارش ندارند آورده شده اند.
در فصل چهارم، به معرفی و بیان روش پیشنهادی خواهیم پرداخت. در این فصل روش پیشنهادی در دو بخش ارائه میشود. در بخش اول با توجه به مراجع موجود و روشهایی که در زمینه بهینهسازی ذخیرهساز انرژی و افزایش کارایی آن معرفی شده است، روشی را برای ذخیرهسازی انرژی معرفی میکنیم که در این روش تأثیر ضریب شارژ و دشارژ باطری به حداقل رسیده است و بدین ترتیب کارایی این بخش از سیستم تعبیهشده مبتنی بر برداشتگر انرژی را افزایش میدهیم. در ابتدای بخش اول مزایا و معایب روشهای موجود در این زمینه را نیز بررسی و بیان خواهیم کرد. در ادامه در بخش دوم، الگوریتم زمانبندی مبتنی بر سیستم پیشنهادی معرفی شده در بخش اول را بیان خواهیم کرد. همانطورکه در فصل دوم بیان خواهد شد، یکی از مشخصههای اصلی سیستمهای تعبیهشده، اجرای بیدرنگ وظایف میباشد. در کنار این مسئله بررسی موجودیت انرژی برای اجرای هر وظیفه نیز بسیار حائز اهمیت است از این رو الگوریتم پیشنهادی سعی در اجرای وظایف در زمان مناسب و با مصرف انرژی مناسب میباشد که جزئیات کامل این الگوریتم در فصل چهارم، آورده شده است.
در نهایت در فصل پنجم، نتایج حاصل از شبیهسازی روش پیشنهادی بیان خواهد شد. در این فصل به مقایسه الگوریتم پیشنهادی با برخی الگوریتمهای دیگر از دید مصرف انرژی، تأمین سررسید وظایف و برخی پارامترهای دیگر خواهیم پرداخت و با نتیجهگیری و معرفی برخی کارهای آتی، به گزارش پیشرو پایان خواهیم داد.
فصل دوم
فصل دوم : مفاهیم اولیه
2-1 مقدمه
در این فصل به معرفی سیستم تعبیهشده و نیازمندی آن، همینطور تکنیک برداشت انرژی از محیط و لزوم استفاده از آن میپردازیم. در یک سیستم تعبیه شده بیدرنگ مبتنی بر برداشت انرژی علاوه بر اجرای وظایف در سررسید متناظرشان با توجه به محدودیتهای زمانی تعریف شده، بحث مدیریت توان و انرژی نیز بسیار حائز اهمیت است. بنابراین در این فصل قبل از معرفی الگوریتمها و روشهای موجود، مفاهیم اولیه در این سیستمها را بررسی خواهیم کرد.
2-2 سیستمهای تعبیهشده
امروزه کاربردهای فراوان سیستمهای دیجیتال، برکسی پوشیده نیست. لیکن بسیاری از مردم تنها کامپیوتر شخصی خود را به عنوان یک سیستم کامپیوتری میشناسند. حال آنکه روزانه با دهها سیستم مبتنی بر پردازنده، برخورد و تعامل دارند. مایکروفرها، اتومبیلها (حتی اجزای درون اتومبیل مثل سیستم ضدقفل و …)، دستگاههای کنترل از راه دور، تلفن همراه، آسانسورها و حتی ماوس و صفحه کلید یک کامپیوتر رومیزی نیز در ردهی سیستمهای مبتنی بر پردازنده قرار میگیرند. برخلاف کامپیوترهای همهمنظوره که برای رفع نیازهای عمومی طراحی شده‌اند، سیستم‌های نهفته به گونه‌ای طراحی می‌شوند که برای یک کاربرد خاص با کمترین هزینه بهترین کارایی را از خود نشان دهند. این سیستمها داری هسته پردازشی شامل میکروکنترلر، ریزپردازنده و یا پردازنده سیگنالهای دیجیتال میباشند این هسته پردازشی بعنوان یک واحد مهم در سخت‌افزار یک سیستم تعبیهشده ایفای نقش میکند]1[ .
سیستمهای تعبیه‌شده برای اهداف خاص طراحی می‌شوند و اغلب توسط ابزارهای دیگر(نه لزوما کامپیوترها) و پروسههای خاصی کنترل می‌شوند. برخی از این سیستم‌ها نیازمندی‌های خاصی نظیر حمایت از پردازش‌های بیدرنگ دارند. معمولا برنامه‌های کاربردی یک سیستم تعبیه شده را روی یک کامپیوتر رومیزی، طراحی و در نهایت روی سخت افزار و سیستمعامل تعبیهشده خاص خود، پیاده سازی میکنند که در طراحی این برنامه‌ها باید مشخصههای خاص و عام سیستم تعبیهشده در نظر گرفته شود.
مشخصههای یک سیستم تعبیه شده عبارتند از ]1[ :
هزینه کم : باتوجه به فراوانی سیستمهای تعبیهشده در زندگی بشر، طراحان باید بتوانند سیستمهای تعبیهشدهای با حداقل قیمت و بالاترین کارایی طراحی کنند. بنابراین منابع موجود برای طراحان محدود است.
توان پایین16 : یک فاکتور بحرانی در طراحی چنین سیستمهایی پایین بودن توان مصرفی آنهاست چراکه این سیستمها اکثرا با باطری کار کرده و انتظار میرود که در یک دوره زمانی طولانی فعال باقی بمانند بعنوان مثال حسگرها، تلفن‌های همراه و PDA17 ها. بعلاوه اندازه یک سیستم تعبیه شده نیز یک عامل محدود کننده در استفاده از ابزارهای خنک کننده در سیستم است بنابراین خاصیت کم‌توان بودن یک سیستم تعبیه شده یک مشخصه اساسی است.
قابلیت پیش‌بینی پذیری18 : بدلیل اینکه تعداد زیادی از برنامه‌های کاربردی بیدرنگ، توسط سیستم‌های تعبیه‌شده اجرا می‌شوند، پیش بینی رفتار این سیستمها بسیار مهم است. این بدین معنی است که رفتار این سیستمها، تحت هر شرایطی باید قابل پیشبینی باشد. این سیستمها شامل سخت افزاری هستند که تضمین میکند هر زیربرنامه‌ای که روی آنها اجرا می‌شود، در هر زمان اجرا، سربار19 اجرای یکسانی داشته باشد. علاوه براین، نرم افزارهای موجود با در نظر گرفتن بدترین شرایط ممکن طراحی می‌شوند و به این طریق است که سربار زمانی سیستم را می‌توان بصورت قطعی درنظر گرفت. بنابراین قابلیت پیش بینی در سیستم‌های تعبیه‌شده، ممکن و قابل اجراست.
قابلیت اعتماد20 : بسیاری از سیستم‌های تعبیه‌شده، بحرانی امن21 هستند بنابراین باید در سطح قابل قبولی از اعتماد پذیری قرار داشته باشند. تجهیزات انرژی هسته‌ای یک نمونه از سیستم‌های به شدت بحرانی امن هستند که بخش‌های بحرانی آن باید بطور کامل توسط نرم افزار، کنترل شوند. قابلیت اعتماد در سایر سیستمها مثل خودرو، قطار، هواپیما و… هم بسیار مهم است. ویژگی قابلیت اعتماد، جنبههای زیر از یک سیستم را دربرمیگیرد :
قابلیت اطمینان22که یک سیستم خراب نشود و در صورت خرابی بتوان قسمت خراب شده را در مدت زمان مشخص و مناسبی ترمیم کرد (نگهداشت پذیری23 ). همچنین در دسترس بودن و قابلیت استفاده24 ، ایمنی که هیچ خرابی در سیستم، سبب آسیب و صدمه به کل سیستم یا کاربر آن، نشود. و درنهایت امنیت25که محرمانگی دادههای حساس در سیستم حفظ شود.
کارایی26 : سیستمهای تعبیهشده باید از لحاظ انرژی مصرفی، اندازه برنامه، زمان اجرا و هزینه، کارا باشند که از این میان کارایی در میزان انرژی مصرفی از اهمیت بسیار بالایی برخوردار است
خاص منظوره بودن : همانطور که گفته شد برخلاف سیستمهای رومیزی همه منظوره، یک سیتم تعبیه شده باید برای هدف خاصی طراحی شده باشد. بعنوان مثال پردازندههای کنترل ماشین و یا قطار، نرم افزار و برنامههای خاص آن را راه اندازی و اجرا میکنند نه نرم افزار پردازنده یک کامپیوتر یا دوربین و … را.
2-3 سیستم بیدرنگ
اجرای بیدرنگ وظایف و عملیات سیستم،علاوه بر ویژگیهای ذکر شده، مسئله مهمی است که در برخی سیستمهای تعبیهشده همچون سیستمهای پزشکی، ارتباطات چندرسانهای، رادارهای فضایی و… از اهمیت ویژهای برخوردار است. یک سیستم بیدرنگ، سیستمی است که هم شامل صحت منطقی خروجیها است و هم زمان پاسخ مناسب سیستم را دربر میگیرد وباید علاوه بر ارضای محدودیتهای زمانی، نتایج و پیامدهای سخت حاصل از ریسک، مثل خرابی و ازدست رفتن وظیفه را کنترل کند. طبق تعریف Donald Gillies ” صحت محاسبات، در یک سیستم بیدرنگ، نه فقط وابسته به صحت و درستی منطقی محاسبات است بلکه همچنان وابسته به زمان نتایج حاصله میباشد و اگر محدودیتهای زمانی در نظر گرفته نشود خطای سیستمی رخ میدهد.”
بطورکلی سیستمهای بیدرنگ، پاسخی برای یکسری از ورودیهای خارجی هستند که بصورت غیرقابل پیشبینی وارد سیستم میشوند سپس این ورودیها توسط سیستم بیدرنگ پردازش شده و تصمیمات مناسب در زمان مناسب اتخاذ میشوند همچنین خروجی لازم برای کنترل دستگاههای جانبی متصل به آنها نیز تولید میشود و در صورتیکه سرویسها و منابع خواسته شده توسط وظیفه، قبل از اتمام آن، در اختیارش قرار نگیرد و وظیفه نتواند در زمان مناسب و تعیین شده خاتمه یابد، وظیفه مورد نظر از اعتبار ساقط و خراب میشود بر این اساس سیستمهای بیدرنگ، از لحاظ محدودیت زمانی به 3 دسته تقسیم میشوند ]2[ :
بیدرنگ سخت27: در این سیستم، پاسخ دیرهنگام، ناصحیح بوده و منجر به خطای سیستمی میشود و تمامی وظایف باید در سررسید خود اجرا شده در غیر اینصورت منجر به ایجاد یک فاجعه میشود. بعنوان مثال در یک نیروگاه هستهای تأخیر در وظیفهای که مسئول خنک کردن راکتور میباشد می تواند منجر به وقوع فاجعه شود.
بیدرنگ نرم28: اجباری در بررسی تمامی محدودیتهای زمانی سیستم نیست و در صورت تأخیر در اجرای وظیفه، سیستم دچار بحران و یا وقوع فاجعه نمیشود گرچه تکرار تأخیر، میتواند منجر به خطای سیستمی شود. برنامه‌های چندرسانه‌ای مثالی از این سیستمهاست.
بیدرنگ ثابت29: این سیستم، سررسیدهای سختی دارد اما در جاییکه یک احتمال کم و مشخص از خطا و نقض سررسید وجود دارد، سیستم میتواند این خطا را تحمل کند بعبارتی سررسیدها هم به صورت سخت و هم به صورت نرم هستند. یعنی درعین حال که اجرا نشدن وظیفه در سررسیدش باعث بیاعتبار شدن آن وظیفه میشود (مثل بیدرنگ سخت) اما گاهی سیستم میتواند سررسید را نادیده بگیرد (مثل وقفه‌های نرم).
2-4 زمانبندی وظایف
در کنار مشخصههای سیستمهای تعبیهشده بحث زمانبندی و ترتیب اجرای وظایف بسیار حائز اهمیت است. وظایف زیادی در اجرای یک برنامه وجود دارد که هر کدام متقاضی منابع خاص خود از سیستم میباشند منابعی همچون پردازنده، حافظه، وسایل ورودی/خروجی و… . علاوه بر اینها هریک از وظایف، دارای محدودیتهای زمانی خاص خود نیز میباشند محدودیتهایی که باعث الزام اجرای وظیفه در یک بازه زمانی خاص میشود حال اگر منابع مورد نیازسیستم در زمان مناسب در اختیار وظیفه قرار نگیرد سیستم نمیتواند بازده و کارایی مناسبی داشته باشد در این میان دو بحث زمانبندی و تخصیص30 مطرح میشود. زمانبندی یعنی تخصیص پردازنده به وظایف و تخصیص یعنی اختصاص دادن سایر منابع به وظایف.
بحث زمانبندی یک مسئله کاملا کلی و عمومی است و باید با توجه به نواحی مختلفی که مطرح میشود بطور خاص مورد بررسی قرار گیرد بعنوان مثال، وظایف در صنعت، عملیات ساخت و تولید و واحدهای پردازشی، ماشینها هستند و در حمل و نقل، ممکن است عملیات پرواز و واحدهای پردازشی، هواپیماها باشند. بسته به محیط اجرایی، وظایف انواع و دسته بندیهای مختلفی دارند. وظایف میتوانند بصورت دوره ای تکرار شوند و یا رخدادگرا باشند به این معنی که درصورتیکه وقفه خاصی فعال شود و یا وظیفه دیگری که وابسته به وظیفه جاری است، اجرا و خاتمه یابد و یا سایر رخدادهای سیتمی، در این صورت، وظیفه مورد نظر، فعال شده و باید اجرا شود. دورهی وظایف دورهای هم میتواند ثابت باشد و یا بصورت پویا رخ دهد ]3[.
2-4-1 انواع زمانبندی
الگوریتمهای زمانبندی را از دیدگاههای مختلفی به چند دسته تقسیم میکنند]4[ :
زمانبندی ایستا31 : در این نوع زمانبندی، تصمیمات در مورد زمان شروع و خاتمه وظیفه قبل از شروع به کار سیستم، کاملا مشخص بوده و زمانبندی با مرتبه ثابت صورت میگیرد در این نوع زمانبندی اولویتها ثابت و سربار پردازنده بسیار کم است ]4[.
زمانبندی پویا32 : در این نوع زمانبندی، هیچ پیشبینی از بارکاری33 آتی سیستم نداریم و تصمیمات در زمان ورود وظیفه به صف آماده34 و عموما براساس اولویت هر وظیفه، گرفته میشود همچنین میتواند خود را با متغیرهای پویا در تقاضای کاربر و موجودیت منابع، سازگار کند بعبارتی زمانیکه تقاضای کاربر همچنین موجودیت منابع از قبل مشخص نیست از این زمانبندی استفاده میشود]5[.
زمانبندی انحصاری35 : در این نوع زمانبندی، پردازنده در اختیار و انحصار وظیفه با بالاترین اولویت قرار میگیرد و اگر درحین اجرای یک وظیفه، وظیفهای با اولویت بالاتر وارد لیست آماده شد، پردازنده از وظیفهی در حال اجرا گرفته شده و به وظیفه با اولویت بالاتر اختصاص مییابد(بعبارتی وظیفه با بالاترین اولویت، پردازنده را به انحصار خود درمیآورد.) در اینحالت اجرای وظیفه با بالاترین اولویت قطعی است و بدین ترتیب زمان پاسخ وظیفه کاهش مییابد بعد از اتمام وظیفه جدید هم، پردازنده لزوما به وظیفه معلق شده باز نمیگردد. اکثر سیستمهای بیدرنگ، انحصاری هستند چراکه واکنشپذیری در سیستمهای انحصاری بسیار مهم است.
زمانبندی غیرانحصاری36 : عکس سیستمهای انحصاری است و هر وظیفه در بازهای از زمان، پردازنده را در اختیار میگیرد و انحصار فقط در مورد وظیفه با اولویت بالا نیست ]6[.
2-5 تعاریف اولیه
در این بخش به بیان پارامترهای اولیه در زمانبندی سیستمهای بیدرنگ میپردازیم، این پارامترها، مهمترین و عمومیترین پارامترها در الگوریتمهای زمانبندی هستند]7[.
فرض میشود، مجموعه وظایف ما شامل M وظیفه میباشد که بصورت M = {τ1 , τ2 ,… τM} نشان داده میشود هر وظیفه mτ دارای مشخصههای زیر میباشد :
a : زمان ورود وظیفه به صف آماده و از این زمان به بعد وظیفه میتواند توسط پردازنده، پردازش و اجرا شود.
d : سررسید متناظر وظیفه بعبارتی بیشترین تأخیر قابل قبول برای پردازش و اجرای وظیفه.
D : سررسید مطلق وظیفه که از جمع زمان ورود و سررسید متناظر وظیفه حاصل میشود. توجه شود که سررسید مطلق، زمانی است که بعد از آن اجرای وظیفه فاقد اعتبار خواهد بود اما منظور از سررسید متناظر، فاصله زمانی است که واحد پردازش، در این فاصله قادر به اجرای وظیفه جاری خواهد بود. در شکل 1-1، هردو سررسید نشان داده شدهاست.
T : تناوب وظیفه در وظایف تناوبی (بعد از گذشت T واحد زمانی، وظیفه مجددا وارد لیست آماده میشود.) در تکرارهای آتی وظایف تناوبی، تمامی پارامترها بجز زمان ورود و سررسید مطلق ثابت هستند که بصورت زیر محاسبه میشوند:
ai,j = ϕi + (j-1)Ti (1)
Di,j = ϕi + (j-1)Ti + di (2)
که ai,j و Di,j، به ترتیبj امین زمان ورود و j امین سررسید مطلق وظیفه iτ درj امین تکرار آن میباشد همچنین ϕi، فاز وظیفه iτ میباشد و برابر با اولین زمان ورود وظیفه به سیستم خواهد بود. i,jτ نیز، j امین تکرار وظیفه iτ میباشد.

شکل 1-1 : نمودار مشخصات یک وظیفه
P : اولویت اجرای هر وظیفه میباشد که عموما برای سیستمهای بیدرنگ که بحث زمان و اجرا در زمان خاص بسیار حائز اهمیت است، سررسید متناظر هر وظیفه بعنوان اولویت آن درنظر گرفته میشود و در زمان اجرا وظیفهای که کمترین سررسید را داشتهباشد اولویت بیشتری برای اجرا خواهد داشت.
WCET : بدترین حالت زمان اجرای وظیفه37.
WCEC : بیشترین انرژی مورد نیاز برای اجرای وظیفه38.
همواره داریم :
0 ≤ WCET ≤ d ≤ T (3)
دقت شود که پارامترهای WCET و WCECلزوما متناسب با یکدیگر نیستند و وظیفهای که بیشترین زمان اجرا را دارد لزوما بیشترین انرژی مصرفی را ندارد.
2-6 الگوریتمهای زمانبندی اولیه
تحقیقات گستردهای روی زمانبندی وظایف درکاربردهای بیدرنگ با محدودیتهای زمانی انجام شده است که در ادامه به اختصار به معرفی دو الگوریتم اولیه میپردازیم.
2-6-1 الگوریتم زمانبندی نزدیکترین سررسید اول (EDF)39
این الگوریتم معروفترین الگوریتم زمانبندی بیدرنگ میباشد که برای سیستمهای تعبیه شدهی تک پردازندهای با هدف اجرای بیدرنگ وظایف طراحی شد. با وجود اینکه الگوریتمی بهینه میباشد اما برای اجرا در سیستمهای چند هستهای مناسب و بهینه نیست.( طراحان در سالهای بعد از ارائه نسخه تک پردازنده الگوریتم EDF ، نسخههای متناسب با سیستمهای چند پردازندهای هم ارائه دادند که همچنان بحث درمورد بهینه بودن آنها مطرح است.) این روش بطور کلی از توان محاسباتی پردازنده استفاده کرده و زمانبندی را بصورت پویا و درصورت فعال شدن هر وظیفه در زمان اجرا انجام میدهد فرض اولیه برای EDF اینست که در هر نقطه از زمان، اولویت یک وظیفه فعال شده ثابت نیست و به زمان بستگی دارد و در زمان فعال شدن وظیفه بعدی ممکن است تغییر یابد، اولویت، طبق سیاست EDF بدین گونه تعریف میشود که وظیفه درحال اجرا باید کمترین زمان باقی مانده تا درخواست بعدی را از بین تمامی وظایف فعال شده (وظایف موجود در صف آماده) داشته باشد به عبارتی اولویت اجرا با وظیفهای است که نزدیکترین سررسید را داشته باشد و وظیفهای که بیشترین اولویت (کمترین سررسید) را دارا میباشد زودتر اجرا میشود. علاوه بر این طراحان به بحث قابل زمانبندی40 بودن یک مجموعه وظیفه نیز پرداخته و از دید آنان یک مجموعه، شامل N وظیفه با مشخصههای Ci (زمان اجرای هر وظیفه) و Ti (تناوب هر وظیفه) تنها در صورت شرط زیر قابل زمانبندی است]6[.
∑_”i=1″ ^”N” ▒”Ci ” /”Ti ” ” ≤ 1″ (4)
قابل اثبات است که الگوریتم “نزدیکترین سررسید اول” نسبت به این شرط، امکان پذیر و بهینه است اما در عین حال این روش نیازمند به انحصار در آوردن یک وظیفه قبل از اتمام آن است و این باعث افزایش سربار زمان اجرا بدلیل عملیات سوئیچ پردازنده از یک وظیفه به وظیفه با اولویت بالاتر و تأثیرات منفی اجرای وظایف در لایههای حافظه نهان میشود.
بطور کلی مشخصه های اصلی الگوریتم “نزدیکترین سررسید اول” عبارتند از :
بهینه بودن
پیاده سازی و اجرای ساده
ساده بودن شرط قابل زمانبندی
برای تعداد پردازنده بیشتر از 1 بهینه نیست.
با وجود تمام ویژگیهاییکه این الگوریتم دارد اما فقط از دید محدودیت زمانی و زمان اجرا بدان پرداخته شده است و سایر پارامترهای مهم همچون محدودیت انرژی و توان مصرفی وظایف و پردازنده حین اجرا اشاره ای نشده است اما در کل با توجه به بهینه بودن زمانی این الگوریتم، اساس بسیاری از الگوریتمها میباشد.
2-6-2 الگوریتم زمانبندی نرخ یکنواخت (RMS)41
الگوریتم زمانبندی نرخ یکنواخت، الگوریتمی اولویت دار و ایستا است. که اولویتها را براساس پریود زمانی طوریکه وظیفه با کوتاهترین دوره تناوب و یا بالاترین نرخ اجرا، بالاترین اولویت را به خود اختصاص میدهد. Liu , Layland نشان دادند که درصورتیکه تخصیص اولویت RMS امکانپذیر نباشد، در اینصورت مجموعهای از وظایف قابل زمانبندی نیستند.
فرضیات اولیهای که مطرح میشود عبارتند از :
تمامی وظایف بصورت دوره ای تکرار میشوند.
همزمانی، اشتراک منابع و مبادله و تغییر داده در وظایف وجود ندارد.
پردازنده همواره وظیفه با بالاترین اولویت را اجرا میکند.
طبق این الگوریتم تمامی وظایف با مشخصه بیدرنگ سخت در صورتیکه شرط زیر برقرار باشد همواره در سررسید متناظرشان اجرا میشوند :
∑_”i=1″ ^”N” ▒”Ei ” /”Ti ” ” ≤ n (” “2” ^(“1″ /”n” ) “-1 )” (5)
Ei : بیشترین زمان اجرای i امین وظیفه
Ti : دوره تناوب اجرای i امین وظیفه
n : تعداد وظایف
بعبارتی (Ei )/(Ti ) کسری از زمان مورد نیاز پردازنده برای اجرای i امین وظیفه است. زمانیکهn→∞ مقدار n (2^(1/n)-1 )~ 0.693 و این بدان معنی است که برای اینکه تمامی وظایف بیدرنگ سخت در زمان مناسب، اجرا شوند، پردازنده باید 70% زمان خود را صرف چنین وظایفی کند و این درحالی است که پردازنده، قادر به اختصاص 100% زمان خود به وظایف بیدرنگ نرم میباشد بنابراین این ویژگی مطلوبی نیست چراکه در اینصورت زمانی برای تغییر کدها و مشخصههای اضافه شده نداریم طبق یک حساب سرانگشتی باید سیستمی طراحی کرد که کمتر از 60% تا 70% از زمان پردازنده به اجرای وظایف اختصاص یابد علاوه بر مشکلات گفته شده در صورتیکه وظیفه با بالاترین نرخ اجرا، بالاترین اولویت را داشته باشد ممکن است وظیفهای که خیلی مهم نیست و درعین حال زیاد اجرا میشود بالاترین اولویت را بگیرد و این باعث وقوع قحطی در وظایف مهمتر با نرخ اجرای کمتر میشود ]6[.

دسته بندی : پایان نامه ارشد

پاسخ دهید