صفحه محصول - زمانبندی کارهای فوری در رایانش ابری با الگوریتم 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[ انجام مي گردد . فصل دوم ادبيات و پيشينه ي تحقيق 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 جمع بندي و نتيجه گيري همان طور که بيان شد در بيشتر کارهاي انجام شده براي زمان بندي کارها در ابرهاي محاسباتي تنها به زمان اجراي کارها توجه شده بود و به مهلت تعيين شده براي دريافت پاسخ، زمان ارسال کارها و کاهش تعداد منابع مصرفي (استفاده از حداکثر ظرفيت منبع) توجه چنداني نشده است، همچنين در تعداد محدودي از موارد ارائه شده، زمان بندي براي کارهاي بلادرنگ انجام گرفته است. در اين تحقيق قصد داريم با استفاده از الگوريتم رقابت استعماري، که يک الگوريتم فوق ابتکاري است، براي دست يابي به پاسخ بهينه جهت نگاشت کارها به منابع موجود در محيط ابرهاي محاسباتي، الگوريتمي براي زمان بندي کارهاي بلادرنگ نرم در محيط ابرهاي محاسباتي طراحي شود که بتواند برنامه را در کمترين زمان ممکن، پيش از مهلت تعيين شده و با استفاده از کمترين تعداد منابع اجرا نمايد، با اين هدف که از توانايي هاي الگوريتم رقابت استعماري، با توجه به سرعت مناسب آن در يافتن پاسخ بهينه، استفاده شود. فصل سوم روش پيشنهادي 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[ فصل چهارم شبيه‌سازي و ارزيابي روش‌هاي پيشنهادي 4-1 مقدمه در اين فصل ابتدا شبيه ساز معرفي مي شود، سپس به جزئيات شبيه سازي روش پيشنهادي معرفي شده در فصل سوم پرداخته خواهد شد و از طريق رسم نمودار روش مذکر مورد ارزيابي قرار خواهد گرفت. 4-2 شبيه ساز شبيه ساز مورد استفاده، کلود سيم مي باشد، شبيه ساز کلود سيم، مدل سازي رفتار مولفه هاي سيستم مانند مراکز داده، ماشين هاي مجازي و سياست هاي آماده سازي منابع را پشيباني مي کند. مولفه هايي مانند مرکز داده، کارگزار و سرويس اطلاعات ابر را به عنوان موجوديت در کلود سيم تعريف مي کنيم. در حال حاضر اين شبيه ساز محيط هاي ابرهاي محاسباتي واحد و يا متحد شده (مجموعه اي از چند محيط ابري که توسط ارائه دهندگان مختلف سرويس ابر توليد مي شود). همچنين واسط هايي را براي پياده سازي سياست ها و تکنيک هاي آماده سازي جهت تخصيص ماشين هاي مجازي تحت آزمايش هاي پيچيده در اختيار قرار مي دهد. محققان بسياري در زمينه آماده سازي منابع ابر و مديريت انرژي کارايي مراکز داده در سازمان هايي مانند آزمايشگاه HP در آمريکا از شبيه ساز کلود سيم براي انجام کارهاي خود استفاده مي کنند. 4-2-1 مزاياي کلود سيم شبيه ساز کلود سيم قادر است لايه هاي سرويس ابر IaaS، PaaS و SaaS را از يکديگر تفکيک کند و منابع مجازي سازي شده موردنياز ابر را مدل کند. از جمله مزاياي اين شبيه ساز عبارت است از: در نظر گرفتن تاثيرات زمان. شبيه ساز کاملا انعطاف پذير و کاربردي. تست سياست هاي مورد نظر در يک محيط قابل کنترل و قابل تکرار. تنظيم گلوگاه هاي سيستم قبل از انجام استقرار روي ابر واقعي. 4-2-2 مدل سازي در کلود سيم ابتدا مدل سازي ابر، سپس مدل کردن تخصيص ماشين هاي مجازي و در نهايت مدل کرد بارهاي کاري پويا شرح داده مي شود. 4-2-2-1 مدل سازي ابر براي مدل کردن سرويس هاي سطح زيرساخت در شبيه ساز، مي توانيم موجوديت مرکز داده را توسعه دهيم. موجوديت مرکز داده تعداد زيادي از موجوديت ها مانند ميزبان را مديريت مي کند. اين ميزبان ها طبق سياست تخصيص ماشين هاي مجازي که توسط ارائه دهنده سرويس ابر تعريف مي شود، به ماشين هاي مجازي تخصيص داده مي شوند. در اين شبيه ساز سياست ماشين مجازي بيانگر سياست هاي کنترل ماشين مجازي در رابطه با دوره زندگي آن مانند فراهم کردن ميزبان براي ماشين مجازي، ايجاد و از بين بردن آن و مهاجرت اين ماشين هاي مجازي مي باشد. به طور مشابه يک يا چند سرويس کاربردي مي تواند به اين ماشين مجازي واحد تخصيص يابد، اين همان آماده سازي کاربردها در زمينه ابرهاي محاسباتي است. در اين شبيه ساز هر موجوديت نمونه اي از يک مولفه است. يک مولفه در کلود سيم مي تواند يک کلاس(انتزاعي يا کامل)، يا مجموعه اي از کلاس ها باشد که يک مدل (مرکز داده يا ميزبان) را در کلود سيم نشان مي دهد. 4-2-2-2 مدل کردن تخصيص ماشين هاي مجازي به منظور شبيه سازي سياست هاي آماده سازي مختلف تحت سطوح مختلف کارايي که از يکديگر مجزا باشند، شبيه ساز کلود سيم آماده سازي ماشين هاي مجازي را در دو سطح پشتيباني مي کند: ابتدا سطح ميزبان و سپس در سطح ماشين مجازي. در سطح ماشين ميزبان تعيين مي کنيم که چه مقدار از توان پردازشي کل هر هسته به هر ماشين مجازي اختصاص خواهد يافت. در سطح ماشين مجازي، هر ماشين مجازي يک مقدار ثابتي از توان پردازشي موجود را به سرويس هاي کاربردي منحصر به فرد (واحد هاي وظيفه) که بر روي آن قرار گرفته است، تخصيص مي دهد. در اين شبيه ساز، هر واحد وظيفه را به عنوان يک انتزاع جزئي تر از يک سرويس کاربردي که در ماشين مجازي قرار گرفته است، در نظر مي گيريم. 4-2-2-3 مدل کردن بارهاي کاري پويا يکي از نيازهاي مهم در هر محيط شبيه سازي اين است که از مدل کردن الگوهاي بار کاري پويا پشتيباني کند. اين کار بهره وري پردازنده ها را در بازه هاي زماني مختلف تغيير مي دهد تا بتواند بار کاري حالت واقعي (بارکاري اي که در دنياي واقعي وجود دارد) را مدل سازي کند. 4-2-3 جمع بندي شبيه ساز کلود سيم نرم افزاري کلي است که مي توان از آن براي مدل کردن محيط ابرهاي محاسباتي و تست کارايي سرويس هاي کاربردي استفاده کرد. اين شبيه ساز مبتني بر زبان جاوا است و يک شبيه ساز مبتني بر رويداد مي باشد. يعني موجوديت هايي که در آن تعريف مي شود، از طريق فرستادن رويداد با يکديگر ارتباط برقرار مي کنند. ارائه دهندگان سرويس ابر براي اين که سرويسي را در سطح عالي به کاربران ارائه دهند با مسائلي از جمله تضمين کيفيت سرويس که مي تواند زمان پاسخ کمتر و يا گذردهي بالاتر باشد، بهره وري کارايي منابع، بارهاي کاري پويا مانند مدل کردن کاربردهاي وبي چون سرويس دهنده-سرويس گيرنده و نقض سطح توافق ارائه سرويس مواجه بوده اند. در اين ميان ، مشکل تست کردن از جمله مهمترين مسائل است زيرا اين امکان وجود ندارد که آزمايش ها را در يک محيط قابل مقياس، قابل تکرار و قابل اعتماد با استفاده از يک محيط ابر واقعي انجام داد. پس کليد حل اين مشکلات استفاده از ابزار شبيه سازي است. در اين شبيه ساز نه تنها سربار حافظه بسيار ناچيز است بلکه دقت شبيه سازي بسيار بالا مي باشد و براي تست الگوريتم ها و ارزيابي آن ها، ابزار بسيار مناسبي است. 4-3 ارزيابي براي اينکه بتوانيم نتايج بدست آمده از زمان بندي کارها بر اساس الگوريتم رقابت استعماري را با نتايج زمان بندي کارها بر اساس الگوريتم ژنتيک مقايسه کنيم، زمان بندي کارها بر اساس الگوريتم ژنتيک نيز در همين محيط شبيه سازي شده است و در قسمت ضميمه به تفسير آن مي پردازيم. در اين شبيه سازي، در الگويتم رقابت استعماري با در نظر گرفتن نرخ انقلاب (Prevolution=0.2)، ، ، و الگوريتم در نسل 72 ام به پايان رسيد و نتايج به صورت زير مي باشد: مقدار بهينه برازندگي در نسل 100 ام به 2.3 رسيده است. استفاده از منابع به شدت توسعه يافته است. نسبت بين زمان اجراي مورد انتظار و زمان اجرايي که واکنش نشان داده شد 12.4 است. در الگوريتم ژنتيک با در نظر گرفتن و و و الگوريتم درنسل 89 ام به پايان رسيد و نتايج به صورت زير مي باشد: مقدار بهينه برازندگي در نسل 100 ام به 3.2 رسيده است. استفاده از منابع توسعه يافته است. نسبت بين زمان اجراي مورد انتظار و زمان اجرايي که واکنش نشان داده شد 16.5 است. حال با توجه به اينکه زمان بندي کارها بر اساس الگوريتم رقابت استعماري نسبت به زمان بندي کارها بر اساس الگوريتم ژنتيک بهينه مي باشد، با دو آزمايش 200 خادمي و 400 خادمي در ادامه، به تفسير دقيق بهينه شدن زمان انجام کارها، تعداد کارهاي انجام نشده در مهلت مشخص و تعداد خادم هاي مورد استفاده در هر مرحله با استفاده از نمودار مي پردازيم. سيستم هدف يک محيط IaaS است. ابتدا با فرض 200 خادم تعدادي کار به سيستم وارد کرده، بار ديگر 400 خادم در نظر گرفته خواهد شد و همان تعداد کار به آن وارد خواهيم کرد، نيمي از خادم ها در هريک از دو مرحله فوق شامل خادم هاي HP ProLiant ML110 G4 و نيم ديگر از نوع خادم هاي HP ProLiant ML110 G5 است. در جدول 4-2 ويژگي هاي اين خادم ها از جمله نوع پردازنده، فرکانس، تعداد هسته، حافظه و پهناي باند نمايش داده شده است. جدول 4-2 مشخصات و تنظيمات خادم هاي مورد نظر خادمنوع پردازندهفرکانستعداد هستهحافظهپهناي باند شبکهHP ProLiant ML110 G4Intel Xeon 30401860 MIPS24GB1GB/sHP ProLiant ML110 G5Intel Xeon 30752660 MIPS24GB1GB/s .در اين پياده سازي براي داشتن مرکز داده ناهمگون براي هر خادم، مقدار کارايي پردازنده به ميزان يکي از مقادير 1860 و 2660 در واحد MIPS در نظر گرفته شده است. مدل هاي خادم HP ProLiant ML110 G4 و HP ProLiant ML110 G5 مقدار حافظه هر خادم برابر 4 گيگابايت است، براي هر خادم يک گيگابايت حافظه ذخيره سازي و يک گيگابايت بر ثانيه پهناي باند در ارتباط با ديگر خادم ها در نظر گرفته شده است. در هر آزمايش به تعداد کارهاي ورودي در هر مرحله، ماشين مجازي در مرکز داده در نظر گرفته شده و هر کار به يک ماشين مجازي اختصاص داده مي شود، هريک از ماشين هاي مجازي داراي توان پردازشي برابر يکي از مقادير 500، 1000، 2000 و 2500 در واحد MIPS مي باشند. تعداد مورد نياز از ماشين هاي مجازي به صورت تصادفي از بين نمونه هاي فوق ايجاد و بر اساس الگوريتم پيشنهادي بر روي خادم هاي موجود جايگذاري انجام مي شود. 4-2-1 آزمايش 200 خادمي تعداد 200 خادم (که 100 تاي آن ها از نوع HP ProLiant ML110 G4 و 100 تاي آن ها از نوع HP ProLiant ML110 G5 مي باشد) در نظر گرفته مي شود و سپس کارها را به سيستم وارد مي کنيم. (کارها تعداد 16، 32، 64، 128، 256، 512، 1024،2048،4096 مي باشند.) جدول 4-3 زمان انجام کار، تعداد کارهاي انجام نشده در مهلت مشخص و تعداد خادم هاي مورد استفاده در هر مرحله از آزمايش 200خادمي و شکل4-1 نمودار زمان انجام کار و شکل 4-2 نمودار تعداد کارهاي انجام نشده در مهلت مشخص و شکل 4-3 نمودار تعداد خادم هاي مورد استفاده در هر مرحله از آزمايش 200 خادمي را نشان مي دهند. جدول 4-3 نتايج بدست آمده با 200 خادم(زمان انجام کار، تعداد کارهاي انجام نشده در مهلت مشخص و تعداد خادم هاي مورد استفاده) تعداد خادم هاي مورد استفاده در الگوريتم ژنتيکتعداد خادم هاي مورد استفاده در الگوريتم رقابت استعماريتعداد کارهاي انجام نشده در مهلت مشخص با استفاده از الگوريتم ژنتيکتعداد کارهاي انجام نشده درمهلت مشخص با استفاده از الگوريتم رقابت استعماريزمان اجراي الگوريتم ژنتيک (ms)زمان اجراي الگوريتم رقابت استعماري (ms)تعداد کارهاي ورودي166001.9211.843163213002.7452.734326422004.8674.6516412839009.3798.762128200842017.62010.4252562001332031.12225.39151220018553139.101120.7561024200200208540.316512.24820482002002510845.455800.2354096 -1901831193747زمان (ms)زمان (ms)20472402925114تعداد کارهای ورودیتعداد کارهای ورودی شکل 4-1 نمودار زمان انجام کار با 200 خادم -441589975995تعداد کارهای انجام نشده0تعداد کارهای انجام نشده21043902695575تعداد کارهای ورودیتعداد کارهای ورودی شکل 4-2 نمودار کارهاي انجام نشده در مهلت مشخص با 200 خادم -6229351328420تعداد خادم های مورد استفاده0تعداد خادم های مورد استفاده22567902981325تعداد کارهای ورودیتعداد کارهای ورودی شکل 4-3 نمودار تعداد خادم هاي مورد استفاده در هر مرحله با 200 خادم 4-2-2 آزمايش 400 خادمي حال همان آزمايش قبل با 400 خادم انجام شده و نتايج بررسي خواهد شد. تعداد 400 خادم (که 200 تاي آن ها از نوع HP ProLiant ML110 G4 و 200 تاي آن ها از نوع HP ProLiant ML110 G5 مي باشد) در نظر گرفته مي شود و سپس کارها را به سيستم وارد مي کنيم. (کارها تعداد 16، 32، 64، 128، 256، 512، 1024، 2048،4096 مي باشند.) جدول 4-4 زمان انجام کار، تعداد کارهاي انجام نشده و تعداد خادم هاي مورد استفاده در آزمايش 400 خادمي و شکل4-4 نمودار زمان انجام کار و شکل 4-5 نمودار تعداد کارهاي انجام نشده در مهلت مشخص و شکل 4-6 نمودار تعداد خادم هاي مورد استفاده در هر مرحله از آزمايش 400 خادمي را نشان مي دهند. جدول 4-4 نتايج بدست آمده با 400 خادم(زمان انجام کار، تعداد کارهاي انجام نشده در مهلت مشخص و تعداد خادم هاي مورد استفاده) تعداد خادم هاي مورد استفاده در الگوريتم ژنتيکتعداد خادم هاي مورد استفاده در الگوريتم رقابت استعماريتعداد کارهاي انجام نشده در مهلت مشخص با استفاده از الگوريتم ژنتيکتعداد کارهاي انجام نشده در مهلت مشخص با استفاده از الگوريتم رقابت استعماريزمان اجراي الگوريتم ژنتيک (ms)زمان اجراي الگوريتم رقابت استعماري (ms)تعداد کارهاي ورودي166001.9211.843163213002.7452.734326422004.8674.6516412839009.3798.762128256840015.99910.9032564001330019.33014.9815124001852188.86780.239102440027973237.512212.8212048400392156511.889422.1234096 18186402816860تعداد کارهای ورودیتعداد کارهای ورودی-277442980123زمان (ms)زمان (ms) شکل 4-4 نمودار زمان انجام کار با 400 خادم 47625010985500 -520700266700تعداد کارهای انجام نشده0تعداد کارهای انجام نشده 2159635-304800تعداد کارهای ورودیتعداد کارهای ورودیشکل4-5 نمودار کارهاي انجام نشده در مهلت مشخص با 400 خادم -4635501390015تعداد خادم های مورد استفاده0تعداد خادم های مورد استفاده22167853185795تعداد کارهای ورودیتعداد کارهای ورودی شکل 4-6 نمودار تعداد خادم هاي مورد استفاده در هر مرحله با 400 خادم 4-3 نتيجه گيري در اين پياده سازي، در الگويتم رقابت استعماري با در نظر گرفتن نرخ انقلاب (Prevolution=0.2)، ، ، و الگوريتم در نسل 72 ام به پايان رسيد و نتايج به صورت زير مي باشد: مقدار بهينه برازندگي در نسل 100 ام به 2.3 رسيده است. استفاده از منابع به شدت توسعه يافته است. نسبت بين زمان اجراي مورد انتظار و زمان اجرايي که واکنش نشان داده شد 12.4 است. در الگوريتم ژنتيک با در نظر گرفتن و و و الگوريتم درنسل 89 ام به پايان رسيد و نتايج به صورت زير مي باشد: مقدار بهينه برازندگي در نسل 100 ام به 3.2 رسيده است. استفاده از منابع توسعه يافته است. نسبت بين زمان اجراي مورد انتظار و زمان اجرايي که واکنش نشان داده شد 16.5 است. سپس در دو آزمايش 200 خادمي و 400 خادمي که در هر دو مورد نيمي از خادم ها از نوع HP ProLiant ML110 G4 و نيمي ديگر از نوع HP ProLiant ML110 G5 مي باشند زمان انجام کار، تعداد کارهاي انجام نشده در مهلت مشخص و تعداد خادم هاي مورد استفاده در هر مرحله نشان داده شد. با توجه به نتايج حاصل از زمان بندي کارها بر اساس الگوريتم رقابت استعماري و نتايج حاصل از زمان بندي کارها بر اساس الگوريتم ژنتيک که بيان شد، نشان مي دهد که زمان بندي کارها بر اساس الگوريتم رقابت استعماري عملکرد بهتري نسبت به زمان بندي کارها بر اساس الگوريتم ژنتيک دارد. در بيشتر کارهاي انجام شده در بحث زمان بندي کارها در ابرهاي محاسباتي تنها به زمان اجراي کارها توجه شده بود، به مهلت اجرا و تعداد منابع مورد استفاده توجه چنداني نشده بود، اما در الگوريتم پيشنهادي ما به دليل اينکه کارها از نوع بلادرنگ هستند علاوه بر زمان اجراي کارها به مهلت تعيين شده براي دريافت پاسخ و کاهش تعداد خادم هاي مورد استفاده (استفاده از حداکثر ظرفيت يک خادم) نيز توجه زيادي شده است به نحوي که کارها بايد قبل از مهلت تعيين شده انجام شوند و درغير اين صورت، موجب جريمه شدن و باعث کاهش سودمندي مي شود و همچنين از حداکثر ظرفيت خادم ها براي انجام کارها استفاده مي شود. هرچه زمان انجام کار، تعداد کارهاي انجام نشده در مهلت مشخص و تعداد خادم هاي مورد استفاده کمتر شود نشان دهنده بهبود عملکرد الگوريتم زمان بندي است. فصل پنجم جمع بندي و پيشنهادات 5-1 جمع بندي در اين فصل ابتدا به خلاصه کار انجام شده در اين تحقيق سپس مزايا و معايب روش پيشنهادي، نوآوري و پيشنهادات آينده بيان خواهد شد. 5-1-1 خلاصه کار انجام شده محيط ابرهاي محاسباتي از چندين عرضه کننده تشکيل مي گردد که هريک منابعي را در اختيار کاربران قرار مي دهند. در اين تحقيق با استفاده از الگوريتم رقابت استعماري ، الگوريتمي براي زمان بندي کارهاي بلادرنگ نرم در محيط ابرهاي محاسباتي ارائه شد که برنامه را در کمترين زمان ممکن، پيش از مهلت مشخص و با استفاده از کمترين تعداد منابع اجرا نمايد. در اين شبيه سازي، در الگويتم رقابت استعماري با در نظر گرفتن نرخ انقلاب (Prevolution=0.2)، ، ، و الگوريتم در نسل 72 ام به پايان رسيد و نتايج به صورت زير مي باشد: مقدار بهينه برازندگي در نسل 100 ام به 2.3 رسيده است. استفاده از منابع به شدت توسعه يافته است. نسبت بين زمان اجراي مورد انتظار و زمان اجرايي که واکنش نشان داده شد 12.4 است. در الگوريتم ژنتيک با در نظر گرفتن و و و الگوريتم درنسل 89 ام به پايان رسيد و نتايج به صورت زير مي باشد: مقدار بهينه برازندگي در نسل 100 ام به 3.2 رسيده است. استفاده از منابع توسعه يافته است. نسبت بين زمان اجراي مورد انتظار و زمان اجرايي که واکنش نشان داده شد 16.5 است. سيستم هدف يک محيط IaaS است. در دو آزمايش200 خادمي و 400 خادمي زمان انجام کارها، تعداد کارهاي انجام نشده در مهلت مشخص و تعداد خادم هاي مورد استفاده در هر مرحله نشان داده شد و مورد ارزيابي قرار گرفت. نيمي از خادم ها در هريک از دو آزمايش ياد شده شامل خادم هاي HP ProLiant ML110 G4 و نيم ديگر از نوع خادم هاي HP ProLiant ML110 G5 هستند. کارها هم از تعداد 16 شروع شده و تا 4096 ادامه مي يابد. (کارها تعداد 16، 32، 64، 128، 256، 512، 1024،2048،4096 مي باشند.) با توجه به نتايج حاصل از زمان بندي کارها بر اساس الگوريتم رقابت استعماري و نتايج حاصل از زمان بندي کارها بر اساس الگوريتم ژنتيک که بيان شد، نشان مي دهد که زمان بندي کارها بر اساس الگوريتم رقابت استعماري عملکرد بهتري نسبت به زمان بندي کارها بر اساس الگوريتم ژنتيک دارد. در بيشتر کارهاي انجام شده در بحث زمان بندي کارها در ابرهاي محاسباتي تنها به زمان اجراي کارها توجه شده بود، به مهلت تعيين شده براي انجام کار و تعداد خادم هاي مورد استفاده توجه چنداني نشده بود، اما در الگوريتم پيشنهادي ما به دليل اينکه کارها از نوع بلادرنگ نرم هستند علاوه بر زمان اجراي کارها به مهلت مشخص شده براي دريافت پاسخ و کاهش تعداد خادم هاي مورد استفاده (استفاده از حداکثر ظرفيت يک خادم) نيز توجه زيادي شده است به نحوي که کارها بايد قبل از مهلت تعيين شده انجام شوند و درغير اين صورت، موجب جريمه شدن (که باعث کاهش سودمندي مي گردد) و همچنين از حداکثر ظرفيت خادم ها براي انجام کارها استفاده کند. هرچه زمان انجام کار، تعداد کارهاي انجام نشده در مهلت مشخص و تعداد خادم هاي مورد استفاده کمتر شود نشان دهنده بهبود عملکرد الگوريتم زمان بندي است. 5-1-2 مزايا و معايب روش پيشنهادي 5-1-2-1 مزاياي روش پيشنهادي استفاده از منابع بهينه شده است. نسبت بين زمان اجراي مورد انتظار و زمان اجرايي کمتر شده است. مقدار بهينه برازندگي بهتر شده است. 5-1-2-2 معايب روش پيشنهادي عدم توانايي بهره برداري کامل از زمان و منابع در محاسبات ابري. 5-3 نو آوري در مدل هاي قبلي زمان بندي از جمله زمان بندي کارها بر اساس الگوريتم ژنتيک در محيط ابرهاي محاسباتي به زمان پاسخگويي مورد نظر کاربر و استفاده از بيشترين ظرفيت خادم ها توجه چنداني نشده بود و فقط زمان بندي در محيط ابرهاي محاسباتي انجام مي گرفت و سپس نتيجه ارسال مي شد، اما در روش پيشنهادي در اين تحقيق براي دستيابي به پاسخ بهينه در زمان بندي کارها، از الگوريتم رقابت استعماري جهت نگاشت کارها به منابع موجود در ابرهاي محاسباتي استفاده شده است، که در آن به مهلت تعيين شده براي انجام کار و استفاده از کمترين تعداد خادم (استفاده از بيشترين ظرفيت هر خادم) توجه شده است و همچنين علاوه بر اين نکته زمان اجراي کارها همانطور که در فصل چهار مشاهده کرديد بهينه شده است. هدف از اين الگوريتم استفاده از توانايي هاي الگوريتم رقابت استعماري با توجه به سرعت مناسب آن در يافتن پاسخ بهينه است. 5-4 پيشنهادات در آينده مي توان با ايجاد تغييراتي ، توجه بيشتري به کاهش فضاي راه حل پرداخت ، زيرا ابرهاي محاسباتي براي يکپارچه سازي منابع بيشمار و کارها از اهميت ويژه اي برخوردار است، همينطور مي توان با تغيير شاخص هاي الگوريتم و ترکيب الگوريتم هاي مختلف بهتر شدن زمان بندي کارها در ابرهاي محاسباتي را نتيجه گرفت و همچنين بهره برداري بيشتر از زمان و منابع را حاصل نمود. فصل ششم ضميمه 6-1 مقدمه در اين فصل به چگونگي انجام شبيه سازي زمان بندي کارهاي بلادرنگ با استفاده از الگوريتم ژنتيک در محيط ابرهاي محاسباتي پرداخته مي شود. 6-2 شبيه سازي با استفاده از الگوريتم ژنتيک شبيه سازي که بر اساس الگوريتم ژنتيک مي باشد به صورت زير انجام پذيرفت: کارها، همانطور که در فصل سوم بيان شد به ماشين هاي مجازي اختصاص داده مي شوند. مدل ماشين مجازي بلادرنگ، درخواست ماشين مجازي بلادرنگ و ساختار زمان بندي ابري بلادرنگ همانند آنچه در فصل سوم قسمت 3-1-4 بيان شد مي باشد فقط با اين تفاوت که در مرحله سوم ساختار زمان بندي ابري بلادرنگ از الگوريتم ژنتيک استفاده مي شود، در زير چگونگي کار الگوريتم ژنتيک در آن را بيان مي کنيم. الگوريتم ژنتيک يک تکنولوژي جديد است. الگوريتم هاي ژنتيکي و تکنولوژي هاي ژنتيکي در اصل يک فناوري بهينه سازي جستجو هستد، که از يک جمعيت اوليه شروع مي شوند، با استفاده از اصل بقا و توليد مثل و پيوند زني و دگرگوني و به طور مداوم اجرا شدن و تکرار، راه حل بهينه را بدست مي آورند. راه حلي که براي اين مساله در نظر گرفته شده است به صورت زير مي باشد: 6-2-1 کد گذاري به قسمتي از الگوريتم ژنتيک که براي کد کردن راه حل هاي مساله مورد استفاده قرار مي گيرد گفته مي شود. به هرکدام از اين راه حل ها يک کروموزوم مي گويند. مجموعه کروموزوم ها جمعيت اوليه را تشکيل مي دهند. در هر راه حل براي هر ماشين مجازي خادمي مناسب از ميان خادم ها در نظر گرفته مي شود. هر کروموزوم داراي N ژن مي باشد که طول کروموزوم را تشکيل مي دهند، تعداد ژن ها برابر تعداد ماشين هاي مجازي (کارها) مي باشد. مرکز داده ابر وظيفه جمع آوري و نگهداري اطلاعات مربوط به خادم ها را بر عهده دارد. در اين روش براي ايجاد هر کروموزوم از درون ليست مرتب شده خادم ها، خادمي براي هر ماشين مجازي در نظر گرفته مي شود، اين ليست در انجام هر کدام از عمليات نظير ايجاد جمعيت اوليه، جهش و انتخاب به روز رساني مي شود. 6-2-2 جمعيت اوليه همانطور که بيان گرديد هر ژن نشان دهنده يک ماشين مجازي و خادم مناسب براي آن مي باشد. در تشکيل جمعيت اوليه، براي هر ماشين مجازي يک خادم در دسترس را انتخاب کرده، و به عنوان يک ژن در کروموزوم، به صورت تصادفي قرار مي دهيم. مجموعه اي از اين کروموزوم ها جمعيت اوليه را تشکيل مي دهند. 6-2-3 تابع برازندگي (محاسبه هزينه) تابع هدف به صورت فرمول شماره 6-1 مي باشد: فرمول6-1 در اين فرمول زمان پايان کارk ام، تابع جريمه برابر ، مهلت اجراي کارiام و برابر زمان واقعي پايان کار iام مي باشد. در تابع جريمه و هزينه هاي تاخير درنظر گرفته شده اند. 6-2-4 عملگر انتخاب تعداد معيني را به طور تصادفي از بين افراد جمعيت انتخاب مي کنيم و سپس بر اساس مقايسه نسبت مقدار برازندگي، آن هايي که داراي بيشترين مقدار برازندگي هستند براي نسل بعدي انتخاب مي شوند. 6-2-5 عملگر تقاطع به دليل اينکه هر خادم مي تواند بيش از يک کار را انجام دهد، لذا ترتيب قرارگيري و نگاشت ماشين هاي مجازي در خادم ها مي تواند در ميزان دريافت پاسخ در مدت زمان کوتاه تر و استفاده بهتر از ظرفيت خادم ها موثر باشد. توسط عمليات تقاطع مي توان شانس جابجايي ژن ها را براي دستيابي به راه حل بهتر افزايش داد. ابتدا دو کروموزوم انتخاب مي کنيم و با فرض اينکه نرخ تقاطع براي کروموزوم هايي که داراي مقدار برازندگي بالايي هستند برابر و براي آنهايي که داراي مقدار برازندگي کمتري هستند مي باشد، نرخ تقاطع را با استفاده از فرمول6-2 بدست مي آوريم (بيشترين نرخ تقاطع برابر 0.4 و کمترين نرخ تقاطع برابر 0.2 مي باشد) و يک رقم تصادفي بين صفر و يک ايجاد کرده c=Random(0,1) ، اگر نرخ تقاطع از رقم ايجاد شده کمتر باشد، را که شامل نقاط متفاوت ژن مي باشد، توليد مي کنيم، اگر D خالي باشد، کروموزوم ها به طور مستقيم و بدون هيچ تغييري به نسل بعد مي روند، در غير اين صورت به طور تصادفي عمل تقاطع روي دو نقطه ژن متفاوت انجام مي شود و کروموزوم هاي با بيشترين مقدار برازندگي در نسل بعدي براي کاهش تنزل نگه داشته مي شوند. فرمول6-2 6-2-6 الگوريتم جهش ابتدا نرخ جهش را براي هر کروموزوم بر اساس فرمول6-3 محاسبه مي کنيم. و سپس يک کروموزوم به صورت تصادفي با استفاده از الگوريتم انتخاب که ذکر شد انتخاب شده و به ازاي هر ژن از کروموزوم يک عدد تصادفي توليد مي گردد، اگر اين مقدار تصادفي از نرخ جهش کمتر باشد، در آن ژن عمل جهش با انتخاب يک خادم در دسترس، به صورت تصادفي و جايگذيني در آن ژن انجام مي گيرد. اين عمل باعث مي شود در نقطه کمينه محلي به دام نيفتد. فرمول6-3 با هر تغيير ژن در کروموزوم در عمليات جهش و تقاطع، ليست خادم ها به روز رساني مي شود و همچنين مقدار تابع برازندگي براي کروموزوم جديد محاسبه مي گردد. 6-2-7 الگوريتم خاتمه اجراي الگوريتم تا زماني ادامه ميابد که يکي از شرايط خاتمه اتفاق بيفتد.اين شرايط عبارتند از: تعداد توليد نسل ها به حد ماکزيمم برسد. در صورتي که تابع برازندگي بهترين راه حل بعد از تعدادي تکرار خاص، تغيير زيادي نداشته باشد. همگرا شدن تابع برازندگي کروموزوم ها در پايان الگوريتم ژنتيک کروموزوم هايي که 20 نسل متوالي داراي بالاترين برازندگي مي باشند ذخيره مي شود، زماني که شرط خاتمه برآورده شود بر اساس مقدار برازندگي اندازه کروموزوم ها مرتب شده اند و نتايج خارج مي شوند. 6-3 نتيجه گيري با در نظر گرفتن و و و الگوريتم درنسل 89 ام به پايان رسيد و نتايج زير حاصل شد: مقدار بهينه برازندگي در نسل 100 ام به 3.2 رسيده است. استفاده از منابع توسعه يافته است. نسبت بين زمان اجراي مورد انتظار و زمان اجرايي که واکنش نشان داده شد 16.5 است. مراجع [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