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

)، رخدادهایی مثل ورود وظایف با اولویت بالاتر / پایینتر را کنترل میکند. درصورتیکه در حین اجرا، وظیفه با اولویت بالاتری وارد سیستم شود، این مدل وظیفه در حال اجرا را قبضه کرده و وظیفه تازهوارد را اجرا میکند در غیراینصورت اجرای وظیفه جاری ادامه مییابد.
Execute_edf(Jobhead[P_id] , JQp_id , P_id) {
Execute Jobhead[P_id];
If ((isHigherPriority(Jobarrived[P_id])) and (!isFinished(Jobhead[P_id])) then
Insert Jobarrived[P_id] in JQp_id ;
Preempt Jobarrived[P_id];
Else
Insert Jobarrived[P_id] in JQp_id ;
Execute Jobhead[P_id];
}شکل 22شکل 3-19 شبه‌کد سیاست اجرای EDF [37]
مدل چهارم (شکل 3-20 )(sched-edf())، در هر نقطه زمانبندی فراخوانی میشود. این مدل وظیفه بعدی را براساس EDF، زمانبندی کرده همچنین مسئول مهاجرت وظایف غیرتناوبی نیز میباشد.

Sched_edf(Jobhead[P_id] , , JQp_id , P_id) {
If (isFinished(Jobhead[P_id])) then
If (! IsEmpty(JQp_id)) then
execute_edf(Jobhead[P_id] , , JQp_id , P_id);
Else
CPU remains idle;
If (ispreempted(Jobhead[P_id])) then
If (Jobhead[P_id] is peridic) then
execute_edf(Jobhead[P_id] , , JQp_id , P_id);
If (Jobhead[P_id] is aperidic) then
Selected_pid = selectprocessor(Jobhead[P_id]);
Migrate Jobhead[P_id] in JQ of Selected_pid;
execute_edf(Jobhead[P_id] , , JQp_id , P_id);
}
شکل 3-20 شبه‌کد سیاست زمانبندی TBS و EDF ]37[
شکل 23شکل 3-20 شبه‌کد سیاست زمانبندی TBS و EDF [37]

Selected_processor(JobAP) {
Find Vd for JobAP an all the cores;
Selected the core with minimum Vd ;
Return processor id of Selected core;
}
شکل 3-21 شبه‌کد روش مهاجرت وظایف غیرتناوبی در ]37[
شکل 24شکل 3-21 شبه‌کد روش مهاجرت وظایف غیرتناوبی در [37]
در ادامه با یک مثال عملکرد سیستم را بهتر نشان میدهیم.
جدول 3-2، مجموعه وظایف تناوبی را نشان میدهد که شامل شماره وظیفه، بدترین حالت زمان اجرا، دوره تناوب، سررسید و تعداد وظایف در یک فوق دوره153 میباشد. تمامی وظایف تناوبی در زمان صفر وارد سیستم شده و فوق دوره مجموعه وظیفه، 168 است. در جدول 3-3 نیز یک مجموعه از وظایف غیرتناوبی که در زمانهای مختلف و داخواهی میرسند، آورده شده است. شکل 3-22 نمودار زمانی وظایف این مثال را توسط الگوریتم بیان شده برروی 2 هسته پردازشی و تا زمان 17 نشان میدهد. اعداد نشان داده شده در این نمودار، شمارههای متناظر با وظایف میباشند. همانطورکه در این شکل قابل مشاهده است، الگوریتم مجموعه وظایف تناوبی را بین دو هسته پردازشی، جزءبندی میکند. وظیفه T0 با بهرهوری 5/0 به هسته 0 تخصیص داده میشود و وظیفه T1 و T2 به ترتیب با بهرهوری 25/0 و 14/0 به هسته 1 تخصیص داده میشوند از آنجاییکه کل بهرهوری هسته 1 (39/0) کمتر از بهرهوری هسته 0 (5/0) میباشد، وظایف غیرتناوبی A3 و A4 که سررسیدهای مجازی نزدیکتری روی هسته 1 بدست میآورند، برروی هسته 1 زمانبندی میشوند A5 نیز که در زمان 6 وارد میشود ابتدا برروی هسته 1 تخصیص داده میشود اما بعد به هسته 0 برای قبضه شدن مهاجرت میکند.
جدول 2جدول 3-2 مشخصات وظایف تناوبی در مثال مربوطه در [37]
جدول 3-2 مشخصات وظایف تناوبی در مثال مربوطه در ]37[

جدول 3جدول 3-3 مشخصات وظایف غیرتناوبی در مثال مربوطه در [37]
جدول 3-3 مشخصات وظایف غیرتناوبی در مثال مربوطه در ]37[

شکل 3-22 نمودار زمانی مثال مربوطه در ]37[
شکل 25شکل 3-22 نمودار زمانی مثال مربوطه در [37]
مزايا و معايب اين الگوريتم :
یکی از مزایای این الگوریتم توجه به بهره‌وری هسته‌ها در هنگام توزیع وظایف می‌باشد که باعث شده تعادل بارگذاری بخوبی در آن انجام شود. همچنین تمایز بین وظایف تناوبی و غیرتناوبی از جمله مزیت‌های دیگر این الگوریتم است. اما بزرگترین عیب این الگوریتم این است که این الگوریتم فقط به بهره وری هسته‌ها پرداخته و سعی در کاهش بارکاری هر هسته دارد و اصلا به میزان انرژی مصرفی سیستم توجهی نکرده است. نوع توزیع وظایف بین هسته‌ها، عدم سعی در خالی نگه داشتن هسته‌ها و کاهش انرژی مصرفی آن‌ها و خاموش کردن هسته‌ها در حالت بیکار، باعث مصرف توان نامطلوب این الگوریتم خواهد شد.

3-7 نتيجه‌گيری
الگوریتم‌های زمانبندی چندهسته‌ای به سه دسته عمومی، جزبندی و دوگانه تقسیم می‌شوندو دارای مزایا و معایب خاص خود هستند. در این فصل علاوه بر اینکه طبقه‌بندی الگوریتم‌های چند هسته‌ای بیان شد، انواع روش‌های زمانبندی تک هسته‌ای نیز شرح داده شد. سپس چند مقاله به تفصیل مورد بررسی قرار گرفته و الگوریتم‌های پیشنهادی آن‌ها برای توزیع و زمانبندی وظایف بین هسته‌ها بیان شد. بیشتر این الگوریتم‌ها، چهار پارامتر مهم عدم نقض سررسید، مصرف انرژی پایین، زمان‌پاسخ وظایف غیرتناوبی و بهره‌وری سیستم، را به طور همزمان درنظر نگرفتند و تنها به یک یا چندتا از این پارامترها اهمیت می‌دادند. نکته بارز و قابل توجه روش‌های پیشنهاد شده تاکنون این است که هیچ کدام از این روش‌ها، برای اختصاص تعداد هسته‌ها با توجه به نوع وظایف سیستم، روشی را پیشنهاد نداده و تفکیک سازی متناسب با نوع وظایف، همراه با تفکیک سازی هسته‌ها از هم رخ نداده است. در حالی این مهم در روش پیشنهادی ما وجود داشته و نقش مهمی در کارایی الگوریتم پیشنهادی داشته است.

فصل چهارم
فصل چهارم : الگوريتم پيشنهادی

در این فصل الگوریتمی برای توزیع و زمانبندی وظایف در یک سیستم چندهسته‌ای پیشنهاد خواهد شد. این الگوریتم شامل سه سطح است، سطح اول تفکیک وظایف و هسته‌های متناسب با آن‌ها، سطح دوم الگوریتمی برای توزیع واختصاص وظایف بین هسته‌ها و سطح سوم، یک الگوریتم انرژی- سررسید محور، برای تنظیم فرکانس هسته‌ها متناسب با سررسید و زمان اجرای وظایف می‌باشد. همچنین برای زمانبندی هر صف از هسته‌ها از الگوریتم‌های تک‌پردازنده EDF و HPF154 استفاده شده است.

4-1 جايگاه الگوريتم پيشنهادی
در طبقه‌بندی روش‌های توزیع وظایف بین هسته‌ها در زمانبندی یک سیستم چندهسته‌ای، بیان شد که سه روش برای توزیع وظایف بین هسته‌ها وجود دارد: 1) الگوریتم‌های جزبندی (بدون مهاجرت) 2) الگوریتم‌های کاملا مهاجرتی (عمومی) 3) الگوریتم‌های دوگانه (مهاجرتی محدودشده)
در الگوریتم‌های جزبندی، مجموعه کل وظایف سیستم به m زیرمجموعه مجزا (m تعداد هسته‌های پردازنده می‌باشد) تقسیم می‌شود و سپس هر زیرمجموعه به یک هسته اختصاص می‌یابد، هر هسته نیز با یک الگوریتم جدا برای خودش، این زیرمجموعه اختصاص یافته به خودش را زمانبندی می‌کند. در روش جزبندی، هیچ وظیفه‌ای از یک زیرمجموعه نمی‌تواند به زیرمجموعه دیگر مهاجرت کند و باید تا اتمام کار خود در صف همان هسته باقی بماند.
در الگوریتم‌های عمومی، کل وظایف سیستم، در یک صف عمومی قرار می‌گیرند و سپس توسط تنها یک زمانبند، زمانبندی شده و برای اجرا به هسته‌ها ارسال می‌شوند. در اینجا هر هسته دارای یک زمانبندی مجزا نیست و سیستم با همان تک زمانبند در صف عمومی، وظایف را به هسته‌های مورد نظر اختصاص می‌دهد. در این حالت وظایف می‌توانند بین هسته‌ها مهاجرت کنند و همچنین در صورت معلق شدن، می‌توانند پس از بازیابی، در پردازنده متفاوتی اجرا شوند.
اما در دسته سوم یعنی الگوریتم‌های دوگانه، برخی وظایف می‌توانند بین هسته‌ها جابجا شوند درحالی که برخی دیگر نمی‌توانند مهاجرت کنند. در واقع این نوع الگوریتم، ترکیبی از دو الگوریتم عمومی و جزبندی است.
الگوریتم پیشنهادی ما در این پژوهش، در دسته سوم این طبقه‌بندی، یعنی الگوریتم‌های دوگانه جای دارد. این بدین معنی است که در الگوریتم پیشنهادی ما، مجموعه کل وظایف سیستم، به دو زیرمجموعه مجزا تفکیک شده و هر زیرمجموعه، مربوط به دسته‌ای از هسته‌ها می‌باشد. همچنین هر کدام از این زیرمجموعه‌ها نیز خود به زیرمجموعه‌های دیگری به تعداد هسته‌های مربوط به خود تفکیک‌ شده و در نتیجه، هر هسته، روی مجموعه وظایف اختصاص یافته خود، زمانبندی را انجام می‌دهد. این مفهوم در شکل 4-1 به خوبی نشان داده شده است.

شکل 4-1 ساختار کلی زمانبندی سیستم پیشنهادی
شکل 26شکل 4-1 ساختار کلی زمانبندی سیستم پیشنهادی
4-2 کليات الگوريتم پيشنهادی
الگوریتم پیشنهادی ما در این پژوهش شامل سه بخش متفاوت می‌باشد که در هر کدام از این بخش‌ها، روش جدیدی ارائه شده است که ترکیب این سه بخش، الگوریتم پیشنهادی ما را شکل خواهد داد. در این قسمت، هر یک از این سه بخش، به طور کلی و خلاصه، معرفی خواهند شد.
در بخش اول الگوریتم پیشنهادی، روش جدیدی برای نوع سازماندهی وظایف متناسب با هسته‌ها، پیشنهاد می‌شود. ویژگی بارز این سازماندهی این است که پیش از توزیع وظایف بین هسته‌ها، ماهیت وظیفه‌ها مورد توجه قرار می‌گیرد و براساس خصوصیت این وظایف تفکیک شده، سازماندهی هسته‌های پردازنده انجام می‌شود.
در بخش دوم الگوریتم پیشنهادی، روش جدیدی برای توزیع وظایف بین هسته‌ها، پیشنهاد می‌شود، یعنی الگوریتم جدیدی برای مشخص شدن اینکه هر وظیفه باید به کدام هسته برای اجرا فرستاده شود، پیشنهاد می‌شود. الگوریتم توزیع پیشنهادی ما، هدف‌های مهمی را دنبال می‌کند، از جمله این هدف‌ها می‌توان به کاهش نرخ نقض سررسید، کاهش مصرف انرژی، افزایش زمان پاسخ برخی وظایف و افزایش بهره‌وری سیستم اشاره کرد. همچنین سعی شده است تا سربار پیچیدگی الگوریتم، نسبت به کارهای گذشته، کاهش پیدا کرده و کارایی سیستم افزایش یابد.
در بخش سوم الگوریتم پیشنهادی، تکنیک جدیدی برای تنظیم فرکانس و ولتاژ هسته‌ها، در هنگام اجرای وظایف روی هر هسته، پیشنهاد می شود. این الگوریتم، همزمان با الگوریتم توزیع، اجرا می‌شود و زمان اجرای نهایی وظایف و میزان انرژی مصرفی آن‌ها را محاسبه خواهد کرد. همچنین این الگوریتم، جز الگوریتم‌های تنظیم فرکانس سررسید محور می‌باشد که به این معنی است که این الگوریتم، علاوه بر اینکه سعی در کاهش مصرف انرژی دارد، سررسید وظایف را نیز در نظر دارد، یعنی با استفاده از تکنیک پیشنهادی، برای جلوگیری از نقض سررسید وظیفه در حال اجرا، در مواقع لازم، سطح فرکانس اجرایی هسته را افزایش می‌دهد.

4-3 مدل وظيفه الگوريتم پيشنهادی
در مدل پیشنهاد شده در این پژوهش، وظایف سیستم به دو دسته تناوبی و غیرتناوبی تقسیم می‌گردند. وظایف تناوبی از نوع غیر انحصاری بوده و وظایف غیرتناوبی از نوع انحصاری درنظر گرفته می شوند. این مسئله بدین معنی است که هرگاه وظیفه‌ای تناوبی در حال اجرا در هسته‌ای باشد و وظیفه دیگری با اولویت بالاتر از راه برسد، این وظیفه جدید نمی‌تواند پردازنده را از وظیفه در حال اجرا بگیرد و در انحصار خود قرار دهد. اما اگر وظیفه غیرتناوبی در حال اجرا باشد و وظیفه غیرتناوبی دیگری با اولویت بالاتر وارد صف این هسته شود، پردازنده از وظیفه در حال اجرا گرفته شده و به وظیفه با اولویت بالاتر داده می شود.
همچنین در این مدل، وظایف غیرتناوبی می‌توانند تحت شرایطی بین هسته‌ها مهاجرت کنند، اما وظایف تناوبی چنین اجازه‌ای ندارند و باید تا پایان اجرا، روی هسته‌ای که الگوریتم توزیع، آن را به وظیفه اختصاص داده، باقی بمانند.
مشخصه‌های وظایف سیستم پیشنهادی به صورت زیر می باشد:
Si : مجموعه کل وظایف سیستم
Tp : مجموعه وظایف تناوبی
TAp : مجموعه