بخشی از مقاله
چکیده
رایانش ابری، سبک محاسباتی جدیدی است که به سبب پیشرفت های بی شمار آن مانند ارائه سرویس بر حسب تقاضا، پرداخت در ازای استفاده و اشتراک منابع در بین سایر سبک های محاسباتی برتری پیدا کرده و مشتریان و تولیدکنندگان بسیاری را به خود جلب کرده است. در چنین محیط توزیع شده ای، زمانبندی درخواست های کاربر با هدف کیفیت بخشی ارائه سرویس در رایانش ابری چالش مهم و کلیدی است.
به جهت بررسی این چالش در این مقاله، از نظریه بازیها به عنوان راه حل بالقوه برای مدل کردن مسئله تخصیص و زمانبندی در سیستم ابری استفاده کرده ایم. از آنجایی که بازیکنان اهداف مختلفی می توانند داشته باشند نظریه بازی، خیلی خوب با محیط محاسبات ابری وفق می یابد. در این روش، از مکانیسم تقسیم وظایف و تخصیص آنها به مجموعه ای از منابع استفاده شده است. نتایج پیاده سازی نشان می دهد که روش پیشنهادی با کاهش زمان اجرایی جریان کار، افزایش توازن بار و افزایش موازی سازی و همچنین پاسخ به موعد زمانی وظایف راه حل خوبی ایجاد و در حدود %80 بهبودی حاصل کرده است.
-1 مقدمه
رایانش ابری[1,8] الگوی جدیدی در سیستم های توزیعی است که می تواند زیرساخت سخت افزار و نرم افزار برنامه های کاربردی را به عنوان سرویس به کاربران خود ارائه می کند. کاربران بر اساس نیازمندی های سطح سرویس - SLO1 - که پارامترهای کیفیت ارائه سرویس هایشان - QoS2 - را مشخص می کند، می توانند با پرداخت هزینه از منابع و سرویس های به اشتراک گذاشته شده استفاده کنند.[1,2,3] جریان کار، یک مدل برای توصیف محدوده وسیع برنامه های کاربردی و رفتار آنها در سیستم های توزیع شده ابر می باشد. فرایندی است که از یک سری مراحل تشکیل شده است و می تواند پیچیدگی اجرا و مدیریت برنامه های کاربردی را آسان کنداخیراً،. رایانش ابری به عنوان یک راه حل نوید بخشی برای اجرای برنامه های کاربردی نمایان شدند.[5]
برنامه کاربردی جریان کار معمولاً به عنوان گراف فاقد حلقه نمایش داده می شود، که گره های گراف نشان دهنده ی وظایف و لبه های آن نشان دهنده ی وابستگی های داده میان وظایف است 10]،8،.[4 وزن روی نودها پیچیدگی محاسباتی را نشان می دهد و وزن های نمایشی روی لبه ها، مقدار ارتباطی است. در رایانش ابری، تولیدکنندگان مطابق با زمانبندی منابع خود را به طور مستقیم به کاربران اختصاص داده می شود و این شیوه برای جریان کار و دیگر برنامه های کاربردی ایده ال است. با توجه به مدل توزیعی رایانش ابری، زمانبندی وظایف جریان کار و انتساب آنها به منابع دردسترس به عنوان چالش مهمی مطرح است.
مسئله زمانبندی جریان کار حالتی خاصی از مسئله زمانبندی گراف است که با توجه به NP-hard بودن مسئله زمانبندی رایانش ابری، تاکنون تحقیقات زیادی در حل این مسئله انجام شده است7]،. [6 همین موضوع موجب شده تا راه حل های سنتی به دلیل ناسازگاری با شرایط پیچیده معماری رایانش ابری، نتواند جوابگوی نیاز کاربر و ارائه دهندگان سرویس باشد. از این رو، مدل های ابتکاری و فراابتکاری و مدل های اقتصادی و مبتنی بر بازار در ارائه یک راه حل بهینه و تامین تقاضای منابع ابر مناسب شوند.[9] ساختار مقاله در ادامه به صورت زیر است: در بخش 2 به معرفی کارهای مرتبط می پردازیم. در بخش 3 مدل ریاضی روش پیشنهادی بیان می شود. در بخش 4 به توضیح الگوریتم پیشنهادی بر اساس نظریه بازی می پردازیم. ارزیابی روش پیشنهادی در بخش5 انجام می شود و سرانجام در بخش 6 نتیجه گیری و کارهایی که می توان در آینده انجام داد را بیان می کنیم.
-2 کارهای انجام شده
بیشتر الگوریتم های زمانبندی سنتی مانند RR، FCFS، SJF، EDFو الگوریتم های حریصانه، به تخصیص منابع و اشتراک آنها بین کاربران متفاوت ابری به کار برده شده اند به گونه ای که نیازشان را پاسخ دهند.[9] به این دلیل که در این الگوریتم ها نرخ مصرف منابع فیزیکی، توازن بار، fairness، زمان اجرایی در نظر گرفته نشده است بنابراین نمی توانند با پیچیدگی محیط ابر سازگار باشند. در [10] یک زمانبندی بر اساس مسیر بحرانی پویا در محیط توری ارائه شده است. در این روش کارهایی که موعد زمانی دارند روی مسیر بحرانی قرار می گیرند و اول زمانبندی می شوند. این فرایند تا زمان نگاشته شدن همه وظایف ادامه می یابد. هدف اصلی این روش، کاهش طول CP در هر مرحله است.
این روش، از بینش الگوریتم ابتکاری min-min استفاده می کند و کار را به منبعی که سریعتر اجرا می کند می دهد. پس از انتخاب وظیفه، با بررسی همه منابع در دسترس، منبعی که کمترین زمان اجرایی را دارد برای زمانبندی کار انتخاب می شود. با بررسی تمام منابع موجود می توان زمان شروع وظیفه بحرانی فرزند روی منبع یکسان را کم کرد. این روش با اجرای موازی وظایف، باعث کاهش مسیر بحرانی در هر مرحله زمانبندی شده است.
در [11] یک روش بهینه زمانبندی به کمک نظریه بازی غیر مشارکتی در سیستم های توری پیشنهاد شده است. در این روش، از چند دلال استفاده شده که درخواست کاربر را می گیرند و سر منفعت بالاتر با هم رقابت می کنند. دلالان سعی می کنند از زمانبندی استفاده کنند که هم زمان و هزینه کمتری برای کاربر داشته باشد و هم خودشان سود بیشتری ببرند. از تابع سودمندی UB در مقاله برای کاهش زمان و هزینه های اجرایی استفاده شده است.رحمانی و همکاران در[12] با استفاده از تعادل نش در نظریه بازی، یک پیش زمانبندی برای گراف وظایف طراحی کرده اند. در این روش از قانون ادغام وظایف برای کاهش زمان شروع وظایف و در نتیجه کاهش زمان کل اجرایی استفاده کرده اند.
ایده تعادل نش در تشخیص تعداد پردازنده ها و تشخیص ادغام کارامد استفاده شده است به طوریکه با کاهش زمان بیکاری پردازنده ها، بازده عملیاتی بالا رود. الگوریتم پیشنهاد شده شامل سه مرحله تعیین تعداد پردازنده ها، ادغام گراف اولیه و زمانبندی است. ابریشمی و همکاران در [8] یک الگوریتم زمانبندی جریان کار آگاه از موعد زمانی در محیط ابری طراحی شده اند . در این روش با تطبیق الگوریتمPCP که پیش از این برای محیط توری طراحی شده بود به محیط ابری دو الگوریتم زمانبندی جدید ایجاد کردند که الگوریتم یک بخشی - IC-PCP - مسیرهای بحرانی ویژه ابر Iaas است و الگوریتم دو بخشی - IC-PCPD2 - مسیرهای بحرانی ویژه با توزیع موعد زمانی است. یک راهکار در [13]مبتنی بر رفتار دسته جمعی زنبور عسل طراحی شده است.
ABC یک الگوریتم بهینه است که مبتنی بر رفتار هوشمند گروهی از زنبورهاست که راه حل های بهینه برای مسائل پیچیده زمانبندی تولید می کند. هدف این طرح، بهینه سازی مصرف منابع و زمان کلی در زمانبندی وظایف و منابع می باشد. جمعیت اولیه، مجموعه وظایف یا درخواست های کاربر است. زمانبندی روی جمعیت اولیه در سه مرحله اجرا می شود. بویا و همکاران در[14] یک الگوریتم ابتکاری گروه پرندگان برای زمانبندی جریان کار در ابر طراحی شده اند.
PSO الهام گرفته از طبیعت و براساس تکرار است که متاثر از رفتار اجتماعی حیوانات مانند حرکت دسته جمعی پرندگان است. الگوریتم پرندگان از این جهت که با یک جمعیت اولیه تصادفی شروع می شود، شبیه الگوریتم های تکاملی دیگر است. در [15] یک روش به حل مسئله بارکار پویا در ابر به کمک توسعه بخشیدن به بازی معمای زندانی پیشنهاد شده است. فرایند توزیع بار بین گره های مختلف سیستم های توزیعی به بهبود بهره وری منابع و زمان پاسخگویی کارها کمک می کند. در این روش، قوانینی برای تعاملات بین بازیکنان ایجاد شده که رفتار محلی سیستم را با تحلیل هزینه ها و منفعت جابه جایی حجم کار نشان می دهد.
-3 فرموله بندی مسئله
مدل سیستم زمانبندی پیشنهادی شامل یک برنامه کاربردی، یک لایه زیرساخت ابر و یک معیار کارایی برای زمانبندی است. یک برنامه کاربردی جریان کار توسط یک گراف بدون حلقه G - T,E - به نمایش درآمده است. که T مجموعه ای از n وظیفه W1'W2'…'WQ ، و E مجموعه ای از وابستگی ها بین وظایف می باشد. هر وابستگی ei,j= - ti,tj - یک نمونه محدودیت است که نشان می دهد ti باید قبل از شروع tj اجرایش کامل شده باشد. در گراف وارد شده، گره ای که هیچ والدی ندارد گره ورودی، وگره ای که هیچ فرزندی ندارد گره خروجی نامیده می شود. ما در الگوریتم پیشنهادی به یک گره ورودی و یک گره خروجی نیاز داریم و آنها را به عنوان Tentry و Texit به ابتدا و انتهای جریان کارمان اضافه می کنیم. زمان اجرایی این وظایف صفر است و با وابستگی های به وزن صفر با وظایف دیگر متصل شده اند.
در مرحله انتساب، ابتدا سعی کردیم وظایفی که موعد زمانی دارند در اولویت اجرا قرار می گیرند. در این روش چون وظایف در قالب گراف تعریف شده اند از اینرو وابستگی هایی بین آنها مشاهده می شود که در صورت ارتباط از a به b، می توان گفت شرط اجرای b کامل شدن اجرای a است. پس سعی کردیم زمان اجرای a را به حداقل برسانیم. مجموعه منابع را با M نشان داده ایم و k تعداد منابع به صورت 0 P1'P2'…'PN می باشد. با توجه به تعداد منابع موثر، وظایف نیز به زیربخشهایی با اندازه های مختلف تقسیم می شوند و به صورت همزمان به همه منابع برای زمانبندی تخصیص داده می شوند.
-4 الگوریتم پیشنهادی مبتنی بر نظریه بازیها
در این بخش، روش پیشنهادی زمانبندی وظایف جریان کار را به کمک نظریه بازیها بیان می کنیم. قبل از شروع زمانبندی، سریعترین زمان شروع - - EST ، سریعترین زمان پایان - - EFT، حدکثر زمان شروع - - LST و حداکثر زمان پایان - - LFT برای هریک از وظایف برنامه کاربردی جریان کار محاسبه می شود.سپس در هر مرحله زمانبندی یک مسیر بحرانی از وظایف موعد زمانی ساخته می شود و شروع به اجرای آنها می کنیم. این روند تا جایی ادامه دارد که همه گره های گراف انجام شوند. در شکل1 روند اجرای مسئله به صورت شبه کد نمایش داده شده است.
-4-1 ایجاد مسیر
پس از اینکه درخواست کاربر به عنوان یک برنامه کاربردی جریان کار به سیستم ابری وارد شد، زمانبند سیستم آن را زمانبندی می کند. ابتدا یک مسیر از وظایف دارای موعد زمانی، ساخته می شود. برای هر وظیفه دو زمان شروع در نظر گرفته شده که حد بالا و حد پایین نامیده می شود. حد بالا همان سریعترین زمان شروع وظیفه است که در رابطه - - 1 محاسبه شد.
