بخشی از مقاله
چکیده
در این مقاله روشی بر مبنای بهینه سازی ژنتیک جهت تخصیص بهینه بارکاری وارد شده به منابع پردازشی در سامانه های رایانش ابری پیشنهاد شده است. استفاده از روش پیشنهادی در سیستم های رایانش ابری تعادل بار در ابرها و کاهش زمان پاسخ به کاربران را در پی دارد. در این مقاله یک تابع برازش در روش بهینه سازی ژنتیک پیشنهاد شده است. با افزایش روزافزون کاربران ابرها و افزایش حجم بار پردازشی روی ابرها به نظر می رسد درآینده ایی نه چندان دور مسئله تعادل بار و در پی آن کاهش زمان پاسخ در ابرها بسیار گسترده تر از اکنون مورد بررسی قرار خواهد گرفت. با توجه به NP-Complete بودن مسئله تعادل بار روی ابرها، الگوریتم های تکاملی در بهینه سازی این مسئله بازخورد بهتری نسبت به الگوریتم های مبتنی بر گرادیان از خود نشان داده اند. در این مقاله روشی تکاملی بر مبنای روش بهینه سازی ژنتیک جهت تخصیص بهینه بارهای کاری به منابع پردازشی در ابر پیشنهاد شده است.
این روش قابلیت تعادل بار روی ابرها را در زمان مطلوبی دارد و با روش های مرسوم امروزی مقایسه شده است. در این مقاله یک پایگاه اطلاعاتی در نظر گرفته شده است که اطلاعات کل ماشین های مجازی در ابر را در اختیار دارد و الگوریتم از آن اطلاعات و همچنین اطلاعات مربوط به بارکاری وارد شده به ابر تشخیص می دهد که بار وارد شده باید روی کدام ماشین مجازی اجرا شود. شبیه سازی های انجام گرفته نشان داده است هرچه نسبت تعداد ماشین های مجازی به تعداد وظیفه ها در ابر کم می شود، این الگوریتم نسبت به الگوریتم های مورد بحث در مقاله سریع تر می تواند بار واردشده به ابرها را متعادل کرده و به طور بهینه با توجه به قدرت پردازش هر ماشین مجازی، یک یاتعدادی بار کاری به آن ماشین تخصیص دهد و در نتیجه زمان اجرای کل بار وارده به ابر را کمینه کند.
کلیدواژه- تعادل بار، الگوریتم ژنتیک، تاریع برازش، الگوریتم نوبتی گردشی، الگوریتم Min ،Min الگوریتم Min. Max
۱ مقدمه
با گسترش روز افزون کاربران ابرها و استفاده از ابرها به عنوان ابزارهای محاسباتی و کاربردی مسئله کنترل بار روی ابرها جدی شد و محققان در پی روش هایی برای تعادل بار بین کلیه منابع پردازشی در ابر برآمدند. در زمینه تعادل بار پیشتر روی معماری های خوشه ای و سیستم های محاسباتی گرید روش های بهینه ای ارائه شد ولی آن روش ها به دلیل ماهیت توزیعی و نامتجانس بودن ابرها قابل پیاده سازی روی ابرها نیستند بنابراین روش های جدید دیگری نیاز است تا بتوان بار ایجاد شده توسط کاربران ابر را بین کلیه منابع پردازشی ابر متعادل کرد. رایانش ابری نوع توسعه یافته محاسبات گرید است]۱][۲[، که علاوه بر سرویس های محاسباتی سرویس های دیگری نظیر نرم افزار ، زیرساخت و پلت فرم را نیز ارائه می کند]۳.[ تعادل بار باعث می شود درخواست های رد شده در ابرها به دلیل سرریز محاسباتی و پهنای باند کمتر شود و درنتیجه رضایت کاربران و ملاقات ”توافق سطح سرویس۱” را به دنبال دارد.
مسئله تعادل بار در ابرها یکی از مسائل بسیار مهم در زمینه رایانش ابری می باشد. به دلیل زیاد بودن حجم درخواست ها برای سرویس های ابری باید مکانیزمی جهت کنترل بار وارد شده به ابر طراحی گردد که هیچکدام از سرویس دهنده های ابر دچار سرریز محاسباتی نشوند. و بتوانند به طور کامل بار وارد شده به ابر را متعادل کنند. هرچه بار در ابر بین سرویس دهنده ها متعادل تر شود به دنبال آن زمان پاسخ به درخواست های کاربران کاهش پیدا کرده، تعداد درخواست های پذیرش شده در واحد زمان افزایش پیدا می کند و در نتیجه کارایی ابر بالاتر می رود. در ]۴[ ساختار اجرای وظیفه ها روی ابر تشریح شده است. سامانه ابری از چندین مرکز داده که در سرتاسر جهان تحت بستر اینترنت با یکدیگر کار می کنند، تشکیل شده است. هر مرکز داده شامل تعدادی ماشین فیزیکی پر قدرت می باشد که میزبان ماشین های مجازی هستند. وظیفه های وارد شده به ابر جهت پردازش تحت یک روش زمان بندی بهینه به ماشین های مجازی ارسال می شوند و در آنجا پردازش می شوند.تعادل بار را در دو سطح می توان بررسی کرد:۱- تعادل بار در سطح ماشین مجازی ۲- تعادل بار در سطح وظیفه ها
• تعادل بار در سطح ماشین مجازی: الگوریتم ها در این نوع از تعادل بار، در زمان سر ریز شدن محاسباتی یک ماشین فیزیکی به دنبال انتقال ماشین مجازی از ماشین سرریز شده به یک ماشین سرریز نشده هستند. الگوریتم های ارائه شده در ]۵[ و ]۶[ از این دست از الگوریتم ها می باشند.
• تعادل بار در سطح وظیفه ها: نوع دیگر از تعادل بار روش های مبتنی بر زمان بندی وظیفه ها می باشد. الگوریتم های تعادل بار در این سطح همان الگوریتم های زمان بندی تخصیص وظیفه ها به ماشین های مجازی هستند که باعث تعادل بار روی همه ماشین های مجازی ابر می شوند. در ]۷[ یک روش برای تعادل بار در این سطح بیان شده است.
در این مقاله الگوریتم اصلاح شده ژنتیک به همراه یک تابع برازش بهینه برای تعادل بار ارائه شده است. در بخش ۲ پیش زمینه ایی از مسئله تعادل بار به همراه قالب کلی روش پیشنهادی ارائه شده است. در بخش ۳ فرضیات مسئله معرفی شده و تعریف مسئله انجام می گیرد. در بخش۴ الگوریتم های پیشین مورد بحث در مقاله به صورت جامع پوشش داده می شوند. دربخش ۵ الگوریتم پیشنهادی ارائه می شود. در بخش ۶ نتایج شبیه سازی نشان داده شده است.
۲ پیش زمینه
در ]۸[ ،NP-Complete بودن تعادل بار در ابرها اثبات شده است. به طور خلاصه در این مقاله مسئله تعادل بار در ابرها به مسئله معروف ”مجموع زیر مجموعه ها” که یک مسئله NP-Complete است، کاهش پیدا کرده و نشان داده می شود که مسئله تعادل بار نیز یک مسئله NP-Complete است. با توجه به ماهیت مسئله تعادل بار در ابرها که NP-Complete می باشند و دخیل بودن چندین هدف در تعادل بار، می توان نتیجه گرفت که روش های بهینه سازی در عمل بازخورد بهتری نسبت به روش های مبتنی بر گرادیان از خود نشان می دهند. در زمانی که باری به ابر وارد می شود این بار از یک یا تعدادی ماشین عبور داده می شود - ماشین های زمان بند - . این ماشین ها وظیفه تخصیص بار وارد شده را به کلیه سرویس دهنده های ابر - ماشین های مجازی - دارند. به نوعی از زمان بندی که بتواند بار را روی ابر با توجه به قدرت و ظرفیت پردازشی هر سرویس دهنده به طور مناسب توزیع کند تعادل بار گفته می شود.
۲- ۱ معماری تعادل بار
به صورت کلی برای تعادل بار در ابرها سه معماری را می توان مورد بررسی قرار داد: ۱- معماری متمرکز ۲- معماری توزیع شده ۳- معماری ترکیبی. هرکدام از این معماری ها معایب و محاسن مختص به خود را دارند به عنوان مثال در معماری توزیع شده قابلیت ”تحمل خرابی” وجود دارد ولی در معماری متمرکز وجود ندارد. یا در معماری متمرکز سربار سیگنالینگ برای هماهنگی بین سرویس دهنده ها وجود ندارد ولی در معماری توزیع شده وجود دارد. در معماری ترکیبی سعی شده است تعادل بار به صورت سلسله مراتبی انجام گیرد. به این ترتیب از محاسن دو معماری دیگر استفاده شود و معایب آن ها تا حد زیادی مرتفع می گردد.
در روش پیشنهاد شده در این مقاله معماری متمرکز استفاده شده است و شمای کلی این معماری در شکل ۱ نشان داده شده است. در معماری متمرکز کل بار وارد شده به ابر توسط یک یا تعدادی ماشین به نام ”متعادل کننده بار” و توسط یک روش تخصیص بهینه بین سرور ها - ماشین های مجازی - تقسیم می شود. به طوری که زمان اجرای کل وظیفه ها در آن ها کمینه گردد ]۹.[ ناظر ماشین های مجازی اطلاعات فعلی هرماشین مجازی را نگهداری می کند. این اطلاعات شامل قدرت پردازشی هر ماشین - MIPS - ، پهنای باند هر ماشین، میزان بار اختصاص یافته به هر ماشین، میزان حافظه در دسترس هر ماشین و ... هستند.
در معماری توزیع شده سرویس دهنده ایی به نام متعادل کننده بار وجود ندارد و کلیه ماشین های مجازی برای تعادل بار با یکدیگر در ارتباط هستندو وظیفه هایی که در هر ماشین مجازی سر ریز می شود به ماشین مجازی دیگری که سر ریز نشده است منتقل می شود. سرور متعادل کننده بار با توجه به اطلاعات ناظر ماشین های مجازی بار متناسب با ظرفیت پردازشی هر سرور را برای آن ارسال می کند. این تعادل به طوری انجام می شود که ”زمان اجرای کل وظیفه ها ۲” کمینه گردد]۰۱. [ الگوریتم پیشنهادی این مقاله روی سرویس دهنده متعادل کننده بار اجرا می شود و به صورت بهینه وظیفه ها را به ماشین های مجازی تخصیص می دهد.
۲- ۲ معیارهای بهینگی در الگوریتم های تعادل بار در ]۶[ تعدادی معیار جهت بررسی بهینگی یک الگوریتم تعادل بار مطرح شده است. تعدادی از این معیار ها به طور خلاصه به شرح زیر می باشند.
• گذردهی : تعداد وظیفه هایی که در واحد زمان اجرایشان به پایان می رسد. گذردهی بالاتر موجب افزایش کارایی سیستم می شود.
• سربار الگوریتم : میزان سرباری است که اجرای الگوریتم به سیستم وارد می کند. هرچه سربار الگوریتم کمتر باشد بار وارد شده به ابر سریع تر متعادل می گردد.
• تحمل پذیری خرابی : قابلیت ادامه کار بدون توقف در صورت خرابی هریک از گره های ابر می باشد. این معیار باعث افزایش بهره وری سیستم می شود
• زمان پاسخ : زمانی است که درخواست های کاربران در ابر اجرا شده و خروجی به آن ها تحویل داده می شود.
در این مقاله هدف معرفی الگوریتمی جهت کاهش ”زمان پایان تمام وظیفه ها” یا به عبارتی ”زمان پاسخ” به کلیه کاربران می باشد. فرض می شود به تعداد N وظیفه بخواهد روی M ماشین مجازی اجرا شود و هر ماشین مجازی دارای MIPS پهنای باند و حافظه در دسترس متفاوت با دیگری باشند و هر وظیفه دارای تعداد میلیون دستورات - MI - تصادفی با توزیع پواسن با مقدار _ = 300 باشد. N وظیفه به دسته های M وظیفه ایی تقسیم می شوند - - .
۳ فرضیات و مدلسازی مسئله تعادل بار
در رابطه - ۱ - فرض شده است که کل بار وارد شده به ابر برابر با L باشد و به تعداد جمعا M ماشین مجازی در ابر موجود باشد. در حالت ایده آل بدون در نظر گرفتن مسائل جانبی - مانند تغییرات پهنای باند و میزان حافظه در دسترس ماشین های مجازی - بار متعادل شده برای هر ماشین مجازی از رابطه - ۲ - بدست می آید. در روابط فوق،بار روی ماشین مجازی i برابر با _i است. L کل بار واردشده به ماشین های مجازی است و M تعداد ماشین های مجازی را نشان می دهد. زمانی که به هر ماشین مجازی دقیقا به اندازه _i بار تعلق بگیرد، تعادل بار انجام شده است. در این رابطه قدرت پردازشی همه ماشین های مجازی یکسان در نظر گرفته شده و از تاخیرهای شبکه و پهنای باند صرف نظر شده است. که در حالت واقعی این رابطه عملا ممکن نیست و برای کارایی بهتر باید تاخیرهای انتقال اطلاعات در شبکه و ظرفیت پردازشی ماشین های مجازی نیز در محاسبات در نظر گرفته شود. در بخش بعد روش هایی برای میل به این هدف ارائه شده است.
مسئله تعادل بار را می توان به صورت یک ماتریس دو بعدی مدل کرد - مانند ماتریس . - P همانطور که در ماتریس P نشان داده شده است، اندیس هر ستون ماتریس نشان دهنده شماره یک ماشین مجازی و مقادیر درایه ها در هر سطر ماتریس نشان دهنده شماره وظیفه نگاشت شده به ماشین مجازی مورد نظر است. هر سطر از ماتریس نشان دهنده یک جایگشت تصادفی از نحوه تخصیص وظیفه ها به ماشین های مجازی می باشد. هدف در تعادل بار پیدا کردن بهترین جایگشت در ماتریس P است. با توجه به اینکه در پیدا کردن بهترین جایگشت باید تغییرات پهنای باند و ظرفیت پردازشی هر ماشین مجازی و میزان حافظه در دسترس آن ها محاسبه گردد، لذا مسئله تعادل بار که همان پیدا کردن بهترین جایگشت از ماشین مجازی است به یک مسئله بهینه سازی چند هدفی تبدیل می شود که باید با روش های بهینه سازی، راه حلی بهینه یافت شود.
در رابطه - ۳ - ، تعداد سطرهای ماتریس - تعداد دسته های بار کاری - می باشد. وظیفه ها به صورت M تایی به الگوریتم وارد می شوند و الگوریتم برای هر دسته - هر سطر - بهترین جایگشت را می یابد. هدف یافتن بهترین جایگشت از بردار⃗ است که اندیس وظیفه مورد نظر است. اگر _ ij برابر با مجموع زمان انتقال و پردازش وظیفه _i روی ماشین مجازی j در زمان t باشد، آنگاه در زمان t مجموع زمان پردازش کل بار روی ماشین های مجازی برابر با - t - می باشد. که در رابطه - ۴ - نشان داده شده است. هدف از کاهش زمان پاسخ یافتن حداقل - t - ممکن در تمام جایگشت های بردار
⃗ است. همانطور که در رابطه - ۵ - مشخص است هدف از این مقاله کاهش زمان دل بار و پیدا کردن بهترین جایگشت از مجموعه بردار ⃗ است.}مجموعه جایگشت های Makespan =min - - t - - 8X 2 {
۴ کارهای انجام شده پیشین
می توان الگوریتم های تعادل بار را از جنبه های مختلفی تقسیم بندی کرد. یکی از این جنبه ها تکاملی یا غیر تکاملی بودن الگوریتم می باشد. در ادامه تعدادی از الگوریتم های تکاملی و غیر تکاملی به تشریح ذکر شده اند و در قسمت آخر کارایی آن ها با یکدیگر مقایسه شده است.
۴-۱ الگوریتم Round Robin
در ]۲۱[ الگوریتم نوبتی گردشی ارائه شده است وظیفه ها به صورت اولین ورودی اولین خروجی عمل می کنند و زمانبندی به صورت اشتراک زمانی می باشد و گره ایی که کمترین بار را دارد - گره ای که کمترین اتصالات با گره های اطراف را دارد - کاندید برای وظیفه بعدی است. مشکل این روش آن است که تنها تعداد اتصالات را معیار سر ریز شدن یک ماشین مجازی قرار می دهد در صورتی که در عمل این گونه نیست و عوامل دیگری نظیر قدرت محاسباتی و پهنای باند و
