بخشی از مقاله
چکیده
پهنای باند شبکهها و تکنولوژی سختافزار آنها به سرعت در حال توسعه بوده و باعث پیشرفت اینترنت شده است. مفهومی جدید، به نام رایانش ابری، از میزبانهای با توان پایین برای رسیدن به قابلیت استفاده بالا استفاده میکند. امروزه سرویس رایانش ابری به یکی از متدولوژیهای توسعهپذیر در صنعت کامپیوتر مبدل شده است. رایانش ابری، یک فناوری مبتنی بر تقاضا است، به طوریکه تخصیص منابع پویا و انعطافپذیر را برای خدمات تضمین شده و قابل اعتماد، به طریق پرداخت هزینه به هنگام استفاده از خدمات به عموم ارائه میدهد . ویژگی منحصر به فرد این فناوری این است که میتوان به صورت همزمان، به هر تعداد از خدمات مبتنی بر رایانش ابری، توسط هر تعداد از کاربر دسترسی پیدا کرد. رایانش ابری، سبک محاسباتی جدیدی است که به سبب پیشرفتهای بیشمار آن مانند ارائه سرویس برحسب تقاضا، پرداخت در ازای استفاده و اشتراک منابع در بین سایر سبکهای محاسباتی برتری پیدا کرده و مشتریان و تولیدکنندگان بسیاری را به خود جلب کرده است.
محاسبات ابری یک تکنولوژی در حال ظهور است، با توجه به اینکه منطق محاسبات ابری براساس پردازش موازی سیستمها است بنابراین سازوکار زمانبندی یکی از مهمترین نقشهای حیاتی را در محیط محاسبات ابری ایفا میکند و هسته محاسبات ابری، بدون زمانبندی مفهومی ندارد. در این مقاله با استفاده از الگوریتم بهینهسازی مبتنی بر آموزش و یادگیری زمانبندی وظایف در محیط ابر در جهت کمینهسازی زمان تکمیل وظایف انجام شده است و نتایج با الگوریتم بهینهسازی کلونی مورچگان مقایسه شده است. نتایج حاکی از این است که الگوریتم بهینهسازی مبتنی بر آموزش و یادگیری با زمان تکمیل وظایف 124 و 208 به ترتیب بهازای 20 و 30 وظیفه بهترین عملکرد را در زمانبندی وظایف در محیط رایانش ابری دارد.
واژگان کلیدی: زمانبندی وظایف، محاسبات ابری، الگوریتم بهینهسازی مبتنی بر آموزش و یادگیری.
مقدمه
واژه ابر واژهای است استعاری که به اینترنت اشاره میکند و در نمودارهای شبکههای رایانهای نیز از شکل ابر برای نشاندادن شبکه اینترنت استفاده میشود. دلیل تشبیه اینترنت به ابر در این است که اینترنت مانند ابری جزئیات فنیاش را از دید کاربران پنهان میسازد و لایهای از انتزاع را بین این جزئیات فنی و کاربران به وجود میآورد. به عنوان مثال آنچه یک ارائه-دهنده سرویس نرمافزاری رایانش ابری ارائه میکند، برنامههای کاربردی تجاری برخط است که از طریق مرورگر وب یا نرم-افزارهای دیگر به کاربران ارائه میشود. "ابر"، روزبهروز در حال رشد و توسعه است و البته با چالشهای بسیاری نیز مواجه است که یکی از آنها، مبحث "زمانبندی" است. زمانبندی، تکنیکی است که برای ارتقای مجموع زمان اجرای یک وظیفه مورد استفاده قرار میگیرد. پروسه زمانبندی در تکنولوژی ابر، مسئول انتخاب بهترین منابع مناسب برای اجرای وظیفه است و برای این منظور، تعدادی پارامتر را مدنظر قرار میدهد.
زمانبندی مؤثر و کارآمد میبایست به گونهای ارائه شود که هم "کاربر" و هم "ارائهدهنده سرویس"، منتفع شوند - . - Chawla & Bhonsle, 2012 مؤفقیت ابرها تا حدودی به استفاده از "مجازیسازی" به عنوان تکنولوژی پایه و اساسی ابر بازمیگردد. مجازیسازی و یا کنترلر تعبیهشده PC تکنولوژی است که امکان اجرای دو و یا تعداد بیشتری سیستمعامل را در کنار یکدیگر فراهم میآورد. مجازیسازی، به استفاده مؤثر و کارآمد از منابع کمک مینماید و یک سیستم مؤثر و کارآمد را ایجاد میکند. رایانش ابری به شدت به مفهوم "مجازیسازی" متکی است. ابرها، خوشههای مجازی هستند. بنابراین، زمانبندی مؤثر وظایف و ماشینهای مجازی میان انواع ماشینهای فیزیکی ناهمگن، یک وظیفه بسیارمهم محسوب میشود از مفهوم زمانبندی وظیفه به منظور تخصیص وظایف به ماشینهای مجازی در زمانهای مختلف، استفاده میشود.
مسأله زمانبندی وظایف در رایانش ابری به دلیل طبیعت پویای منابع و همچنین درخواستهای مختلف کاربران یک مبحث چالش برانگیز محسوب میشود. هدف اصلی الگوریتم زمانبندی وظایف این است تا کارایی و کیفیت سرویس را بهبود بخشد و همزمان نیز کارایی و مطلوبیت وظایف را حفظ نموده و زمان تکمیل وظایف را کاهش دهد. هدف از یک استراتژی کارآمد و مؤثر زمانبندی وظایف، کاهش زمان تکمیل وظایف به کمترین مقدار ممکن است؛ به گونهای که اجرای وظایف کاری پیشنهاد شده، در حداقل زمان ممکن صورت پذیرد. در این راستا، استراتژیهای گوناگون زمانبندی وجود دارند که میبایست این موارد را تأمین نمایند - . - Kalra & Singh, 2015 زمانبندی وظایف یک فرآیند کلیدی در زیرساخت به عنوان سرویس است که هدف آن اجرای درخواستهای وارد شده به سیستم بر روی منابع، به شیوهای کارآمد با درنظرگرفتن سایر خصوصیات محیط ابر میباشد.
زمانبندی وظایف، ماشینهای مجازی را به عنوان واحدهای زمانبندی جهت تخصیص منابع فیزیکی برای اجرای وظایف در نظر میگیرد. هر ماشین مجازی یک واحد انتزاعی از ظرفیتهای محاسباتی و ذخیرهسازی تهیهشده در ابر است. دلیل خصوصیات پویای محیط محاسبات ابری و ناهمگون بودن آن بحث زمانبندی وظایف را به عنوان یک مسأله NP-Complete به شمار میآید. در چنین سیستمی پروسهی زمانبندی میبایست بهصورت اتوماتیک و بسیار سریع انجام گیرد - . - Danielson, 2008 بنابراین در این مقاله قصد داریم با بهبود الگوریتم بهینهسازی مبتنی بر آموزش و یادگیری مسأله زمانبندی وظایف در محاسبات ابری را حل کنیم. ادامه ساختار این مقاله به این صورت است که در بخش اول مروری بر پیشینه تحقیقات انجام شده خواهیم داشت و در بخش دوم الگوریتمهای فراابتکاری بیان میشوند. در بخش سوم مدل پیشنهادی و در بخش چهارم ارزیابی نتایج استفاده از الگوریتمهای فراابتکاری در جهت حل مسأله ارائه شده و در نهایت در بخش آخر نتیجهگیری انجام میشود.
-1 مروری بر پیشینه تحقیق
یو در سال 2009 به زمانبندی وظایف بیدرنگ به وسیله الگوریتم ژنتیک چندهدفه پرداخته است. وظایف بیدرنگ فعالیتهای محاسباتی با محدودیتهای زمانی هستند و به دو دسته سخت و نرم تقسیم میشوند. در وظایف بیدرنگ سخت تأخیر فاجعه بار میتواند باشد. هدف الگوریتمهای زمانبندی بیدرنگ سخت درنظرگرفتن همه مهلتهای زمانی وظایف است. در مورد وظایف بیدرنگ نرم مهلت زمانی وظایف حیاتی نیست. در این تحقیق یک الگوریتم زمانبندی برای وظایف بیدرنگ نرم با استفاده از الگوریتم ژنتیک چندهدفه روی سیستمهای چندپردازندهای معرفی شده است. در این تحقیق فرض شده که وظایف ارتباط اولویتی دارند و میتوانند بر روی محیط چندپردازندهای همگن اجرا شوند. هدف الگوریتم زمانبندی معرفیشده کمینه-سازی دیرکرد در تمام فرایندها و تعداد پردازندهها است - . - Yoo , 2009 ژائو و همکاران در سال 2009 به زمانبندی وظایف مستقل مبتنی بر الگوریتم ژنتیک در محاسبات ابری پرداختند.
در این تحقیق مشخص شده که مسأله زمانبندی یک مسأله NP-Complete است و نقش کلیدی در سیستمهای محاسبات ابری بازی میکند. در این مقاله یک الگوریتم بهینهسازی مبتنی بر الگوریتم ژنتیک برای زمانبندی مستقل و تقسیم وظایف منطبق بر محاسبات مختلف معرفی شده است. در این مقاله سیستمها همگن در نظر گرفته شده است. الگوریتم ژنتیک برای حل این مسأله پیشنهاد شده است و نتایج آن با الگوریتمهای دیگر مقایسه شده است - . - Zhao, Zhang, Liu, Xie, & Hu, 2009 پیج و همکاران در سال 2010 به تخصیص وظایف پویا با استفاده از الگوریتم ژنتیک در سیستم توزیعشده همگن پرداختند. در این تحقیق یک الگوریتم فراابتکاری تکاملی برای زمانبندی وظایف در سیستم توزیعشده همگن ارائه شده است. الگوریتم ژنتیک با هشت ابتکار جدید ترکیب شده است تا زمان اجرای کل را کمینه کند.
الگوریتم بر روی دسته وظایف غیرنگاشت شده عمل میکند و بهطور انحصاری وظایف را با نگاشت-های مجدد به پردازندهها تخصیص میدهد. الگوریتم روی سیستم توزیعشده جاوا پیادهسازی شده است و با شش مسأله در حوزههای بیوانفورماتیک، مهندسی پزشکی، علوم کامپیوتر و کریپتوگرافی ارزیابی شده است. نتایج روی 150 پردازنده همگن نشان میدهد که الگوریتم کارایی بهتر نسبت به الگوریتمهای فراابتکاری دیگر دارد - . - Page, Keane, & Naughton, 2010 سلورانی و همکاران در سال 2010 به بهبود هزینه مبتنی بر الگوریتم در زمانبندی وظایف در محاسبات ابری پرداختند. هدف این تحقیق زمانبندی گروهی وظایف در محاسبات ابری است که منابع هزینهها و کارایی مختلف دارند. روش پیشنهادی در محاسبات باعث بهبود هزینه مبتنی بر الگوریتم زمانبندی برای ساخت نگاشت مفید از وظایف به منابع در دسترس در ابر است.
این الگوریتم زمانبندی معیارهای هزینه منبع و کارایی محاسبات را در نظرگرفته است - . - Selvarani & Sadhasivam, 2010 داتا و همکاران در سال 2011 یک الگوریتم ژنتیک برای زمانبندی کار در محاسبات ابری ارائه دادند. این تحقیق به نگاشت کارهای کاربران به منابع محاسباتی برای رسیدن به حداکثر سود میپردازد و اینکه مسأله زمانبندی متعلق به خانواده مسائل ترکیبی است و برنامهنویسی خطی راهحلی برای آن ندارد و هر قانون ساده و یا الگوریتمی قادر به یافتن پاسخ بهینه آن نیست. این تحقیق یک راهحل با استفاده از الگوریتم ژنتیک ارائه میدهد. یک مدل برای محیط محاسبات ابری پیشنهاد میدهد که مبتنی بر الگوریتم ژنتیک و عملگرهای تقاطع مانند PMX، OX، CX و عملگرهای جهش است تا بهترین زمانبندی را ارائه دهد. روش پیشنهادی تضمین میکند که بهترین پاسخ را تولید میکند - . - Dutta & Joshi, 2011
کومار و همکاران در سال 2012 به زمانبندی وظایف مستقل در محاسبات ابری با الگوریتم ژنتیک بهبود یافته پرداختند. هدف این تحقیق یک الگوریتم زمانبندی جدید است که یک نسخه بهبودیافته از الگوریتم ژنتیک را ارائه میدهد. در روش پیشنهادی الگوریتمهای زمانبندی Max-Min و Min-Min با الگوریتم ژنتیک استاندارد ادغام شدهاند و Min-Min و Max-Min پیشنهاد شده برای بهبود الگوریتم ژنتیک مقایسه شده و به وسیله گراف نمایش داده شده است - . - Kumar & Verma, 2012 بهوی و همکاران در سال 2013 بر روی زمانبندی وظایف در محاسبات ابری با استفاده از الگوریتم بهبود یافته Max-Min پژوهشی انجام دادند. در این تحقیق الگوریتم Max-Min در جهت کاهش زمان تکمیل وظایف بهبود یافته است. در الگوریتم پایه Max-Min وظایف با
