دانلود متن کامل پایان نامه در سایت jemo.ir موجود است

>
در این الگوریتم، بصورت همزمان محدودیتهای زمانی و انرژی را بررسی میکنیم، چراکه در بررسی جداگانه علاوه بر زمان اجرای بالاتر الگوریتم، برخی نواقص نیز بوجود میآید. بعنوان مثال اگر قبل از بررسی موجودیت انرژی برای اجرای یک وظیفه، فقط با درنظر گرفتن مهلت زمانی آن، زمان شروع و خاتمه آن محاسبه شود، ممکن است در این زمان، انرژی کافی برای اجرای وظیفه موجود نباشد، درنتیجه پردازنده قادر به اجرای آن نخواهد بود و در حالت دیگر اگر قبل از بررسی مهلت زمانی اجرای وظیفه، اجرای آن را تا زمان کافی بودن انرژی، به تأخیر بیاندازیم، ممکن است این تأخیر، سبب نقض سررسید وظیفه شود. بنابراین قبل از اجرای یک وظیفه، بررسی چند مسئله حائز اهمیت است:
مهلت زمانی اجرای وظیفه
انرژی مورد نیاز برای اجرای وظیفه
موجودیت انرژی (در محیط و در واحد ذخیرهسازی)
انتخاب فرکانس مناسب پردازنده برای اجرای وظیفه
یک الگوریتم مناسب، باید قبل از خاتمه زمان سررسید مطلق یک وظیفه (Dm) که از جمع زمان ورود (am) و سررسید متناظر وظیفه(dm)، حاصل میشود، وظیفه جاری را اجرا و خاتمه دهد. بعنوان مثال اگر وظیفهای با زمان سررسید 2، در زمان 3 وارد سیستم شده باشد، پردازنده باید تا قبل از زمان 5 اجرای آن را به اتمام برساند. اطلاعات مهلت زمانی و انرژی مورد نیاز برای اجرای یک وظیفه از مشخصههای یک وظیفه، قابل استخراج است. قبل از بررسی موجودیت انرژی، الگوریتم، در ابتدا پایینترین فرکانس ممکن برای اجرای یک وظیفه را محاسبه میکند. درصورتیکه همانند مراجع ]10[، ]11[، ]17[، ]18[ و ]19[، فاکتور کاهش سرعت Sn = fn / fmax را به ازای هر وظیفه، تعریف کنیم و درصورتیکه wn، بدترین حالت زمان اجرای وظیفه متناظر باشد، از رابطه ، میتوان کمترین فرکانس ممکن برای اجرای وظیفه τm را محاسبه کرد. در این رابطه نیز منظور از ، سررسید متناظر است نه سررسید مطلق. بنابراین خواهیم داشت:
(45)
بعد از تعیین flow ، وظیفه، توسط هر فرکانسی بین flow , fmax ، میتواند اجرا شود (fmax بیشترین فرکانس پردازنده میباشد). درصورتیکه وظیفه در پایین ترین فرکانس اجرا شود ، زمان اجرایش طولانی شده و این میتواند سبب نقض سررسید مابقی وظایف موجود شود و از طرفی درصورتیکه در بالاترین فرکانس اجرا شود، انرژی زیادی مصرف کرده و این نیز ممکن است سبب نقض سررسید در مابقی وظایف، بدلیل کمبود انرژی شود. بنابراین انتخاب فرکانس مناسب برای اجرای وظایف از اهمیت بالایی برخوردار است. پارامتر مهمی که در انتخاب فرکانس مناسب برای اجرای وظیفه دخالت دارد، موجودیت انرژی است که با توجه به مزایا و معایب المانهای ذخیرهسازی که در ابتدای فصل بیان کردیم، الگوریتم مناسب، الگوریتمی است که تصمیمات زمانبندی و انتخاب فرکانس را طوری اتخاذ کند که تاحد ممکن انرژی مورد نیاز برای اجرای وظیفه، از محیط، برداشت شده و تعداد رجوع به ذخیرهساز انرژی، حداقل شود. بنابراین برای رسیدن به این مهم در روش پیشنهادی برخلاف روشهای قبلی، موجودیت انرژی را بجای بررسی در یک نقطه از زمان، در یک فاصله زمانی بررسی کرده و میزان انرژی مورد نیاز برای اجرای وظایفی که در این بازه نیز وارد سیستم میشوند، محاسبه میکنیم. درنهایت توسط مقایسه این دو مقدار، تصمیمات زمانبندی، اتخاذ خواهد شد. البته در حالت کلی، زمانی یک وظیفه، اجازه اجرا دارد، که انرژی کافی برای اجرای وظایف موجود در بازه انتخابی، موجود باشد. مزیت بررسی وظایف و موجودیت انرژی در بازه، در این است که، علاوه بر اینکه از وجود انرژی کافی برای نه تنها یک وظیفه، بلکه برای چند وظیفه پیاپی در صف آماده، اطمینان حاصل کرده و سپس تصمیمات زمانبندی لحاظ میشود، تأثیرات اجرای یک وظیفه برروی سایر وظایف، هم از دید زمان و هم انرژی، نیز بررسی شده و الگوریتم قادر به تصمیمگیری بهتری خواهد بود. بعلاوه زمانیکه نیاز به بهروز کردن زمانهای اجرا و خاتمه برای سایر وظایف هستیم، برخلاف روش بکار رفته در ]19[که این تغییرات را در کل وظایف اعمال میکرد و درنتیجه زمان اجرای الگوریتم بسیار بالا میرفت، در این روش فقط تغییرات برروی وظایف موجود در بازه اعمال میشود و از آنجاییکه انتخاب بازه بصورت پویا رخ میدهد، تأثیر این تغییرات میتواند در زمان اجرای کمتری برروی سایر وظایف نیز اعمال شود. بنابراین با 3 مسئله مواجه هستیم :
انتخاب بازه زمانی برای بررسی انرژی
محاسبه انرژی مورد نیاز برای اجرای وظایف موجود دراین بازه
محاسبه موجودیت انرژی در واحد ذخیرهسازی (شامل باطری و ابرخازن) و انرژی محیطی
4-4-1 انتخاب بازه زمانی
نکته مهم در انتخاب بازه زمانی مناسب برای بررسی موجودیت انرژی و انرژی مورد نیاز وظایف در آن بازه، طول بازه میباشد. چراکه در صورت بزرگ بودن بازه، تعداد وظایف وارد شده به سیستم در این فاصله، زیاد میشود. در نتیجه انرژی مورد نیاز این وظایف نیز، مقدار بیشتری است بنابراین در این بازه بزرگ، موجودیت انرژی نیز باید، حداقل به اندازه انرژی مورد نیاز باشد. در بدترین حالت یعنی در زمان کاهش و یا عدم وجود انرژی محیطی، ظرفیت ذخیرهساز انرژی باید به اندازه انرژی مورد نیاز باشد، پس نیازمند ظرفیت ذخیرهسازی بالایی خواهیم بود. اما درصورت کوچک بودن بازه، درست است که نسبت به حالت قبل، ظرفیت ذخیرهسازی، کمتر خواهد بود، اما در اینحالت درصو
رتیکه وظایف موجود در بازه انرژی کمتری نیز نیاز داشته باشند، به موجودیت انرژی کمتری نیز نیاز خواهیم داشت درنتیجه الگوریتم براساس یک مقدار کمی از انرژی، در مورد زمان اجرا و فرکانس اجرایی تصمیمگیری میکند. حال با توجه به اینکه زمان ورود وظایف غیرتناوبی از قبل مشخص نیست، اگر در حین اجرای یک وظیفه، یک وظایفه غیرتناوبی با انرژی مطالبه شده بالا و سررسید کمتر از وظیفه جاری، وارد سیستم شود باتوجه به انحصاری بودن سیستم، پردازنده باید وظیفه تازه وارد را اجرا کند که باتوجه به کم بودن موجودیت انرژی، بالا بودن مقدار انرژی مورد نیاز برای اجرای وظیفه و نزدیک بودن سررسید وظیفه، با احتمال بسیار بالایی وظیفه از سیستم بدلیل نقض سررسید، حذف خواهد شد و این برای یک سیستم تعبیهشده بیدرنگ، نقص محسوب میشود. درنتیجه انتخاب بازه کوچک هم عمل مناسبی نیست. در این راستا بازهای که انتخاب میکنیم براساس سررسید مطلق وظایف موجود در صف آماده میباشد. بعبارتی زمان ابتدای بازه زمان جاری سیستم، tc ، و زمان انتهای بازه، سررسید مطلق وظیفه جاری، میباشد یعنی [tc , Dm]. واضح است که این فاصله به ازای هر تغییری در وظیفه موجود در ابتدای صف آماده، به روز میشود.
4-4-2 محاسبه انرژی مورد نیاز برای اجرای وظایف موجود در بازه
بعد از محاسبه بازه مورد نظر، باید وظایفی را که در این بازه وارد سیستم میشوند، شناسایی کنیم. این وظایف به 3 دسته قابل تقسیماند:
وظایفی که در بازه [tc , Dm] ، وارد سیستم شده و باید در همین بازه نیز اجرا و خاتمه یابند.
وظایفی که در (tc , Dm]، وارد سیستم شده و در همین بازه هم شروع به اجرا خواهند شد، اما زمان خاتمه آنها در این بازه نمیباشد. بعبارتی دارای سررسید بیشتری نسبت به سایر وظایف میباشند.