بخشی از مقاله
چکیده
یکی از مسائل عمده و مهم برای شرکتهای ارایه دهنده سرویسهای مبتنی بر رایانش ابری، رسیدن به راهکاری برای زمانبندی بهینه کارهای موجود میباشد. زمانبندی بهینه باعث گسترش استفاده از منابع و کاهش زمان اجرای کارها میگردد و دستیابی به این هدف باعث میشود تا شرکتها و سازمانهای مربوطه علاوه بر بهینه نمودن کیفیت و عملکرد سرویسهای خود، با کاهش انرژی و به دنبال آن کاهش هزینههای تمام شده امکان ارائه سرویسهای خود را با قیمتهای رقابتی تر داشته و در ادامه کاربران نهایی نیز تمایل بیشتری به بهره گیری و تهیه سرویسهای ابری خواهند داشت. در این مقاله ما به بررسی روشی جهت بهینه سازی زمانبندی اجرا کارها با ایجاد اصلاح و ارتقا در الگوریتم مورچگان خواهیم پرداخت.
-1 مقدمه
رایانش ابری یک روند جدید در محاسبات اینترنت بوده که منابعی همچون انرژی، ذخیره سازی، شبکه، برنامهها و ... را به عنوان سرویس ارائه مینماید. این سرویس به سه بخش به نامهای زیرساخت به عنوان سرویس - IaaS - پلتفرم به عنوان سرویس - PaaS - و نرم افزار به عنوان سرویس - SaaS - طبقه بندی میشود. [1] چالش اصلی در محیط توزیع شده، زمانبندی وظایف و در نتیجه آن برقراری توازن بین درخواستهای ورودی بوده که باعث می-شود تا سیستم در شرایط پایدار قرار داشته باشد. [2]
مبحث زمانبندی در رایانش ابری به عنوان یک مسئله NP-Hard بوده و از اهمیت ویژه ای برخوردار است. [3] زمانبندی و اختصاص منابع نه تنها با کیفیت سرویس دهی مرتبط میباشد بلکه مستقیماً برروی سود ارایه دهندگان سرویس ابری نیز تاثیرگذار است. در حال حاضر زمانبندی منابع به یکی از داغ ترین موضوعهای رایانش ابری تبدیل شده و روشهای زمانبندی متعددی توسط محققین در این زمینه ارائه شده است. از آنجا که منابع رایانش ابری معمولاً به صورت پویا اختصاص داده شده و بازپس گرفته میشوند لذا روش-های سنتی قادر به برآورد سازی الزامات عملی زمانبندی منابع مربوطه نبوده و در این حالت منابع به طور قابل توجهی هدر میروند.[4]
هم اکنون روشهای زمانبندی گوناگونی به جهت اختصاص وظایف به نودهای مختلف و ماشینهای موجود در محیطهای توزیع شده به کار گرفته میشوند. اگر چه این الگوریتمها به طور موثری کار میکنند ولی هنوز به برخی چالشها مانند تاخیر ارتباطی، بکارگیری موثر منابع، قابلیت اطمینان و تخصیص کار به ماشینهای غیر قابل استفاده، به طور دقیقی نپرداخته اند.[2] اهمیت بالای کاهش مصرف انرژی و تاثیرات آن بر هزینههای تمام شده سرویسها باعث شده که در سالهای اخیر تحقیقات گسترده ای در زمینه بهینه سازی مصرف انرژی در محیط ابر صورت بگیرد. اخیرا روشهای زیادی برای مدیریت انرژی در سیستمهای توزیع شده با مقیاس بزرگ ارائه شده و کارهای زیادی نیز در سطوح مختلف آن صورت پذیرفته است. ما در اینجا به بررسی برخی از این تحقیقات میپردازیم.
در مقاله [4] از مدل تخصیص منابع دینامیک مکان - آگاه برای محیطهای ابری استفاده شده است که این مدل دو وظیفه مهم را انجام می-دهد، یکی از آنها تصمیم به جهت تعیین جایگذاری ماشینهای مجازی و دیگری تصمیم برای مهاجرت ماشینهای مجازی میباشد. بدین صورت که اگر ارائه کننده درخواستی از کاربر دریافت کند، درآن صورت ارائه کننده نزدیکترین میزبان فیزیکی در این ناحیه را مییابد. ارائه کننده سرویس، یک ماشین مجازی مناسب یافته و سطح بهره وری آن را با ماشین فیزیکی خاص بررسی میکند، اگر سطح بهره وری ماشین فیزیکی برای تخصیص یک ماشین مجازی مناسب باشد فراهم کننده ماشین مجازی را به آن اختصاص میدهد.
مزیت این مدل این است که ازکاهش عملکرد مرکز داده جلوگیری میکند اما از معایب آن این است که این مدل دریک محیط واقعی محاسبات ابری قابل اجرا نیست، این مدل به کارایی درمحیط محاسبات ابری نمیپردازد. الگوریتمBest Fit Random Heuristic در مقاله [5] توضیح داده شده است که هزار عدد تخصیص مختلف که نیازهای ماشینهای مجازی را برآورده کرده و موجب سرریز ظرفیت میزبانهای فیزیکی نشود را به طور تصادفی انتخاب کرده وانرژی مصرفی این هزار تخصیص را محاسبه و در نهایت آنکه کمترین مصرف انرژی را دارد اجرا میگردد.
BELOGLAZOV و همکارانش در مقاله [6] از سیاست کمترین مهاجرت - MM - برای مهاجرت ماشینهای مجازی و نیز الگوریتم اول بهترین - FF - برای استقرار اولیه ماشینهای مجازی استفاده کرده اند. در الگوریتم اول بهترین، هرچه تعداد ماشینهای مجازی و میزبانها کم باشد بهترین نتیجه را ارائه میدهد اما هر چه تعداد ماشینهای مجازی و میزبانها بیشتر باشد نتیجه عکس خواهد داد. در مقاله [7] الگوریتم Optimal VM Allocation توضیح داده شده است. با استفاده از آن، مصرف انرژی ماشینهای مجازی را روی تمام ماشین-های فیزیکی مجاسبه نموده و در انتها آن را روی میزبانی قرار میدهد که کمترین مصرف انرژی را داشته باشد. پیچیدگی زمانی این الگوریتم، O - m - ^n است که به صورت نمایی زیاد میباشد.
در مقاله [8] الگوریتم Greedy Heuristic توضیح داده شده است. بر اساس آن ابتدا همه ماشینهای مجازی بر اساس فاکتور مرتب سازی خود مرتب میگردند، سپس تمام تخصیصهای ممکن که در آن شرایط خواسته شده نقض نشود محاسبه میگردد. پیچیدگی زمانی این الگوریتم O - nlogn - +O - n.m - O - nlogn - ⊂ O - n.m - میباشد که بهینه نیست. از دیگرکارهای انجام شده دراین راستای تحقیقاتی است که G.Lovasz و همکارانش در [9] انجام دادند.
آنها به منظور پیدا کردن تعادل بهینه بین صرفه جویی انرژی و عملکرد ارائه دهنده ابر ابتدا به محاسبه این مسئله پرداختند که با استفاده از روش مجازی سازی که در آن منابع فیزیکی باید با بقیه ماشینهای مجازی به اشتراک گذاشته شود چه مقدار افت کارایی حاصل میگردد ، سطح پایه عملکرد را سطحی که در توافقنامه بین کاربر و ارائه دهنده تعریف شده در نظر گرفته اند. آنها سه پارامتر را در کارایی یک برنامه کاربردی موثر شناخته اند که عبارتند از: تعداد درخواستهای رقیب برای یک منبع، بار کلی روی یک منبع و مقدار منبع مورد نیاز خود برنامه که تابع هزینه برای آن حساب شده که در بدترین حالت O - n.m - میباشد و لازم است که پارامترهایی نظیر تاخیر شبکه، یا تاثیر ناهمگنی مراکز داده که از جمله مشخصههای محیطهای ابری است بررسی شود.
با بررسی و تحقیقات بیشتر از طریق مطالعه اقدامات قبلی صورت گرفته در زمینه دستیابی به زمانبندی بهینه، در این مقاله سعی داریم تا با ایجاد تغییراتی در بهره گیری از روش زمانبندی مورچگان و موازنه ی بارهای ورودی و منابع، امکان کاهش زمان اجرای کارها را فراهم آوریم. در روش زمانبندی ACO پیشنهادی ما اطلاعات هیورستیک با در نظر گرفتن برخی پارامترهای خاص به شکلیکاملاً مناسب به گونه ای محاسبه میگردد تا امکان استفاده از مسیر بهینه فراهم گردد.
-2 مفاهیم اولیه
مجازی سازی مهمترین تکنولوژی مورد استفاده در رایانش ابری میباشد. مجازی سازی انعطاف پذیری زیادی را از طریق جداسازی منابع شبکه و رایانشی فیزیکی از منابع مجازی که میتوانند به اشکال مختلف به صورت مستقل و مدیریت شده به کار برده شوند، ارائه مینماید. [10] در حال حاضر به لطف پیشرفت سریع تکنولوژی مجازی سازی، ایجاد ماشینهای مجازی - به عنوان منابع اصلی در پلتفرم رایانش ابری - به یک راه حل جدید برای رفع مشکل مدیریت پویای منابع تبدیل شده است. [11] در این شرایط مسئله مهمی که با آن روبرو خواهیم بود زمانبندی مناسب وظایف به گونه ای است که امکان بهره گیری هرچه مناسب تر از منابع موجود در محیط رایانش ابری را داشته باشیم. [2]
برخلاف زمانبندی سنتی وظایف - مانند مکانیزیم زمانبندی در کلاستر - که در آن در یک مرحله واحدهای اجرایی به صورت مستقیم به منابع فیزیکی نگاشت داده میشدند، در بخش IaaS - اجرای میان افزار - منابع در دو مرحله ی زیرساخت - Infrastructure-level - و ماشین مجازی - VM-Level - زمانبندی میشوند. در مرحله اول یک یا چند زیرساخت ابر ایجاد شده و ماشینهای مجازی از طریق زمانبند VM به سخت افزار فیزیکی تخصیص مییابند سپس در مرحله دوم کارها با استفاده از تکنیک زمانبندی کار، برای اجرا به منابع مجازی اختصاص داده میشوند. [12] نمایش این مراحل در شکل - 1 - قابل مشاهده است.
ماشینهای مجازی به عنوان یکی از اصلی ترین منابع در رایانش ابری به حساب میآیند و به صورت معمول زمانبندی منابع ماشین مجازی در محیط رایانش ابری بر مبنای وضعیت موجود سیستم صورت میپذیرد و در صورت عدم در نظر گرفتن برخی متغیرها، پهنای باند شبکه و تاریخچه دادهها مشکلاتی را در این زمینه بوجود خواهد آورد. بنابراین نحوه تخصیص کار به منابع به صورتیکه کمترین منابع اشغال گردیده و در عین حال بیشترین بازده را به دنبال داشته باشد، بسیار حائز اهمیت است. مشکل شامل زمانبندی و اجرای T کار در N ماشین مجازی است.
در واقع این وظیفه broker است تا کارها را به ماشینهای مجازی مناسب اختصاص داده تا به مواردی همچون SLA، هزینه و عملکرد مناسب برسیم. باید در نظر داشت که امکان اختصاص چند کار به یک ماشین وجود دارد به طور مثال در جدول - 1 - حرف T به عنوان task یا همان کار در نظر گرفته شده است و VM به عنوان ماشین مجازی میباشند. تعداد 6 کار قرار است برروی 3 ماشین اجرا شوند، همانطور که قابل مشاهده است ماشین یک کارهای 1 و4 ، ماشین 2 کارهای 3 و 5 و در انتها ماشین سه کارهای 2 و 6 را انجام داده اند.
-3 طرح مساله
هدف رسیدن به روشی برای زمانبندی مناسب بوده که در آن با موازنه بار و اختصاص صحیح کارها به ماشینها شاهد کاهش زمان اجرای کارها و به دنبال آن استفاده هرچه بهینه تر از منابع، کاهش انرژی مصرف شده و کاستن هزینه تمام شده باشیم. ACO یا همان روش مورچگان به عنوان یکی از راهکارهای بهینه برای زمانبندی با در نظر گرفتن موازنه بار مورد توجه بوده است. توسعه این الگوریتم از رفتار مورچهها الهام گرفته است. مورچهها حشره-هایی اجتماعی بوده و در دسته بزرگی از جمعیت به نام کلونی - Colony - زندگی میکنند و رفتارشان به جای اینکه تابع بقای فرد باشد، تابع بقای کلونی است. در این الگوریتم از رفتار مورچههای کارگری که برای یافتن کوتاهترین مسیر از لانه تا منبع غذایی در تلاش هستند، الگو گرفته شده است.
مورچهها برای یافتن غذا ابتدا محدوده دور لانه را بطور تصادفی طی می-نمایند. مورچه ها در هنگام حرکت ردی از خود برروی زمین به نام فرومون - pheromone - به جا می گذارند. به طور کلی مورچه ها قادر هستند تا فرومون را بو بکشند لذا مسیری احتمال انتخاب بیشتری را دارد که اثر فرومون قوی تری داشته باشد. به محض اینکه مورچهای منبع غذایی پیدا کرد، کیفیت و مقدار غذا را ارزیابی کرده و مقداری از غذا را با خود به لانه می برد. در طول بازگشت اثر فرومون خود را که با کیفیت و کمیت غذای حمل شده رابطه مستقیمی دارد، به جای میگذارد. این رد فرومون، سایر مورچهها را در رسیدن به منبع غذا راهنمایی مینماید.
از آنجا که فرومون در اثر مجاورت با هوا تبخیر می شود، لذا مسیری که مورچه کمتری از آن عبور نماید، به عبارت دیگر رد فرمون در آن تشدید نشود، فرومون موجود در آن بعد از مدتی کاملاً محو خواهد شد. در واحد زمانی یکسان، از مسیر کوتاه تر نسبت به مسیر طولانی تر مورچه های بیشتری عبور خواهند کرد لذا فرومون بیشتری در این مسیر باقی مانده و پس از مدتی همه مورچهها از مسیر کوتاه تر عبور خواهند کرد.
همانطور که در شکل - 3 - مشخص است در مرحله اول مورچه بعداز یافتن منبع غذایی در حال بازگشت به لانه از خود اثر فرومون را به جای میگذارد و در مرحله دوم مورچههای دیگر نیز از مسیرهای متفاوتی به همان منبع غذایی میرسند ولی به مرور زمان از یک مسیر اثر فرمون بیشتری را حس مینمایند و در مرحله سوم و پس از گذشت مدت زمانی اکثر مورچهها با توجه به فرمون بیشتر به جای مانده در مسیر کوتاه تر، نسبت به انتخاب آن اقدام میگذارند.
دو نکته مهم و قابل توجه در این روش وجود دارد، یکی اینکه انتخاب مسیر با فرومون قوی تر توسط مورچهها دارای احتمال بیشتری بوده ولی قطعیتی در آن نیست و دیگری مسئله تبخیر شدن فرومون برجای مانده است که این عمل تبخیر شدن احتمال پیدا کردن کوتاه ترین مسیر جدید را ممکن میسازد.اثر فرومون توسط مورچههای دیگر برای نمایش جمع آوری تجربه در زمان حل مشکل ویرایش میگردد. بعداز ایجاد اثر فرومون و پارامترهای کنترلی اولیه، چرخه اصلی این الگوریتم تا زمانیکه معیار اتمام پروسه حاصل گردد - به طور مثال رسیدن به تعداد تکرار تعیین شده یا رسیدن به محدودیت زمانی تعیین شده - ادامه خواهد داشت.
