بخشی از مقاله
چکیده
رایانش ابری به عنوان یکی از انواع سیستم های توزیع شده که دسترسی به منابع گوناگون را از طریق سرویس ها بر روی بستر اینترنت فراهم می کند روز به روز در حال گسترش می باشد.از آنجایی که وظیفه ابر پاسخگویی به حجم بالای وظایف دریافتی است مساله زمانبندی وظایف در رایانش ابری، مساله بسیار مهم می باشد که سعی دارد یک زمانبندی بهینه برای اجرای وظایف و تخصیص منبع بهینه مشخص نماید. روش های بسیاری به خصوص روش های اکتشافی و تکاملی برای این مساله ارائه گردیده است. دراین مقاله روشی با کمک آتوماتای یادگیر سلولی که یک مدل گسسته ریاضی است برای مساله زمانبندی وظایف در محاسبات ابری پیشنهاد شده است که با استفاده از یک شبکه از اتوماتای یادگیر و نسبت دادن آن با محیط ابر یک الگوریتم جدید ارائه شده است که بتوان یک زمانبندی مناسب را در زمان کمتری به دست آورد.
کلمات کلیدی: زمانبندی وظایف، محاسبات ابری، آتوماتای یادگیر سلولی
مقدمه
در×سالهای×اخیر×با×رشد×روز×افزون×حجم×اطلاعات×پردازشی، نیاز×به×سیستم×های×توزیع×شده×و×پردازش×موازی×بیشتر×از×قبل احساس×شده×است×؟محاسبات×گرید×از×دسته×سیستم×های× توزیع شده×و×زیر×بنای×سیستم×های×رایانش×ابری×می×باشند×؟×این فناوری×با×استفاده×از×زیر×ساخت×های×ارتباطی×و×شبکه×های کامپیوتری×امکان×دسترسی×به×انواع×منابع×را×به×صـورت×راه×دور× می دهد×؟منابع×محاسباتی×ناهمگون×سخت×افزاری×و×نرم×افزاری×را می×توان×بدون×محدودیت×جغرافیایی×به×هم×متصل×نمود×به×طوری که×کل×ساختار×سیستم×به×صورت×یـک×ماشـین×مجـازی× واحد×دیده شود،×،سپس×برنامه×های×کاربردی×بسیار×پیچیده×و×بزرگ×را×که×به توان×پردازشی×بسیار×بالا×و×به×حجم×عظیمی×از×داده×نیاز×دارند×بر روی×این×ماشین×مجازی×می×تـوان×اجـرا×نمـود×؟ در×واقع×هدف×این است×که×از×منابع×محاسباتی×سیستم×ها×زمانی×که×بی×کار×هستند برای×اجرای×کارهای عظیم×بهره×برده×شود)×یاری و فتحـی،.(1388 محاسـبات ابـری در×واقـع الگـویی×از× محاسبات×توزیع×شده،×مرکب×از تعداد×زیادی×منابع×و درخواست×با×هدف×به اشتراک×گذاری×منابع×به×صورت×سرویس،×بر×روی×بستر×اینترنت می×باشد.
سرویس×ها×در×محیط×محاسبات×ابری×،×در×سه×سطح×ارایه می×شوندْ ×
×
ٌ؟ × Software as a Service (SaaS) ٍ؟ × platform as a Service(PaaS)
َ؟ Infrastructure as a Service(IaaS)
زمان بندی ماشین های مجازی را به عنوان واحدهای زمان بندی، جهت تخصیص منابع فیزیکی ناهمگون برای اجرای وظایف می گیرد .هر ماشین مجازی یک واحد انتزاعی از ظرفیت های محاسباتی و ذخیره سازی تهیه شده در ابر می باشد. به دلیل خصوصیات پویای محیط محاسبات ابری وناهمگون بودن آن بحث زمان بندی وظایف به عنوان یک مسئله NP-Complete به شمار می آید . در چنین سیستمی پروسه ی زمان بندی می بایست به صورت اتوماتیک و بسیار سریع انجام گیرد(صدیق و عاصمی ،.(1191
کارهای مرتبط
برای حل مسائل NP-Complete اغلب از روش های اکتشافی و تکاملی استفاده می شود. برای حل مسئله زمانبندی وظایف در محیط توزیع شده از الگوریتم هایی مانند: Simulated Annealing،Tabu Search و Genetic Algorithm استفاده شده است((Bonomi,1990) .(Kumar at el. 2012 روشی بر مبنای الگوریتم FCFS ارائه کـرده است. (Ye at el.2010)زمانبندی FCFS با الگوریتم Backfilling را مورد استفاده قرار داده است. در (Wieczorek,2007) از الگوریتم ژنتیک برای حل مسئله زمانبندی اسـتفاده شده است. (Ku at el.2011) از الگوریتم کلونی مورچـه هـا بهـره جسـته و در (Kufmann,2001)الگـوریتمی بـا الهـام از رفتـار دسـته مـاهی هـا و پرنـدگان ارائـه شـده اسـت. در (Xu,2010) با الهام گرفتن از رفتار مولکول ها در واکنش های شیمیایی، بهینه سازی در زمانبندی کارها در گرید انجام گرفته است. و کارهای دیگری که اغلب از ترکیب الگـوریتم هـای فوق استفاده نموده اند مانند((Lee & wang, 2011 که از ترکیب الگوریتم ژنتیک با الگوریتم گداختگی استفاده کرده است.
تعریف اتوماتای یادگیر سلول:
اتوماتای سلولی شبکه ای است از سایت ها که هر کدام می تواند k حالت (وضعیت) داشته باشد. در هر سایت یک اتوماتون با حـالات محـدود قـرار دارد. در حالـت یـک بعـدی، هـر سایت دو همسایه نزدیک به خود دارد. در این حالت، وضعیت سایت I در زمان t+1 یعنی مطابق فرمول زیر به دست می آید:
×
تابع را قانون اتوماتای سلولی می نامیم. اتوماتون یک شی انتزاعی است که تعداد محدودی عمل را می تواند انجام دهد و هر عملی که انجام می دهد، توسـط محیطـی احتمـالی ارزیـابی می گردد و پاسخی به اتوماتون داده می شود. اتوماتون از این پاسخ استفاده نموده و عمل بعدی را انتخاب می کند. در طی این پروسه اتوماتون یاد می گیـرد کـه چگونـه بهتـرین عمـل را انتخاب نماید. بطور کلی هر اتوماتون یادگیرنده از دو بخش زیر تشکیل می گردد.
الف)اتوماتونی با تعداد محدودی عملیات و محیطی احتمالی که با اتوماتون در حال عمل و عکس العمل هستند. ب)الگوریتم یادگیری که به وسیله آن اتوماتون یاد می گیرد که بهترین عمل را انجام دهد.
