چکیده الگوریتم زمان بندی کار، که یک مسئله NP-کامل است، نقش کلیدی در سیستم ابرهای محاسباتی ایفا می کند. الگوریتم رقابت استعماری یکی از جدیدترین الگوریتم های بهینه سازی تکاملی است. همانگونه که از نام آن بر می آید، این الگوریتم بر مبنای مدل سازی فرایند اجتماعی- سیاسی پدیده استعمار بنا نهاده شده است.در این تحقیق با استفاده از الگوریتم رقابت استعماری ، الگوریتمی برای زمانبندی کارهای بلادرنگ نرم در محیط ابرهای محاسباتی طراحی می گردد که بتواند برنامه را در کمترین زمان ممکن، پیش از مهلت تعیین شده و با استفاده از کمترین تعداد منابع اجرا نماید، به نحوی که زمان اجرای کار در مقایسه با زمان بندی کارهای بلادرنگ بر اساس الگوریتم ژنتیک و در شرایط مساوی کاهش پیدا نماید. الگوریتم پیشنهادی از سیستم های ناهمگن، که در آن منابع از ناهمگونی محاسباتی و ارتباطات برخوردار هستند استفاده می نماید. زمان بندی نیز از نوع متمرکز و پویا در نظر گرفته شده است، که در این نوع زمان بندی باید به کارهای از قبل پیش بینی شده و محیط سیستم و حالت فعلی سیستم جهت ساخت طرح زمان بندی توجه کرد.پیاده سازی های الگوریتم پیشنهادی برای دو آزمایش 200 خادمی و 400 خادمی انجام گرفته است و کارها از تعداد 16 تا 4096 به سیستم وارد گردیده است، نتایج بدست آمده با نتایج زمان بندی کارهای بلادرنگ بر اساس الگوریتم ژنتیک مقایسه گردیده است و بهینه بودن الگوریتم پیشنهاد شده را بر اساس زمان انجام کار، تعداد کارهای انجام نشده در مهلت تعیین شده و تعداد خادم های مورد استفاده نتیجه می گیریم.در این تحقیق با استفاده از الگوریتم رقابت استعماری در زمان بندی کارهای بلادرنگ در محیط ابرهای محاسباتی، استفاده از منابع بهینه شده است، نسبت بين زمان اجراي مورد انتظار و زمان اجرايي کمتر شده است و مقدار بهينه برازندگي نیز بهتر شده است. واژه های کلیدیابرهای محاسباتی، کارهای بلادرنگ، الگوریتم ژنتیک، الگوریتم رقابت استعماریفهرست مطالبعنوان صفحهفصل اول- کلیات تحقیق 11-1-مقدمه.. 21-1-1 ابرهای محاسباتی.. 21-1-2 الگوریتم رقابت استعماری.. 31-1-3 زمان بندی کارها.. 31-2 اهمیت موضوع تحقیق.. 51-3 تعریف مسئله.. 61-4 اهداف تحقیق.. 61-5 محدوده تحقیق.. 61-6 ساختار کلی پایان نامه.. 6فصل دوم- ادبیات و پیشینه ی تحقیق 72-1مقدمه.. 82-2ابرهای محاسباتی.. 82-2-1 تعریف.. 92-2-2تاریخچه.. 92-2-3معماری ابرهای محاسباتی.. 102-2-4مدل های پیاده سازی ابرهای محاسباتی.. 112-2-5 مجازی سازی.. 122-2-6مزایای ابرهای محاسباتی.. 122-2-7چالش های ابرهای محاسباتی.. 132-3زمان بندی کارهای مستقل.. 142-3-1تعریف.. 152-3-2الگوریتم هایزمان بندی در ابرهای محاسباتی.. 162-3-2-1 مروری بر الگوریتم های زمان بندی حداکثر تلاش.. 202-3-2-2الگوریتم زمان بندی آگاه از منبع.. 202-3-2-3 قیمت گذاری بر اساس فعالیت بهبود یافته (ABC).. 212-3-2-4بهینه سازی ازدحام ذرات (PSO).. 212-3-2-5 الگوریتم توافق زمان-هزینه (CTC).. 212-3-2-6 چندین گردش کاری با چندین محدودیت QOS (MQMW).. 222-3-2-7 الگوریتم زودترین زمان پایان ناهمگن (HEFT).. 222-3-3 الگوریتم های فوق ابتکاری.. 222-4 زمان بندی بلادرنگ.. 232-4-1 برخی از الگوریتم های زمان بندی بلادرنگ.. 242-4-1-1الگوریتم نرخ یکنواخت.. 242-4-1-2 الگوریتم ابتدا زودترین مهلت(EDF).. 242-4-1-3 الگوریتم کمترین لختی.. 242-4-1-4 زمان بندی دو سطحی.. 252-5الگوریتم رقابت استعماری.. 252-5-1 مراحل الگوريتم رقابت استعماری.. 252-5-1-1 شکل دهي امپراطوري‌هاي اوليه.. 272-5-1-2 مدل‌سازي سياست جذب: حرکت مستعمره‌ها به سمت امپرياليست.. 292-5-1-3 جابجايي موقعيت مستعمره و امپرياليست.. 312-5-1-4قدرت کل يک امپراطوري.. 322-5-1-5سیاست رقابت استعماري.. 332-5-1-6 سقوط امپراطوري‌هاي ضعيف.. 352-5-1-7 همگرايي.. 362-5-2 مزاياي الگوريتم رقابت استعماری.. 382-6تحقیقات انجام شده در زمان بندی ابرهای محاسباتی.. 402-7 جمع بندی و نتیجه گیری.. 42فصل سوم- روش پیشنهادی 433-1 مقدمه.. 443-1-1 بیان مساله.. 443-1-2 پارامترهای زمان بندی.. 443-1-2-1 مدل زمان بندی.. 453-1-2-2 تطابق اولیه.. 453-1-3 تابع هدف.. 473-1-4 نحوه انجام عمل زمان بندی.. 473-1-4-1 مدل ماشین مجازی بلادرنگ نرم.. 473-1-4-2 مدل خادم.. 483-1-4-3 درخواست ماشین مجازی بلادرنگ.. 483-1-4-4 ساختار زمان بندی ابری بلادرنگ.. 483-1-5 مراحل اجراي الگوريتم رقابت استعماری.. 503-1-5-1 شکل دهی امپراطوری های اولیه.. 503-1-5-2 سیاست جذب.. 513-1-5-3 انقلاب.. 513-1-5-4 سیاست رقابت استعماری.. 52فصل چهارم- شبيه‌سازي و ارزيابي روش‌هاي پيشنهادي 544-1 مقدمه.. 554-2 شبیه ساز.. 554-2-1 مزایای کلود سیم.. 554-2-2 مدل سازی در کلود سیم.. 554-2-2-1 مدل سازی ابر.. 564-2-2-2 مدل کردن تخصیص ماشین های مجازی.. 564-2-2-3 مدل کردن بارهای کاری پویا.. 564-2-3 جمع بندی شبیه ساز.. 564-3 ارزیابی.. 584-2-1 آزمایش 200 خادمی.. 594-2-2 آزمایش 400 خادمی.. 624-3 نتیجه گیری.. 65فصل پنجم- جمع بندی و پيشنهادات 675-1 جمع بندی.. 685-1-1 خلاصه کار انجام شده.. 685-1-2 مزایا و معایب روش پیشنهادی.. 695-1-2-1 مزایای روش پیشنهادی.. 695-1-2-2 معایب روش پیشنهادی.. 695-3 نو آوری.. 695-4 پیشنهادات.. 70فصل ششم- ضمیمه 716-1 مقدمه.. 726-2 شبیه سازی با استفاده از الگوریتم ژنتیک.. 726-2-1 کد گذاری.. 726-2-2 جمعیت اولیه.. 736-2-3 تابع برازندگی (محاسبه هزینه).. 736-2-4 عملگر انتخاب.. 736-2-5 عملگر تقاطع.. 736-2-6 الگوریتم جهش.. 746-2-7 الگوریتم خاتمه.. 746-3 نتیجه گیری.. 75مراجع 76Abstract 79 فهرست شکل هاعنوان صفحهشکل2-1معماری ابر محاسباتی]8[. 10شكل2-2 فلوچارت الگوريتم رقابت استعماری]11[. 26شكل2-3 اجزاي اجتماعي سياسي تشکيل دهنده يک کشور]11[. 27شكل2-4 چگونگي شکل‌گيري امپراطوري‌هاي اوليه]12[. 29شكل2-5شماي کلي حرکت مستعمرات به سمت امپرياليست]12[. 30شكل2-6حرکت واقعي مستعمرات به سمت امپرياليست]12[. 30شكل 2-7تغيير جاي استعمارگر و مستعمره]11[. 32شكل 2-8کل امپراطوري، پس از تغيير موقعيت‌ها]11[. 32شكل 2-9 شماي کلي رقابت استعماري: امپراطوري‌هاي بزرگتر، با احتمال بيشتري، مستعمرات امپراطوري‌هاي ديگر را تصاحب مي‌کنند]11[. 33شکل 2-10 سقوط امپراطوري ضعيف ]11[. 36شکل2-11 شبه کد مربوط به الگوریتم رقابت استعماری]11[. 37شکل 2-12 شماي کل الگوريتم رقابت استعماری به صورت گرافيکي]11[ 38شکل3-1 نمونه کشور به کار گرفته در الگوریتم پیشنهادی.. 45شکل3-2 فلوچارت حل مساله.. 46شکل 3-3 نمایش چگونگی ساختار زمان بندی کارهای بلادرنگ در ابرهای محاسباتی 49شكل3-4 چگونگي شکل‌گيري جمعیت و امپراطوري‌هاي اوليه.. 51شکل 3-5 اعمال سیاست انقلاب.. 52شکل3-6 حرکت یک کشور مستعمره به سمت استعمارگر.. 52شكل 3-7 تغيير جاي استعمارگر و مستعمره.. 52شكل 3-8 کل امپراطوري، پس از تغيير موقعيت‌ها.. 52شكل 3-9 شماي کلي رقابت استعماري: امپراطوري‌هاي بزرگتر، با احتمال بيشتري، مستعمرات امپراطوري‌هاي ديگر را تصاحب مي‌کنند.. 53شکل 4-1 نمودار زمان انجام کار با 200 خادم.. 61شکل 4-2 نمودار کارهای انجام نشده در مهلت مشخص با 200 خادم 61شکل 4-3 نمودار تعداد خادم های مورد استفاده در هر مرحله با 200 خادم 62شکل 4-4 نمودار زمان انجام کار با 400 خادم.. 64شکل4-5 نمودار کارهای انجام نشده در مهلت مشخص با 400 خادم 64شکل 4-6 نمودار تعداد خادم های مورد استفاده در هر مرحله با 400 خادم 65 فهرست جدول هاعنوان صفحهجدول 4-2 مشخصات و تنظيمات خادم هاي مورد نظر.. 59جدول 4-3 نتایج بدست آمده با 200 خادم(زمان انجام کار، تعداد کارهای انجام نشده در مهلت مشخص و تعداد خادم های مورد استفاده).. 60جدول 4-4 نتایج بدست آمده با 400 خادم(زمان انجام کار، تعداد کارهای انجام نشده در مهلت مشخص و تعداد خادم های مورد استفاده).. 63 فصل اول 1-1-مقدمهدر اين فصل ابتدا خلاصه اي از ابرهاي محاسباتي، الگوريتم رقابت استعماري و زمان بندي کارها بيان خواهد شد و سپس به اهميت موضوع تحقيق، تعريف مساله، اهداف تحقيق، محدوده تحقيق و ساختار کلي پايان نامه پرداخته خواهد شد.ابرهاي محاسباتي[1] جديد ترين نسل سيستم هاي توزيع شده[2] هستند که امروزه نام آن در صنعت فناوري ارتباطات و اطلاعات زياد شنيده مي شود و مورد استقبال جامعه علمي و تجاري قرار گرفته است. ابرهاي محاسباتي شکل تکامل يافته تر سيستم هاي مشبک عمومي هستند که به معناي واقعي ايده ارائه خدمات فناوري اطلاعات به صورت يک خدمت عمومي برمبناي پرداخت به اندازه استفاده را اجرايي کردند. شايد يکي از مهمترين عوامل ظهور و موفقيت ابرها، پيشرفت هاي سخت افزاري و نرم افزاري درمجازي سازي است. با استفاده از مجازي سازي مي توان چندين ماشين مجازي مستقل (محيط مهمان) را به طور همزمان بر روي يک منبع سخت افزاري (محيط ميزبان) ايجاد کرد. ماشين مجازي، يک پياده سازي نرم افزاري از يک کامپيوتر واقعي است که رفتار آن را تقليد مي کند، بنابراين مي توان با نصب يک سيستم عامل (مهمان) بر روي ماشين مجازي، نرم افزارهاي کاربردي مورد نظر خود را بر روي آن اجرا کرد. همچنين عرضه کنندگان خدمات مي توانند برنامه هايي را که بر روي ماشين مجازي اجرا مي کردند، و يا حتي خود ماشين مجازي را به عنوان يک خدمت در اختيار کاربران قرار دهند. استفاده از ماشين هاي مجازي سه مزيت عمده براي عرضه کنندگان خدمات دارد:(1) به آنها اجازه مي دهد که زيرساخت سخت افزاري خود را براساس نيازهاي کاربر تقسيم بندي و سفارشي سازي نمايند. به عنوان مثال مي توانند بر روي يک سخت افزار قدرتمند، به طور همزمان چندين ماشين مجازي با سيستم هاي عامل مختلف را براي کاربران متفاوت ايجاد نمايند.(2) محيط اجرايي هر برنامه بر روي يک ماشين مجازي مي باشد. بنابراين بروز خطا در هريک از برنامه ها و يا ماشين مجازي، تأثير بر روي ساير برنامه هاي در حال اجرا نخواهد داشت.(3) با استفاده از روش هايي همچون مهاجرت زنده[3]، در صورت بروز هرگونه مشکل سخت افزاري و يا نرم افزاري، کل ماشين مجازي مي تواند به سخت افزار ديگري منتقل شده و کار خود را ادامه دهد که باعث بالا رفتن قابليت اطمينان سيستم مي گردد. معمولا عرضه کنندگان بزرگ داراي مراکز داده بسيار بزرگ در نقاط مختلف جهان هستند که حتي در صورت بروز مشکل در کل يک منطقه، مي توانند به کار خود ادامه دهند.الگوريتم رقابت استعماري[4] يکي از جديدترين الگوريتم هاي بهينه سازي تکاملي است. همانگونه که از نام آن بر مي آيد، اين الگوريتم بر مبناي مدل سازي فرايند اجتماعي- سياسي پديده ي استعمار بنا نهاده شده است. اين الگوريتم همانند ساير روش هاي بهينه سازي تکاملي، کار خود را با تعدادي جمعيت اوليه آغاز مي نمايد. در اين الگوريتم، هر عنصر جمعيت، متناظر با کروموزوم در الگوريتم ژنتيک[5] و ذره در الگوريتم بهينه سازي ذرات[6] ، کشور ناميده مي شود.کشور ها به دو دسته مستعمره و استعمارگر تقسيم مي شوند. هر استعمارگر، بسته به قدرت خود، تعدادي از کشورهاي مستعمره را به سلطه خود درآورده و آن ها را کنترل مي کند. سياست همگون سازي و رقابت استعماري، هسته اصلي اين الگوريتم را تشکيل مي دهند. در سياست همگون سازي، مستعمرات را با در نظر گرفتن ضرايبي به سمت استعمارگر آن حرکت مي دهيم.اگر در حين سياست همگون سازي، يک مستعمره نسبت به استعمارگر به موقعيت بهتري برسد، جاي آن دو با يکديگر عوض خواهد شد. براي محاسبه قدرت کل يک امپراطوري نيز، مجموع قدرت کشور استعمارگر به اضافه درصدي از قدرت مستعمرات آن، در نظر گرفته مي شود. بخش مهم ديگر اين الگوريتم، رقابت استعماري مي باشد. در طي اين فرايند، امپراطوري هاي ضعيف، به تدريج قدرت خود را از دست داده و به مرور زمان، به حالتي برسد که تنها يک امپراطوري در مجموعه جواب ها باقي بماند، اين حالت زماني است که الگوريتم رقابت استعماري با رسيدن به نقطه بهينه تابع هدف، متوقف مي شود.