پایان نامه رایگان درمورد انرژی مصرفی، الگوریتم زمانبندی، مصرف انرژی

(20)

که در آن f_(t_i ) زمان پایان یافتن وظیفه شماره i و d_i سررسید مطلق آن می‌باشد.شکل 3-12 بلوک دیاگرام مدل این سیستم را نشان می‌دهد.

شکل 3-12 مدل سیستم مرجع ]36[
شکل 15شکل 3-12 مدل سیستم مرجع [36]
الگوریتم پیشنهادی در این مقاله از سه بخش اصلی متفاوت تشکیل می‌شود که عبارت‌انداز:
الگوریتم M-EDF 145
الگوریتم ED3VFS 146
الگوریتم TLDHLB 147
الگوریتم M-EDF برای زمانبندی وظایفی است که به یکی از هسته‌های پردازنده، توزیع شده است. الگوریتم ED3VFS ، نسخه پیشرفته الگوریتم D3VFS 148 است و برای تنظیم مد عملیاتی روی هرهسته پردازنده استفاده می‌شود. در نهایت نیز الگوریتم TLDHLB برای توزیع وظایف بین هسته‌ها استفاده می‌شود ودارای دو سطح می‌باشد:
سطح اول دارای یک استراتژی بارگذاری غیرتعادلی می‌باشد
سطح دوم دارای یک استراتژی بارگذاری تعادلی می‌باشد
برای مثال وقتی، یک وظیفه جدید که نیاز دارد تا توسط یک هسته سرویس داده شود، از راه برسد، الگوریتم TLDHLB آن را با درنظر گرفتن تعادل بارگذاری، به یک هسته مناسب توزیع می‌کند. بعداز اینکه هسته، وظیفه را دریافت کرد، الگوریتم M-EDF ، این وظیفه جدید را زمانبندی می‌کند، همزمان با آن الگوریتم ED3VFS نیز روی این هسته به صورت دوره‌ای اجرا خواهد شد تا انرژی مصرفی را کاهش دهد.

الگوريتم M-EDF :
الگوریتم زمانبندی اصلی که در هسته سیستم عامل میکروسی‌2 149 استفاده شده، یک الگوریتم زمانبندی براساس اولویت بنیادی است. برای اینکه هم وظایف بی‌درنگ و هم وظایف معمولی را همزمان پوشش دهد، الگوریتم M-EDF به عنوان جایگزینی برای الگوریتم EDF انتخاب شده است. در واقع M-EDF ترکیبی از EDF و زمانبندی اولویت ثابت150 می‌باشد. برای وظایف بی‌درنگ از الگوریتم EDF استفاده شده است. هنگامی که دو یا چند وظیفه بی‌درنگ دارای سررسید برابری باشند یا برای وظایف معمولی، M-EDF از الگوریتم زمانبندی اولویت ثابت برای مشخص کردن ترتیب اجرای وظایف استفاده می‌کند.
در واقع اگر همزمان یک وظیفه بی‌درنگ و یک وظیفه معمولی در صف آماده باشند، M-EDF وظیفه بی‌درنگ را برای اجرا انتخاب می‌کند. برای مشارکت و همکاری کردن با الگوریتم TLDHLB برای ذخیره توان ایستا، در اینجا M-EDF طوری تغییر داده شده است که وقتی یک وظیفه دارای بالاترین اولویت، در حالت بیکار باشد و هیچ وظیفه دیگری برای اجرا نباشد، بتواند هسته پردازنده را خاموش کند. یعنی وقتی هسته پردازنده، همه وظایف را به اتمام رساند، خودش را خاموش خواهدکرد تا انرژی کمتری مصرف شود.
الگوريتم ED3VFS :
این الگوریتم برای تنظیم کردن فرکانس و ولتاژ پردازنده، به صورت پویا استفاده می‌شود. در این الگوریتم دو پارامتر با نام‌های α و β وجود دارند که این دو پارامتر در الگوریتم D3VFS به صورت پیش‌فرض روی عدد 10 تنظیم می‌شوند و به صورت زیر تعریف می‌شوند:
α : هرگاه وظیفه‌ای به اندازه α واحد زمانی اجرایش طول کشید ولی تمام نشد و همچنان پردازنده در حال اجرای آن بود، الگوریتم D3VFS اجرا می‌شود تا فرکانس و ولتاژ را بالاتر ببرد و سرعت سیستم زیاد شود تا بهره‌وری بیشتر شود( ولی مصرف انرژی نیز افزایش می‌یابد)
β : هرگاه به اندازه β واحد زمانی، هیچ وظیفه‌ای، سررسیدش را از دست ندهد، آنگاه این الگوریتم اجرا می‌شود تا فرکانس و ولتاژ را کم کند تا انرژی مصرفی کاهش یابد. ( β بزرگتر باعث افزایش انرژی مصرفی و افزایش سرعت می‌شود)
در این مقاله با الهام بخشیدن از D3VFS ، یک روش بهتری برای تنظیم پارامترهای α و β ، پیشنهاد شده است تا بتواند کارایی سیستم زمانبندی را بهبود دهد. سه اشکال موجود در D3VFS عبارت انداز:
در D3VFS ، سررسید مربوط به وظایف، نیازی ندارد که بیشتر از 10 یا یک مقدار آستانه ثابتی باشد. هنگامی که کوتاه‌ترین سررسید کمتر از 10 باشد، α و β منفی می‌شوند، که باید اصلاح شود.
لزومی ندارد که α و β حتما باهم برابر باشند، زیرا اثرات آن‌ها باهم متفاوت است. در الگوریتم ED3VFS ، مقدار α بزرگتر درنظر گرفته شده تا زمان بیشتری پردازنده در سرعت پایین بماند، زیرا سیستم در سرعت‌های آهسته‌تر، فرکانس عملیاتی را افزایش خواهد داد. این باعث می‌شود تا مقدار توان ذخیره شده بیشتر شود (یعنی هرچقدر بتوانیم سرعت سیستم را آهسته نگه داریم، انرژی بیشتری را ذخیره کرده‌ایم). از سوی دیگر β برای کاهش فرکانس عملیاتی استفاده می‌شود، هرچقدر β بزرگتر باشد، باعث می‌شود که سیستم برای مدت طولانی در سرعت بالا بماند، بنابراین باعث می‌شود که بهره‌وری بهتر شود اما توان بیشتری را مصرف می‌کند.
معمولاً در یک سیستم بیشتر از یک وظیفه همزمان در حال کار هستند و در محیط‌های واقعی این وظایف همیشه شبیه هم نیستند. بهترین تنظیمات برای هر وظیفه این است که متفاوت باشد، بنابراین دادن تنظیمات متفاوت برای مجموعه وظایف متفاوت انعطاف‌پذیرتر است.
برای حل این مشکلات بالا، در این مقاله یک روش متفاوتی برای بهبود کارایی و بهترشدن الگوریتم ذخیره توان پیشنهاد شده است. شبه کد این الگوریتم در شکل 3-13 نشان داده شده است.
ایده اصلی الگوریتم ED3VFS این است که تنظیمات α و β آزادانه تغییر داده می‌شود، در واقع با تغییر مجموعه وظایف، این دو پارامتر، دو مقدار متفاوت دارند.
در الگوریتم ED3VFS ، پارامترهای α و β به صورت زیر مقداردهی می‌شوند:
β={█((0.2D_sr)¦(0.4D_sr )@(0.6D_sr)¦(0.8D_sr ))┤ (21)
α=D_sr-β (22)
که در آن D_sr عبارت انداز کوتاه‌‌ترین سررسید مربوط به وظیفه‌ها.
همانطور که مشاهده می‌کنید در اینجا اثر α و β ، عکس هم درنظر گرفته شده است. نتایج آزمایشات مقایسه بین ED3VFS و D3VFS نشان داد که انرژی مصرفی ED3VFS در β=0.2D_sr ,0.6D_sr ,0.8D_sr کمتر از D3VFS بوده است. همچنین از دست دادن سررسیدها نیز در β=0.2D_sr ,0.4D_sr ، صفر بوده است، یعنی هیچ سررسیدی از دست نرفته است. در β=0.6D_sr نیز کمتر از D3VFS، سررسید از دست داده شد، یعنی با این تنظیمات جدید در ED3VFS، هم انرژی کمتر و هم بهره‌وری بیشتر( از دست دادن سررسید کمتر) اتفاق افتاده است.
بهترین حالتی که هم انرژی کمتری مصرف شده و هم سررسید کمتری از دست برود به این صورت شد که اگر وظایف ما بی‌درنگ سخت باشد:
β= 0.2Dsr , α= 0.8Dsr (23)
و اگر بی‌درنگ نرم باشد :
β= 0.6Dsr , α= 0.4Dsr (24)

(1) Initially setting the power mode of DSP to default level fd .
(2) Every timer interrupt occur
(3) if (There is any real time task)
(4) Setting α = Dsr × 0.2
(5) Setting β = Dsr – α
(6) if (Deadline missed)
(7) Extending deadline of the task that missed deadline for de ticks.
(8) Rising power mode.
(9) else if (Utilization of DSP Sr for α ticks)
(10) Rising power mode
(11) else if (There is no deadline missed for β ticks)
(12) Falling power mode
(13) else
(14) setting the power mode of DSP to deadline level fd
(15) endif

الگوريتم TLDHLB : شکل 16شکل 3-13 شبه کد الگوریتم ED3VFS [36]
برای سیستم‌هایی که دارای محدودیت توان باطری هستند، این ایده که اجازه دهیم همه‌ هسته‌های پردازنده همواره در حالت فعال باشند، ایده خوبی نیست، زیرا باعث می‌شود انرژی زیادی مصرف شود. در یک سیستم چندهسته‌ای، متعادل کردن حجم‌کار بین هسته‌‌ها، می‌تواند زمان اتمام کل همه وظایف را کاهش دهد، یعنی هسته‌های پردازنده می‌توانند برای مدت بیشتری به حالت خواب151 بروند و انرژی بیشتری را ذخیره کنند.
در سطح اول این الگوریتم دو سطحی، از یک استراتژی بارگذاری غیرتعادلی برای ذخیره توان ایستا استفاده شده است. ایده اصلی در این استراتژی توزیع بار، عبارت انداز:
توزیع وظایف به هسته‌هایی از پردازنده که در حالت فعال هستند و خاموش کردن هسته‌ها، وقتی که همه وظایف موجود در صف آن هسته به اتمام برسند.
برای مثال فرض کنید یک واحد پردازنده مدیر داریم و دو هسته تحت نظر آن قرار دارند. همانطور که در شکل 3-14 مشاهده می‌شود، در ابتدا که هیچ وظیفه‌ای وجود ندارد، هر دو هسته خاموش هستند. وقتی وظیفه T1 آزاد می‌شود، پردازنده مدیر وضعیت هسته‌ها را چک می‌کند، اگر هیچ کدام از هسته‌ها در حالت فعال نبودند، هسته شماره 1 را روشن می‌کند و T1 را به آن اختصاص می‌دهد. براساس ED3VFS، هسته شماره 1 ، در سرعت پیش فرض کار خواهد کرد که معمولا در کمترین سرعت خود قرار دارد. در ادامه که چند وظیفه دیگر که به سیستم اضافه می‌شود، پردازنده مدیر آنها را به هسته‌ای می‌فرستد که فعال باشد و در بالاترین فرکانس خود نباشد. پس از مدتی که سرعت هسته شماره 1 به حداکثر خود رسید، حال اگر Tn آزاد شود، پردازنده مدیر آن را به هسته شماره 2 که خاموش بوده ارسال می‌کند. وقتی که هسته شماره 1 تمام وظایف خود را به پایان رساند، این هسته خودش را به وسیله الگوریتم MEDF، خاموش می‌کند.

شکل 3-14 مثالی از بارگذاری غیرتعادلی – a : حالت آغازین –b : وظیفه t1 آزاد شده و هسته 1 شده است- c : زمانی که هسته 1 در حالت حداکثر فرکانس کار می‌کند،وظیفهn آزاد شده و در نتیجه هسته2 روشن شده و وظیفهn به آن اختصاص میابد – d : هسته 1 اجرای همه وظایفی که به آن اختصاص داده شده بود را تمام می‌کند و خودش را خاموش می‌کند. ]36[
شکل 17شکل 3-14 مثالی از بارگذاری غیرتعادلی
در لایه دوم این الگوریتم، یک استراتژی بارگذاری تعادلی وجود دارد. وقتی که دو یا چند هسته در حال کار در حالت فعال باشند، استراتژی بارگذاری تعادلی در سطح دوم، وظایف جدید آزادشده را توزیع خواهد کرد. برخلاف روش‌های سنتی که شامل وظایف بی‌درنگ نمی‌شدند، در این سیستم به صورت همزمان هم وظایف معمولی و هم وظایف بی‌درنگ در نظر گرفته شده است. استراتژی بارگذاری سنتی، برای سیستم‌های بی‌درنگ طراحی نشده است، بنابراین در این مقاله یک معیار توزیع جدیدی پیشنهاد شده که مشکل توزیع وظایف بی‌درنگ را حل می‌کند.
این استراتژی جدید، از سررسید وظایف به عنوان یک معیار برای بارگذاری تعادلی استفاده می‌کند. هرچقدر بتوانیم وظایف را بر اساس سررسیدشان، یکنواخت‌تر توزیع کنیم، احتمال از دست دادن سررسید کمتری خواهیم داشت. شکل3-15 یک مثال ساده از این موضوع است که در آن دو هسته و چهار وظیفه وجود دارند. این مثال نشان می‌دهد که نتیجه یکی از دو توزیع وظایف، به شکست منجر می شود. در شکل 3-15 الف ، وظیفه1 در سررسید d1 به اتمام می‌رسد، بنابراین برای اجرای وظیفه 2 به اندازه کافی زمان وجود ندارد و در نتیجه سررسید آن از دست میرود. برای وظیفه 4 نیز در هسته 2 ، همین شرایط وجود دارد. در شکل 3-15 ب ، از یک توزیع متفاوتی استفاده شده است که نتیجه آن اجرای به موقع وظایف و از دست نرفتن سررسیدهای آنان می‌باشد. در این حالت، برش زمانی152 بین دو سررسید، طولانی‌تر است که این بدین معنی است که زمان بیشتری برای اجرای وظیفه بعدی وجود دارد، در نتیجه احتمال از دست رفتن سررسید کاهش می‌یابد.

شکل3-15 مثالی از توزیع وظایف بی‌درنگ؛ الف) توزیع ناجور وظایف؛ ب) توزیع مناسب وظایف ]36[
شکل 18شکل3-15 مثالی از توزیع وظایف