بخشی از مقاله
بررسی الگوریتم هاي تعادل بار در رایانش ابري
چکیده
امروزه محاسبات ابري به عنوان یک مدل جدید و محبوب براي برنامه هاي کاربردي، علمی تبدیل شده است. براي این امر سیستم هاي گوناگونی توسط کارشناسان پیشنهاد و ارائه شده، که از آن جمله می توان به محاسبات خوشه اي؛ محاسبات هوشمند و در نهایت رایانش ابري اشاره کرد. در سیستم رایانش ابري، کاربران به سادگی فقط با داشتن اینترنت پرسرعت و دستگاه هاي ساده اي که توان پشتیبانی اینترنت را داشته باشد با پرداخت هزینه به سرویس دهنده ها می توانند از این سیستم استفاده کنند. می توان گفت یکی از مهمترین چالش ها در این سیستم مدیریت منابع و زمانبندي جهت رسیدن به تعادل بار می باشد. ما در این مقاله با مقایسه چند الگوریتم تعادل بار به ضعف و قوت این الگوریتم ها اشاره کرده و در بخش نتیجه گیري چندین کار آتی را براي پژوهش هاي تحقیقاتی در آینده پیشنهاد کرده ایم.
کلمات کلیدي:
رایانش ابري، زمانبندي، تعادل بار، مدیریت منابع، محاسبات خوشه اي
١
-1 مقدمه
محاسبات ابري1 ساختاري شبیه یک توده ابر دارد، که به واسطه آن کاربران می توانند به برنامه هاي کاربردي از هرجایی از دنیا دسترسی داشته باشند. محاسبات ابري در واقع همان شکل دیگر اینترنت است که به صورت عام و فراگیر در آمده است. از مزایاي محاسبات ابري مبحث اشتراك گذاري فایل ها و داشتن فضاي مجازي است. محاسبات ابري این امکان را به شما می دهد، که فضایی در حدود یک میلیون گیگابایت در اختیار داشته باشید. کاربران براي منابع و برنامه هاي مورد استفاده هزینه پرداخت میکنند، مانند پرداخت هزینه براي آب، برق و گاز. یکی از چالش هاي مهم کارشناسان و محققان تعادل بار در ابر و عملکرد سیستم می باشد، که در تحقیقات خود به بررسی منابع و اشکالاتی که در اجراي برنامه ها و مسئله ي زمانبندي عملکرد سیستم است، پرداخته اند. پاسخ دهی به درخواستها و مدیریت و نحوه زمانبندي که در کمترین زمان بهترین پاسخ را بدهد نیازمند آمادگی و زمانبندي و مدیریت خرابی است. علاوه بر این بسیاري از یافته هاي پژوهشی، ازجمله الگوریتم ژنتیک، کلونی مورچه، هوش مصنوعی و... براي حل مساله تعادل بار استفاده می شوند. ادامه ي این مقاله به این شرح است که، در بخش دوم الگوریتم هایی که در مساله تعادل بار مورد استفاده قرار می گیرد را بررسی می کنیم و نتیجه ي گردآوري چندین مقاله را ارائه می دهیم، ودر بخش سوم نتیجه گیري و زمینه هاي تحقیقات جدید براي کارهاي آتی را بیان می کنیم.
-2 بررسی الگوریتم هاي تعادل بار موجود
-1-2الگوریتم هاي زمانبندي جهت رسیدن به تعادل بار
بر اساس یک طبقه بندي ساده می توان الگوریتم هاي زمانبندي کار جهت رسیدن به تعادل بار در محیط هاي ابري را به دو گروه اصلی طبقه بندي کرد، الگوریتم زمانبندي اکتشافی حالت دسته اي و الگوریتم زمانبندي اکتشافی فوري. با توجه به اینکه که محیط ابر یک سیستم ناهمگن است و سرعت هر پردازنده سریع تغییر می کند الگوریتم زمانبندي اکتشافی حالت فوري، براي یک محیط ابر مناسب تر است. از الگوریتم هاي اکتشافی که در مبحث تعادل بار مطرح می شوند، دو الگوریتم زیر بیشترین استفاده را دارد:
١-٢: FIFO معیار انتخاب در این روش زمان ورود است. این الگوریتم انحصاري می باشد. یعنی به ترتیب ورود از سرویس دهنده منابع ابر سرویس می گیرند. از این الگوریتم به ندرت استفاده می شود ویا به عنوان الگوریتم ثانویه به همراه دیگر الگوریتم ها استفاده می شود.
٢-٣: RR این الگوریتم غیرانحصاري است. در این الگوریتم، زمانبند به هر پروسه یک واحد زمانی ثابت اختصاص می دهد و سپس در بین آنها گردش می کند. از این الگوریتم به همراه الگوریتم FIFO در محاسبات ابري استفاده می کنند به طوري که با بروز وقفه، وظیفه ي در حال اجرا در صف آماده قرار می گیرد وظیفه بعدي بر اساس FIFO انتخاب می گردد.
1 ابر، مجموعهاي از رایانههاي توزیع شده است
2 first in first out
٢
-2-2الگوریتم تپه نوردي تصادفی
الگوریتم تپه نوردي تصادفی، که یک حالت کلی از تعادل بار با بهینه سازي هرچه بهتر منابع را بیان کرده است. هدف اصلی این الگوریتم به حداکثر رساندن استفاده از منابع ابر و پاسخگویی مناسب به درخواست ها است. در این الگوریتم با به کار بردن الگوریتم RR، پخش کارها در میان واحدهاي پردازشی ساده شده است. در الگوریتم تپه نوردي تصادفی بیشتر بر روي تشخیص منابع و استفاده ي درست از آنها تمرکز شده است، که به شرح زیر می باشد:
یک جدول از فهرست ماشین هاي مجازي نگهداري می کند، که این جدول شامل دو قسمت است: -1 ماشین هاي مجازي اختصاص داده نشده،-2 ماشین هاي مجازي اختصاص داده شده. با ورود کار در ابر یک پرس و جو براي تشخیص نوع درخواست و یک کد به طور تصادفی به ماشین مجازي که کار براي پردازش در آن قرار می گیرد، تولید می شود. در هربار که ماشین مجازي درخواستی را به پایان می رساند یک پیغام جهت تخصیص دوباره تولید می کند و یک حساب کارایی از ماشین مجازي نگهداري می شود، تا اگر طبق انتظار کارایی نداشت مکررا واگذاري انجام ندهد و از آن ماشین در کارهاي ضعیف تر استفاده کند. در هر دوره تخصیص منبع، جدول به روز می شود و دوباره از قسمت تولید پرس و جو به درخواست هاي بعدي رسیدگی می کند
.(Brototi mondal, 2012, 783 – 789)
-3-2روش دوطرفه سریع بارگذاري فایل به صورت تعادل بار پویا
این مقاله مشابه مقاله قبل، علاوه بر تمرکز بر روي تعادل بار و به حداکثر رساندن استفاده از منابع ابر و پاسخگویی مناسب به درخواست ها، به مشکلات درخواست هاي مشابه نیز پرداخته است. آنها یک روش دوطرفه سریع بارگذاري فایل به صورت تعادل بار پویا در ابر پیشنهاد کرده اند ٤.DDFTP به گونه اي که اگر دو مدل مشابه از یک فایل در دو سرویس دهنده باشد آن را با استفاده از پروتکل FTP5 تقسیم کرده و به اشتراك می گذارد و با پروتکل ٦TCP بسته هاي به اشتراك گذاشته شده را کنترل می کند. در این روش سرویس دهنده ها قسمت هاي تقسیم شده را پردازش کرده و پس از پایان، یک جواب کلی به درخواست کننده می دهد .(Jameela Al-Jaroodi, 2013, 1116–1130)
-4-2الگوریتم زمانبندي کار بر اساس اولویت
این مقاله الگوریتم زمانبندي کار بر اساس اولویت در محاسبات ابري را پیشنهاد کرده است. هدف اصلی براي پیاده سازي تعادل بار در این الگوریتم، زمانبندي کار، دستیابی به محاسبات با کارایی بالا و بهترین توان عملیاتی سیستم است. با توجه به اینکه اولویت
٣
کارها یک مسئله مهم در تعادل بار است؛ چرا که بعضی کارها باید زودتر از دیگران سرویس دهی شود. این الگوریتم شامل سه سطح اولویت از جمله سطح زمانبندي(سطح هدف)، سطح منبع(سطح ویژگی) و سطح کار(سطح جایگزینی) است.
براي هرکار درخواستی یک منبع با اولویت تعیین می شود. اولویت هرکار با کار دیگر جداگانه بررسی می شود. براي بررسی کارها و تخصیص منبع، الگوریتم زمانبندي کار بر اساس اولویت در محاسبات ابري را پیشنهاد کرده اند که در مرحله ي اول مجموعه کارها و منابع وارد می شوند. سپس ایجاد ماتریس مقایسه سازگار براي همه ي کارها مطابق با اولویت دسترس پذیري به منابع و نهایتا محاسبه بردار اولویت براي همه ي ماتریس ها طبق یک سري فرمول محاسبه می شود. یک گام در ٧AHP محاسبه ي بردار وزن W و ایجاد ماتریس با بردار اولویت است، که اگر W1,W2,…Wd با بردار اولویت Q1,Q2,…,Qm متناظر باشد، در این حالت می توان ماتریس نرمال از سطح کارها را به عنوان معادله تعریف کرد . =[W1,W2,…,Wn] روشن است که یک ماتریس با )mتعداد کار)سطر و )dتعداد منابع) ستون است. سپس ایجاد ماتریس با بردار اولویت و محاسبه ي ماتریس مقایسه اي سازگار براي منبع، که نرخ سازگاري CR به صورت معادله زیر تعریف می شود:
(١) CR=CI/RI
RI به صورت شاخص تصادفی است. RI را می توان به طور تصادفی بر اساس نرخ مقایسه ماتریس محاسبه کرد. جدول 1 برخی از مقادیر RI که محاسبه شده است را نشان می دهد. همچنین CI را به وسیله ي معادله ي زیر می توان محاسبه کرد:
