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

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

در این شبیه سازی، در الگویتم رقابت استعماری با در نظر گرفتن نرخ انقلاب (Prevolution=0.2)،  ،  ،   و   الگوریتم در نسل ۷۲ ام به پایان رسید و نتایج به صورت زیر می باشد:
•    مقدار بهینه برازندگی در نسل ۱۰۰ ام به ۲٫۳ رسیده است.
•    استفاده از منابع به شدت توسعه یافته است.
•    نسبت بین زمان اجرای مورد انتظار و زمان اجرایی که واکنش نشان داده شد ۱۲٫۴ است.
در الگوریتم ژنتیک با در نظر گرفتن  و   و  و  الگوریتم درنسل ۸۹ ام به پایان رسید و نتایج به صورت زیر می باشد:
•    مقدار بهینه برازندگی در نسل ۱۰۰ ام به ۳٫۲ رسیده است.
•    استفاده از منابع توسعه یافته است.
•    نسبت بین زمان اجرای مورد انتظار و زمان اجرایی که واکنش نشان داده شد ۱۶٫۵ است.

سیستم هدف یک محیط IaaS است. در دو آزمایش۲۰۰ خادمی و ۴۰۰ خادمی زمان انجام کارها، تعداد کارهای انجام نشده در مهلت مشخص و تعداد خادم های مورد استفاده در هر مرحله نشان داده شد و مورد ارزیابی قرار گرفت. نیمی از خادم ها در هریک از دو آزمایش یاد شده شامل خادم های HP ProLiant ML110 G4 و نیم دیگر از نوع خادم های HP ProLiant ML110 G5  هستند. کارها هم از تعداد ۱۶ شروع شده و تا ۴۰۹۶ ادامه می یابد. (کارها تعداد ۱۶، ۳۲، ۶۴، ۱۲۸، ۲۵۶، ۵۱۲، ۱۰۲۴،۲۰۴۸،۴۰۹۶ می باشند.) با توجه به نتایج حاصل از زمان بندی کارها بر اساس الگوریتم رقابت استعماری و نتایج حاصل از زمان بندی کارها بر اساس الگوریتم ژنتیک که بیان شد، نشان می دهد که زمان بندی کارها بر اساس الگوریتم رقابت استعماری عملکرد بهتری نسبت به زمان بندی کارها بر اساس الگوریتم ژنتیک دارد.

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

فهرست مطالب

فصل اول- کلیات تحقیق    1
۱-۱-مقدمه    2
۱-۱-۱ ابرهای محاسباتی    2
۱-۱-۲ الگوریتم رقابت استعماری    3
۱-۱-۳ زمان بندی کارها    3
۱-۲ اهمیت موضوع تحقیق    5
۱-۳ تعریف مسئله    6
۱-۴ اهداف تحقیق    6
۱-۵ محدوده تحقیق    6
۱-۶ ساختار کلی پایان نامه    6

فصل دوم- ادبیات و پیشینه ی تحقیق    7
۲-۱ مقدمه    8
۲-۲ ابرهای محاسباتی    8
۲-۲-۱  تعریف    9
۲-۲-۲ تاریخچه    9
۲-۲-۳  معماری ابرهای محاسباتی    10
۲-۲-۴ مدل های پیاده سازی ابرهای محاسباتی    11
۲-۲-۵ مجازی سازی    12
۲-۲-۶ مزایای ابرهای محاسباتی    12
۲-۲-۷ چالش های ابرهای محاسباتی    13
۲-۳ زمان بندی کارهای مستقل    14
۲-۳-۱ تعریف    15

۲-۳-۲ الگوریتم های زمان بندی در ابرهای محاسباتی    16

۲-۳-۲-۱  مروری بر الگوریتم های زمان بندی حداکثر تلاش    20
۲-۳-۲-۲  الگوریتم زمان بندی آگاه از منبع    20
۲-۳-۲-۳  قیمت گذاری بر اساس فعالیت بهبود یافته (ABC)    21
۲-۳-۲-۴  بهینه سازی ازدحام ذرات (PSO)    21
۲-۳-۲-۵  الگوریتم توافق زمان-هزینه (CTC)    21
۲-۳-۲-۶  چندین گردش کاری با چندین محدودیت  QOS (MQMW)    22
۲-۳-۲-۷  الگوریتم زودترین زمان پایان ناهمگن (HEFT)    22
۲-۳-۳  الگوریتم های فوق ابتکاری    22
۲-۴ زمان بندی بلادرنگ    23
۲-۴-۱    برخی از الگوریتم های زمان بندی بلادرنگ    24
۲-۴-۱-۱الگوریتم نرخ یکنواخت    24
۲-۴-۱-۲ الگوریتم ابتدا زودترین مهلت(EDF)    24
۲-۴-۱-۳ الگوریتم کمترین لختی    24
۲-۴-۱-۴ زمان بندی دو سطحی    25
۲-۵ الگوریتم رقابت استعماری    25
۲-۵-۱  مراحل الگوریتم رقابت استعماری    25
۲-۵-۱-۱  شکل دهی امپراطوری‌های اولیه    27
۲-۵-۱-۲  مدل‌سازی سیاست جذب: حرکت مستعمره‌ها به سمت امپریالیست    29
۲-۵-۱-۳  جابجایی موقعیت مستعمره و امپریالیست    31
۲-۵-۱-۴  قدرت کل یک امپراطوری    32
۲-۵-۱-۵  سیاست رقابت استعماری    33
۲-۵-۱-۶  سقوط امپراطوری‌های ضعیف    35
۲-۵-۱-۷  همگرایی    36
۲-۵-۲  مزایای الگوریتم رقابت استعماری    38

۲-۶ تحقیقات انجام شده در زمان بندی ابرهای محاسباتی    40

۲-۷ جمع بندی و نتیجه گیری    42

فصل سوم- روش پیشنهادی    43
۳-۱ مقدمه    44
۳-۱-۱ بیان مساله    44
۳-۱-۲ پارامترهای زمان بندی    44
۳-۱-۲-۱ مدل زمان بندی    45
۳-۱-۲-۲ تطابق اولیه    45
۳-۱-۳ تابع هدف    47
۳-۱-۴ نحوه انجام عمل زمان بندی    47
۳-۱-۴-۱ مدل ماشین مجازی بلادرنگ نرم    47
۳-۱-۴-۲ مدل خادم    48
۳-۱-۴-۳  درخواست ماشین مجازی بلادرنگ    48
۳-۱-۴-۴  ساختار زمان بندی ابری بلادرنگ    48
۳-۱-۵ مراحل اجرای الگوریتم رقابت استعماری    50
۳-۱-۵-۱ شکل دهی امپراطوری های اولیه    50
۳-۱-۵-۲ سیاست جذب    51
۳-۱-۵-۳ انقلاب    51
۳-۱-۵-۴ سیاست رقابت استعماری    52

فصل چهارم- شبیه‌سازی و ارزیابی روش‌های پیشنهادی    54
۴-۱ مقدمه    55
۴-۲ شبیه ساز    55
۴-۲-۱ مزایای کلود سیم    55
۴-۲-۲ مدل سازی در کلود سیم    55
۴-۲-۲-۱ مدل سازی ابر    56
۴-۲-۲-۲ مدل کردن تخصیص ماشین های مجازی    56
۴-۲-۲-۳ مدل کردن بارهای کاری پویا    56
۴-۲-۳ جمع بندی شبیه ساز    56
۴-۳ ارزیابی    58
۴-۲-۱ آزمایش ۲۰۰ خادمی    59
۴-۲-۲ آزمایش ۴۰۰ خادمی    62
۴-۳ نتیجه گیری    65

فصل پنجم- جمع بندی و پیشنهادات    67
۵-۱ جمع بندی    68
۵-۱-۱ خلاصه کار انجام شده    68
۵-۱-۲ مزایا و معایب روش پیشنهادی    69
۵-۱-۲-۱ مزایای روش پیشنهادی    69
۵-۱-۲-۲ معایب روش پیشنهادی    69
۵-۳ نو آوری    69
۵-۴ پیشنهادات    70

فصل ششم- ضمیمه    71
۶-۱ مقدمه    72
۶-۲ شبیه سازی با استفاده از الگوریتم ژنتیک    72
۶-۲-۱ کد گذاری    72
۶-۲-۲ جمعیت اولیه    73
۶-۲-۳ تابع برازندگی (محاسبه هزینه)    73
۶-۲-۴ عملگر انتخاب    73
۶-۲-۵ عملگر تقاطع    73
۶-۲-۶ الگوریتم جهش    74
۶-۲-۷ الگوریتم خاتمه    74
۶-۳ نتیجه گیری    75
مراجع    76
Abstract    79

 
فهرست شکل ها
شکل۲-۱ معماری ابر محاسباتی]۸[    10
شکل۲-۲ فلوچارت الگوریتم رقابت استعماری]۱۱[    26
شکل۲-۳  اجزای اجتماعی سیاسی تشکیل دهنده یک کشور]۱۱[    27
شکل۲-۴ چگونگی شکل‌گیری امپراطوری‌های اولیه]۱۲[    29
شکل۲-۵ شمای کلی حرکت مستعمرات به سمت امپریالیست]۱۲[    30
شکل۲-۶ حرکت واقعی مستعمرات به سمت امپریالیست]۱۲[    30
شکل ۲-۷ تغییر جای استعمارگر و مستعمره]۱۱[    32
شکل ۲-۸ کل امپراطوری، پس از تغییر موقعیت‌ها]۱۱[    32
شکل ۲-۹ شمای کلی رقابت استعماری: امپراطوری‌های بزرگتر، با احتمال بیشتری، مستعمرات امپراطوری‌های دیگر را تصاحب می‌کنند]۱۱[    33
شکل ۲-۱۰ سقوط امپراطوری‌ ضعیف ]۱۱[    36
شکل۲-۱۱ شبه کد مربوط به الگوریتم رقابت استعماری]۱۱[    37
شکل ۲-۱۲ شمای کل الگوریتم رقابت استعماری به صورت گرافیکی]۱۱[    38
شکل۳-۱ نمونه کشور به کار گرفته در الگوریتم پیشنهادی    45
شکل۳-۲ فلوچارت حل مساله    46
شکل ۳-۳ نمایش چگونگی ساختار زمان بندی کارهای بلادرنگ در ابرهای محاسباتی    49
شکل۳-۴ چگونگی شکل‌گیری جمعیت و امپراطوری‌های اولیه    51
شکل ۳-۵ اعمال سیاست انقلاب    52
شکل۳-۶ حرکت یک کشور مستعمره به سمت استعمارگر    52
شکل ۳-۷ تغییر جای استعمارگر و مستعمره    52
شکل ۳-۸ کل امپراطوری، پس از تغییر موقعیت‌ها    52
شکل ۳-۹ شمای کلی رقابت استعماری: امپراطوری‌های بزرگتر، با احتمال بیشتری، مستعمرات امپراطوری‌های دیگر را تصاحب می‌کنند    53
شکل ۴-۱ نمودار زمان انجام کار با ۲۰۰ خادم    61
شکل ۴-۲ نمودار کارهای انجام نشده در مهلت مشخص با ۲۰۰ خادم    61
شکل ۴-۳ نمودار تعداد خادم های مورد استفاده در هر مرحله با ۲۰۰ خادم    62
شکل ۴-۴ نمودار زمان انجام کار با ۴۰۰ خادم    64
شکل۴-۵ نمودار کارهای انجام نشده در مهلت مشخص با ۴۰۰ خادم    64
شکل ۴-۶ نمودار تعداد خادم های مورد استفاده در هر مرحله با ۴۰۰ خادم    65

فهرست جدول ها
جدول ۴-۲ مشخصات و تنظیمات خادم های مورد نظر    59
جدول ۴-۳ نتایج بدست آمده با ۲۰۰ خادم(زمان انجام کار، تعداد کارهای انجام نشده در مهلت مشخص و تعداد خادم های مورد استفاده)    60
جدول ۴-۴ نتایج بدست آمده با ۴۰۰ خادم(زمان انجام کار، تعداد کارهای انجام نشده در مهلت مشخص و تعداد خادم های مورد استفاده)    63