مبانی نظری زمانبندی کارهای فوری در رایانش ابری با الگوریتم ICA (docx) 1 صفحه
دسته بندی : تحقیق
نوع فایل : Word (.docx) ( قابل ویرایش و آماده پرینت )
تعداد صفحات: 1 صفحه
قسمتی از متن Word (.docx) :
دانشکده فنی و مهندسی، گروه کامپيوتر
پايان نامه جهت اخذ درجه کارشناسی ارشد
رشته مهندسی کامپيوتر گرايش نرم افزار
عنوان:
زمان بندی کارهای بلادرنگ در محيط ابرهای محاسباتی با استفاده از الگوريتم رقابت استعماری
استاد راهنما:
دکتر حسين دلداری
استاد مشاور:
دکتر اسماعيل خيرخواه
نگارش:
حسام خسروی بيژائم
زمستان 1393
اظهارنامه
عنوان پایان نامه: زمان بندی کارهای بلادرنگ در محیط ابرهای محاسباتی با استفاده از الگوریتم رقابت استعماری
اینجانب حسام خسروی بیژائم دانشجوی دوره کارشناسی ارشد موسسه آموزش عالی سلمان، نویسنده پایان نامه تحت راهنمایی دکتر حسین دلداری متعهد می شوم:
آ. تحقیقات در این رساله توسط اینجانب انجام شده و از صحت و اصالت برخوردار است.
ب. در استفاده از نتایج پژوهش های محققان دیگر به مرجع مورد استفاده استناد شده است.
ج. مطالب مندرج در این پایان نامه تا کنون توسط خود یا فرد دیگری برای دریافت هیچ نوع مدرک یا امتیازی به جایی ارائه نشده است.
د. کلیه حقوق این اثر متعلق به موسسه آموزش عالی سلمان است و مقالات مستخرج با نام "موسسه آموزش عالی سلمان" و یا " Salman institute of higher education" به چاپ خواهد رسید.
ه. حقوق معنوی تمام افرادی که در بدست آمدن نتایج اصلی رساله تاثیر گذار بوده اند در مقالات مستخرج از آن رعایت شده است.
و. در کلیه مراحل انجام این رساله، در مواردی که از موجود زنده (یا بافت های آن ها) استفاده شده، ضوابط و اصول اخلاقی رعایت شده است.
ز. در کلیه مراحل انجام این رساله، در مواردی که به حوزه اطلاعات شخصی افراد دسترسی یافته یا استفاده شده، اصل راز داری، ضوابط و اصول اخلاقی انسانی رعایت شده است.
تاریخ
-825586624مالکیت نتایج و حق نشرکلیه حقوق این اثر و محصولات آن (مقالات مستخرج، برنامه های رایانه ای، نرم افزارهای و تجهیزات ساخته شده) متعلق به موسسه آموزش عالی سلمان است. این مطلب بایستی به نحو مقتضی در تولیدات علمی مربوطه ذکر شود.استفاده از اطلاعات و نتایج این رساله بدون ذکر مرجع مجاز نیست.00مالکیت نتایج و حق نشرکلیه حقوق این اثر و محصولات آن (مقالات مستخرج، برنامه های رایانه ای، نرم افزارهای و تجهیزات ساخته شده) متعلق به موسسه آموزش عالی سلمان است. این مطلب بایستی به نحو مقتضی در تولیدات علمی مربوطه ذکر شود.استفاده از اطلاعات و نتایج این رساله بدون ذکر مرجع مجاز نیست.-86262997190امضای دانشجو
هوالعلیم
زیباترین نام را بر زبان جاری می کنم ... که هرکس زبان به حمد تو گشود بی تردید نگاه تو بر او افتاده.
پس بر قلبم آن جاری کن که خود می پسندی در ثنایت لب گشایم.
در وادی معرفت نگنجد، سرچشمه هدایت نجوشد، سر بر قامت بندگی فرو نیافتد...، گر گنجینه ای را که مقدسش خواندی و به آن قسم یاد کردی، کوچک شمرده شود و تنها خاطره جوهر خشک شده ای از آن بر برگ برگ صفحات زندگی باقی ماند.
تو علم را روشنی قرار دادی و فانوسی در بیغوله راه که مسیر را، راه نماید و تزکیه را مقدم بر آن دانستی تا نگاهبانش باشد که تزکیه و تعلیم در معیت هم گوهر وجودی انسان را به نور تو منور کند، پرده از واقعیات کنار زند. آن جاست که حقیقت رخ نمایاند، نظر فراتر افتد، خوان گنجینه های دانش رنگین شود و... آری آنجاست که آدمی معنا یابد.
من اگر وعده هایم با تو زیر خروارها تل فراموشی و غفلت مدفون گردیده، اگر زشتی طغیان در نظرم زیبا جلوه گری می کند و چشمانم خشک تر از آن است که در مقام توبه اشکی بر آن جاری شود، بدان از سر جهل است و نسیان... اما بارالها چشم طمع بر رحمتت دوخته ام و در تمنای رهایی از ظلمت ضلالت، ترنم باران معرفتت را می طلبم، امید آنکه جوانه های حقیقت را در وجودم برویاند و انعکاس آن چشمانم را روشن کند.
اکنون چهره بر چهره خاک می سایم و تو را به حبیبت قسم می دهم که..." هر آن خصلت ناپسند که در من می بینی به لطف واسع خویش اصلاحش فرمای تا پسندیده شود و هر آن عیب که نفسم را به فساد بیالاید از من بازگیر و هر آن نقص که جانم را از کمال بازدارد برطرفش فرمای!"
و در آن روز که نوبت زندگانی به سر رسد و پیک مرگ حلقه بر در خانه تن کوبد و دعوت واجب الاجابه تو از آسمان ها به گوش آید... پروردگارا! بر محمد و آل پاکش درود فرست و به حق ایشان عمر ما را با رستگاری به پایان آور و عاقبتمان را ختم به خیر فرمای...!
زبان قاصر است و مجال کوتاه...
180276542545000 تو خود قصیده ی مهر را از لوح نانوشته ی قلبم بخوان ...!
سپاسگزاری
سپاس خداوندگار حکیم را که با لطف بی کران خود آدمی را زیور عقل آراست.
در ابتدا از استاد راهنمای محترم جناب آقای دکتر حسین دلداری که در تمام مراحل انجام این پایان نامه مساعدت های لازم را مبذول فرمودند و استاد مشاور محترم جناب آقای دکتر اسماعیل خیرخواه که در تمام مراحل انجام این پایان نامه کمک خویش را نسبت به اینجانب دریغ نکرده اند و همواره راهنمایی های این عزیزان روشن کننده مسیر حرکت اینجانب بوده است، کمال تشکر وقدر دانی را به عمل می آورم و سپاسگزارم.
همچنین بوسه می زنم بر دستان خداوندگاران مهر و مهربانی، پدر و مادر عزیزم و بعد از خدا، ستایش می کنم وجود مقدس شان را و تشکر می کنم از خواهر عزیزم به پاس عاطفه سرشار و گرمای امید بخش وجودشان، که در این سردترین روزگاران، بهترین پشتیبان من بودند.
حسام خسروی بیژائم
زمستان 1393
تقدیم به:
تمامی رهپویان راه علم ومعرفت
چکیده
الگوریتم زمان بندی کار، که یک مسئله NP-کامل است، نقش کلیدی در سیستم ابرهای محاسباتی ایفا می کند. الگوریتم رقابت استعماری یکی از جدیدترین الگوریتم های بهینه سازی تکاملی است. همانگونه که از نام آن بر می آید، این الگوریتم بر مبنای مدل سازی فرایند اجتماعی- سیاسی پدیده استعمار بنا نهاده شده است.
در این تحقیق با استفاده از الگوریتم رقابت استعماری ، الگوریتمی برای زمان بندی کارهای بلادرنگ نرم در محیط ابرهای محاسباتی طراحی می گردد که بتواند برنامه را در کمترین زمان ممکن، پیش از مهلت تعیین شده و با استفاده از کمترین تعداد منابع اجرا نماید، به نحوی که زمان اجرای کار در مقایسه با زمان بندی کارهای بلادرنگ بر اساس الگوریتم ژنتیک و در شرایط مساوی کاهش پیدا نماید. الگوریتم پیشنهادی از سیستم های ناهمگن، که در آن منابع از ناهمگونی محاسباتی و ارتباطات برخوردار هستند استفاده می نماید. زمان بندی نیز از نوع متمرکز و پویا در نظر گرفته شده است، که در این نوع زمان بندی باید به کارهای از قبل پیش بینی شده و محیط سیستم و حالت فعلی سیستم جهت ساخت طرح زمان بندی توجه کرد.
پیاده سازی های الگوریتم پیشنهادی برای دو آزمایش 200 خادمی و 400 خادمی انجام گرفته است و کارها از تعداد 16 تا 4096 به سیستم وارد گردیده است، نتایج بدست آمده با نتایج زمان بندی کارهای بلادرنگ بر اساس الگوریتم ژنتیک مقایسه گردیده است و بهینه بودن الگوریتم پیشنهاد شده را بر اساس زمان انجام کار، تعداد کارهای انجام نشده در مهلت تعیین شده و تعداد خادم های مورد استفاده نتیجه می گیریم.
در این تحقیق با استفاده از الگوریتم رقابت استعماری در زمان بندی کارهای بلادرنگ در محیط ابرهای محاسباتی، استفاده از منابع بهینه شده است، نسبت بين زمان اجراي مورد انتظار و زمان اجرايي کمتر شده است و مقدار بهينه برازندگي نیز بهتر شده است.
واژه های کلیدی
ابرهای محاسباتی، کارهای بلادرنگ، الگوریتم ژنتیک، الگوریتم رقابت استعماری
فهرست مطالب
عنوان صفحه
TOC \o "1-4" \h \z \u TOC \o "1-4" \h \z \u فصل اول- کلیات تحقیق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 الگوریتم های زمان بندی در ابرهای محاسباتی16
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-6 تحقیقات انجام شده در زمان بندی ابرهای محاسباتی40
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
Abstract79
فهرست شکل ها
عنوان صفحه TOC \o "5-5" \h \z \u
TOC \o "5-5" \h \z \u TOC \o "5-5" \h \z \u TOC \o "5-5" \h \z \u شکل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
فهرست جدول ها
عنوان صفحه TOC \o "6-6" \h \z \u
TOC \o "6-6" \h \z \u TOC \o "6-6" \h \z \u جدول 4-2 مشخصات و تنظيمات خادم هاي مورد نظر59
جدول 4-3 نتایج بدست آمده با 200 خادم(زمان انجام کار، تعداد کارهای انجام نشده در مهلت مشخص و تعداد خادم های مورد استفاده)60
جدول 4-4 نتایج بدست آمده با 400 خادم(زمان انجام کار، تعداد کارهای انجام نشده در مهلت مشخص و تعداد خادم های مورد استفاده)63
فصل اول
کليات تحقيق
1-1-مقدمه
در اين فصل ابتدا خلاصه اي از ابرهاي محاسباتي، الگوريتم رقابت استعماري و زمان بندي کارها بيان خواهد شد و سپس به اهميت موضوع تحقيق، تعريف مساله، اهداف تحقيق، محدوده تحقيق و ساختار کلي پايان نامه پرداخته خواهد شد.
1-1-1 ابرهاي محاسباتي
ابرهاي محاسباتي جديد ترين نسل سيستم هاي توزيع شده هستند که امروزه نام آن در صنعت فناوري ارتباطات و اطلاعات زياد شنيده مي شود و مورد استقبال جامعه علمي و تجاري قرار گرفته است. ابرهاي محاسباتي شکل تکامل يافته تر سيستم هاي مشبک عمومي هستند که به معناي واقعي ايده ارائه خدمات فناوري اطلاعات به صورت يک خدمت عمومي برمبناي پرداخت به اندازه استفاده را اجرايي کردند. شايد يکي از مهمترين عوامل ظهور و موفقيت ابرها، پيشرفت هاي سخت افزاري و نرم افزاري در مجازي سازي است. با استفاده از مجازي سازي مي توان چندين ماشين مجازي مستقل (محيط مهمان) را به طور همزمان بر روي يک منبع سخت افزاري (محيط ميزبان) ايجاد کرد. ماشين مجازي، يک پياده سازي نرم افزاري از يک کامپيوتر واقعي است که رفتار آن را تقليد مي کند، بنابراين مي توان با نصب يک سيستم عامل (مهمان) بر روي ماشين مجازي، نرم افزارهاي کاربردي مورد نظر خود را بر روي آن اجرا کرد. همچنين عرضه کنندگان خدمات مي توانند برنامه هايي را که بر روي ماشين مجازي اجرا مي کردند، و يا حتي خود ماشين مجازي را به عنوان يک خدمت در اختيار کاربران قرار دهند. استفاده از ماشين هاي مجازي سه مزيت عمده براي عرضه کنندگان خدمات دارد:
به آنها اجازه مي دهد که زيرساخت سخت افزاري خود را براساس نيازهاي کاربر تقسيم بندي و سفارشي سازي نمايند. به عنوان مثال مي توانند بر روي يک سخت افزار قدرتمند، به طور همزمان چندين ماشين مجازي با سيستم هاي عامل مختلف را براي کاربران متفاوت ايجاد نمايند.
محيط اجرايي هر برنامه بر روي يک ماشين مجازي مي باشد. بنابراين بروز خطا در هريک از برنامه ها و يا ماشين مجازي، تأثير بر روي ساير برنامه هاي در حال اجرا نخواهد داشت.
با استفاده از روش هايي همچون مهاجرت زنده، در صورت بروز هرگونه مشکل سخت افزاري و يا نرم افزاري، کل ماشين مجازي مي تواند به سخت افزار ديگري منتقل شده و کار خود را ادامه دهد که باعث بالا رفتن قابليت اطمينان سيستم مي گردد. معمولا عرضه کنندگان بزرگ داراي مراکز داده بسيار بزرگ در نقاط مختلف جهان هستند که حتي در صورت بروز مشکل در کل يک منطقه، مي توانند به کار خود ادامه دهند.
1-1-2 الگوريتم رقابت استعماري
الگوريتم رقابت استعماري يکي از جديدترين الگوريتم هاي بهينه سازي تکاملي است. همانگونه که از نام آن بر مي آيد، اين الگوريتم بر مبناي مدل سازي فرايند اجتماعي- سياسي پديده ي استعمار بنا نهاده شده است. اين الگوريتم همانند ساير روش هاي بهينه سازي تکاملي، کار خود را با تعدادي جمعيت اوليه آغاز مي نمايد. در اين الگوريتم، هر عنصر جمعيت، متناظر با کروموزوم در الگوريتم ژنتيک و ذره در الگوريتم بهينه سازي ذرات ، کشور ناميده مي شود.کشور ها به دو دسته مستعمره و استعمارگر تقسيم مي شوند. هر استعمارگر، بسته به قدرت خود، تعدادي از کشورهاي مستعمره را به سلطه خود درآورده و آن ها را کنترل مي کند. سياست همگون سازي و رقابت استعماري، هسته اصلي اين الگوريتم را تشکيل مي دهند. در سياست همگون سازي، مستعمرات را با در نظر گرفتن ضرايبي به سمت استعمارگر آن حرکت مي دهيم. اگر در حين سياست همگون سازي، يک مستعمره نسبت به استعمارگر به موقعيت بهتري برسد، جاي آن دو با يکديگر عوض خواهد شد. براي محاسبه قدرت کل يک امپراطوري نيز، مجموع قدرت کشور استعمارگر به اضافه درصدي از قدرت مستعمرات آن، در نظر گرفته مي شود. بخش مهم ديگر اين الگوريتم، رقابت استعماري مي باشد. در طي اين فرايند، امپراطوري هاي ضعيف، به تدريج قدرت خود را از دست داده و به مرور زمان، به حالتي برسد که تنها يک امپراطوري در مجموعه جواب ها باقي بماند، اين حالت زماني است که الگوريتم رقابت استعماري با رسيدن به نقطه بهينه تابع هدف، متوقف مي شود.]30[
1-1-3 زمان بندي کارها
زمان بندي کارها، يکي از معروف ترين مسائل بهينه سازي ترکيبي است که نقش کليدي براي بهبود سيستم هاي انعطاف پذير و قابل اعتماد دارد. هدف اصلي زمان بندي کارها به منابع سازگار مطابق با زمان سازگار است، که شامل پيدا کردن يک دنباله مناسب است که در آن کارها را مي توان تحت تراکنش محدوديت منطقي اجرا کرد.]1[
مسئله زمان بندي کارها به معناي نگاشت و تعيين ترتيب اجراي کارها بر روي منابع موجود است، به گونه اي كه يك يا چند معيار كارآيي بهينه شوند. اين مسئله جزو مسائل شناخته شده NP-کامل محسوب مي گردد.
بنابراين هيچ الگوريتم شناخته شده با مرتبه زماني چندجمله اي وجود ندارد، كه بتواند جواب بهينه اي براي اين مسئله پيدا كند. علاوه براين، مسئله زمان بندي در سيستم ابرهاي محاسباتي به دليل برخي از خصوصيات خاص آن همچون ناهمگوني، استقلال، و پويايي منابع، به مراتب پيچيده تر از سيستم هاي سنتي است. تحقيقات زيادي بر روي مسئله زمان بندي کارها در سيستم ابرهاي محاسباتي انجام گرفته كه در فصل بعدي برخي از آنها را مورد بررسي قرار خواهيم داد. الگوريتم هاي زمان بندي ارائه شده به دو دسته اصلي تقسيم مي گردند:
الگوريتم هاي ايستا كه عمل زمان بندي را پيش از شروع اجراي برنامه انجام مي دهند؛ و الگوريتم هاي پويا كه عمل زمان بندي را در حين اجراي برنامه انجام مي دهند. مزيت الگوريتم هاي ايستا در آن است كه مي توانند با استفاده از امكان رزرو پيشاپيش منابع، مانع از ايجاد تاخير در اجراي کارها گردند. معمولا هدف الگوريتم هاي ارائه شده حداقل كردن زمان اجراي برنامه است، بدون اينكه هيچ تضمين خاصي در مورد سقف زمان اجرا به كاربر داده شود (زمان بندي حداكثر تلاش). اما مسئله هنگامي پيچيده تر مي شود كه بحث كيفيت خدمت نيز مطرح گردد. در اين مسئله، محيط ابرهاي محاسباتي از چندين عرضه كننده تشكيل مي گردد كه هريك منابعي را در اختيار كاربران قرار مي دهند. هريك از اين منابع قادرند يك يا چند کار را با كيفيت خدمت متفاوت (همانند زمان اجرا، امنيت و قيمت متفاوت) اجرا نمايند. در زمان بندي مبتني بر كيفيت خدمت، زمان بند بايد به گونه اي عمل كند كه حداقل كيفيت خدمت موردنياز كاربر برآورده شود. اما نكته مهم در اين است
كه كاربر معمولا كيفيت خدمت موردنياز براي هر کار به تنهايي را مشخص نمي نمايد، بلكه كيفيت خدمت كل كارها را تعيين مي نمايد. به عنوان مثال، كاربر مايل است که کارهاي وي قبل از مهلت معين و با حداقل قيمت اجرا شود. اكنون زمان بند بايد با توجه به زمان اجرا و قيمت پيشنهادي هر منبع براي هريك از كارها، منابع را به گونه اي انتخاب كند كه كل کار در مهلت تعيين شده پايان يابد و قيمت نيز حداقل گردد. نكته اي كه به پيچيدگي مسئله مي افزايد اين است كه نحوه محاسبه كيفيت خدمت كل برنامه از روي كيفيت خدمت هر کار براي معيارهاي مختلف، متفاوت است. به عنوان مثال براي قيمت برابر با حاصل جمع قيمت کارها، براي زمان اجرا برابر با زمان طولاني ترين مسير بين کار ابتدايي و پاياني (مسير بحراني) برنامه، و براي قابليت اطمينان برابرحاصل ضرب قابليت اطمينان هر کار است. همان طور كه قبلا نيز اشاره شد، اين مسئله جزو مسائل چند هدفه يا چند معياري مي باشد و به دليل پيچيدگي مسئله، الگوريتم هاي چنداني براي آن پيشنهاد نشده است. علاوه براين، اكثر محققين از روشهاي فوق ابتكاري همانند الگوريتم هاي ژنتيك براي حل آن استفاده كرده اند كه زمان اجراي آنها معمولا طولاني است. اما به دو دليل براي حل اين مسئله نياز به الگوريتم هايي داريم كه زمان اجراي كوتاهي داشته باشند. دليل اول آن است كه در محيط هاي پويا همانند سيستم هاي ابرهاي محاسباتي، وضعيت منابع به سرعت تغيير مي كند. بنابراين چنانچه زمان اجراي الگوريتم زمان بندي بالا باشد، ممكن است در اين مدت وضعيت بسياري از منابع تغيير كرده و از دسترس خارج شده باشند. دليل ديگر آن است كه معمولا زمان اجراي کارها يكي از پارامترهاي مهم كيفيت خدمت براي كاربران است، و در بسياري از موارد مهلت زماني مشخصي براي اجراي برنامه وجود دارد. لذا بالا بودن زمان اجراي الگوريتم زمان بندي، باعث بالا رفتن زمان كل اجراي برنامه مي شود كه ممكن است باعث اجرا نشدن برنامه در مهلت مقرر شود. بنابراين به نظر مي رسد براي حل اين مسئله بايد به دنبال الگوريتم هاي ابتكاري با مرتبه زماني مناسب، و زمان اجراي كوتاه باشيم. از طرف ديگر، بسياري از محققين از مدل زمان بندي ايستا براي زمان بندي مبتني بر كيفيت خدمت استفاده كرده اند. با توجه به اينكه رزرو پيشاپيش منابع روش مناسبي براي تضمين كيفيت خدمت موردنياز كاربران مي باشد، به نظر مي رسد زمان بندي ايستا كارآيي بهتري براي زمان بندي مبتني بر كيفيت خدمت داشته باشد.
1-2 اهميت موضوع تحقيق
الگوريتم هاي زيادي براي زمان بندي کارها در بسياري از زمينه هاي مختلف پژوهشي مطرح شده است، در حالي که فقط چند مورد از آنها زمينه مطرح شده را پوشش مي دهد.
اغلب روشهاي بهينه‌سازي عام مطرح شده، شبيه‌سازي کامپيوتري فرايند‌هاي طبيعي هستند. شايد يک دليل براي اين کار، ملموس بودن و سادگي فرموله کردن و درک تکامل اين فرايند‌ها است. در نقطه مقابل، در ارائه‌ي الگوريتم‌هاي بهينه‌سازي، علي‌رغم توجه به تکامل زيستي انسان و ساير موجودات (الگوريتم‌هاي ژنتيک)، به تکامل اجتماعي وتاريخي او به عنوان پيچيده‌ترين و موفق‌ترين حالت تکامل، توجه چنداني نشده است. در اين تحقيق، نو بودن ايده‌ي پايه‌اي و هوشمندانه تر بودن الگوريتم رقابت استعماري نسبت به رفتار بيولوژيکي (الگوريتم ژنتيک) و توانايي بهينه‌سازي هم‌تراز و حتي بالاتر در مقايسه با الگوريتم‌هاي مختلف بهينه‌سازي، سرعت مناسب يافتن جواب بهينه، سرعت همگرايي بالا و توانايي بهينه سازي با تعداد متغيرهاي بسيار زياد اين الگوريتم، باعث مي شود تا در اين تحقيق از آن، براي بهينه سازي زمان بندي کارهاي بلادرنگ در محيط ابرهاي محاسباتي استفاده شود.]30[
1-3 تعريف مسئله
محيط ابرهاي محاسباتي از چندين عرضه کننده تشکيل مي گردد که هريک منابعي را در اختيار کاربران قرار مي دهند. در اين تحقيق با استفاده از الگوريتم رقابت استعماري جهت نگاشت کارها به منابع، الگوريتمي براي زمان بندي کارهاي بلادرنگ از نوع نرم در محيط ابرهاي محاسباتي طراحي مي گردد که بتواند برنامه را در کمترين زمان ممکن، پيش از مهلت تعيين شده و با استفاده از کمترين تعداد منابع اجرا نمايد.
1-4 اهداف تحقيق
هدف از اين تحقيق، استفاده از توانايي هاي الگوريتم رقابت استعماري با توجه به سرعت مناسب آن در يافتن پاسخ بهينه، براي زمان بندي کارهاي بلادرنگ نرم در محيط ابرهاي محاسباتي مي باشد که بتواند برنامه را در کمترين زمان ممکن، پيش از مهلت تعيين شده و با استفاده از کمترين تعداد منابع اجرا نمايد.
1-5 محدوده تحقيق
اين تحقيق در زمينه زمان بندي کارهايي از نوع بلادرنگ نرم در محيط ابرهاي محاسباتي صورت خواهد گرفت.
1-6 ساختار کلي پايان نامه
در اين پايان نامه ابتدا ادبيات موضوع و مفاهيم مرتبط از جمله ابرهاي محاسباتي، زمان بندي کارها، الگوريتم هاي زمان بندي ارائه شده در ابرهاي محاسباتي و الگوريتم رقابت استعماري بيان مي شود، سپس زمان بندي کارهاي مستقل بلادرنگ بر اساس الگوريتم رقابت استعماري را در محيط ابرهاي محاسباتي پياده سازي کرده و در نهايت، مقايسه اي در شرايط يکسان، با راهکارهايي که بر اساس الگوريتم ژنتيک بوده]1[ انجام مي گردد .
فصل دوم
ادبيات و پيشينه ي تحقيق
2-1 مقدمه
سيستم هاي توزيع شده و تکنيک هاي پردازش موازي، از جمله راه حل هاي استفاده ي بهتر و سريع تر از دنياي حجيم و پيچيده اطلاعات عصر حاضر مي باشد. امروزه صد ها رايانه و ابر رايانه با ظرفيت ها و معماري هاي گوناگون در سراسر دنيا وجود دارند که در کاربردهاي گوناگون علمي، نظامي، تجاري و غيره از آنها استفاده مي شود، و اکثرا لزوم به اشتراک گذاري اطلاعات در ميان آنها امري مقتضي است. يک سيستم توزيع شده مجموعه اي است از کامپيوتر هاي مستقل که در نظر کاربران به صورت يک سيستم منسجم واحد به نظر مي آيد و مي بايست داراي دو ويژگي اصلي باشد: خودمختاري و شفافيت توزيع. خودمختاري به معني مديريت جداگانه هر گره در عين تعامل آن با ساير گره ها مي باشد، به نحوي که سياست هاي مديريت يا اختلال در هر گره برروي ساير گره ها تاثير نگذارد. شفافيت توزيع، تصور تک واحد بودن سيستم را براي کاربران بوجود مي آورد که خود شامل شفافيت در مباحثي نظير دسترسي، مکان، مهاجرت، تغيير مکان منبع، تکرار، همروندي و خطا مي باشد]8[.
ابرهاي محاسباتي از مجموعه رايانه هاي عظيم متصل به اينترنت تشکيل شده است و راهکاري انعطاف پذير براي رفع نياز بسياري از برنامه هاي کاربردي است]23[.
يکي از چالش برانگيزترين مسائل در ابرها استراتژي زمان بندي يا اختصاص منابع به درخواست هاي سيستم مي باشد. دلايل متعددي از جمله ناهمگون بودن و پويايي خصوصيات منابع و درخواست ها در محيط ابرهاي محاسباتي موجب شده که اين موضوع به عنوان يک مسئله ي NP-کامل نمود پيدا کند.
2-2 ابرهاي محاسباتي
ابرهاي محاسباتي الگويي از محاسبات توزيع شده، مرکب از تعداد زيادي منابع و درخواست ها با هدف به اشتراک گذاري منابع به صورت سرويس، بروي بستر اينترنت مي باشد]31[.
ساختار اصلي ابرهاي محاسباتي سيستم هايي با توان محاسباتي بالا، مراکز داده ها، رسانه هاي ذخيره سازي، بستر هاي نرم افزاري و خدمات نرم افزاري است که روي اينترنت به کاربر ارائه مي شود]24 .[سطوح خدمات رساني ابرهاي محاسباتي به سه سطح تقسيم مي شود. خدمات به صورت نرم افزاري(Saas)، خدمات به صورت بستر هاي نرم افزاري(Paas)، خدمات به صورت زير ساختي(Iaas).
2-2-1 تعريف
با پيشرفت فناوري اطلاعات نياز به انجام کارهاي محاسباتي در همه جا و همه زمان به وجود آمده است. همچنين نياز به اين هست که افراد بتوانند کارهاي محاسباتي سنگين خود را بدون داشتن سخت افزارها و نرم افزارهاي گران، از طريق خدماتي انجام دهند. ابرهاي محاسباتي آخرين پاسخ فناوري به اين نيازها بوده است.
ابر محاسباتي مدلي است براي فراهم كردن دسترسي آسان بر اساس تقاضاي كاربر از طريق شبكه به مجموعه اي از منابع محاسباتي قابل تغيير و پيکربندي )مثل: شبکه ها، خادم ها، فضاي ذخيره سازي، برنامه هاي کاربردي و سرويس ها( که اين دسترسي بتواند با کمترين نياز به مديريت منابع و يا نياز به دخالت مستقيم فراهم کننده سرويس به سرعت فراهم شده يا آزاد گردد]31[.
2-2-2 تاريخچه
پيدايش مفاهيم اساسي ابر محاسباتي به دهه ۱۹۶۰ بازمي گردد. زماني که جان مک کارتي اظهار داشت که محاسبات ممکن است روزي به عنوان يکي از صنايع همگاني، سازماندهي شود. تقريبا تمام ويژگي هاي امروز ابرهاي محاسباتي (منابع انعطاف پذير، ارائه به صورت يک صنعت همگاني، برخط بودن و توهم دسترسي به عرضه نامحدود) به همراه مقايسه با صنعت برق و شکلهاي مصرف عمومي و خصوصي و دولتي و انجمني را پارک هيل داگلاس در کتابي که با عنوان مشکل صنعت همگاني رايانه در سال ۱۹۶۶ مورد بررسي قرار داد. واژه ابر در واقع بر گرفته از صنعت تلفن است به اين گونه که کمپاني هاي ارتباطات راه دور که تا دهه ۱۹۹۰ تنها خطوط نقطه به نقطه اختصاصي ارائه مي کردند، شروع به ارائه شبکه هاي خصوصي مجازي با کيفيتي مشابه و قيمت هاي کمتر نمودند. نماد ابر براي نمايش نقطه مرزي بين بخش هايي که در حيطه مسئوليت کاربرند و آن هايي که در حيطه مسئوليت عرضه کننده بکار گرفته مي شد. ابر محاسباتي مفهوم ابر را به گونه اي گسترش مي دهد که خادم ها را نيز علاوه بر زيرساخت هاي شبکه در بر گيرد]9.[
2-2-3 معماري ابرهاي محاسباتي
معماري سامانه هاي نرم افزاري دست اندر کار در ارائه ابرهاي محاسباتي عموما شامل اجزايي است که با يکديگر از طريق رابط برنامه نويسي نرم افزار و معمولاَ وب سرويس ارتباط برقرار مي کنند.
اين طراحي شباهتي با فلسفه يونيکس دارد که در آن چند برنامه مختلف که هر يک کاري را به خوبي انجام مي دهند، با يکديگر از طريق واسط هاي جهاني کار مي کنند. پيچيدگي کنترل مي شود و سامانه هاي حاصل، مديريت پذيرتر از همتاهاي يکپارچه خود هستند.
شکل2-1 ديد کلي از معماري ابرهاي محاسباتي را نمايش مي دهد.
شکل2-1 معماري ابر محاسباتي]8[
لايه منابع فيزيکي: مديران ارائه دهنده ي سرويس هاي ابرهاي محاسباتي نياز به ارتباط با حجم عظيمي از خوشه ها و رسانه هاي ذخيره سازي دارند، از اين رو از تجهيزات شبکه اي براساس ساختار توپولوژي مناسب جهت ايجاد مرکز داده هاي اين محيط بهره مي برند.
لايه منابع مجازي: توسط تکنولوژي مجازي سازي، استخري از منابع مجازي را توسط منابع سخت افزاري لايه فيزيکي، ايجاد مي کنند که بر اساس نياز درخواست هاي کاربران با حفظ درجه بالايي از اشتراک به آنها اختصاص مي يابد.
لايه مديريت سکو: مديريت سکو شامل، مديريت منابع، مديريت درخواست ها، مديريت کاربران و مديريت امنيت مي باشد.
لايه سرويس هاي کاربردي: در کنار استفاده از سرويس هاي محاسباتي و ذخيره سازي، از سرويس هاي بستر هاي نرم افزاري و برنامه ها و نرم افزارها نيز به صورت برخط مي توان بهره مند گرديد.
سرويس ها در محيط ابرهاي محاسباتي در سه سطح ارائه مي شوند و اين تقسيم بندي، امکان پشتيباني از مديريت متفاوت براي هر سطح، و همچنين تکنولوژي مجازي سازي را موجب مي شود. در محيط ابر، محاسبات بروي استخري از منابع پويا و مجازي به صورت بر خط و بر اساس نياز کاربران اختصاص مي يابند.]10[
معماري IaaS ( Insfractructure as a Service )، زير ساخت رايانه اي که به طور بستر مجازي است به صورت سرويس ارائه مي شود .
معماري PaaS ( Platform as a Service )، يک لايه از نرم افزار را ارائه مي دهند .
معماري SaaS ( Software as a Service )، نرم افزار را به صورت سرويس روي اينترنت قرار مي دهند .
2-2-4 مدل هاي پياده سازي ابرهاي محاسباتي
روشهاي پياده سازي ابرهاي محاسباتي را مي توان به سه مدل ابر عمومي، ابر خصوصي(داخلي)، ابر ترکيبي(آميخته) تقسيم کرد]10[.
ابر عمومي يا ابر خارجي: توصيف کننده ابرهاي محاسباتي در معناي اصلي و سنتي آن است. سرويس ها به صورت پويا و از طريق اينترنت و در واحدهاي کوچک از يک عرضه کننده شخص ثالث تدارک داده مي شوند و عرضه کننده، منابع را به صورت اشتراکي به کاربران اجاره مي دهد.
ابر خصوصي: يک زير ساخت از ابرهاي محاسباتي است که توسط يک سازمان براي استفاده داخلي آن سازمان به وجود آمده است.
ابر آميخته: متشکل از چندين ارائه دهنده داخلي و يا خارجي، گزينه مناسبي براي بيشتر مؤسسات تجاري مي باشد.
2-2-5 مجازي سازي
مجازي سازي لايه اي است که، با استفاده از تکنيک هاي زمان بندي ، منابع فيزيکي را به چندين ماشين مجازي با، بار کاري متفاوت تقسيم بندي مي کند، بدين صورت که هر ماشين مجازي تصور مي کند که تمام منابع فيزيکي سخت افزار را تحت اختيار دارد. برنامه هاي کاربردي تحت عنوان ماشين مجازي به خادم هاي مرکز داده تخصيص داده مي شوند.
2-2-6 مزاياي ابرهاي محاسباتي
دليل تشبيه اين تکنولوژي به ابر اين است که مانند ابر جزئيات فني اش را از کاربران مخفي مي سازد و لايه اي از انتزاع را بين اين جزئيات فني و کاربران بوجود مي آورد. آنچه سيستم ابرهاي محاسباتي ارائه مي کند برنامه هاي کاربردي تجاري برخط است که از طريق مرورگر وب يا نرم افزارهاي ديگر به کاربران ارائه مي شود]8[.
از ديدگاه سخت افزاري ابرهاي محاسباتي در مقايسه با فناوري هاي مشابه قبلي سه جنبه جديد دارد:
ايجاد تصور و توهم دسترسي به منابع نامحدود فناوري اطلاعات در زمان تقاضا و درنتيجه، از بين بردن نياز کاربر به برنامه ريزي تدارک منابع فناوري اطلاعات براي مصارف آينده.
از بين بردن نياز به سرمايه گذاري پيشاپيش براي منابع فناوري اطلاعات، شرکتهاي تجاري مي توانند در اندازه کوچکتر کارشان را آغاز کنند و بر اساس نياز در زمان دلخواه منابع سخت افزاري مورد نياز خود را افزايش يا کاهش دهند.
امکان پرداخت براي استفاده از منابع فناوري اطلاعات در واحدهاي زماني کوتاه مدت مورد نياز آن منبع )مثال: براي پردازشگر در واحد ساعت؛ يا براي رسانه هاي ذخيره سازي در واحد روز).
مزاياي اصلي ابرهاي محاسباتي عبارتند از:
1.سهولت کاربرد: افزايش يا کاهش ميزان منابع مورد استفاده برحسب نياز، تحت اختيار کاربران مي باشد.
2.هزينه: اين فناوري از اين بابت که مشتريان را از مخارج سخت افزار، نرم افزار و خدمات، همچنين درگيري هاي نصب و نگهداري نرم افزارهاي کاربردي بروي سيستم هاي شخصي مي رهاند، هزينه ها را به ميزان زيادي کاهش مي دهد.
3.عدم وابستگي به دستگاه و مکان: کاربران مي توانند در هر مکاني و با هر دستگاهي بوسيله ي يک مرورگر وب از راه اينترنت به سامانه هاي ابري دسترسي داشته باشد.
4.چند مستاجري: در محيط ابرهاي محاسباتي امکان به اشتراک گذاري منابع و هزينه هاي بين گروهي از کاربران وجود دارد و بدين وسيله موارد زير امکان پذير مي شود:
5.قابليت اطمينان: با وجود تعداد زيادي سايت ها و منابع فيزيکي و تکنيک هاي پشتيباني از داده ها در سيستم هاي توزيع شده، قابليت اطمينان افزايش مي يابد.
6. مقياس پذيري: در اين سيستم، کاربران مي توانند برحسب نياز و در زمان تقاضا، به صورت پويا و لحظه اي، منابع را تدارک ببينند و نيازي به تدارک پيشين براي مواقع وجود بار زياد در منابع نمي باشد.
7.امنيت: با استفاده از سياست هاي محافظت از داده ها نظير تمرکز داده ها و منابع امنيتي بيشتر و پيچيده تر امنيت افزايش مي يابد، اما نگراني ها در خصوص از دست دادن کنترل بروي داده هاي حساس همچنان وجود دارد.
8. به دليل عدم نياز به نصب برنامه هاي کاربردي براي هر کاربر نگهداري آسان تر و با هزينه کمتر انجام مي شود. در ابرهاي محاسباتي مي توان نتايج را با ديگران به اشتراک گذاشت.
9. سنجش پذيري: منابع در ابرهاي محاسباتي بايد قابل اندازه گيري باشند و لازم است که ميزان مصرف منابع براي هر کاربر و هر منبع بر اساس واحدهاي ساعتي، روزانه، هفتگي، ماهانه اندازه گرفت.
2-2-7 چالش هاي ابرهاي محاسباتي
در دنياي ابرهاي محاسباتي گذشته از مزايا و فوايدي که در استفاده از اين سبک محاسباتي وجود دارد با چالش هاي پيچيده اي نيز مواجه هستيم. در ادامه سعي شده تا ليستي از مهمترين چالش هاي مطرح شده، بيان شود.]9،31، 32، 33[
آسيب پذيري در برابر رکود اقتصادي: مدل خدمات رايانه اي، در مقابل رکود اقتصادي بسيار آسيب پذير است.
شکل جديد نرم افزارها: متخصصين نرم افزار در راه ايجاد نرم افزاري هستند که ميليون ها کاربر به جاي اجراي آن بر روي کامپيوترهاي شخصي خود، بتوانند از آن مانند يک سرويس استفاده کنند.
پذيرش: اين رويکرد نسبتا تازه است ودر بسياري موارد هنوز پذيرفته نشده است. بخش هاي فناوري اطلاعات هنوز بسيار محتاط عمل مي کنند زيرا سکوي ابرمحاسباتي توسط آنها کنترل نخواهد شد.
کنترل: ارائه دهندگان خدمات، معمولا سکوها را براي پشتيباني از شيوه هاي تجاري و فناوري اطلاعات يک شرکت خاص طراحي نمي کنند. بلکه با توجه به اينکه چه تکنولوژي اي به بهترين نحو نيازها را پاسخ مي دهد و به هنگام نياز آن را تغيير دهند که اين کار بدون موافقت يا رضايت مشتريان انجام مي گيرد.
هزينه هاي پهناي باند: به لطف پهناي باند بالاي شبکه، کاربر حتي هنگامي که در حال استفاده از وب به عنوان يک کامپيوتر فراگير است، احساس کار بر روي سيستم محلي را دارد. با اين حال مشکل متحمل شدن هزينه شارژ بالايي براي پهناي باند. (مثلا براي يک شرکت که پايگاه داده اي چند ترابايتي را از طريق ابر محاسباتي اجرا مي کند، اين هزينه مي تواند بسيار بالا باشد.) پيش مي آيد.
محبوس شدن توسط ارائه دهندگان و استانداردها: نياز به استانداردهاي باز براي تمام شيوه هاي استفاده از وب به عنوان يک کامپيوتر فراگير وجود دارد، زيرا هنگامي که ارائه دهندگان خدمات، شرايط استفاده از خدمات و يا روش هاي عملياتي خود را بعد از مدتي تغيير بدهند، کاربران آن ها احساس به دام افتادن و درماندگي مي کنند.
شفافيت دسترسي: اگر شرکت ها نتوانند نشان دهند که چه کسي به داده هاي مشتريان دسترسي دارد و چگونه مانع دستيابي کارمندان غير مجاز به اطلاعات مي شوند، نخواهند توانست از حسابرسي ظرفيت هاي خود، به وسيله مشتريان آينده با موفقيت بيرون بيايند.
قابليت اطمينان: صحت سازگاري و جامعيت داده ها مي بايست تا سطح بالايي تضمين شود.
حفظ حريم خصوصي: طرفداران حفظ حريم خصوصي، مدل ابر را مورد انتقاد قرار مي دهند، زيرا ارائه دهندگان سرويس هاي ابر مي توانند کنترل و نظارت کامل قانوني ويا غير قانوني بر روي داده ها و ارتباطات بين کاربران سرويس و ميزبان ابر داشته باشند.
امنيت: امنيت ابرهاي محاسباتي وقتي که در داخل سازمان اداره شوند بالاتر است.
ميزان در دسترس بودن و کارايي: علاوه بر امنيت داده ها، ميزان در دسترس بودن و کارايي برنامه هاي کاربردي که روي ابر ميزباني مي شوند براي کاربران از اهميت بالايي برخوردار است.
2-3 زمان بندي کارهاي مستقل
زمان بندي کارها، يکي از معروف ترين مسائل بهينه سازي ترکيبي است که نقش کليدي براي بهبود سيستم هاي انعطاف پذير و قابل اعتماد دارد. هدف اصلي زمان بندي کارها به منابع سازگار مطابق با زمان سازگار است، که شامل پيدا کردن يک دنباله مناسب است که در آن کارها را مي توان تحت تراکنش محدوديت منطقي اجرا کرد]1[.
يک زمينه جذاب در محاسبات ابري، سيستم زمان بندي کارها است، توپولوژي هاي زمان بندي کارها به دو دسته ي ايستا و پويا تقسيم شده اند. مطالعات گسترده ايي بر روي الگوريتم هاي ايستا و پويا در زمينه زمان بندي کارهاي مستقل صورت گرفته است. با توجه به نتايج بدست آمده الگوريتم هاي ايستا به دليل ثابت ماندن منابع در طول زمان کارايي کمتري نسبت به الگوريتم هاي پويا دارند. زمان بندي ايستا با استفاده از به اصطلاح فن آوري از پيش زمان بندي شده براي زمان بندي کارها شناخته شده در محيط از قبل پيش بيني شده مي باشد، در حالي که زمان بندي پويا نه تنها بايد به کارهاي از قبل پيش بيني و محيط سيستم وابسته باشد بلکه به حالت فعلي سيستم جهت ساخت طرح زمان بندي نيز بستگي دارد]1، 8.[
ابرهاي محاسباتي، که به معني اختصاص دادن محاسبات در يک استخر منابع پويا متشکل از رايانه هاي گسترده است، موجب مي شود کاربران توانايي محاسبه ي فضاي حافظه و نرم افزار خدمات برخط را با توجه به شرايط مختلف به دست آوردند. در ابرهاي محاسباتي، منابع (از جمله پردازنده) از ناهمگوني محاسباتي و ارتباطي برخوردار هستند و هميشه به صورت پويا قرار داده شده اند. زمان بندي کارها در ابرهاي محاسباتي به صورت يک مشکل زمان بندي پويا مطرح مي شود. به طور عمده دو عامل از عدم اطمينان وجود دارد:
زمان نامشخص است.
منابع نامشخص است. در مدت زمان طولاني از اجراي امکان پذير، مقدار منابع موجود و فرم آنها در تمام راه تغيير مي يابند. قابليت منابع، جريان بار، منافع و کارهاي درخواست شده، که مي تواند اثر زيادي بر زمان بندي داشته باشد، پويا هستند.
2-3-1 تعريف
زمان بندي کارها يک فرايند کليدي است که هدف آن، اجراي درخواست هاي وارد شده به سيستم، بروي منابع، به شيوه اي کارآمد، با در نظر گرفتن ساير خصوصيات محيط ابر مي باشد. زمان بندي کارها، ماشين هاي مجازي را به عنوان واحدهاي زمان بندي، جهت تخصيص منابع فيزيکي ناهمگون براي اجراي کارها در نظر مي گيرد. هر ماشين مجازي يک واحد انتزاعي از ظرفيت هاي محاسباتي و ذخيره سازي تهيه شده در ابر مي باشد. زمان بندي درست مي تواند روي عملکرد سيستم تاثير بسيار خوبي داشته باشد. الگوريتم زمان بندي کارا مي تواند نيازمندي هاي کاربر را برآورده کند، و بهره وري منبع را بهبود بخشد، به موجب آن عملکرد کلي محيط ابرهاي محاسباتي را افزايش مي دهد]34.[
2-3-2 الگوريتم هاي زمان بندي در ابرهاي محاسباتي
مسئله زمان بندي کارها به معناي نگاشت و تعيين ترتيب اجراي کارها بر روي منابع موجود است، به گونه اي كه يك يا چند معيار كارآيي بهينه شوند. اين مسئله جزو مسائل شناخته شده NP-کامل محسوب مي گردد.
بنابراين هيچ الگوريتم شناخته شده با مرتبه زماني چندجمله اي وجود ندارد، كه بتواند جواب بهينه اي براي اين مسئله پيدا كند. علاوه براين، مسئله زمان بندي در سيستم ابرهاي محاسباتي به دليل برخي از خصوصيات خاص آن همچون ناهمگوني، استقلال، و پويايي منابع، به مراتب پيچيده تر از سيستم هاي سنتي است. تحقيقات زيادي بر روي مسئله زمان بندي کارها در سيستم ابرهاي محاسباتي انجام گرفته كه در ادامه برخي از آنها را مورد بررسي قرار خواهيم داد. الگوريتم هاي زمان بندي ارائه شده به دو دسته پويا و ايستا تقسيم مي گردند، مزيت الگوريتم هاي ايستا در آن است كه مي توانند با استفاده از امكان رزرو پيشاپيش منابع، مانع از ايجاد تاخير در اجراي کارها گردند. معمولا هدف الگوريتم هاي ارائه شده حداقل كردن زمان اجراي برنامه است، بدون اينكه هيچ تضمين خاصي در مورد سقف زمان اجرا به كاربر داده شود (زمان بندي حداكثر تلاش). اما مسئله هنگامي پيچيده تر مي شود كه بحث كيفيت خدمت نيز مطرح گردد. در اين مسئله، محيط ابرهاي محاسباتي از چندين عرضه كننده تشكيل مي گردد كه هريك منابعي را در اختيار كاربران قرار مي دهند. هريك از اين منابع قادرند يك يا چند کار را با كيفيت خدمت متفاوت (همانند زمان اجرا، امنيت و قيمت متفاوت) اجرا نمايند. در زمان بندي مبتني بر كيفيت خدمت، زمان بند بايد به گونه اي عمل كند كه حداقل كيفيت خدمت موردنياز كاربر برآورده شود. به عنوان مثال كاربر مايل است که کارهاي وي قبل از مهلت معين و با حداقل قيمت اجرا شود. اكنون زمان بند بايد با توجه به زمان اجرا و قيمت پيشنهادي هر منبع براي هريك از كارها، منابع را به گونه اي انتخاب كند كه كل کار در مهلت تعيين شده پايان يابد و قيمت نيز حداقل گردد. نكته اي كه به پيچيدگي مسئله مي افزايد اين است كه نحوه محاسبه كيفيت خدمت كل برنامه از روي كيفيت خدمت هر کار براي معيارهاي مختلف، متفاوت است. به عنوان مثال براي قيمت برابر با حاصل جمع قيمت کارها، براي زمان اجرا برابر با زمان طولاني ترين مسير بين کار ابتدايي و پاياني (مسير بحراني) برنامه، و براي قابليت اطمينان برابرحاصل ضرب قابليت اطمينان هر کار است. همان طور كه قبلا نيز اشاره شد، اين مسئله جزو مسائل چند هدفه يا چند معياري مي باشد و به دليل پيچيدگي مسئله، الگوريتم هاي چنداني براي آن پيشنهاد نشده است. علاوه براين، اكثر محققين از روشهاي فوق ابتكاري همانند الگوريتم هاي ژنتيك براي حل آن استفاده كرده اند كه زمان اجراي آنها معمولا طولاني است. اما به دو دليل براي حل اين مسئله نياز به الگوريتم هايي داريم كه زمان اجراي كوتاهي داشته باشند. دليل اول آن است كه در محيط هاي پويا همانند سيستم ابرهاي محاسباتي، وضعيت منابع به سرعت تغيير مي كند. بنابراين چنانچه زمان اجراي الگوريتم زمان بندي بالا باشد، ممكن است در اين مدت وضعيت بسياري از منابع تغيير كرده و از دسترس خارج شده باشند. دليل ديگر آن است كه معمولا زمان اجراي کارها يكي از پارامترهاي مهم كيفيت خدمت براي كاربران است، و در بسياري از موارد مهلت زماني مشخصي براي اجراي برنامه وجود دارد. لذا بالا بودن زمان اجراي الگوريتم زمان بندي، باعث بالا رفتن زمان كل اجراي کار مي شود كه ممكن است باعث اجرا نشدن کار در مهلت مقرر شود. بنابراين به نظر مي رسد براي حل اين مسئله بايد به دنبال الگوريتم هاي ابتكاري با مرتبه زماني مناسب، و زمان اجراي كوتاه باشيم. از طرف ديگر، بسياري از محققين از مدل زمان بندي ايستا براي زمان بندي مبتني بر كيفيت خدمت استفاده كرده اند. با توجه به اينكه رزرو پيشاپيش منابع روش مناسبي براي تضمين كيفيت خدمت موردنياز كاربران مي باشد، به نظر مي رسد زمان بندي ايستا كارآيي بهتري براي زمان بندي مبتني بر كيفيت خدمت داشته باشد.
در خصوص مسئله زمان بندي، راهکارهاي متعددي ارائه شده است: الگوريتم حريص ، دوره گرد، سيستم صف، رزرو پيشرفته و پيش بيني زمان بندي. اغلب اين الگوريتم ها معيارهايي همچون، نرخ بهره وري استفاده از منابع، توازن بار و لزوم پاسخ دهي سريع به درخواست ها را در نظر نمي گيرند.
براي حل مسائل NP- کامل اغلب از الگوريتم هاي تکاملي و مکاشفه اي گوناگون استفاده مي شود. براي حل مسائل زمان بندي در محيط هاي توزيع شده نيز از الگوريتم هايي مانند: Simulated Annealing، Tabu Search و Genetic algorithm بهره گرفته شده است]8.[
الگوريتم هاي زمان بندي پارامتر هاي مختلفي، از قبيل سرعت، ميزان بهره برداري از منبع، هزينه، عملکرد، مقياس پذيري، قابليت اطمينان، مدت زمان اجرا، دسترس پذيري و نرخ موفقيت زمان بندي را دارند]34[.
حال به بررسي جنبه هايي از مسئله مي پردازيم كه بر روي فرآيند زمان بندي تاثير مي گذارند:
اولين ويژگي در فرآيند زمان بندي، تعدد معيارها است كه بر اين اساس مسائل زمان بندي به دو گروه تقسيم مي گردند:
تك معياره: بهينه سازي تنها براي يك معيار صورت مي پذيرد.(معمولا زمان اجرا)
چند معياره: زمان بند سعي مي كند چندين معيار را به طور همزمان بهينه نمايد.
بديهي است كه زمان بندي چند معياره به مراتب پيچيده تر بوده ونياز به استفاده از روشهاي بهينه سازي چند هدفه دارد. ويژگي بعدي ميزان پويايي زمان بندي است، اين ويژگي به رابطه بين فرآيند زمان بندي و اجراي كار مي پردازد. بدين معنا كه آيا زمان بندي پيش از اجراي كار صورت مي پذيرد، يا به طور همزمان با آن. براين اساس روشهاي زمان بندي به سه دسته تقسيم مي گردند:
پويا: در اين روش زمان بندي هر کار زماني صورت مي پذيرد كه آماده اجرا باشد.
ايستا: در اين روش پيش از شروع كار، زمان بندي به طور كامل صورت مي پذيرد.
زمان بندي تركيبي: اين روش تركيبي از دو روش فوق است. به اين معنا كه زمان بندي قسمتي از كار از پيش صورت مي پذيرد، و به محض اتمام اين قسمت، زمان بندي قسمت بعدي آغاز مي گردد.
آخرين ويژگي كه مورد بررسي قرار مي گيرد، امكان رزرو پيشاپيش منابع است. بسياري از سيستم هاي فعلي کارها را به سيستم هاي مديريت منابع محلي ارسال مي كنند كه برمبناي سيستم هاي صف بندي استاندارد عمل مي نمايند. بدين معنا كه سيستم محلي تضمين مي كند كه کار در اولين فرصت ممكن اجرا خواهد شد، اما زمان اجراي آن بستگي به بار محلي سيستم دارد و به طور دقيق مشخص نيست (سيستم هاي مبتني بر حداكثر تلاش). اما سيستم هاي جديدتر، مجهز به امكان رزرو پيشاپيش منابع هستند؛ بدين معنا كه كاربر قادر است منابع مورد نياز خويش را از پيش درخواست نمايد و آنها را با اطمينان بالايي در بازه زماني تعيين شده دريافت نمايد.
يكي ديگر از عوامل تاثيرگذار بر روي الگوريتم هاي زمان بندي كارها، ويژگي هاي منابعي است كه کارها بر روي آنها اجرا مي گردند. از لحاظ تنوع، منابع به دو دسته تقسيم مي گردند:
منابع همگون: در اين مدل كليه منابع ويژگي هاي ايستا و پوياي يكساني دارند (يعني نوع، كارآيي، بار و ... آنها مشابه است).
منابع ناهمگون: در اين مدل منابع مختلف، داراي ويژگي هاي متفاوتي هستند.
ناهمگوني منابع خود به دو گروه تقسيم مي شود. در مدل تك نوعي، كليه منابع از يك نوع يكسان هستند (مثلا از نوع منابع محاسباتي) و تفاوت آنها در ويژگي هاي آنها، همچون سرعت پردازنده و يا اندازه حافظه اصلي مي باشد. اما در مدل چند نوعي، نوع منابع با يكديگر متفاوت است، به عنوان مثال منابع محاسباتي، ذخيره سازي و يا شبكه اي. بيشتر الگوريتم هاي زمان بندي موجود بر روي منابع ناهمگون از نوع منابع محاسباتي متمركز بوده اند.
دومين ويژگي در طبقه بندي منابع، نحوه اجراي کارها است كه بر اين مبنا منابع به دو دسته تقسيم مي گردند:
غير چند برنامه اي: در اين مدل زمان بند در هرلحظه تنها مي تواند يك کار را به يك منبع محاسباتي ارسال نمايد.
چند برنامه اي: در اين مدل زمان بند قادر است چندين کار را به طور همزمان بر روي يك منبع محاسباتي زمان بندي نمايد.
از آنجا كه بيشتر سيستم هاي فعلي، بر پايه سيستم هاي مديريت منابع محلي بنا شده اند كه از مدل غير چند برنامه اي حمايت مي كنند، تقريبا تمامي الگوريتم هاي زمان بندي كارها، بر پايه مدل غير چند برنامه اي هستند.
کار الگوريتم هاي زمان بندي در ابرهاي محاسباتي را مي توان به دو گروه اصلي طبقه بندي کرد. الگوريتم حالت دسته اي برنامه ريزي اکتشافي (BMHA) و حالت برخط الگوريتم هاي اکتشافي. در BMHA، کار ها در مجموعه ي زماني که به سيستم مي رسند در صف جمع آوري مي شوند. الگوريتم زمان بندي پس از يک دوره ثابت از زمان شروع خواهد شد.
نمونه هاي اصلي از الگوريتم هايي که بر اساسBMHA هستند؛ الگوريتم زمان بندي FCFS ، الگوريتم زمان بندي دوره گرد (RR)، الگوريتم min-min و الگوريتم max-min. در الگوريتم زمان بندي حالت اکتشافي برخط، کارها هنگامي که به سيستم مي رسند زمان بندي مي شوند. از آنجا که محيط ابر يک سيستم ناهمگن است و سرعت هر پردازنده به سرعت تغيير مي کند، الگوريتم هاي زمان بندي حالت اکتشافي برخط براي يک محيط ابر مناسب تر مي باشد.
الگوريتم FCFS کارها در يک صف قرار مي گيرند و به ترتيب ورود سرويس مي گيرند، اين الگوريتم سريع و ساده است.
الگوريتم RR فرآيندها در يک روش FIFO اعزام مي شوند اما يک مقدار محدود از زمان پردازنده به نام زمان برش يا کوانتومي داده شده است. اگر يک فرايند کامل نباشد، قبل از آنکه زمان پردازش آن تمام شود، پردازنده پيش دستي مي کند و به فرايند بعدي در صف مي رود و فرايند کامل نشده را در پشت ليست آماده قرار مي دهد.
الگوريتم min-min کارهاي کوچک را انتخاب مي کند تا ابتدا اجرا شوند، اما کارهاي بزرگ مي توانند تاخير طولاني داشته باشند.
الگوريتم max-min کارهاي بزرگ را انتخاب مي کند تا ابتدا اجرا شوند، اما کارهاي کوچک مي توانند تاخير مدت طولاني داشته باشد.
الگوريتم زمان بندي اولويت به هر فرآيند يک اولويت اختصاص مي دهد و اين اولويت براي اجراي مجاز است، فرآيندهاي با اولويت برابر به ترتيب FCFS زمان بندي مي شوند. کوتاهترين کار اول (SJF) انجام مي شود، اين الگوريتم حالت خاصي از الگوريتم زمان بندي اولويت کلي مي باشد. يک الگوريتم SJF به سادگي يک الگوريتم اولويت است که در آن اولويت معکوس (پيش بيني شده) پشت سر هم CPU بعدي برود. به اين معنا که، هرچه بيشتر پشت سر هم باشند در CPU، اولويت پايين تر است و بالعکس. اولويت مي توانند به صورت داخلي و يا خارجي تعريف شده باشد. اولويت هاي تعريف شده داخلي از برخي از مقادير قابل اندازه گيري و يا کيفيت براي محاسبه اولويت يک پردازنده استفاده مي کنند.
2-3-2-1 مروري بر الگوريتم هاي زمان بندي حداکثر تلاش
زمان بندي حداكثر تلاش سعي دارد يك معيار را (كه معمولا زمان اجراي كار مي باشد) بهينه نمايد، بدون اينكه هيچ تضميني در مورد آن معيار به كاربر بدهد. اولين الگوريتم ها از اين دسته در دهه ۱۹۶۰ ميلادي ارائه شده اند. تا پايان دهه ۱۹۹۰ اكثر الگوريتم ها براي سيستم هاي چندپردازنده اي همگون (سيستم هايي كه در آنها همه منابع يكسان هستند) پيشنهاد گرديده اند.]19، 34[
2-3-2-2 الگوريتم زمان بندي آگاه از منبع
الگوريتم زمان بندي آگاه از منبع (RASA) از مزاياي دو الگوريتم Min-Min و Min-Max استفاده مي کند که ابتدا زمان اتمام کارها روي هر يک از منابع که در دسترس هستند را تخمين مي زند، سپس الگوريتم هاي Min-Min و Min-Max متناوب بکار مي گيرد. نتايج آزمايشات بکارگيري RASA در زمان بندي کارها مستقل حاکي از اين است که قابليت اجراي RASA در بدست آوردن زمان بندي با مدت زمان اجراي کمتر بطور قياسي خوب است و نسبت به الگوريتم هاي زمان بندي موجود در سيستم هاي توزيع شده مقياس بزرگ قدم را فراتر نهاده است. اما از جمله معايب اين الگوريتم مي توان به ناديده گرفتن نرخ ورود کار، هزينه هاي اجراي کار در هر يک از منابع و هزينه هاي ارتباطي در زمان اجراي هر کار اشاره کرد.
2-3-2-3 قيمت گذاري بر اساس فعاليت بهبود يافته (ABC)
اين الگوريتم يک الگوريتم زمان بندي مبتني بر هزينه بهبود يافته براي نگاشت موثر کارها به منابع در دسترس ابري است که هم هزينه منبع و هم هزينه عملکرد محاسباتي را در نظر مي گيرد و نرخ ارتباطات/ محاسبه را از طريق گروه بندي کارهاي کاربر، براساس توانايي پردازش يک منبع ابري خاص و فرستادن کارهاي گروه بندي شده به منبع، بهبود مي بخشد. هدف الگوريتم حداقل کردن زمان تکميل کار نهايي و حداقل کردن هزينه است.
2-3-2-4 بهينه سازي ازدحام ذرات (PSO)
اين الگوريتم براي کارها از طريق متفاوت کردن هزينه هاي ارتباطي و محاسباتي مورد استفاده قرار مي گيرد. در اين الگوريتم هدف حداقل کردن زمان اجرا و بهبود انجام کار است. نگاشت منبع-کار بر اساس PSO در هزينه صرفه جويي مي کند و علاوه بر اين تعادل خوبي از حجم کاري روي منابع محاسباتي را از طريق توزيع کارها به منابع در دسترس فراهم مي کند.
2-3-2-5 الگوريتم توافق زمان-هزينه (CTC)
CTC براي کارهاي ابري محدود به هزينه است، در CTC بين زمان و هزينه در طول پردازش زمان بندي کردن توافقي صورت مي گيرد. اين الگوريتم به دو زير الگوريتم CTC-MC و CTC-MT تقسيم مي شود. CTC-MC هزينه را در مهلت تعيين شده ي کاربر به حداقل مي رساند، CTC-MT زمان اجرا را در بودجه ي تعيين شده ي کاربر به حداقل مي رساند. هر دو اين الگوريتم ها به کاربر اجازه مي دهد تا يک توافق قابل قبول را بين زمان اجرا و سطح اجرا برقرار کند.
2-3-2-6 چندين گردش کاري با چندين محدوديت QOS (MQMW)
MQMW به منظور زمان بندي گردش هاي کاري متعدد ابرهاي محاسباتي که محدود به چند کيفيت سرويس هستند، مي باشد. اين الگوريتم بر اساس ويژگي هاي کليدي ابرها، فاکتورهايي را بررسي مي کندکه زمان اجراي نهايي و هزينه گردش کاري را تحت تاثير قرار مي دهد.
2-3-2-7 الگوريتم زودترين زمان پايان ناهمگن (HEFT)
HEFT براي زمان بندي چند پردازنده اي نمودار وظيفه برنامه کاربردي است و شامل سه فاز وزن کردن، رتبه بندي و نگاشت مي باشد، اين الگوريتم ابتدا ميانگين زمان اجرا را براي هر کار و نيز ميانگين زمان ارتباط بين منابع از هر دو کار متوالي را محاسبه مي کند، سپس کارايي کارها را، روي يک تابع مرتب (غير افزايشي) رتبه بندي مي کند. کارها با مقدار رتبه بالاتر اولويت بالاتري دارند، در هنگام انتخاب منبع کارها با توجه به اولويتشان زمان بندي مي شوند و منبع به کاري که آن را در اسرع وقت (نزديک ترين زمان ممکن) کامل کند، اختصاص داده مي شود.
2-3-3 الگوريتم هاي فوق ابتکاري
روش هاي فوق ابتكاري از رايج ترين روش ها براي حل مسائل بهينه سازي پيچيده هستند. اين روش ها در مسائل بهينه سازي كه فضاي حالت بسيار بزرگي دارند، از يك راه حل اوليه (و يا مجموعه اي از راه حل هاي اوليه در روش هايي همچون الگوريتم هاي ژنتيك) آغاز كرده و در يك فرآيند تكراري آن راه حل را بهبود مي بخشند تا به جواب نسبتا بهينه دست پيدا كنند. اين روش ها داراي يك ساختار عمومي براي كدگذاري مسئله، و يك راهبرد كلي براي حل مسئله مي باشند. يكي از متداول ترين روش هاي فوق ابتكاري، الگوريتم هاي ژنتيك هستند. اين الگوريتم ها از يك جمعيت اوليه از راه حل ها آغاز شده و با استفاده از عملگرهاي ژنتيك همچون انتخاب، توليد مثل و جهش، نسل بعدي از راه حل ها را توليد مي كنند كه كيفيت بهتري نسبت به نسل قبلي دارند. بهبود نسل ها به طور تكراري ادامه مي يابد تا به راه حل هاي نزديك به بهينه برسيم. از الگوريتم هاي ژنتيك براي حل مسئله زمان بندي کارها بر روي سيستم هاي ناهمگون استفاده شده است.]20[
از ديگر روش هاي فوق ابتكاري شناخته شده، روش سردسازي شبيه سازي شده است كه ايده آن از نحوه ايجاد ساختارهاي كريستالي منظم با استفاده از روش سردسازي گرفته شده است.]21[
در يک تحقيق ديگر يك الگوريتم مبتني بر جستجوي هدايت شده قطعي به نام الگوريتم Push-Pull براي زمان بندي كارها در سيستم هاي ناهمگون ارائه شده است. عبارت قطعي به اين معنا است كه در ايجاد راه حل هاي داوطلب از روال هاي قطعي استفاده مي گردد، برخلاف روشهاي قبلي همچون الگوريتم هاي ژنتيك كه در آن راه حل هاي كانديد به صورت تصادفي ايجاد مي گردند. اين الگوريتم ابتدا با استفاده از يك الگوريتم شناخته شده مانند HEFT، يك زمان بندي اوليه براي مسئله ايجاد مي نمايد در يك فرآيند تكراري، اين زمان بندي با استفاده از دو روال Push و Pull بهبود مي يابد تا به جواب نسبتا بهينه دست يابد. روال Push، ابتدا مسير بحراني زمان بندي فعلي را پيدا كرده و سعي مي كند با انتقال بعضي از کارهاي آن بر روي منابع ديگر، زمان خاتمه كار را كاهش دهد. اما روال Pull، ابتدا در زمان بندي فعلي به دنبال فضاهاي آزاد بين کارها بر روي منابع جستجو مي كند، و سپس سعي مي كند با انتقال برخي کارها بر روي اين فضاهاي آزاد، زمان اجرا را كاهش دهد. اين دو روال تا زماني كه هيچ بهبودي امكان پذير نباشد، تكرار مي گردند.]22[
2-4 زمان بندي بلادرنگ
سيستم بلادرنگ، سيستمي است که در آن زمان پاسخگويي به وقايع خيلي اهميت دارد و صحت درستي يک فرايند تنها وابسته به صحت منطقي آن نباشد، بلکه به زماني که در آن اجرا مي شود نيز وابسته باشد. سيستم هاي بلادرنگ به دو دسته بلادرنگ سخت و بلادرنگ نرم تقسيم مي شوند.
بلادرنگ سخت سيستمي است که در يک مهلت زماني يا پاسخ مي دهد يا هيچ. به عبارت ديگر در مدل سخت کار انجام شده توسط سيستم، بايستي دقيقا به موقع انجام شود و هيچ گونه تاخيري قابل قبول نيست و اگر نه، سبب ناتواني سيستم مي‌شود. (کارهاي بلادرنگ سخت تاخير را مجاز نمي دانند)
سيستم بلادرنگ نرم سيستمي است که در بعضي از مواقع، آماده نشدن پاسخ در مهلت زماني تعيين شده قابل تحمل است. به عبارت ديگر در مدل نرم اگر يک ارائه دهنده خدمات نتواند در مهلت تعيين شده کار را انجام دهد و زمان اجرا بيش از مهلت تعيين شده باشد يک جريمه دريافت مي کند و باعث کاهش سودمندي مي شود. (کارهاي بلادرنگ نرم تاخير را مجاز مي دانند)
در يک سيستم بلادرنگ، کارها به دو نوع متناوب و غير متناوب تقسيم مي شوند. کارهاي متناوب با دوره تناوب مشخص تکرار مي شوند و کارهاي غير متناوب به صورت تصادفي رخ مي دهند(زمان رخ دادن مشخصي ندارند).
برخي از الگوريتم هاي زمان بندي بلادرنگ
2-4-1-1الگوريتم نرخ يکنواخت
يک الگوريتم داراي اولويت است که به هر کار ، اولويتي متناسب با فرکانس آن رخداد اختصاص داده مي شود . به عنوان مثال اگر کار 1، داراي دوره تناوب 20 ميلي ثانيه است و به آن اولويت 50 داده مي شود و به کار2 ، داراي دوره تناوب 100 ميلي ثانيه است اولويت 10 داده مي شود.
2-4-1-2 الگوريتم ابتدا زودترين مهلت(EDF)
اين الگوريتم مي گويد، بايد ليستي آماده اجرا داشته باشيم که در آن کارها به ترتيب مهلتشان مرتب شده اند. سپس کاري انجام مي شود که اول صف باشد يعني کاري که کمترين مهلت را دارد ( فرصتش از همه کمتر است).
2-4-1-3 الگوريتم کمترين لختي
اين الگوريتم مي گويد کاري انتخاب شود که کمترين لختي را دارد.
تعريف مقدار لختي يک کار :حداکثر مقدار زماني که کار مي تواند در آن مدت آماده باقي بماند و اجرا نشود. (مثال : اگر يک پروسسي 200 ميلي ثانيه وقت نياز داشته باشد و 250 ميلي ثانيه مهلت داشته باشد، لختي آن 50 ميلي ثانيه است.)
2-4-1-4 زمان بندي دو سطحي
تاکنون فرض کرده ايم که کارهاي آماده اجرا همه در حافظه اصلي قراردارند ، اما اگر حافظه اصلي به اندازه کافي نباشد برخي از کارهاي قابل اجرا در حافطه جا نمي گيرند و بايد روي ديسک نگهداري شوند . زمان تعويض کار براي کاري که در ديسک است، به علت مبادله از ديسک به حافظه اصلي ، بسيار بزرگتر از حالتي است که به کار برويم در حافظه اصلي قرار دارد. از بين کارهاي آماده اجرا ، زمان بند براي اختصاص کار به خادم از الگوريتم زمان بندي دو سطحي استفاده مي کند. اين زمان بند شامل دو سطح زمان بند سطح بالا و زمان بند سطح پايين است. زمان بند سطح بالا تعيين مب کند که کدام کارها در حافظه باشند و کدام کارها در ديسک باشند و زمان بند سطح پايين از بين آن ها که در حافظه هستند، انتخاب مي کند پردازنده به کدام يک اختصاص داده شود.
2-5 الگوريتم رقابت استعماري
الگوريتم رقابت استعماري، همانند ساير روشهاي بهينه‌سازي تکاملي، با تعدادي جمعيت اوليه شروع مي‌شود. در اين الگوريتم، هر عنصر جمعيت، يک کشور ناميده مي‌شود. کشورها به دو دسته مستعمره و استعمارگر تقسيم مي‌شوند. هر استعمارگر، بسته به قدرت خود، تعدادي از کشورهاي مستعمره را به سلطه خود درآورده و آنها را کنترل مي‌کند. سياست جذب و رقابت استعماري، هسته اصلي اين الگوريتم را تشکيل مي‌دهند. مطابق سياست جذب که به صورت تاريخي، توسط کشورهاي استعمارگري همچون فرانسه و انگليس، در مستعمراتشان اعمال مي‌شد، کشورهاي استعمارگر با استفاده از روش‌هايي همچون احداث مدارس به زبان خود، سعي در از خود بي خود کردن کشور مستعمره، با از ميان بردن زبان کشور مستعمره و فرهنگ و رسوم آن داشتند.
2-5-1 مراحل الگوريتم رقابت استعماري
شکل 2-2 فلوچارت الگوريتم رقابت استعماري را نشان مي‌دهد. همانند ديگر الگوريتم‌هاي تکاملي، اين الگوريتم، نيز با تعدادي جمعيت اوليه تصادفي که هر کدام از آنها يک "کشور" ناميده مي‌شوند؛ شروع مي‌شود. تعدادي از بهترين عناصر جمعيت به عنوان امپرياليست انتخاب مي‌شوند. باقيمانده جمعيت نيز به عنوان مستعمره، در نظر گرفته مي‌شوند. استعمارگران بسته به قدرتشان، اين مستعمرات را با يک روند خاص که در ادامه مي‌آيد؛ به سمت خود مي‌کشند. قدرت کل هر امپراطوري، به هر دو بخش تشکيل دهنده آن يعني کشور امپرياليست (به عنوان هسته مرکزي) و مستعمرات آن، بستگي دارد. در حالت رياضي، اين وابستگي با تعريف قدرت امپراطوري به صورت مجموع قدرت کشور امپرياليست، به اضافه در صدي از ميانگين قدرت مستعمرات آن، مدل شده است. با شکل‌گيري امپراطوري‌هاي اوليه، رقابت امپرياليستي ميان آنها شروع مي‌شود. هر امپراطوري‌اي که نتواند در رقابت استعماري، موفق عمل کرده و بر قدرت خود بيفزايد (و يا حداقل از کاهش نفوذش جلوگيري کند)، از صحنه رقابت استعماري، حذف خواهد شد. بنابراين بقاي يک امپراطوري، وابسته به قدرت آن در جذب مستعمرات امپراطوري‌هاي رقيب، و به سيطره در آوردن آنها خواهد بود. در نتيجه، در جريان رقابت‌هاي امپرياليستي، به تدريج بر قدرت امپراطوري‌هاي بزرگتر افزوده شده و امپراطوري‌هاي ضعيف‌تر، حذف خواهند شد. امپراطوري‌ها براي افزايش قدرت خود، مجبور خواهند شد تا مستعمرات خود را نيز پيشرفت دهند.
شكل2-2 فلوچارت الگوريتم رقابت استعماري]11[
با گذشت زمان، مستعمرات، از لحاظ قدرت به امپراطوري‌ها نزديک‌تر خواهند شد و شاهد يک نوع همگرايي خواهيم بود. حد نهايي رقابت استعماري، زماني است که يک امپراطوري واحد در دنيا داشته باشيم، با مستعمراتي که از لحاظ موقعيت، به خود کشور امپرياليست، خيلي نزديک هستند.
2-5-1-1 شکل دهي امپراطوري‌هاي اوليه
در بهينه سازي، هدف يافتن يک جواب بهينه بر حسب متغيرهاي مسئله، است. ما يک آرايه از متغيرهاي مسئله را که بايد بهينه شوند، ايجاد مي‌کنيم. در الگوريتم ژنتيک اين آرايه، کروموزوم ناميده مي‌شود. در اينجا نيز آن را يک کشور مي‌ناميم. در يک مسئله‌ي بهينه‌سازي بعدي، يک کشور، يک آرايه‌ي است. اين آرايه به صورت زير تعريف مي‌شود.
مقادير متغيرها در يک کشور، به صورت اعداد اعشاري نمايش داده مي‌شوند. از ديدگاه تاريخي‌ـ‌فرهنگي، اجزاي تشکيل دهنده يک کشور را مي‌توان ويژگي هاي اجتماعي– سياسي آن کشور، همچون فرهنگ، زبان، ساختار اقتصادي و ساير ويژگي‌ها در نظر گرفت. شکل 2-3 اين مسئله را به خوبي نشان مي‌دهد. مطابق اين شکل متغيرهاي مجهول تابع هزينه که ما در طي فرايند بهينه‌سازي به دنبال آنها مي‌گرديم، در نگاه اجتماعي‌ـ‌سياسي ويژگي‌هاي تاريخي و فرهنگي‌اي هستند که يک کشور را به نقطه مينيمم تابع هزينه رهنمون مي‌سازند. در حقيقت در حل يک مسئله بهينه‌سازي توسط الگوريتم معرفي شده، ما به دنبال بهترين کشور (کشوري با بهترين ويژگي هاي اجتماعي‌ـ‌سياسي) هستيم. يافتن اين کشور در حقيقت معادل يافتن بهترين پارامترهاي مسئله است که کمترين مقدار تابع هزينه را توليد مي‌کنند. شكل2-3 اجزاي اجتماعي سياسي تشکيل دهنده يک کشور را نشان مي دهد.
فرهنگزبانسياست اقتصاديمذهب…..
شكل2-3 اجزاي اجتماعي سياسي تشکيل دهنده يک کشور]11[
براي شروع الگوريتم، تعداد کشور اوليه را ايجاد مي‌کنيم. تا از بهترين اعضاي اين جمعيت (کشورهاي داراي کمترين مقدار تابع هزينه) را به عنوان امپرياليست انتخاب مي‌کنيم. باقيمانده تا از کشورها، مستعمراتي را تشکيل مي‌دهند که هرکدام به يک امپراطوري تعلق دارند. براي تقسيم مستعمرات اوليه بين امپريالست‌ها، به هر امپرياليست، تعدادي از مستعمرات را که اين تعداد، متناسب با قدرت آن است، مي‌دهيم. براي انجام اين کار، با داشتن هزينه همه امپرياليست‌ها، هزينه نرماليزه آنها را به صورت زير در نظر مي‌گيريم.
(2-1)
که در آن ، هزينه امپريالست nام، بيشترين هزينه ميان امپرياليست‌ها و ، هزينه نرماليزه شده اين امپرياليست، مي‌باشد. هر امپرياليستي که داراي هزينه بيشتري باشد (امپرياليست ضعيف تري باشد)، داراي هزينه نرماليزه کمتري خواهد بود. با داشتن هزينه نرماليزه، قدرت نسبي نرماليزه‌ي هر امپرياليست، به صورت زير محاسبه شده و بر مبناي آن، کشورهاي مستعمره، بين امپريالسيت‌ها تقسيم مي‌شوند.
(2-2)
از يک ديد ديگر، قدرت نرماليزه شده يک امپرياليست، نسبت مستعمراتي است که توسط آن امپرياليست اداره مي‌شود. بنابراين تعداد اوليه‌ي مستعمرات يک امپرياليست برابر خواهد بود با
(2-3)
که در آن ، تعداد اوليه مستعمرات يک امپراطوري و نيز تعداد کل کشورهاي مستعمره موجود در جمعيت کشورهاي اوليه است. نيز تابعي است که نزديک‌ترين عدد صحيح به يک عدد اعشاري را مي‌دهد. با در نظر گرفتن براي هر امپراطوري، به اين تعداد از کشورهاي مستعمره اوليه را به صورت تصادفي انتخاب کرده و به امپرياليست nام مي‌دهيم. با داشتن حالت اوليه تمام امپراطوري‌ها، الگوريتم رقابت استعماري شروع مي‌شود. روند تکامل در يک حلقه قرار دارد که تا برآورده شدن يک شرط توقف، ادامه مي‌يابد.
شکل 2-4 چگونگي شکل‌گيري امپراطوري‌هاي اوليه را نشان مي‌دهد. همانگونه که در اين شکل نشان داده شده است. امپراطوري‌هاي بزرگتر، تعداد بيشتري مستعمره دارند. در اين شکل، امپريالست شماره 1 قوي‌ترين امپراطوري را ايجاد کرده است و بيشترين تعداد مستعمرات را دارد.
شكل2-4 چگونگي شکل‌گيري امپراطوري‌هاي اوليه]12[
2-5-1-2 مدلسازي سياست جذب: حرکت مستعمره‌ها به سمت امپرياليست
سياست همگون‌سازي (جذب) با هدف تحليل فرهنگ و ساختار اجتماعي مستعمرات در فرهنگ حکومت مرکزي انجام مي‌گرفت. کشورهاي استعمارگر، براي افزايش نفوذ خود، شروع به ايجاد عمران (ايجاد زيرساخت‌هاي حمل و نقل، تاسيس دانشگاه و ...) کردند. به عنوان مثال کشورهايي نظير انگليس و فرانسه با تعقيب سياست همگون‌سازي در مستعمرات خود در فکر ايجاد انگليس نو و فرانسه نو در مستعمرات خويش بودند. با در نظر گرفتن شيوه نمايش يک کشور در حل مسلئه بهينه‌سازي، در حقيقت اين حکومت مرکزي با اعمال سياست جذب سعي داشت تا کشور مستعمره را در راستاي ابعاد مختلف اجتماعي سياسي به خود نزديک کند. اين بخش از فرايند استعمار در الگوريتم بهينه‌سازي، به صورت حرکت مستعمرات به سمت کشور امپرياليست، مدل شده است]12.[
شکل 2-5، شماي کلي اين حرکت را نشان مي‌دهد.
شكل2-5 شماي کلي حرکت مستعمرات به سمت امپرياليست]12[
مطابق اين شکل کشور امپرياليست کشور مستعمره را در راستاي محورهاي فرهنگ و زبان به سمت خود جذب مي‌کند. همانگونه که در اين شکل نشان داده شده است، کشور مستعمره (Colony)، به اندازه واحد در جهت خط واصل مستعمره به استعمارگر (Imperialist)، حرکت کرده و به موقعيت جديد(New Position of Colony) ، کشانده مي‌شود. در اين شکل، فاصله ميان استعمارگر و مستعمره با نشان داده شده است. نيز عددي تصادفي با توزيع يکنواخت (و يا هر توزيع مناسب ديگر) مي‌باشد. يعني براي داريم]13.[
(2-4)
که در آن عددي بزرگتر از يک و نزديک به 2 مي‌باشد. يک انتخاب مناسب مي‌تواند باشد. وجود ضريب باعث مي‌شود تا کشور مستعمره در حين حرکت به سمت کشور استعمارگر، از جهت‌هاي مختلف به آن نزديک شود.
شكل2-6 حرکت واقعي مستعمرات به سمت امپرياليست]12[
با بررسي تاريخي پديده همگون‌سازي، يک حقيقت آشکار در اين زمينه اين است که علي رغم اينکه کشوهاي استعمارگر بطور جدي پيگير سياست جذب بودند، اما وقايع بطور کامل مطابق سياست اعمال شده آنها پيش نمي‌رفت و انحرافاتي در نتيجه کار وجود داشت. در الگوريتم معرفي شده، اين انحراف احتمالي با افزودن يک زاويه تصادفي به مسير جذب مستعمرات، انجام مي‌گيرد. بدين منظور، در حرکت مستعمرات به سمت استعمارگر، کمي زاويه تصادفي نيز به جهت حرکت مستعمره، اضافه مي‌کنيم. شکل 2-6 اين حالت را نشان مي‌دهد. بدين منظور اين‌بار به جاي حرکت به اندازه ، به سمت کشور استعمارگر و در جهت بردار واصل مستعمره به استعمارگر، به همان ميزان، ولي با انحراف در مسير، به حرکت خود ادامه مي‌دهيم. را به صورت تصادفي و با توزيع يکنواخت در نظر مي‌گيريم (اما هر توزيع دلخواه و مناسب ديگر نيز مي‌تواند استفاده شود)]11.[
(2-5)
در اين رابطه، پارامتري دلخواه مي‌باشد که افزايش آن باعث افزايش جستجوي اطراف امپرياليست شده و کاهش آن نيز باعث مي‌شود تا مستعمرات تا حد ممکن، به بردار واصل مستعمره به استعمارگر، نزديک حرکت کنند. با در نظر گرفتن واحد راديان براي ، عددي نزديک به /4π، در اکثر پياده‌سازي ها، انتخاب مناسبي بوده است.
2-5-1-3 جابجايي موقعيت مستعمره و امپرياليست
سياست جذب در عين نابودي ساختارهاي اجتماعي سياسي کشور مستعمره در بعضي موارد نتايج مثبتي را نيز براي آنها در پي داشت. بعضي از کشورها در نتيجه اعمال اين سياست، به نوعي از خود باوري عمومي دست يافتند و پس از مدتي همان تحصيل کرد‌گان (به عبارت ديگر جذب شدگان فرهنگ استعماري) بودند، که به رهبري ملت خود براي رهايي از چنگال استعمار پرداختند. نمونه هاي فراواني از اين موارد را مي‌توان در مستعمرات انگليس و فرانسه يافت. از سوي ديگر نگاهي به فراز و نشيب چرخش قدرت در کشورها به خوبي نشان مي‌دهد که کشور هايي که زماني در اوج قدرت سياسي – نظامي بودند، پس از مدتي سقوط کردند و در مقابل کشورهايي سکان قدرت را در دست گرفتند که زماني هيچ قدرتي در دست نداشتند. در مدلسازي اين واقعه تاريخي در الگوريتم معرفي شده به اين صورت عمل شده است که در حين حرکت مستعمرات به سمت کشور استعمارگر، ممکن است بعضي از اين مستعمرات به موقعيتي بهتر از امپرياليست برسند (به نقاطي در تابع هزينه برسند که هزينه کمتري را نسبت به مقدار تابع هزينه در موقعيت امپرياليست، توليد مي‌کنند.) در اين حالت، کشور استعمارگر و کشور مستعمره، جاي خود را با همديگر عوض کرده و الگوريتم با کشور استعمارگر در موقعيت جديد ادامه يافته و اين بار، اين کشور امپرياليست جديد است که شروع به اعمال سياست همگون‌سازي بر مستعمرات خود مي‌کند. تغيير جاي استعمارگر و مستعمره، در شکل 2-7 نشان داده شده است. در اين شکل، بهترين مستعمره‌ي امپراطوري، که هزينه‌اي کمتر از خود امپرياليست دارد، به رنگ تيره‌تر، نشان داده شده است. شکل 2-8، کل امپراطوري را پس از تغيير موقعيت‌ها، نشان مي‌دهد]11.[
شكل 2-7 تغيير جاي استعمارگر و مستعمره]11[ شكل 2-8 کل امپراطوري، پس از تغيير موقعيت‌ها]11[
2-5-1-4 قدرت کل يک امپراطوري
قدرت يک امپراطوري برابر است با قدرت کشور استعمارگر، به اضافه درصدي از قدرت کل مستعمرات آن. بدين ترتيب براي هزينه کل يک امپراطوري داريم.
(2-6)
که در آن هزينه کل امپراطوري nام و عددي مثبت است که معمولا بين صفر و يک و نزديک به صفر در نظر گرفته مي‌شود. کوچک در نظر گرفتن ، باعث مي‌شود که هزينه کل يک امپراطوري، تقريبأ برابر با هزينه حکومت مرکزي آن (کشور امپرياليست)، شود و افزايش نيز باعث افزايش تاثير ميزان هزينه مستعمرات يک امپراطوري در تعيين هزينه کل آن مي‌شود. در حالت نوعي در اکثر پياده‌سازي به جوابهاي مطلوبي منجر شده است]11.[
2-5-1-5 سياست رقابت استعماري
همانگونه که قبلا نيز بيان شد، هر امپراطوري‌اي که نتواند بر قدرت خود بيفزايد و قدرت رقابت خود را از دست بدهد، در جريان رقابت‌هاي امپرياليستي، حذف خواهد شد. اين حذف شدن، به صورت تدريجي صورت مي‌پذيرد. بدين معني که به مرور زمان، امپراطوري‌هاي ضعيف، مستعمرات خود را از دست داده و امپراطوري‌هاي قوي تر، اين مستعمرات را تصاحب کرده و بر قدرت خويش مي‌افزايند. براي مدل کردن اين واقعيت، فرض مي‌کنيم که امپراطوري در حال حذف، ضعيف‌ترين امپراطوري موجود است. بدين ترتيب، در تکرار الگوريتم، يکي يا چند تا از ضعيف‌ترين مستعمرات ضعيف‌ترين امپراطوري را برداشته و براي تصاحب اين مستعمرات، رقابتي را ميان کليه امپراطوري‌ها ايجاد مي‌کنيم. مستعمرات مذکور، لزوما توسط قوي ترين امپراطوري، تصاحب نخواهند شد، بلکه امپراطوري‌هاي قوي تر، احتمال تصاحب بيشتري دارند. شکل 2-9 شماي کلي اين بخش از الگوريتم را نشان مي‌دهد]11.[
شكل 2-9 شماي کلي رقابت استعماري: امپراطوري‌هاي بزرگتر، با احتمال بيشتري، مستعمرات امپراطوري‌هاي ديگر را تصاحب مي‌کنند]11[
در اين شکل امپراطوري شماره 1 به عنوان ضعيف‌ترين امپراطوري در نظر گرفته شده و يکي از مستعمرات آن در معرض رقابت امپرياليستي قرار گرفته است و امپراطوري هاي 2 تا N براي تصاحب آن با هم رقابت مي‌کنند. براي مدلسازي رقابت ميان امپراطوري‌ها براي تصاحب اين مستعمرات، ابتدا احتمال تصاحب هر امپراطوري (که متناسب با قدرت آن امپراطوري مي‌باشد)، را با در نظر گرفتن هزينه کل امپراطوري، به ترتيب زير محاسبه مي‌کنيم. ابتدا از روي هزينه کل امپراطوري، هزينه کل نرماليزه شده آن را تعيين مي‌کنيم.
(2-7)
در اين رابطه ، هزينه کل امپراطوري nام و نيز، هزينه کل نرماليزه شده آن امپراطوري مي‌باشد. هر امپراطوري که کمتري داشته باشد بيشتري خواهد داشت. در حقيقت معادل هزينه کل يک امپراطوري و معادل قدرت کل آن مي‌باشد. امپراطوري با کمترين هزينه، داراي بيشترين قدرت است. با داشتن هزينه کل نرماليزه شده، احتمال (قدرت) تصاحب مستعمره رقابت، توسط هر امپراطوري، به صورت زير محاسبه مي‌شود.
(2-8)
با داشتن احتمال تصاحب هر امپراطوري، روشي همانند چرخه رولت در الگوريتم ژنتيک مورد نياز است تا مستعمره مورد رقابت را با احتمال متناسب با قدرت امپراطوري ها در اختيار يکي از آنها قرار دهد. در کنار امکان استفاده از چرخ رولت موجود، در اين نوشتار مکانيزم جديدي براي پياده‌سازي اين فرايند معرفي شده است که نسبت به چرخه رولت داراي هزينه محاسباتي بسيار کمتري مي‌باشد. زيرا عمليات نسبتا زياد مربوط به محاسبه تابع توزيع جمعي احتمال را که در چرخه رولت مورد نياز است را حذف مي‌کند و فقط به داشتن تابع چگالي احتمال نياز دارد. در ادامه مکانيزم مطرح شده براي اختصاص متناسب با احتمال مستعمره مورد رقابت به امپراطوري هاي رقيب توضيح داده مي‌شود.
با داشتن احتمال تصاحب هر امپراطوري، براي اينکه مستعمرات مذکور را به صورت تصادفي، ولي با احتمال وابسته به احتمال تصاحب هر امپراطوري، بين امپراطوري‌ها تقسيم کنيم؛ بردار را از روي مقادير احتمال فوق، به صورت زير تشکيل مي دهيم.
بردار داراي سايز 1*Nimp مي‌باشد و از مقادير احتمال تصاحب امپراطوري‌ها تشکيل شده است. سپس بردار تصادفي ، هم سايز با بردار را تشکيل مي‌دهيم. آرايه‌هاي اين بردار، اعدادي تصادفي با توزيع يکنواخت در بازه [0,1] مي‌باشند.
سپس بردار را به صورت زير تشکيل مي‌دهيم.
با داشتن بردار ، مستعمرات مذکور را به امپراطوري‌اي مي‌دهيم که انديس مربوط به آن در بردار بزرگتر از بقيه مي‌باشد. امپراطوري‌اي که بيشترين احتمال تصاحب را داشته باشد، با احتمال بيشتري انديس مربوط به آن در بردار ، بيشترين مقدار را خواهد داشت. عدم نياز به محاسبه CDF باعث مي‌شود که اين مکانيزم نسبت به چرخه رولت با سرعت به مراتب بيشتري عمل کند. مکانيزم جديد مطرح شده نه تنها مي‌تواند در اختصاص مستعمره به امپراطوري بر حسب احتمال تصاحب آنها مفيد باشد، بلکه به عنوان يک مکانيزم انتخاب بر حسب احتمال مي‌تواند جايگزين چرخه رولت در الگوريتم ژنتيک براي انتخاب والدين شود و سرعت اجراي عمليات در آن را تا حد زيادي افزايش دهد.
با تصاحب مستعمره توسط يکي از امپراطوري ها، عمليات اين مرحله از الگوريتم نيز به پايان مي‌رسد.
2-5-1-6 سقوط امپراطوري‌هاي ضعيف
همانگونه که بيان شد، در جريان رقابت‌هاي امپرياليستي، خواه ناخواه، امپراطوري هاي ضعيف به تدريج سقوط کرده و مستعمراتشان به دست امپراطوري‌هاي قوي‌تر مي‌افتد. شروط متفاوتي را مي‌توان براي سقوط يک امپراطوري در نظر گرفت. در الگوريتم پيشنهاد شده، يک امپراطوري زماني حذف شده تلقي مي‌شود که مستعمرات خود را از دست داده باشد. شکل 2-10 اين مسئله را به خوبي نشان مي‌دهد. در اين شکل، امپراطوري شماره 4 به علت از دست دادن کليه مستعمراتش، ديگر قدرتي براي رقابت ندارد و بايد از ميان بقيه امپراطوري‌ها حذف شود]11[.
شکل 2-10 سقوط امپراطوري ضعيف ]11[
2-5-1-7 همگرايي
الگوريتم مورد نظر تا برآورده شدن يک شرط همگرايي، و يا تا اتمام تعداد کل تکرارها، ادامه مي‌يابد. پس از مدتي، همه امپراطوري‌ها، سقوط کرده و تنها يک امپراطوري خواهيم داشت و بقيه کشورها تحت کنترل اين امپراطوري واحد، قرار مي‌گيرند. در اين دنياي ايده آل جديد، همه‌ي مستعمرات، توسط يک امپراطوري واحد اداره مي‌شوند و موقعيت‌ها و هزينه‌هاي مستعمرات، برابر با موقعيت و هزينه کشور امپرياليست است. در اين دنياي جديد، تفاوتي، نه تنها ميان مستعمرات، بلکه ميان مستعمرات و کشور امپرياليست، وجود ندارد. به عبارت ديگر، همه‌ي کشورها، در عين حال، هم مستعمره و هم استعمارگرند. در چنين موقعيتي رقابت امپرياليستي به پايان رسيده و به عنوان يکي از شروط توقف الگوريتم متوقف مي‌شود. شبه کد مربوط به الگوريتم رقابت استعماري در شکل 2-11، نشان داده شده است]11.[
001- چند نقطه تصادفي روي تابع انتخاب کرده و امپراطوري‌هاي اوليه را تشکيل بده.2- مستعمرات را به سمت کشور امپرياليست حرکت بده (سياست همسان‌سازي).3- اگر مستعمره‌اي در يک امپراطوري، وجود داشته باشد که هزينه‌اي کمتر از امپرياليست داشته باشد؛ جاي مستعمره و امپرياليست را با هم عوض کن.4- هزينه‌ي کل يک امپراطوري را حساب کن (با در نظر گرفتن هزينه‌ي امپرياليست و مستعمراتشان). 5- يک مستعمره از ضعيف‌ترين امپراطوري انتخاب کرده و آن را به امپراطوري‌اي که بيشترين احتمال تصاحب را دارد، بده.6- امپراطوري‌هاي ضعيف را حذف کن.7- اگر تنها يک امپراطوري باقي مانده باشد، توقف کن وگرنه به 2 برو.001- چند نقطه تصادفي روي تابع انتخاب کرده و امپراطوري‌هاي اوليه را تشکيل بده.2- مستعمرات را به سمت کشور امپرياليست حرکت بده (سياست همسان‌سازي).3- اگر مستعمره‌اي در يک امپراطوري، وجود داشته باشد که هزينه‌اي کمتر از امپرياليست داشته باشد؛ جاي مستعمره و امپرياليست را با هم عوض کن.4- هزينه‌ي کل يک امپراطوري را حساب کن (با در نظر گرفتن هزينه‌ي امپرياليست و مستعمراتشان). 5- يک مستعمره از ضعيف‌ترين امپراطوري انتخاب کرده و آن را به امپراطوري‌اي که بيشترين احتمال تصاحب را دارد، بده.6- امپراطوري‌هاي ضعيف را حذف کن.7- اگر تنها يک امپراطوري باقي مانده باشد، توقف کن وگرنه به 2 برو.
شکل2-11 شبه کد مربوط به الگوريتم رقابت استعماري]11[
شماي کلي الگوريتم در شکل 2-12 نيز نشان داده شده است. مطابق اين شکل، الگوريتم با جمعيت اوليه تصادفي و تشکيل امپراطوري هاي اوليه آغاز شده و در يک چرخه سياست جذب و رقابت امپرياليستي تکرار مي‌شوند]11[.
شکل 2-12 شماي کل الگوريتم رقابت استعماري به صورت گرافيکي]11[
2-5-2 مزاياي الگوريتم رقابت استعماري
الگوريتم توسعه داده شده، در وهله اول با داشتن يک ديدگاه کاملأ نو به مبحث بهينه‌سازي، پيوندي جديد ميان علوم انساني و اجتماعي از يک سو و علوم فني و رياضي از سوي ديگر، برقرار مي‌کند. ارتباط ميان اين دو شاخه از علم به گونه‌اي مي‌باشد که غالبا رياضيات به عنوان ابزاري قوي و دقيق در خدمت علوم انساني کلي نگر قرار گرفته و به درک و تحليل نتايج آن کمک مي‌کند. اما الگوريتم توسعه داده شده بر خلاف معمول، نقطه‌ي قوت علوم انساني و اجتماعي، يعني کلي‌نگري و وسعت ديد آن را به خدمت رياضيات درآورده و از آن به عنوان ابزاري براي درک بهتر رياضيات و حل بهتر مسائل رياضي استفاده مي‌کند. بنابراين حتي بدون در نظر گرفتن قابليت‌هاي رياضي و عملي روش توسعه داده شده، پيوند ايجاد شده ميان اين دو شاخه به ظاهر جدا از هم، به عنوان يک پژوهش ميان رشته‌اي، در نوع خود داراي ارزش بسياري مي‌باشد]11.[
مزاياي الگوريتم اجتماعي پيشنهادي را مي‌توان به صورت زير خلاصه کرد:
نو بودن ايده‌ي پايه‌اي الگوريتم: به عنوان اولين الگوريتم بهينه سازي مبتني بر يک فرايند اجتماعي‌ـ سياسي
مبتني بر رفتار اجتماعي انسان که هوشمندانه تر از رفتار هاي بيولوژيکي اوست.
سرعت همگرايي بالا
توانايي بهينه سازي توابعي با تعداد متغيير زياد: توانايي بهينه سازي هم‌تراز و حتي بالاتر در مقايسه با الگوريتم هاي مختلف بهينه سازي، در مواجهه با انواع مسائل بهينه سازي
سرعت مناسب يافتن جواب بهينه
2-6 تحقيقات انجام شده در زمان بندي ابرهاي محاسباتي
موازنه بار که يکي از چالش هاي اصلي در ابرهاي محاسباتي است، را مي توان به عنوان يک مسئله بهينه سازي در نظر گرفت. در مقاله]30[ استراتژي موازنه بار با استفاده از الگوريتم ژنتيک ( GA ) پيشنهاد شده است. نتايج شبيه سازي براي يک کاربرد نمونه معمولي نشان مي دهد که الگوريتم پيشنهاد شده عملکرد بهتري نسبت به روش FCFS ، دوره گرد(RR) و الگوريتم هاي جستجوي محلي تصادفي تپه نوردي ( SHC ) دارد.
Chenhong Zhao و Shanshan Zhang بيان مي دارند يک الگوريتم بهينه سازي شده بر اساس الگوريتم ژنتيک جهت زمان بندي کارهاي مستقل از هم و بخش پذير مطابق با محاسبات مختلف ارائه شده است. بنابراين آنها با تحقيقات بيشتر در زمينه زمان بندي، بهينه سازي با الگوريتم ژنتيک را نتيجه گرفته اند به طوري که براي هر کار ويژگي هايي از جمله زمان رسيدن، بدترين حالت زمان محاسبه و پايان فرصت را در نظر گرفته اند، همچنين هر واحد فرايند داراي صف مختص خود مي باشد، علاوه بر اين دو بردار CRV (بردار m جزئي براي هرکار) و CSV (بردار m جزئي براي هر واحد فرايند) دارد که از آن ها براي بدست آوردن راه حل هاي ممکن استفاده مي شود.]1[
هديه ساجدي و سيد جواد عبداللهي يک زمان بندي کار بر اساس الگوريتم رقابت استعماري بهبود يافته را بيان کرده اند، در اين زمان بندي ارائه شده، به خصوصيت پهناي باند و زمان ارسال کارها نيز توجه شده است براي توازن بار مناسب و افزايش بهره وري منابع، از تابع هزينه جديدي براي محاسبه زمان اجراي کارها بر روي منابع موجود در محيط ابر استفاده کرده اند.]36[
Shuo Liu و همکارانش يک زمان بندي براي کارهاي بلادرنگ ارائه داده اند بر اساس تابع مطلوبيت زمان که بيان مي دارد در انجام عمل زمان بندي براي کارهاي بلادرنگ فقط به بهبود دادن زمان انجام کارها نبايد اکتفا کرد و بلکه علاوه بر بهينه کردن زمان اجرا به مهلت انجام کار نيز بايد توجه کرد.]14[
Weisong Shi ,zhifeng Yu در استراتژي خود تمام برنامه ها را در يک صف قرار مي دهند و تصميم مي گيرند کدام برنامه بايد اول اجرا شود و اگر برنامه جديدي رتبه ي بهتري در صف کار ها داشته باشد زودتر اجرا مي شود. اين الگوريتم نيز فقط مخصوص زمان اجراي برنامه ها است و ساير نياز هاي کيفيت سرويس مانند هزينه (کاهش تعداد خادم هاي مورد استفاده) را برآورد نمي کند.]15[
Elana و همکاران يک الگوريتم ژنتيک در جهت پيدا کردن بهترين راه حل زمان بندي، پياده سازي کرده اند که علاوه بر قابليت هاي ماشين مجازي، الگوريتم آنها همچنين سياست خوبي در جهت پيدا کردن راه حل زمان بندي مناسب تعريف شده و براي عملکرد و مقياس پذيري، بهينه سازي در نظر دارد. آن ها مجموع وزني CPU هاي موجود، RAM و ديسک را در الگوريتم تصميم گيري در نظر گرفته اند.]16[
ژنگ و همکاران يک الگوريتم زمان بندي بهينه سازي شده براي رسيدن به بهينه سازي مشکلات زمان بندي ابر، پيشنهاد داده اند. آن ها همچنين جمع ساده اي از CPU، RAM و هارد ديسک در تابع برازندگي خود در نظر گرفته اند.]18[
احسان آريانيان و داوود مالکي بيان مي دارند که زمان بندي منابع کارآمد و مديريت منابع در دسترس به يک نگراني بزرگ درمراکز داده مدرن تبديل شده است. در اين تحقيق نسخه بهبود يافته الگوريتم تخصيص منابع بر اساس الگوريتم ژنتيک ارائه شده است و در نظر گرفتن پارامترهاي بيشتر درالگوريتم تخصيص منابع لازم است. علاوه بر اين، اهميت توجه به وزن براي پارامترهاي الگوريتم تصميم گيري ارائه شده است. در اين تحقيق نشان داده شده است که برخي از پارامترها نسبت به بقيه مهمتر هستند و بايد تاثير بيشتري درتابع الگوريتم ژنتيک داشته باشد.]7[
آرش قربان نيا و يلدا آرين يافتن يک راه حل مناسب جهت نگاشت مجموعه اي از کارهاي داراي مهلت اجرا به منابع در دسترس سيستم با توجه به شرايط سيستم ابرهاي محاسباتي ارايه کرده اند. در نتيجه هدف الگوريتم به كارگيري تكنيك ها و پارامترهاي مناسب در هر مرحله به منظور امكان برقراري توازن بار با پيچيدگي زماني كمتر و همچنين زمان اجراي كوتاه تر دسته درخواست ها نسبت به الگوريتم هاي ديگر مي باشد.]35[
ناديا حاضري ومحمود احمدي به استراتژي هاي جديدي كه توانسته اند به چندين نياز كيفي خدمات رساني مانند بهينه كردن توام زمان و هزينه رسيدگي كنند، پرداخته اند. در تحقيق آن ها الگوريتم ارايه شده زمان بندي محدود به كيفيت خدمات رساني چندگانه براي چندين جريان هاي كاري متعدد MQMW به كاهش توام زمان و هزينه باهم مي پردازد و بهترين سرويس دهي ممكن را حتي هنگامي كه كاربران چندين كارمتنوع را براي ابر ارسال مي كنند انجام مي دهد، استراتژي زمان بندي ديگر الگوريتم ژنتيك التهاب شبيه سازي شده براي محاسبات ابري است كه با ارزيابي تمام نيازمندي هاي خدمات رساني به كاربران به جستجوي منابع مورد نياز آنها برروي ماشين هاي مجازي پرداختند و بهينه ترين زمان بندي كارها را با بهترين كيفيت خدمات رساني ارايه داده اند.]31[
Ali Heydarzadegan و همکارانش يک روش زمان بندي براي کارهاي بلادرنگ در محيط ابر محاسباتي با استفاده از الگوريتم ژنتيک ارائه داده اند، در اين روش از بخش بندي کروموزوم و شيوه تعادل بار براي اختصاص کارها به منابع استفاده کرده اند، همچنين بيان مي دارند که براي انجام کارهاي بلادرنگ هرچه تعداد منابع بيشتر باشد، بهتر است. روش ارائه شده به مهلت انجام کار توجه کرده است ولي به کاهش تعداد منابع مورد استفاده توجهي نکرده است.]2[
2-7 جمع بندي و نتيجه گيري
همان طور که بيان شد در بيشتر کارهاي انجام شده براي زمان بندي کارها در ابرهاي محاسباتي تنها به زمان اجراي کارها توجه شده بود و به مهلت تعيين شده براي دريافت پاسخ، زمان ارسال کارها و کاهش تعداد منابع مصرفي (استفاده از حداکثر ظرفيت منبع) توجه چنداني نشده است، همچنين در تعداد محدودي از موارد ارائه شده، زمان بندي براي کارهاي بلادرنگ انجام گرفته است. در اين تحقيق قصد داريم با استفاده از الگوريتم رقابت استعماري، که يک الگوريتم فوق ابتکاري است، براي دست يابي به پاسخ بهينه جهت نگاشت کارها به منابع موجود در محيط ابرهاي محاسباتي، الگوريتمي براي زمان بندي کارهاي بلادرنگ نرم در محيط ابرهاي محاسباتي طراحي شود که بتواند برنامه را در کمترين زمان ممکن، پيش از مهلت تعيين شده و با استفاده از کمترين تعداد منابع اجرا نمايد، با اين هدف که از توانايي هاي الگوريتم رقابت استعماري، با توجه به سرعت مناسب آن در يافتن پاسخ بهينه، استفاده شود.
مراجع
[1] Chenhong Zhao, Shanshan Zhang, Qingfeng Liu“Independent Tasks Scheduling Based on Genetic Algorithm in Cloud Computing” IEEE, 25, 2009.
[2] Ali Heydarzadegan, Yaser Nemati,Mohammad Iman Jamnezhad, Mohsen Moradi “Offering a New Approach to Optimal Scheduling of Tasks in the Cloud Using Chromosome Portioning” International Research Journal of Applied and Basic Sciences, 2014.
[3] Saswati Sarkar “ Optimum Scheduling and Memory Management inInput Queued Switches with Finite Buffer Space”, IEEE 1373, 2003.
[4] LeeCY，Piramuthu S.Tsai YK．”Job shop scheduling with a genetic algorithm and machine 1earning “ Inr J. Pred Res,35-4,1171, 1997.
[5] Radoslaw Szymanek and Krzysztof Kuchcinski, “ Task Assignment and Scheduling under Memory Constraints ” , IEEE, 2000.
[6] Kousik Dasgupta, Brototi Mandal, Paramartha Dutta, Jyotsna Kumar Mondal,Santanu Dam“ A Genetic Algorithm (GA) based Load Balancing Strategy for Cloud Computing” International Conference on Computational Intelligence: Modeling Techniques and Applications (CIMTA) ,Elsevier, 340, 2013.
[7] Ehsan Arianyan,Davood maleki,Alireza Yari“ Efficient Resource Allocation in Cloud Data Centers Through Genetic Algorithm” IEEE, 2012.
[8] Rajkumar Buyya, Chee Shin Yeo, Srikumar Venugopala, James Broberg, Ivona Brandic, “Cloud computing and emerging IT platforms: Vision, hype, and reality for delivering computing as the 5th utility” Future Generation Computer Systems, ELSEVIER,2008
[9] http://fa.wikipedia.org/wiki/رايانش ابري
[10] Rajkumar Buyya, William Voorsluys, James Broberg, and, Introduction to Cloud Computing, Cloud Computing: Principles and Paradigms, R. Buyya, J. Broberg, A.Goscinski (eds), ISBN-13: 978-0470887998, Wiley Press, New York, USA, February 2011.
[11] Atashpaz-Gargari, E.; Lucas, C., "Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition," Evolutionary Computation, 2007. CEC 2007. IEEE, 2007.
[12] Hamid Taghavifar, Aref Mardani, Leyla Taghavifar, A hybridized artificial neural network and imperialist competitive algorithm optimization approach for prediction of soil compaction in soil bin facility, Measurement, Volume 46, Issue 8, 2288-2299, 2013.
[13] J. Wiley & Sons, Inc., Hoboken. ” Discovering knowledge in data, An Introduction to Data Mining”, In New Jersey and Canada, 2005.
[14] Shuo Liu, Gang Quan, Shangping Ren, “On-line Scheduling of Real-time Services for Cloud Computing”, IEEE, 6th World Congress on Services, 2010.
[15] Zhifeng Yu and Weisong Shi, "A Planner-Guided Scheduling Strategy for Multiple WorkApplications," icppw, International Conference on Parallel Processing, 1-8, 2008.
[16] Elena Apostol, Iulia Baluta, Alexandru Gorgoi, Valentin Cristea. “Efficient Manager for Virtualized Resource Provisioning in Cloud Systems”, IEEE International Conference on Intelligent Computer Communication and Processing (ICCP),511 – 517, 2011.
[17] Hai Zhong, Kun Tao, Xuejie Zhang, “An Approach to Optimized Resource Scheduling Algorithm for Open-source Cloud Systems”,The fifth annual ChinaGrid conference, 124-128, 2010.
[18] Zhongni Zheng, Rui Wang, Hi Zhong, Xuejie Zhang, “An Approach for Cloud Resource Schedulgin Based on Prallel Genetic Algorithm”, 3rd International Conference on Computer Research and Development (ICCRD), 444 – 447, 2011.
[19] Y. K. Kwok and I. Ahmad, “Static scheduling algorithms for allocating directed task graphs to multiprocessors,” ACM Computing Surveys, vol. 31, no. 4,406–471, 1999.
[20] L. Wang, H. J. Siegel, V. R. Roychowdhury, and A. A. Maciejewski, “Task matching and scheduling in heterogeneous computing environments using a geneticalgorithmbased approach,” Journal of Parallel and Distributed Computing, vol. 47, pp. 8–22, 1997.
[21] M. Aggarwal, R. Kent, and A. Ngom, “Genetic algorithm based scheduler for computational grids,” in 19th International Symposium on High Performance Computing Systems and Applications (HPCS 2005), pp. 209 – 215,2005.
[22] S. C. Kim, S. Lee, and J. Hahm, “Push-Pull: Deterministic search-based DAG scheduling for heterogeneous cluster systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 11, pp. 1489–1502, 2007.
[23] Rajkumar Buyya, Chee Shin Yeo, Srikumar Venugopal, James Broberg, and Ivona Brandic, “Cloud Computing and Emerging IT Platforms: Vision, Hype, and Reality for Delivering Computing as the 5th Utility”, Future Generation Computer Systems, Elsevier Science, Amsterdam, Volume 25, Number 6, pp. 599-616,2009.
[24] Brian Hayes, Cloud computing, Communications of the ACM, Volume 51, Issue 7, July 2008.
[25] J. Yu and R. Buyya, "Task Scheduling Algorithms for Grid Computing", Metaheuristics for Scheduling in Distributed Computing Environments, F. X. a. A. Abraham, ed., Springer, 2008.
[26] IanFoster, Yong Zhao, Ioan Raicu and Shiyong Lu, “Cloud Computing and Grid Computing 360-Degree Compared”, Grid Computing Environments Workshop,2008.
[27] Zhan, Sh., Huo, H., "Improved PSO-based Task Scheduling Algorithm in Cloud Computing ", Journal of Information & Computational Science, 2013.
[28] Chawla, Y., Bhonsle, M., "A Study on Scheduling Methods in Cloud", International Journal of Emerging Trends & Technology in Computer Science, Vol. 1, pp. 12-17, 2012
[29] Gua, G., Ting, H., “Genetic Simulated Annealing for Task Scheduling based on cloud Computing Environment”, Intelligent Computing and Integrated Systems (ICISS), pp. 60-63, 2010.
]30[ اسماعيل آتش پز گرگري." توسعه الگوريتم بهينه‌سازي اجتماعي و بررسي کارايي آن"، (1387).
]31 [ناديا حاضري ومحمود احمدي "استراتژيهاي جديد زمان بندي كارها براساس كيفيت خدمات رساني به كاربران درمحيط محاسبات ابري " اولين همايش ملي رويكردهاي نوين در مهندسي كامپيوتر و بازيابي اطلاعات، (1392).
]32 [ بهشتي،محمد تقي،سروي،معين، "رايانش ابر: ساختار، مزايا و چالش ها".اولين کارگاه ملي رايانش ابري ايران، (1391).
]33[ غفاري، اميررضا،"سيستم هاي محاسبات ابرين:نمونه ها؛ کاربردها؛ چالش ها".دانشگاه شهيد بهشتي، (1389).
]34 [ شمس، زينب، فراهي، احمد، "بررسي قابليت اطمينان الگوريتم هاي زمان بندي در محيط محاسبات ابري". اولين همايش استفاده از فناوري اطلاعات و شبکه هاي کامپيوتري دانشگاه پيام نور، دانشگاه پيام نور واجد طبس، (1391).
]35[ آرش قربان نيا و يلدا آرين" ارايه يك روش زمان بندي تركيبي برمبناي الگوريتم ژنتيك درمحيط محاسبات ابري" اولين همايش تخصصي سيستمهاي هوشمند كامپيوتري و كاربردهاي آنها، (1390) .
]36[ هديه ساجدي و سيد جواد عبداللهي "زمان بندي وظايف در محيط رايانش ابري با استفاده از الگوريتم رقابت استعماري بهبود يافته" نوزدهمين کنفرانس ملي سالانه انجمن کامپيوتر ايران، دانشگاه شهيد بهشتي، تهران، (1392).
Abstract
Task scheduling algorithm, which is an NP-completeness problem, plays a key role in cloud computing systems. Imperialist competitive algorithm is one of the newest evolutionary optimization algorithms. As its name suggests, this algorithm is based on the socio-political phenomenon of colonialism modeling.
In this study, using the Imperialist competitive algorithm, An algorithm for soft real-time tasks scheduling in the cloud computing environment is designed to implement the program before the deadline set by the user, And on equal terms has declined the execution time and using the minimum number of resources compared to methods based on genetic algorithm.we prompt the algorithm in heterogeneous systems, where resources are of computational and communication heterogeneity. Dynamic scheduling is also in consideration.
In this study, using the ICA algorithm for soft real-time tasks scheduling in the cloud computing environment for two session, 200 servers and 400 servers and works in this system as 16th to 4096th, result in this system compaire with the GA algorithm for real-time tasks scheduling in the cloud computing environment,so the ICA algorithm for real-time tasks scheduling in the cloud computing environment optimized than the GA algorithm for real-time tasks scheduling in the cloud computing environment.
In this study, with using the Imperialist competitive algorithm for scheduling real-time tasks in the cloud computing environment, optimized use of resources, the ratio between the expected execution time and execution time is less and optimal fitness value is better.
Key words:
Cloud computing, Real-time Tasks, Genetic algorithm, Imperialist competitive algorithm
Salman Institute of Higher Education
Department of Computer (software)
«M.Sc.» Thesis
Title:
Realtime Tasks Scheduling in Cloud Computing with using ICA Algorithm
Supervisor:
Dr.Hossein Deldari
Advisor:
Dr.Esmaeil Kheirkhah
By:
Hesam Khosravi Bizhaem
قیمت: 59٬000 تومان
قیمت: 59٬000 تومان
قیمت: 59٬000 تومان
قیمت: 59٬000 تومان
قیمت: 59٬000 تومان
قیمت: 59٬000 تومان
قیمت: 59٬000 تومان
قیمت: 59٬000 تومان
قیمت: 59٬000 تومان
قیمت: 59٬000 تومان
