بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
معرفي و مقايسه الگوريتم هاي زمان بندي منابع در محاسبات ابري
محاسبات ابری در سال های اخیر به عنوان یکی از مهم ترین تکنولوژی ها برای تحویل تقاضای سرویس های پیشرفته از طریق اینترنت عمومی، ضروری شده است. مسئله زمانبندی منابع در محیط محاسبات ابری، مسئله ای بسیار مهم می باشد. سیستم زمانبندی، وظایف مختلفی را در محاسبات ابر، جهت افزایش نرخ تکمیل کار و افزایش بهره وری از منابع و در نتیجه افزایش توانمحاسباتی را کنترل می کند. در این مقاله، الگوریتم های استراتژی تعادل بار زنبور عسل(HBB-LB) و ژنتیک و الگوریتم Backfill و الگوریتم زمان بندی اولویت پویا بر زمان بندی درخواست سرویس در محاسبات ا بری را بررسی کرده و با الگوریتم های FCFS, RR,SHC مقایسه میکنیم.
١ مقدمه
محاسبات ابري در سال هاي اخير به عنوان يکي از مهم ترين تکنولوژيها براي تحويل تقاضاي سرويس هاي پيشرفته از طريق اينترنت عمومي، ضروري شده است . محيط محاسبات ابري قابليلت ذخيره سازي داده ها را به صورت امن ، راحت و آسان و همچنين قابليت ارائه توان محاسباتي را از طريق اينترنت فراهم مي سازد. مجازي سازي، توزيع پذيري و قابليت توسعه و گسترش خصوصيات جداييناپذير ابر ميباشند. محاسبات ابري سه نوع سرويس را به کاربران خود ارائه ميدهد: زيرساخت به عنوان سرويس (IaaS)، پلتفرم به عنوان سرويس (PaaS) و نرم افزار به عنوان سرويس (SaaS). اين سرويس ها به صورت "پرداخت در ازاي استفاده " در اختيار کاربران قرار ميگيرد. مسئله زمان بندي منابع در محيط محاسبات ابري، مسئله اي بسيار مهم ميباشد. در محيط محاسبات ابري هر کاربر ممکن است براي اجراي هر کار، با صدها منابع مجازي روبه رو شود. در اين حال ، تخصيص کارها به منابع مجازي توسط خود کاربر غيرممکن ميباشد. هدف از استفاده سيستم هاي محاسبات ابري به حداقل رساندن هزينه استفاده از منابع توسط فراهم آورندگان خدمات و نيز به حداکثر رساندن درآمد حاصل از سرويس دادن به برنامه هاي کاربردي مصرف کنندگان مي باشد. سيستم زمان بندي، وظايف مختلفي را در سيستم ابر جهت افزايش نرخ تکميل کار و افزايش بهره وري از منابع و در نتيجه افزايش توان محاسباتي، کنترل مي کند.
محاسبات ابري به شدت به مجازي سازي متکي است . مي توان گفت که ابرها شاخه هاي مجازي هستند. از اين رو زمان بندي وظايف در سرتاسر ماشين هاي فيزيکي غيريکنواخت مختلف يک وظيفه بحراني مي باشد. ما در اين مقاله به بررسي انواع آن ها ميپردازيم . روند ادامه مقاله به اين شرح ميباشد که در بخش دوم الگوريتم هاي زمان بندي موجود شرح داده شده اند در بخش سوم شبيه سازي الگوريتم ها ارائه شده و در آخر، مقاله با نتيجه گيري به پايان ميرسد.
٢ الگوريتم ها
٢-١ الگوريتم زنبور عسل
الگوريتم زنبور عسل اولين بار در سال ٢٠٠٥ توسعه يافت .
اين الگوريتم براي کارهاي بهينه سازي ترکيبي به کار ميرود. يک جمعيت زنبور عسل ميتواند در مسافت زيادي و نيز در جهت هاي گوناگون پخش شود تا از منابع غذايي بهره گيرد.
فرآيند جستجوي غذاي يک کلوني در طبيعت به وسيله زنبورهاي پيشاهنگ شروع ميشود. زنبورهاي پيشاهنگ به طور تصادفي بين گلزارها حرکت ميکنند و در اين پروسه سعي مي کنند کوتاه ترين و بهترين راه را پيدا کنند. براي بازگشت به کندو از نور آفتاب استفاده ميکنند. الگوريتم کلوني زنبورهاي مصنوعي الهام گرفته از رفتار زنبورها در طبيعت ميباشد مشابه با کلوني زنبورهاي طبيعي، اين الگوريتم نيز از سه گروه زنبورهاي کارگر، تماشاگر و پيشاهنگ تشکيل شده است . انتخاب تصادفي منابع غذايي و همچنين تبادل اطلاعات ، تصميم گيري در مورد منابع غذايي و انتخاب منابع غذايي توسط تماشاگران هر يک از زنبورهاي کارگر و تماشاگر ممکن است تغييراتي بر روي موقعيت منبع غذايي در حافظه خود ايجاد کنند و شايستگي آن را محاسبه کنند.
زنبورها دو نوع حرکت که يکي به سمت جلو و ديگري به سمت عقب را انجام ميدهند. زنبورها پس از پيدا کردن راه حل مسئله و يا راه حل جديد دوباره «حرکت به سمت عقب » را انجام ميدهند.
اين روند زماني پايان ميپذيرد که يک راه حل تقريبا کامل براي مسئله پيدا شود. از کلوني زنبورها براي مسائل ترکيبي بهينه سازي استفاده ميشود که در هر مرحله به ميزاني مسئله حل ميشود [١].
در فرمول (١) هر مرحله شامل يکسري مراحل از قبل انتخاب شده است .
٢-٢ الگوريتم ژنتيک
الگوريتم ژنتيک به عنوان يکي از روش هاي تصادفي بهينه يابي، توسط جان هالند در سال ١٩٦٧ ابداع شده است .
اين الگوريتم يک تکنيک برنامه نويسي است که از تکامل ژنتيکي به عنوان يک الگوي حل مسئله استفاده ميکند. مسئله اي که بايد حل شود ورودي است و راه حل ها طبق يک الگو کدگذاري ميشوند که تابع fitness نام دارد و هر راه حل کانديد را ارزيابي ميکند که اکثر آن ها به صورت تصادفي انتخاب ميشوند.
روند استفاده از الگوريتم هاي ژنتيک به صورت زير ميباشد: الف ) معرفي جواب هاي مسئله به عنوان کروموزوم ب ) معرفي تابع fitness ج ) جمع آوري اولين جمعيت د) معرفي عملگرهاي انتخاب ه ) معرفي عملگرهاي توليد مثل
در الگوريتم هاي ژنتيک ابتدا به طور تصادفي يا الگوريتميک ، چندين جواب براي مسئله توليد ميکنيم . اين مجموعه جواب را جمعيت اوليه ميناميم . هر جواب را يک کروموزوم ميناميم .
سپس با استفاده از عملگرهاي الگوريتم ژنتيک پس از انتخاب کروموزوم هاي بهتر، کروموزوم ها را باهم ترکيب کرده و جهشي در آن ها ايجاد ميکنيم . در نهايت نيز جمعيت فعلي را با جمعيت جديدي که از ترکيب و جهش در کروموزوم ها حاصل ميشود،
ترکيب مي کنيم [٢].
٢-٣ الگوريتم Backfill
در ادامه الگوريتم هاي زمان بندي منابع که در محيط محاسبات ابر استفاده شده است ، معرفي شده و اين الگوريتم ها با پارامترهاي زمانبنديشان در جدول ٥ سازماندهي ميشوند.
بهبود الگوريتم زمان بندي backfill با استفاده از روش تعادل مارپيچي در ابر: در الگوريتم backfill سنتي، کارهاي کوچک تا زمانيکه موجب نشود کارهاي بيشتري به تعويق افتد، به جلو ميروند. هم چنين کارهاي backfill براساس ترتيب ورودشان زمان بندي ميشود. اين نشان ميدهد که الگوريتم backfill سنتي اولويت را به کارهاي کوچک ميدهد. در اينجا زمانبند اولين کار ممکن را براي backfill انتخاب ميکند و منجر به قطعه قطعه شدن ميشود. با استفاده از روش تعادل مارپيچي BS کارها بين left و right در انباره کار قرار ميگيرند و سپس بر اساس الگوريتم backfill زمان بندي ميشوند. نتايج به دست آمده نشان ميدهند که بهره وري از منابع در الگوريتم بهبوديافته ، بهتر شده است .
الگوريتم پيشنهادي backfill بهبوديافته براي CLOUD METASCHEDULER است . در اين مطالعه backfill بهبوديافته با استفاده از روش BS براي حل مسائل زمان بندي در ابر، مورد بحث قرار گرفته است . اساسا اين روش مشتق شده از تحقيق در عمليات از مطالعات مديريت و ارزيابي الگوريتم backfill با استفاده از ابزارcloudsim مي باشد.
٢-٣-١ محدوديت در الگوريتم هاي BACKFILL
مفهوم اصلي محدوديت فراتر از الگوريتم هاي backfill با خود را دارد. با توجه به الگوريتم سطحي با حرکت رو به جلو کار کوچک تر تا زمانيکه آن کارهاي بيشتر ايجاد نمي کند به تعويق مي افتد. همچنين در backfill کارها طبق ترتيب زمان ورودشان زمان بندي مي شوند. اين نشان مي دهد که الگوريتم backfill سنتي اولويت را به کارهاي کوچک تر مي دهد. در اينجا زمانبند انتخاب مي کند اولين کار ممکن را براي backfill ودرنتيجه قطعه قطعه مي شود.
شکل ١. مثال از الگوريتم backfill سنتي
شکل ٢. ترتيب v شکل کار
يک مثال براي الگوريتم backfill در شکل ١ نشان داده شده است اولين کار در صف ,پردازنده به اندازه کافي براي اجرا دارد بنابراين آن فورا آزاد مي شود. سومين کار مي تواند در زمان ٠ آغاز شود توسط اولين پرش اما آن اولين کار را به تأخير مي اندازد.
دومين صف کار يک نقطه لنگر دارد پتانسيل ترتيب رسيدن يکي پس از ديگري است وشانسي در کارهاي backfill وجود ندارد.
به عنوان يک نتيجه هم زمان پاسخ و هم استفاده از سيستم بهبود پيدا کرده است . IBA حذف محدوديت هاي بيان شده بالا در الگوريتم backfill و کمک به دستيابي به کيفيت سرويس درcloud metascheduler است . در روش BS کارها مرتب شدند به عنوان V در شکل ٢ نشان داده شده است .
٢-٣-٢ بهبود الگوريتم IBA) BACKFILL)
IBA مجددا سفارش ترتيب ورود کارها با استفاده از روش BS را مي دهد. در روش BS کارها بين سمت چپ )L ( و راست )R) در منبع کار قرار داده مي شوند. در نظر بگيريد يک مجموعه کار J که دارد يک دنباله کار به ترتيب {j5,j4,j3,j2,j1} بطوريکه j٥=>j٤=>j٣=>j٢=>,j١. در اينجا همان مجموعه از کارها زمان بندي مي شود تا ثابت شود که IBA از منابع بهتر از
backfill استفاده مي کند.
قبل از الگوريتم backfill زير منظور صف با استفاده از روش BSاست . کارهاي اصلي ترتيب ورودشان {j٥ ,j٤ ,j٣ ,j٢ ,j١} است ترتيب کارها با توجه به پردازنده مورد نياز به صورت صعودي است مانند {j٥ ,j٢ ,j١ ,j٤ ,j٣}. طبق روش BS جاي بزرگ ترين کارJ٥ در آخرين موقعيت وj٢ در يکي مانده به آخر است . j١ در اولين موقعيت {j٢}R= {j١}L= . توجه داشته باشيد که j٥ گنجانده نشده درR. کارهاي باقيمانده در استخر کار {j٤ ,j٣} هستند. حالا sum_R =sum_l< از اين رو کار بزرگ J٤ از استخر کار به سمت چپ است . اينجا sum_R=sum_L< بنابراين جاي کار باقيمانده J٣ به سمت راست است . ترتيب کار جديد که با ادغام گرفتن R,L با آخرين موقعيت J٥ به عنوان ,j٣ ,j٤ ,j١} {j٥ ,j٢ است . ترتيب کار جديد تغيير مي کند که در شکل ٣ نشان داده شده است . اولين کار در صف ، پردازنده کافي براي اجرا دارد بنابراين فورا اجرا مي شود. دومين کار در صف در زمان ٠ آغاز مي شود توسط پرش از اول اما آن کار اول را به تأخير مي اندازد.
سومين کار درصف دارد يک نقطه لنگرگاه پتانسيل که پس از پايان کار اول است .
چهارمين کار در صف نيز آغازشده در زمان ٤، با پريدن از کار سوم که اين کار تأخير بيشتر دارد. در نهايت آخرين کار در صف منتشر شده است . قبلا در backfill سنتي اين امکان براي backfill تنها با يک کار واحد بود. در حال حاضر با استفاده از IBA در اينجا backfill دو کار را که از راه منابع بالا به دست آمده را استفاده مي کند [٣].
٢-٤ الگوريتم زمان بندي اولويت پويا بر زمان بندي
درخواست سرويس در محاسبات ابري:
هر واحد کاري را در واحد زمانبندياش ارزيابي مجدد مي نمايد و اولويت را دوباره محاسبه ميکند و در نهايت به حالت بهينه اي ميرسد. ساختار اصلي اين الگوريتم ترکيب شده از صف ها هست که تعداد آن ها بستگي به اولويت کارها دارد. به عنوان مثال ، يک کار ميتواند به سه گروه از واحدهاي کاري با اولويت ١، ٢ و ٣ تقسيم شود. در اين صورت زمانبند ميتواند سه صف ايجاد نمايد که هر کدام از صف ها مي تواند واحد کاري مربوطه خود را لود کند. قبل از اينکه صف ها براي زمانبند فرستاده شوند، آن ها يک اولويت اوليه دريافت مينمايند که اولويت بستگي به منبع کار و طراحي سيستم دارد.
هر کار به داخل زمانبند ميآيد و به واحدهاي کاري تقسيم ميگردد. هر واحد کاري با چرخه زماني Tin صف مربوطه اش قرار ميگيرد. واحد زمانبند واحد کاري جديد را به انتهاي صف مربوطه اش درج ميکند. هر واحد زمان بندي، پروسه زمان بندي را با چرخه زماني T انجام ميدهد. هدف از معرفي روش out ديناميک اين است که از واحدهاي کاري با اولويت کم که خيلي منتظر بمانند، اجتناب شود. براي دستيابي به اين هدف ، واحد زمان بندي در هر صف يک آستانه Ak قرار ميدهد که به معني زمان محدود براي منتظر ماندن يک کار در صف ميباشد و k نشان دهنده اولويت ميباشد. اگر يک واحد کاري در زمان Ak منتظر بماند، آن کار بايستي به صف با اولويت بالاتر منتقل شود.
و اگر در صف با اولويت بالاتر زمان Ak منتظر بماند، آنگاه بلافاصله به مؤلفه خلاصه منتقل ميشود [٤].
٢-٥ زمان بندي گردش علمي الاستيک براي محاسبات ابري :
بيش ترين ميزان موجود در الگوريتم زمان بندي گردش کار يک محيط محاسبه ، در نظر گرفته شده که در آن تعداد منابع محاسبه محدود است . محاسبه منابع معمولا در چنين محيطي امکان پذير نيست . اين منابع به محيط منتشر نمي شوند تا در گردش کار کامل اجرا شوند. براي پرداختن به اين مشکل در مرحله اول يک مدل از محيط ابر و يک نمودار گردش کار به نمايندگي براي چنين محيطي فرماليزه شده است . سپس پيشنهاد شده که الگوريتم زمان بندي گردش کار sheft، يک گردش کار الاستيک در محيط محاسبات ابري را زمان بندي کند.
آزمايش مقدماتي نشان مي دهد که sheft نه تنها نماينده بهتر چندين الگوريتم زمان بندي گردش کار در زمان اجراي گردش کار بهينه است اما همچنين منابع را به مقياس الاستيک در زمان اجرا قادر مي سازد.
مدل اوليه يک محيط محاسبات ابري است که منابع به تعدادي خوشه تقسيم شده اند. منابع با قابليت محاسباتي يکسان در يک گروه خوشه بندي ميشوند. منابع درون يک خوشه معمولا مانند شبکه هاي ميان ارتباطي اشتراک گذاري مي کنند بطوريکه نرخ انتقال داده آنها با يکديگر درون اين خوشه يکسان است .
همچنين منابع درون يک خوشه با منابع درون خوشه ديگر سرعت انتقال داده يکسان دارند. اين مدل با هردو محيط هاي محاسبات همگن و ناهمگن شرايط قابليت محاسبات و ارتباط داده ها را دارد.بعد يک گردش کار علمي که شامل مجموعه اي از وظايف و مجموعه اي از وابستگي داده اي در اين وظايف است رسمي شده است . سپس گراف بدون دور با وزن مستقيم نمونه اي هست براي نشان دادن يک گردش کار در محيط محاسبات که در آن رئوس گراف نشان دهنده ي مجموعه اي از وظايف و لبه هاي گراف نشان دهنده مجموعه اي از وابستگي داده اي است هزينه ارتباط تعيين شده با توجه به وزن لبه در گراف و هزينه محاسبات وظيفه (کار) تعيين شده توسط وزن راس گراف است [٥].
٣ شبيه سازي
Cloud Analyst 1-3
در اين مقاله Cloud Analyst به عنوان يک ابزار شبيه سازي استفاده شده است که يک ابزار مبتني بر cloud sim ميباشد.
براي مدل سازي و آناليز کردن محيط محاسبات ابري مورد استفاده قرار ميگيرد. Cloud Analyst برخلاف ساير نرم افزارهاي شبيه سازي، که با زبان هاي برنامه نويسي مختلف کار ميکنند يک ابزار شبيه سازي گرافيکي است .
يک تصويرکلي از رابط گرافيکي GUI از ابزار شبيه سازي Cloud Analyst در شکل (a)١ و معماري آن در شکل (b)١ نشان داده شده است [٦].
شکل ٥. تصوير(a)١ تصويرکلي از رابط گرافيکيو(b)١ و معماري CloudAnalyst.
٣-٢ شبيه سازي الگوريتم زنبور عسل
وظايف محاسباتي در استخر منابع پويا قرار داده ميشوند. که ماشين هاي مجازي آنلاين با توجه به شرايط مختلف از کاربر و يا سيستم به محاسبات ابري ميپردازد. سرويس درخواستي کاربران براي کاربردهاي گوناگون را ميتوان در هر مرکز داده ها باهر سرور در ابر انجام داد. مسيريابي درخواست سرويس به سرورهاي گوناگون براساس سياست هاي مديريت ابر و با توجه به بار از سرورهاي انفرادي، تراکم پايگاه ها و غيره انجام ميشود. در يک سيستم غير پيشگيرانه اغلب از سياست هاي دو اصل زمان بندي (FIFO) و (WRR) استفاده ميشود در نهايت با درجات مختلف از بارها بر روي هر ماشين مجازي اين سياست انجام ميشود که اين ممکن است منجر به اختلاف بين ماشين هاي مجازي در محاسبات بار به صورت مجازي شود به همين ترتيب اين باعث به وجود آمدن مشکلات اضافي از قبيل کاهش زمان پاسخ و کاهش منابع خواهد شد اين شرايط موجب ميشود که ما به تکنيک هاي متعادل کننده ي بار پويا که حل مشکل عدم تعادل بار بين ماشين هاي مجازي را انجام ميدهد اهميت زيادي دهيم .
تکنيک ها متعادل کننده ي بار در کاهش Makespan و زمان پاسخ موثر هستند [١].
به طور کلي Makespan را ميتوان به عنوان زمان انجام کار تعريف نمود. ما زمان تکميل وظيفه (کار) Ti در ماشين مجازي j
