بخشی از مقاله
چکیده
مسئله تضمین کیفیت سرویس به کاربران گرید از طریق رزرو نمودن پیشاپیش1 منابع فراهم می شود. رزرو نمودن پیشاپیش، مکانیسمی است که توانایی تخصیص منابع به کاربران را براساس توافق بر روی نیازمندی های کیفیت سرویس و افزایش تعداد درخواست های پذیرفته شده کاربران در سیستم گرید فراهم می کند. زمانبندی و رزرو نمودن پیشاپیش منابع در گرید یک مساله NP-complete است، پس نمی توان از الگوریتم های قطعی برای بهبود آن استفاده نمود.
روش های هیوریستیک برای این منظور عبارتند از الگوریتم ژنتیک، سرمایش شبیه سازی شده، تپه نوردی و روش های جستجوی دیگر. در این مقاله روش هیوریستیک جدیدی به نام الگوریتم جستجوی تصادفی تقلید نیروی گرانشی GELS برای حل مساله زمانبندی و رزرو نمودن پیشاپیش منابع در گرید را نشان می دهیم. این الگوریتم بر پایه مفاهیم جستجوی تصادفی، دو تا از چهار پارامتر اصلی سرعت2 و نیروی گرانشی3 در فیزیک استفاده می نماید. الگوریتم پیشنهادی را GELSAR4 نامیده و برای تصدیق آن، الگوریتم را پیاده سازی نموده و با الگوریتم ژنتیک مقایسه نموده ایم. بر اساس نتایج بدست آمده مشاهده می شود که تعداد کارهای رزروشده نسبت به الگوریتم ژنتیک 7.5 درصد افزایش یافته و نیز زمان اجرای الگوریتم تا 50 درصد کاهش می یابد.
-1 مقدمه
در سیستم محاسباتی گرید، با چندین درخواست همزمان کاربر برای استفاده از منابع در آینده، باید از یک الگوریتم زمانبندی موثر برای رزرو نمودن پیشاپیش منابع استفاده نمود، بطوریکه تعداد درخواست های بیشتری پذیرفته شود. توانایی ارائه و تضمین سرویس به کاربران، یکی از مسائل با اهمیت در گرید است. بدون تضمین، کاربران هیچ میلی به پرداخت پول برای سرویس های گرید یا شرکت دادن منابع اشان در گرید ندارند که این باعث جلوگیری از توسعه مدل گرید می شود. بنابراین باید چارچوبی برای طراحی موثر و کارامد الگوریتم های زمانبندی برای رزونمودن پییشاپیش منابع و تضمین سرویس به کاربران استفاده نمود.
محیطی که در آن کاربران، کارهایشان را ارائه نموده و این کارها ممکن است در زمان آینده شروع شده و باید در یک موعد زمانی خاصی تکمیل شود. به کمک مفاهیم محاسبات هندسی ونیز ماتریس منابع، چگونگی مدیریت موثر تکه منابع مورد استفاده در رزرو نمودن پیشاپیش را نشان می دهیم. الگوریتم های زمانبندی برای رزرونمودن پییشاپیش منابع درسیستم محاسباتی گرید بصورت یک مشکل NP-complete است که نمی توان با استفاده از الگوریتم های سنتی آن را حل نمود. بنابراین روشی نیاز است که توانایی حل چنین مسائلی را داشته باشد.
از جمله روش های شناخته شده ای که برای حل چنین مسائلی استفاده می شوند[5,7,10,11] عبارتند از الگوریتم ژنتیک، سرمایش شبیه سازی شده، تپه نوردی و روش های جستجوی مکاشفه ای دیگر... . در این مقاله از روش جدیدی به نام GRAVITY برای حل این چنین مسائل استفاده می کنیم. در این روش با تخصیص منابع محاسباتی گرید به درخواست های کاربران به صورت اولیه کار را شروع می نماییم.
ساختارمقاله به صورت زیر سازماندهی شده است: در بخش 2 به بیان مساله زمانبندی و رزرونمودن پیشاپیش منابع پرداختیم. در بخش 3 به شرح الگوریتم GELS پرداخته و در بخش 4 به جزیئات بیشتر الگوریتم GELS برای زمانبندی و رزرو منابع پرداخته والگوریتم جدید را GELSAR نامیدیم. در بخش 5 نتایج شبیه سازی را با پارامتر های کارآیی مختلف نشان دادیم و با نتیجه گیری مقاله را به پایان رساندیم.
-2 تعریف مسئله
زمانبند S برای گرید با n سرور که از نظر جغرافیایی در شبکه توزیع شده هستند را در نظر بگیرید. با فرض آنکه همه سرور ها ظرفیت پردازش آن ها یکسان و برابر c باشد. کاربری با کار j درخواست سرویس را به زمانبند ارائه می دهد. زمانبند S برای هر سرور i ، دوره های زمانی در آینده که این سرورها برای کارها رزروشده است را در یک رکوردی نگهداری می کند. در حقیقت این زمانبندی نشان دهنده مجموعه ای از رزرونمودن پیشاپیشی است که ایجاد شده است و تضمین می نماید که منبع سرور در زمان خاصی در آینده برای کارهای پذیرفته شده در دسترس می باشد. شکل1 مسئله زمانبندی را برای دو سرور نشان می دهد. در زمان جاری - - t=0 دو کار زمانبندی شده در سرور1 وجود دارد. کار جاری در زمان t4 پایان خواهد یافت. کار D سرور1 را از زمان t8 تا t10 رزرونموده است. به طور مشابه دو کار برای سرور 2 زمانبندی شده است.
در شکل 2 مسئله زمانبندی به صورت هندسی نمایش داده شده و دوره های بیکاری سرورها در این طرح به صورت نقطه نشان داده شده است. فرض کنید در یک زمان چندین کار با زمان آماده سازی یک و زمان اجرای مختلف تقاضای سرویس نمایند که این مسئله در شکل 3 نشان داده شده است. زمانی که تقاضای سرویس - rj,lj,dj - برای چندین کار جدید به صورت همزمان صادر می شود، زمانبند s بلافاصله الگوریتمی را اجرا می کند تا تعیین نماید که آیا زمانبندی کارها و رزرو منابع در آینده عملی امکان پذیر است. اگر چنین باشد، زمانبند s مجموعه ای از معیارها و ملاک ها را برای انتخاب سرورهایی که بتواند این کارها را اجرا نماید بکار می گیرد، سپس شماره این سرور را به کاربر برمی گرداند و در نهایت زمانبند بهنگام سازی می شود، در غیر اینصورت کار رد می شود.
بنابراین تصمیمات زمانبندی و توسعه الگوریتم های زمانبندی موثرو کارآمد، درصد پذیرفته شدن کارها و بهره وری سیستم را افزایش می دهد. در شکل1 سه کار با زمان های اجرای مختلف در زمان t1 به زمانبند ارائه شده اند، یکی از اهداف زمانبند تخصیص کارها به مجموعه ای از نودهای محاسباتی است به طوری که تعداد کارهای بیشتری زمانبندی شود. در شکل 3 این مسئله نشان داده شده است. در شکل 4 زمانبندی کارها به صورت هندسی نمایش داده شده است.
GELS -3
در سال 1995 وادوریس و تسانگ [2] برای اولین بار الگوریتم GLS برای جستجو در یک فضای جستجو و حل مسائل NP-complete پیشنهاد داد و در سال 2004 بری وبستر [1] آن را به عنوان یک الگوریتم نیرومند ارائه داد و آن را با GELS نام گذاری کرد. ایده این الگوریتم بر اساس اصل نیروی گرانشی است که در طبیعت سبب می شود اشیا به سمت یکدیگر جذب شوند بطوریکه شیئ سنگین تر دارای نیروی گرانش بیشتر است و آن را بر اشیای دیگر اعمال کرده و اشیای با وزن کمتر را به سوی خود جذب می کند. البته فاصله دو شیئ بر اندازه این نیرو بسیار موثراست بطوریکه، دو جسم با وزن یکسان و با فاصله های مختلف نسبت به شیئ با وزن کمتر را در نظر بگیرید جسمی که دارای فاصله کمتری با شیئ کم وزن است نیروی جاذبه بیشتری بر آن اعمال می کند.
