بخشی از مقاله
چکیده - در الگوی رایانش ابری، حفظ تعادل بار یک چالش است، با افزایش فوق العاده کاربران وتقاضای خدمات مختلف آنها در پلت فرم محاسبات ابری، استفاده پربار و یا کارآمد از منابع در محیط ابرتبدیل به یک نگرانی بحرانی شد. تعادل بار نقش حیاتی در حفظ ریتم رایانش ابری دارد . معیارهای عملکرد الگوریتم های تعادل بار درمحیط ابر زمان پاسخ و زمان انتظاراست. در این مقاله ما به طور عمده بر روی دو الگوریتم تعادل بار در ابر ،الگوریتم MIN-MIN و الگوریتم MAX-MINتمرکز می کنیم.
-1 مقدمه
تعادل بار [1] روشی است که حجم کار میان گره های متنوع در محیط داده شده را توزیع می کند به گونه ای که تضمین می کند هیچ گره ای در سیستم بیش از حد پربار یا بیکار در هر لحظه از زمان نباشد. یک الگوریتم تعادل بار کارآمد نشان می دهدکه هر گره در سیستم چه میزان بیشتر یا کمتر از همان حجم کاررا انجام می دهد. مسئولیت الگوریتم های تعادل باراین است که کارهای موجود در دامنه ابر را به منابع اشغال نشده اختصاص دهند به طوری که به طور کلی زمان پاسخ در دسترس بهبود یافته و همچنین بهره برداری از منابع کارآمد را فراهم کند. تعادل بار یکی از نگرانی های مهم در محاسبات ابری است زیرا نمی توان تعداد درخواست هایی که در هر ثانیه در محیط ابر صادر می شود را پیش بینی نمود. غیر قابل پیش بینی بودن به دلیل رفتار همیشه در حال تغییردر ابراست. تمرکز اصلی حفظ تعادل بار در حوزه ابربه تخصیص بار به صورت پویا در میان گره ها به منظور برآوردن نیازهای کاربر و ارائه حداکثر استفاده از منابع توسط ارائه بار به گره های متمایزدر دسترس است.
-2 انتظارات از تعادل بار در محیط ابر
تعادل بار [1] روشی است که حجم کاررابه تمام گره های موجود حاضر در سیستم به طور مساوی اختصاص می دهد. رضایت بالای کاربر شعار پشت پرده تعادل بار است. همانطور که تعداد کاربران و همچنین خواسته های آنها روز به روزدر حال افزایش است، ابرها باید خدمات رضایت مندی را برای مشتریان خود فراهم کنند. یک الگوریتم تعادل بار مناسب و یا ایده آل استفاده از منابع در دسترس را مطلوبتر می کند، در نتیجه اطمینان حاصل می شود که گره ای بیش از حد یا کمتر از حد بار نشده باشد. تعادل بار مقیاس پذیری، جلوگیری از گلوگاه را فراهم کرده ،همچنین زمان صرف شده برای رسیدن به پاسخ را کاهش می دهد. بسیاری از الگوریتم های تعادل بار [2] به منظور برنامه ریزی و زمانبندی بار در میان دستگاه های مختلف طراحی شده اند. اما تا کنون هیچ الگوریتم تعادل بار ایده آلی توسعه داده نشده است که باررا به طور مساوی در سراسر سیستم اختصاص دهد. ثابت شده است که اختصاص وظایف به طور مساوی در سراسر سیستم یک مسئلهNP complete نظر گرفته می شود .[7]
-3 تعادل بار در یک محیط محاسبات ابری
الگوریتم های تعادل بار در محیط ابر به دودسته تقسیم بندی می شوند:
.1زمانبندی حالت فوری 2 .2زمانبندی حالت دسته ای 3 درحالت immediateکلیه کارها به صورت برخط زمان بندی می شوند و هر کار پس از دریافت توسط زمان بند به یکی از منابع سپرده می شد.در این حالت هر کار بر اساس زمان ورود خود به منابع داده می شود. در زمانبندی حالت فوری الگوریتم 4 MET که به عنوان حداقل زمان اجرا و الگوریتم MCT5 که به عنوان حداقل زمان اتمام است استفاده می شود.درالگوریتم MCT کار ها به گره های مشابهی داده خواهد شد که در حداقل زمان تکمیل می شوند. در حالت Batch کارها به صورت گروهی زمان بندی می شوند و گروه ها با یک وقفه کوتاه به منابع مربوطه سپرده می شوند. Min-Min و Max-Min متعلق به دسته زمان بندی حالت دسته ای هستند.
-1-3 الگوریتم تعادل بار MIN-MIN
در این الگوریتم کارها در ابتدا به هر گره اختصاص پیدا نمی کند. در ابتدا حداقل زمان اتمام برای تمام گره های موجود محاسبه می شود. هنگامی که این محاسبه به اتمام می رسد کارهابا حداقل زمان اتمام انتخاب شده و به گره های مربوطه اختصاص داده می شود.زمان اجرای تمام کارهای دیگر که در حال حاضر در آن ماشین در دسترس هستند به روز شده است و کار از مجموعه کار در دسترس دور ریخته می شود. این روال تا زمانی انجام می شود که همه وظایف به ماشین معادل اختصاص داده شده باشد.این الگوریتم زمانی بهتر است که تعداد کارهای کوچک از تعداد کارهای بزرگ بیشتر است یا به عبارت بهتر برای اجرای کارهای کوچک قبل ازکارهای بزرگ پیشنهاد می شود.گرسنگی نقطه ضعف این الگوریتم می باشد.MIN-MIN یک الگوریتم ساده و سریع است که موجب بهبود عملکرد می شود.زمان بندی کارها در MIN-MIN در ابتدا باعث بهترین زمانبندی وبهبود زمان اتمام6 می شود. تعیین کار کوچک اولین اشکال آن است. بنابراین، وظایف کوچکتر اولین بار اجرا می شوند، در حالی که وظایف بزرگتر را در مرحله انتظارنگه می دارد که در نهایت باعث نتایج ضعیف در استفاده از ماشین خواهد شد. الگوریتمMIN-MIN حداقل زمان اتمام برای کارهایی که اختصاص داده نشده اندرا به نمایش می گذارد - شبیه به - MCT، و بعدا کارها را با حداقل زمان اتمام به گره هایی که قادر به رسیدگی به آن می باشد اختصاص می دهد. شرح معماری الگوریتم MIN-MINدرشکل 2 نشان داده شده است.
متمرکز می شود بر روی این که کارهای کوچک چگونه با کارهای کوچک همزمان اجرا می شوند.MAX-MIN تقریبا با MIN-MIN یکسان است به جز اینکه این الگوریتم کارهایی که حداکثر زمان اتمام را دارند انتخاب و به ماشین مربوطه اختصاص می دهد. هنگامی که کارها با حداکثر زمان تکمیل کارهایی که حداقل زمان اتمام را دارند پشت سر می گذارند این الگوریتم از مشکل گرسنگی رنج می برد.شرح معماری الگوریتم MAX-MIN در شکل 3 آمده است. شکل :2شرح معماری الگوریتم MIN-MIN
-2-3 الگوریتم تعادل بار MAX-MIN
الگوریتم MAX-MIN بسیار مشابه با الگوریتم MIN-MIN می باشد.در ابتدا برای تمام کارهایی که به سیستم ارسال شده اند حداقل زمان اتمام محاسبه می شود،سپس از بین تمام آن هایی که زمان اتمام دارند،بیشترین زمان انتخاب شده و به ماشین مربوطه اختصاص داده می شود.این الگوریتم بیشتربرای اجرای کارهای بزرگ با کمترین تاخیر و ایجاد تعادل بار بیشتر استفاده می شود. برای مثال اگر در یک مجموعه کار تنها یک کار طولانی ارائه شده باشد پس از آن، الگوریتم MAX-MIN کار کوتاه را همزمان با کار طولانی اجرا می کند.زمان اتمام
