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

پروپوزال زمانبندی کارهای فوری در رایانش ابری با الگوریتم 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[ انجام مي گردد . روش پيشنهادي 3-1 مقدمه در اين فصل به بيان روش ارائه شده براي زمان بندي کارهاي بلادرنگ بر اساس الگوريتم رقابت استعماري در محيط ابرهاي محاسباتي پرداخته مي شود. 3-1-1 بيان مساله محيط ابرهاي محاسباتي از چندين عرضه کننده تشکيل مي گردد که هريک منابعي را در اختيار کاربران قرار مي دهند. هر مرکز داده ابري از تعداد زيادي خادم تشکيل شده و درخواست هاي کاربران توسط اين خادم ها سرويس دهي مي شود. کارها به عنوان ماشين مجازي به خادم ها تخصيص داده و اجرا مي شوند. در اين تحقيق براي دست يابي به پاسخ بهينه از الگوريتم رقابت استعماري جهت نگاشت ماشين هاي مجازي به خادم هاي موجود، براي زمان بندي کارهاي بلادرنگ در محيط ابرهاي محاسباتي استفاده شده است که بتواند برنامه را در کمترين زمان ممکن، پيش از مهلت تعيين شده و با استفاده از کمترين تعداد منابع اجرا نمايد. 3-1-2 پارامترهاي زمان بندي فرض کنيد يک سيستم محاسبات ابري شامل m خادم ناهمگن (1m>) مي باشد. ويژگي هاي کارها در اين سيستم به شرح زير است: کارها دوره اي () مي باشد. (به عنوان مثال، زمان رسيدن کار مشخص شده نيست. هر کار داراي ويژگي هاي زمان رسيدن() ، بدترين حالت زمان محاسبه() و پايان فرصت (مهلت اجرا) () است. زمان آماده به کار برابر با زمان ورود آن است.) کارها مستقل از يکديگر هستند. هر کار داراي دو راه دسترسي به يک واحد فرآيند است: دسترسي منحصر به فرد، که در اين صورت هيچ کار ديگري نمي تواند از آن منابع استفاده نمايد، يا دسترسي اشتراکي، که در آن صورت مي توان منابع را با کار ديگري به اشتراک گذاشت (کار ديگر نيز بايد مايل به اشتراک گذاشتن منابع باشد.) 3-1-2-1 مدل زمان بندي دراين روش فرض شده است که زمان بندي متمرکز است؛ يعني يک واحد پردازنده اصلي در ابر، وظيفه جمع آوري تمام کارها، اندازه انتظار جهت توزيع و ورود به واحد ديگر را بر عهده دارد. هر خادم داراي يک صف توزيع مختص خود مي باشد. واحد اصلي از طريق اين صف توزيع با واحدها ارتباط برقرار مي کند. واحد اصلي به صورت موازي با واحدهاي ديگر کار مي کند، کارهاي تازه رسيده را زمان بندي مي کند، و به صورت دوره اي صف توزيع را به روز رساني مي کند. کارها به صورت صعودي با مقدار پايان دورهشان (مهلت اجرا) طبقه بندي شده اند. 3-1-2-2 تطابق اوليه هر زمان بندي به صورت يک رشته متشکل از يک راه حل نشان داده مي شود. هر رشته به عنوان يک کشور در الگوريتم رقابت استعماري در نظر گرفته مي شود، شکل 3-1 نمايي از يک کشور را نشان مي دهد. …… شکل3-1 نمونه کشور به کار گرفته در الگوريتم پيشنهادي در هر راه حل براي هر ماشين مجازي، خادمي مناسب از ميان خادم ها، در نظر گرفته مي شود که در واقع نشان مي دهد هر ماشين مجازي به خادم موجود در ستون مربوطه نگاشت داده مي شود. هر کشور، داراي N کلوني مي باشدکه طول کشور را تشکيل مي دهند، تعداد کلوني ها برابر تعداد کارهاي ورودي به سيستم ( ماشين هاي مجازي) مي باشد. مرکز داده سيستم ابر وظيفه جمع آوري و نگهداري اطلاعات مربوط به خادم را بر عهده دارد. در اين روش براي ايجاد هر کشور از درون يک ليست مرتب شده از خادم هاي آماده موجود، برگرفته از ليست خادم ها در مرکز داده سيستم ابر، خادمي براي هر ماشين مجازي در نظر گرفته مي شود، اين ليست در انجام هر کدام از عمليات ايجاد جمعيت اوليه، جذب، انقلاب و سياست رقابت استعماري به روز رساني مي شود. شکل 3-2 فلوچارت حل مسئله را نشان مي دهد. 2819400-666750شروع00شروع1548130328295انطباق هر ماشین مجازی به یک خادم مطابق با تطابق اولیه00انطباق هر ماشین مجازی به یک خادم مطابق با تطابق اولیه3346450146685002224405-175895اختصاص هر کار به یک ماشین مجازی00اختصاص هر کار به یک ماشین مجازی3329305-34925000 1532890408305کشورهای اولیه تولید می شوند. (به تعداد کلیه راه حل های ممکن)00کشورهای اولیه تولید می شوند. (به تعداد کلیه راه حل های ممکن)332105022161500 332105029718000 332041538100000160083555245با استفاده از تابع برازندگی، زمان اجرای فرایند ها بدست می آید.00با استفاده از تابع برازندگی، زمان اجرای فرایند ها بدست می آید. 1017270120650استعمارگران اولیه انتخاب می شوند.(10 کشوری که دارای کمترین مقدار برازندگی می باشند.)00استعمارگران اولیه انتخاب می شوند.(10 کشوری که دارای کمترین مقدار برازندگی می باشند.) 2447925183515تشکیل امپراطوری های اولیه00تشکیل امپراطوری های اولیه33464502222500 90487518224500904875182245001254125259080سیاست جذب ( Beta=2) اعمال می شود و تابع هزینه موقعیت جدید محاسبه می شود.00سیاست جذب ( Beta=2) اعمال می شود و تابع هزینه موقعیت جدید محاسبه می شود.33896308382000 2230120294640انقلاب (pRevolution=0.2) اعمال می شود.00انقلاب (pRevolution=0.2) اعمال می شود.34124909525000 340741012954000 1800225349250001813560351155002125980635خیر00خیر29743401270وجود مستعمره با هزینه کمتر از استعمارگرش00وجود مستعمره با هزینه کمتر از استعمارگرش3074035-254000 2686050309881بله00بله341185539497000 3460750400685002153285117475جای آن مستعمره با استعمارگرش عوض می شود.00جای آن مستعمره با استعمارگرش عوض می شود. 180403548260002205990143510قدرت کل امپراطوری محاسبه می شود.00قدرت کل امپراطوری محاسبه می شود. 2210435164465عملیات رقابت استعماری انجام می شود.00عملیات رقابت استعماری انجام می شود.3469005-63500 2222500295910خیر00خیر3039745229870وجود امپراطوری بدون مستعمره00وجود امپراطوری بدون مستعمره31724602825750034639252413000 183832516002000185420015557500 2773680117475بله00بله347789526543000 1847850378460003482340309245002220595-635حذف امپراطوری بدون مستعمره00حذف امپراطوری بدون مستعمره 2837815671195بله00بله3512820782320002377440127635خیر00خیر909320408305003121660148590برآورده شدن شرط توقف00برآورده شدن شرط توقف324993012763500شکل3-2 فلوچارت حل مساله 3009900717550پایان00پایان مسئله پوياي مورد نظر عنوان مي کند که کار بايد قبل از زمان پايان ملاقات شود، لذا فرض بر اين است که اگر يک کار نتواند در مهلت مشخص به زمان پايان برسد، جهت تاخير مي بايست يک جريمه دريافت کند. 3-1-3 تابع هدف در تابع فوق نشان دهنده زمان پايان کارk ام است. تابع تنبيه (جريمه) مي باشد که به صورت زير عمل مي کند، مهلت اجراي کار i ام و به معني زمان واقعي پايان کار i ام است. نشان دهنده مقدار ظرفيت باقيمانده از خادم j ام مي باشد. در تابع تنبيه(جريمه) و هزينه هاي تاخير را تنظيم مي کنند. نحوه انجام عمل زمان بندي همانطور که در فصل دوم بيان شد، کارهاي بلادرنگ با توجه به مهلت اجرا (deadline) خود به دو دسته سخت و نرم تقسيم مي شوند. پس در کل، دو مدل مختلف ماشين مجازي در ابرهاي محاسباتي تعريف شده است و کار ما از نوع نرم آن مي باشد. مدل ماشين مجازي بلادرنگ نرم ماشين مجازي بلادرنگ نرم را با نام SRT-VM تعريف مي کنيم و داراي مشخصه هايي از جمله (بهره وري پردازنده)، (تعداد ميليون دستورالعمل ها در ثانيه)، (مهلت اجرا) مي باشد. اگر محاسبات در زمان انجام شود و اين زمان از مهلت اجرا گذشته باشد، توسط تابع جريمه يک جريمه به آن داده مي شود. 3-1-4-2 مدل خادم خادم ها داراي دو مشخصه ظرفيت و ظرفيت باقي مانده هستند که با هر تخصيص به ميزاني که از ظرفيت آن ها به ماشين مجازي اختصاص داده شده است، از ظرفيت باقي مانده کم مي شود. ظرفيت خادم (CAP) : مقدار ظرفيت کلي يک خادم بر اساس تعداد ميليون دستورالعمل ها در ثانيه ظرفيت باقي مانده خادم (RCAP) : مقدار ظرفيت باقي مانده (استفاده نشده) از خادم بر اساس تعداد ميليون دستورالعمل ها در ثانيه براي استفاده از حداکثر ظرفيت خادم ها و در نتيجه کاهش تعداد خادم ها، ماشين مجازي خادمي را انتخاب مي کند که داراي کمترين ظرفيت لازم براي اجراي آن ماشين مجازي باشد. 3-1-4-3 درخواست ماشين مجازي بلادرنگ در ابرهاي محاسباتي کارگزاران نقش پيدا کردن منابع ابر و يا ماشين مجازي را براي کارهاي بلادرنگ دارند. پس يک ماشين مجازي به يک کار بلادرنگ که آن کار شامل موارد زير است اختصاص داده مي شود. TAk={(ak,ck,dk,pk,Tk)|k=1,...,n هرکار بايد نهايتا در زمان کامل شود، در کارهايي که دوره اي مي باشند، زمان شروع هر دوره به صورت و زمان پايان آن به صورت که محاسبه مي شود و کارهايي که دوره اي نمي باشند در آن ها برابر صفر در نظر گرفته شده است. ساختار زمان بندي ابري بلادرنگ ساختار زمان بندي ابري بلادرنگ شامل 5 مرحله زير مي باشد: درخواست خدمات به صورت زير ساختي (IaaS) براي ارائه درخواست هاي کارهاي بلادرنگ و مشخصه هاي آن به کارگزار (broker) ايجاد ماشين مجازي بلادرنگ بر اساس کارهاي بلادرنگ (RT-VM) درخواست ماشين مجازي بلادرنگ: کارگزار درخواست ماشين را براي (RT- VM) مي دهد. اين درخواست از تخصيص دهنده ماشين مجازي در ابرهاي محاسباتي انجام مي شود. نگاشت پردازده فيزيکي (تخصيص ماشين مجازي) اجراي برنامه هاي بلادرنگ کار ما در مرحله 3 انجام مي شود، يعني با استفاده از الگوريتم رقابت استعماري نگاشتي از بهترين تخصيص ماشين هاي مجازي به خادمي که کمترين زمان اجرا، با توجه به کمترين ظرفيت لازم براي اجراي آن ماشين مجازي دارد را انتخاب مي کند و بر مي گرداند. شکل 3-3 نشان دهنده چگونگي انجام مراحل فوق مي باشد. شکل 3-3 نمايش چگونگي ساختار زمان بندي کارهاي بلادرنگ در ابرهاي محاسباتي در ادامه نحوه انجام مرحله 3 که همان الگوريتم رقابت استعماري مي باشد را بيان مي کنيم. طبق الگوريتم تطابق اوليه، ماشين هاي مجازي به خادم ها اختصاص داده مي شوند و سپس با استفاده از الگوريتم رقابت استعماري بهترين جايگذاري انتخاب مي شود. 3-1-5 مراحل اجراي الگوريتم رقابت استعماري 3-1-5-1 شکل دهي امپراطوري هاي اوليه جمعيت اوليه متشکل از تعدادي راه حل مي باشد که در الگوريتم رقابت استعماري استاندارد به صورت تصادفي ايجاد مي شود. در اين روش قصد داريم جمعيت اوليه را به صورت هدفمند ايجاد نماييم تا علاوه بر تسريع در يافتن جواب، پاسخ بدست آمده نيز نسبت به حالت معمول، به پاسخ بهينه نزديک تر باشد. روش کار به اين صورت است که براي پيشنهاد يک خادم به هر کار ابتدا مناسب بودن آن به صورت زير بررسي مي شود. کمترين مقدار(هرچه کوچکتر از يک باشد بهتر است) همانطور که بيان گرديد هر کلوني نشان دهنده يک ماشين مجازي و خادم مناسب براي آن مي باشد. بهترين خادم از لحاظ زمان اجراي کار با توجه به کمترين ظرفيت لازم براي آن در نظر گرفته مي شود، در صورتي که خادمي واجد شرايط نباشد، خادم بعدي (دومين بهترين خادم) تست مي شود و اين روند به صورت best fit براي تمامي کلوني ها صورت مي گيرد و سپس ليست خادم هاي کشور بر اساس ظرفيت باقي مانده هر خادم و با توجه به حجم کاري ماشين هاي مجازي، به روز مي شود. در تشکيل جمعيت اوليه، ايجاد هر راه حل نسبت به راه حل قبلي به اين صورت است که براي کلوني ابتدايي، خادمي تست مي شود که نسبت به همان کلوني در کشور قبلي، در اولويت بعدي از ليست خادم هاي مرکز داده قرار دارد، اين شيوه انتخاب خادم هاي کانديد، نسبت به روش تصادفي باعث مي شود تمامي خادم ها شانس قرار گرفتن در راه حل را داشته باشند. بدين ترتيب جمعيتي خواهيم داشت که تمامي راه حل هاي ممکن را دارد. تابع هزينه را براي کشورها محاسبه مي کنيم و 10 تا از کشورهايي که داراي تابع هزينه کمتري هستند را به عنوان استعمارگر انتخاب مي کنيم. ساير کشور ها را به صورت تصادفي بين اين 10 استعمارگر تقسيم مي کنيم. شکل 3-5 چگونگي شکل گيري جمعيت و امپراطوري هاي اوليه را نشان مي دهد. قدرت کل هر امپراطوري را با درنظر گرفتن محاسبه مي کنيم، به صورت مجموع مقدار تابع هزينه استعمارگر آن امپراطوري با 0.1 مجموع مقادير تابع هزينه ي مستعمره هاي آن امپراطوري: TCn= Cost(In )+ 0.1* Mean( cost(Cn)) شكل3-4 چگونگي شکل‌گيري جمعيت و امپراطوري‌هاي اوليه]12[ 3-1-5-2 سياست جذب سياست جذب با اعمال مي شود، به صورتي که کشور مستعمره به اندازه x واحد به سمت استعمارگر خود حرکت مي کند. (x عددي تصادفي با توزيع يکنواخت مي باشد و d فاصله بين استعمارگر و مستعمره است.) 3-1-5-3 انقلاب در اين مرحله مستعمرات با احتمال نرخ انقلاب (Prevolution=0.2) دچار انقلاب مي شوند، به طوري که يک مستعمره به طور کامل يا با حفظ برخي ويژگي ها (به منظور حفظ تنوع و فرار از مينيمم هاي محلي) دچار دگرگوني مي شود. شکل3-5 اعمال سياست انقلاب را نشان مي دهد. شکل 3-5 اعمال سياست انقلاب]11[ با توجه به اعمال سياست جذب و رخ دادن انقلاب ممکن است يک مستعمره در موقعيت بهتري از استعمارگر خود در تابع هزينه برسد، پس تابع هزينه جديد محاسبه مي گردد و اگر مستعمره اي وجود داشت که هزينه اش از هزينه استعمارگر آن کمتر باشد، جاي مستعمره و استعمارگر عوض مي شود و قدرت کل امپراطوري جديد محاسبه مي گردد. شکل 3-6 نشان دهنده حرکت مستعمره به سمت استعمارگر مي باشد، شکل 3-7 تغيير جاي استعمارگر و مستعمره و شکل 3-8 کل امپراطوري بعد از تغيير موقعيت ها را نشان مي دهند. شکل3-6 حرکت يک کشور مستعمره به سمت استعمارگر]11[ شكل 3-7 تغيير جاي استعمارگر و مستعمره]11[شكل 3-8 کل امپراطوري، پس از تغيير موقعيت‌ها]11[ 3-1-5-4 سياست رقابت استعماري در اين مرحله ضعيف ترين مستعمره از ضعيف ترين امپراطوري با احتمال به يکي از 9 امپراطوري ديگر داده مي شود. مقدار احتمال تصاحب مستعمره ي امپراطوري ضعيف توسط امپراطوري i ام است هر چه هزينه کل امپراطوري i ام کمتر باشد احتمال مربوط به آن بيشتراست. شکل 3-9 نشان دهنده اعمال سياست رقابت استعماري مي باشد. اگر تعداد مستعمره هاي يک امپراطوري صفر شود خود امپراطوري تبديل به يک کشور مستعمره مي شود و تعداد امپراطوري ها يکي کاهش ميابد. اين کار آنقدر ادامه پيدا مي کند تا فقط يک امپراطوري باقي بماند. شكل 3-9 شماي کلي رقابت استعماري: امپراطوري‌هاي بزرگتر، با احتمال بيشتري، مستعمرات امپراطوري‌هاي ديگر را تصاحب مي‌کنند]11[ مراجع [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