–148

2259965-72517000
دانشگاه صنعتی اصفهان
دانشکده برق و کامپیوتر
زمانبندی وظایف در سیستمهای تعبیهشده بیدرنگ برداشتگر انرژی با هدف کاهش نرخ خطای سررسید و افزایش کارایی انرژی مصرفی
پایان‌نامه کارشناسی ارشد مهندسی کامپیوتر- معماری کامپیوتر
فاطمه درویشی بدرآبادی
استاد راهنما
دکتر محمد علی منتظری
1394
2259965-70612000
دانشگاه صنعتی اصفهان
دانشکده برق و کامپیوتر
پایان‌نامه‌ی کارشناسی ارشد رشته‌ی مهندسی کامپیوتر – معماری کامپیوتر خانم فاطمه درویشی بدرآبادی
تحت عنوان
زمانبندی وظایف در سیستمهای تعبیهشده بیدرنگ برداشتگر انرژی با هدف کاهش نرخ خطای سررسید و افزایش کارایی انرژی مصرفی
در تاریخ 25/03/94 توسط کمیته‌ی تخصصی زیر مورد بررسی و تصویب نهایی قرار گرفت.
1- استاد راهنمای پایان‌نامهدکتر محمدعلی منتظری
2- استاد داور دکتر شادرخ سماوی
سرپرست تحصیلات تکمیلی دانشکدهدکتر محمدعلی خسروی فرد
تشکر و قدردانی :
خداوند را شاکرم که در تمام لحظات زندگی، بزرگترین حامیم بوده و هست. از او توفیق خدمت به کسانی را میخواهم که وجودم جز هدیه وجودشان نیست، پدر و مادر دلسوز و مهربانم که زحماتشان با هیچ واژهای قابل قدردانی نیست. همچنین برخود واجب میدانم از زحمات و دلسوزیهای، استاد ارجمند، جناب آقای دکتر منتظری، کمال تشکر و قدردانی را داشته باشم و از خداوند منان برای ایشان آرزوی سلامتی و سعادت، را دارم. همچنین از همراهیها و دلگرمیهای دوست و همسر مهربانم که معنای زیبای واژه عشق را از او هدیه دارم، بسیار ممنون و سپاسگذارم.

کلیه‌ی حقوق مادی مترتب بر نتایج مطالعات، ابتکارات و نوآوری‌های ناشی از تحقیق موضوع این پایان‌نامه (رساله) متعلق به دانشگاه صنعتی اصفهان است.
تقدیم به :
چشمان زیبای مادرم ،
دستان پرمهر پدرم،
قلب مهربان دوست و همسرم
به پاس قدردانی از دریایی از عشق ، که بیدریغ ، نثارم کردند.
فهرست مطالب
عنوان صفحه
فهرست مطالب……………………………………………………………………………………………………………………………………………هشت
TOC o “1-3” h z u چکیده……………………………………………………………………………………………………………………………………………………………. PAGEREF _Toc422760184 h 1فصل اول: توصیف مسئله1-1 مقدمه PAGEREF _Toc422760186 h 21-2 ساختار پایان نامه PAGEREF _Toc422760187 h 4فصل دوم : مفاهیم اولیه2-1 مقدمه PAGEREF _Toc422760189 h 62-2 سیستمهای تعبیه شده PAGEREF _Toc422760190 h 62-3 سیستم بی درنگ PAGEREF _Toc422760191 h 82-4 زمانبندی وظایف PAGEREF _Toc422760192 h 92-4-1 انواع زمانبندی PAGEREF _Toc422760193 h 92-5 تعاریف اولیه PAGEREF _Toc422760194 h 102-6 الگوریتمهای زمانبندی اولیه PAGEREF _Toc422760195 h 122-6-1 الگوریتم زمانبندی نزدیکترین سررسید اول (EDF) PAGEREF _Toc422760196 h 122-6-2 الگوریتم زمانبندی نرخ یکنواخت (RMS) PAGEREF _Toc422760197 h 132-7 برداشت انرژی محیطی PAGEREF _Toc422760198 h 142-7-1 اجزای سیستم تعبیه شده مبتنی بر برداشت انرژی PAGEREF _Toc422760199 h 152-7-2 انواع سیستم برداشتگر انرژی PAGEREF _Toc422760200 h 162-8 مدیریت توان در سیستمهای تعبیه شده PAGEREF _Toc422760201 h 192-9 نتیجه گیری PAGEREF _Toc422760202 h 20فصل سوم : بررسی منابع و کارهای انجام شده3-1 مقدمه PAGEREF _Toc422760204 h 213-2 الگوریتمهای زمانبندی سیستم تعبیه شده بدون برداشتگر انرژی PAGEREF _Toc422760205 h 223-2-1 الگوریتم زمانبندی MILP وLEDF PAGEREF _Toc422760206 h 233-3 عوامل مشترک در زمانبندی سیستمهای بیدرنگ برداشتگر انرژی PAGEREF _Toc422760207 h 243-4 الگوریتمهای زمانبندی سیستم تعبیه شده مبتنی بر برداشتگر انرژی PAGEREF _Toc422760208 h 253-4-1 روش زمانبندی LSA PAGEREF _Toc422760209 h 253-4-2 روش زمانبندی EA-DVFS PAGEREF _Toc422760210 h 303-4-3 روش زمانبندی AS-DVFS PAGEREF _Toc422760211 h 333-4-4 روش زمانبندی LM-APM PAGEREF _Toc422760212 h 353-4-5 روش زمانبندی HA-DVFS PAGEREF _Toc422760213 h 413-4-6 الگوریتم انتخاب فرکانس باتوجه به وضعیت سیستم PAGEREF _Toc422760214 h 483-5 نتیجه گیری PAGEREF _Toc422760215 h 54فصل چهارم : الگوریتم پیشنهادی4-1 مقدمه PAGEREF _Toc422760217 h 554-2 ذخیره ساز انرژی PAGEREF _Toc422760218 h 564-2-1 مزایای ابرخازن در برابر باطری با قابلیت شارژ مجدد PAGEREF _Toc422760219 h 564-2-2 معایب ابرخازن در برابر باطری با قابلیت شارژ مجدد PAGEREF _Toc422760220 h 574-3 مدل سیستم PAGEREF _Toc422760221 h 614-3-1 مدل برداشتگر انرژی PAGEREF _Toc422760222 h 614-3-2 مدل پردازنده PAGEREF _Toc422760223 h 614-3-3 مدل ذخیره ساز انرژی PAGEREF _Toc422760224 h 624-3-4 مدل وظیفه PAGEREF _Toc422760225 h 634-4 الگوریتم زمانبندی بیدرنگ PAGEREF _Toc422760226 h 634-4-1 انتخاب بازه زمانی PAGEREF _Toc422760227 h 654-4-2 محاسبه انرژی مورد نیاز برای اجرای وظایف موجود در بازه PAGEREF _Toc422760228 h 65center922150نه
نه
4-4-3 محاسبه موجودیت انرژی PAGEREF _Toc422760229 h 664-5 نتیجه گیری PAGEREF _Toc422760230 h 74فصل پنجم : شبیه سازی و نتیجه گیری5-1 مقدمه PAGEREF _Toc422760232 h 755-2 تنظیمات اولیه PAGEREF _Toc422760233 h 755-3 مقایسه نرخ خطای سررسید PAGEREF _Toc422760234 h 785-4 کمترین ظرفیت ذخیره سازی برای داشتن نرخ خطای سررسید صفر PAGEREF _Toc422760235 h 855-5 سودمندی انرژی PAGEREF _Toc422760236 h 875-6 نرخ خطای سررسید در حالت عدم وجود واحد ذخیره ساز انرژی PAGEREF _Toc422760237 h 895-7 : بررسی سربار زمانبندی PAGEREF _Toc422760238 h 895-8 نتیجه گیری PAGEREF _Toc422760239 h 905-9 پیشنهادات PAGEREF _Toc422760240 h 91مراجع PAGEREF _Toc422760241 h 92
center727786ده
ده

فهرست شکلها
TOC h z c “شکل” شکل 1-1 : نمودار مشخصات یک وظیفه PAGEREF _Toc422782510 h 11شکل 2-1 : نوع اول سیستم برداشتگر انرژی PAGEREF _Toc422782511 h 16شکل3-1 : منحنی توان در روش LSA PAGEREF _Toc422782512 h 26شکل 3-2 : مدل سیستم روش LM-APM PAGEREF _Toc422782513 h 36شکل 3-3 : شبه کد الگوریتم HA_DVFS قسمت تنظیم بارکاری پردازنده و انتخاب پویای ولتاژ و فرکانس PAGEREF _Toc422782514 h 44شکل 3-4 : زمانبندی دو وظیفه PAGEREF _Toc422782515 h 45شکل 3-5 : شبه کد الگوریتم بهره وری از انرژی سرریز شده PAGEREF _Toc422782516 h 46شکل 4-1 : اتصال دو باطری برای جداسازی فازهای شارژ و دشارژ PAGEREF _Toc422782517 h 59شکل 4-2: مدل سیستم پیشنهادی PAGEREF _Toc422782518 h 61شکل 4-3: محاسبه dl در حالت Edemand = EH(tc , Dmax) + ES(tc) PAGEREF _Toc422782519 h 68شکل 4-4 : شبه کد الگوریتم پیشنهادی PAGEREF _Toc422782520 h 73شکل 5-1 : نمودار توان برداشت PH(t) PAGEREF _Toc422782521 h 76شکل 5-2 : مقایسه نرخ خطای سررسید الگوریتم پیشنهادی با سایر الگوریتم ها PAGEREF _Toc422782522 h 79شکل 5-3 نمودار خطی تغییرات نرخ خطای سررسید الگوریتم ها در مقادیر متفاوت بهره وری PAGEREF _Toc422782523 h 80شکل 5-4 : 4 نمونه گیری از انرژی خورشیدی PAGEREF _Toc422782524 h 80شکل 5-5 : مقایسه نرخ خطای سررسید برای 5000 مجموعه وظیفه PAGEREF _Toc422782525 h 81شکل 5-6 : مقایسه نرخ خطای الگوریتم ها در مقادیر مختلف ظرفیت باطری و بهره وری PAGEREF _Toc422782526 h 83شکل 5-7 : مقایسه نرخ خطای سررسید در حالت ذخیره ساز دوگانه و باطری PAGEREF _Toc422782527 h 84شکل 5-8 : مقایسه نرخ خطای سررسید در مقادیر مختلف ذخیره سازی باطری و ابرخازن PAGEREF _Toc422782528 h 85شکل 5-9 : مقایسه حداقل ظرفیت واحد ذخیره سازی برای داشتن خطای سررسید صفر PAGEREF _Toc422782529 h 86شکل 5-10: نمودار کارایی انرژی در مقادیر مختلف بهره وری PAGEREF _Toc422782530 h 88شکل 5-11 : مقایسه نرخ خطای سررسید در دو حالت صحت و حذف واحد ذخیره ساز انرژی PAGEREF _Toc422782531 h 89
center650929یازده
یازده

فهرست جدولها
TOC h z c “جدول” جدول 4-1 : مقایسه باطری و ابرخازن PAGEREF _Toc422762790 h 58جدول 4-2 : حالات کاری باطری های شکل4-1 PAGEREF _Toc422762791 h 59جدول 5-1 : مشخصات پردازنده XScale اینتل PAGEREF _Toc422762792 h 76جدول 5-2: نرخ خطای سررسید الگوریتم HA-DVFS براساس شکل 5-4 PAGEREF _Toc422762793 h 80جدول 5-3 : محاسبه سربار زمانبندی الگوریتم ها PAGEREF _Toc422762794 h 90
22767236444238دوازده
0دوازده

-260591-50494300
چکیدهبا رشد و توسعه تکنولوژی در زندگی بشر، نیاز به رشد و توسعه سیستمهای تعبیهشده که بخش عمدهای از سیستمهای دیجیتال را شامل میشوند هم بیشتر میشود.ازجمله مشخصههای اصلی یک سیستم تعبیه شده، بیدرنگ بودن و مصرف انرژی مناسب میباشد بعلاوه اجرای یک برنامه شامل وظایف مختلفی است که هرکدام منابع خاص خود را از سیستم میطلبند حال اگر این منابع در زمان مناسب در اختیار وظایف قرار نگیرد، سیستم نمیتواند بازده و کارایی مناسبی داشته باشد بنابراین وجود یک زمانبند مناسب برای چنین سیستمهایی از اهمیت ویژهای برخوردار است. محدودیت مصرف انرژی در سیستمهای تعبیه شده، بسیار حائز اهمیت است این اهمیت از آنجا ناشی میشود که بسیاری از این سیستمها، مبتنی بر باطری هستند و اغلب مواقع امکان شارژ مجدد باطری وجود ندارد و درصورت اتمام انرژی موجود در باطری، سیستم از کار خواهد افتاد در چنین مواقعی استفاده از برداشتگرهای انرژی میتواند راهکار مناسبی برای غلبه بر محدودیت انرژی سیستم باشد. الگوریتمهای زمانبندی زیادی در زمینه بیدرنگ بودن و بهبود مصرف انرژی ارائه شده است اما هرکدام دارای محدودیتها و نواقصی میباشند در اغلب مطالعات انجام شده از باطری ایده آل بعنوان منبع انرژی که مقدار معین انرژی را در یک ولتاژ خروجی ثابت، ذخیره یا پخش میکند استفاده شده است و از تاثیر ضریب شارژ/دشارژ باطری در میزان انرژی منتقل شده، صرفنظر شده است لیکن این امر همیشه صحیح نیست و طراحی بر مبنای این مدل ساده و حداقل کردن میانگین مصرف انرژی لزوما منجر به بهینه شدن طول عمر باطری نمیشود. در این راستا در این پایان نامه روشی را برای زمانبندی سیستمهای تعبیه شده مبتنی بر برداشت انرژی و باطری غیرایدهآل با هدف بهبود انرژی مصرفی درحین اجرای بیدرنگ وظایف سیستم و کاهش نرخ خطای سررسید مجموعه وظایف، پیشنهاد میدهیم در این روش با انتخاب بازه مناسب برای برداشت انرژی از محیط، به بررسی موجودیت انرژی سیستم و میزان انرژی مورد نیاز برای اجرای بیدرنگ وظایف در آن بازه پرداخته و با توجه به پارامترهای موجود، انرژی مورد نیاز برای اجرای وظیفه و سطح فرکانس مناسب برای پردازنده را اختصاص میدهیم. نتایج حاصل از شبیهسازی نشان میدهد که روش پیشنهادی در مقایسه با روشهای موجود، نرخ خطای سررسید را کمتر میکند همچنین در روش پیشنهادی، تعداد دفعات رجوع به باطری کمتر شده که در نتیجه باعث اتلاف کمتر انرژی حاصل از شارژ/دشارژ باطری و افزایش طول عمر آن و در نهایت افزایش طول عمر سیستم میشود.
کلمات کلیدی : سیستمهای تعبیه شده، برداشتگر انرژی، زمانبندی بیدرنگ، ذخیرهساز انرژی غیرایدهآل
-301249-61837700
فصل اول
فصل اول: توصیف مسئله1-1 مقدمهدر سالهای اخیر با رشد و توسعه کامپیوترها در همه جنبههای زندگی بشر و افزایش نیازهای روزمره و گسترش برنامه‌های کاربردی، نیاز به طراحی و توسعه سیستمهای تعبیهشده بیش از پیش مورد توجه قرار گرفته است. سیستم‌های تعبیه‌شده، ابزارهای محاسباتی هستند که درون بخش عظیمی از محصولات و کاربردهای روزمره جاسازی شدهاند. سیستمهای پردازش اطلاعات در تجهیزات ارتباط از راه دور، سیستمهای حمل و نقل، تلفن همراه، اسباب بازی، دوربین و… مثالهایی از سیستم‌های تعبیه‌شده میباشند. این سیستمها به دلیل خاصمنظوره بودن، جایگزین تجاری مناسب و ماندنی برای کامپیوترها و یا ابزارهای همه منظوره نیستند. همانطورکه برنامه‌های کاربردی بصورت تصاعدی پیچیده میشوند با پیچیدگی ابزارهای محاسباتی تعبیه‌شده نیز مواجه می‌شویم. اکثر این سیستمها دارای محدودیتهای زمانی بوده و نیازمند اجرای وظایف در بازه زمانی خاص میباشند بنابراین وجود یک زمانبند مناسب برای سیستمهای بیدرنگ تعبیه شده، امری ضروری است. الگوریتم زمانبندی مناسب، یکی از قسمتهای مهم سیستمهای بیدرنگ میباشد تا بتواند منابع مورد نیاز وظایف را در زمان مناسب در اختیار آنها قرار داده و وظایف بتوانند در زمان مناسب اجرا شوند. علاوه براین، محیطهای کاری این سیستمها، ضرورت استفاده از منبع انرژی مناسب را برای کاربردهای بیدرنگ ایجاب میکند بنابراین در کنار محدودیت زمانی بحث مدیریت انرژی و منبع انرژی نیز بسیار حائز اهمیت است. اغلب سیستمهای تعبیه شده، مبتنی بر باطری هستند و طول عمر این سیستمها نیز وابسته به طول عمر باطری میباشد بنابراین در بسیاری از مواقع که منبع انرژی دائمی در دسترس نیست استفاده از منابع تجدیدپذیر انرژی میتواند مورد توجه قرار گیرد. بنابراین یکی از راهکارهای موجود پیش پای طراحان سیستمهای تعبیهشده بیدرنگ، استفاده از منابع انرژی محیطی و برداشتگرهای انرژی است. این منابع میتوانند شامل انرژی خورشیدی، حرارتی و شیمیایی باشند و یا حتی انرژی جنبشی حاصل از امواج دریا و یا حرکت دست و پای انسان و سایر موجودات زنده نیز میتواند بعنوان منبع انرژی در اختیار سیستمهای تعبیهشده قرار گیرد. در این سیستمها برخلاف سیستمهای مبتنی بر باطری سنتی که سیستم، بعد از اتمام انرژی موجود در باطری، دیگر قادر به ادامه عملیات خود نیست، میتوانند با استفاده از باطری با قابلیت شارژ مجدد، انرژی را از محیط پیرامون خود دریافت کرده و در باطری و یا سایر ذخیرهسازهای انرژی همچون خازن، ذخیره و در اختیار سیستم قرار دهند. از جمله سیستمهای تعبیهشده بیدرنگ که استفاده از انرژی محیطی میتواند نقش بسیار مهمی در جهت افزایش کارایی این سیستمها داشته باشد عبارتند از : دستگاههای خودپرداز، سیستمهای تعبیهشده موجود در اتوموبیلها (سیستم ضد قفل و دزدگیر و …)، سیستمهای تعبیهشده موجود در اتاق عمل و موارد پزشکی، شبکههای حسگر ، سیستمهای کنترل از راه دور و رباتها خصوصا رباتهای مینیاب و امداد و نجات و … که در همه این موارد اجرای به موقع و صحیح عملیات سیستم بسیار مهم میباشد. بنابراین طول عمر، پیوستگی عملیات و کارایی این سیستمها بسیار حائز اهمیت است که استفاده از تکنیک برداشت انرژی محیطی درجهت بهبود موارد گفته شده میتواند نقش موثری داشته باشد.
امروزه برداشتگرهای انرژی، بسیار مورد توجه قرار گرفتهاند و ازجمله چالشهای موجود در این سیستمها، تکنیکهای مدیریت توان خوب در کنار الگوریتمهای زمانبندی مناسب میباشد. در دهه گذشته محققان بدنبال مسئله توان و انرژی و زمانبندی با هدف کاهش توان مصرفی تحت محدودیتهای انرژی بودند اما در بیشتر کارهای انجام شده بدنبال قابلیت شارژ مجدد باطریها نبودند. ایدهی اکثر کارهای پیشین، ذخیره توان، توسط کاهش سرعت پردازنده بود و از دید آنها این مسئله برای تأمین محدودیتهای زمانی سیستم کافی بود. اما امروزه بکار بردن این تکنیکها به تنهایی در سیستمهای مبتنی بر برداشت انرژی، موجب بروز محدودیتهایی در این سیستمها میشود چراکه آنها توان پردازشی را بجای مدیریت پویای توان، برطبق انرژی موجود و بارکاری پردازنده، کمینه میکنند. به عبارتی چالشهای تکنیکی زیادی باید حل شوند تا بتوان به سیستم تعبیهشده کارا رسید. منبع انرژی، ناپایدار است و موجودیت انرژی محیط، از زمانی به زمان دیگر دائما درحال تغییر است بنابراین باید مدلی از برداشت انرژی و توان متناظر بصورت یک متغیر زمانی داشته باشیم تا بتوانیم براساس اطلاعاتی که از موجودیت انرژی در هر لحظه داریم به زمانبندی وظایف بپردازیم. در سیستمهای برداشتگر انرژی، هدف از زمانبندی بیدرنگ این است که وظایف، مادامیکه انرژی در منبع ذخیرهساز موجود است، در سررسید متناظرشان اجرا شوند.
در این راستا در این پایان نامه ابتدا به معرفی مدلی برای ذخیرهساز انرژی در سیستم برداشتگر انرژی پرداخته و سپس متناسب با مدل بیان شده، الگوریتمی برای اجرای بیدرنگ وظایف ارائه میدهیم. سیستم تعبیهشده روش پیشنهادی مبتنی بر پردازنده با قابلیت انتخاب پویای ولتاژ و فرکانس میباشد و بدین ترتیب، میتوان بهازای هر وظیفه و موجودیت انرژی در محیط و ذخیرهساز انرژی، سطح فرکانس مناسب را برای اجرای وظیفه به پردازنده اختصاص داد و درنهایت از طریق زمانبندی به مدیریت انرژی در سیستمهای بیدرنگ تعبیه شده مبتنی بر برداشت انرژی خواهیم پرداخت.
1-2 ساختار پایان نامهفصلها در این پایان نامه بدین ترتیب سامان یافتهاند:
در فصل اول به تعریف و بیان مسئله پرداختیم. در فصل دوم بطور کامل به معرفی سیستمهای تعبیهشده و مشخصات آنها میپردازیم. سیستم‌های تعبیهشده (نهفته یا توکار نیز گفته می شوند) سیستم‌هایی کامپیوتری هستند که به عنوان بخشی از یک سیستم بزرگتر که خود شامل اجزای الکترونیکی و یا مکانیکی است، می‌باشند و وظیفه‌ی کنترل عملکرد و پردازش درست سیستم را بر عهده دارند. بر خلاف کامپیوترهای همه منظوره ( به عنوان مثال کامپیوترهای شخصی) که برای رفع نیازهای عمومی طراحی شده‌اند، سیستم‌های نهفته به گونه‌ای طراحی می‌شوند که برای یک کاربرد خاص با کمترین هزینه بهترین کارایی را از خود نشان دهند. امروزه درون اکثر وسایل و دستگاه‌های پیرامون ما (خودپرداز، تلفن‌همراه، اتومبیل و ماشین لباسشویی) سیستم نهفته‌ای قرار دارد. مشخصه‌ی کلیدی این سیستم‌ها، طراحی اختصاصی برای انجام یک کار مشخص است. به این دلیل که سیستم‌های نهفته برای یک کار مشخص اختصاص یافته‌اند، مهندسین طراح می‌توانند محصول را برای کاهش اندازه و قیمت بهینه کرده و اطمینان پذیری و کارایی آن را بالا ببرند. امروزه، انواع باطری، نقش اساسی را در جهت تأمین انرژی سیستمها برعهده دارند. این مسئله باعث بروز مشکلاتی همچون کاهش طول عمر سیستمها و عدم پیوستگی عملیات آنها میشود. که برای غلبه بر این مشکلات راهکاری که معرفی میشود، استفاده از تکنیک برداشت انرژی از محیط با استفاده از برداشتگرهای انرژی است. با استفاده از این روش، انرژی همواره در اختیار سیستم قرار گرفته و مشکلات ناشی از عدم وجود انرژی کافی و سایر مشکلات، مرتفع میشود. سیستمهای تعبیه شدهای که انرژی مورد نیاز خود را از محیط پیرامون تأمین میکنند به سیستمهای تعبیهشده مبتنی بر برداشتگر انرژی معروفند. مسائل مهمی که در این نوع از سیستمها مطرح است، بحث زمانبندی وظایف یک برنامه با درنظر گرفتن محدودیت انرژی و محدودیت زمانی خاص وظایف، کارایی ذخیره سازی انرژی و البته کارایی تمام بخشهای یک سیستم تعبیهشده مبتنی بر برداشتگر انرژی و … میباشد. که این مسائل در کنار انواع سیستمهای برداشتگر انرژی و الگوریتمهای اولیه زمانبندی در سیستمهای تعبیهشده همچنین معرفی روشهای مدیریت توان در سیستمهای تعبیهشده بیدرنگ نیز در فصل دوم بیان خواهند شد.
در ادامه در فصل سوم به معرفی کارهای انجام شده در زمینه زمانبندی سیستمهای تعبیهشده بیدرنگ مبتنی بر باطری و همینطور مبتنی بر برداشت انرژی، خواهیم پرداخت و نواقص کارهای انجام شده نیز در این فصل بررسی خواهند شد. بطورکلی منابعی که در زمینه زمانبندی این نوع سیستمها معرفی شدهاند به دو دسته کلی روشهای تحلیلی بر پایه مسائل ریاضی و روابط آن و روشهای مبتنی بر الگوریتم و شبیهسازی و پیادهسازی قابل تقسیماند. در فصل سوم در ابتدا به معرفی چند روش ابتدایی که وظایف را در سیستمهای مبتنی بر باطری و بدون در نظر گرفتن تکنیک برداشت انرژی، زمانبندی میکنند میپردازیم و در ادامه برخی روشهای زمانبندی که مبتنی بر تکنیک برداشت انرژی میباشند را معرفی و بررسی خواهیم کرد. بطور خاص در این بخش از فصل سوم، الگوریتمهایی را که در روش پیشنهادی این گزارش، از آنها استفاده شده است را معرفی و مقایسه میکنیم. لازم به ذکر است که ترتیب معرفی این روشها بدین صورت است که هر الگوریتمی که در ادامه الگوریتم (ها)ی قبلی معرفی شده است، سعی در رفع نواقص روش(ها)ی قبلی دارد و روش پیشنهادی ما نیز که در فصل چهارم آورده شده است در ادامه این روشها میباشد. در انتهای فصل نیز برخی الگوریتمهای زمانبندی دیگر که لزوما نقشی در روش پیشنهادی این گزارش ندارند آورده شده اند.
در فصل چهارم، به معرفی و بیان روش پیشنهادی خواهیم پرداخت. در این فصل روش پیشنهادی در دو بخش ارائه میشود. در بخش اول با توجه به مراجع موجود و روشهایی که در زمینه بهینهسازی ذخیرهساز انرژی و افزایش کارایی آن معرفی شده است، روشی را برای ذخیرهسازی انرژی معرفی میکنیم که در این روش تأثیر ضریب شارژ و دشارژ باطری به حداقل رسیده است و بدین ترتیب کارایی این بخش از سیستم تعبیهشده مبتنی بر برداشتگر انرژی را افزایش میدهیم. در ابتدای بخش اول مزایا و معایب روشهای موجود در این زمینه را نیز بررسی و بیان خواهیم کرد. در ادامه در بخش دوم، الگوریتم زمانبندی مبتنی بر سیستم پیشنهادی معرفی شده در بخش اول را بیان خواهیم کرد. همانطورکه در فصل دوم بیان خواهد شد، یکی از مشخصههای اصلی سیستمهای تعبیهشده، اجرای بیدرنگ وظایف میباشد. در کنار این مسئله بررسی موجودیت انرژی برای اجرای هر وظیفه نیز بسیار حائز اهمیت است از این رو الگوریتم پیشنهادی سعی در اجرای وظایف در زمان مناسب و با مصرف انرژی مناسب میباشد که جزئیات کامل این الگوریتم در فصل چهارم، آورده شده است.
در نهایت در فصل پنجم، نتایج حاصل از شبیهسازی روش پیشنهادی بیان خواهد شد. در این فصل به مقایسه الگوریتم پیشنهادی با برخی الگوریتمهای دیگر از دید مصرف انرژی، تأمین سررسید وظایف و برخی پارامترهای دیگر خواهیم پرداخت و با نتیجهگیری و معرفی برخی کارهای آتی، به گزارش پیشرو پایان خواهیم داد.
-179593-50255500
فصل دوم
فصل دوم : مفاهیم اولیه2-1 مقدمهدر این فصل به معرفی سیستم تعبیهشده و نیازمندی آن، همینطور تکنیک برداشت انرژی از محیط و لزوم استفاده از آن میپردازیم. در یک سیستم تعبیه شده بیدرنگ مبتنی بر برداشت انرژی علاوه بر اجرای وظایف در سررسید متناظرشان با توجه به محدودیتهای زمانی تعریف شده، بحث مدیریت توان و انرژی نیز بسیار حائز اهمیت است. بنابراین در این فصل قبل از معرفی الگوریتمها و روشهای موجود، مفاهیم اولیه در این سیستمها را بررسی خواهیم کرد.
2-2 سیستمهای تعبیهشدهامروزه کاربردهای فراوان سیستمهای دیجیتال، برکسی پوشیده نیست. لیکن بسیاری از مردم تنها کامپیوتر شخصی خود را به عنوان یک سیستم کامپیوتری میشناسند. حال آنکه روزانه با دهها سیستم مبتنی بر پردازنده، برخورد و تعامل دارند. مایکروفرها، اتومبیلها (حتی اجزای درون اتومبیل مثل سیستم ضدقفل و …)، دستگاههای کنترل از راه دور، تلفن همراه، آسانسورها و حتی ماوس و صفحه کلید یک کامپیوتر رومیزی نیز در ردهی سیستمهای مبتنی بر پردازنده قرار میگیرند. برخلاف کامپیوترهای همهمنظوره که برای رفع نیازهای عمومی طراحی شده‌اند، سیستم‌های نهفته به گونه‌ای طراحی می‌شوند که برای یک کاربرد خاص با کمترین هزینه بهترین کارایی را از خود نشان دهند. این سیستمها داری هسته پردازشی شامل میکروکنترلر، ریزپردازنده و یا پردازنده سیگنالهای دیجیتال میباشند این هسته پردازشی بعنوان یک واحد مهم در سخت‌افزار یک سیستم تعبیهشده ایفای نقش میکند]1[ .
سیستمهای تعبیه‌شده برای اهداف خاص طراحی می‌شوند و اغلب توسط ابزارهای دیگر(نه لزوما کامپیوترها) و پروسههای خاصی کنترل می‌شوند. برخی از این سیستم‌ها نیازمندی‌های خاصی نظیر حمایت از پردازش‌های بیدرنگ دارند. معمولا برنامه‌های کاربردی یک سیستم تعبیه شده را روی یک کامپیوتر رومیزی، طراحی و در نهایت روی سخت افزار و سیستمعامل تعبیهشده خاص خود، پیاده سازی میکنند که در طراحی این برنامه‌ها باید مشخصههای خاص و عام سیستم تعبیهشده در نظر گرفته شود.
مشخصههای یک سیستم تعبیه شده عبارتند از ]1[ :
هزینه کم : باتوجه به فراوانی سیستمهای تعبیهشده در زندگی بشر، طراحان باید بتوانند سیستمهای تعبیهشدهای با حداقل قیمت و بالاترین کارایی طراحی کنند. بنابراین منابع موجود برای طراحان محدود است.
توان پایین : یک فاکتور بحرانی در طراحی چنین سیستمهایی پایین بودن توان مصرفی آنهاست چراکه این سیستمها اکثرا با باطری کار کرده و انتظار میرود که در یک دوره زمانی طولانی فعال باقی بمانند بعنوان مثال حسگرها، تلفن‌های همراه و PDA ها. بعلاوه اندازه یک سیستم تعبیه شده نیز یک عامل محدود کننده در استفاده از ابزارهای خنک کننده در سیستم است بنابراین خاصیت کم‌توان بودن یک سیستم تعبیه شده یک مشخصه اساسی است.
قابلیت پیش‌بینی پذیری : بدلیل اینکه تعداد زیادی از برنامه‌های کاربردی بیدرنگ، توسط سیستم‌های تعبیه‌شده اجرا می‌شوند، پیش بینی رفتار این سیستمها بسیار مهم است. این بدین معنی است که رفتار این سیستمها، تحت هر شرایطی باید قابل پیشبینی باشد. این سیستمها شامل سخت افزاری هستند که تضمین میکند هر زیربرنامه‌ای که روی آنها اجرا می‌شود، در هر زمان اجرا، سربار اجرای یکسانی داشته باشد. علاوه براین، نرم افزارهای موجود با در نظر گرفتن بدترین شرایط ممکن طراحی می‌شوند و به این طریق است که سربار زمانی سیستم را می‌توان بصورت قطعی درنظر گرفت. بنابراین قابلیت پیش بینی در سیستم‌های تعبیه‌شده، ممکن و قابل اجراست.
قابلیت اعتماد : بسیاری از سیستم‌های تعبیه‌شده، بحرانی امن هستند بنابراین باید در سطح قابل قبولی از اعتماد پذیری قرار داشته باشند. تجهیزات انرژی هسته‌ای یک نمونه از سیستم‌های به شدت بحرانی امن هستند که بخش‌های بحرانی آن باید بطور کامل توسط نرم افزار، کنترل شوند. قابلیت اعتماد در سایر سیستمها مثل خودرو، قطار، هواپیما و… هم بسیار مهم است. ویژگی قابلیت اعتماد، جنبههای زیر از یک سیستم را دربرمیگیرد :
قابلیت اطمینانکه یک سیستم خراب نشود و در صورت خرابی بتوان قسمت خراب شده را در مدت زمان مشخص و مناسبی ترمیم کرد (نگهداشت پذیری ). همچنین در دسترس بودن و قابلیت استفاده ، ایمنی که هیچ خرابی در سیستم، سبب آسیب و صدمه به کل سیستم یا کاربر آن، نشود. و درنهایت امنیتکه محرمانگی دادههای حساس در سیستم حفظ شود.
کارایی : سیستمهای تعبیهشده باید از لحاظ انرژی مصرفی، اندازه برنامه، زمان اجرا و هزینه، کارا باشند که از این میان کارایی در میزان انرژی مصرفی از اهمیت بسیار بالایی برخوردار است
خاص منظوره بودن : همانطور که گفته شد برخلاف سیستمهای رومیزی همه منظوره، یک سیتم تعبیه شده باید برای هدف خاصی طراحی شده باشد. بعنوان مثال پردازندههای کنترل ماشین و یا قطار، نرم افزار و برنامههای خاص آن را راه اندازی و اجرا میکنند نه نرم افزار پردازنده یک کامپیوتر یا دوربین و … را.
2-3 سیستم بیدرنگاجرای بیدرنگ وظایف و عملیات سیستم،علاوه بر ویژگیهای ذکر شده، مسئله مهمی است که در برخی سیستمهای تعبیهشده همچون سیستمهای پزشکی، ارتباطات چندرسانهای، رادارهای فضایی و… از اهمیت ویژهای برخوردار است. یک سیستم بیدرنگ، سیستمی است که هم شامل صحت منطقی خروجیها است و هم زمان پاسخ مناسب سیستم را دربر میگیرد وباید علاوه بر ارضای محدودیتهای زمانی، نتایج و پیامدهای سخت حاصل از ریسک، مثل خرابی و ازدست رفتن وظیفه را کنترل کند. طبق تعریف Donald Gillies ” صحت محاسبات، در یک سیستم بیدرنگ، نه فقط وابسته به صحت و درستی منطقی محاسبات است بلکه همچنان وابسته به زمان نتایج حاصله میباشد و اگر محدودیتهای زمانی در نظر گرفته نشود خطای سیستمی رخ میدهد.”
بطورکلی سیستمهای بیدرنگ، پاسخی برای یکسری از ورودیهای خارجی هستند که بصورت غیرقابل پیشبینی وارد سیستم میشوند سپس این ورودیها توسط سیستم بیدرنگ پردازش شده و تصمیمات مناسب در زمان مناسب اتخاذ میشوند همچنین خروجی لازم برای کنترل دستگاههای جانبی متصل به آنها نیز تولید میشود و در صورتیکه سرویسها و منابع خواسته شده توسط وظیفه، قبل از اتمام آن، در اختیارش قرار نگیرد و وظیفه نتواند در زمان مناسب و تعیین شده خاتمه یابد، وظیفه مورد نظر از اعتبار ساقط و خراب میشود بر این اساس سیستمهای بیدرنگ، از لحاظ محدودیت زمانی به 3 دسته تقسیم میشوند ]2[ :
بیدرنگ سخت: در این سیستم، پاسخ دیرهنگام، ناصحیح بوده و منجر به خطای سیستمی میشود و تمامی وظایف باید در سررسید خود اجرا شده در غیر اینصورت منجر به ایجاد یک فاجعه میشود. بعنوان مثال در یک نیروگاه هستهای تأخیر در وظیفهای که مسئول خنک کردن راکتور میباشد می تواند منجر به وقوع فاجعه شود.
بیدرنگ نرم: اجباری در بررسی تمامی محدودیتهای زمانی سیستم نیست و در صورت تأخیر در اجرای وظیفه، سیستم دچار بحران و یا وقوع فاجعه نمیشود گرچه تکرار تأخیر، میتواند منجر به خطای سیستمی شود. برنامه‌های چندرسانه‌ای مثالی از این سیستمهاست.
بیدرنگ ثابت: این سیستم، سررسیدهای سختی دارد اما در جاییکه یک احتمال کم و مشخص از خطا و نقض سررسید وجود دارد، سیستم میتواند این خطا را تحمل کند بعبارتی سررسیدها هم به صورت سخت و هم به صورت نرم هستند. یعنی درعین حال که اجرا نشدن وظیفه در سررسیدش باعث بیاعتبار شدن آن وظیفه میشود (مثل بیدرنگ سخت) اما گاهی سیستم میتواند سررسید را نادیده بگیرد (مثل وقفه‌های نرم).
2-4 زمانبندی وظایف
در کنار مشخصههای سیستمهای تعبیهشده بحث زمانبندی و ترتیب اجرای وظایف بسیار حائز اهمیت است. وظایف زیادی در اجرای یک برنامه وجود دارد که هر کدام متقاضی منابع خاص خود از سیستم میباشند منابعی همچون پردازنده، حافظه، وسایل ورودی/خروجی و… . علاوه بر اینها هریک از وظایف، دارای محدودیتهای زمانی خاص خود نیز میباشند محدودیتهایی که باعث الزام اجرای وظیفه در یک بازه زمانی خاص میشود حال اگر منابع مورد نیازسیستم در زمان مناسب در اختیار وظیفه قرار نگیرد سیستم نمیتواند بازده و کارایی مناسبی داشته باشد در این میان دو بحث زمانبندی و تخصیص مطرح میشود. زمانبندی یعنی تخصیص پردازنده به وظایف و تخصیص یعنی اختصاص دادن سایر منابع به وظایف.
بحث زمانبندی یک مسئله کاملا کلی و عمومی است و باید با توجه به نواحی مختلفی که مطرح میشود بطور خاص مورد بررسی قرار گیرد بعنوان مثال، وظایف در صنعت، عملیات ساخت و تولید و واحدهای پردازشی، ماشینها هستند و در حمل و نقل، ممکن است عملیات پرواز و واحدهای پردازشی، هواپیماها باشند. بسته به محیط اجرایی، وظایف انواع و دسته بندیهای مختلفی دارند. وظایف میتوانند بصورت دوره ای تکرار شوند و یا رخدادگرا باشند به این معنی که درصورتیکه وقفه خاصی فعال شود و یا وظیفه دیگری که وابسته به وظیفه جاری است، اجرا و خاتمه یابد و یا سایر رخدادهای سیتمی، در این صورت، وظیفه مورد نظر، فعال شده و باید اجرا شود. دورهی وظایف دورهای هم میتواند ثابت باشد و یا بصورت پویا رخ دهد ]3[.
2-4-1 انواع زمانبندیالگوریتمهای زمانبندی را از دیدگاههای مختلفی به چند دسته تقسیم میکنند]4[ :
زمانبندی ایستا : در این نوع زمانبندی، تصمیمات در مورد زمان شروع و خاتمه وظیفه قبل از شروع به کار سیستم، کاملا مشخص بوده و زمانبندی با مرتبه ثابت صورت میگیرد در این نوع زمانبندی اولویتها ثابت و سربار پردازنده بسیار کم است ]4[.
زمانبندی پویا : در این نوع زمانبندی، هیچ پیشبینی از بارکاری آتی سیستم نداریم و تصمیمات در زمان ورود وظیفه به صف آماده و عموما براساس اولویت هر وظیفه، گرفته میشود همچنین میتواند خود را با متغیرهای پویا در تقاضای کاربر و موجودیت منابع، سازگار کند بعبارتی زمانیکه تقاضای کاربر همچنین موجودیت منابع از قبل مشخص نیست از این زمانبندی استفاده میشود]5[.
زمانبندی انحصاری : در این نوع زمانبندی، پردازنده در اختیار و انحصار وظیفه با بالاترین اولویت قرار میگیرد و اگر درحین اجرای یک وظیفه، وظیفهای با اولویت بالاتر وارد لیست آماده شد، پردازنده از وظیفهی در حال اجرا گرفته شده و به وظیفه با اولویت بالاتر اختصاص مییابد(بعبارتی وظیفه با بالاترین اولویت، پردازنده را به انحصار خود درمیآورد.) در اینحالت اجرای وظیفه با بالاترین اولویت قطعی است و بدین ترتیب زمان پاسخ وظیفه کاهش مییابد بعد از اتمام وظیفه جدید هم، پردازنده لزوما به وظیفه معلق شده باز نمیگردد. اکثر سیستمهای بیدرنگ، انحصاری هستند چراکه واکنشپذیری در سیستمهای انحصاری بسیار مهم است.
زمانبندی غیرانحصاری : عکس سیستمهای انحصاری است و هر وظیفه در بازهای از زمان، پردازنده را در اختیار میگیرد و انحصار فقط در مورد وظیفه با اولویت بالا نیست ]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τ میباشد.
3433445923290143891011722102026920959485277622089027019888206877051439545160020
233337346654T1
00T1

197994062414d1,1
00d1,1
1981200276797
307072932485D1,2
00D1,22408555643255شکل SEQ شکل * ARABIC 1-1 : نمودار مشخصات یک وظیفهشکل SEQ شکل * ARABIC 1-1 : نمودار مشخصات یک وظیفهcenter43096D1,1
00D1,117143015757a1,1
00a1,1

شکل 1-1 : نمودار مشخصات یک وظیفه
P : اولویت اجرای هر وظیفه میباشد که عموما برای سیستمهای بیدرنگ که بحث زمان و اجرا در زمان خاص بسیار حائز اهمیت است، سررسید متناظر هر وظیفه بعنوان اولویت آن درنظر گرفته میشود و در زمان اجرا وظیفهای که کمترین سررسید را داشتهباشد اولویت بیشتری برای اجرا خواهد داشت.
WCET : بدترین حالت زمان اجرای وظیفه.
WCEC : بیشترین انرژی مورد نیاز برای اجرای وظیفه.
همواره داریم :
0 ≤ WCET ≤ d ≤ T (3)
دقت شود که پارامترهای WCET و WCECلزوما متناسب با یکدیگر نیستند و وظیفهای که بیشترین زمان اجرا را دارد لزوما بیشترین انرژی مصرفی را ندارد.
2-6 الگوریتمهای زمانبندی اولیهتحقیقات گستردهای روی زمانبندی وظایف درکاربردهای بیدرنگ با محدودیتهای زمانی انجام شده است که در ادامه به اختصار به معرفی دو الگوریتم اولیه میپردازیم.
2-6-1 الگوریتم زمانبندی نزدیکترین سررسید اول (EDF)
این الگوریتم معروفترین الگوریتم زمانبندی بیدرنگ میباشد که برای سیستمهای تعبیه شدهی تک پردازندهای با هدف اجرای بیدرنگ وظایف طراحی شد. با وجود اینکه الگوریتمی بهینه میباشد اما برای اجرا در سیستمهای چند هستهای مناسب و بهینه نیست.( طراحان در سالهای بعد از ارائه نسخه تک پردازنده الگوریتم EDF ، نسخههای متناسب با سیستمهای چند پردازندهای هم ارائه دادند که همچنان بحث درمورد بهینه بودن آنها مطرح است.) این روش بطور کلی از توان محاسباتی پردازنده استفاده کرده و زمانبندی را بصورت پویا و درصورت فعال شدن هر وظیفه در زمان اجرا انجام میدهد فرض اولیه برای EDF اینست که در هر نقطه از زمان، اولویت یک وظیفه فعال شده ثابت نیست و به زمان بستگی دارد و در زمان فعال شدن وظیفه بعدی ممکن است تغییر یابد، اولویت، طبق سیاست EDF بدین گونه تعریف میشود که وظیفه درحال اجرا باید کمترین زمان باقی مانده تا درخواست بعدی را از بین تمامی وظایف فعال شده (وظایف موجود در صف آماده) داشته باشد به عبارتی اولویت اجرا با وظیفهای است که نزدیکترین سررسید را داشته باشد و وظیفهای که بیشترین اولویت (کمترین سررسید) را دارا میباشد زودتر اجرا میشود. علاوه بر این طراحان به بحث قابل زمانبندی بودن یک مجموعه وظیفه نیز پرداخته و از دید آنان یک مجموعه، شامل N وظیفه با مشخصههای Ci (زمان اجرای هر وظیفه) و Ti (تناوب هر وظیفه) تنها در صورت شرط زیر قابل زمانبندی است]6[.
i=1NCi Ti ≤ 1 (4)
قابل اثبات است که الگوریتم “نزدیکترین سررسید اول” نسبت به این شرط، امکان پذیر و بهینه است اما در عین حال این روش نیازمند به انحصار در آوردن یک وظیفه قبل از اتمام آن است و این باعث افزایش سربار زمان اجرا بدلیل عملیات سوئیچ پردازنده از یک وظیفه به وظیفه با اولویت بالاتر و تأثیرات منفی اجرای وظایف در لایههای حافظه نهان میشود.
بطور کلی مشخصه های اصلی الگوریتم “نزدیکترین سررسید اول” عبارتند از :
بهینه بودن
پیاده سازی و اجرای ساده
ساده بودن شرط قابل زمانبندی
برای تعداد پردازنده بیشتر از 1 بهینه نیست.
با وجود تمام ویژگیهاییکه این الگوریتم دارد اما فقط از دید محدودیت زمانی و زمان اجرا بدان پرداخته شده است و سایر پارامترهای مهم همچون محدودیت انرژی و توان مصرفی وظایف و پردازنده حین اجرا اشاره ای نشده است اما در کل با توجه به بهینه بودن زمانی این الگوریتم، اساس بسیاری از الگوریتمها میباشد.
2-6-2 الگوریتم زمانبندی نرخ یکنواخت (RMS)
الگوریتم زمانبندی نرخ یکنواخت، الگوریتمی اولویت دار و ایستا است. که اولویتها را براساس پریود زمانی طوریکه وظیفه با کوتاهترین دوره تناوب و یا بالاترین نرخ اجرا، بالاترین اولویت را به خود اختصاص میدهد. Liu , Layland نشان دادند که درصورتیکه تخصیص اولویت RMS امکانپذیر نباشد، در اینصورت مجموعهای از وظایف قابل زمانبندی نیستند.
فرضیات اولیهای که مطرح میشود عبارتند از :
تمامی وظایف بصورت دوره ای تکرار میشوند.
همزمانی، اشتراک منابع و مبادله و تغییر داده در وظایف وجود ندارد.
پردازنده همواره وظیفه با بالاترین اولویت را اجرا میکند.
طبق این الگوریتم تمامی وظایف با مشخصه بیدرنگ سخت در صورتیکه شرط زیر برقرار باشد همواره در سررسید متناظرشان اجرا میشوند :
i=1NEi Ti ≤ n (21n-1 ) (5)
Ei : بیشترین زمان اجرای i امین وظیفه
Ti : دوره تناوب اجرای i امین وظیفه n : تعداد وظایف
بعبارتی Ei Ti کسری از زمان مورد نیاز پردازنده برای اجرای i امین وظیفه است. زمانیکهn→∞ مقدار n 21n-1 ~ 0.693 و این بدان معنی است که برای اینکه تمامی وظایف بیدرنگ سخت در زمان مناسب، اجرا شوند، پردازنده باید 70% زمان خود را صرف چنین وظایفی کند و این درحالی است که پردازنده، قادر به اختصاص 100% زمان خود به وظایف بیدرنگ نرم میباشد بنابراین این ویژگی مطلوبی نیست چراکه در اینصورت زمانی برای تغییر کدها و مشخصههای اضافه شده نداریم طبق یک حساب سرانگشتی باید سیستمی طراحی کرد که کمتر از 60% تا 70% از زمان پردازنده به اجرای وظایف اختصاص یابد علاوه بر مشکلات گفته شده در صورتیکه وظیفه با بالاترین نرخ اجرا، بالاترین اولویت را داشته باشد ممکن است وظیفهای که خیلی مهم نیست و درعین حال زیاد اجرا میشود بالاترین اولویت را بگیرد و این باعث وقوع قحطی در وظایف مهمتر با نرخ اجرای کمتر میشود ]6[.
الگوریتم زمانبندی “نرخ یکنواخت” نیز همچون الگوریتم “نزدیکترین سررسید اول” فقط به اجرای وظایف در بازه زمانی مشخص پرداخته و هیچگونه تأملی برروی انرژی و توان مورد نیاز برای اجرای وظایف نداشته است. امروزه با توجه به اهمیت سیستمهای تعبیهشده، پرداختن فقط به یک مشخصه و بهبود آن در این سیستمها کار درست و بهینهای نیست. درست است که الگوریتم “نزدیکترین سررسید اول” الگوریتمی بهینه از دیدگاه زمانی محسوب میشود اما اگر اجرای این الگوریتم به تنهایی نتواند دیگر پارامترهای سیستم (همچون انرژی مصرفی) را بهبود دهد تأثیر چندانی در کارایی سیستم ندارد. بعبارتی الگوریتمی برای سیستمهای تعبیه شدهی بیدرنگ مناسب است که در کنار بررسی محدودیت زمانی بتواند به بررسی یک یا چند پارامتر مهم همچون انرژی مصرفی، توان پردازشی، حرارت، طول عمر سیستم، قابلیت تحمل پذیری خطا و… در الگوریتم زمانبندی مورد نظر بپردازد و تأثیر هریک از این عوامل را برروی کارایی سیستم بررسی کند]7[.
2-7 برداشت انرژی محیطیازجمله چالشهایی که در یک سیستم تعبیه شده مطرح است بحث انرژی مصرفی در کارایی چنین سیستمهایی است. تا قبل از سال 2005 انرژی مورد نیاز، منحصرا توسط انواع باطری تأمین میشد. باطریها بدلیل ضریب شارژ/دشارژی که دارند نمیتوانند منبع مناسبی برای تأمین انرژی سیستمهای تعبیه شده باشند. ازجمله معایب یک سیستم مبتنی بر باطری عبارتند از:
طول عمر محدود باطری : طول عمر سیستمهای مبتنی بر باطری وابسته به طول عمر باطری میباشد در نتیجه با کاهش عمر باطری، ادامه بقای این سیستمها هم با خطر مواجه میشود.
کاهش ظرفیت باطری در دراز مدت بدلیل ضریب سودمندی انرژی λ : باطریها در درازمدت ظرفیت مفید انرژی خود را ازدست میدهند.
هزینه بالا در جایگزین کردن باطری
عدم پیوستگی در اجرای عملیات سیستم : در صورت نیاز به جایگزین کردن باطری بدلیل خرابی، اجرای عملیات سیستم با تأخیر مواجه میشود و این برای یک سیستم تعبیه شده یک نقص محسوب میشود.
بنابراین طراحان سیستم تعبیه شده بدنبال راهکاری برای رفع مشکل بودند و از جمله راهکارهای معرفی شده، بحث برداشت انرژی از محیط میباشد.
نظریه برداشت انرژی، مبحثی است برای جداسازی محدودیت انرژی از سیستمهای مبتنی بر باطری و افزایش استقلال سیستم. بطور ساده سیستم برداشتگر انرژی، سیستمی است که قسمتی یا تمامی انرژی مورد نیاز برای اجرای عملیاتش را از منابع انرژی محیط پیرامون خود بدست میآورد این منابع محیطی میتوانند شامل انرژی خورشیدی، انرژی مکانیکی، انرژی شیمیایی، انرژی حاصل از باد یا امواج دریا و … باشند. در واقع اگر سیستمها بجای منبع انرژی و ذخیره آن، دارای یک مبدل انرژی باشند و بتوانند انرژی مورد نیاز خود را از محیط دریافت کنند علاوه بر افزایش طول عمر سیستم و کاهش هزینه، این امر باعث مستقل شدن هرچه بیشتر سیستمهای تعبیه شده و رشد کارایی آنها در زندگی بشر میشود. بنابراین دو مزیت اصلی چنین سیستم هایی عبارتند از:
داشتن پتانسیل غلبه بر محدودیت انرژی تحمیل شده توسط سیستمهای تعبیه شده مبتنی بر باطری قدیمی
حفظ پیوستگی در اجرای عملیات سیستم تا زمان وقوع خطای مکانیکی
شایان ذکر است که تکنولوژی برداشت انرژی از محیط، خود به تنهایی مبحث جدیدی نیست آنچه که حائز اهمیت است اینست که چطور بتوان از قابلیت آن در جهت افزایش کارایی انرژی سیستمهای تعبیه شده برای برآورده کردن محدودیتهایش استفاده کنیم. بطور مثال چند دهه است که از انرژی خورشیدی، مکانیکی و … استفاده میشود اما مهم اینست که از توان این منابع در جهت تغذیه سیستم تعبیه شده خود استفادهی بهینه و درست را داشته باشیم ]8[.
2-7-1 اجزای سیستم تعبیهشده مبتنی بر برداشت انرژیبطور کلی عملکرد یک سیستم برداشتگر انرژی بدین صورت است که ابتدا انرژی توسط برداشتگرهای انرژی از محیط پیرامون، برداشت شده، توسط مبدل انرژی به انرژی قابل ذخیره در باطری تبدیل میشود و در نهایت این انرژی برای اجرای عملیات سیستم تعبیه شده در اختیار آن قرار میگیرد. بنابراین اجزای یک سیستم تعبیه شده مبتنی بر برداشت انرژی عبارتند از:
برداشتگر انرژی : باتوجه به نوع انرژی محیطی، ابزارها و وسایلی برای دریافت این انرژی از محیط وجود دارند بعنوان مثال پنلهای خورشیدی در سیستمهایی که از انرژی خورشیدی استفاده میکنند. تفاوت اساسی در انواع برداشتگرهای انرژی، سطح توان خروجی(جریان، ولتاژ)، AC یا DC بودن و مدل امپدانس میباشد. بعنوان مثال آسیاب بادی، ژنراتورهای سیمپیچ مغناطیسی و فیزوالکتریک داری توان خروجی AC هستند درحالیکه انرژی خورشیدی و حرارتی دارای توان خروجی DC میباشند ]9[.
مبدل انرژی: ازآنجاییکه اکثر سیستمهای دیجیتال با توان DC راهاندازی میشوند و ممکن است برداشتگرهای انرژی، سطح توان متفاوتی داشته باشند، سیستمهای مبتنی بر برداشت انرژی نیازمند مبدلهایی هستند تا توان حاصل از برداشتگر را به توان مورد نیاز تبدیل کنند از اینرو دو نوع مبدل انرژی قابل استفاده است: مبدل AC_DC و مبدل DC_DC که برای تعیین سطح ولتاژ خروجی مناسب بکار میرود.
ذخیره ساز انرژی : ذخیره ساز انرژی در سیستمهای برداشتگر انرژی در حکم منبع انرژی نیستند و فقط برای ذخیره کردن انرژی مورد استفاده قرار میگیرند و میتواند باطری و یا خازن باشد که در سیستمهای امروزه بیشتر از باطری با قابلیت شارژ مجدد استفاده میشود.
سیستم تعبیه شده
مقدار انرژی که میتواند در ذخیره ساز انرژی ذخیره شود تحت تأثیر فاکتورهایی همچون کارایی مدل برداشتگر انرژی، ولتاژ ورودی/خروجی مبدلهای DC_DC ، وضعیت ذخیره سازهای انرژی و مشخصههای بار کاری سیستم، قرار دارد.
2-7-2 انواع سیستم برداشتگر انرژیدر حال حاضر بطور کلی دو نوع سیستم برداشت انرژی موجود است که در ادامه به اجمال به بررسی آنها میپردازیم.
روش اول :
328471717918PD (t)
00PD (t)
203766030342Pc (t)
00Pc (t)
88143514605PS (t)
00PS (t)
3805886192405سیستم تعبیه شده
00سیستم تعبیه شده
2583815178131ذخیره ساز انرژی
00ذخیره ساز انرژی
1409065633095شکل SEQ شکل * ARABIC 2-1 : نوع اول سیستم برداشتگر انرژیشکل SEQ شکل * ARABIC 2-1 : نوع اول سیستم برداشتگر انرژی1409396178435مبدل انرژی
00مبدل انرژی
206733170732برداشتگر انرژی
00برداشتگر انرژی

355061627305233837434290116014539039
شکل 2-1 : نوع اول سیستم برداشتگر انرژی]10[
101669851714501001458519050ابتدا انرژی با توان Ps(t) از محیط برداشت شده، توسط مبدل به انرژی قابل ذخیره در باطری تبدیل میشود سپس در باطری (ذخیره ساز انرژی) ذخیره میشود و درنهایت در اختیار پردازنده برای اجرای عملیات سیستم قرار میگیرد ]10[. معایب این نوع سیستم عبارتند از :
شارژ و دشارژ زیاد
اتلاف انرژی در صورت سرریز باطری
ازکار افتادن سیستم درصورت خرابی باطری
روش دوم :
در این روش انرژی مورد نیاز سیستم علاوه بر ذخیرهساز انرژی میتواند بطور مستقیم از طریق محیط نیز تأمین شود در اینصورت ظرفیت ذخیره ساز انرژی، کمتر و مراجعه به آن نیز کمتر از روش قبل است و پردازنده در صورت وجود انرژی کافی در محیط میتواند بدون اتلاف انرژی به سبب سربار شارژ/دشارژ باطری، به انرژی مورد نیازش دست یابد ]11[ .
42333013175PD (t)
00PD (t)
405517275949برداشتگر انرژی
00برداشتگر انرژی

-3156683225376Pc (t)
00Pc (t)
43462448890سیستم تعبیهشده
00سیستم تعبیهشده
74866543484PS (t)
00PS (t)
20116801136650034111108945مبدل انرژی
00مبدل انرژی
13437708945مبدل انرژی
00مبدل انرژی

103251014635440938451197112353310180036ذخیره ساز انرژی
00ذخیره ساز انرژی

19888201717263139440158419
شکل 2-2 : نوع دوم سیستم برداشتگر انرژی ]11[
معایب این نوع سیستم عبارتند از :
اتلاف انرژی در صورت سرریز باطری
شارژ و دشارژ زیاد باطری درصورت کمبود انرژی محیط
در یک سیستم مبتنی بر برداشت انرژی محیطی برای برآورده شدن کارایی کل سیستم باید پاره ای از مسائل مورد بررسی قرار گیرند :
شناخت منابع انرژی و انواع مبدل انرژی مربوطه: باتوجه به محیطی که سیستم تعبیهشده مورد استفاده قرار میگیرد باید نوع انرژی مناسب و مبدل متناسب با آن شناسایی شود.
مشخص کردن توان خروجی برداشتگر انرژی در شرایط مختلف (در حالت بهینه همواره سعی میشود که یک برداشتگر انرژی با بیشترین توان ممکن خود، انرژی را از محیط برداشت کند.)
ظرفیت ذخیره ساز انرژی (باطری، ابرخازن و…)
بررسی تمام اجزای سیستم تعبیهشده و محاسبه توان مورد نیاز در تمامی حالات
دقت پیشبینی انرژی در آینده : با توجه به اینکه رفتار سیستم برداشتگر انرژی بصورت پویا است و انرژی برداشت شده متغیری وابسته به زمان است و ثابت نیست و پیوستگی عملیات و سودمندی انرژی مصرفی برای اجرای آنها در یک سیستم تعبیه شده از اهمیت بالایی برخوردار است، طراحان یک سیستم تعبیه شده مبتنی بر برداشت انرژی برای نیل به این هدف خود، نیازمند این هستند که بطور دقیق نگرشی از موجودیت انرژی در آینده داشته باشند تا بتوانند براساس پیشبینی خود از انرژی در ساعات و روزهای آتی، ترتیب عملیات اجرایی خود را تنظیم کنند.
بیش از یک دهه است که سیستمهای تعبیه شده با قابلیت جمع آوری انرژی مورد توجه قرار گرفتهاند عاملهای اساسی در تحقیقات در این حوزه عبارتند از: 1- چگونگی مدیریت توان برای رسیدن به طول عمر بیشتر در وسایلی همچون موبایلها، نوت بوکها و… . 2- چگونگی طراحی یک زمانبند بیدرنگ با مصرف کارای انرژی]11[.
بعلاوه از آنجاییکه سیستمهای برداشتگر انرژی وابسته به زمان میباشند و میزان برداشت انرژی در هر لحظه قطعی نیست اولا این سیستمها برای سیستمهای بحرانی- امن(بعنوان مثال برخی از سیستمهای موجود در نیروگاه هستهای ) مناسب نیستند ثانیا سیستمهایی که از انرژی محیطی استفاده میکنند نیازمند روشی مناسب در مدیریت انرژی و توان میباشند تا بتوانند بصورت کارا از تکنیک برداشت انرژی استفاده کنند علاوهبر این، این سیستمها نیازمند منبع انرژی تکمیلی همچون باطری هستند تا در بازههایی از زمان که انرژی کافی نیست بتواند انرژی مورد نیاز سیستم را تأمین کند بنابراین از جمله چالشهای تحقیقات مدرن در این حوزه، تکنیکهای مدیریت توان خوب در کنار الگوریتمهای زمانبندی وظیفه مناسب برای سیستمهای برداشتگر انرژی میباشند. زمانیکه سیستم بیدرنگ باشد و وظایف لزوما باید قبل از سررسیدشان اجرا و خاتمه یابند، مسئله مدیریت توان و انرژی بسیار حائز اهمیت میشود چراکه درصورتیکه انرژی کافی در اختیار نباشد پردازنده هم نمیتواند در زمان مناسب وظیفه را اجرا کند بعبارتی در سیستمهای تعبیه شده بیدرنگ، تطابق انرژی مصرفی با الگوی تولید و برداشت انرژی و همینطور استفاده درست از منبع انرژی تکمیلی (ذخیره ساز انرژی) برای حداقل کردن هزینه و ضمانت رفتار بیدرنگ سیستم بسیار اساسی است. اکثر روشهایی که در این زمینه تمرکز دارند از تکنیک انتخاب پویای فرکانس/ولتاژ (DVFS) که در ادامه با جزئیات بیشتری بیان خواهد شد برای مدیریت توان و انرژی استفاده میکنند گرچه همانطور که در فصل بعد بیان خواهیم کرد اگر بتوان بجای و یا در کنار حداقل کردن مصرف انرژی، ترتیبی اتخاذ شود که میزان انرژی مصرفی سیستم متناسب با انرژی برداشت شده از محیط باشد در اینصورت عملکرد سیستم بسیار بهتر خواهد بود در این راستا الگوریتمها و روشهای متفاوتی ارائه شدند که هرکدام به نحوی سعی در بهبود مصرف انرژی و افزایش بهرهوری سیستم و در مجموع بالابردن کارایی سیستم داشتهاند در فصلهای بعد به اختصار به معرفی چند الگوریتم به همراه ذکر مزایا و معایب هریک خواهیم پرداخت.
باتوجه به مطالب گفته شده دو محدودیت اساسی برای سیستمهای تعبیهشده بیدرنگ مطرح است که اکثر روشهای موجود سعی در تأمین این دو محدودیت دارند ]12[:
محدودیت زمانی: این حالت زمانی است که سیستم برای اجرای وظیفه جاری، انرژی کافی در اختیار دارد اما زمان کافی برای اجرای آن نیست و درنهایت وظیفه بدلیل عدم وجود زمان کافی نمیتواند قبل از اتمام سررسیدش خاتمه یابد و اجرای آن ناتمام میماند.
محدودیت انرژی: در این حالت برخلاف محدودیت زمانی، زمان کافی برای اجرای وظیفه جاری، در اختیار پردازنده قرار دارد اما پردازنده بدلیل عدم وجود انرژی کافی و مورد نیاز وظیفه قادر به اجرا و خاتمه وظیفه نمیباشد و در نهایت اجرای وظیفه ناتمام میماند.
بنابراین طراحان سیستمهای تعبیهشده مبتنی بر برداشت انرژی، بدنبال روشی هستند تا بتواند زمانبندی وظایف را طوری انجام دهند که وظایف درعین اجرا و خاتمه در سررسید متناظرشان، انرژی مصرفی هریک و در مجموع انرژی مصرفی کل سیستم نیز بهبود یابد.
2-8 مدیریت توان در سیستمهای تعبیهشده
یک تفاوت اساسی در سیستمهای تعبیهشده، تفاوت در میزان توان مصرفی میباشد چراکه توان کمتر، سبب هزینه عملیات کمتر، نیاز به خنک سازی کمترو طول عمر بیشتر باطری میشود. افزایش فرکانس عملیاتی سیستم و یا استفاده از قدرت بیشتر مدارات مجتمع و یا هردو، سبب بهبود بازده و عملکرد سیستم میشود اما در عین حال این روشها موجب افزایش توان مصرفی نیز میشوند بنابراین طراحان سیستمهای تعبیه شده بدنبال روشی هستند تا بتوانند در عین کاهش توان، عملکرد سیستم را نیز بهبود بخشند بدین منظور دو روش پیشنهاد میشود]13[ : 1 ) مدیریت توان ایستا که استفاده از ابزارها و وسایل با توان ایستای پایین میباشند . 2) مدیریت توان پویا که در این روش، سطح توان در طول عملیات برطبق بار پردازشی سیستم کنترل میشود.
در سیستمهای دیجیتال مبتنی بر تکنولوژی CMOS ، مصرف توان سیستم از رابطه زیر بدست میآید:
P = c.v².f (6)
که c ظرفیت کل مدارهایی که در طول عبور سیگنال نیازمند شارژ هستند، v، ولتاژ و f، فرکانس کاری سیستم میباشد. همانطورکه در معادله 6 مشخص است، کاهش ولتاژ، فرکانس سیستم و یا هر دو میتواند موجب کاهش توان مصرفی سیستم شود و این اصل اساسی مدیریت توان پویا میباشد. در مدیریت توان پویا بدنبال دورههایی از زمان پردازش هستیم تا بتوانیم ولتاژ و یا فرکانس عملیاتی سیستم را کاهش دهیم (DVFS) درنتیجه میانگین توان مصرفی سیستم کاهش مییابد همچنین در طول این دورهها، بخشهای بیکار سیستم برای کاهش توان مصرفی بیشتر، خاموش میشوند]13[.
DVFS یک تکنیک رایج برای ذخیره توان در بسیاری از سیستمهای دیجیتال، سیستمهای تعبیهشده، لپتاپها و کامپیوترهای رومیزی است که موجب بهبود عملکرد سیستم نیز میشود. در بسیاری از زمانبندهای سیستم نیز از این تکنیک برای کاهش توان مصرفی و درنهایت بهبود انرژی مصرفی سیستم، استفاده میشود در این سیستمها پردازنده دارای N سطح فرکانسی مختلف است که هریک از این سطوح متناسب با وضعیت و نیازمندیهای وظیفه جاری برای اجرای آن اختصاص داده میشود. همانطور که گفته شد حالت بهینه برای سیستم، زمانی است که میزان انرژی مصرفی و انرژی برداشت شده از محیط با یکدیگر متناسب باشند که تکنیک انتخاب پویای فرکانس میتواند به این امر کمک کند. در این حالت فرکانس کاری پردازنده برای اجرای یک وظیفه، متناسب با توان برداشت انرژی، انتخاب میشود. البته با توجه به اینکه رفتار سیستم برداشتگر انرژی بصورت پویا است و اطلاع دقیقی از میزان انرژی در لحظات آتی نداریم در کنار تکنیک DVFS، باید از الگوریتم زمانبندی مناسبی نیز برای رسیدن به این هدف بهره ببریم در فصل بعد با جزئیات بیشتری به بررسی پردازنده با قابلیت انتخاب پویای فرکانس و ولتاژ و الگوریتمهای زمانبندی مربوطه خواهیم پرداخت.
2-9 نتیجهگیریدر فصلی که گذشت، تعاریف و مفاهیم اولیه در سیستمهای تعبیهشده، مشخصات و نیازمندیهای آن بیان شد. همچنین اهمیت و لزوم استفاده از سیستمهای برداشتگر انرژی درجهت افزایش طول عمر سیستمهای تعبیهشده نیز بیان شد. در فصل بعد به معرفی برخی کارهای انجام شده در زمینه زمانبندی سیستمهای تعبیهشده مبتنی بر برداشتگر انرژی خواهیم پرداخت.
630948-55403000
فصل سوم
فصل سوم : بررسی منابع و کارهای انجام شده3-1 مقدمهدر فصل قبل، مفاهیم اولیه در زمانبندی سیستمهای بیدرنگ تعبیهشده مبتنی بر برداشتگر انرژی را بیان کردیم، در ادامه در این فصل برخی روشها و الگوریتمها در این سیستمها را معرفی میکنیم. در ابتدا الگوریتمهایی که مبتنی بر باطری هستند بیان میشوند. و در ادامه، الگوریتمهاییکه متناسب با سیستمهای برداشتگر انرژی میباشند را معرفی و مقایسه میکنیم.
سیستمهای تعبیه شده مبتنی بر برداشتگر انرژی که از این به بعد در ادامه گزارش تنها با نام سیستم بیان میشود، شامل ترکیبی از اجزاء هستند که با یکدیگر در تعاملند و کارایی انرژی این سیستمها از جنبههای مختلف و در سطوح متفاوتی میتواند بهبود داده شود. بعنوان مثال زمانبندی و فرکانس/ولتاژ پردازنده تعبیه شده، باید بدقت، طوری انتخاب شود که کارایی عملکرد سیستم و همینطور محدودیتهای توان/انرژی سیستم، تأمین شود. درنهایت برای داشتن یک سیستم کارا و مناسب باید تمامی اجزای آن بدرستی و در تعامل مناسب با یکدیگر عمل کنند. از اینرو حوزههای تحقیقاتی بر روی چنین سیستمهایی میتواند شامل موارد زیر باشد :
مقالاتی که بر روی انرژی محیطی و حداکثر کردن کارایی برداشتگرهای انرژی ارائه میشوند.
کارهایی که در زمینه مبدلهای انرژی و افزایش بهبود عملکرد ساختاری و مدارات یک مبدل انرژی در جهت کاهش هرچه بیشتر اتلاف انرژی در زمان تبدیل و بطورکلی افزایش کارایی انواع مبدل انرژی ارائه میشوند.
برخی از نویسندگان و محققان در زمینه ذخیرهساز انرژی و زمانبندی ذخیره و یا دریافت انرژی به/ از ذخیرهساز انرژی کار میکنند و سعی در ارائه روشی برای کارایی هرچه بیشتر این واحد از سیستم تعبیهشده دارند. این قسمت در فصل 4 با جزئیات بیشتری بیان خواهد شد.
بهبود عملکرد خود سیستم تعبیهشده، حوزه دیگری است که نظر بسیاری از طراحان را به خود جلب کرده است. در این میان، بحث زمانبندی وظایف بسیار حائز اهمیت است چراکه درصورت عدم وجود یک زمانبند مناسب برای اجرای عملیات سیستم، سیستم قادر به اجرای صحیح عملیاتش نخواهد بود. در این پایان نامه، ما نیز بر روی زمانبندی وظایف تمرکز میکنیم.
بطورکلی منابعی که بر روی زمانبندی وظایف یک سیستم تعبیهشده بیدرنگ ارائه شدهاند به دو دسته قابل تقسیماند:
روش تحلیلی : در این روش محققان، بصورت تحلیلی و اثبات روابط ریاضی، سعی در نشان دادن بهبود عملکرد سیستم پیشنهادی شان را دارند. در روش تحلیلی ابتدا محققان مدل پیشنهادی خود را در قالب یک مدل ریاضی، معرفی کرده و با استفاده از روابط ریاضی، کارایی مدل پیشنهادی را اثبات میکنند.
روش الگوریتمیک و مبتنی بر شبیهسازی : در این روش محققان، بصورت توصیف مسئله و الگوریتمیک و در قالب شبیهسازی و یا بصورت جامعتر بوسیله پیادهسازی بر روی سیستمهای واقعی، کارایی روش خود را نشان میدهند. روش پیشنهادی در این پروژه نیز بر پایه این روش میباشد.

این نوشته در مقالات ارسال شده است. افزودن پیوند یکتا به علاقه‌مندی‌ها.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *