جستجوی مقالات فارسی – زمانبندی وظایف در سیستم های تعبیه شده بی درنگ برداشتگر انرژی با …

نتایج الگوریتم انتخاب فرکانس باتوجه به وضعیت سیستم
در این الگوریتم، باتوجه به موجودیت انرژی باطری و انرژی محیطی و همینطور بررسی وضعیت بهرهوری مجموعه وظایف، در مورد فرکانس اجرایی پردازنده تصمیمگیری میشود و درصورت عدم انرژی کافی، وظیفه جاری، حذف خواهد شد با این تفاصیر معایب الگوریتم نامبرده عبارتند از :
این روش از یک الگوریتم مجزا برای محاسبه حد آستانه بهرهوری وظایف تناوبی استفاده میکند. بدینصورت که ابتدا این وظایف توسط الگوریتم دلخواهی زمانبندی میشوند و از نتایج بدست آمده برای محاسبه کران پایین حدآستانه بهرهوری استفاده میشود. قابل ذکر است که از تأثیر زمان اجرای این الگوریتم در الگوریتم کلی چشمپوشی شده است.
درصورتیکه در بازهای از زمان یک و یا تعداد بیشتری وظایف غیرتناوبی وارد سیستم شوند، در ابتدا الگوریتم برای محاسبه حدآستانه بهرهوری، مقدار U_th,L را صفر درنظر میگیرد. بعد از محاسبه بهرهوری کل وظایف موجود در آن بازه، واضح است که مقدار بهرهوری محاسبه شده بیشتر از مقدار آستانه خواهد بود در نتیجه الگوریتم فرض را بر حالت سربار گذاشته و انرژی بیشتری در فرکانس بالاتری برای اجرای وظیفه غیرتناوبی، اختصاص میدهد و این مسئله میتواند سبب افزایش انرژی مصرفی سیستم تعبیهشده شود. بعبارتی الگوریتم، عملا از تأثیر انرژی درخواستی وظایف غیرتناوبی چشمپوشی کرده است که میتواند در برخی مواقع کارایی انرژی سیستم را کاهش دهد.
ایراد مهمی که به الگوریتم وارد است این است که، الگوریتم در صورت عدم وجود انرژی کافی برای اجرای وظیفه بلافاصله وظیفه جاری را حذف میکند درصورتیکه به احتمال زیاد، بتوان با دادن یک زمان تأخیر در اجرای آن، انرژی کافی را از محیط برداشت کرد.
الگوریتم احتمال وقوع سرریز را در بازه زمانی بررسی میکند نه در زمان اجرای یک وظیفه. حالتی قابل تصور است که انرژی محیطی برای اجرای وظیفه جاری، کافی باشد اما در ادامه بازه با افزایش انرژی محیطی مواجه باشیم در اینصورت الگوریتم، وقوع سرریز را تشخیص داده و وظیفه جاری را با فرکانس بالاتری اجرا میکند که این مسئله علاوه بر افزایش انرژی مصرفی میتواند، سبب کاهش انرژی موجود برای سایر وظایف شود.
در این الگوریتم سخنی از تأثیر ضریب شارژ و دشارژ باطری بیان نشده است و فقط محدود بودن ظرفیت باطری مد نظر نویسندگان قرار است.
اما در مجموع الگوریتم معرفی شده با بررسی همزمان محدودیتهای زمانی و انرژی توانسته پیچیدگی محاسباتی را برخلاف روشهای قبلی کاهش دهد و بتواند از دید کاهش نرخ خطای سررسید و ظرفیت ذخیرهساز انرژی، به نتایجی مشابه با الگوریتم HA-DVFS، در کنار مرتبه زمانی کمتر الگوریتم کمتر، نائل شود. در این مقاله بیان میشود که مرتبه زمانی اجرای الگوریتم از مرتبه O(MN) میباشد البته همانطورکه بیان شد از مرتبه زمانی الگوریتم اولیه برای محاسبه کران پایین آستانه بهرهوری درمورد وظایف تناوبی چشمپوشی شده است. این درحالی است که مرتبه زمانی الگوریتم HA-DVFS، از مرتبه O(M²N) میباشد.
در کنار منابعی که در بخشهای قبلی با جزئیات کامل، بیان کردیم برخی منابع دیگری نیز وجود دارند که در زمینه زمانبندی سیستمهای تعبیهشده بیدرنگ مبتنی بر برداشتگر انرژی ارائه شدهاند. که در این گزارش، مجال برای بررسی کامل آنها وجود ندارد و به شرح مختصری از آنها بسنده میکنیم.
در ]22[نویسندگان یک روش تست و بررسی برای قابل اجرا بودن زمانبندی EDF و اولویت ثابت، با درنظر گرفتن محدودیت انرژی، ارائه دادهاند. نسخه اولیه الگوریتم EDF تنها به مسئله زمان اجرای وظایف و اجرای به موقع آنها توجه داشت درحالیکه در این مقاله بحث انرژی مصرفی و محدودیت انرژی هر وظیفه نیز بدان اضافه شده است. در این مقاله نیز نویسندگان، سررسید متناظر هر وظیفه را بعنوان اولویت ثابت آن وظیفه برای اجرا درنظر گرفتهاند. همچنین درحین اجرا، با بررسی ظرفیت باطری درمورد دریافت انرژی از باطری و یا دریافت انرژی از باطری با قابلیت شارژ مجدد تصمیمگیری میشود.
در ]23[ الگوریتم زمانبندی بیدرنگ مبتنی بر روش EDF ، با نام ^[81]Edeg، برای سیستمهای تک پردازنده ارائه شده است که محدودیتهای انرژی و زمانی را بصورت همزمان برای رسیدن به کارایی سیستم، بررسی میکند. براساس یک برنامه واقعی^[82]، توان آنی مصرف شده توسط وظایف، میتواند تحت تأثیر مدارات و منابع مورد نیاز هریک از وظایف، متغیر باشد در نتیجه متغیرهای بدترین حالت مصرف انرژی و بدترین حالت زمان اجرا برای هر وظیفه از یکدیگر مستقل میباشند. در روشی که در این مقاله ارائه شده است هر وظیفه دارای دو مشخصه مجزای WCET و WCEC می باشد. بنابراین Edeg، براساس دو مفهوم کلیدی زمان و انرژی عمل میکند. ایده اصلی این روش این است که پردازنده مادامیکه انرژی به اندازه تمامی وظایف آتی در ذخیرهساز انرژی موجود است، وظایف را در یک فرکانس ثابت، اجرا میکند در غیر اینصروت به حالت بیکار برای برداشت و ذخیره انرژی میرود. ایرادی که به این روش وارد است این است که ظرفیت ذخیرهساز انرژی در این روش باید بسیار بالا باشد تا پردازنده قادر به اجرای وظایف در سررسید متناظرشان باشد.
شمار زیادی از سیستمهای تعبیهشده بیدرنگ دارای مجموعهای از برنامهها میباشند که در قالب یک فریم اجرا میشوند بعد از اجرای تمامی این برنامهها،کل فریم مجددا تکرار میشود به چنین سیستمهایی سیستمهای مبتنی بر فریم^[83] گویند. مقال

ه ]24[ بحث زمانبندی برای سیستمهای تعبیهشده مبتنی بر فریم را بیان کرده است که قادر به اجرای وظایف بیدرنگ سخت در سررسید متناظرشان میباشد. در این روش، زمانی پردازنده عملیاتش را شروع میکند که واحد ذخیرهساز انرژی کاملا شارژ شده باشد. دراین مورد دوره تناوب تمامی وظایف، یکسان و سررسید هریک از آنها نیز برابر با مقدار دوره تناوب در نظر گرفته شده است. درنتیجه بیان میشود که ترتیب اجرای وظایف درون یک فریم، چه در حالتیکه وظایف قابل زمانبندی باشند و یا قابل زمانبندی نباشند، بسیار بحرانی و حائز اهمیت نیست. بعلاوه فرض میشود توان برداشت انرژی، ثابت بوده و وظایف در یک نرخ ثابتی از انرژی و توان اجرا میشوند. ایده اصلی این روش اضافه کردن یک زمان بیکاری کوچک به سیستم برای برداشت انرژی و شارژ باطری و در مقابل داشتن حداقل زمان زمانبندی است یعنی وظایفی که همگی دارای مشخصههای انرژی و سررسید یکسانی هستند با وجود انرژی کافی در ذخیرهساز انرژی قادر خواهند بود در کمترین زمان قبل از سررسیدشان اجرا شوند. واضح است که یکسان درنظر گرفتن مشخصههای وظایف و همینطور نرخ ثابت انرژی و توان در دنیای واقعی فرض مناسبی نیست.
زمانبندی وظایف تناوبی میتواند براساس اولویت ثابت^[84] و ایستا و یا همانند روش EDF، بصورت پویا، انجام پذیرد. در ]25[ روشی برای زمانبندی وظایف انحصاری با اولویت ثابت که این اولویت در زمان اجرا به هر وظیفه اختصاص داده میشود ارائه شده است (EHFP₄^[85]) . این روش، الگوریتمی برخط است که تصمیمات زمانبندی، بدون هیچگونه پیشبینی از موجودیت انرژی در زمانهای آتی و در زمان اجرا ، گرفته میشود. براساس چهار حالت الگوریتم ابتکاری بیان شده است :
هر زمان که باطری خالی میباشد بعبارتی E(t)=E_min، پردازنده برای یک مدت زمان دلخواهی به حالت بیکار میرود.
بصورت پویا سطح انرژی ذخیره شده در باطری دائما بررسی میشود. هدف از این قسمت کاهش احتمال جایگزینی باطری میباشد.
در این قسمت بیان میشود هرچه ظرفیت باطری بیشتر باشد برای سیستم مناسبتر میباشد در اینحالت بحث محاسبه بیشترین زمانیکه سیستم در صورت عدم انرژی کافی باید متوقف شود در حالتیکه خطای سررسید رخ ندهد بسیار حائز اهمیت است که این زمان آرامش بصورت برخط توسط زمانبند در زمان اجرا تعیین میشود.
در این قسمت الگوریتم به بررسی سرریز در زمان بیکار بودن سیستم میپردازد بنابراین پردازنده، تنها زمانی به حالت بیکار میرود که زمان آرامش و سطح انرژی باطری، بیشینه نباشد. بر این اساس برای موجودیت انرژی باطری یک حد آستانهای درنظر گرفته میشود و زمانیکه سطح انرژی باطری به این مقدار آستانه رسید، پردازنده به حالت بیکار خود میرود.
در آخر بیان میشود که توسط زمانبندی تنها بصورت برخط و با تصمیمات در زمان اجرا و بدون داشتن هیچگونه پیشبینی از برداشت انرژی در آینده، نمیتوان به الگوریتم زمانبندی بهینهای رسید.
الگوریتم زمانبندی که در ]26[ معرفی شده است، برروی یک پردازنده با یک سطح ولتاژ و فرکانس و یک سیستم برداشتگر انرژی و همینطور باطری ایدهآل با قابلیت شارژ مجدد، وظایفی را که مشخصاتی همچون زمان ورود، سررسید متناظر، بدترین حالت زمان اجرا و بدترین حالت انرژی مصرفی را دارند را زمانبندی میکند. در این مقاله بیان میشود که لزوما مشخصههای زمان اجرا و انرژی مصرفی وظایف با یکدیگر متناسب نیستند. همچنین فرض شده است که توان مصرفی آنی یک وظیفه از توان ورودی واحد برداشتگر انرژی، کمتر نیست بعبارتی وظایف میتوانند سبب تهی شدن کامل باطری شوند. در این روش، تضمین اینکه تمامی سررسیدها در یک سیستم برداشتگر انرژی، برآورده شوند، یکی از مهمترین مسائل پیش رو است. الگوریتم ED-H، قبل از اجرای وظیفه جاری، به بررسی موجودیت انرژی برای وظایفی که در آینده وارد سیستم میشوند، میپردازد و درصورت کافی بودن این انرژی، وظیفه جاری اجرا و درغیر اینصورت تا زمان برداشت انرژی کافی از محیط، به اجرای وظیفه جاری تأخیر میدهد. بعبارتی این الگوریتم براساس دانشی در مورد وظیفه جاری و و وظایفی که در آینده وارد سیستم خواهند شد، تصمیمات زمانبندی را اتخاذ میکند. همچنین در این روش قبل از اجرا، محدودیت زمانی و انرژی وظایف و نرخ انرژی قابل ذخیره، نیز بررسی میشود و درصورت ناکافی بودن هر یک از موارد گفته شده، پردازنده به حالت بیکار میرود. واضح است که این روش نرخ خطای سررسید را در مقایسه با سایر روشهای دیگر افزایش میدهد. همچنین در این روش ظرفیت باطری نیز بیشتر خواهد شد چراکه در سیستم پیشنهادی، پردازنده قادر نخواهد بود بطور مستقیم انرژی مورد نیاز خود را از محیط دریافت کند، بلکه برای تأمین انرژی لزوما باید به باطری مراجعه کند. بنابراین باتوجه به اینکه شرط اجرای وظیفه جاری، وجود انرژی کافی برای اجرای سایر وظایف آتی سیستم میباشد، دراینصورت ظرفیت باطری باید به اندازه انرژی مورد نیاز تمامی وظایف سیستم باشد که این در عمل امکانپذیر نخواهد بود. بعلاوه درصورت عدم انرژی کافی، پردازنده به حالت بیکار میرود که این خود میتواند تا زمان برداشت انرژی کافی توسط برداشتگر انرژی، سبب نقض سررسید وظیفه جاری و درنهایت حذف آن از سیستم شود. نکته قابل توجهی که در این مقاله بدان پرداخته شده است بررسی جداگانه بدترین حالت زمان اجرا و بدترین حالت انرژی مصرفی، بعنوان مشخصههای اصلی یک وظیفه میباشد.
3-5 نتیجهگیری
نسل جدید سیستمهای تعبیهشده، برای تأمی
ن انرژی مورد نیاز برای اجرای عملیات خود، قادر به دریافت انرژی از محیط پیرامون میباشند. بدین منظور، سیستم، نیازمند واحد برداشت انرژی و همینطور واحد ذخیرهساز انرژی با قابلیت شارژ مجدد میباشد. بر این اساس و باتوجه به اینکه مقدار این انرژی، در زمان، متغیر میباشد، بحث مدیریت توان و مدیریت انرژی در چنین سیستمهایی بسیار حائز اهمیت است. از اینرو وجود یک الگوریتم زمانبندی مناسب که بتواند تصمیمات دقیقی درمورد زمان درست شروع فعالیت سیستم و همینطور زمان مناسب بیکاری و آرامش آن را طوریکه از اتلاف انرژی برداشت شده نیز جلوگیری کند، اتخاذ کند و درکنار این تصمیمات زمانبندی مدیریت انرژی مناسبی نیز داشته باشد در سیستمهای تعبیهشده مبتنی بر برداشتگر انرژی بسیار مورد توجه قرار دارد. در این حوزه، مطالعات و تحقیقات گستردهای انجام شده است که در فصلی که گذشت به معرفی پارهای از الگوریتمها و روشهای انجام شده پرداختیم. با وجود کارهایی که در این زمینه انجام شده است هنوز وجود الگوریتمی که بتواند درکنار زمانبندی مناسب وظایف، میزان انرژی مصرفی سیستم و همینطور تعداد مراجعات به باطری را برای افزایش طول عمر بیشتر سیستم، کاهش دهد، بسیار لازم و ضروری است. و این مهم با توجه به رشد روز افزون سیستمهای تعبیهشده در تمامی زوایای زندگی بشر، از اهمیت دو چندانی برخوردار میشود. براین اساس در فصل آینده، سیستم تعبیهشده و همینطور الگوریتم زمانبندی متناظر با آن را با هدف کاهش مراجعات به باطری و بهبود انرژی مصرفی در کنار اجرای بیدرنگ وظایف تناوبی و غیر تناوبی، معرفی میکنیم.
فصل چهارم
فصل چهارم : الگوریتم پیشنهادی
4-1 مقدمه
تکنیک برداشت انرژی از محیط پیرامون، مزایای زیادی برای سیستمهای تعبیهشده امروزه، ازجمله پیوستگی در اجرای عملیات سیستم و افزایش طول عمر آن، دارد. اما رسیدن به تمامی این مزایا درکنار یک الگوریتم زمانبندی مناسب که بتواند تصمیمات درست و دقیقی درمورد زمان اجرای وظایف، سرعت مناسب پردازنده و همینطور زمان مناسب، برای رجوع به باطری برای دریافت انرژی، اتخاذ نماید، امکانپذیر است. در این فصل بر این اساس الگوریتم پیشنهادی خود را با هدف کاهش معایب روشهای قبلی ارائه میدهیم.
روش پیشنهادی در این پروژه از دو دیدگاه میباشد :
ذخیرهساز انرژی : یک نکته کلیدی در کارایی سیستمهای تعبیهشده مبتنی بر برداشتگر انرژی، کارایی ذخیرهساز انرژی است]27[. از اینرو در این بخش، روشی برای ذخیره کردن انرژی برداشت شده از محیط، ارائه میشود، که در کنار رجوع کمتر به باطری غیر آیدهآل و در نتیجه کاهش اثرات منفی حاصل از ضریب سودمندی شارژ و دشارژ باطری، بتوانیم وقوع سرریز را نیز در سیستم، کاهش دهیم.
الگوریتم زمانبندی بیدرنگ : مبتنی بر ذخیرهساز انرژی بخش اول، در این بخش با هدف کاهش نرخ خطای سررسید و بهبود انرژی مصرفی وظایف و همینطور کاهش اتلاف انرژی حاصل از سرریز، الگوریتم زمانبندی خود را ارائه میدهیم.
در ادامه با جزئیات بیشتری دو بخش نام برده را بیان خواهیم کرد.
4-2 ذخیرهساز انرژی
در کنار مراجعی که تنها به بحث زمانبندی وظایف در یک سیستم تعبیه شده مبتنی بر برداشتگر انرژی میپردازند، مراجعی نیز هستند که تنها برروی ذخیرهساز انرژی، تمرکز داشته و تنها سعی در یافتن روشی برای بهبود عملیات ذخیره و برداشت انرژی از ذخیرهساز انرژی و افزایش کارایی عملکرد آن را دارند. در این میان، از دید محققان و طراحان، باطری، دارای معایبی است که ادامه استفاده از آن، در سیستمهای تعبیهشده امروزه، نیازمند تمهیداتی در روند طراحی و اصلاح عملکرد آن میباشد.
یکی از راهکارهای موجود در برابر معایب سیستمهای مبتنی بر باطری و افزایش طول عمر مفید آنها، استفاده از تکنیک برداشت انرژی محیطی میباشد اما در اکثر این سیستمها نیز انرژی مازاد در باطری ذخیره میشود، و در صورتیکه اجرای وظایف، انرژی بیشتری از مقدار انرژی برداشت شده بخواهد، پردازنده، برای تأمین انرژی مورد نیاز خود به ناچار، از انرژی ذخیره شده در باطری استفاده میکند. درنتیجه باز هم، عملیات شارژ و دشارژ باطری میتواند، بر روی سیستم، اثرات منفی بسیاری را داشته باشد. خصوصا با توجه به اینکه انرژی محیطی به شدت در زمانهای گوناگون، متغیر میباشد، این مسئله در زمانهای کمبود انرژی محیطی، بیشتر قابل مشاهده است. درنتیجه نیازمند تغییرات اساسی در واحد ذخیرهساز انرژی هستیم تا بتوانیم تا حد ممکن از رجوع به باطری جلوگیری کنیم و یا حتی بتوانیم جایگزین مناسبی برای آن پیدا کنیم. با کاهش مراجعه به باطری میتوانیم تأثیرات ضریب سودمندی را بر روی سیستم، کاهش داده، بعلاوه این امر موجب به حداقل رساندن ظرفیت باطری، شده و در نتیجه هزینه سیستم نیز کاهش مییابد]27[.
در این حوزه برخی محققان برای بهبود شرایط توصیف شده، باتوجه به تکنیکهای جدیدی که در طراحی ابرخازنها^[86] ارائه شده است، از ترکیب ابرخازن و باطری بعنوان ذخیرهساز انرژی استفاده کردهاند. براین اساس در ادامه به معرفی مزایا و معایب ابرخازن در قیاس با باطری با قابلیت شارژ مجدد میپردازیم. لازم به ذکر است که ابرخازن که به آن خازن دو لایه نیز میگویند در مقدار ظرفیت با خازن معمولی متفاوت است و ظرفیت آنها نسبت به خازن معمولی بسیار بیشتر میباشد]28[.
4-2-1 مزایای ابرخازن در برابر باطری با قابلیت شارژ مجدد
از دید پارامترهای
الکتریکی:
سرعت بسیار بالا در عملیات شارژ و دشارژ: ابرخازنها میتوانند در مدت چند میلی ثانیه تا چند دقیقه تهی شده و در مدت چند ثانیه تا چند دقیقه شارژ شوند.