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

فصل دوم پایان نامه زمانبندی در رایانش ابری با عنوان زمان بندی کارهای بلادرنگ در محیط ابرهای محاسباتی با استفاده از الگوریتم رقابت استعماری  می باشد. در واقع در این نوشتار به مبانی نظری و پیشینه تحقیق زمان بندی کارهای بلادرنگ در رایانش ابری می پردازیم.سیستم های توزیع شده  و تکنیک های پردازش موازی، از جمله راه حل های استفاده ی بهتر و سریع تر از دنیای حجیم و پیچیده اطلاعات عصر حاضر می باشد. امروزه صد ها رایانه و ابر رایانه با ظرفیت ها و معماری های گوناگون در سراسر دنیا وجود دارند که در کاربردهای گوناگون علمی، نظامی، تجاری و غیره از آنها استفاده می شود، و اکثرا لزوم به اشتراک گذاری اطلاعات در میان آنها امری مقتضی است.

 یک سیستم توزیع شده مجموعه ای است از کامپیوتر های مستقل که در نظر کاربران به صورت یک سیستم منسجم واحد به نظر می آید و می بایست دارای دو ویژگی اصلی باشد: خودمختاری و شفافیت توزیع. خودمختاری به معنی مدیریت جداگانه هر گره  در عین تعامل آن با سایر گره ها می باشد، به نحوی که سیاست های مدیریت یا اختلال در هر گره برروی سایر گره ها تاثیر نگذارد. شفافیت توزیع، تصور تک واحد بودن سیستم را برای کاربران بوجود می آورد که خود شامل شفافیت در مباحثی نظیر دسترسی، مکان، مهاجرت، تغییر مکان منبع، تکرار، همروندی و خطا می باشد]۸[.

ابرهای محاسباتی از مجموعه رایانه های عظیم متصل به اینترنت تشکیل شده است و راهکاری انعطاف پذیر برای رفع نیاز بسیاری از برنامه های کاربردی است]۲۳[.یکی از چالش برانگیزترین مسائل در ابرها استراتژی زمان بندی  یا اختصاص منابع به درخواست های سیستم می باشد. دلایل متعددی از جمله ناهمگون بودن و پویایی خصوصیات منابع و درخواست ها در محیط ابرهای محاسباتی موجب شده که این موضوع به عنوان یک مسئله ی NP-کامل  نمود پیدا کند.

فهرست مطالب

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

فصل دوم- ادبیات و پیشینه ی تحقیق    7
۲-۱ مقدمه    8
۲-۲ ابرهای محاسباتی    8
۲-۲-۱  تعریف    9
۲-۲-۲ تاریخچه    9
۲-۲-۳  معماری ابرهای محاسباتی    10
۲-۲-۴ مدل های پیاده سازی ابرهای محاسباتی    11
۲-۲-۵ مجازی سازی    12
۲-۲-۶ مزایای ابرهای محاسباتی    12
۲-۲-۷ چالش های ابرهای محاسباتی    13
۲-۳ زمان بندی کارهای مستقل    14
۲-۳-۱ تعریف    15

۲-۳-۲ الگوریتم های زمان بندی در ابرهای محاسباتی    16

۲-۳-۲-۱  مروری بر الگوریتم های زمان بندی حداکثر تلاش    20
۲-۳-۲-۲  الگوریتم زمان بندی آگاه از منبع    20
۲-۳-۲-۳  قیمت گذاری بر اساس فعالیت بهبود یافته (ABC)    21
۲-۳-۲-۴  بهینه سازی ازدحام ذرات (PSO)    21
۲-۳-۲-۵  الگوریتم توافق زمان-هزینه (CTC)    21
۲-۳-۲-۶  چندین گردش کاری با چندین محدودیت  QOS (MQMW)    22
۲-۳-۲-۷  الگوریتم زودترین زمان پایان ناهمگن (HEFT)    22
۲-۳-۳  الگوریتم های فوق ابتکاری    22
۲-۴ زمان بندی بلادرنگ    23
۲-۴-۱    برخی از الگوریتم های زمان بندی بلادرنگ    24
۲-۴-۱-۱الگوریتم نرخ یکنواخت    24
۲-۴-۱-۲ الگوریتم ابتدا زودترین مهلت(EDF)    24
۲-۴-۱-۳ الگوریتم کمترین لختی    24
۲-۴-۱-۴ زمان بندی دو سطحی    25
۲-۵ الگوریتم رقابت استعماری    25
۲-۵-۱  مراحل الگوریتم رقابت استعماری    25
۲-۵-۱-۱  شکل دهی امپراطوری‌های اولیه    27
۲-۵-۱-۲  مدل‌سازی سیاست جذب: حرکت مستعمره‌ها به سمت امپریالیست    29
۲-۵-۱-۳  جابجایی موقعیت مستعمره و امپریالیست    31
۲-۵-۱-۴  قدرت کل یک امپراطوری    32
۲-۵-۱-۵  سیاست رقابت استعماری    33
۲-۵-۱-۶  سقوط امپراطوری‌های ضعیف    35
۲-۵-۱-۷  همگرایی    36
۲-۵-۲  مزایای الگوریتم رقابت استعماری    38
۲-۶ تحقیقات انجام شده در زمان بندی ابرهای محاسباتی    40
۲-۷ جمع بندی و نتیجه گیری    42

مراجع   

 
فهرست شکل ها
شکل۲-۱ معماری ابر محاسباتی]۸[    10
شکل۲-۲ فلوچارت الگوریتم رقابت استعماری]۱۱[    26
شکل۲-۳  اجزای اجتماعی سیاسی تشکیل دهنده یک کشور]۱۱[    27
شکل۲-۴ چگونگی شکل‌گیری امپراطوری‌های اولیه]۱۲[    29
شکل۲-۵ شمای کلی حرکت مستعمرات به سمت امپریالیست]۱۲[    30
شکل۲-۶ حرکت واقعی مستعمرات به سمت امپریالیست]۱۲[    30
شکل ۲-۷ تغییر جای استعمارگر و مستعمره]۱۱[    32
شکل ۲-۸ کل امپراطوری، پس از تغییر موقعیت‌ها]۱۱[    32
شکل ۲-۹ شمای کلی رقابت استعماری: امپراطوری‌های بزرگتر، با احتمال بیشتری، مستعمرات امپراطوری‌های دیگر را تصاحب می‌کنند]۱۱[    33
شکل ۲-۱۰ سقوط امپراطوری‌ ضعیف ]۱۱[    36
شکل۲-۱۱ شبه کد مربوط به الگوریتم رقابت استعماری]۱۱[    37
شکل ۲-۱۲ شمای کل الگوریتم رقابت استعماری به صورت گرافیکی]۱۱[    38