دانلود مقاله بررسی الگوریتم های زمانبندی وتعادل بار در رایانش ابری

بخشی از مقاله

چکیده

پیدایش رایانش ابری به عنوان یک مدل جدید از ارائه خدمات در سیستمهای توزیع شده میباشد، که محققان را تشویق به جستجوی ایدههایی برای ارائه هرچه بهتر خدمات به کاربران میکند. در سیستم رایانش ابری، کاربران به سادگی فقط با داشتن اینترنت پرسرعت و دستگاههای سادهای که توان پشتیبانی اینترنت را داشته باشد، با پرداخت هزینه به سرویس دهندهها میتوانند از این سیستم استفاده کنند؛ ماننده آب، برق و گاز. میتوان گفت، از مهمترین چالش ها در این سیستم مدیریت منابع، زمانبندی و تعادل بار میباشد. ما در این مقاله الگوریتمهای زمانبندی و تعادل بار را بررسی و گردآوری کردهایم تا مخاطبان درک بهتری از مفهوم آن داشته باشند. در نهایت چالشهای موجود در این الگوریتمها اشاره کرده و در بخش نتیجهگیری چندین کار آتی را برای پژوهشهای تحقیقاتی در آینده پیشنهاد کردهایم.

کلمات کلیدی:رایانش ابری، الگوریتم های زمانبندی، بهرهوری منابع، تعادل بار

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

-2 الگوریتمهای زمانبندی وتعادل بار موجود

-1-2 الگوریتم های زمانبندی اکتشافی زمانبندی:1

1 scheduling

1

اولین همایش ملی پیشرفت های تکنولوژی در مهندسی برق، الکترونیک و کامپیوتر

First National Conference of Technology Developments on Electronical, Electronics and Computer Engineering

. . . W W W . T D E C O N F . I R . . .

هدف نوبت دهی به فرایندهایی است که در حالت آمادهای به سر میبرند و قرار است یکی از آنها برای اجرا انتخاب شود. این که با چه روشی انتخاب کنیم سبب به وجود آمدن الگوریتم های زمانبندی میشود. هر الگوریتم معیاری خاصی برای انتخاب دارد.

بر اساس یک طبقه بندی ساده میتوان الگوریتمهای زمانبندی کار را در محیط های ابری به دو گروه اصلی طبقه بندی کرد، الگوریتم زمانبندی اکتشافی حالت دستهای و الگوریتم زمانبندی اکتشافی فوری. از الگوریتمهای اکتشافی میتوان به موارد زیر اشاره کرد:

: FIFO2 -1-1- 2 معیار انتخاب در این روش زمان ورود است. این الگوریتم انحصاری میباشد.یعنی به ترتیب ورود از سرویس دهندهی منابع ابر سرویس میگیرند.از این الگوریتم به ندرت استفاده میشود و یا به عنوان الگوریتم ثانویه به همراه دیگر الگوریتمها استفاده میشود.

: Greedy-R3 -2-1-2 در این الگوریتم وظایف با اولین زمان اجرای سریع به قویترین منبع ابر در دسترس برای به حداکثر رساندن زمان پاسخ سیستم اختصاص می یاید.
: Greedy-p4 -3-1-2 در این الگوریتم وظایف با اولین زمان اجرای سریع به ضعیفترین منبع ابر در دسترس برای به حداکثر رساندن زمان پاسخ سیستم اختصاص می یابد.

: Min-min -4-1-2 در این الگوریتم وظایف به منبعی تخصیص مییابد که حداقل زمان تکمیل را فراهم سازد. این الگوریتم ابتدا کوچکترین وظیفه را زمانبندی میکند سپس به سراغ سایر وظایف میرود.

: Max-min -5-1-2 این الگوریتم ابتدا وظایف طولانی را زمانبندی میکند سپس نوبت به وظایف بعدی میرسد. این الگوریتم زمانی استفاده میشود که وظایف کوتاه بیشتری نسبت به وظایف طولانی وجود دارد.

RR5 -6-1-2 :این الگوریتم غیرانحصاری است. در این الگوریتم، زمانبند به هر پروسه یک واحد زمانی ثابت اختصاص میدهد و سپس در بین آنها گردش میکند.از این الگوریتم به همراه الگوریتم fifo در محاسبات ابری استفاده میکنند به طوری که با بروز وقفه، وظیفهی در حال اجرا در صف آماده قرار میگیرد وظیفه بعدی بر اساس fifo انتخاب میگردد.

-2-2الگوریتمهای زمانبندی مهم و کارا در محاسبات ابری
در الگوریتم اول، سعیدپارسا و رضا انتظاری ملکی یک الگوریتم برنامه ریزی RASA6 با وظایف جدید ارائه کردهاند، که از 2 الگوریتم برنامه ریزی سنتی×Max-min و Min-min تشکیل شده است. RASA از مزایای این دو الگوریتم استفاده کرده و معایب آن را پوشش میدهد. اگر چه فرصت هر کار، هزینه ورود وظایف، هزینههای اجرای وظیفه در هر یک از منابع، هزینههای ارتباطی در نظر گرفته نشده است. نتایج تجربی نشانگر این است که RASA الگوریتم زمانبندی موجود را در یک مقیاس بزرگی در سیستمهای توزیع شده به عمل درمیآورد. در الگوریتم دوم ،مهدی جوانمرد و همکارانش یک الگوریتم RSDC7 زمانبندی قابل اطمینان توزیع در محیط محاسبات ابری ارائه کردهاند. دراین الگوریتم کارهای اصلی به زیرمجموعه-هایی تقسیم میشوند. به منظور قبول تعادل کار و زمان درخواست، بصورت جداگانه محاسبه میشوند. برنامه ریزی هر یک از کارها بوسیله محاسبه درخواستها و قبول زمان در قالب کارهای اشتراکی انجام شده است. به طوری که کارایی سیستم افزایش مییابد. در الگوزیتم سوم Dr.h.s.Guruprasad, Dr.M.Dakshayini یک الگوریتم بر پایهی اولویت و پذیرش کنترل طرح ارائه کردهاند. دراین الگوریتم اولویت به پذیرش صف اختصاص داده شده است. پذیرش هرصف بوسیله محاسبه تاخیرات قابل تحمل و هزینه سرویس ها انجام میپذیرد. مزیت این الگوریتم در این است که سیاست با ساختار ابری ارائه شده با معماری بسیار بالا (99%)، میزان تکمیل خدمات نیز با QOS8 تضمین شده را بدست آوردهاند. از آنجا که این سیاست بالاترین حق اولویت را برای پرداخت درخواست سرویس های کاربر فراهم میکند، بطور کلی هزینه سرویس دهی برای ابر افزایش مییابد؟ در نهایت در الگوریتم چهارم Shalmali Ambike و همکارانش یک الگوریتم زمانبندی متمایز با مدل غیر پیشگیرانه تقدم صف ها برای فعالیتها بوسیله کاربر ابر در محیط محاسبات ابری اعمال کردهاند. در این دست آورد یک برنامه کاربردی وب برای انجام برخی ازعملیات مانند آپلود و دانلود یک فایل ساخته شده است از این رو به یک الگوریتم زمانبندی موثر کارها نیاز است. درخواست های QOS کاربر در ابر و منفعت حداکثر سرویس دهنده سرویسهای محاسبات ابر، بوسیله ی این الگوریتم بدست میآید(.(Pinal Salot, 2013, 131 - 135

first in first out Greedy (response) scheduling Greedy (parallelization) scheduling round robin Resource- Aware-Scheduling algorithm

RELIABLE SCHEDULING DISTRIBUTED IN CLOUD COMPUTING Quality of service

2

3

4

5

6

7

8

2

اولین همایش ملی پیشرفت های تکنولوژی در مهندسی برق، الکترونیک و کامپیوتر

First National Conference of Technology Developments on Electronical, Electronics and Computer Engineering

. . . W W W . T D E C O N F . I R . . .

-3-2الگوریتم زمانبندی اولویتبندی کارها
این مقاله الگوریتم زمانبندی کار بر اساس اولویت در محاسبات ابری را پیشنهاد کرده است. هدف اصلی برای پیاده سازی زمانبندی کار، دستیابی به
محاسبات با کارایی بالا و بهترین توان عملیاتی سیستم است. اولویت کارها یک مسئله مهم در زمانبندی است؛ چرا که بعضی کارها باید زودتر از دیگران
سرویس دهی شود. این الگوریتم شامل سه سطح اولویت از جمله سطح زمانبندی(سطح هدف)، سطح منبع(سطح ویژگی) و سطح کار(سطح جایگزینی)
است. برای هرکار درخواستی یک منبع با اولویت تعیین میشود. اولویت هرکار با کار دیگر جداگانه بررسی میشود. برای بررسی کارها و تخصیص منبع،
الگوریتم زمانبندی کار بر اساس اولویت در محاسبات ابری را پیشنهاد کردهاند که در مرحلهی اول مجموعه کارها و منابع وارد میشوند. سپس ایجاد
ماتریس مقایسه سازگار برای همهی کارها مطابق با اولویت دسترس پذیری به منابع و نهایتا محاسبه بردار اولویت برای همهی ماتریسها طبق یک سری
فرمول محاسبه میشود. یک گام در AHP9 محاسبهی بردار وزن ×W و ایجاد ماتریس با بردار اولویت است، که اگر :1':2'…:G با بردار اولویت
Q1,Q2'…'4m متناظر باشد، در این حالت میتوان ماتریس نرمال از سطح کارها را به عنوان معادله تعریف کرد . >:1':2'…': Q@ روشن
است که یک ماتریس با )mتعداد کار)سطر و )dتعداد منابع) ستون است. سپس ایجاد ماتریس با بردار اولویت و محاسبهی ماتریس مقایسهای
سازگار برای منبع، که نرخ سازگاری ×CR به صورت معادله زیر تعریف میشود:
(1) CR=CI/RI
RI به صورت شاخص تصادفی است. RI را میتوان به طور تصادفی بر اساس نرخ مقایسه ماتریس محاسبه کرد. جدول 1 برخی از مقادیر RI که
محاسبه شده است را نشان میدهد. همچنین CI را به وسیلهی معادلهی زیر میتوان محاسبه کرد: ×