پروپوزال پیاده سازی زمانبندي وظایف در رایانش ابري با استفاده از الگوریتم کلونی مورچگان بهبود یافته

یکی از چالشهای موجود در سیستمهای محاسبات ابری مسئله زمانبندی وظایف یا اختصاص منابع به درخواست های سیستم می باشد. دلایل متعددی مانند ناهمگونی و پویایی خصوصیات منابع و درخواست ها در محیط محاسبات ابری باعث شده است که این موضوع یک مسئله NP-COMPLET شده باشد(آرش قربان نیا دلاور و یلدا آرین،1391(. به جریان کار و اجرای وظایف برنامه کاربردی، گردش کاری می گویند. فرآیند نگاشت وظایف به منابع محاسباتی برای اجرای وظایف در یک گردش کاری زمانبندی گردش کاری نامیده می شود(زینب شمس، احمد فراهی، 1391).  الگوریتم های زمانبندی نقش بسیار مهمی در محاسبات ابری دارند چرا که هدف زمانبندی این است که زمان پاسخ را کاهش دهند و بهره برداری از منابع را بهبود بخشد. برای این منظور الگوریتم های زمانبندی مختلفی وجود دارد که در این پایان نامه به بررسی 2 مورد از  آنها می پردازیم و مزایا و معایب آنها را بررسی می کنیم. 

به طور کلی می توان الگوریتم های زمانبندی را به صورت زیر دسته بندی کرد : 

• محلی(Local) / سراسری (Global): در سیستم زمانبندی محلی می توان اجرای پروسه های مختلف را برروی یک پردازنده خاص مدیریت کرد.در صورتی که در حالت سراسری و کلی می توان با استفاده از اطلاعات مربوط به پروسه ها و پردازنده ها شاخص های بهینه سازی را به آسانی بهبود بخشید.

• ایستا (Static) / پویا (Dynamic): در روش ایستا فرض بر این است که منابع ثابت بوده و در زمانی که قرار است برنامه بر روی آنها اجرا شود در دسترس قرار می گیرد. در حالی که در حالت پویا منابع به صورت شناور عمل می کند و هر آن امکان دارد حتی تعداد آنها تغییر کند. 

• بهینه(Optimal) / نیمه بهینه(Suboptimal): روش بهینه سعی دارد یک هدف را به بهترین شکل برآورده سازد. صورتی که روش های نیمه بهینه تنها یک هدف را لحاظ نمی کند بلکه سعی در بهبود نسبی چندین هدف به صورت توام دارد. 

• تقریبی(Approximate) / اکتشافی (Heuristic): در روش تقریبی از یک واحد و معیار تعریف شده برای تحمیل بهینه بودن استفاده می شود. هرگاه مقدار مورد نظر برآورده شد هدف نیز حاصل گردیده است. در روش اکتشافی با فرض های واقعی در مورد سیستم و گسترده کردن دامنه جستجو، ضمن لحاظ کردن اطلاعات سیستمی نظیر پردازنده ها، بار کاری و غیره تمام راه حل های ممکن را یافته و جواب نزدیک به بهینه را پیدا می کند. این روش در الگوریتم های زمانبندی بیشتر استفاده می شود. از جمله این الگوریتمها می توان به MIN-MIN و MIN – MAX  اشاره کرد.

• توزیع شده(Distributed) / متمرکز(Non-Distributed): در روش های توزیع شده مسئولیت اصلی به عهده یک یا چند زمانبند توزیع شده است. روش متمرکز دو مشکل اساسی دارد که عبارتند از تحمل خطا و غیرقابل گسترش بودن.

• همکار(Cooperative) / غیر همکار(Non-Cooperative) : در صورتی که ارتباط گره ها به صورت غیر همکار باشد زمانبندهای منفرد به تنهایی عمل می کند و تصمیمات زمانبندی را با توجه به هدف بهینه سازی خودشان بدون توجه به دیگر بخش ها انجام می دهد. در حالت همکار هر زمانبند مسئولیت خاص خود را در زمانبندی کارها دارد. اما تمام زمانبندها در جهت هدف کلی سیستم عمل می کند(محسن یوسفی نژاد، امین مهران زاده،1391).

نمونه های از الگوریتم های مورد استفاده در محیط ابری شامل الگوریتم های FCFS، Round Robin، موازنه بار فرصت طلبانه OLB، MIN-MIN، MIN-MAX ،ژنتیک و کلونی مورچگان می باشد. که به طور خلاصه بعضی از آنها را شرح می دهیم:

الگوریتم FCFS از قدیمی ترین و رایج ترین الگوریتم های زمانبندی است، که وظایف را به ترتیب ورودشان به منابع اختصاص می دهد. مشکل این روش این است که اگر وظایف طولانی در میان وظایف موجود باشد، زمان پاسخ کارها بسیار زیاد می شود و توازن بار را بر روی منابع در نظر نمی گیرد(محسن یوسفی نژاد، امین مهران زاده،1391). 

هدف الگوریتم MIN-MIN  کاهش تکمیل زمان وظایف با اختصاص زود هنگام وظایف کوچک به منابع می باشد. در این الگوریتم ابتدا زمان تکمیل همه وظایف بر روی همه منابع محاسبه شده و در یک ماتریس m*n قرار داده می شود. هدف این الگوریتم رسیدن به کمترین زمان پاسخ است و برای رسیدن به این هدف ابتدا وظایفی با زمان تکمیل کم و سپس وظایفی با زمان بیشتر را زمانبندی می کنند(محسن یوسفی نژاد، امین مهران زاده،1391). 

الگوریتم MIN-MAX از دو گام برای نگاشت هر وظیفه استفاده می کند. گام اول از کمترین زمان اتمام و گام دوم از کمترین زمان اجرا به عنوان معیار استفاده می کند. ایده در این روش، زوج ماشین و وظیفه، ازگام اول انتخاب می شود به طوری که ماشین می تواند وظیفه مربوط به خود را به طور موثر با زمان اجرای کمتر در مقایسه با دیگر ماشین ها اجرا کند(محسن یوسفی نژاد، امین مهران زاده،1391). 

الگوریتم کلونی مورچه به عنوان یک راه حل چند عامله (Multi Agent) برای مسائل مشکل بهینه سازی ارائه شده است.  مورچه ها با وجود کور و کم هوش بودن می توانند با استفاده از فرومونی که در حین حرکت از خود به جا می گذارند کوتاهترین مسیر از خانه تا غذا را پیدا کنند این نوع رفتار مورچه ها دارای نوعی هوشمندی توده ای است که عناصر رفتاری تصادفی دارند و بین آنها هیچ  نوع ارتباط مستقیمی وجود ندارد. دو "ویژگی تبخیر شدن فرومون" و " احتمال تصادف" به مورچه ها امکان پیدا کردن کوهتاهترین مسیر را می دهد. این دو ویژگی باعث انعطاف در حل هرگونه مسئله بهینه سازی می شود. از آنجایی که این الگوریتم نوعی الگوریتم بهینه سازی است بنابراین از آن می توان در زمانبندی وظایف استفاده کرد. الگوریتم کلونی مورچه از قانون متناسب تصادفی برای متعادل کردن بار سیستم ورودی با تکمیل تمام کارها استفاده می کند. در صورت امکان، طبق وضعیت محیط رفتار می کند. برای استفاده موثر از منابع، الگوریتم مورچه متعادل پیشنهاد شده است که بار کاری را با کوچک کردن زمان تکمیل متعادل می نماید. مزیت این روش این است که بار روی منابع متعادل می گردد و برای توزیع بار وضعیت محیط را نیز در نظر می گیرد و همچنین زمان تکمیل پایینی دارد. از معایب این الگوریتم می توان عدم عدالت و زمان اجرای بالا را برشمرد(پایان نامه الگوریتم کلونی مورچگان، زهره اروندان).  

الگوریتم ژنتیک (GA) تکنیکی است که برای جستجو در فضاهای حل بزرگ استفاده می شود. روشهاي هوش مصنوعی مانند محاسبات تکاملی به ویژه در شاخه الگوریتم ژنتیک به دلیل هوش و موازي سازي ضمنی اش مورد توجه افراد مختلف قرار گرفته است. GA به طور گسترده اي براي حل مشکل زمانبندي منابع در مقیاس بزرگ، سیستمهاي خوشه ای  غیرخطی و بدست آوردن اثرات ایده آل، بکار گرفته شده است. هنگام استفاده ازGA کلاسیک براي حل مشکلاتی مانند دانه بندي درشت، ابعاد بالا و داده هاي بزرگ، تنظیم مسائل بهینه سازي مانند همگرایی ناقص، همگرایی آهسته و نبودن هیچ همگرایی، اجتناب ناپذیر است. بنابراین محققان انواع مختلفی از الگوریتم ژنتیک بهبود یافته را پیشنهاد دادند(محسن یوسفی نژاد، امین مهران زاده،1391).

می توانیم اینگونه بیان کنیم که الگوریتم ژنتیک ابزاري است که توسط آن ماشین می تواند مکانیزم انتخاب طبیعی را شبیه سازي نماید این عمل با جستجو در فضاي مسأله جهت یافتن جواب برتر و نه الزاماً بهینه صورت می پذیرد  الگوریتم ژنتیک را می توان یک روش جستجوي کلّی نامید که از قوانین تکامل بیولوژیک طبیعی تقلید میکند. در واقع الگوریتم هاي ژنتیک از اصول انتخاب طبیعی داروین براي یافتن فرمول بهینه جهت پیش بینی یا تطبیق الگو استفاده می کنند. الگوریتم هاي ژنتیک اغلب گزینه خوبی براي تکنیک هاي پیش بینی بر مبناي رگرسیون هستند.

در این پایان نامه قصد داریم الگوریتم های ژنتیک و کلونی مورچگان را در زمانبندی محاسبات ابری با هم مقایسه و بهترین روش را در میان آن ها انتخاب کنیم. 

اهداف مشخص تحقيق (شامل اهداف آرماني، کلی، اهداف ويژه و كاربردي): 
انتظار می رود در پایان کار الگوریتم های کارآمدی همچون الگوریتم ژنتیک و الگوریتم کلونی مورچه ها با توجه به معیارهای زمانبندی دقیق تر آن ها، راهبردهای بهتری در محاسبات ابری تشخیص داده شوند.