الگوریتم های زمانبندی وظایف در رایانش ابری

زمانبندی وظایف در رایانش ابری

جهت تخصیص منابع و حفظ تعادل بار بین ماشین های مجازی در رایانش ابری روشهای مختلفی مطرح شده است. برخی از این روشها عبارتند از الگوریتم ژنتیک، الگوریتم کلونی زنبور عسل، الگوریتم کلونی مورچگان، جهش قورباغه، الگوریتم وال، سنجاقک، الگوریتم قطه های آب و غیره. از این رور هر کدام از این روشها دارای مشکلاتی در زمینه ایجاد تعادل بار و تخصیص منابع هستند. اصلی ترین چالشی که این الگوریتم ها با آن مواجه هستند، ایجاد تعادل بار بین ماشین های مجازی به منظور تخصیص منابع در دیتاسنترهای رایانش ابری است.

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

الگوریتم های زمانبندی وظایف در رایانش ابری

در این بخش به معرفی برخی از مهمترین الگوریتم های زمانبندی وظایف در رایانش ابری پرداخته خواهد شد.

الگوریتم های زمانبندی بر اساس PSO

پديده PSO، براي اولين بار توسط کندي و ابرهارت در سال ۱۹۹۵ مطرح شد. PSO يک الگوريتم محاسبه اي تکاملي الهام گرفته از طبيعت و براساس تکرار مي‌باشد. منبع الهام اين الگوريتم، رفتار اجتماعي حيوانات، همانند حرکت دسته جمعي پرندگان و ماهي‌ها بود. از اين جهت که PSO نيز با يک ماتريس جمعيت تصادفي اوليه، شروع مي‌شود، شبيه بسیاری دیگر از الگوریتم های تکاملی همچون الگوريتم ژنتيک پيوسته است.

برخلاف الگوریتم ژنتیک ، PSO هيچ عملگر تکاملي همانند جهش و تزويج ندارد. هر عنصر جمعيت، يک ذره ناميده مي‌شود (که همان معادل کروموزوم در GA) است. در واقع الگوريتم PSO از تعداد مشخصي از ذرات تشکيل مي شود که به طور تصادفي، مقدار اوليه مي گيرند. براي هر ذره دو مقدار وضعيت و سرعت، تعريف مي شود که به ترتيب با يک بردار مکان و يک بردار سرعت، مدل مي‌شوند[۱].

الگوریتم ژنتیک

الگوریتم ژنتیک برای اولین بار در سال ۱۹۷۵ توسط Holland و برپایه ی اصل تکامل که در طبیعت مشاهده می گردد بنا نهاده شده است. در الگوریتم ژنتیک هر کروموزوم بیانگر یک راه حل ممکن برای مسئله می باشد و متشکل رشته ای از ژن ها است. در ابتدا جعیت به صورت تصادفی برای ایجاد نقطه ی شروع الگوریتم انتخاب می شوند. یک تابع برازش برای بررسی تناسب کروموزوم و محیط تعریف می شود. تابع برازش می تواند بر اساس make span, Flow time و یا هزینه ی اجرایی بنا نهاده شده باشد.
بر اساس مقدار برازش، کروموزوم ها انتخاب شده و عملگر های تزویج و جهش بر آنها اِعمال شده و نسل جدید جمعیت تولید می شوند. کیفیت هر نسل بوسیله ی تابع برازش ارزیابی می شود. این فرایند تا تولید نسل دلخواه ادامه می یابد[۲].

الگوریتم های بر پایه ی کلونی مورچگان

این الگوریتم ها از رفتار واقعی مورچه ها در یافتن کوتاهترین مسیر بین کلونی و منابع غذا، الهام گرفته شده است. این روش نوین در سال ۱۹۹۲ توسط Dorigo به عنوان رساله ی دکترای وی معرفی شد و در اصل سیستم مورچه نامیده می شد. مورچه ها در مسیر طی شده ردپایی با استفاده از ماده شیمیایی خاصی به نام فرومون برجای می گذارند. با گذشت زمان و عبور سایر مورچه ها، درمسیرهای بهینه غلظت فرومون بیشتر شده و مورچه های بعدی مسیر بهتر را تشخیصص می دهند[۳].
روش ACO برای حل مسائل بهینه سازی گسسته که نیازمند یافتن یک مسیر به هدف می باشند، مفید است. مسائل مختلفی از قبیل مسئله ی کوله پشتی چند بُعدی، زمانبندی کارها در محیط Grid ، و بسیاری دیگر با استفاده از این روش با موفقیت حل شده است.

الگوریتم LCA

این الگوریتم که اخیرا توسط دکتر علی حسین زاده کاشان برای بهینه سازی های سراسری و بر پایه ی تقلید فرایند قهرمانی در رقابت های ورزشی ارائه شده است. روش LCA می تواند به صورت زیر بیان گردد:
یک تعداد نقش های مجزا به عنوان تیم های ورزشی در یک لیگ مصنوعی برای چندین هفته با هم به رقابت می پردازند. براساس زمانبندی هفتگی لیگ، تیم ها دو به دو بازی می کنند و خروجی بازی آنها به صورت برد، باخت و یا مساوی تعیین می گردد. هر تیم دارای ترکیب و چینش خاصی بوده که دارای مقدار برازش بخصوصی به خود می گیرد. با ثبت و نگهداری مسیر وقایع هفته ی گذشته، هر تیم برای تغییرات مورد نیاز در چینش و نحوه ی بازی خود برای بازی هفته آینده تصمیم می گیرد و مسابقات پس از تعدادی فصل ( شرط توقف ) پایان می پذیرد[۴].

LCA الگوریتمی بر مبنای جمعیت می باشد که در آن تیم ها همانند ذرات در PSO با تفاوت اندک در نحوه ی انجام جستجوی آنها هستند. روشی که برای ایجاد راه حل های جدید در LCA استفاده می شود، بسیار شبیه فرایند آنالیز بازی است که توسط مربیان تیم برای طراحی ترکیب مناسب برای بازی آینده بکار می رود. به عنوان نمونه در یک انالیز بازیف مربیی تیم چینش تیم خود را بر اساس تجربه خود از مسابقه و همچنین سبک بازی تیم حریف اصلاح می کند. الگوریتم LCA الگوریتمی بر مبنای جمعیت و چارچوبی برای بهینه سازی سراسری در فضای جستجوی پیوسته می باشد[۴].

الگوریتم سنجاقک

 الگوریتم سنجاقک با توجه به دیدگاه رینولدز، رفتار ذرات شامل سه اصل مهم می باشد که عبارتند از: ۱٫ جدایی: این عملگر اشاره به عدم تماس دو یا چند فرد یا ذره در یک فضا دارد.۲٫ ترازبندی: عدم تجاوز سرعت ذرات یا اشیا نسبت به سایر همسایه ها در یک فضای واحد.۳٫ انسجام: این عملگر نیز به این اشاره دارد که افراد به سمت به هدف واحد یا مرکز مورد نظر سوق پیدا کنند.هدف اصلی هر ذره در سناریو فوق زنده ماندن است. بنابراین همه افراد یا ذرات باید به سمت منبع غذایی جهش پیدا کرده و از وابستگی به موارد دیگر خود داری نمایند. با توجه به این دو رفتار ذرات، ۵ عامل اصلی در بروز رسانی موقعیت ذرات وجود دارد که در شکل زیر نشان داده شده است[۵].

خدمات رایان پیپر جهت مشاوره انجام پروپوزال، پایان نامه و پیاده سازی مقاله در زمینه رایانش ابری

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

جهت دانلود انواع الگوریتم های زمانبندی وظایف در رایانش ابری می توانید به سایت ناب لرنینگ مراجعه نموده و کلیه الگوریتم های زمانبندی وظایف شبیه سازی شده را مشاهده نمایید. 

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

[۱]. Suraj Pandey, LinlinWu, Siddeswara Mayura Guru, Rajkumar Buyya, “A Particle Swarm Optimization-based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments”, Cloud Computing and Distributed Systems Laboratory, 2010.

[۲]. Suraj Pandey, LinlinWu, Siddeswara Mayura Guru, Rajkumar Buyya, “A Particle Swarm Optimization-based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments”, Cloud Computing and Distributed Systems Laboratory, 2010.

[۳]. Shaminder Kaur, Amandeep Verma, “An Efficient Approach to Genetic Algorithm for Task Scheduling in Cloud Computing Environment”, I.J. Information Technology and Computer Science, 2012, pp. 74-79.[13]. Medhat Tawfeek, Ashraf El-Sisi, “Cloud Task

[۴]. Scheduling Based on Ant Colony Optimization”, The International Arab Journal of Information Technology, Vol. 12, No. 2, 2015. Shafii Muhammad Abdulhamid, Muhammad Shafie Abd, Latiff and Ismaila Idris, “TASKS SCHEDULING TECHNIQUE USING

[۵].LEAGUE CHAMPIONSHIP ALGORITHM FOR MAKESPAN MINIMIZATION IN IAAS CLOUD”, Faculty of Computing, 2015. Seyedali Mirjalili, “Dragonfly algorithm: a new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems”, Neural Comput & Applic DOI 10.1007/s00521-015-1920-1, 2015.

ما منابه هر مطلب را برای شما در این صفحه قرار داده ایم که خدمت رایگان خود را به کلیه دانشجویان و اساتید محترم به اثبات رسانیم.

هر مشکلی دارید یا هر سوالی در ذهن دارید می توانید از طریق فرم زیر در عرض چند ثانیه شماره تماستان را وارد نموده و رایگان مشاوره بگیرید.

الگوریتم های زمانبندی وظایف در رایانش ابری

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *