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

بی‌درنگ
در این ایده، از پارامتر واریانس سررسید هر وظیفه، به عنوان یک معیار برای توزیع سررسید استفاده شده‌ است. از آنجایی که واریانس، چگونگی توزیع یک مجموعه از اعداد را شرح می‌دهد، در نتیجه واریانس می‌تواند به عنوان بیان کننده تراکم توزیع داده‌ها استفاده شود.
یک واریانس کوچک از سررسید یک وظیفه، نشان می‌دهد که فاصله زمانی بین دو سررسید، کوتاه است. معادله زیر فرمول محاسبه واریانس را نشان می‌دهد:
Var(x)=1/N ∑_(i=1)^N▒〖(x_i-x ̅)〗^2 (25)
که در آن N تعداد داده‌ها، x_i ، داده شماره i و x ̅ میانگین داده‌هاست.
غیراز این توزیع وظایف براساس سررسید، از سه استراتژی دیگر نیز برای توزیع وظایف معمولی، استفاده شده است. این سه استراتژی همچنین برای وظایف بی‌درنگی که یکنواختی توزیع سررسیدشان باهم برابر است نیز استفاده می‌شود.
استراتژی اول، به ترتیب اجرای وظایف در هر هسته مربوط می‌شود، به این معنی که، توزیع کننده، یک وظیفه را به هسته‌ای می‌فرستد که بالاترین اولویت را به آن وظیفه بدهد. برای مثال فرض کنید که دو هسته و دو وظیفه روی هر هسته داشته باشیم. حال وقتی یک وظیفه جدید آزاد می‌شود، اگر اولویت اجرای این وظیفه، در هسته شماره 1، دومین باشد (یعنی اگر این وظیفه را به هسته اول بفرستیم، زمانبندی که هسته اول با توجه به وظایف موجود در صف خود، انجام می‌دهد، به این صورت می‌باشد که این وظیفه، دومین وظیفه‌ برای اجرا است) و در هسته شماره 2، سومین اولویت را داشته باشد، این وظیفه به هسته اول فرستاده می‌شود.
دومین استراتژی، به تعداد وظایف موجود در صف هر هسته توجه می‌کند. به این معنی که توزیع‌کننده، وظیفه جدید را به هسته‌ای می‌فرستد که کمترین تعداد وظیفه در آن باشد.
وقتی توزیع‌کننده نتوانست با این استراتژی‌ها، تصمیم بگیرد که وظیفه را به کدام هسته بفرستد، آنگاه از آخرین استراتژی استفاده خواهد شد. این استراتژی بسیار ساده می‌باشد، به این صورت که ، توزیع‌کننده هسته‌ای را انتخاب می‌کند که شماره سریال کوچکتری داشته باشد و همچنین در حالت فعال قرار داشته باشد. شبه کد این الگوریتم را به صورت کامل در شکل 3-16 مشاهده می‌کنید.
همانطور که در این شبه‌کد مشاهده می‌کنید، پس از بررسی وضعیت هسته‌ها توسط پردازنده مدیر، در سطح اول الگوریتم توزیع ابتدا بررسی می شود که اگر همه هسته‌ها خاموش بودند، هسته‌ای که شماره سریال کمتری دارد، وظیفه به آن اختصاص میابد. در غیر این صورت اگر چند هسته روشن و در حداکثر فرکانس درحال کار بودند و چند هسته خاموش بودند، آنگاه یکی از هسته‌های خاموش انتخاب شده و وظیفه به آن اختصاص می یابد. اگر همه هسته‌ها روشن باشند و یکی از هسته‌های روشن در حداکثر فرکانس خود کار نکند، وظیفه به آن ارسال می‌شود، اما اگر هیچ‌کدام از حالت‌های ذکر شده برقرار نشد، وارد سطح دوم الگوریتم شده و هسته‌ای که واریانس سررسید آن کمتر باشد توسط تابع maxuniformity() انتخاب می‌شود، و اگر حداقل دو هسته واریانس سررسید برابری داشتند، توسط تابع minorder() هسته‌ای انتخاب می‌شود که اگر وظیفه در صف آن قرار گیرد، زودتر اجرا می شود. اگر باز هم دو هسته وجود داشتند که شرایط یکسانی داشتند، تابع mintaskNum() وظایف را به هسته‌ای کمترین تعداد وظایف را در صف خود دارد می‌فرستد. اگر دو صف با تعداد وظایف برابر وجود داشت، توسط تابع minSerial() وظیفه به هسته‌ای که شماره سریال کمتری دارد ارسال می شود.
مزايا و معايب اين الگوريتم:
این الگوریتم یکی از بهترین الگوریتم‌های توزیع وظایف در سیستم‌های چندهسته‌ای می‌باشد که با یک توزیع بار حساب شده بین هسته‌ها، توانسته نرخ نقض سررسید وظایف را بخوبی کاهش داده و همچنین بهره‌وری و کارایی سیستم را بسیار بهبود ببخشد. همچنین با یک الگوریتم تنظیم ولتاژ و فرکانس سررسید محور مناسب، توانسته انرژی مصرفی را با در نظرگرفتن سررسید وظایف، تا حد زیادی کاهش دهد.
از جمله معایب این الگوریتم، که ما آن‌ها را در الگوریتم پیشنهادی خود بهبود داده‌ایم این است که این الگوریتم، بدون توجه نوع وظایف بی‌درنگ و ماهیت آن‌ها، آن‌ها را بین هسته‌ها توزیع کرده است که این مسئله تا حد زیادی می‌تواند روی انرژی مصرفی سیستم و همچنین زمان پاسخ وظایف، تاثیر منفی بگذارد. در واقع این الگوریتم هیچ تمایزی از لحاظ تناوبی و غیرتناوبی بودن وظایف بی‌درنگ، قائل نیست و این مسئله می‌تواند زمان پاسخ وظایف غیرتناوبی را افزایش دهد. همچنین عیب دیگر این الگوریتم، بالا بودن پیچیدگی و محاسبات زیاد آن، برای توزیع و زمانبندی اجرای وظایف است و همچنین الگوریتم تنظیم فرکانس و ولتاژ سررسید محور آن، دارای دو پارامتر کنترل‌کننده است که این موضوع باعث سوئیچ زیاد بین سطوح مختلف فرکانسی پردازنده خواهد شد وسربار الگوریتم را نیز افزایش می‌دهد.

(1) Initialy turning off all of DSP’s , DSPoff = DSPall
(2) When a task that need be processd by DSP is released
(3) Getstatus(DSPall)
(4) % First level for load unbalance %
(5) if (DSPoff == DSPall)
(6) DSPt = minserial (DSPoff)
(7) Turn on minserial (DSPoff)
(8) else if (DSPfs == DSPon)
(9) if (DSPon == DSPall)
(10) go to line 21
(11) else
(12) DSPt = minserial (DSPoff)
(13) Turn on minserial (DSPoff)
(14) else if (Num(DSPon – DSPfs)==1)
(15) DSPt = DSPon – DSPfs
(16) else
(17) go to line 21
(18) Dispatch the task to DSPt.
(19) end
(20) % Second level for load balance%
(21) if (Num(maxUniformity(DSPon))==1)
(22) DSPt = maxUniformity(DSPon)
(23) else if (Num(minOrder(DSPon))==1)
(24) DSPt = minOrder(DSPon)
(25) else if (Num(minTask(DSPon))==1)
(26) DSPt = minTask(DSPon)
(27) else
(28) DSPt = minserial(DSPon)
(29) Dispatch the task to DSPt.
(30) End.شکل 19شکل 3-16 شبه کد الگوریتم توزیع وظایف TLDHLB [36]

3-6-4 الگوريتم زمانبندی پيشنهادی در مرجع ]37[
در این مقاله، یک الگوریتم زمانبندی بیدرنگ برای مجموعه وظایف ترکیبی برروی مدل چند هستهای همگن، ارائه شده است. وظایف تناوبی براساس سیاست EDF، جزءبندی شده و زمانبندی میشوند. وظایف غیرتناوبی نیز بصورت سراسری به هستههای مختلف، تخصیص داده میشوند. در ادامه به جزئیات الگوریتم میپردازیم.
سیستم بکار رفته در این مقاله، دارای m، هسته پردازشی همگن p={p1 , p2 ,… , pm} میباشدوظایف سیستم نیز شامل ترکیبی از وظایف تناوبی و غیرتناوبی است. مجموعه وظایف تناوبی T={T1 , T2, … , Tn}، شامل n وظیفه تناوبی انحصاری و مستقل است و مجموعه وظایف غیرتناوبی A={A1 ,A2 , …, Ak} شامل k وظیفه غیرتناوبی انحصاری میباشد. هر وظیفه تناوبی توسط 4 مشخصه Ai , Ci , Pi , Di که به ترتیب بیانگر زمان ورود وظیفه، بدترین حالت زمان اجرا، دوره تناوب وظیفه و سررسید متناظر آن میباشد شناسایی میشوند. در این مدل دوره تناوب وظایف، برابر با سررسید متناظرشان درنظر گرفته شده است. وظایف غیرتناوبی نیز شامل دو مشخصه Ei و Ai که به ترتیب بیانگر زمان ورود و بدترین حالت زمان اجرا است میباشد. بهرهوری وظیفه تناوبی Ti بصورت Ui=Ci/Pi تعریف میشود و جمع بهرهوری تمامی وظایف تناوبی بصورت بهرهوری کل هر هسته درنظر گرفته میشود. از آنجاییکه بیشترین مقدار بهرهوری هر هسته، یک میتواند باشد از اینرو برای بهرهوری کل سیستم داریم : Um که m، تعداد هستههای پردازنده است.
الگوریتم پیشنهادی شامل نظریه جزءبندی برای وظایف تناوبی و تخصیص سراسری برای وظایف غیرتناوبی است. که نمادهای بکار رفته در این الگوریتم عبارتند از:
PQ : صف وظایف تناوبی
AQ : صف وظایف غیرتناوبی
JQueue = {JQ1 , JQ2 , … JQm} : مجموعه صف وظایف متناسب با هر هسته پردازنده است که این صف میتواند شامل ترکیبی از وظایف تناوبی و غیرتناوبی باشد که همگی آماده اجرا هستند.
UT : بهرهوری وظایف تناوبی
Vd : سررسید مجازی
P-id و Selected-pid : شناسههای هسته پردازنده
Jobhead[i] : وظیفه تناوبی و یا غیرتناوبی در ابتدای صف JQi
Jobhead[P-id] : وظیفه تناوبی و یا غیرتناوبی در ابتدای صف تخصیص داده شده به هسته با شناسه P-id
AJobhead : وظیفه غیرتناوبی در ابتدای صف وظایف غیرتناوبی
Jobarrived[P-id] : وظیفه رسیده در زمان t در صف JQP-id
Jobnext[P-id] : وظیفه بعدی در صف JQP-id که آماده برای اجرا است.
JobAP : بیانگر وظایف غیرتناوبی است.
ورودیهای الگوریتم شامل : مجموعه وظایف تناوبی، مجموعه وظایف غیرتناوبی، و تعداد هستههای پردازنده.
خروجیهای الگوریتم شامل : زمانبندی انجام شده.
فرضیات شامل : تمامی وظایف تناوبی مستقل بوده و همگی در زمان صفر وارد صف آماده میشوند و وظایف غیرتناوبی در هر زمان دلخواهی میتوانند وارد شوند.
اما الگوریتم شامل 5 مدل اساسی است :
در مدل اول(شکل 3-17)، وظایف تناوبی به m زیرمجموعه، جزءبندی میشوند. در ابتدا قبل از عمل جزءبندی، وظایف تناوبی براساس بهرهوریاشان بصورت صعودی مرتب میشوند. هر زیرمجموعه از وظایف، متناظر با یک هسته میباشد. وظایف غیرتناوبی نیز در زمان ورودشان در صف غیرتناوبی سراسری وارد و سپس به یک هسته پردازشی تخصیص داده میشوند. هر هسته شامل صف مجزایی است که برای نگهداری وظایف تناوبی و غیرتناوبی در هر لحظه استفاده میشود.

Partition(T,PQ,P) {
Populate periodic task set T in PQ;
Sort PQ in ascending order by UT;
Partition_WFD(PQ);
}
شکل 3-17 شبه‌کد الگوریتم جزبندی با WFD ]37[
شکل 20شکل 3-17 شبه‌کد الگوریتم جزبندی با WFD [37]
مدل زمانبند دوم(شکل 3-18)، وظایف تناوبی و همینطور وظایف غیرتناوبی را با استفاده از سیاست EDF زمانبندی میکند. وظایف غیرتناوبی بصورت سراسری در زمان ورودشان و یا در زمان مهاجرتشان، به هستههای مختلف تخصیص داده میشوند. مدل 5 (شکل 3-21)(Select-Processor())، هسته متناظر برای اجرای وظیفه غیرتناوبی را پیدا میکند. سپس سررسید مجازی روی هر هسته محاسبه میشود و هستهای که نزدیکترین سررسید مجازی را دارا باشد برای اجرای وظیفه غیرتناوبی مورد نظر، بکار برده میشود. این به این معنی است که هسته‌ای که اگر وظیفه غیرتناوبی در آن قرار بگیرد سریع‌تر اجرا شود، انتخاب می‌شود. همان طور که شبه‌کد شکل 3-18 مشاهده می‌کنید، در ابتدا همه وظایف تناوبی را وارد صف‌های مربوط به هر هسته که با توجه به الگوریتم تخصیص داده شده بودند، می‌کند و هر وظیفه غیرتناوبی که در هر لحظه ممکن است برسد را نیز وارد صف کلی وظایف غیرتناوبی می‌کند، سپس اگر صف وظایف غیرتناوبی خالی بود، برای وظایف تناوبی در هر صف هسته‌ها الگوریتم EDF اجرا می شود.
Scheduler (T, A, PQ, P, JQueue) {
Join all pending periodic jobs till time t to a queue in JQueue;
Join aperiodic jobs to AQ qrrived at time t;
If (!is_Empty(AQ)) then
p_id = select_processor(AJobhead);
insert AJobhead in JQp_id;
For all Pb 1≤i≤m
If (! Finished(Jobhead[i]) or ! preempted(Jobhead[i]) ) then
Execute_edf(Jobhead[i], JQi ,Pi);
Else
Sched_edf(Jobhead[i], JQi ,Pi);
}
شکل 3-18 شبه کد زمانبند پیشنهادی در ]37[
شکل 21شکل 3-18 شبه کد زمانبند پیشنهادی در [37]
مدل سوم(شکل 3-19) (execute-edf())