بخشی از مقاله
چکیده :
برنامه ریزی وظایف در محیط محاسبات ابری یک مشکل NP سخت است. متعادل سازی بار وظایف در ماشین های مجازی یکی از جنبه های مهم برنامه ریزی وظایف در ابر می باشد. هر گاه ماشین مجازی خاصی پربار شود و باقی ماشین های مجازی تحت فشار بار بوسیله پردازش وظایف قرار گیرند، بار باید برای رسیدن به بهره برداری بهینه ماشین ها متعادل شود.
در این جا ما از الگوریتم فراابتکاری زنبور عسل جهت رسیدن به تعادل بار روی ماشین ها استفاده می کنیم. الگوریتم پیشنهاد شده همچنین اولویت وظایف در صف ماشین ها را بر اساس کمترین زمان انتظار برقرار می کند. رویکرد ما نشان می دهد، که بهبود قابل توجهی در متوسط زمان اجرا و کاهش زمان انتظار در صف وجود دارد.
- 1 مقدمه
محاسبات ابری یک رویکرد مبتنی بر اینترنت می باشد که در آن تمامی برنامه های کاربردی و فایل ها در یک ابر متشکل از هزاران کامپیوتر، که با هم به صورت پیچیده ای ارتباط دارند، میزبان می باشند. ابر رایانه1 شامل مفاهیم موازی2 و محاسبات توزیع شده3 برای فراهم کردن منابع اشتراکی سخت افزار، نرم افزارو اطلاعات به کامپیوترها یا دیگر دستگاه هایی است که مورد تقاضا می باشند. ظهور سیستم های این چنین که از الگوی "پرداخت به ازای استفاده"4 استفاده می کنند از سیستم توزیع شده می باشد.
در اینجا مشتری نیازی به خرید نرم افزار یا پلت فرم محاسباتی ندارد بلکه با امکانات اینترنتی، مشتری می تواند از قدرت محاسباتی و یا منابع نرم افزاری با پرداخت پول فقط در زمان استفاده از منبع، بهره گیرد. مشتری علاقه مند به کاهش زمان اجرای برنامه ها روی ماشین ها می باشد. واحد پردازش5 در محیط محاسبات ابری، ماشین مجازی6 نامیده می شوند. از نقطه نظر تجاری، این ماشین های مجازی باید هم سریع و هم موازی باشند. این امر منجر به مشکلاتی در زمانبندی وظایف7 برای اختصاص منابع در دسترس می شود.
زمانبند باید برای فرایندها زمانبندی مناسبی برای اختصاص منابع در دسترس ارائه دهد. که بتواند یک یا چندین کار را به یک ماشین مجازی برای اجرای هم زمان اختصاص دهد. این نوع از محیط باید مطمئن شود که بار به خوبی در همه ماشین های مجازی متعادل شده باشد.
به عنوان نمونه بار نباید روی یکی از ماشین ها زیاد و برخی دیگر بیکار بمانند. مسئولیت تعادل بار روی ماشین های مجازی بر عهده زمانبندی می باشد. الگوریتم تعادل بار8 با استفاده حداکثر از منابع در دسترس، زمان پاسخ9 کاربر را بهبود می دهد. هدف اصلی از تعادل بار، سرعت بخشیدن به اجرای برنامه های کاربردی روی منابع است که حجم کار متفاوت در زمان اجرا دارند
تکنیک های متعادل کننده در محیط های همگن10 و ناهمگن11 مانند محیط های شبکه12 مورد بحث های گسترده قرار گرفته اند. اساسا دو نوع متعادل کننده بار وجود دارد : - 1 استاتیک - 2 . داینامیک.
الگوریتم های استاتیک تنها زمانی که گره تفاوت کمی دارد به درستی کار می کند. بنابراین این نوع الگوریتم، الگوریتم مناسبی برای محیط های ابر که دارای بار متفاوت در زمان های مختلف می باشد نیست. الگوریتم داینامیک از استاتیک برای متعادل کردن بار مناسب تر است. ولی برای به دست آوردن این مزیت ما نیاز به در نظر گرفتن هزینه های اضافی برای جمع و نگهداری بار اطلاعاتی هستیم. تکنیک های پویا برای تعادل بار وظایف در منابع ناهمگن بسیار موفق هستند.
در این روش پیشنهادی ما که از تکنیک داینامیک استفاده می کند علاوه بر تعادل بار، اولویت کارها در صف ماشین های مجازی را هم رعایت می کند. در محیط محاسبات ابری، هر زمان یک ماشین مجازی بار کارهایش زیاد شود، باید این کارها از ماشین مجازی حذف و به ماشینی که مرکز داده اش یکسان است اضافه شود، این کارها به ماشینی که ترکیبی خوب از اولویت ها دارند و نیازی به قرار گرفتن مدت طولانی در صف جهت تبدیل به پردازش ندارد، اضافه می شود. تعادل بار در ماشین مجازی در سطح درون داده ای انجام می شود.
رویکرد ما نشان می دهد که موازنه بار در محیط محاسبات ابری می توانداز مدلسازی رفتار جستجوگر زنبورعسل15 جهت منبع غذایی پیروی کند. در زنبور عسل، یک زنبور دیده بان 16 وجود دارد. پروسه ی جستجوی غذای یک کلونی - مجموعه زنبورهای یک کندو - به وسیله ی زنبورهای دیده بان آغاز می شود که برای جستجوی گلزار های غنی فرستاده می شوند. زنبورهای دیده بان به صورت تصادفی از گلزاری به گلزار دیگر حرکت می کنند. زنبور عسل هنگامی که یک منبع غذایی پیدا کرد جهت تبلیغ منبع غذایی با استفاده از یک نوع رقص لرزان - 17چرخشی - به کندوی عسل باز می گردد. این رقص ،کیفیت و کمیت و فاصله منبع از کندوی عسل را نمایش می دهد.
زنبورهای کاوشگر18 سپس از زنبورهای دیده بان برای محل غذا سپس درو کردن آن پیروی می کنند. سپس آنها هم به کندو بازگشته و با انجام رقص به زنبورهای دیگر منابع غذایی ترک کرده را ایده می دهند و از این روست که منابع غذایی را رها می کنند و یا استثمار می کنند.
در شیوه ای مشابه، کارهای حذف شده از ماشین های پربار به عنوان زنبور های عسل در نظر گرفته می شوند. پس از ارسال کار به ماشین، اولویت کارهای در صف آن ماشین را به روز رسانی می کند و کم شدن بار کاری ماشین خاص را به باقی کارهای منتظر اعلام می کند. هرگاه یک وظیفه با اولویت بالا به دیگر ماشین ها ارسال می شود، باید ماشینی که دارای کمترین تعداد کار با اولویت بالا را داشته انتخاب شود تا کار زودتر انجام شود.
در اصل، وظایف، زنبور عسل ها هستند و ماشین ها منابع غذایی می باشند. انتساب19 یک ماشین به کار حذف شده مانند جستجوی منبع غذایی توسط زنبور می باشد. کار باید به یک ماشین برنامه ریزی شود که مشابه جستجوی زنبور عسل برای منبع غذایی جدید می باشد. کار حذف شده باقی کارها را بروزرسانی می کند که مشابه رقص زنبور عسل در کندو جهت متوجه کردن باقی زنبورها می باشد.
