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

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

در اين شبيه سازي، در الگويتم رقابت استعماري با در نظر گرفتن نرخ انقلاب (Prevolution=0.2)، ، ، و الگوريتم در نسل 72 ام به پايان رسيد و نتايج به صورت زير مي باشد:
• مقدار بهينه برازندگي در نسل 100 ام به 2.3 رسيده است.
• استفاده از منابع به شدت توسعه يافته است.
• نسبت بين زمان اجراي مورد انتظار و زمان اجرايي که واکنش نشان داده شد 12.4 است.
در الگوريتم ژنتيک با در نظر گرفتن و و و الگوريتم درنسل 89 ام به پايان رسيد و نتايج به صورت زير مي باشد:
• مقدار بهينه برازندگي در نسل 100 ام به 3.2 رسيده است.
• استفاده از منابع توسعه يافته است.
• نسبت بين زمان اجراي مورد انتظار و زمان اجرايي که واکنش نشان داده شد 16.5 است.

سيستم هدف يک محيط IaaS است. در دو آزمايش200 خادمي و 400 خادمي زمان انجام کارها، تعداد کارهاي انجام نشده در مهلت مشخص و تعداد خادم هاي مورد استفاده در هر مرحله نشان داده شد و مورد ارزيابي قرار گرفت. نيمي از خادم ها در هريک از دو آزمايش ياد شده شامل خادم هاي HP ProLiant ML110 G4 و نيم ديگر از نوع خادم هاي HP ProLiant ML110 G5 هستند. کارها هم از تعداد 16 شروع شده و تا 4096 ادامه مي يابد. (کارها تعداد 16، 32، 64، 128، 256، 512، 1024،2048،4096 مي باشند.) با توجه به نتايج حاصل از زمان بندي کارها بر اساس الگوريتم رقابت استعماري و نتايج حاصل از زمان بندي کارها بر اساس الگوريتم ژنتيک که بيان شد، نشان مي دهد که زمان بندي کارها بر اساس الگوريتم رقابت استعماري عملکرد بهتري نسبت به زمان بندي کارها بر اساس الگوريتم ژنتيک دارد.

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

فهرست مطالب

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

فصل دوم- ادبیات و پیشینه ی تحقیق 7
2-1 مقدمه 8
2-2 ابرهای محاسباتی 8
2-2-1 تعریف 9
2-2-2 تاریخچه 9
2-2-3 معماری ابرهای محاسباتی 10
2-2-4 مدل های پیاده سازی ابرهای محاسباتی 11
2-2-5 مجازی سازی 12
2-2-6 مزایای ابرهای محاسباتی 12
2-2-7 چالش های ابرهای محاسباتی 13
2-3 زمان بندی کارهای مستقل 14
2-3-1 تعریف 15

2-3-2-1 مروری بر الگوریتم های زمان بندی حداکثر تلاش 20
2-3-2-2 الگوریتم زمان بندی آگاه از منبع 20
2-3-2-3 قیمت گذاری بر اساس فعالیت بهبود یافته (ABC) 21
2-3-2-4 بهینه سازی ازدحام ذرات (PSO) 21
2-3-2-5 الگوریتم توافق زمان-هزینه (CTC) 21
2-3-2-6 چندین گردش کاری با چندین محدودیت QOS (MQMW) 22
2-3-2-7 الگوریتم زودترین زمان پایان ناهمگن (HEFT) 22
2-3-3 الگوریتم های فوق ابتکاری 22
2-4 زمان بندی بلادرنگ 23
2-4-1 برخی از الگوریتم های زمان بندی بلادرنگ 24
2-4-1-1الگوریتم نرخ یکنواخت 24
2-4-1-2 الگوریتم ابتدا زودترین مهلت(EDF) 24
2-4-1-3 الگوریتم کمترین لختی 24
2-4-1-4 زمان بندی دو سطحی 25
2-5 الگوریتم رقابت استعماری 25
2-5-1 مراحل الگوريتم رقابت استعماری 25
2-5-1-1 شکل دهي امپراطوري‌هاي اوليه 27
2-5-1-2 مدل‌سازي سياست جذب: حرکت مستعمره‌ها به سمت امپرياليست 29
2-5-1-3 جابجايي موقعيت مستعمره و امپرياليست 31
2-5-1-4 قدرت کل يک امپراطوري 32
2-5-1-5 سیاست رقابت استعماري 33
2-5-1-6 سقوط امپراطوري‌هاي ضعيف 35
2-5-1-7 همگرايي 36
2-5-2 مزاياي الگوريتم رقابت استعماری 38

2-7 جمع بندی و نتیجه گیری 42

فصل سوم- روش پیشنهادی 43
3-1 مقدمه 44
3-1-1 بیان مساله 44
3-1-2 پارامترهای زمان بندی 44
3-1-2-1 مدل زمان بندی 45
3-1-2-2 تطابق اولیه 45
3-1-3 تابع هدف 47
3-1-4 نحوه انجام عمل زمان بندی 47
3-1-4-1 مدل ماشین مجازی بلادرنگ نرم 47
3-1-4-2 مدل خادم 48
3-1-4-3 درخواست ماشین مجازی بلادرنگ 48
3-1-4-4 ساختار زمان بندی ابری بلادرنگ 48
3-1-5 مراحل اجراي الگوريتم رقابت استعماری 50
3-1-5-1 شکل دهی امپراطوری های اولیه 50
3-1-5-2 سیاست جذب 51
3-1-5-3 انقلاب 51
3-1-5-4 سیاست رقابت استعماری 52

فصل چهارم- شبيه‌سازي و ارزيابي روش‌هاي پيشنهادي 54
4-1 مقدمه 55
4-2 شبیه ساز 55
4-2-1 مزایای کلود سیم 55
4-2-2 مدل سازی در کلود سیم 55
4-2-2-1 مدل سازی ابر 56
4-2-2-2 مدل کردن تخصیص ماشین های مجازی 56
4-2-2-3 مدل کردن بارهای کاری پویا 56
4-2-3 جمع بندی شبیه ساز 56
4-3 ارزیابی 58
4-2-1 آزمایش 200 خادمی 59
4-2-2 آزمایش 400 خادمی 62
4-3 نتیجه گیری 65

فصل پنجم- جمع بندی و پيشنهادات 67
5-1 جمع بندی 68
5-1-1 خلاصه کار انجام شده 68
5-1-2 مزایا و معایب روش پیشنهادی 69
5-1-2-1 مزایای روش پیشنهادی 69
5-1-2-2 معایب روش پیشنهادی 69
5-3 نو آوری 69
5-4 پیشنهادات 70

فصل ششم- ضمیمه 71
6-1 مقدمه 72
6-2 شبیه سازی با استفاده از الگوریتم ژنتیک 72
6-2-1 کد گذاری 72
6-2-2 جمعیت اولیه 73
6-2-3 تابع برازندگی (محاسبه هزینه) 73
6-2-4 عملگر انتخاب 73
6-2-5 عملگر تقاطع 73
6-2-6 الگوریتم جهش 74
6-2-7 الگوریتم خاتمه 74
6-3 نتیجه گیری 75
مراجع 76
Abstract 79

 
فهرست شکل ها
شکل2-1 معماری ابر محاسباتی]8[ 10
شكل2-2 فلوچارت الگوريتم رقابت استعماری]11[ 26
شكل2-3 اجزاي اجتماعي سياسي تشکيل دهنده يک کشور]11[ 27
شكل2-4 چگونگي شکل‌گيري امپراطوري‌هاي اوليه]12[ 29
شكل2-5 شماي کلي حرکت مستعمرات به سمت امپرياليست]12[ 30
شكل2-6 حرکت واقعي مستعمرات به سمت امپرياليست]12[ 30
شكل 2-7 تغيير جاي استعمارگر و مستعمره]11[ 32
شكل 2-8 کل امپراطوري، پس از تغيير موقعيت‌ها]11[ 32
شكل 2-9 شماي کلي رقابت استعماري: امپراطوري‌هاي بزرگتر، با احتمال بيشتري، مستعمرات امپراطوري‌هاي ديگر را تصاحب مي‌کنند]11[ 33
شکل 2-10 سقوط امپراطوري‌ ضعيف ]11[ 36
شکل2-11 شبه کد مربوط به الگوریتم رقابت استعماری]11[ 37
شکل 2-12 شماي کل الگوريتم رقابت استعماری به صورت گرافيکي]11[ 38
شکل3-1 نمونه کشور به کار گرفته در الگوریتم پیشنهادی 45
شکل3-2 فلوچارت حل مساله 46
شکل 3-3 نمایش چگونگی ساختار زمان بندی کارهای بلادرنگ در ابرهای محاسباتی 49
شكل3-4 چگونگي شکل‌گيري جمعیت و امپراطوري‌هاي اوليه 51
شکل 3-5 اعمال سیاست انقلاب 52
شکل3-6 حرکت یک کشور مستعمره به سمت استعمارگر 52
شكل 3-7 تغيير جاي استعمارگر و مستعمره 52
شكل 3-8 کل امپراطوري، پس از تغيير موقعيت‌ها 52
شكل 3-9 شماي کلي رقابت استعماري: امپراطوري‌هاي بزرگتر، با احتمال بيشتري، مستعمرات امپراطوري‌هاي ديگر را تصاحب مي‌کنند 53
شکل 4-1 نمودار زمان انجام کار با 200 خادم 61
شکل 4-2 نمودار کارهای انجام نشده در مهلت مشخص با 200 خادم 61
شکل 4-3 نمودار تعداد خادم های مورد استفاده در هر مرحله با 200 خادم 62
شکل 4-4 نمودار زمان انجام کار با 400 خادم 64
شکل4-5 نمودار کارهای انجام نشده در مهلت مشخص با 400 خادم 64
شکل 4-6 نمودار تعداد خادم های مورد استفاده در هر مرحله با 400 خادم 65

فهرست جدول ها
جدول 4-2 مشخصات و تنظيمات خادم هاي مورد نظر 59
جدول 4-3 نتایج بدست آمده با 200 خادم(زمان انجام کار، تعداد کارهای انجام نشده در مهلت مشخص و تعداد خادم های مورد استفاده) 60
جدول 4-4 نتایج بدست آمده با 400 خادم(زمان انجام کار، تعداد کارهای انجام نشده در مهلت مشخص و تعداد خادم های مورد استفاده) 63