بخشی از مقاله
چکیده
پردازشهای ابری و محیط ابر و پایگاه دادههای ابری محلی برای پردازش برنامههای کامپیوتری و ذخیرهسازی اطلاعات روی شبکه و اینترنت میباشد که برای بهرهمندی از آنها باید بهینهترین سیاست اجرایی را پیاده نمود. در سیستمهای توزیع شده مانند محیطهای رایانش ابری، خدمات درخواستی کاربران چنان انجام میشود که کاربر احساس کند فقط با یک سیستم واحد مواجه است. در رایانش ابری، یک سیستم زمانبندی کارا و موثر، نقش کلیدی را دارد و تأثیر مستقیم بر موفقیت و سودآوری آن محیط خواهد داشت.
در این مقاله، با استفاده از الگوریتم فرا-ابتکاری رقابت استعماری، به یک راهحل کارا و دقیق جهت زمانبندی وظایف در محیطهای پردازش ابری دست یافتهایم. از جواب حاصل از یک روش تکراری مانند الگوریتم تطبیقی پویا به عنوان جواب اولیهی روش رقابت استعماری استفاده کردیم تا روند رسیدن به جواب دقیق را سرعت بخشیم. نتایج در مقایسه با سایر روشهای مورد آزمایش نشان داد که زمانبندی بر اساس روش پیشنهادی، عملکرد مناسبی در نگاشت وظایف ابری به منابع سختافزاری ناهمگون دارد.
.1 مقدمه
رایانش ابری مفهومی که اخیرا در دنیای تکنولوژی اطلاعات معرفی شده است، محیطی برای به اشتراک گذاری منابع - نرمافزار و سختافزارهای دادهای و پردازشی - را فراهم مینماید. این محیط نوعی پردازش توزیع شده روی شبکه است که در آن یک برنامه میتواند در آن واحد بر روی کامپیوترهای مختلف اجرا شود. در واقع رایانش ابری به کاربران خدمات راه دور ارائه میکند. ارائهی فضای مجازی، توزیعپذیری و قدرت توسعهپذیری به صورت پویا از ویژگیهای محیطهای ابری میباشد .[2] رایانش ابری مدلی است برای داشتن دسترسی آسان و بنا به سفارش شبکه، به مجموعهای از منابع محاسباتی پیکرپذیر - مانند شبکهها، سرورها، فضای ذخیرهسازی، سرویسها و برنامههای کاربردی - که بتواند با کمترین کار و زحمت و یا نیاز به دخالت فراهم کنندهی سرویس، به سرعت فراهم شده یا آزاد گردند .[3]
از فواید این تکنولوژی جدید میتوان به افزایش سرعت پردازش برنامهها نام برد زیرا در محیط ابری میتوان از توانایی تمام منابع موجود به طور موازی جهت انجام کارها بیشترین بهره را برد. در یک محیط ابری کاربران میتوانند برنامه و درخواستهایی را در این محیط جهت پردازش قرار دهند و یا دادههای خود را در آن ذخیره نمایند. در محیط ابری به دلیل قابلیت مجازیسازی آن، هیچ یک از کاربران با جزئیاتی - مانند منابع اطلاعاتی، تجهیزات سختافزاری، سیستم عامل و ... - که در ابر قرار دارند سر و کار نداشته و به اصطلاح آنها را نمیبیند .
[4] با افزایش تقاضا برای اجرای برنامههای مختلف در ابر، به ویژه برنامههای بزرگ و مشترک - مانند برنامههای تجاری و علمی - ، استراتژیهای زمانبندی درخواستهای ابر از اهمیت بسیار زیادی برخوردار شدهاند. مسأله و چالش اصلی در رایانش ابری این است که چطور همهی کاربران از خدمات ارائه شده توسط ابر راضی باشند؟ وظیفهی برطرف کردن این مسأله به عهدهی واحد هماهنگ کننده ابر میباشد .[5] واحد زمانبندی شامل یک الگوریتم زمانبندی است که باید وظایف و برنامههای درخواستی را طوری برنامهریزی کند که کاربران را خرسند نموده و در عین حال مدیر ابر نیز متضرر نشود. الگوریتم زمانبندی کمک میکند تا بازدهی و توان عملیاتی کل سیستم ابر افزایش یابد.
زمانبندی به عنوان مسألهی یافتن یک دنباله و ترتیب درست از اجرای وظایف مطرح میشود؛ منظور از دنبالهی اجرایی درست آنست که اجرای وظایف از قیدها و محدودیتهای زمانی، حافظه و سهم CPU تجاوز نکند. زمانبندی نقش کلیدی را در کارایی سراسری برنامههای اجرا شونده روی محیط ابری ایفا میکند. برای زمانبندی اجرای یک وظیفه بر روی یک سختافزار مشخص دو شرط لازم است برقرار باشد؛ نخست اینکه منابع ابری توانایی برآورده ساختن حداقل نیازهای وظیفهی مورد نظر را داشته باشند و برای اجرای آن آماده باشند. دوم اینکه منبع یا منابعی برای اجرای وظیفه در دسترس باشد. همانگونه که در شکل 1 قابل مشاهده است، کاری که الگوریتم میکند یافتن یک نگاشت مناسب از وظایف به منابع است. سیستم رایانش ابری از مجموعهای از منابع کمتوان جهت رسیدن به عملکردی خوب و قدرت پردازش بالا استفاده میکند و البته یک الگوریتم زمانبندی مناسب کلید این موفقیت است.
-1 ادبیات و پیشینه موضوع
از ابتدای تولد رایانش ابری تا بدین روز همواره در زمینهی زمانبندی وظایف، تحقیقات گسترده انجام گرفته و در نتیجهی آنها روشها و الگوریتمهای متفاوتی معرفی شدهاند. روشهایی مانند زمانبندی به کمک الگوریتم ژنتیک [5] و [8]، الگوریتم ژنتیک بهبود یافته [7]، زمانبندی بر مبنای استراتژی Min-Min یا [14] Max-Min و [15]، الگوریتم زمانبندی توزیعشده پویا ، سیستم کلونی مورچه [16]، شبکههای عصبی مصنوعی [17] و... از جمله روشهای به کار رفته جهت یافتن بهترین برنامه زمانی وظایف در محیط ابری هستند؛ مقالات [3]، [13]، [18]، [19]، مرور مختصری بر الگوریتمهای زمانبندی موجود داشتهاند. روشهای معرفی شده هر یک در شکل خاصی از شبکههای ابری با کاربریهای مختلف و با نتایج قابل قبول و کاربردی مورد استفاده قرار گرفتهاند.
محققان در [5] و [8] تحقیق کردهاند که در روشهای مبتنی بر الگوریتمهای بهینهسازی مانند GA معمولا سعی بر این است که ابتدا با یک حدس اولیه از نگاشت وظایف به منابع، مقدار یک تابع هزینه خاص را - معمولا بر حسب مجموع زمان اجرای وظایف میباشد - کمینه کنند. یک مزیت روش ژنتیک، تابع ارزیابی جواب است که با هر پیچیدگی میتواند باشد و این کمک میکند بتوانیم هر گونه قید و شرط لازم برای زمانبندی ابری را در الگوریتم ژنتیک لحاظ کنیم؛ این ویژگی GA قابلیت بهینهسازی چند هدفه را نیز ممکن میکند و ما میتوانیم همزمان چند مسألهی زمانبندی در ابر را حل نماییم. مزیت دیگر آنکه GA در دام جوابهای محلی نمیافتد و تقریبا میتوان مطمئن بود که بهترین زمانبندی ممکن را نتیجه میدهد. از معایب این روش به کند بودن آن میتوان اشاره کرد.
در [7] روش ژنتیک بهبود یافته را به این صورت توضیح میدهند که ابتدا جمعیت اولیه به صورت تصادفی تولید شده و سپس یک روش حریصانه این جمعیت اولیه را بهبود میبخشد و سپس ادامه کار همانند روش ژنتیک معمولی دنبال میشود. ایدهی بهبود دادن جوابهای اولیه توسط یک الگوریتم متفرقه منجر به کاهش زمان یافتن جواب بهینه میشود. در تحقیق [16] از الگوریتم مورچه ACO استفاده شده است که در آن چندین مورچهی مصنوعی به طور تصادفی و بر اساس میزان فرومون و مقادیر اکتشافی و استفاده از قانون انتخاب سیستم کلونی مورچه، جوابهایی متمایز را ایجاد میکنند. مقدار فرومون مورچهها بر اساس شایستگی جوابی که یافتهاند بروز میشود. در پایان هر تکرار جوابهای متناظر با بیشترین اثر فرومون، شانس انتخاب بیشتری دارند؛ این روند تا یافتن جواب مناسب ادامه مییابد.
همچنین در [9] روش جستجوی ACO به همراه GA برای مسألهی زمانبندی وظایف به کار رفته است. در این تحقیق از امتیازات مثبت هر کدام از روش-های مذکور استفاده شده است تا بهترین جواب ممکن حاصل گردد. ابتدا الگوریتم ژنتیک که از خاصیت جستجوی سراسری برخوردار است، یک جواب اولیهی مناسب برای مسأله پیدا میکند. سپس به کمک ویژگی بازخوردی الگوریتم مورچه، جوابهای دیگری مورد آزمایش قرار گرفته تا به نقطهی بهینه نزدیک گردد. در [6] بیان شده که روشهای اکتشافی-تصادفی مبتنی بر جمعیت مانند GA، ACO و PSO معمولا در سیستمهای ابری و پردازش موازی مرتبط با سازمانهای علمی استفاده میشود.
در روشهای توزیعشده پویا همواره با ورود وظایف جدید به محیط ابری، صف وظایف در حال انتظار1به روز شده و برنامه زمانی تا جایی که لازم باشد دستخوش تغییر میگردد. در مقاله [20] یک الگوریتم پویا جهت زمانبندی سیستم رایانش شبکهای معرفی شده است که بر اساس آن همواره سیستم در یکی از حالات چهار گانه زیر قرار میگیرد : -1 انتظار برای درخواستها -2 اختصاص منابع بیکار به وظایف -3 پردازش وظایف حاضر در صف اجرا-41ورود وظایف جدید و تخصیص دوباره - شکل . - 1
روشهای Min-Max از استراتژی مشابه الگوریتمهای حریصانه بهره میگیرند؛ در این مورد، الگوریتم با کمک دو صف اولویت جداگانه یکی مخصوص وظایف و دیگری برای منابع، سعی میکند بیشترین منابع را در اختیار پرهزینهترین وظایف قرار دهد تا بدین شکل توازنی بین هزینهی زمانی وظایف سبک و سنگین ایجاد شود. نمونهای از این روش در [14] و [15] معرفی شده است. نمونهی پیشرفتهی این الگوریتم در [21] مختصرا بررسی و مورد مقایسه قرار گرفته است.
[6] و [22] روش تطبیقی پویا جهت زمانبندی برنامههای ابری را بدین صورت معرفی کرده است که وظایف و منابع در ساختارهای درختی قرار میگیرند و دادههای مورد نیاز هر برنامه تکه تکه شده و به صورت موازی به نودهای کامپیوتری منتقل میگردند. در این روش برخلاف روشهای معمول، به جای استفاده از زمان تقریبی اجرای وظایف، از نزدیکترین زمان اجرای ممکن استفاده میشود. روش تطبیقی پویا به دلیل استفاده از ساختمان دادههای درختی و شبکهای، سرعت بالایی دارند و بنابراین برای محیطهای ابری با حجم زیاد از وظایف و درخواستها مناسب است.
یک روش خوشهبندی فازی در [10] به عنوان یک عمل پیشپردازش برای طبقهبندی منابع ابری استفاده شده میشود؛ سپس گرافهای جهتدار جهت زمانبندی وظایف برای اجرا بر روی خوشههای متمایزی از منابع سختافزاری به کار رفتهاند. در [23] الگوریتم بهینهسازی اجتماع ذرات - PSO - به عنوان یک روش جستجوی جواب بهینه برای مسألهی بهینهسازی استفاده شده است. مولفین با استفاده از یک تکنیک پیشنهادی به بهبود عملکرد الگوریتم PSO پرداختهاند و تا بدین ترتیب بتوانند میانگین زمان اجرای وظایف و همچنین سرعت دسترسی به منابع را کاهش دهند. مقالهی [24] نیز از روش تفاضل تکاملی - که همانند الگوریتم ژنتیک، یک روش مبتنی بر جمعیت است - برای بهینهسازی زمان اجرای کارها در محیط رایانش ابری استفاده کرده است.
2 الگوریتم بهینه سازی تطبیقی پویا
در الگوریتم پیشنهادی ما یک تکنیک بهینهسازی تکاملی به کار رفته است که سرعت رسیدن به نقطهی بهینه تا حدودی بستگی به حدسهای اولیه دارد. برای پیدا کردن این حدس اولیه مناسب، در اینجا ما از روش تکراری تطبیقی پویا استفاده میکنیم تا در یک زمان سریع جواب مسألهی زمانبندی را تولید کند. الگوریتم تطبیقی پویا بنابر [6] یک روش مبتنی بر قدرت پهنای باند شبکه است که در آن بهصورت پیشفرض، دادههای مورد نیاز تمام وظایف ورودی به محیط رایانش توزیعی قبل از اجرای وظایف، تقسیمبندی شده و هر قسمت از دادهها در یک منبع سختافزاری ذخیره میگردد تا در زمان اجرای هر وظیفه، دیتای مورد نیاز آن برنامه از منابع همسایه به صورت موازی بازیابی شود. روش تطبیقی پویا به منظور افزایش سرعت کار خود، ابتدا به کمک ساختار kd-Tree لیست منابع سختافزاری موجود را مرتب سازی میکند تا در حین اجرای الگوریتم، در زمانی کوتاه قویترین منبع را پیدا کند. خلاصهای از روش کار تطبیقی پویا به شرح زیر است :
❖ درخت kd-Tree بر اساس مشخصات منابع ابری - مانند پهنای باند انتقال داده، قدرت پردازش - ساخته میشود.
❖ زیرمجموعهی n تایی R={51'52'…'5Q} از منابع پردازشی با بیشترین درجه پیوند بین یکدیگر از درخت kd-Tree گرفته میشود.
❖ برای هر وظیفه - Task - به نام taski
❖ زمان شروع به اجرای task یک مقدار زیاد قرار میشود
❖ به ازای هر منبع محاسباتی Rj در R نودهای همسایهی Rj پیدا کرده و پهنای باند موجود بین Rj و این همسایهها محاسبه میشود.
❖ فایل مربوط به دادههای مورد نیاز taski به تعداد همسایههای Rj و به نسبت پهنای باند آنها شکسته و اطلاعات آنها ذخیره میشود
❖ با توجه به تقسیم بالا، زمان انتقال دیتای مورد نیاز task[i] به نود Rj محاسبه میگردد.
❖ سریعترین زمان ممکن برای شروع به کار task[i] بر اساس زمان انتقال دیتا و آخرین وضعیت نود Rj محاسبه میشود.
❖ این محاسبات برای سایر Rj ها بررسی میشود و هر نود که بهترین زمان شروع را تضمین کند، task[i] به آن نود جهت بارگیری اختصاص داده میشود
