دانلود پروژه کامل با عنوان انواع الگوریتم های زمانبندی در رایانش ابری (docx) 1 صفحه

دسته بندی : تحقیق

نوع فایل : Word (.docx) ( قابل ویرایش و آماده پرینت )

تعداد صفحات: 1 صفحه

قسمتی از متن Word (.docx) :

چکیده امروزه محاسبات ابری شهرت زیادی پیداکرده و نمونه‌ای از محاسبات توزیع‌شده، متشکل از منابع و درخواست‌ها باهدف اشتراک‌گذاری منابع به صورت سرویس در بستر اینترنت است. این محیط تصوری از منابع بی‌نهایت را برای کاربران فراهم می‌کند؛ بنابراین کاربران می‌توانند مبنی بر تقاضا، میزان استفاده از منابعشان را افزایش یا کاهش دهند. به عبارتی محیط ابر، پرداخت به اندازه استفاده است. در ابر، فراهم‌کنندگان می‌خواهند بیش‌ترین بازده را از منابع خود ببرند و کاربران نیز می‌خواهند هزینه‌های خود را حداقل نمایند درعین‌حال، عملکرد مورد نیازشان را نیز به دست آورند. استفاده مناسب و بهینه از منابعی همچون حافظه، پردازشگر یک چالش است از این رو، چگونگی زمانبندی وظایف مسئله‌ای مهم محسوب می‌شود که تأثیر زیادی در عملکرد فراهم‌کنندگان سرویس ابر دارد. زمانبندی، انتخاب بهترین منبع مناسب باهدف انتشار بار در پردازنده‌ها و حداکثر بهره‌وری از منابع است. درحالی‌که باید زمان پاسخ و تکمیل هر وظیفه و همچنین هزینه سرویس را حداقل نماید. در این گزارش ابتدا به بیان مسئله و مشکل زمانبندی و ادبیات تحقیق اشاره می‌شود. سپس تعاریفی مرتبط با زمانبندی وظایف را مطرح کرده و ویژگی‌های یک زمانبند خوب را بیان می‌کنیم و در آخر به بررسی برخی از الگوریتم‌های موجود در ابر پرداخته و مقایسه‌ای از آن‌ها ارائه می‌شود. فهرست مطالب عنوان شماره صفحه تقدیم و تشکر .................................................................................. ................ ........................................................... ا چکیده .................................................................................................. ................ ..................................................... ب فهرست مطالب .................................................................................... ................ ...................................................... ج فهرست اشکال ..................................................................................... ................ ...................................................... ز فهرست جداول ...................................................................................... ................ ................................................... ح فصل اول: کلیات تحقیق REF _Ref385079959 \r \h \* MERGEFORMAT ‏1-1 REF _Ref385079959 \h \* MERGEFORMAT مقدمه ............................................................ ............. ................... ................ ................ ...................... PAGEREF _Ref385079959 \h 1 REF _Ref385079966 \r \h \* MERGEFORMAT ‏1-2 REF _Ref385079966 \h \* MERGEFORMAT بیان مسئله ...................................................... ................ ................ ................ ............................ PAGEREF _Ref385079966 \h 1 REF _Ref385079968 \r \h \* MERGEFORMAT ‏1-3 REF _Ref385079968 \h \* MERGEFORMAT اهمیت و ضرورت تحقیق...................................... ................ ................ ............................................ PAGEREF _Ref385079968 \h 2 REF _Ref385080365 \r \h \* MERGEFORMAT ‏1-4 REF _Ref385080365 \h \* MERGEFORMAT ادبیات تحقیق ............................................... ................ ................ ................ ................................... PAGEREF _Ref385080365 \h 2 REF _Ref385080383 \r \h \* MERGEFORMAT ‏1-5 REF _Ref385080383 \h \* MERGEFORMAT ساختار گزارش ............................................ ................ ................ ................ ...................................... PAGEREF _Ref385080383 \h 5 فصل دوم: مقدمه‌ای بر رایانش ابری REF _Ref385082310 \r \h \* MERGEFORMAT ‏2-1 REF _Ref385082310 \h \* MERGEFORMAT مقدمه..................................................................................... ..................................................... PAGEREF _Ref385082310 \h 7 REF _Ref385082319 \r \h \* MERGEFORMAT ‏2-2 REF _Ref385082319 \h \* MERGEFORMAT تعریف رایانش ابری .................................................. ................ ................ ................ ............................. PAGEREF _Ref385082319 \h 7 REF _Ref385082337 \r \h \* MERGEFORMAT ‏2-3 REF _Ref385082337 \h \* MERGEFORMAT سیر تکامل محاسبات ..................................................... ................ ................ ................ ..................... PAGEREF _Ref385082337 \h 8 REF _Ref385082344 \r \h \* MERGEFORMAT ‏2-4 REF _Ref385082344 \h \* MERGEFORMAT عناصر زیربنایی محاسبات ابری .............................................................................................................. PAGEREF _Ref385082344 \h 9 REF _Ref385087431 \h \* MERGEFORMAT محاسبات گرید ................................................................................................................................. PAGEREF _Ref385087431 \h 9 REF _Ref385087437 \h \* MERGEFORMAT مجازی سازی ................................................................................................................... PAGEREF _Ref385087437 \h 10 REF _Ref385087443 \h \* MERGEFORMAT وب 2 ..................................................................................................................................... PAGEREF _Ref385087443 \h 10 REF _Ref385087450 \h \* MERGEFORMAT معماری مبتنی بر سرویس(SOA) ....................................................................................... PAGEREF _Ref385087450 \h 10 REF _Ref385082446 \r \h \* MERGEFORMAT ‏2-5 REF _Ref385082446 \h \* MERGEFORMAT سرویس‌های محاسبات ابری ........................................................................................................... PAGEREF _Ref385082446 \h 11 REF _Ref385088118 \h \* MERGEFORMAT نرم‌افزار به عنوان سرویس (SaaS) .................................................................................. PAGEREF _Ref385088118 \h 11 REF _Ref385088124 \h \* MERGEFORMAT پلتفرم به عنوان سرویس (PaaS)........................................................................................... PAGEREF _Ref385088124 \h 11 REF _Ref385088129 \h \* MERGEFORMAT زیرساخت به عنوان سرویس (IaaS) ................................................................................. PAGEREF _Ref385088129 \h 11 REF _Ref385082493 \r \h \* MERGEFORMAT ‏2-6 REF _Ref385082493 \h \* MERGEFORMAT بررسی اجمالی از معماری ابر سطح بالا ................................................................................................ PAGEREF _Ref385082493 \h 11 REF _Ref385088636 \h \* MERGEFORMAT لایه کاربر.............................................................................................................................. PAGEREF _Ref385088636 \h 12 REF _Ref385089196 \h \* MERGEFORMAT زیر لایه کاربردی................................................................................................... PAGEREF _Ref385089196 \h 12 REF _Ref385089201 \h \* MERGEFORMAT زیر لایه محیط برنامه‌نویسی......................................................................................... PAGEREF _Ref385089201 \h 13 REF _Ref385088652 \h \* MERGEFORMAT لایه مدیریت سیستم ابر ..................................................................................................... PAGEREF _Ref385088652 \h 13 REF _Ref385089782 \h \* MERGEFORMAT ناظر SLA ........................................................................................................................ PAGEREF _Ref385089782 \h 14 REF _Ref385089805 \h \* MERGEFORMAT تأمین منابع ........................................................................................................................ PAGEREF _Ref385089805 \h 14 REF _Ref385089813 \h \* MERGEFORMAT ترتیب‌دهنده و زمانبند ............................................................................................... PAGEREF _Ref385089813 \h 14 REF _Ref385089821 \h \* MERGEFORMAT توزیع‌کننده ........................................................................................................................ PAGEREF _Ref385089821 \h 14 REF _Ref385089828 \h \* MERGEFORMAT حسابداری ................................................................................................................ PAGEREF _Ref385089828 \h 14 اندازه‌گیری ................................................................................................................ PAGEREF _Ref385089834 \h 15 REF _Ref385089840 \h \* MERGEFORMAT متعادل‌کننده بار ...................................................................................................... PAGEREF _Ref385089840 \h 15 REF _Ref385089856 \h \* MERGEFORMAT مدیریت سیاست ....................................................................................................... PAGEREF _Ref385089856 \h 15 REF _Ref385089861 \h \* MERGEFORMAT ناظر ذخیره منابع پیشرفته ......................................................................................... PAGEREF _Ref385089861 \h 16 REF _Ref385089868 \h \* MERGEFORMAT مدیریت امنیت و تشخیص منابع ........................................................................... PAGEREF _Ref385089868 \h 16 REF _Ref385089877 \h \* MERGEFORMAT مدیریت خودمختار .......................................................................................... PAGEREF _Ref385089877 \h 16 REF _Ref385089885 \h \* MERGEFORMAT اقدامات سبز............................................................................................................ PAGEREF _Ref385089885 \h 17 REF _Ref385088669 \h \* MERGEFORMAT لایه ماشین مجازی .............................................................................................................. PAGEREF _Ref385088669 \h 17 REF _Ref385090496 \h \* MERGEFORMAT ماشین‌های مجازی ............................................................................................... PAGEREF _Ref385090496 \h 17 REF _Ref385090504 \h \* MERGEFORMAT ناظر ماشین مجازی ................................................................................................... PAGEREF _Ref385090504 \h 17 REF _Ref385088711 \h \* MERGEFORMAT لایه مرکز داده .............................................................................................................. PAGEREF _Ref385088711 \h 18 REF _Ref385090718 \h \* MERGEFORMAT سخت‌افزار .............................................................................................................. PAGEREF _Ref385090718 \h 18 REF _Ref385082519 \r \h \* MERGEFORMAT ‏2-7 REF _Ref385082519 \h \* MERGEFORMAT مدلهای پیادهسازی محاسبات ابری .............................................................................................. PAGEREF _Ref385082519 \h 18 REF _Ref385091115 \h \* MERGEFORMAT ابر خصوصی....................................................................................................................... PAGEREF _Ref385091115 \h 18 REF _Ref385091123 \h \* MERGEFORMAT ابر عمومی....................................................................................................................... PAGEREF _Ref385091123 \h 19 REF _Ref385091128 \h \* MERGEFORMAT ابر گروهی......................................................................................................................... PAGEREF _Ref385091128 \h 19 REF _Ref385091132 \h \* MERGEFORMAT ابر آمیخته..................................................................................................................... PAGEREF _Ref385091132 \h 19 فصل سوم: تعاریف مرتبط با زمانبندی وظایف REF _Ref385091542 \h \* MERGEFORMAT زمانبندی در سیستمهای توزیع‌شده ................................................................................................. PAGEREF _Ref385091542 \h 21 REF _Ref385091549 \h \* MERGEFORMAT ویژگی‌های زمانبند وظایف...................................................................................................................... PAGEREF _Ref385091549 \h 22 REF _Ref385091555 \h \* MERGEFORMAT هدف زمانبندی وظایف............................................................................................................... PAGEREF _Ref385091555 \h 23 REF _Ref385092040 \h \* MERGEFORMAT تعادل بار .............................................................................................................................. PAGEREF _Ref385092040 \h 23 REF _Ref385092046 \h \* MERGEFORMAT کیفیت خدمات ................................................................................................................. PAGEREF _Ref385092046 \h 23 REF _Ref385092061 \h \* MERGEFORMAT اصول اقتصادی .................................................................................................................... PAGEREF _Ref385092061 \h 23 REF _Ref385092066 \h \* MERGEFORMAT بهترین زمان اجرا ................................................................................................................ PAGEREF _Ref385092066 \h 24 REF _Ref385092071 \h \* MERGEFORMAT توان عملیاتی سیستم ........................................................................................................... PAGEREF _Ref385092071 \h 24 REF _Ref385091561 \h \* MERGEFORMAT ساختارهای زمانبندی...................................................................................................................... PAGEREF _Ref385091561 \h 24 REF _Ref385092342 \h \* MERGEFORMAT زمانبندی متمرکز ........................................................................................................ PAGEREF _Ref385092342 \h 24 REF _Ref385092347 \h \* MERGEFORMAT زمانبندی توزیع‌شده ......................................................................................................... PAGEREF _Ref385092347 \h 24 REF _Ref385092351 \h \* MERGEFORMAT زمانبندی غیرمتمرکز .................................................................................................. PAGEREF _Ref385092351 \h 25 REF _Ref385091575 \h \* MERGEFORMAT طبقه‌بندی سلسله مراتبی............................................................................................................ PAGEREF _Ref385091575 \h 25 REF _Ref385092679 \h \* MERGEFORMAT زمانبندی محلی در برابر عمومی ..................................................................................................... PAGEREF _Ref385092679 \h 26 REF _Ref385092685 \h \* MERGEFORMAT زمانبندی ایستا در برابر پویا ............................................................................................................ PAGEREF _Ref385092685 \h 26 REF _Ref385092692 \h \* MERGEFORMAT بهینه در برابر غیر بهینه .................................................................................................................. PAGEREF _Ref385092692 \h 27 REF _Ref385092700 \h \* MERGEFORMAT توزیع‌شده در برابر غیر توزیعی ...................................................................................................... PAGEREF _Ref385092700 \h 27 REF _Ref385092705 \h \* MERGEFORMAT تقریبی در برابر اکتشافی ................................................................................................................. PAGEREF _Ref385092705 \h 27 REF _Ref385092709 \h \* MERGEFORMAT همکار در برابر غیر همکار ............................................................................................................. PAGEREF _Ref385092709 \h 27 REF _Ref385091581 \h \* MERGEFORMAT مقدمه‌ای بر جریان کار............................................................................................................................. PAGEREF _Ref385091581 \h 28 REF _Ref385093093 \h \* MERGEFORMAT تعریف جریان کار............................................................................................................................ PAGEREF _Ref385093093 \h 28 REF _Ref385093099 \h \* MERGEFORMAT زمانبندی جریان کار......................................................................................................................... PAGEREF _Ref385093099 \h 28 REF _Ref385093104 \h \* MERGEFORMAT معماری سیستم مدیریت جریان کار.................................................................................................. PAGEREF _Ref385093104 \h 28 فصل چهارم: الگوریتم‌های زمانبندی REF _Ref385098472 \h \* MERGEFORMAT مقدمه ....................................................................................................................................................... PAGEREF _Ref385098472 \h 31 REF _Ref385098487 \h \* MERGEFORMAT مدلهای اکتشافی برای زمانبندی وظایف ............................................................................................. PAGEREF _Ref385098487 \h 31 REF _Ref385099467 \h \* MERGEFORMAT استراتژیهای ایستا ........................................................................................................ PAGEREF _Ref385099467 \h 32 REF _Ref385100550 \h \* MERGEFORMAT الگوریتم موازنه بار فرصت‌طلبانه (OLB).............................................................. PAGEREF _Ref385100550 \h 32 REF _Ref385100556 \h \* MERGEFORMAT الگوریتم زمان اجرا کمینه (MET)........................................................................... PAGEREF _Ref385100556 \h 32 REF _Ref385100560 \h \* MERGEFORMAT الگوریتم زمان اتمام کمینه (MCT) ...................................................................... PAGEREF _Ref385100560 \h 32 REF _Ref385100564 \h \* MERGEFORMAT الگوریتم Min-Min ..................................................................................... PAGEREF _Ref385100564 \h 33 REF _Ref385100567 \h \* MERGEFORMAT الگوریتم Min-Max ...................................................................................... PAGEREF _Ref385100567 \h 33 REF _Ref385100574 \h \* MERGEFORMAT الگوریتم GA ....................................................................................................... PAGEREF _Ref385100574 \h 33 REF _Ref385100578 \h \* MERGEFORMAT الگوریتم گرمایشی SA .............................................................................................. PAGEREF _Ref385100578 \h 34 REF _Ref385100583 \h \* MERGEFORMAT الگوریتم Tabu ..................................................................................................... PAGEREF _Ref385100583 \h 34 REF _Ref385100587 \h \* MERGEFORMAT الگوریتم A* ........................................................................................................ PAGEREF _Ref385100587 \h 35 REF _Ref385099473 \h \* MERGEFORMAT استراتژیهای پویا ..................................................................................................... PAGEREF _Ref385099473 \h 35 REF _Ref385101762 \h \* MERGEFORMAT حالتOn-line ............................................................................................................... PAGEREF _Ref385101762 \h 35 REF _Ref385101766 \h \* MERGEFORMAT حالت Batch ................................................................................................................... PAGEREF _Ref385101766 \h 36 REF _Ref385099480 \h \* MERGEFORMAT زمانبندهای اکتشافی ........................................................................................................ PAGEREF _Ref385099480 \h 37 REF _Ref385102044 \h \* MERGEFORMAT هادوپ ......................................................................................................................... PAGEREF _Ref385102044 \h 37 REF _Ref385102048 \h \* MERGEFORMAT درایَد ........................................................................................................................... PAGEREF _Ref385102048 \h 39 REF _Ref385099486 \h \* MERGEFORMAT الگوریتمهای زمانبندی جریان کار ................................................................................................. PAGEREF _Ref385099486 \h 39 REF _Ref385102480 \h \* MERGEFORMAT الگوریتم مسیر بحرانی سریع (FCP) ................................................................................. PAGEREF _Ref385102480 \h 40 REF _Ref385102484 \h \* MERGEFORMAT الگوریتم زمانبند کلی تطبیقی (AGS)................................................................................ PAGEREF _Ref385102484 \h 40 REF _Ref385102492 \h \* MERGEFORMAT مکانیزم نگاشت جریان کار(WMM) ................................................................................ PAGEREF _Ref385102492 \h 41 REF _Ref385102505 \h \* MERGEFORMAT الگوریتم انشعاب جریان کار تطبیقی (AWS)....................................................................... PAGEREF _Ref385102505 \h 41 REF _Ref385102510 \h \* MERGEFORMAT رویکرد سود و زیان .......................................................................................................... PAGEREF _Ref385102510 \h 42 REF _Ref385518536 \h \* MERGEFORMAT الگوریتم بهینه‌سازی اجتماع ذرات(PSO) ......................................................................................... PAGEREF _Ref385518536 \h 43 REF _Ref385518546 \h \* MERGEFORMAT الگوریتم بهینهسازی کلونی مورچگان(ACO) .................................................................................. PAGEREF _Ref385518546 \h 43 REF _Ref385544538 \h \* MERGEFORMAT مقایسه الگوریتمهای اکتشافی ........................................................................................................... PAGEREF _Ref385544538 \h 43 REF _Ref385099511 \h \* MERGEFORMAT نتیجهگیری ........................................................................................................................... PAGEREF _Ref385099511 \h 45 REF _Ref385098502 \h \* MERGEFORMAT الگوریتمهای زمانبندی وظایف بلادرنگ ............................................................................................. PAGEREF _Ref385098502 \h 45 REF _Ref385104178 \h \* MERGEFORMAT استراتژی اولویت ایستا...................................................................................................... PAGEREF _Ref385104178 \h 46 REF _Ref385104196 \h \* MERGEFORMAT استراتژی اولویت پویا....................................................................................................... PAGEREF _Ref385104196 \h 46 REF _Ref385104200 \h \* MERGEFORMAT زمانبندهای بلادرنگ........................................................................................................ PAGEREF _Ref385104200 \h 46 فصل پنجم: نتیجه‌گیری و کارهای آینده REF _Ref385159757 \h \* MERGEFORMAT نتیجهگیری ................................................................................................................................ PAGEREF _Ref385159757 \h 49 REF _Ref385159761 \h \* MERGEFORMAT کارهای آینده ........................................................................................................................................... PAGEREF _Ref385159761 \h 49 منابع ..................................................................................................................................................... PAGEREF منابع \h 50 فهرست اشکال عنوان شماره صفحه شکل 2-1 تعریف NIST از محاسبات ابری ................................................................................................................ PAGEREF _Ref385104669 \h 8 شکل 2-2 سیر تکامل محاسبات ................................................................................................................................. PAGEREF _Ref385104677 \h 9 شکل 2-3 معماری سطح بالای محاسبات ابری با مسائل امنیتی ................................................................................. PAGEREF _Ref385104683 \h 12 شکل 3-1 زمانبندی محلی و عمومی در یک سیستم توزیع شده ................................................................................ PAGEREF _Ref385104715 \h 21 شکل 3-2 طبقه‌بندی الگوریتم‌های زمانبندی .............................................................................................................. PAGEREF _Ref385104753 \h 25 شکل 3-3 مدل مرجع جریان کار .............................................................................................................................. PAGEREF _Ref385104763 \h 29 شکل 4-1 انواع الگوریتم‌های زمانبندی .................................................................................................................... PAGEREF _Ref385122856 \h 31 فهرست جداول عنوان شماره صفحه جدول 1-1 مقایسه پارامترهای مختلف در الگوریتم‌های زمانبندی .............................................................................. PAGEREF _Ref386497567 \h 4 جدول 4-1 مقایسه الگوریتم‌های زمانبندی................................................................................................................. PAGEREF _Ref385424343 \h 43 فصل اول کلیات تحقیق مقدمه با توجه به پیشرفت در عرصه رایانش، روش‌های بسیاری جهت توزیع منابع و استفاده از داده‌ها از قبیل خوشه‌بندی داده‌ها، رایانش گرید و سیستم مدیریت پایگاه داده‌های توزیع‌شده معرفی‌شده‌اند. رایانش ابری، بخش عظیمی از صنعت فناوری اطلاعات را دگرگون کرده و با ویژگی‌هایی که دارد شکل دیگری از خدمات را به کاربران ارائه کرده است. این فناوری یک مکانیزم در حال ظهور برای محاسبات سطح بالا تلقی می‌شود که در آن ابرها از کاربران خود بر مبنای میزان استفاده از منابع، هزینه دریافت کرده و منابع خود را در اختیار آنها قرار می‌دهند. این عمل شبیه پرداخت صورت حساب برق در هر ماه است که مشتریان به ازای برقی که مصرف می‌کنند هزینه پرداخت می‌کنند. رایانش ابری، داده‌ها را به اشتراک گذاشته‌شده و سرویس‌ها را به صورت شفاف از طریق اینترنت ارائه می‌شوند. با افزایش تعداد کاربران ابر، وظایفی که باید زمانبندی شوند نیز افزایش می‌یابد. زمانبندی در ابر، یک مکانیزم است که وظایف کاربران را به منابع مناسب برای اجرا تخصیص میدهد و به طور مستقیم بر عملکرد ابر تأثیر میگذارد REF Choudhary \h \* MERGEFORMAT [1].. بیان مسئله ابر یک مدل محاسباتی است که نرم‌افزارها، میان افزارها و منابع محاسباتی مبتنی بر وب را هنگام تقاضای کاربران ارائه میکند. با پیشرفت فناوری، کاربران فقط به منابعی که برای انجام کارشان نیاز دارند دسترسی پیدا میکنند، بنابراین فقط به ازای منابعی که استفاده کردند هزینه پرداخت میکنند. در محیط ابر، نیاز است منابع محاسباتی طوری زمانبندی شوند که هم ارائه‌دهندگان، حداکثر استفاده را از منابعشان ببرند و هم کاربران برنامه‌های کاربردی مورد نیاز خود را با کمترین هزینه در اختیار بگیرند. زمانبندی، یکی از مهم‌ترین مسائل در ابر محسوب میشود. محدودیت و موقتی بودن منابع دو شرطی هستند که به زمانبندی تحمیل‌شده‌اند. برای مثال ممکن است وظایف ترتیب اجرای مشخصی داشته باشند یا یک منبع در یک زمان فقط یک وظیفه را اجرا کند. اهمیت مشکل زمانبندی باعث شده که تحقیقات وسیعی در این زمینه انجام شود. هنگامی که فراهم‌کننده منابع درخواستی را از کاربر دریافت میکند، برنامه کاربردی تصمیم به زمانبندی میگیرد. زمانبندکار مسئول تخصیص منابع به کارها است به طوری که از منابع محاسباتی به صورت کارآمد استفاده شود. برنامه کاربردی همچنین مطمئن میشود که به هر کار، یک مقدار مساوی از منابع داده شود. در محیط ناهمگون، یک تصمیم زمانبندی، پیچیدهتر نیز میشود. اهمیت و ضرورت تحقیق از آنجایی که منابع موجود در ابر در هر زمان در حال تغییر هستند مسئله زمانبندی وظایف امر مهمی است که تأثیر زیادی در عملکرد محیط محاسبات ابری دارد. الگوریتم زمانبندی روشی است که به وسیله آن وظایف به منابع موجود در مراکز داده تخصیص داده می‌شود. انتخاب یک زمانبندی نامناسب می‌تواند باعث ناکارآمدی سخت‌افزار یا کند شدن برنامه ابر شود. در مواردی انتخاب نادرست الگوریتم باعث می‌شود مسئله‌ای که چند ثانیه زمان می‌برد در چندین ساعت حل شود؛ بنابراین یک زمانبند خوب باید در شرایط مختلف رفتار مناسبی داشته باشد. کارآمدی یک الگوریتم را توسط مقدار زمانی که برای اجرای آن لازم است ارزیابی می‌کنند. در این تحقیق به بررسی برخی از الگوریتم‌های موجود در ابر می‌پردازیم تا با شناخت بهتر آن‌ها بتوانیم الگوریتمی کارا برای محیط ابر طراحی کنیم. ادبیات تحقیق انواع متنوعی از الگوریتمهای زمانبندی در سیستمهای توزیع‌شده وجود دارد. هدف اصلی الگوریتمهای زمانبندی به دست آوردن عملکرد محاسباتی بالا و بهترین توان عملیاتی سیستم است. الگوریتم‌های زمانبندی کار سنتی قادر به فراهم کردن زمانبندی در محیط ابر نیستند زیرا سربار هزینه‌دارند و فراهمکنندگان به سمت استفاده از الگوریتمهای اکتشافی یا ترکیبی میروند. در این قسمت به بررسی چندین الگوریتم زمانبندی میپردازیم. در ضمن در جدول 1-1 نیز به مقایسه آنها پرداخته خواهد شد. در REF Selvarani \h \* MERGEFORMAT [2] یک الگوریتم بهبودیافته مبتنی بر هزینه برای زمانبندی وظیفه ارائه‌شده است. این الگوریتم به منظور نگاشت کارآمد وظایف به منابع موجود در ابر مطرح شده است. دو فاز اصلی در این الگوریتم شامل استفاده از الگوریتم لانه زنبور بهبودیافته برای اختصاص اولویت به وظایف و سپس از الگوریتمی به منظور گروه‌بندی وظایف بر اساس اولویت آنها می‌باشد. این الگوریتم زمانبندی، هزینه صرف شده بابت در اختیار گرفتن منابع و کارایی محاسبات انجام‌شده برای اتمام وظایف جریان کار را محاسبه می‌نماید. در این الگوریتم نسبت هزینه صرف شده برای در اختیار گرفتن منابع به هزینه ارتباط کارآمد برای انجام وظایف جریان کار، بهبود قابل‌توجهی داشته است. در REF Liu \h \* MERGEFORMAT [3] الگوریتم توازی زمان- هزینه ارائه‌شده که عملکرد آن با در نظر گرفتن ویژگی‌های محاسبات ابری می‌باشد. به عنوان مثال، فشرده‌سازی جریان کار به منظور کاهش زمان اجرا و هزینه بر اساس اطلاعات ورودی کاربر که کاربر در هر زمانی وارد سیستم می‌کند، صورت می‌گیرد. در REF Pandey \h \* MERGEFORMAT [4] یک الگوریتم اکتشافی زمانبندی جریان کار، مبتنی بر بهینه‌سازی گروهی وظایف ارائه‌شده است. الگوریتم گروهی وظایف، از رفتار گروهی حیوانات، مانند حرکت دسته‌جمعی پرندگان و ماهی ها الهام گرفته‌شده است. به این جهت که این الگوریتم نیز با یک ماتریس جمعیت تصادفی اولیه، شروع می‌شود، عملکرد آن مشابه بسیاری دیگر از الگوریتم‌های تکاملی همچون الگوریتم ژنتیک پیوسته و الگوریتم‌های مبتنی بر رقابت می‌باشد اما برخلاف الگوریتم ژنتیک، الگوریتم گروهی وظایف هیچ عملگر تکاملی همانند جهش و تزویج ندارد. الگوریتم اکتشافی زمان‌بندی جریان کار، مبتنی بر بهینه‌سازی گروهی وظایف به منظور بهینه‌سازی گروهی وظایف، بر اساس رویکرد اکتشافی برنامه‌های کاربردی و با توجه به منابع موجود در ابر و با هدف کاهش زمان انجام محاسبات و کاهش زمان انتقال داده‌ها طراحی شده است. این الگوریتم از دو جزء اصلی که شامل استفاده از الگوریتم اکتشافی به منظور کشف صحیح منابع و سپس استفاده از الگوریتم بهینه‌سازی گروهی وظایف به منظور نگاشت صحیح این منابع به وظایف می‌باشد، تشکیل شده است. نتایج تجربی نشان می‌دهد که استفاده از این الگوریتم صرفه‌جویی در هزینه‌ها و توزیع متعادل حجم کار بر روی منابع را در برداشته است. در REF Varalakshmi \h \* MERGEFORMAT [5] یک الگوریتم بهینه زمان‌بندی جریان کار ارائه‌شده است. این الگوریتم، به منظور زمانبندی جریان‌های کار در محیط ابر مطرح‌شده و ساختار کلی آن بر اساس یک درخت بیان می‌شود. این الگوریتم متشکل از دو فاز اصلی است که در فاز اول آن با استفاده از الگوریتم کشف منابع، تمامی منابع موجود برچسب خورده و سپس هر کدام از منابع، اطلاعات خود را به گره پدر خود که مستقیماً به آن متصل است ارسال می‌کند، بدین ترتیب کنترل منابع توسط هر گره پدر آسان تر خواهد شد، سپس در فاز دوم با توجه به فاکتور کیفیت سرویس (QOS) که توسط کاربر تعیین می‌شود، اختصاص منابع برای انجام وظایف جریان کار صورت می‌گیرد. به طور کلی این الگوریتم، راه‌حلی را به منظور زمانبندی جریان‌های کاری، با توجه به فاکتورهای QOS درخواستی کاربر ارائه می‌دهد. با استفاده از این الگوریتم، بهبود قابل‌توجهی در استفاده از CPU مشاهده شده است. یک الگوریتم بهبود هزینه برای زمانبندی جریان کار در ابرهای ترکیبی در REF Bittencourt \h \* MERGEFORMAT [6] ارائه‌شده و دارای دو مرحله اصلی الگوریتم، انتخاب وظایف و انتخاب منابع، از ابر عمومی و تشکیل ابر ترکیبی میباشند. درحالی‌که زمانبند تصمیم میگیرد که کدامیک از وظایف باعث کاهش زمان اجرا با استفاده از منابع ابر عمومی میشوند، تعیین کارایی و هزینههای اجرا، نقش عمدهای را در زمانبندی جدید ایفا می‌کنند. در REF Zomaya1 \h \* MERGEFORMAT [7] یک استراتژی پویا توازن بار مبنی بر الگوریتم ژنتیک (GA) ارائه‌شده است. سرعت زمانبند افزایش و تغییر بین پردازندهها کاهش مییابد، وظایف برای اجرا انتخاب و در حالت پیشرفته خصوصیات وظایف شناخته میشود. آستانه سازگاری به توازن بار پویا پردازندهها کمک میکند. در REF Sandeep \h \* MERGEFORMAT [8] الگوریتم بهینهسازی ژنتیک-فازی برای زمانبندی کار به منظور بهبود منابع در چارچوب هادوپ پیشنهاد شده است. در الگوریتم زمانبندی، تجدیدنظر شده و زمان اجرای وظایف را پیش‌بینی میکند تا توازن بار بهتری در میان گرهها در ابر داشته باشد، اما انتخاب بردار وظیفه تأثیر زیادی در کارآمدی پیش‌بینی دارد. در REF Lizheng \h \* MERGEFORMAT [9] یک الگوریتم بهینهسازی اجتماع ذرات(PSO)، برای زمانبندی وظایف در محیط ابر پیشنهادشده که زمان پردازش را حداقل میکند. این الگوریتم با مجموعه وظایف بزرگتر همگرایی سریعتری دارد. فقدان تنوع PSO در همگرایی نابجای آن نقش دارد؛ بنابراین از PSO ترکیبی با عملیات متفاوت برای جلوگیری از همگرایی نابجا در مشکل زمانبندی وظایف استفاده میشود. تمرکز این مقاله، بر حداقل سازی زمان تکمیل کارها و همچنین حداکثر استفاده منابع است. در REF Yajun \h \* MERGEFORMAT [10] یک الگوریتم که ترکیبی ازFCFS و GA ارائه‌شده است. تا بار وظایف ترتیبی در محیط گرید را متوازن کند و زمان اجرا را حداقل و حداکثر استفاده از منابع را داشته باشد. یک تکنیک ارائه‌شده که تفاوت بین ژنتیک و FCFS را برطرف و به تخصیص وظایف سریع نیز کمک میکند. مدلپارامترهاابزارکاراییزمان اجرابهرهوری منابعهزینهImproved Cost-Based Algorithm for Task Scheduling**CloudSimA Compromised-Time-Cost Scheduling Algorithm**SwinDeW-CA Particle Swarm Optimization-based Heuristic for Scheduling Workflow Applications**Amazon EC2An Optimal Workflow Based Scheduling and Resource Allocation in Cloud*Open NebulaA Cost optimization algorithm for workflow Scheduling in Hybrid Clouds***GloBusObservations on Using Genetic Algorithms for Dynamic Load-balancing**Java EnvironmentTasks Scheduling Optimization for the Cloud Computing Systems**Amazon EC2Task Scheduling Optimization in cloud Computing based on Heuristic Algorithm***Amazon EC2A Hybrid Load balancing Strategy of Sequential Tasks for Grid Computing Environments***OmNet ++ جدول 1- SEQ جدول_1- \* ARABIC 1 مقایسه پارامترهای مختلف در الگوریتمهای زمانبندی ساختار گزارش در این فصل به بیان مساله زمانبندی و ضرورت تحقیق پرداختیم. بقیه این گزارش به شرح زیر است: در فصل دوم به مقدمهای از محاسبات ابری شامل تعریف، سیر تکامل محاسبات و عناصر زیربنایی محاسبات ابری میپردازیم. در ضمن سرویسهای متفاوت ابر از قبیل، نرم‌افزار به عنوان سرویس، پلتفرم به عنوان سرویس و زیرساخت به عنوان سرویس و مدلهای استقرار ابر را مورد بررسی قرار میدهیم. همچنین یک معماری سطح بالا از ابر نیز در این فصل ارائه می‌شود. در فصل سوم تعاریف مرتبط با مشکل زمانبندی وظایف را شرح میدهیم. ویژگی‌های زمانبندی وظایف را بیان و هدف از زمانبندی را بررسی میکنیم. همچنین یک طبقه‌بندی سلسله مراتبی مرسوم شامل استراتژیهای ایستا، پویا را شرح می‌دهیم و تعاریفی در رابطه با زمانبندی جریان کار بیان میکنیم. در فصل چهارم الگوریتم‌های زمانبندی وظایف مطرح میشود. به عنوان مثال الگوریتم‌های پویا و ایستا و همچنین الگوریتم‌های زمانبندی بلادرنگ را بیان میکنیم. در ضمن برخی از چارچوبها و زمانبندهای اکتشافی و مبتنی بر بلادرنگ را نیز شرح میدهیم. همچنین بین الگوریتمها مقایسه انجام و نتایج نیز شرح داده شده است. در فصل پنجم نتیجه‌گیری و کارهای آینده ارائه خواهند شد. فصل دوم مقدمهای بر رایانش ابری مقدمه امروزه فناوری اطلاعات و اینترنت عنصر جدایی‌ناپذیر زندگی مردم شده است. با تغییر شیوه زندگی افراد جامعه نیازهای مانند امنیت اطلاعات، پردازش سریع، دسترسی فوری به اطلاعات و از همه مهمتر صرفه‌جویی در هزینهها نیز تغییر پیدا کرده است. به طبع با گسترش این نیازها سازمانها و افراد نیازهای کاملاً متفاوت در زمینه خدمات الکترونیکی با گذشته دارند. محاسبات ابری یک فناوری توسعهیافته است که صنایع IT را قادر میسازد هزینههای محاسباتی را کاهش دهند. کاربران ابر بر حسب تقاضا منابع را در اختیار میگیرند و به اندازهای که از سرویسها استفاده میکنند هزینه را پرداخت میپردازند؛ بنابراین محاسبات ابری یک نوع محاسبات سودمند شناخته میشود. تعریف رایانش ابری به دلیل آن که هنوز تعریف یکسانی از محاسبات ابری ارائه نشده در زیر به چند مورد اشاره می‌کنیم: ابر از دید زیرساخت به نوعی از سیستمهای موازی و توزیعشده گفته میشود که شامل مجموعهای از کامپیوترهای مجازی به هم متصل شده است REF Rajkumar \h \* MERGEFORMAT [11]. رایانش ابری به معنای استفاده اشتراکی از برنامهها و منابع میباشد. ابرها انبار بزرگی از منابع مجازی هستند که به راحتی قابل‌استفاده و در دسترساند (مانند سخت‌افزار، پلتفرمهای توسعه‌یافته و/یا سرویسها(. این منابع میتوانند به صورت پویا پیکربندی مجدد شوند تا یک بار متغیر (مقیاس) را تنظیم و همچنین بهره‌برداری مطلوبی از منابع را فراهم میکنند. این انبار منابع معمولاً به وسیله یک مدل پرداخت به اندازه هزینه که در آن حداقل تضمینهای دادرسی توسط ارائهدهنده زیرساخت بر اساس توافقات سطح سرویس بهره‌برداری میشود REF Vaquero \h \* MERGEFORMAT [12]. موسسه ملی فناوری و استانداردها(NIST) نیز این‌گونه تعریف کرده است: رایانش ابری مدلی است برای فراهم کردن دسترسی آسان بر اساس تقاضای کاربر از طریق شبکه به مجموعهای از منابع رایانشی قابل‌تغییر و پیکربندی (مثل شبکهها، سرورها، فضای ذخیره‌سازی، برنامه‌های کاربردی و سرویسها) که این دسترسی بتواند با کمترین نیاز به مدیریت منابع و یا نیاز به دخالت مستقیم فراهم‌کننده سرویس به سرعت فراهم‌شده یا آزاد گردد. بر اساس این تعریف پنج ویژگی ضروری شامل اشتراک منبع رایانش مجازی، دستیابی به شبکه گسترده، قابلیت انعطاف سریع، سلف‌سرویس درخواستی (بنا بر سفارش و تقاضا)، خدمات اندازهگیری شده را برای ابر در نظر گرفته است مدل‌ها و خصوصیات اساسی ابر در شکل 2-1 نشان داده شده است REF Mell \h \* MERGEFORMAT [13]. زیرساخت به عنوان سرویس(IaaS)پلتفرم به عنوان سرویس(PaaS)نرم افزار به عنوان سرویس(SaaS)سرویسهای ابرابر عمومیابر انجمنیابر ترکیبیابر خصوصیمدلهای پیادهسازی ابرخصوصیات ابرانبار منابعدستیابی به شبکه گستردهسرویسهای قابل اندازهگیریقابلیت انعطاف سریعسلف سرویس(بنا بر تقاضا) شکل2- SEQ شکل \* ARABIC 1تعریف NIST از محاسبات ابری REF Mell \h \* MERGEFORMAT [13] سیر تکامل محاسبات براي شناخت بهتر رایانش ابري از دید زیرساخت، ابتدا نگاهی به سیر تکاملی سیستمهاي محاسباتی از ابتدا تا کنون می‌اندازیم تا بتوانیم جایگاه آن را در بین دیگر سیستمها تشخیص دهیم. اگر کامپیوترهای مرکزی را به عنوان نسل اول سیستمهاي محاسباتی در نظر بگیریم، ما با یک سیستم بسیار بزرگ مواجه بودیم که کاربران از طریق یک ترمینال واحد به آن دسترسی پیدا می‌کردند. به مرور این سیستمها کوچک‌تر شدند و با توان پردازشی بیشتري به صورت رایانههاي شخصی در اختیار همه کاربران قرار گرفتند. سپس این امکان فراهم شد که با اتصال مجموعهاي از این سیستمهاي کوچک، شبکه‌ای با توان پردازشی بیشتر فراهم نمود تا پاسخگوي نیازهاي پردازشی بیشتر و سنگینتر باشند؛ اما نیازهاي پردازشی به شکل فزایندهاي در حال افزایش بودند و نیاز به سیستمهاي محاسباتی بزرگتر و قويتر احساس شد؛ بنابراین تعداد زیادي از این شبکه‌ها به صورت اختصاصی در سرتاسر اینترنت به هم متصل شدند و شبکه محاسبات توري را به وجود آوردند. در این بین مشاهده شد که میلیونها کاربر در اینترنت وجود دارند که در اکثر اوقات از تمام توان رایانه خود استفاده نمیکنند و سیستم محاسباتی دیگري شکل گرفت تا کاربرانی که تمایل داشته باشند، زمانهاي بیکار سیستم خود را براي کارهاي محاسباتی عام‌المنفعه هدیه کنند؛ بنابراین تعداد بسیار زیادي منبع محاسباتی کوچک در شبکه‌ای تحت عنوان محاسبات داوطلبانه به هم پیوستند و توان پردازشی عظیمی را به وجود آوردند؛ اما هنوز منابع بسیار زیاد دیگري در سازمان ها و مراکز داده اینترنتی وجود داشت که تمام ظرفیت آنها به طور کامل بکار گرفته نشده بود. این منابع نمی‌توانستند در شبکه محاسبات توري به صورت اختصاصی بکار گرفته شوند، زیرا براي آنها وظیفه دیگري تعریف شده بود. درعین‌حال امکان استفاده از آنها در شبکه داوطلبانه هم وجود نداشت، چون فلسفه وجودي آنها، کاربردهاي تجاري بود. در شکل 2-2 روند تکامل محاسبات را مشاهده میکنید. ابرداوطلبانه و گریداینترنت، P2P، گریدشبکه و کلاسترکامپیوتر شخصیکامپیوترهای مرکزی شکل SEQ شکل \* ARABIC 2-2 سیر تکامل محاسبات به این ترتیب رویکرد جدیدي شکل گرفت که بتوان با استفاده از فناوری‌های مجازي سازي این منابع را به صورت قابل‌انعطاف و پویا براي کاربردهاي مختلف مورد استفاده قرار داد و از تمام ظرفیت آ نها به طور موثر استفاده کرد. این فناوري رایانش ابري در لایه زیرساخت نام داشت که امکان استفاده از منابع محاسبات و ذخیره‌سازی را به صورت یک سرویس بر حسب نوع نیاز فراهم می‌آورد. در حقیقت با ایجاد یک لایه انتزاعی بر روي کلیه منابع فیزیکی خود به کمک مجازي سازي امکان مدیریت پویاي منابع فیزیکی حاصل می‌شود. رایانش ابري از دید زیرساخت، به گونهاي سیستمهاي توزیعشده و موازي اطلاق میگردد که مجموعهاي از رایانه‌های مجازي را که به یکدیگر متصل هستند، شامل می‌شود. این رایانه‌ها به طور پویا عرضه‌شده و به عنوان یک یا چند منبع محاسباتی یکپارچه بر اساس توافقات سطح سرویس ارائه می‌شوند. عناصر زیربنایی محاسبات ابری محاسبات گرید محاسبات گرید یک فناوری جدید است و شامل اصول، مفاهیم، تئوریها، روش‌ها و کاربردهای مختلف در زمینههای گوناگون است. یک شبکه از کلیه قابلیت‌های سخت‌افزاری و نرم‌افزاری موجود که به صورت یک سیستم جامع و کامل در خدمت مؤسسات تجاری و سازمان ها است تا بدین وسیله حداکثر استفاده را از این منابع ببرند. گرید یک سیستم توزیعی و موازی است؛ که قابلیت اشتراکگذاری، انتخاب و اجماع منابع توزیع‌شده در گستره جغرافیا را به صورت پویا و در زمان اجرا بر اساس ویژگیهای منابع، مانند در دسترس بودن، قدرت محاسباتی، هزینه و کیفیت سرویس مورد نیاز کاربران، فراهم میآورد REF Rajkumar \h \* MERGEFORMAT [11]. گرید دارای ابزارهای خاصی است که امکان حل مسائل پیچیده، در زمینه علم، مهندسی و تجارت را برای سازمانهای خاص فراهم میکند. حل مسائل علمی نیاز به حجم بالای محاسبات و پردازش دارند و منابعی در یک دامنه مدیریتی را میطلبد که گرید این توانایی را برآورده کرد. مجازی سازی فراهم‌کنندگان سرویس ابر به طور اساسی میلیونها کامپیوتر را که از مراکز داده با مقیاس بالا تشکیل‌شده‌اند را فراهم میکند. این قبیل مراکز داده به مشتریان زیادی با برنامه‌های کاربردی تفاوت سرویسدهی میکند. مجازی سازی میتواند برای این هدف در نظر گرفته شود. ایده مجازی سازی از سیستم‌عامل توزیع‌شده می‌آید اگرچه مجازی سازی سخت‌افزار اجازه میدهد چندین سیستم‌عامل ماشین مجازی را فراخوانی کند و پشته نرم‌افزار در یک پلتفرم فیزیکی منفرد قرار بگیرند REF Blau \h \* MERGEFORMAT [14]. وب 2 پدیدآورندگان این فناوری به دنبال نسل جدیدي از وب بودند که بتواند جذاب، کاربردي و قابل‌گسترش باشد. این از جمله عواملی بود که بحث‌های زیادي پیرامون این پدیده مطرح شود. وب 2 در نظر دارد اینترنت را به صورت پلتفرم درآورد. بدین معنی که هدف وب 2، بی‌نیاز کردن ما از سیستم‌عامل است، اگرچه این ادعایی بزرگ است اما وب 2 تا حد زیادي به این هدف دست یافته است. اینجا بود که مفهومی بنام سیستم‌عامل جهانی شکل گرفت. کاربران با داشتن یک مرورگر روي هر دستگاهی و با اتصال به اینترنت می‌توانند از کلیه سرویس‌های لازم جهت کارهاي روزمره خود بهره گیرند. یکی از پیامدهای سیستم‌عامل جهانی، پایان چرخه‌ی سنتی تولید و عرضه نرم‌افزار است. می‌توان گفت اینترنت و به طور مشخص وب 2 مهم‌ترین عامل در شکل‌گیری پردازش ابري می‌باشد. وب 2 جزیی از پردازش ابري است. معماری مبتنی بر سرویس(SOA) سبکی از معماری که از اتصال سست سرویسها جهت انعطاف‌پذیری و تعامل پذیری کسب‌وکار و به صورت مستقل از فناوری، پشتیبانی میکند و از ترکیب مجموعه سرویسهای مبتنی بر کسب‌وکار تشکیل‌شده که این سرویسها انعطاف‌پذیری و پیکربندی پویا را برای فر آیند ها محقق میکند REF Papazoglou \h \* MERGEFORMAT [15]. به عبارتی معماری سرویس گرا برای پیاده‌سازی استانداردهای سرویس وب و یک مکانیزم تحویل سرویس به کار میرود. سرویس‌های محاسبات ابری مدلهاي سرویس‌دهی یا اشکال ارائه خدمات رایانش ابري، در واقع نوعی منابع است که در این فناوري از طریق اینترنت در اختیار کاربران گذاشته میشود. تمام سرویس‌های ابري را میتوان بر اساس این منابع طبقه‌بندی کرد و معمولاً با لفظ «به عنوان سرویس» آورده شده و مورد استفاده قرار میگیرند. سرویس‌های اصلی ابر شامل نرم‌افزار به عنوان سرویس(SaaS)، پلتفرم به عنوان سرویس(PaaS)، زیرساخت به عنوان سرویس(IaaS) میباشند REF Goyal \h \* MERGEFORMAT [16]. نرم‌افزار به عنوان سرویس (SaaS) در این مدل نرم‌افزارهای کاربردی تجاری به عنوان سرویس به کاربران/مشتری عرضه می‌شود؛ زیرا مشتری بر حسب نیاز از اجزاء نرم‌افزاری فراهم‌کننده‌های متفاوت استفاده می‌کند؛ بنابراین هدف اصلی حفاظت از اطلاعاتی است که به وسیله این سرویس ها تشکیل‌شده‌اند. به عنوان مثال تعدادی از فراهم‌کنندگان نرم‌افزار به عنوان سرویس می‌توان به Google App, Salesforce نام برد. پلتفرم به عنوان سرویس (PaaS) در این مدل برنامه‌های کاربردی روی یک پلت فرم یا سیستم‌عامل توسعه داده می‌شوند؛ و به کاربر این امکان را می‌دهند که برنامه‌های خود را در ابر اجرا کنند.Microsoft Azure, Google AppEngine مثال‌هایی از فراهم‌کنندگان پلت فرم به عنوان سرویس هستند. زیرساخت به عنوان سرویس (IaaS) در این مدل سختافزار کامپیوتر مشابه سرورها، تکنولوژی شبکه، ذخیرهسازی و فضای مراکز داده به عنوان سرویس ارائه می‌شوند. برای مدیریت بهتر منابع می‌تواند شامل سیستم‌عامل و تکنولوژی مجازی سازی باشد. مثل Amazon S3, EC2 و Open Nebula REF Goyal \h \* MERGEFORMAT [16]. بررسی اجمالی از معماری ابر سطح بالا بر طبق شکل 2-3 یک معماری سطح بالا REF Thirupathi \h \* MERGEFORMAT [18]، REF Reddy \h \* MERGEFORMAT [17] از سرویس‌های محاسبات ابری همراه با مسائل امنیتی در لایه‌های مختلف مشاهده میکنید. در این قسمت ما جزئیات هر لایه و مسائل امنیتی هر کدام را شرح می‌دهیم. امنیت به عنوان سرویس، امنیت جستجوگر، تصدیقتشخیص هویت، زیرساخت، حریم خصوصی، گذر داده، بازرسی و موافقت، مسائل امنیتی و جامعیت ابرپخش VM، رهاییVM، زیرساخت، جداسازی بین مشتریان ،مسائل قانونی ابر، مدیریت دسترسی و تشخیص هویتامنیت در بقیه مواردامنیت فیزیکی : سرور و شبکهسخت افزارناظر ماشین های مجازیماشینهای مجازیمتعادل کننده باربرنامه ها ، برنامه نویسی، ابزارها و محیط ابرB2B, Face Book, Myspace, Enterprise, ISV, Scientific, CDNs, Web 2.0 Interfaces, Aneka, Mashups, Map Reduce, Hadoop, Dryad , Workflows, scriptingناظر SLAاندازهگیریحسابداریتامین منابعزمانبند و توزیع کنندهمدیریت سیاستناظر رزرو منابع پیشرفتهVM-2AppOSVM-1AppAppOSAppVM-nOSAppلایه کاربرلایه فراهم کننده سرویسلایه VMلایهمرکز دادهزیرساخت به عنوان سرویس( IaaS)پلتفرم به عنوان سرویس( PaaS)نرم افزار به عنوان سرویس( SaaS)مدیریت امنیت و تشخیص هویتاقدامات سبزمدیریت خود مختار شکل 2- SEQ شکل \* ARABIC 3 معماری سطح بالای محاسبات ابری با مسائل امنیتی REF Reddy \h \* MERGEFORMAT [17] لایه کاربر انواع مختلفی از کاربران مثل مشتریان، برنامه‌نویسان کاربردی و مدیرها از طریق لایه کاربر با نرم‌افزارهای ابر ارتباط برقرار می‌کنند. این لایه از دو زیر لایه تشکیل شده است. زیر لایه کاربردی برنامه‌های کاربردی ابر از طریق لایه کاربر برای کاربران نهایی ابر قابل مشاهده است. به طور معمول، برنامه‌های کاربردی از طریق پورتال وب توسط کاربران را دیده و تا در زمان مورد نیاز از آنها استفاده کنند. سربار تعمیر و نگهداری نرم‌افزار است که توسط این لایه فرعی و همچنین عملیات در حال انجام و هزینه‌های پشتیبانی انجام می‌شود. علاوه بر این، آن وظایف محاسباتی را از ترمینال کاربر به سرور در مراکز داده که در آن برنامه‌های کاربردی ابر مستقر هستند، انتقال میدهد. این به نوبه خود، سخت‌افزار مورد نیاز از دیدگاه کاربر را به حداقل می‌رساند و به آنها اجازه به دست آوردن عملکرد بیشتر می‌دهد. این رویکرد از پردازش مؤثر حجم کار در CPU های فشرده و حافظه فشرده کاربران بدون هیچگونه سرمایه‌گذاری عظیم در ماشین محلی خود، پشتیبانی میکند. بنابراین این لایه فرعی حتی کار، درجه‌بندی کد و تست را ساده میکند. توسعه‌دهندگان میتوانند ویژگی‌های جدید را از طریق تکه‌ها به راحتی و بدون توزیع کاربران نهایی، به عنوان نرم‌افزار ابر در زیرساخت‌های محاسبات ارائه‌دهنده و نه در ماشین کاربر توسعه داده شود. از آنجایی که توسعه محیط باعث محدود شدن ارائه‌دهنده مرکز داده میشود، پیکربندی و تست برنامه با استفاده از قابلیت این زیر لایه، پیچیدگی کمتری دارد. با وجود همه فواید و مزایای استفاده از قابلیت این زیر لایه، تعدادی از مسائل مربوط به توسعه به مانع برمیخورد. به طور خاص، دسترس‌پذیری و امنیت برنامه‌های کاربردی ابر دو چالش عمده‌ای هستند که تأثیر مستقیمی بر موافقت‌نامه سطح خدمات (SLAs) دارند REF Krutz \h \* MERGEFORMAT [19]. زیر لایه محیط برنامه‌نویسی کاربران این لایه، توسعه‌دهندگان کاربردی ابر هستند که مسئول توسعه و به‌کارگیری برنامه‌های کاربردی بر روی ابرمی باشند. ارائه‌دهندگان خدمات ابر از محیط توسعه با مجموعه‌ای لازم از تعریف رابط‌های برنامه کاربردی حمایت میکنند. توسعه‌دهندگان با محیط از طریق رابط‌های برنامه کاربردی موجود، ارتباط برقرار میکنند که با پشتیبانی از مقیاس‌پذیری توسعه و حمایت را شتاب میبخشند. موتور App گوگل REF Google \h \* MERGEFORMAT [20] یک مثال از این گروه است که از محیط زمان اجرا پایتون و رابط‌های برنامه کاربردی برای ارتباط برقرار کردن با محیط زمان اجرا ابر گوگل پشتیبانی میکند. از طریق این روش پیاده‌سازی، پراکنده شدن اتو ماتیک و تعادل بار برای توسعه‌دهندگان در توسعه برنامه‌های کاربردی‌شان در یک محیط برنامه‌نویسی آسان میشود. لایه مدیریت سیستم ابر این لایه مدیریت برنامه‌های کاربردی و زیرساخت‌های مجازی را برای راه‌حل‌های کسب‌وکار فراهم می‌کند. این لایه مسئول ارائه منابع مجازی برای سرویس‌های مانند مدیریت سطح سرویس، مدیریت سیاست‌های استفاده، مدیریت مجوز و بازیابی فاجعه است. این لایه پشتیبانی از پراکندگی برنامه‌های کاربردی از طریق تخصیص پویا منابع برنامه‌های کاربردی پشتیبانی میکند، در نتیجه تقاضا استفاده از منابع به حداقل میرسد. مؤلفه‌های کلیدی از لایه مدیریت خدمات ابر در زیر فهرست شده است. ناظر SLA هنگامی که یک مشتری برای اولین بار درخواست سرویس را میفرستد، درخواست توسط ناظرSLA به منظور بررسی نیازمندیهای کنترل کیفیت سرویسQOS))برای اینکه تعیین کند آیا درخواست قبول یا رد شود. آن همچنین مسئول نظارت بر پیشرفت میباشد. اگر هر گونه تخلف از SLA، توسط ناظر SLA مشاهده شود، آن فوراً برای اقدامات اصلاحی عمل میکند. تأمین منابع دسترس‌پذیری ماشینهای مجازی(VMs) و منابع مورد نیاز را از طریق این مکانیزم دنبال میشوند. آن درخواست‌های مختلفی که از سرورهای مجازی میآیند را با ایجاد نسخه‌های متعدد ازVM ها مدیریت میکند. تأمین‌کننده منابع به صورت پویا تنظیم میشود به طوری که پردازش، حتی در اوج بار کامل میشود. ترتیب‌دهنده و زمانبند بر اساس اطلاعات ناظرSLA و تأمین منابع، ترتیب‌دهنده کارها را بر اساس اهداف ارائه‌دهنده خدمات، مرتب یا اولویت‌بندی میکند. زمانبند با داشتن آخرین وضعیت اطلاعات تأمین منابع، از جمله دسترس‌پذیری منابع و پردازش حجم کار، باعث ایجاد تخصیص منابع مؤثر میشود. توزیع‌کننده این ماژول وظیفه کنترل منابعی را دارد که توسط زمانبند انتخاب و به فرآیند اختصاص داده میشود. این شامل تغییر متن، تغییر کاربر، توزیع زمان تأخیر (به عنوان مثال زمان مورد نیاز پخش‌کننده برای توقف و شروع یک فرآیند). همچنین این مسئول شروع اجرای درخواست سرویس به ماشین‌های مجازی اختصاص داده‌شده می‌باشد. حسابداری آن سابقهای از منابع واقعی مورد استفاده توسط درخواست خدمات را نگهداری میکند تا به منظور محاسبه هزینه نهایی و هزینه کاربران از آن استفاده کند. علاوه بر این، تصمیم‌گیری در مورد تخصیص منابع می‌تواند با استفاده از اطلاعات تاریخی بهبودیافته شود. اندازهگیری حسابداری کاربران مبتنی بر استفاده از سیستم ها است. معمولاً، صدور صورت حساب مبتنی بر استفاده از CPU در ساعت و یا نرخ انتقال داده در هر ساعت است. این مکانیزم همچنین اطلاعاتی در مورد سیاست‌های قیمت‌گذاری و انواع خدمات به مشتری فراهم می‌کند. مشتری سطح و یا کیفیت خدمات مورد نیاز را انتخاب میکند، بدون نیاز به این که بداند چگونه فراهم‌کننده ابر، سرویس را تأمین میکند. متعادل‌کننده بار این مکانیزم برای شناسایی ماشینهای مجازی بیکار و برای مهاجرت ماشین‌های مجازی به سایر گره‌های فیزیکی، شامل الگوریتمهایی برای نگاشت ماشینهای مجازی به ماشین‌های فیزیکی در یک محیط محاسبات ابری است. هر گاه یک کاربر حجم کاری را به سیستم ابرمی فرستد، می‌تواند یک ماشین مجازی جدید ایجاد میکند. در حال حاضر الگوریتم نگاشت متعادل‌کننده بار، یک طرح جایگزینی ماشین مجازی را تولید میکند، منابع لازم را به آن اختصاص و ماشین مجازی را به منابع فیزیکی شناخته‌شده توسعه میدهد. مدیریت نکردن و فراموشی ماشین‌های مجازی، میتواند منابع مرکز داده را مصرف و باعث اتلاف انرژی شود. الگوریتم دیگری از متعادل‌کننده بار، ماشینهای مجازی غیرفعال را شناسایی و آنها را خاموش میکند. روند بهینه قرار دادن ماشین مجازی در مقصد، ما نیاز به انتقال ماشین‌های مجازی موجود داریم. برای انجام این عملیات، الگوریتم مهاجرت ماشین مجازی از متعادل‌کننده بار فراخوانی می‌شود. به طور خلاصه متعادل‌کننده بار سه زیر ماژول‌های دارد که در زیر به آنها میپردازیم. مدیریت مهاجرت: این با توجه به اطلاعات ارائه‌شده توسط نگارنده VM، باعث مهاجرت زنده VM ها به سرور فیزیکی میشود. به نظر می‌رسد که سرور روشن یا خاموش است. ناظر سرویس: این ماژول پارامترهایی مانند وضعیت برنامه، حجم کار، استفاده از منابع، مصرف انرژی و غیره را جمع‌آوری میکند. این سرویس مانند ارائه‌کننده اطلاعات جهانی عمل نظارت دادهها را برای حمایت از اقدامات هوشمند گرفته‌شده توسط نگارنده VM فراهم میکند. اطلاعات وضعیت به توقف عدم مدیریت و فراموشی ماشین‌های مجازی کمک میکند. نگارنده ماشین مجازی: این الگوریتم به طور بهینه حجم کار ورودی (VMs)را به ماشینهای فیزیکی در دسترس مینگارد. این اطلاعات را از زمان نظارت بر سرویس جمع‌آوری و در مورد قرار دادن ماشین‌های مجازی تصمیم‌گیری میکند REF Thirupathi \h \* MERGEFORMAT [18]. مدیریت سیاست این برای سازمان الزامی است که تعریف روشن و بدون ابهامی از حکومت، سیاست (به عنوان مثال تنظیم‌کننده)، امنیت، حفظ حریم خصوصی REF Mather \h \* MERGEFORMAT [21] و غیره داشته باشد تا مطمئن شود که برنامه‌های کاربردی بر روی ابر اداره می‌شود نقیض SLAs نیست. به منظور مقابله با کسب‌وکار در درون یک ابر، مصرف کنندگان و ارائه دهندگان ابر، SLAs تضمین شده و مدل های قیمت گذاری معادل تراز وسط قرار دارد. مدیر سیاست در داخل و در سراسر مرزهای سازمان، سیستم عامل های IT و برنامه‌های کاربردی ثابت شده، مرسوم شده است. از این رو، در سطح جهان گسترش کسب‌وکار نیاز به استفاده از روش‌های جدید برای ترکیب و تکمیل سیاست در داخل و در سراسر شبکه خارجی و زنجیر تأمین دارد. ناظر ذخیره منابع پیشرفته این مکانیزم برای تضمین کیفیت سرویس در دسترسی به منابع در سراسر مراکز داده است. ذخیره منابع پیشرفته، کاربران را قادر میسازد تا برنامه‌های کاربردی را با توجه به زمان، مانند برنامه‌های جریان کار موازی که بیدرنگ در آینده‌ای نزدیک نیاز به تعدادی از منابع به اجرا دارند، تکمیل کنند. پیش‌بینی تقاضا در آینده و استفاده میتواند توسـط ارائه‌دهنده دقیقتر انجام شود. با استفاده از ایـن اطلاعات، ارائه‌دهنده میتواند درآمد در زمان‌های مختلف را، با استفاده از سیاستهای مدیریت قیمت‌گذاری به حداکثر برساند. در REF Venugopal \h \* MERGEFORMAT [22] یک مکانیزم برای مذاکره ذخیره منابع پیشرفته با استفاده از جایگزین پروتکل فوق ارائه میدهد. مدیریت امنیت و تشخیص منابع محیط‌های ابر باید هویت و زیرساخت‌های امنیتی را به منظور تأمین انعطاف و پیاده‌سازی سیاستهای امنیتی در سراسر ابرها کنترل کنند REF Jensen \h \* MERGEFORMAT [23]. همچنین لازم است از اطلاعات حساس که در برابر SLAs محافظت‌شده، به عنوان تأمین منابع خارج از مرزهای قانونی شرکت‌های ارائه‌دهنده ابر، کنترل و اطمینان حاصل شود. مسائلی که باید توسط ارائه‌دهنده ابر قبل از متقاعد کردن کاربران نهایی برای مهاجرت برنامه‌های کامپیوتری به برنامه‌های کاربردی ابر در نظر گرفته شود، ایمنی و امنیت اطلاعات محرمانه ذخیره‌شده بر روی ابراست. همچنین مسائل دیگری مانند احراز هویت و اعطای مجوز کاربر و عملکرد برنامه‌های کاربردی و در نهایت، تهیه نسخه پشتیبان از داده‌ها و بازیابی آنها برای ارائه SLAs قابل‌اعتماد برای خدمات ابر مورد نیاز است REF Hawald \h \* MERGEFORMAT [24]. مدیریت خودمختار هر عنصر در معماری سرویس ابری، شامل قابلیت مدیریت خودکار میشود. مدیران خودکار وظیفه انتساب کار به هر یک از منابع موجود، انتقال وظایف مبنی بر پیشرفت کلی درخواستهای انجام‌شده در طول اجرای حجم کار را بر عهده دارد. همچنین مدیران خودکار انطباقی، به منظور به حداقل رساندن زمان اجرای کل و بهینه‌سازی QOS، وظایف حجم کار را به سایتهای اجرایی اختصاص میدهند. سیستم خودمختار می‌تواند یک کار را برای اجرا در یک تاریخ و زمان خاص، به صورت پویا در حجم کار رویدادهای کسب‌وکار غیرمنتظره، در حجم کار از طریق یک سرویس وب، گرفتن هشدار موفقیت یا عدم موفقیت کامل شدن کار، تولید گزارش تاریخچه کار و غیره زمانبندی کند. اقدامات سبز رایانش سبز به اجرای سیاستها و روشهایی که از طریق استفاده بهتر از منابع محاسباتی، تأثیر زباله محاسبات بر محیط را کاهش میدهد، اشاره دارد. فناوری سبز عامل محرکی برای صنعت فناوری اطلاعات است و ناحیه مورد توجه در فناوری سبز، «مرکز داده» است. در این شرایط، رفتن به سمت فناوری سبز در مرکز داده، نه فقط یک مسئولیت اجتماعی است، بلکه یک ضرورت کسب‌وکار نیز محسوب میشود. برای داشتن یک مرکز داده‌های سبز، استفاده از متعادل‌سازی قدرت، ظرفیت خنک‌کننده و زیرساختهای کارآمد مؤلفه‌های کلیدی میباشد. به منظور ایجاد یک مرکز داده‌های سبز، درک چگونگی استقرار این اجزا در یک مرکز داده به طور سنتی و دانستن اقدامات گرفته‌شده برای ایجاد مرکز داده سبز مهم است. لایه ماشین مجازی ماشین‌های مجازی ماشین مجازی یک واحد از منابع محاسبات است. کاربران ابری در صورت دسترسی به ماشین‌های مجازی خود، عملکرد و بهرهوری بیشتری خواهند. کاربران می‌توانند نرمافزار پشته ماشین‌های مجازی را سفارشی کنند. اغلب این خدمات به عنوان زیرساخت به عنوان سرویس (IaaS) نامیده می‌شود. مجازی سازی فناوری اولیه در محیط ابر است که به کاربران کمک میکند، بدون اینکه اخلالی در زیرساخت‌های فیزیکی مراکز داده ارائه‌دهندگان ایجاد کنند، با انعطاف‌پذیری فوق‌العاده‌ای به پیکربندی تنظیمات بپردازند. ناظر ماشین مجازی این یک لایه انتزاعی سخت‌افزار است که به عنوان یک رابط بین ماشین‌های مجازی و سخت‌افزار عمل می‌کند. این لایه دسترسی به منابع را با تمام ماشینهای مجازی هماهنگ میکند.VMM سازمان را قادر می‌سازد که از طریق تثبیت منابع محاسباتی، کسب‌وکار را سرعت بدهند. نهایتاً در مدیریت نتایج پیچیدگی کمتری وجود دارد. بهبود بهره‌برداری از منابع و کاهش مصرف برق از جمله چالش‌های کلیدی برای موفقیت است. لایه مرکز داده مراکز داده، در معماری سرویس ابر پایین‌ترین لایه است. به طور معمول شرکتهای بزرگ کاربران این لایه هستند و سخت‌افزار مورد نیازش را از سخت‌افزار به عنوان سرویس(HaaS) اجاره میکنند. ارائه‌دهنده سخت‌افزار به عنوان سرویس در طول مدت اجاره عملیات مدیریت، ارتقاء سختافزار مشتریان را بر عهده دارد. این به شرکتها کمک میکند که به سرمایه‌گذاری در ساخت و مدیریت مراکز داده اعتقاد پیدا کنند. چالشهای تکنیکی که ارائه‌دهنده سخت‌افزار به عنوان سرویس باید در نظر بگیرد، کارایی، آسانی و سرعت تأمین سیستمهای مقیاس بالا است. همچنین مدیریت مراکز داده، زمانبندی و بهینه‌سازی مصرف انرژی از دیگر چالشهایی است که در این لایه باید برآورده شود. سخت‌افزار منابع محاسباتی سخت‌افزارهایی اساسی مانند منابع CPU، منابع حافظه، دستگاههایI / O و سوئیچها که به صورت ستون فقرات از ابر هستند، ارائه میدهند REF Jensen \h \* MERGEFORMAT [23]. مدلهای پیادهسازی محاسبات ابری ابرها در زیرساختهاي فیزیکی به کار میروند جایی که ابرهاي میان افزار براي تحویل سرویس به مشتریان مورد استفاده قرار میگیرد. چنین زیرساختها و میان افزاری از لحاظ سرویس، حوزهي اجرایی و دستیابی به کاربران باهم متفاوت‌اند؛ بنابراین استقرار ابر به سه نوع تقسیمبندي میشود که عبارت‌اند از: ابر عمومی، ابر خصوصی و ابر آمیخته. ابر خصوصی زیرساخت ابری تنها برای یک سازمان کار می‌کند و ممکن است توسط خود سازمان یا شرکتی دیگر مدیریت شود، نیز میتواند درون یا بیرون سازمان جای بگیرد. این نوع از ابر برای سازمانهای با وسعت بزرگ استفاده میشود و میتواند توسط یک سازمان ثالث مدیریت شود REF Ahronovitz \h \* MERGEFORMAT [25]. مزیت آن را مدیریت در نگهداری، امنیت، به‌روزرسانی بهتر و کنترل بیشتر در توسعه و کاربرد دانسته‌اند. ابر عمومی ابر عمومی به کاربر این امکان را میدهد تا از طریق مرورگر اینترنتی به واسط کاربری دسترسی پیدا کند. کاربران مانند قبض برق، به ازای مدت زمان استفاده، هزینه را میپردازند. این امکان کمـک میکـند تا هزینههای عملیاتی IT کاهش یابد، با این وجود از لحاظ امنیتی ابرهای عمومی نسبت به سایر مدلها بیشتر در معرض حملات و سوءاستفاده هستند، یکی از راهکارهای جلوگیری از وقوع حوادث استفاده از کنترلهای امنیتی در هر دو طرف مشتری و فراهم آورنده ابر است. لازم به ذکر است که هر دو طرف نیاز به شناسایی حدود و اختیارات به همراه محدودیتهای عملیاتی خوددارند. ابر گروهی ابر گروهی درجایی به وجود می‌آید که چندین سازمان نیازهای یکسان دارند و به دنبال این هستند که با به اشتراک گذاردن زیرساخت از مزایای رایانش ابری بهرهمند گردند. به دلیل اینکه هزینهها بین کاربران کمتری نسبت به ابرهای عمومی تقسیم می‌شود، این گزینه گرانتر از ابر عمومی است اما میزان بیشتری از محرمانگی، امنیت و سازگاری باسیاست‌ها را به همراه میآورد REF Jadeja \h \* MERGEFORMAT [26]. ابر آمیخته ترکیبی از ابر عمومی و خصوصی و گروهی است. در این مدل یک ابر خصوصی به یک یا چند سرویس ابر خارجی متصل میشود. سازمانها فعالیتهای اصلی که منجر به ایجاد مزیت رقابتی برای آن‌ها میشود را توسط ابر خصوصی انجام داده درحالی‌که فعالیتهای جانبی توسط سایر ابرها (عمومی یا گروهی) کامل میشوند REF Dillon \h \* MERGEFORMAT [27]. فصل سوم تعاریف مرتبط با زمانبندی وظایف زمانبندی در سیستمهای توزیع‌شده در یک سیستم توزیع‌شده ممکن است برخی از گره‌ها غیرفعال و یا به آرامی بارگذاری شوند و این در حالی است که گرههای دیگر به سختی بار میشوند. یک فرصت برای بهبود عملکرد یک سیستم توزیعی، اجرای از راه دور و مهاجرت وظایف از گرههای سنگین به بیکار و یا گره سبک است. این وظیفه زمانبند توزیعی است که با استفاده از روشهای بهینه، فرآیندها را به گرهها (پردازندهها) زمانبندی کند. اغلب یک تمایز ضمنی بین زمانبندی وظایف و تخصیص وجود دارد. اگرچه میتوان استدلال کرد که این دو کلمه جایگزین یک مشکل هستند. از دیدگاه منابع، مشکل این است که چگونه پردازنده‌ها را به فرآیندها تخصیص دهیم. از دیدگاه کاربر، مشکل این است که چگونه فرآیندها در پردازنده‌ها زمانبندی شوند. زمانبندی در سیستمهای توزیع‌شده به طور عمده، پیچیده‌تر از سیستمهای تک پردازندهای است. سیاست زمانبندی توزیع‌شده برای یک سیستم همه منظوره را میتوان منطقاً به دو بخش تقسیم کرد: یک زمانبندی محلی که نشان میدهد، چگونه فرآیندهای موجود در یک گره، به منبع CPU اختصاص داده میشود، درحالی‌که یک سیاست توزیع عمومی (بار)، حجم کاری سیستم را در میان گره‌ها، از طریق انتقال فرآیند و/ یا جایگزینی اولیه گسترش میدهد. یک زمانبندی بار، فرآیندهای جدید را به گرهها تخصیص میدهد و ممکن است زمانی که فرآیندها سیستم را ترک میکنند، دوباره زمانبندی شود. شکل 3-1 نشان میدهد که هر پردازنده دارای مجموعه فرآیندهای خود است و زمانبند محلی هر پردازنده، باتوجه به یک زمانبندی محلی تعیین میکند که کدامیک از فرآیندها، ممکن است اجرا شوند REF Evers \h \* MERGEFORMAT [28]. زمانبند باربار پردازندهها، زمان انتظار در صفوف آماده، پردازندههای موجودزمان انتقال، کدام فرآیند، و جایی که باید منتقل شودپردازنده Nپردازنده 1پردازنده 2گره Nزمانبند محلی Nگره 1زمانبند محلی 1گره 2زمانبند محلی 2فرآیندهای آمادهفرآیندهای آمادهفرآیندهای آماده شکل3- SEQ شکل3- \* ARABIC 1 زمانبندی محلی و عمومی در یک سیستم توزیع شده REF Evers \h \* MERGEFORMAT [28] ویژگی‌های زمانبند وظایف در محیط محاسبات ابری، زمانبندی وظیفه و تخصیص منبع، توسط ارائه‌دهندگان خدمات از طریق فناوری مجازی مدیریت میشود. آنها برای مخفی و کامل کردن وظایف کاربران به صورت شفاف استفاده میشوند. زمانبندی وظیفه به دلیل شفافیت و انعطاف‌پذیری سیستم محاسبات ابری و نیازهای مختلف برای منابع، پیچیدهتر نیز میشود. استراتژیهای زمانبند وظیفه بر عدالت یا بهرهوری منابع تمرکز دارند که هزینه زمان، فضا و توان عملیاتی افزایش و کیفیت سرویس در محاسبات ابری بهبود خواهد داشت. ویژگیهای زمانبندی وظیفه در ابر محیط محاسبات به شرح زیر است REF Hong \h \* MERGEFORMAT [29]: زمانبندی وظیفه ​​یک پلت فرم واحد و یکپارچه منابع تهیه میکند: ما فرض میکردیم که محاسبات ابری با استفاده از فناوری‌های مجازی، منابع فیزیکی (همه نوع میزبان، ایستگاه‌های کاری و یا حتی PC و غیره) را به عنوان یک استخر منابع واحد، محافظ ناهمگن و عرضه برای استفاده بالا قرار داده است. این در حالی است که به طور عمده در تعداد زیادی از رایانههای توزیع‌شده، پخش‌شده‌اند و منابع در قالب یک مرکز داده عرضه میشوند. زمانبندی وظیفه، عمومی و متمرکز شده است: محاسبات ابری یک مدل محاسباتی است که منابع متمرکز را توسط سرویس منعکسی، به چند برنامه توزیع‌شده تأمین میکند و این به‌کارگیری معکوس میتواند روش‌های ناهمگن اجرای عملیاتی را سادهتر توسعه دهد؛ بنابراین، با فناوری مجازی سازی و خدمات معکوس، زمانبندی وظیفه محاسبات ابری، یک زمانبندی متمرکز جهانی به دست میآورد. هرگره در ابر مستقل است: در محیط محاسبات ابری، زمانبندی داخلی هر گره ابر مستقل است و زمانبندها در ابر هیچ دخالتی باسیاست زمانبندی گرههای دیگر نخواهند داشت. مقیاس‌پذیری زمانبندی وظیفه: مقیاس از تأمین منابع ارائه‌دهنده ابر ممکن است در مراحل اولیه محدود باشد. علاوه بر این، انواع منابع محاسباتی و اندازه منابع مجازی انتزاعی ممکن است بزرگ شوند و تقاضای برنامه افزایش یابد. در ابر، زمانبندی وظیفه باید ویژگیهای مقیاس‌پذیری داشته باشد، به طوری که توان عملیاتی زمانبندی وظیفه در ابر، کم نشود. زمانبندی وظیفه می‌تواند به صورت پویای خود تطبیقی باشد: گسترش و کاهش برنامههای کاربردی در ابر ممکن است بسته به نیاز لازم باشد. منابع محاسباتی مجازی در سیستم ابر همچنین ممکن است در همان زمان گسترش یابند و یا کوچک شوند. منابع همواره در حال تغییرند، برخی منابع ممکن است خراب شوند، منابع جدیدی ممکن است به ابرها بپیوندند و یا راه‌اندازی مجدد شوند. مجموعه زمانبندی وظیفه: زمانبندی وظیفه به دو بخش تقسیم میشود: یک بخش به عنوان زمانبندی یک استخر منابع واحد مورد استفاده قرار میگیرد و در درجه اول مسئول زمانبندی برنامه‌های کاربردی و ابر API است و دیگری برای زمانبندی منابع پورت واحد در ابر، به عنوان مثال، زمانبندی وظیفه Map Reduce. با این حال، هر زمانبندی شامل دو فرآیند دو طرفه است: زمانبند منابع را از ابر اجاره و بعد از استفاده، منابع درخواست شده را بر میگرداند. فرایند اول استراتژی زمانبندی و دومی استراتژی بازگشت است، ترکیبی از زمانبندی و استراتژی بازگشت منابع، مجموعه زمانبندی وظیفه را تشکیل میدهند. هدف زمانبندی وظایف اهداف زمانبندی وظیفه محاسبات ابری، ارائه زمانبندی بهینه برای کاربران و در همان زمان، ارائه توان عملیاتی سیستم ابر و QOS است. اهداف خاص زمانبندی شامل: تعادل بار، کیفیت خدمات، اصول اقتصادی، بهترین زمان اجرا و توان عملیاتی سیستم میباشند. تعادل بار تعادل بار و زمانبندی وظیفه در محیط ابری ارتباط نزدیکی با یکدیگر دارند، مکانیزم زمانبندی وظیفه مسئول تطبیق بهینه وظایف و منابع است. از آنجا که وابستگی الگوریتم زمانبندی وظیفه، تعادل بار را به یکی دیگر از معیارهای مهم در ابر تبدیل میکند. از آنجا که سطح حالت متعادل‌کننده بار در زمانبندی وظیفه تحت محیط محاسبات ابری، دو نوع بارگذاری دارد: در مرحله اول بار ماشین مجازی است، دوم بار لایه منابع است. کیفیت خدمات ابر عمدتاً به کاربران، محاسبات و سرویس‌های ذخیره‌سازی ابر را ارائه میدهد، کاربران منابع را تقاضا و منابع توسط ارائه‌دهنده در قالب کیفیت خدمات عرضه میشوند. هنگامی که مدیریت زمانبندی وظیفه به سمت تخصیص وظیفه میرود، تضمین کیفیت سرویس منابع ضروری است. اصول اقتصادی منابع محاسبات ابری به طور گستردهای در سراسر جهان توزیع‌شده‌اند. این منابع ممکن است به سازمان‌های مختلف تعلق داشته باشند. آنها سیاستهای مدیریتی خودشان را دارند. به عنوان یک مدل کسب‌وکار، محاسبات ابری، با توجه به شرایط مختلف، خدمات مربوطه را ارائه میدهد؛ بنابراین تقاضای عوارض معقول است. اقتصاد بازار زمانبندی وظایف و مدیریت منابع هدایت میکند، ما باید مطمئن شوید به نفع هر دو (مصرف‌کننده و ارائه‌دهنده) باشد، به طوری که محاسبات ابری بتواند بیشتر و بیشتر به جلو حرکت کند. بهترین زمان اجرا در درجه اول برای برنامه‌های کاربردی، وظایف را می‌توان با توجه به نیازهای کاربران، به دسته‌های مختلف تقسیم و پس از آن بهترین زمان اجرا را، بر اساس اهداف مختلف برای هر وظیفه تنظیم کرد. آن QOS زمانبندی وظایف را به طور غیرمستقیم در محیط ابر بهبود خواهد بخشید. توان عملیاتی سیستم عمدتاً برای سیستم‌های محاسبات ابری، توان عملیاتی، اندازه‌گیری عملکرد بهینه زمانبندی وظیفه سیستم است و آن نیز یک هدف است که باید در توسعه مدل کسب‌وکار در نظر گرفته شود. افزایش توان عملیاتی برای کاربران و ارائه‌دهندگان ابر سودی برای هر دو آنها خواهد داشت REF Hong \h \* MERGEFORMAT [29]. ساختارهای زمانبندی معماری زیرساخت‌های زمانبندی با توجه به مقیاس‌پذیری، استقلال و عملکرد سیستم بسیار مهم است. این را می‌توان به سه دسته تقسیم کرد: متمرکز، توزیع‌شده و غیرمتمرکز. زمانبندی متمرکز در یک معماری زمانبندی متمرکز، تصمیم‌گیری‌های زمانبندی توسط یک کنترل‌کننده مرکزی برای تمام وظایف گرفته میشوند. زمانبند تمام اطلاعات را در مورد وظایف را نگهداری و وضعیت همه منابع موجود در سیستم را دنبال میکند. سازمان زمانبندی متمرکز به سادگی قابل‌اجرا و توسعه است. با این حال، به دلیل ماهیت محیط محاسبات گرید/ ابر برای آنها کافی نیست. زمانبندی توزیع‌شده در زمانبندی توزیع‌شده، یک مدیر مرکزی و چند نهاد سطح پایین تر وجود دارد. این مدیر مرکزی مسئول اجرای کامل یک وظیفه و تخصیص وظایف منحصربه‌فرد به ارائه‌دهندگان سطح پایین است. هر یک از موجودیتهای سطح پایینتر زمانبند، مسئول نگاشت وظایف منحصربه‌فرد به منابع گرید/ ابر است. این رویکردها کفایت نمیکنند، از آنجا که موجودیتها برای توسعه به سیاستهای زمانبندی مدیر مرکزی نیاز دارند. شکست مدیر مرکزی باعث خرابی در کل سیستم میشود. زمانبندی غیرمتمرکز در مقابل، زمانبند غیرمتمرکز، محدودیتهای ساختارهای متمرکز یا توزیع‌شده را با توجه به تحمل خطا، مقیاس‌پذیری، استقلال و مهمتر از همه، کفایت برای محیط محاسبات گرید/ ابر نفی میکند. در یک روش زمانبندی غیرمتمرکز فرض میشود که هر یک از موجودیت ها مستقل هستند و تصمیم‌گیری زمانبندی از سیاست‌های خودش ناشی میشود. با این حال، تصمیم‌گیریهای مستقل، ممکن است بهینه‌سازی اهدافشان را به جای عملکرد سیستم به عنوان هدف کلی در نظر بگیرند. این مواقع، از مدل ها و تکنیک‌هایی استفاده میکنند که کنترل واحدهای خود را داشته باشند و به طور همزمان عملکرد عمومی سیستم را نیز نگه میدارند REF AbuRukba \h \* MERGEFORMAT [30]. طبقه‌بندی سلسله مراتبی روشهای متنوعی برای مشکل زمانبندی در سیستمهای محاسبات توزیع‌شده وجود دارد. این تنوع مقایسه سیستمهای مختلف را مشکل میکند. در REF Casavant \h \* MERGEFORMAT [31] یک طبقه‌بندی زمانبندی توزیعی ارائه‌شده و در آن از اصطلاحات رایج و مکانیزم کلاس‌بندی برای مقابله با این مشکل استفاده شده است. این طبقهبندی ترکیبی از طبقهبندی سلسله مراتبی و مسطح است. طبقه‌بندی را میتوان، دستهبندی بر اساس یک مجموعه کوچک مناسب از ویژگیهای اساسی مشخص تعریف کرد. طبقه‌بندی سلسله مراتبی در شکل 3-1 نشان داده شده است. الگوریتم های زمانبندی در سیستم های توزیع شدهعمومیمحلیپویاایستابهینهنیمه بهینهتقریبیاکتشافیتوزیع شدهغیر توزیعیهمکارغیرهمکاربهینهنیمه بهینهبهینهنیمه بهینهتقریبیاکتشافی شکل3- SEQ شکل3- \* ARABIC 2 طبقه‌بندی الگوریتم‌های زمانبندی REF Casavant \h \* MERGEFORMAT [31] زمانبندی محلی در برابر عمومی زمانبند محلی تخصیص زمان پردازنده به فرآیندهاست و زمانبندی عمومی، درباره محلی است که فرآیند میخواهد اجرا شود، تصمیم میگیرد. به عبارتی در زمانبندی محلی، به راحتی میتوان ترتیب اجرای پروسه‌های مختلف بر روی یک پردازنده خاص را مدیریت کرد. درحالی‌که در حالت عمومی، یا آگاهی از تعداد پروسهها و پردازندهها میتوان راحتتر شاخصهای بهینه‌سازی را بهبود بخشید. زمانبندی ایستا در برابر پویا سطح بعدی در طبقه‌بندی، انتخاب بین زمانبندی ایستا و پویا است که از جمله عوامل موثر در بهینه‌سازی محسوب میشوند. تصمیم‌گیری در این مرحله مبنی بر زمان است. زمانبندی ایستا به معنای تخصیص فرآیندها به پردازندهها در زمان کامپایل یا زودتر است. زمانبندی پویا به این معنی است که فرآیندها در زمان شروع اجرا به پردازنده تخصیص داده میشوند (تخصیص در زمان اجرا) و ممکن است در حین اجرا تخصیص دوباره انجام شود. تفاوت دیگر این است که زمانبند ایستا، فقط بر اساس اطلاعات فرآیند و سیستم ایستا تصمیمگیری میکند، درحالی‌که زمانبند پویا، وضعیت فعلی سیستم را نیز در نظر میگیرد. الگوریتم‌های زمانبندی ایستا و پویا در ادامه مورد بحث قرار می‌دهیم. الگوریتم‌های زمانبندی ایستا: در زمانبندی ایستا، اطلاعاتی درباره ترتیب کلی فرآیندها در سیستم و همچنین همه زیر وظایف مستقل مرتبط با یک کار را نگه میدارد REF Evers \h \* MERGEFORMAT [28]. در این روش هر وظیفه فقط یک بار به منبع اختصاص داده میشود. در نتیجه محل قرارگیری وظیفه ثابت است و تخمین هزینهها به راحتی انجام میگیرد. همچنین زمانی که حجم کاری قبل از تصمیمگیری به خوبی توصیف شده باشد، میتواند موثر باشد. با این حال، آن در هنگام تغییرات بار سیستم با شکست مواجه میشود REF Casavant \h \* MERGEFORMAT [31]. الگوریتم‌های زمانبندی پویا: در زمانبندی پویا، دانش پیشین درباره نیازهای منابع یک فرآیند کم است و محیطی که فرآیند در طول حیات خود در آن اجرا میشود، مشخص نیست. در این روش مجموعه کارها یا منابع ثابت نیستند، به عنوان مثال، زمان ورود وظایف یکسان نیست یا امکان دارد برخی منابع در زمانهایی فعال نباشند. همچنین در این نوع زمانبندی از سیاست تعادل بار استفاده میشود تا بار کاری منابع را متعادل نماید و تصمیم بگیرد چه وظایفی به کجا منتقل شوند REF Chapin \h \* MERGEFORMAT [32]. بهینه در برابر غیر بهینه حداقل کردن زمان تکمیل فرآیندها، حداکثر استفاده از منابع و حداکثر توان عملیاتی سیستم را به عنوان معیارهای بهینه‌سازی در نظر میگیرند REF Evers \h \* MERGEFORMAT [28]. در زمانبندی نکته‌ای که عموماً لحاظ میگردد نگهداری اطلاعات مربوط به منابع است. روش بهینه سعی دارد هدف را به بهترین شکل برآورده سازد در صورتی که روشهای نیمه بهینه تنها به یک هدف نمیپردازد بلکه سعی بر بهبود نسبی چندین هدف به صورت توأم دارند. با توجه به ساختار شبکههای ابر روش‌های نیمه بهینه بیشتر مورد استفاده قرار میگیرند REF Bruckner \h \* MERGEFORMAT [33]. توزیع‌شده در برابر غیر توزیعی در روشهای زمانبندی پویا و توزیع‌شده، مسئولیت اصلی به عهده یک زمانبند مرکزی و یا چندین زمانبند توزیع شده است. روشهای متمرکز، روشهایی هستند که از سادگی خاصی برخوردارند اما دو مشکل اساسی دارند که عبارت‌اند از تحمل خطا و غیرقابل گسترش بودن. در مقابل روشهای توزیع‌شده با اهداف سیستمهای موازی منطبق هستند. تقریبی در برابر اکتشافی در روش تقریبی از یک واحد و معیار تعریف‌شده برای تخمین بهینه بودن استفاده میشود. هر گاه مقدار مورد نظر برآورده شد، هدف نیز حاصل گردیده است. این روش در صورتی که هدف، کاهش زمان مربوط به زمانبندی باشد، مناسب است. روش مورد استفاده دیگر روشهای اکتشافی است که با فرضهای واقعی در مورد سیستم و گسترده کردن دامنه جستجو، ضمن لحاظ کردن اطلاعات سیستمی نظیر پردازندهها، بارکاری و غیره تمام راهحلهای ممکن را یافته و جواب نزدیک به بهینه را پیدا میکند. روش اخیر در الگوریتمهای زمانبندی بیشتر استفاده میشود REF Blazewicz \h \* MERGEFORMAT [34]. از دسته الگوریتمهای اکتشافی میتوان به MIN-MIN،MAX-MIN و... اشاره نمود. همکار در برابر غیر همکار در زمانبندی عمومی پویای توزیع‌شده، مکانیزمهایی هستند که با اجزای توزیع‌شده سروکار دارند (همکار) و نیز مکانیزم‌هایی که در آن پردازنده‌های فردی مستقل از اعمال پردازنده‌های دیگر تصمیم‌گیری میکنند (غیر همکار) REF Evers \h \* MERGEFORMAT [28]. در سیستمهای زمانبندی ارتباط گرههایی است که کارها بر روی آن قرار دارند، باید در نظر گرفته شود. در حالتی که ارتباط به صورت غیر همکار باشد زمانبندهای منفرد به تنهایی عمل میکنند و تصمیمات زمانبندی را با توجه به هدف بهینه‌سازی خودشان، بدون توجه به دیگر بخشها انجام میدهند. مثالی خوب از این حالت زمانبندی در سطح برنامه کاربردی است که اهداف را به صورت خصوصی بهینه میسازد. در حالت همکار هر زمانبند مسئولیت خاص خود را در زمانبندی کارها دارد اما تمام زمانبندها در جهت هدف کلی سیستم عمل میکنند. سیاست زمانبند محلی، به جای برآوردن نیازمندیهای کارایی محلی و یا یک کار مخصوص، ایجاد تصمیمی است که هدف سراسری را بهبود ببخشد. مقدمه‌ای بر جریان کار تعریف جریان کار جریان کار به معنای مجموعه‌ای از وظایف به همراه وابستگی بین آنها است. در مدل جریان کار، یک فرآیند متشکل از مراحلی ساده است که باعث کاهش پیچیدگی طراحی و نیازهای مدیریتی برنامه‌های کاربردی می‌شود. پیشرفت‌های اخیر در فناوری‌های مجازی سازی و رشد سریع خدمات ابر در سال‌های اخیر، باعث ایجاد یک الگوی جدید برای توزیع محاسبات بر روی ابرها، به منظور استفاده از منابع موجود و مقیاس‌پذیر شده است. سیستم مدیریت فرآیندهای کسب‌وکار به منظور انطباق با این الگوی جدید و جهت استفاده از مزایای خدمات ابر ایجاد شده است. در این راستا بستر به عنوان سرویس در محاسبات ابری، محیطی اجرایی به منظور ایجاد و استقرار برنامه‌های جریان کار در زیرساخت‌های ابر را فراهم می‌سازد REF Du \h \* MERGEFORMAT [35]. زمانبندی جریان کار فرآیند زمانبندی جریان‌های کار به نگاشت وظیفه (گروهی از وظایف) به منابع محاسباتی موجود و زمانبندی اجرای آنها به طوری که وابستگی میان آنها حفظ شود اطلاق می‌گردد. ساختار جریان‌های کاری اغلب به صورت یک گراف بدون دور و همانند یک ساختار درختی تعریف می‌شود REF Yu \h \* MERGEFORMAT [36]. تصمیم‌گیری برای نگاشت وظایف به یک منبع را می‌توان بر اساس اطلاعات موجود در یک زمانبند انجام داد. نحوه تصمیم‌گیری به دو صورت محلی و جهانی می‌باشد. تصمیم‌گیری‌های محلی تنها بر اساس اطلاعات مربوط به یک وظیفه (گروهی از وظایف) که توسط زمانبندی خاص به کار گرفته‌شده‌اند، اتخاذ می‌شوند اما در مقابل، تصمیم‌گیری‌های جهانی با توجه به کل جریان کاری و نه تنها بر اساس یک وظیفه خاص گرفته می‌شوند REF Ullman \h \* MERGEFORMAT [37]. معماری سیستم مدیریت جریان کار یک مدل مرجع در REF Workflow \h \* MERGEFORMAT [38] منتشرشده که در این مدل تعریف سیستم مدیریت جریان کار و رابطهای مهم سیستم را نشان داده است. شکل 3-2 را مشاهده کنید. رابط 1مدیر و ابزارهای نظارترابط 2رابط 3برنامههای کاربردی مشتریموتورهای جریانکاربرنامههای کاربردی درخواست شدهتعریف فرآیندسرویس تصویب جریانکارسرویسهای جریانکار دیگر موتورهای جریانکارمبادله و واسط برنامه کاربردی جریان کاررابط 5رابط4 شکل3- SEQ شکل3- \* ARABIC 3 مدل مرجع جریان کار REF Workflow \h \* MERGEFORMAT [38] موتور جریان کار: یک سرویس نرمافزاری است که محیطی زمان-اجرا به منظور ایجاد، مدیریت و اجرای نمونه جریان کار فراهم میکند. تعریف فرآیند: ارائه یک فرآیند جریان کار به شکلی که از دست‌کاری خودکار حمایت کند. قابلیت همکاری جریان کار: واسط‌هایی برای اینکه از همکاری در سیستم‌های جریان کاری مختلف حمایت کنند. برنامههای کاربردی درخواست شده: واسط‌هایی برای اینکه از تعامل با انواع برنامه‌های کاربردی IT حمایت کنند. برنامههای کاربردی مشتری: واسط‌هایی برای اینکه از تعامل با واسط کاربر حمایت کنند. مدیریت و نظارت: واسطهایی برای ارائه سیستم نظارت و توابع استاندارد که مدیریت ترکیبی محیط برنامههای کاربردی جریان کار را آسان میکنند. این‌گونه به نظر میرسد که زمانبندی یک تابع ماژول از موتورهای جریان کار است، در نتیجه آن بخش قابل‌توجهی از سیستم مدیریت جریان کار است. فصل چهارم الگوریتمهای زمانبندی وظایف مقدمه روش‌های سنتی که در بهینه‌سازی استفاده می‌شوند، قطعی و سریع هستند و معمولاً جواب دقیقی می‌دهند اما اغلب به صورت محلی عمل می‌کنند. زمانبندی وظایف در فضای جستجوی بزرگ مشکل‌تر است و تعداد راه‌حل‌های موجود زیاد است و وظایف برای یافتن راه‌حل بهینه باید زمان بیشتری صرف کنند. برای حل این مشکل در این موقعیت، روش خوبی تعریف نشده است. با این وجود در ابر، پیدا کردن راه‌حلی نزدیک به بهینه هم کارآمد است. در زمینه مشاغل IT بر روی روش‌های اکتشافی تمرکز دارند. در این فصل به بررسی انواع الگوریتم‌های زمانبندی از جمله الگوریتم‌های اکتشافی، بلادرنگ که در شکل 4-1 نشان داده‌شده، می‌پردازیم. الگوریتم PSOالگوریتم ACOزمانبندهای اکتشافیدرایدهادوپزمانبند FIFOزمانبند Fairزمانبند Capacityزمانبند Delayزمانبند FIFOزمانبند FIFOالگوریتمهای اکتشافیاستراتژیهای پویاحالت On-lineالگوریتم OLBالگوریتم METالگوریتم MCTالگوریتم SAالگوریتم KPBحالت Batchالگوریتم Min-Minالگوریتم Max-Minالگوریتم Suffrageاستراتژیهای ایستاالگوریتم MCTالگوریتم OLBالگوریتم METالگوریتم Min-Minالگوریتم Min-Maxالگوریتم GAالگوریتم SAالگوریتم Tabuالگوریتم A*الگوریتمهای جریانکارالگوریتم FCPالگوریتم AGSالگوریتم WMMالگوریتمAWSرویکرد Loss & Gainالگوریتمهای بلادرنگاولویت ایستااولویت پویازمانبند بلادرنگالگوریتم RMالگوریتم DMالگوریتم EDFالگوریتم LLFهسته MARSهسته ARTالگوریتمهای زمانبندی شکل4- SEQ شکل4- \* ARABIC 1 انواع الگوریتمهای زمانبندی مدلهای اکتشافی برای زمانبندی وظایف در محاسبات ابری، یک مرکز داده معمولی از ماشینهای با سرعت بالا تشکیل شده است. این محیط، گروه متنوع و بزرگ از وظایف را محاسبه میکند. وظایف مربوط به کاربران مختلف از یکدیگر متمایز میشوند. در چنین شرایطی مشکل زمانبندی تطبیق چند وظیفه به چند ماشین است. به طور کلی حالت اکتشافی به عنوان یک الگوریتم نیمه بهینه در جهت به دست آوردن راه‌حل‌های خوب است. استراتژیهای ایستا روش اکتشافی ایستا هنگامی استفاده میشود که مجموعه کامل از وظایف قبل از اجرا شناخته شوند. این استراتژی ها تحت دو فرض اجرا میشوند. اول اینکه وظایف به طور همزمان میرسند و فرض دوم این است که زمان ماشینهای موجود، بعد از هر زمانبندی وظیفه بروز میشوند. الگوریتم موازنه بار فرصت‌طلبانه (OLB) ایده اصلی الگوریتم توازن بار فرصت‌طلبانه، اشغال نگه‌داشتن همه پردازندهها تا حد ممکن است. در این الگوریتم، بدون توجه به زمان اجرای وظایف بر روی منابع، به طور مرتب همه منابع را چک میکند و اختصاص وظایف به منابع صورت میگیرد. الگوریتم در صورت تمام شدن کار منبع و وجود وظیفههای زمانبندی نشده، آن وظیفه را به منبع مورد نظر اختصاص میدهد. در واقع وظایف به هنگام رسیدن به سیستم مدیریت منابع، وارد صف شده و هر منبع به محض آزاد شدن، به وظیفه موجود در سر صف تخصیص داده میشود. این الگوریتم تلاش میکند تا در حد امکان همه منابع را مشغول نگه دارد و به این ترتیب، از منابع حداکثر استفاده را کرده و بار کاری را بین آنها به0 طور متوازن پخش میکند. یکی از مزیتهای OLB سادگی آن است اما از آنجائیکه این الگوریتم زمانهای اجرای مورد انتظار کار را در نظر نمیگیرد، معمولاً زمان تکمیل بالایی دارد. در مقابل الگوریتم OLB، الگوریتمهای MCT و MET قرار دارند که هدف آنها کم کردن زمان اجرایی و زمان تکمیل وظیفه است REF Freund \h \* MERGEFORMAT [39]. الگوریتم زمان اجرا کمینه (MET) الگوریتم زمان اجرای کمینه، بر خلاف OLB، هر وظیفه را به ترتیب دلخواه به ماشینی با بهترین زمان اجرای مورد انتظار آن وظیفه اختصاص میدهد بدون اینکه به دسترس بودن آن ماشین توجه کند. هدف MET این است که به هر وظیفه بهترین ماشین مربوطه به آن داده شود. این میتواند باعث عدم توازن جدی بین ماشینها شود. به طور کلی این الگوریتم برای محیطهای محاسباتی ناهمگن مناسب نیست REF Armstrong \h \* MERGEFORMAT [40]. الگوریتم زمان اتمام کمینه (MCT) ایده اصلی الگوریتم زمان اتمام کمینه، ترکیب مزایای دو روش OLB و MET می‌باشد. الگوریتم MCT یک وظیفه را به پردازندهای که کمترین زمان تکمیل را برای آن داشته باشد اختصاص میدهد. این امر باعث میگردد که برخی از کارها به پردازندههایی انتساب شوند که زمان اجرای خوبی نداشته باشند. به محض ورود یک وظیفه به زمانبند، تمام پردازندههای موجود در سیستم بررسی میشوند تا پردازندهای که کمترین زمان تکمیل را برای آن کار دارد، مشخص شود REF Braun \h \* MERGEFORMAT [41]. الگوریتم Min-Min این رویکرد اولویت‌بندی وظایف و تولید زمانبندی بر اساس اولویت است. این اولویت بر اساس زمان اتمام وظیفه مورد انتظار بر روی یک منبع تولید میشود. این روش وظایف را در چند گروه وظایف مستقل تنظیم میکند. پس از آن این گروهها مکرراً زمانبندی میشوند. هر تکرار مجموعه‌ای از وظایف مستقل نگاشت نشده را میگیرد و برای هر وظیفه، حداقل زمان تکمیل مورد انتظار (MECT) را تولید میکند. وظیفهای که کوچک‌ترین مقدار MECT، بیش از تمام وظایف انتخاب‌شده به منابع مربوطه را دارد، در این تکرار اول زمانبندی میشود. این تا زمانی که تمام وظایف زمانبندی شوند، ادامه می‌یابد REF Maheswaran \h \* MERGEFORMAT [42]. هدف این الگوریتم، رسیدن به کمترین پاسخ است و برای رسیدن به این هدف، ابتدا وظایفی با زمان تکمیل کم و سپس وظایفی با زمان بیشتر را زمانبندی میکند. الگوریتم Min-Max این روش مشابه با روش Min-Min، است. الگوریتم Min-Maxبا مجموعهای از تمام وظایف زمانبندی نشده شروع و سپس برای هر وظیفه در مجموعه زمان تکمیل کمینه را محاسبه میکند. تفاوت این الگوریتم با روش قبلی، وظایف با بیشترین زمان تکمیل انتخاب و به ماشین نگاشت میشود. بعد وظیفه زمانبندی شده از مجموعه حذف میشود. این فرآیند تا زمانی که همه وظایف زمانبندی شوند ادامه مییابد. الگوریتم GA الگوریتم ژنتیک از مجموعه تکنیکهای تکاملی برگرفته از طبیعت است که کاربرد فراوانی در مسائل بهینه‌سازی دارد و برای جستجو در فضاهای حل بزرگ استفاده میشود REF Sivanandam \h \* MERGEFORMAT [43]. در ابتدا برای زمانبندی یک وظیفه خاص، یک جمعیت اولیه از کروموزوم ها به صورت تصادفی تولید میشود. هر کروموزوم یک مقدار تناسب دارد که در اینجا زمان کل اجرای وظیفه متناظر با کروموزوم میباشد. بعد از تولید جمعیت اولیه، برای تمام کروموزومهای موجود در جمعیت مقدار تناسب ارزیابی میشود و کروموزومی که کمترین مقدار تناسب را داشته باشد، بهترین نگاشت خواهد بود. سپس الگوریتم وارد یک حلقه شامل 4 مرحله: انتخاب، تولیدمثل، جهش و ارزیابی میشود. در مرحله انتخاب، برخی کروموزومها را تکثیر و برخی را حذف میشوند، به شکلی که نگاشتهای بهتر احتمال تکثیر بیشتری در نسل بعد داشته باشند. سپس ویژگیهای تضمین بقای بهترین راهحل در جمعیت پیادهسازی شده و اندازه جمعیت ثابت میماند. سپس در عملیات تولیدمثل، یک جفت کروموزوم را انتخاب و یک نقطه تصادفی را در کروموزوم اول بر میگزیند. بعد از عملیات تولیدمثل، عملیات جهش ژنی انجام میشود. جهش ژنی یک کروموزوم را انتخاب کرده و سپس یک وظیفه در آن کروموزوم را برمیگزیند و به یک ماشین جدید اختصاص میدهد. در این مرحله هر سه عمل به صورت تصادفی انجام میشوند. نهایتاً، کروموزومهای این جمعیت تغییریافته دوباره ارزیابی میگردند. این مراحل تا زمان رسیدن به شرایط توقف حلقه، تکرار خواهند شد REF Braun \h \* MERGEFORMAT [41]. الگوریتم گرمایشی SA الگوریتم گرمایشی، یک تکنیک با روش تکرار است که فقط یک راه حل نگاشت ممکن را برای هر فرا وظیفه در یک زمان بررسی میکند. این راه حل از همان نمایش کروموزومها در الگوریتم ژنتیک استفاده میکند. الگوریتم SA از روالی استفاده میکند که بر اساس احتمالات به راه‌حل‌های ضعیف تر اجازه پذیرش داده و تلاش میکند تا جستجوی بهتری در فضای راه حل انجام دهد. این احتمال بر اساس دمای سیستم است که در هر دور کاهش مییابد. با خنک شدن سیستم پذیرش برای راه‌حل‌های ضعیف تر سخت تر خواهد شد. دمای اولیه سیستم، زمان اجرای کلی نگاشت اولیه میباشد. در پیاده‌سازی این الگوریتم نگاشت اولیه از یک توزیع تصادفی یکنواخت تولید خواهد شد. نگاشت به همان شکل الگوریتم ژنتیک، جهش ژنی مییابد و زمان اجرای کلی جدید ارزیابی میشود. اگر زمان اجرای کلی جدید بهتر باشد، نگاشت جدید جایگزین قدیمی میشود. اگر زمان اجرای کلی جدید بدتر یا به عبارتی طولانی تر باشد، یک عدد تصادفی یکنواخت انتخاب و بررسی بر اساس آن انجام میشود REF Zomaya \h \* MERGEFORMAT [44]. الگوریتم Tabu جستجوی Tabu، یک جستجوی فضای راهحل است که ناحیههایی از فضای راهحل را که قبلاً جستجو شدهاند، یادداشت میکند تا در جستجوی بعدی حوالی این ناحیه‌ها را جستجو نکند. یک راه حل نگاشت، از همان نمایش کروموزوم در الگوریتم ژنتیک استفاده میکند. پیاده‌سازی جستجوی Tabu، با یک نگاشت تصادفی تولیدشده از یک توزیع یکنواخت به عنوان راهحل ابتدایی آغاز میگردد. برای دستکاری راهحل فعلی و حرکت در فضای راهحل یک گام کوتاه برداشته میشود. هدف از گام کوتاه پیدا کردن نزدیکترین راهحل کمینه محلی در فضای راهحل است REF DeFalco \h \* MERGEFORMAT [45]. الگوریتم A* الگوریتم A*، یک روش اکتشافی جستجو بر اساس درخت شروع است و از یک گره ریشه که یک راه حل تهی است شروع میشود. همان طور که درخت رشد می‌کند، گرهها نشان‌دهنده زمانبندی جزئی (زیرمجموعه‌ای از وظایف به ماشین ها اختصاص داده شده است) و برگ نشان‌دهنده زمانبندی نهایی (همه وظایف که به ماشین ها اختصاص داده شده است)، هستند. راه حل جزئی از یک گره فرزند، یک وظیفه زمانبندی شده از گره پدر دارد. هر گره پدر می‌تواند توسط فرزندانش جایگزین شود. برای نگه‌داشتن زمان اجرای اکتشافی، یک فرآیند هرس به منظور محدود کردن حداکثر تعداد گره فعال در درخت در هر زمان وجود دارد. اگر درخت هرس نشده باشد، این روش معادل جستجوی کامل است. این روند تا زمانی که برگ به زمانبندی کامل رسیده باشد، ادامه مییابد REF Braun \h \* MERGEFORMAT [41]. استراتژیهای پویا روش اکتشافی پویا زمانی که مجموعه وظایف و یا مجموعه ماشینها ثابت نیستد، ضروری است. به عنوان مثال، همه وظایف به طور همزمان نرسند و یا برخی از ماشینهای در فواصل زمانی به حالت آفلاین بروند. روش اکتشافی پویا در دو حالت، آنلاین و دسته‌ای استفاده میشود. در حالت اول، زمانی که یک وظیفه برسد به یک ماشین زمانبندی میشود، در حالت دوم، وظایف ابتدا در یک مجموعه جمع‌آوری شده و زمانبندی در زمان از پیش برنامه‌ریزی‌شده، اجرا میشود. حالتOn-line در حالت اکتشافی آنلاین، هر وظیفه تنها یک بار زمانبندی شده و نتیجه زمانبندی نمی‌تواند تغییر کند. حالت اکتشافی آنلاین برای مواردی با نرخ ورود کم مناسب است. الگوریتم OLB: یک نوع از روشهای اکتشافی پویا است که یک وظیفه را به اولین ماشینی که آماده است، تخصیص میدهد بدون اینکه زمان اجرای آن وظیفه در آن ماشین را در نظر بگیرد. الگوریتم MET: یک نوع استراتژی اکتشافی پویا است که هر وظیفه را به ماشینی که انجام محاسبات مربوط به وظیفه را در کمترین زمان اجرا بدون در نظر گرفتن زمان در دسترس ماشین، اختصاص میدهد. الگوریتم MCT: یک نوع استراتژی اکتشافی پویا است که هر وظیفه را به ماشینی که زودترین زمان اتمام را دارد تخصیص میدهد. این روش اکتشافی به عنوان یک معیار برای حالت آنلاین، استفاده میشود REF Shoukat \h \* MERGEFORMAT [46]. الگوریتم SA: نوع استراتژی پویا اکتشافی در حالت آنلاین است. این الگوریتم از هر دو روش اکتشافی MET و MCT به شیوه‌ای دوره‌ای بر اساس توزیع بار در سراسر ماشین ها استفاده میکند. الگوریتم MET، بهترین ماشین را انتخاب میکند اما وظایف زیادی را به آن تخصیص میدهد. اکتشافی MCT، بار را متوازن میکند ولی در همان زمان آن وظیفه را به ماشین که دارای کمترین زمان اجرا است، تخصیص نمیدهد. برای مثال، اگر وظایف به طور تصادفی برسند، ما میتوانیم از MET برای رسیدن توازن بار به یک مقدار آستانه داده‌شده و سپس از MCT، برای ایجاد سطح بار در سراسر ماشینها استفاده کنیم. الگوریتم بهترین درصد K (KPB): این الگوریتم فقط زیرمجموعه‌ای از پردازندهها را برای تخصیص در نظر میگیرد. یک وظیفه به پردازندهای که نزدیکترین زمان تکمیل را در زیرمجموعه مزبور داشته باشد، تخصیص داده میشود. اگر k=100 باشد، آنگاه الگوریتم به MTC تقلیل پیدا میکند REF Shoukat \h \* MERGEFORMAT [46]. حالت Batch در حالت دسته‌ای، وظایف تنها در برخی از لحظات از پیش تعریف‌شده زمانبندی میشوند. این دسته‌ای اکتشافی را قادر می‌سازد تا در مورد زمان اجرای واقعی تعداد زیادی از وظایف اطلاع داشته باشد. الگوریتم Min-Min: به این صورت عمل میکند که در هر مرحله، از وظایف و مجموعه پردازندهها مجموعهای از زوجهای وظیفه/پردازنده را انتخاب میکند که نزدیکترین زمان تکمیل مورد انتظار را داشته باشند. سپس از این مجموعه زوج وظیفه/پردازندهای که کمترین زمان تکمیل مورد انتظار را دارد انتخاب میکند و آن وظیفه را به آن پردازنده اختصاص میدهد. این روش مانند روش MTC بر اساس حداقل زمان تکمیل است REF Chen \h \* MERGEFORMAT [47]. به هر حال روشMin-Min همه وظایف تخصیص داده نشده را طی هر رخداد تخصیص بررسی میکند درحالی‌که روش MTC تنها یک وظیفه را در هر زمان بررسی میکند. الگوریتم Max-Min: این الگوریتم به این صورت عمل میکند که در هر مرحله از وظایف و مجموعه پردازندهها، مجموعهای از زوجهای وظیفه/پردازنده را انتخاب میکند که نزدیک‌ترین زمان تکمیل مورد انتظار را داشته باشند REF Shoukat \h \* MERGEFORMAT [46]؛ اما برخلاف قبلی این زوج وظیفه/پردازندهای را که بیش‌ترین زمان تکمیل مورد انتظار را دارد انتخاب میکند و آن کار را به پردازنده اختصاص میدهد. در مواقعی که تعداد وظایف کوتاه از تعداد وظایف بلند بیشتر باشد، انتظار میرود نسبت به الگوریتم قبلی بهتر عمل کند. الگوریتم حق رای: یک نوع روش اکتشافی است و هر وظیفه بر اساس مقدار رای، به منبع اختصاص داده میشود. مقدار رای، تفاوت بین اولین و دومین زودترین زمان اتمام تعریف میشود. وظیفه با مقدار انتظار بیشتر به ماشینی با زودترین (کمترین) زمان اتمام تخصیص داده میشود REF Shoukat \h \* MERGEFORMAT [46]. زمانبندهای اکتشافی یکی از مزایای محاسبات ابری است این است که وظایف ممکن است دشوار، وقت‌گیر و یا گران‌قیمت باشند که برای یک کاربر خاص در مرکز داده انجام میشوند. مرکز داده در ابر، جدایی عملی بین قدرت پردازش و ذخیره‌سازی داده‌ها که هر دو در تعداد زیادی از دستگاه‌های از راه دور قرار دارند را پشتیبانی میکند. از این رو، زمانبندی پیچیده‌تر و چالش‌برانگیز تر از قبل میشود. از آنجا که زمانبند فقط یک جزء اساسی برای تمام زیرساخت است، به طور کلی هیچ زمانبندی نمیتواند برای همه معماری ابر، مناسب باشد. هادوپ هادوپ یک چارچوب محاسباتی مهم است. آن فقط پردازش مقدار زیادی از دادهها را در ابرهای خصوصی و عمومی پردازش میکند و برای پیادهسازی ابر اهمیت بسیاری دارد. هادوپ از گسترده‌ترین و برجستهترین پیاده‌سازی‌های نگاشت-کاهش است که برای تولید و یا کاربردهای آموزشی استفاده میشود. آن قادر است برنامه‌های کاربردی بسیاری را برای کار با پتابایت داده و هزاران گره بسازد. یک خوشه از هادوپ چند گرهای از دو لایه تشکیل شده است. در لایه پایین سیستم فایل توزیع‌شده هادوپ(HDFS)، قرار دارد که دارای قابلیت فراهم کردن اطلاعات در مورد آگاهی از محل داده برای انجام زمانبندی موثر کار است. لایه بالا دارای موتور نگاشت-کاهش است که دارای چندین دنبال کننده وظیفه و یک رد گیر کار است و هر رد گیر میتواند یک گره را نگه دارد. کارهای نگاشت-کاهش توسط مشتریان به رد گیر کار ارسال خواهند شد و سپس رد گیر کار، کارها را به گره دنبال کننده وظیفه که در حال حاضر در خوشه هستند، میدهد REF Borthakur \h \* MERGEFORMAT [48]. هادوپ برای کارهای دسته‌ای بزرگ طراحی شده است. زمانبند پیش‌فرض از روش اکتشافی FIFO، برای زمانبندی استفاده میکند، جایگزینهای دیگری نیز برای این زمانبند وجود دارد که زمانبند عادلانه، زمانبند ظرفیت و زمانبند تأخیر هستند که در زیر آنها را شرح میدهیم. زمانبند FIFO: یک نوع زمانبند اکتشافی است که برای اولین بار در اولین روش اکتشافی بکار برده شد. زمانبند یک کار جدید در صف را بر اساس زمان ورود آن نگه میدارد. کاری که در ابتدای لیست انتظار قرار دارد برای اجرا انتخاب میشود. از آنجا که این زمانبند حداقل سربار را دارد و پیاده‌سازی آن بسیار آسان میباشد اما وظایف با زمان اجرای طولانی، توان عملیاتی ماشینها را پایین میآورد REF Borthakur \h \* MERGEFORMAT [48]. زمانبند عادلانه: نوعی زمانبند اکتشافی است که سهم برابری از منابع را به تمام کارها اختصاص میدهد. وقتی کارهای جدید میرسند، بین وظایف یک مقدار آزاد به اشتراک گذاشته میشود، به طوری که هر وظیفه تقریباً همان مقدار از زمان CPU را میگیرد. زمانبند عادلانه از اولویت‌های کار که به عنوان وزنهای برای تعیین کسری از زمان محاسبه کل که هر کار باید بگیرد، پشتیبانی میکند. همچنین اجازه می‌دهد یک خوشه در میان تعدادی از کاربران به اشتراک گذاشته شود. به طور پیش‌فرض به هر کاربر یک مجموعه جداگانه داده میشود، به طوری که هر کس سهم مشابهی از خوشه میگیرد و مهم نیست که چگونه بسیاری از کارها فرستاده میشوند. در هر مجموعه، به اشتراک‌گذاری عادلانه برای به اشتراک گذاشتن ظرفیت بین کارهای در حال اجرا استفاده میشود. علاوه بر این، سهم حداقل تضمین را فراهم میکند. هنگامی که یک مجموعه شامل کارها، به سهم خود به طور کامل نیاز ندارد، مقدار اضافی در میان کارهای دیگر در حال اجرا تقسیم میشود REF Zaharia \h \* MERGEFORMAT [49]. زمانبند ظرفیت: نوعی زمانبند اکتشافی است که مقداری از ظرفیت خوشه را به صف‌های متعدد که هر کدام از آنها شامل بخشی از ظرفیت هستند، اختصاص میدهد. هر کار که به یک صف فرستاده میشود، میتواند به کل به ظرفیت اختصاص داده‌شده به صف دسترسی داشته باشد. صفها در هر زمان، محدودیتهایی را بر روی درصد منابع اختصاص داده‌شده به یک کاربر، اعمال میکنند؛ بنابراین هیچ کاربری نمیتواند به صورت انحصاری منابع را در اختیار بگیرد. صف به صورت اختیاری از اولویت‌های کار پشتیبانی میکند. در یک صف، کارهای با اولویت بالا برای دسترسی به منابع ترجیح داده میشوند. با این حال، هنگامی که یک کار در حال اجرا است، آن برای یک کار با اولویت بالاتر قبضه نخواهد شد REF Zaharia1 \h \* MERGEFORMAT [50]. زمانبند تأخیر: نوعی زمانبند اکتشافی است که بین زمانبندی عدالت و محلیت داده برخورد ایجاد میکند. این نوع به طور موقت، برای بهبود محلیت، عدالت را رها میکند. برای اینکه یک گره با داده‌های محلی را زمانبندی کند، از کارها درخواست انتظار مینماید. هنگامی که این کار باید بعداً با توجه به عدالت زمانبندی شود، نمیتواند یک کار محلی را راه‌اندازی کند، آن را برای مدت کوتاهی انتظار میکشد، اجازه میدهد دیگر کارها بجای آن، وظایف خود را راه‌اندازی کنند. با این حال، اگر یک کار به مدت طولانی نادیده گرفته شود، آن مجاز است برای جلوگیری از قحطی، کارهای غیر محلی را راه‌اندازی کند. زمانبند تأخیر موثر است اگر وظایف در مقایسه با کارها کوتاه و شکافهای بسیاری در هر گره وجود داشته باشد، کارآمد است REF Zaharia2 \h \* MERGEFORMAT [51]. درایَد دراید یک موتور اجرای توزیع‌شده برای برنامههای موازی داده است و به نظر می‌رسد با چارچوبهای برنامه‌نویسی مایکروسافت، قابلیتهایی مشابه هادوپ را فراهم میکند. دراید برای برنامههای کاربردی، گراف بدون دور را بکار میبرد REF Dryad \h \* MERGEFORMAT [52]. زمانبند کوئینسی، به برخورد بین محلیت و زمانبندی در چارچوب دراید، میپردازد. این نشان میدهد مشکل زمانبندی، یک مسئله بهینه‌سازی است. جریان حداقل هزینه، تصمیم‌گیری زمانبندی، ارتباط وظایف و گرهها را میگیرد. ایده اساسی این است که برخی از وظایف در حال اجرا کشته و سپس وظایف جدید در محل خوشه در پیکربندی بازگردانده شده توسط حل کننده جریان راه‌اندازی شوند REF Isard \h \* MERGEFORMAT [53]. الگوریتمهای زمانبندی جریان کار زمانبندی جریان کار یکی از مسائل کلیدی در مدیریت جریان کار، به خصوص در گرید و سیستمهای جریان کار ابر است REF Radulescu \h \* MERGEFORMAT [54]. این یک فرایند است که اجرای وظایف وابسته در منابع توزیع‌شده را مدیریت میکند. این تخصیص مناسب منابع برای وظایف جریان کار، میتواند برای رضایت توابع هدف اعمال‌شده توسط کاربران تکمیل شود. الگوریتم مسیر بحرانی سریع (FCP) الگوریتم مسیر بحرانی سریع (FCP) سعی در کاهش پیچیدگی زمانبندی وظیفه دارد و این در حالی است که عملکرد زمانبندی را نیز حفظ میکند، این پیچیدگی میتواند به طور موثر کاهش یابد اگر لیست وظایف آماده مرتب شده، اندازه ثابتی داشته باشد. در این حالت، بقیه وظایف در یک لیست ساده و نامرتب FIFO که زمان دسترسی O(1) دارد، ذخیره میشوند. وقتی که یک وظیفه آماده میشود، اگر جایی برای آن وجود داشت به لیست مرتب شده اضافه میشود، در غیر این صورت به لیست FIFO اضافه میشود. وظایف همیشه از لیست مرتب شده برداشته میشوند، بعد از آن، اگر لیست FIFO خالی نبود، یک وظیفه به لیست مرتب شده نقل‌مکان میکند. پیچیدگی زمان مرتب‌سازی وظایف با استفاده از یک لیست به اندازه H بهO(HlogH) کاهش مییابد و همه وظایف، فقط یک بار در لیست مرتب شده صف بندی و برداشته میشوند. نقطه‌ضعف احتمالی، استفاده از اندازه ثابت برای لیست مرتب شده است که این امکان وجود دارد وظیفه با بالاترین اولویت در لیست مرتب شده قرار نگیرد، اما به طور موقت در لیست FIFO ذخیره میشود؛ بنابراین اندازه لیست مرتب شده باید به اندازه کافی بزرگ باشد که عملکرد الگوریتم بیشتر شود. در همان زمان، پیچیدگیزمانی آن نباید بیش ازحد زیاد باشد. آزمایشهای نویسنده نشان میدهد که یک لیست اولویت به اندازه p (تعداد پردازنده‌ها) یک انتخاب خوب برای الگوریتم FCP است. اندازههای کوچک‌تر با مشکلات موازیسازی محدود، درحالی‌که اندازه بیشتر، به معنای بهبود عملکرد بیشتر نیست REF Radulescu \h \* MERGEFORMAT [54]. الگوریتم زمانبند کلی تطبیقی (AGS) در الگوریتم زمانبند تطبیقی ​​کلی (AGS) یکی از کلاس‌های مهم، ذخیره فایل است که به عنوان یک بردار زمان گپ پیادهسازی شده است؛ بنابراین، برای دسترسی کامل راه‌اندازی شده، در مورد تمام گرههای محاسباتی برای زمانبندی وظایف موجود میباشد. اگر برخی از گره برای دوره معینی از زمان ذخیره‌شده باشند یا با صاحب منابع یا با وظایف دیگر که به گرههای محاسباتی اختصاص داده شده بود، بردار زمان گپ، زودتر از یک چرخه زمانبندی، شامل اطلاعات است. اول، برای هر وظیفه، زمان شروع توسط زمان پایان آخرین فرآیند والد تعیین میشود. در گام بعدی، گره محاسباتی که در آن آخرین والد پردازش شد، مشخص میشود. تأخیر انتقال دادهها از والدهای دیگر به گره محاسبه‌شده و زمان شروع به‌روز میگردد. اگر گرهای از زمان شروع به‌روز شده وظیفه تا پایان زمان پردازش وظیفه، در دسترس بود، وظیفه به گره اختصاص داده میشود. در غیر این صورت برای هر گره زمان شروع پس از ارزیابی تأخیر از تمام فرآیندهای والد محاسبه میگردد. با استفاده از زمان آغاز به‌روز شده، زمان پایان این فرآیند را برای گره یافت میشود. از همه گرههای در دسترس، وظیفه، به گره محاسباتی که زمان پایان نزدیکتری دارد نگاشت داده میشود. پس از نگاشت، بردار زمان گپ، به‌روز میگردد REF Aggarwal \h \* MERGEFORMAT [55]. مکانیزم نگاشت جریان کار(WMM) هدف اصلی مکانیزم نگاشت جریان کار(WMM) ، پیدا کردن انتخاب بهینه با توجه به معیارهای کیفیت سرویس درخواست شده توسط کاربر و ارائه توسط ارائه‌دهندگان خدمات است. مراحل اصلی الگوریتم به طور خلاصه در زیر بیان شده است: محاسبه مقادیر کمکی برای تکمیل الگوریتم، تعریف معیارهایی که سطح QOS ارائه‌شده توسط موارد خدمات را تعریف میکنند. نگاشت جریان کار با نمونه سرویس، متناسب با نیاز کاربر به منظور دسترس‌پذیری، بدون نقض محدودیت هزینه مقداردهی اولیه میکند. نمونه خدمات (کاندید) را برای هر نوع خدمات تعریف میکند. دلیل این کار در این مرحله این است که برای ارائه سطح بالاتری از کیفیت سرویس کاندیدها را برای هر نوع خدمات در یک جریان کار کشف کند. در جهت پیدا کردن جایگزین‌های ممکن یک لیست با »بهترین کاندیدها «برای هر نوع خدمات ایجاد میکند. یک طرح که اجازه می‌دهد بیشتر از یک سرویس نمونه در هر نوع خدمات انتخاب شود و کاربر با محدودیت زمانی مواجه نشود، زمانبندی میکند REF Kyriazis \h \* MERGEFORMAT [56]. الگوریتم انشعاب جریان کار تطبیقی (AWS) در الگوریتم تقسیم جریان کار تطبیقی(AWS)، هنگامی که یک زمانبند یک وظیفه را دریافت میکند، برای گراف DAG وظایف، نسبت محاسبه به ارتباطات (CCR) و تعداد خوشههای منبع (به عنوان مثال N) را محاسبه میکند. مقدار CCR بالا به این معنی است که گراف وظیفه فشرده محاسباتی است. سپس، زمانبند N خوشه منبع که دارای بالاترین رتبه با توجه به دانش خود است را انتخاب میکند. یک گراف تکرار پارتیشن هر گره باقی‌مانده در G را برای تعیین اینکه آیا گره را می‌توان به یک زیر گراف G 'قرار داد بررسی میکند. آن به دنبال یالی با بزرگ‌ترین ارتباطات که دو گره متصل به آن هنوز بررسی نشده است، میگردد. در صورتی که چنین یالی وجود نداشت، این بدان معنی است که تمامی گرههای بررسی نشده در حال حاضر از G 'و یکدیگر جداشده و این وظایف در صورت امکان با زیر گراف ادغام خواهند شد. در غیر این صورت، اگر این یال بتواند باG' ادغام شود، پیمایش اولین عمق گراف از دو راس این یال به ادغام گرههای وظایف بیشتر شروع خواهد شد. هدف از پیمایش گراف، در صورت ممکن وظایف بدون نقض محدودیت آستانه منابع به زیر گراف ادغام شوند و در همان زمان، برای جلوگیری از شکستن غیرضروری، ترتیب اولویت در میان وظایف حفظ میکند که میتواند موازیسازی را افزایش ندهد، اما ممکن است هزینه ارتباط بین خوشهای را افزایش دهد. یک پشته برای دست‌کاری گره وظیفه در پیمایش استفاده میشود. اگر این یال تحت محدودیت نتواند در G ' ادغام شود، گره مسئول مشخص خواهد شد. این به معنی ایجاد یک زیر گراف جدید میباشد. زمانبند تا زمانی که همه گرهها درG به خوشه منبع اختصاص داده شوند این حلقه را تکرار میکند. بعد از اتمام الگوریتم، زمانبند هر زیر گراف را به خوشه منبع تعیین‌شده خود توزیع خواهد کرد REF Dong \h \* MERGEFORMAT [57]. رویکرد سود و زیان رویکرد سود و زیان، مکرراً زمانبندی را که توسط یک زمان اکتشافی بهینه یا اکتشافی بهینه‌شده از نظر هزینه تولیدشده را برای مقابله با محدودیتهای بودجه تنظیم میکند. زمانبندی با انتساب اولیه وظایف بر روی ماشینها شروع میشود و تغییر هر وظیفه به یک ماشین متفاوت را بر اساس مقدار وزن مرتبط با آن تغییر خاص محاسبه میکند. این مقادیر وزنها، جدولبندی میشوند، بنابراین، یک جدول وزن برای هر وظیفه در DAG و هر ماشین ایجاد میشود. دو روش جایگزین برای محاسبه مقادیر وزن، با توجه به دو انتخاب برای انتساب اولیه، پیشنهاد شده است: یا داشتن زمان تکمیل بهینه و یا هزینه بهینه. با استفاده از جدول وزن، وظایف بارها و بارها برای انتقال به یک ماشین، (در مورد زیان) تا زمانی که هزینه زمانبندی فعلی بیش از بودجه باشد و یا (در مورد سود) تا زمانی که همه انتقالات ممکن از بودجه تجاوز کند، در نظر گرفته میشوند. در هر صورت، الگوریتم تلاش می‌کند تا انتقال هر جفت از وظایف تنها یک بار اتفاق بیفتد و زمانی که هیچ انتقالی نبود، الگوریتم خاتمه خواهد یافت REF Sakellariou \h \* MERGEFORMAT [58]. الگوریتم بهینه‌سازی اجتماع ذرات (PSO) الگوریتم بهینه‌سازی اجتماع ذرات برای زمانبندی برنامه کاربردی به منابع محاسباتی ارائه‌شده که هم هزینه انتقال داده و هم هزینه محاسبه را در نظر میگیرد، این الگوریتم برای برنامههای کاربردی جریان کاری از طریق متفاوت کردن هزینههای ارتباطی و محاسباتی مورد استفاده قرار میگیرد REF Bala \h \* MERGEFORMAT [59]. در این الگوریتم هدف حداقل کردن زمان اجرا و بهبود جریان کاری است، نتایج آزمایش‌ها نشان میدهد که نگاشت وظیفه به منبع براساس این الگوریتم در هزینه صرفهجویی میکند و علاوه بر این تعادل خوبی از بار کاری روی منابع محاسباتی را از طریق توزیع وظایف به منابع در دسترس فراهم میکند. الگوریتم بهینهسازی کلونی مورچگان(ACO) الگوریتم اکتشافی جامعه مورچگان از رفتار اجتماعی مورچهها الهام گرفته است. مورچهها با اینکه نابینا هستند ولی میتوانند کوتاهترین مسیر بین لانه و منبع غذایشان را پیدا کنند. مورچهها مسیر بین غذا و لانه خود را در ابتدا به صورت کاملاً تصادفی انتخاب میکنند و کم‌کم پس از طی چندین دوره رفت و برگشت بین غذا و لانه و افزایش اثر به جای مانده در مسیر کوتاهتر، در نهایت همگی در کوتاهترین مسیر حرکت میکنند. وقتی مورچهای دنبال غذا میگردد، در طول مسیر حرکت، ماده شیمیایی به نام فرومون از خود بر جای میگذارند REF Marco \h \* MERGEFORMAT [60]. با استفاده از این فرومون، کوتاهترین مسیر پیدا میشود. از این مفهوم برای تخصیص کارها استفاده میشود. زمانی که یک منبع به کاری تخصیص و کامل میکند مقدار فرومون آن افزایش مییابد. اگر منبعی نتواند کاری را تمام کند برای مجازات از فرومون آن کاسته میشود REF Yousef \h \* MERGEFORMAT [61]. مقایسه الگوریتمهای اکتشافی به منظور شناخت بیشتر الگوریتمهای اکتشافی در جدول 4-1 به مقایسه این الگوریتمها میپردازیم. در این جدول، m به معنای تعداد پردازندهها و T تعداد وظایف میباشد. جدول 4- SEQ جدول_4- \* ARABIC 1 مقایسه الگوریتمهای زمانبندی الگوریتمهاهدف و خصوصیاتپیچیدگی زمانیمزایامعایبالگوریتم توازن بار فرصت‌طلبانه - ارسال وظیفه به پردازنده با کمترین بارهدف: اشغال نگه‌داشتن گرهها تا حد ممکن یا به عبارتی توازن بار بین منابعO(m)- سادگی - حداکثر استفاده از منابع- توازن بار - در نظر نگرفتن زمان اجرای وظایف- زمان تکمیل کار بالاالگوریتم حداقل زمان اجرا- اختصاص وظیفه به ماشینی با کمترین زمان اجراO(m)-- عدم توجه به در دسترس بودن منابع و بار پردازندهها- عدم توازن بار- زمان تکمیل بالا در محیط سازگارالگوریتم حداقل زمان تکمیل- ارسال وظیفه به ماشین با کمترین زمان تکمیل- ترکیب دو روش OLB و METهدف: به هر وظیفه بهترین ماشین داده شودO(m)- سعی در ایجاد توازن- زمان تکمیل کار پایین- انتساب وظایف به پردازندهای که زمان اجرای نامناسبالگوریتم بهترین درصد K-- در نظر گرفتن مجموعهای از پردازندهها برای تخصیص- تخصیص کار به پردازندهای با کمترین زمان تکمیلO(mlogm)- بهترین زمان تکمیل در مقایسه با الگوریتمهای بالا- انتخاب نکردن صحیح مقدار k در نتیجه کار تأثیر میگذاردالگوریتم Min-Min- دارای دو فاز کمینه یابی زمان تکمیل- مانند روش MCT مبنی بر حداقل زمان تکمیل هدف: کاهش زمان تکمیل وظایف با اختصاص زودهنگام وظایف کوچک به منابعO(T2×m)- زمان تکمیل نسبتاً مناسب- نتیجه نامناسب در صورت وجود کارهای بلند در میان کارهای کوتاهالگوریتم Min-Maxدارای دو فاز: فاز اول بیشینه یابی و فاز دوم کمینه یابی زمان تکمیلO(T2×m)- زوج ماشین/وظیفهای را که در فاز اول انتخاب میکند به ماشینی با زمان کمتر اختصاص یابدالگوریتم Max-Minدارای دو فاز: فاز اول کمینه یابی و فاز دوم بیشینه یابی زمان تکمیلO(T2×m)- خسارت ناشی از اجرای وظایف بلند را جبران میکندالگوریتم گرمایشی- استفاده از قیاس تعادل گرمایی برای نگاشت وظیفه به ماشین- استفاده از MET و MCTO(m)- زمان تکمیل تقریباً مشابه MCT و KPBالگوریتم حق رأی- اختصاص هر وظیفه بر اساس مقدار رأی- مقدار رأی: تفاوت بین دو مقدار کمینه زمان تکمیلO(T2×m)- توان عملیاتی بالا- سرعت تکمیل بالا- امکان وجود گرسنگیالگوریتم ژنتیک- تکنیکی برای جستجو در فضاهای حل بزرگ- دارای چهار مرحله: انتخاب، تولیدمثل، جهش و ارزیابی- ساده و سریع- روشی بهینه برای حل مسائل بهینه‌سازی نتیجهگیری در این قسمت به مقایسه الگوریتمهای ایستا و پویا در ماشینهای سازگار و ناسازگار میپردازیم. ماشین سازگار، ماشینی است که همه وظایفش را سریعتر از ماشین دیگر اجرا کند. با مقایسه الگوریتمهای اکتشافی در REF Braun \h \* MERGEFORMAT [41] از نظر زمان تکمیل کار، نتایج زیر به دست آمده است. در ماشینهای ناسازگار، الگوریتم GA بهترین نتیجه و این در حالی است که OLB بدترین نتیجه را میدهد. در ماشینهای سازگار نیز GA بهترین عملکرد و MET بدترین عملکرد را دارد. دلیل اینکه MET در محیط سازگار بدتر از OLB عمل میکند این است که در این محیط تخصیص کار به سریعترین پردازنده بدترین انتخاب است چرا که منجر به نگاشت تعداد زیادی کار به تعداد محدودی از پردازندهها میگردد. به طور کلی الگوریتمهای Min-Min و GA می‌توانند به عنوان استراتژیهای جستجوی امید بخشی با زمان تکمیل کار نسبتاً کم به‌کاربرده شوند. با توجه به نتایج آزمایش‌ها در REF Maheswaran \h \* MERGEFORMAT [42] برای مقایسه الگوریتمهای پویا و حالت بر خط از نظر زمان تکمیل کار، در هر دو محیط، الگوریتم KBT دارای بهترین عملکرد و OLB و MET ضعیفترین عملکردها را در مقابل بقیه داشتند. همچنین نتایج مقایسه برای الگوریتمهای دستهای، الگوریتم حق رأی نتیجه بهتری نسبت به دو الگوریتم دیگر دارد. به طور کلی، در بین الگوریتمهای پویا، الگوریتم حق رأی زمان تکمیل کار بهتری نسبت به دیگر الگوریتمها دارد. الگوریتمهای زمانبندی وظایف بلادرنگ گروهی از برنامههای کاربردی وجود دارند که زمان برای آنها اهمیت زیادی دارد. در مورد این برنامههای بحرانی که دارای مهلت زمانی هستند، وجود هر تأخیری باعث خرابی در کل سیستم میشود. برای مثال، مراکز کنترل ترافیک با استفاده از سنسورها، اطلاعاتی را درباره وضعیت اخیر جادهها جمع‌آوری کرده و در پایگاه داده ذخیره میکنند. اگر کاربری درخواستی در مورد وضعیت جادهها به مرکز داده بدهد، یک تصمیم بلادرنگ به کمک اپراتورها، اطلاعات کنترلی مناسب را به کاربر برمیگرداند؛ اما توافقنامه سطح سرویس جاری ابر، کنترل بلادرنگ تحت رفتار زمانی برنامهها را برای کاربران فراهم نمیکنند، بنابراین در آینده یک توافقنامه سرویس که شفافتر، انعطاف‌پذیرتر و قابل‌اطمینان تر باشد، مورد نیاز است. محدودیت زمانی از جمله در برنامههای بلادرنگ، نقش مهمی در محیط ابر ایفا میکند. با این وجود زمانبندهای موجود به دلیل توجه نکردن به فاکتور مهلت زمانی، برای کاربردهای بلادرنگ مناسب نیستند. یک زمانبند بلادرنگ باید علاوه بر بار سیستمها و زمان تکمیل به مهلت زمانی نیز توجه نماید. اولویت برای این‌گونه وظایف دورهای با مهلت زمانی به کار میرود. زمانبند وظایف را بر طبق سیاست اولویت به منابع میدهد. بر این اساس زمانبندی اولویت در دو گروه تقسیم‌بندی میشوند: استراتژی اولویت ایستا و استراتژی اولویت پویا. استراتژی اولویت ایستا یک وظیفه بلادرنگ، از مجموعهای از نمونهها تشکیل شده است. در زمانبندی اولویت ثابت، همه نمونههای یک وظیفه، اولویت یکسانی دارند. قدرتمندترین الگوریتم برای وظایف اولویت، الگوریتم میزانیکنواختی(RM) است. در این الگوریتم، اولویت یک وظیفه خاص به نرخ رهایی آن بستگی دارد. اگر آن نرخ بالا باشد، اولویت وظیفه هم بیشتر است REF Liu1 \h \* MERGEFORMAT [62]. در الگوریتم (RM) مهلت زمانی وظیفه دقیقاً برابر با دوره آن نبود. برای تخصیص اولویت بهینه نبوده و یک الگوریتم ضعیف محسوب میشد. از این رو الگوریتم یکنواختی مهلت زمانی(DM) به عنوان سیاست بهینه برای این سیستمها پیشنهاد شد. این الگوریتم به وظایف با مهلت زمانی کوتاهتر، اولویت بیشتری نسبت به مهلت زمانی طولانیتر، میدهد REF Leung \h \* MERGEFORMAT [63]. استراتژی اولویت پویا روش تخصیص اولویت پویا از رفتار ثابت، کارامدتر است زیرا این استراتژی میتواند از کل پردازنده برای پردازش وظیفه بهره ببرد. اولویت به طور پیوسته با زمان و از یک درخواست به درخواست دیگر یا در همان درخواست در حال تغییر است. بیشترین الگوریتمهای استفادهشده نزدیک‌ترین مهلتزمانی(EDF) و کمترین سستی(LLF) هستند REF Uthaisombut \h \* MERGEFORMAT [64]. الگوریتم نزدیک‌ترین مهلت زمانی، اولویت به وظایف به طور معکوس و متناسب با مهلت زمانی کارهای فعال میدهد. الگوریتم کمترین سستی، پردازنده را به وظیفه فعالی که کمترین سستی را دارا باشد میدهد و این سستی ممکن است چندین بار تغییر کند. زمانبندهای بلادرنگ یک زمانبند پویا تصمیم زمانبندی را در زمان اجرا اتخاذ میکند و ممکن است وظیفهای را خارج از مجموعه جاری وظایف آماده انتخاب کند. زمانبند ایستا تصمیمات زمانبندی را قبل از زمان اجرا میگیرد. به طور کلی زمانبندهای بلادرنگ به منظور رویکردهای زمان‌بندی‌شان در هستهها جای داده‌شده‌اند. هدف هسته MARS REF Hyman \h \* MERGEFORMAT [65] در سیستمهای بلادرنگ سخت رسیدن به شرایط باری بالاست. با رویکردهای زمانبندی ثابت سازگار شده است. زمانبندی کاملاً آفلاین محاسبه‌شده و به عنوان قسمتی از ورودی سیستم به گرهها داده می‌شود. همه ارتباطات زمانبندی و درخواستهای زمانبندی شامل این زمانبندی هستند. گرهها ممکن است به طور همزمان زمانبندی را با زمانبندی از قبل محاسبه‌شده تغییر دهند. هسته ART در فراهم کردن یک سیستم توزیعی قابل پیشبینی، قابل آنالیز و قابل‌اطمینان کمک میکند. این هسته از الگوریتمهای RM،EDF یا LLF برای آنالیز و تضمین فرآیندهای بلادرنگ سخت آفلاین استفاده میکند. فرآیندهای بلادرنگ سخت غیر دورهای با استفاده از زمان اجرای یک سرور قابل تأخیر زمانبندی میشوند. همه فرآیندهای دیگر با استفاده از مقدار عملکردی به صورت پویا زمانبندی میشوند REF Tokuda \h \* MERGEFORMAT [66]. با افزایش سرویسهای بلادرنگ، هستههای بلادرنگ به طور گسترده در محیط ابر مورد نیاز میشوند. با این وجود تعداد زیادی از هستهها قادر به تأمین رضایت سیستمهای بلادرنگ خصوصاً سیستمهای چند هسته‌ای نیستند. صرف‌نظر از پیکربندی هستهها، قرار دادن زمانبند بلادرنگ به عنوان یک افزونه در سیستم‌عامل یک راهحل محسوب میشود. یک مثال RESCH برای هسته لینوکس است REF Kato \h \* MERGEFORMAT [67]. وقتی زمانبندها قدم به محیط ابر گذاشتند، مجازی سازی یک ابزار قدرتمند شد، ماشینهای مجازی توانستند برنامههای بلادرنگ را زمانبندی نمایند، زیرا آنها به یک پلتفرم مستقل اجازه میدهند که نرمافزار را توسعه و انزوا را بین برنامهها فراهم کنند REF Rajkumar1 \h \* MERGEFORMAT [68]. فصل پنجم نتیجه‌گیری و کارهای آینده نتیجهگیری با توجه به توسعه فناوری اطلاعات و ارتباطات بحثهایی مانند کاهش هزینه، کارایی و افزایش سرعت باعث ایجاد تحولی روزافزون در دنیای اینترنت شده است. محاسبات ابری شیوهای از محاسبات کامپیوتری است که قابلیتهای مرتبط با فناوری اطلاعات را به عنوان سرویس، به کاربران عرضه میکند و به آنها این امکان را میدهد تا در بستر اینترنت، بدون داشتن اطلاعات تخصصی یا کنترل کردن زیرساخت، به این سرویسها دسترسی داشته باشند. این فناوری مزایای زیادی را فراهم کرده و مورد استقبال کاربران زیادی قرار گرفته است؛ اما با معایب و چالشهایی نیز روبرو است. یکی از این چالشها، بهرهوری منابع و واگذاری کارهاست که همان مسئله زمانبندی است. زمانبندی، به معنی واگذاری کارآمد و مناسب منابع به کارها است. هدف اصلی آن، کوتاه کردن زمان تکمیل کار، بالا بردن توان عملیاتی سیستم و ایجاد تعادل بار روی منابع است. این مسئله در ابر به دلیل مقیاس بزرگ منابع، پیچیدهتر هم میشود؛ بنابراین شناخت بهتر الگوریتمها میتواند در انتخاب الگوریتم مناسب کمک زیادی کند. در این گزارش در ابتدا به معرفی رایانش ابری و خصوصیات آن و سپس به بررسی مسائل مرتبط با زمانبندی و برخی از الگوریتمهای رایج در محیط ابر پرداختیم. کارهای آینده رایانش ابری شیوه جدیدی از ارائه خدمات را برای کاربران در سراسر دنیا فراهم آورده است. هر دستوری که از طرف کاربران به ارائه‌دهندگان خدمات فرستاده شود بخشی از منابع آنها را به خود اختصاص میدهد. مسئله زمانبندی امر مهمی است و رابطه مستقیمی با سود فراهم‌کنندگان و هزینه کاربران دارد. در زمانبندی، مسئله هزینه اعم از هزینه زمان اجرا، هزینه مهاجرت، هزینه ارتباطی و ... اهمیت زیادی دارد. انتخاب الگوریتم مناسب که بتواند باعث کاهش این هزینهها شود از جمله مواردی است که به آن توجه زیادی شده است. تحقیقات نشان میدهد استفاده از الگوریتمهای اکتشافی عملکرد بهتری نسبت به سایر الگوریتمها دارد. یکی از این الگوریتمها، PSO است و مشاهده‌شده که هزینه اجرای وظایف کم و وظایف برای اجرا به حداقل تعداد منابع نیاز دارند بنابراین بهرهوری منابع نیز بهتر میشود؛ اما استفاده به تنهایی این الگوریتم کافی نیست. با استفاده از الگوریتم ACO، نیز میتوان قابلیت اطمینان را تضمین و امنیت را بالا برد در ضمن زمان پاسخ و تا حدودی هزینهها را کاهش داد؛ بنابراین استفاده ترکیبی از این دو الگوریتم به همراه الگوریتم GA که سرعت نسبتاً مناسبی دارد، میتواند در طراحی یک الگوریتم موثر و کارآمد به منظور کاهش هزینه و قابلیت اطمینان در ابر مناسب باشد. منابع [ SEQ Ref \* MERGEFORMAT 1]. Choudhary M., Peddoju S.K., "A Dynamic Optimization Algorithm for Task Scheduling in Cloud Environment", International Journal of Engineering Research and Applications (IJERA), Vol. 2, Issue 3, pp. 2564–2568, (2012). [ SEQ Ref \* MERGEFORMAT 2]. Selvarani S, Sadhasivam G., "Improved Cost-based Algorithm for Task Scheduling in Cloud Computing", Computational Intelligence and Computing Research (ICCIC), IEEE International Conference on, pp. 1-5, (2010). [ SEQ Ref \* MERGEFORMAT 3]. Liu K, Jin H, Chen J, Liu X, Yuan D, Yang Y. ,"A Compromised-time-cost Scheduling Algorithm in Swindew-c for Instance-intensive Cost-constrained Workflows on a Cloud Computing Platform", International Journal of High Performance Computing Applications, pp. 445-456, (2010). [ SEQ Ref \* MERGEFORMAT 4]. Pandey S, Wu L, Guru SM, Buyya R. , "A Particle Swarm Optimization-based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments", Advanced Information Networking and Applications (AINA), 24th IEEE International Conference on, pp. 400-407, (2010). [ SEQ Ref \* MERGEFORMAT 5]. Varalakshmi P, Ramaswamy A, Balasubramanian A, Vijay Kumar P., "An Optimal Workflow Based Scheduling and Resource Allocation in Cloud", Advances in Computing and Communications, pp. 411-20, (2011). [ SEQ Ref \* MERGEFORMAT 6]. Bittencourt LF, Madeira E., "A Cost Optimization Algorithm for Workflow Scheduling in Hybrid Clouds", In Journal of Internet Services and Applications, pp. 207-227, (2011). [ SEQ Ref \* MERGEFORMAT 7]. Zomaya A., Teh Y-H., "Observations on Using Genetic Algorithms for Dynamic Load-balancing", IEEE Transactions on Parallel and Distributed Systems, pp. 899-912, (2001). [ SEQ Ref \* MERGEFORMAT 8]. Sandeep Tayal, "Tasks Scheduling Optimization for the Cloud Computing Systems", International Journal of Advanced Engg. Sciences and Technologies, Vol. 5, No. 2, pp. 111-115, (2011). [ SEQ Ref \* MERGEFORMAT 9]. Lizheng Guo, Shuguang, shigen, changyuan, "Task Scheduling Optimization in cloud Computing based on Heuristic Algorithm", Journal of Networks, Vol 7, (2012). [ SEQ Ref \* MERGEFORMAT 10]. Yajun Li, Yuhang Yang, Maode Ma, Liang Zhou, "A Hybrid Load Balancing Strategy of Sequential Tasks for Grid Computing Environments", Future Generation Computer systems, pp.819-828, (2009). [ SEQ Ref \* MERGEFORMAT 11]. Rajkumar B., Yeoa Ch., Venugopala S., "Market Oriented Cloud Computing: Vision, Hype, and Reality for Delivering IT Services as Computing Utilities", In High Performance Computing and Communications, 10th IEEE International Conference on, pp. 5-13, (2008). [ SEQ Ref \* MERGEFORMAT 12]. Vaquero L.M., Merino L. R., Caceres J., Lindner M., "A Break in the Clouds: Towards a Cloud Definition": ACM SIGCOMM Computer Communication Review Vol. 39, No. 1, (2009). [ SEQ Ref \* MERGEFORMAT 13]. Mell P., Grance T., "The NIST Definition of Cloud Computing": http://productionscale.com/blog/2011/8/7/the-nist-definition-of-cloud-computingdrft.html, [Accessed: 20-Dec-2013]. [ SEQ Ref \* MERGEFORMAT 14]. Blau B., Neumann D., Weinhardt C., Lamparter S., "Palnning and Pricing Service Mashups", In proceeding of 10th IEEE conference on E-Commerce Technology and 5th IEEE conference on Enterprise Computing , pp.19-26, (2008). [ SEQ Ref \* MERGEFORMAT 15]. Papazoglou M.P., van W.J., Heuvel Den, "Service Oriented Architectures: Approaches and Technologies and Research Issues", The VLDB Journal, Vol. 16, pp.389-415, (2007). [ SEQ Ref \* MERGEFORMAT 16]. Goyal A., Dadizadeh S., "A Survey on Cloud Computing", In University of British Columbia Technical Report for CS, Vol. 50,No.8, (2009). [ SEQ Ref \* MERGEFORMAT 17]. Reddy V.K., Reddy L.S.S., "Security Architecture of Cloud Computing", In International Journal of Engineering Science and Technology, Vol. 3, No. 9, ( 2011). [ SEQ Ref \* MERGEFORMAT 18]. Thirupathi Rao K., "High Level Architecture to Provide Cloud Services Using Green Datacenter", In Advances in Wireless and Mobile Communications (AWMC), Vol. 3 No. 2, pp. 109-119(2010). [ SEQ Ref \* MERGEFORMAT 19]. Krutz R.L., Vines D. R, "Cloud Security: A Comprehensive Guide to Secure Cloud Computing", Wiley Publishing, Inc., (2010). [ SEQ Ref \* MERGEFORMAT 20]. Google App Engine, http://appengine.google.com (2008). [ SEQ Ref \* MERGEFORMAT 21]. Mather T., Kumaraswamy S, Latif Sh., "Cloud Security and Privacy", O’Reilly Media, (2009). [ SEQ Ref \* MERGEFORMAT 22]. Venugopal S, Chu X, Buyya R, "A Negotiation Mechanism for Advance Resource Reservation Using the Alternate Offers Protocol", Proc. Of the 16th International Workshop on Quality of Service (IWQoS), IEEE Communications Society Press, pp. 40–49 (2008). [ SEQ Ref \* MERGEFORMAT 23]. Jensen M., Schwenk J., Gruschka N., Iacono L., "On Technical Security Issues in Cloud Computing", IEEE International Conference on Cloud Computing, (2009). [ SEQ Ref \* MERGEFORMAT 24]. Hawald S. C. , "Cloud Computing with Software as a Service (SaaS): How It Is Changing the Business and Organization Today", IT Today ,(2010). [ SEQ Ref \* MERGEFORMAT 25]. Ahronovitz M., et Al., "Cloud Computing Use Cases", A white paper produced by the Cloud Computing Use Case Discussion Group Version 4.0, (2010). [ SEQ Ref \* MERGEFORMAT 26]. Jadeja Y., Modi K, "Cloud Computing - Concepts, Architecture and Challenges", In Computing, Electronics and Electrical Technologies (ICCEET), International Conference on, pp. 877-880, (2012). [ SEQ Ref \* MERGEFORMAT 27]. Dillon T., Wu Ch., Chang E., "Cloud Computing: Issues and Challenges," In Advanced Information Networking and Applications (AINA), 24th IEEE International Conference on, pp. 27-33, (2010). [ SEQ Ref \* MERGEFORMAT 28]. Evers X.," A Literature Study on Scheduling in Distributed Systems", Delft University of Technology Department of Mathematics and Computing Operating Systems and Distributed Systems Group P.O. Box 356, 2600AJ Delft, The Netherlands, (1992). [ SEQ Ref \* MERGEFORMAT 29]. Hong S., Shi-ping Ch., Chen J., Kai G.," Research and Simulation of Task Scheduling Algorithm in Cloud Computing",In TELKOMNIKA, Vol.11, No.11, pp. 6664-6672, (2013). [ SEQ Ref \* MERGEFORMAT 30]. Abu-Rukba R.," Decentralized Resource Scheduling in Grid/Cloud Computing", The School of Graduate and Postdoctoral Studies The University of Western Ontario London, Ontario, Canada (2013). [ SEQ Ref \* MERGEFORMAT 31]. Casavant T.L., Kuhl J.G., "A Taxonomy of Scheduling in General-purpose Distributed Computing Systems", IEEE Trans. on Software Engineering, Vol. 14, No. 2, pp. 144-154, (1988). [ SEQ Ref \* MERGEFORMAT 32]. Chapin S.J., Katramatos D., Karpovich J., Grimshaw A.S., "The Legion Resource Management System", In Proc. of the 5th Workshop on Job Scheduling Strategies for Parallel Processing, in conjunction with the International Parallel and Distributed Processing Symposium, pp. 162-178, (1999). [ SEQ Ref \* MERGEFORMAT 33]. Bruckner P., Scheduling algorithms, 5th Edition, Springer, 2007. [ SEQ Ref \* MERGEFORMAT 34]. Blazewicz J., "Scheduling in Computer and Manufacturing Systems", Springer-Verlag NewYork. Secaucus, (1996). [ SEQ Ref \* MERGEFORMAT 35]. Du Y., Li X., "Application of Workflow Technology to Current Dispatching Order System", International Journal of Computer Science and Network Security, pp. 59-61, (2008). [ SEQ Ref \* MERGEFORMAT 36]. Yu J., Rajkumar B., "Taxonomy of scientific workflow systems for grid computing", Sigmod Record, pp. 34-44,(2005). [ SEQ Ref \* MERGEFORMAT 37]. Ullman JD., "NP-complete scheduling problems", In Journal of Computer and System sciences, pp. 384-393 ,(1975). [ SEQ Ref \* MERGEFORMAT 38]. Workflow Management Coalition, Workflow Management Coalition Terminology & Glossary, (1999). [ SEQ Ref \* MERGEFORMAT 39]. Freund R. F., Gherrity M., Ambrosius S., Campbell M., Halderman M., Hensgen D., Keith E., Kidd T., Kussow M., Lima J.D., Mirabile F., Moore L., Siegel H.J.,"Scheduling Resource in Multi-User, Heterogeneous, Computing Environment with SmartNet,"In Proceeding of the Seventh Heterogeneous Computing Workshop, pp. 3-19, (1998). [ SEQ Ref \* MERGEFORMAT 40]. Armstrong R., Hensgen D., T. Kidd, "The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions", In 7th IEEE Heterogeneous Computing Workshop, pp.79- 87, (1998). [ SEQ Ref \* MERGEFORMAT 41]. Braun T.D., Siegel H. J., Beck N., "A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems", In Journal of Parallel and Distributed Computing, Vol. 61, pp. 810-837, (2001). [ SEQ Ref \* MERGEFORMAT 42]. Maheswaran M., Ali S., Siegel H.J., Hensgen D.,Freund R, "Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems", In Proceedings of the 8th Heterogeneous Computing Workshop (HCW’99), ( 1999). [ SEQ Ref \* MERGEFORMAT 43]. Sivanandam S., Deepa N., "Introduction to Genetic Algorithms", Springer Publishing Company, Incorporated, (2007). [ SEQ Ref \* MERGEFORMAT 44]. Zomaya A. Y, Kazman R., "Simulated Annealing Techniques", In Algorithms and Theory of Computation Handbook (M. J. Atallah, Ed.), pp. 37-1-37-19, (1999). [ SEQ Ref \* MERGEFORMAT 45]. DeFalco I., DeBalio R., Tarantino E.,Vaccaro R.,"Improving Search by Incorporating Evolution Principles in Parallel Tabu Search", IEEE Conference on Evolutionary Computation,Vol. 2, pp. 823-828, (1994). [ SEQ Ref \* MERGEFORMAT 46]. Shoukat M., Maheswaran M., Siegel H., Hensgen D., Freund R., "Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems", Journal of Parallel and Distributed Computing, pp. 107–131, (1999). [ SEQ Ref \* MERGEFORMAT 47]. Chen R.M, Huang Y.M, "Multi Constraint Task Scheduling in Multi-processor Systems by Neural Networks", proceedings of the 10th IEEE Conference on Tools with artificial intelligence, pp. 288-294, (1998). [ SEQ Ref \* MERGEFORMAT 48]. Borthakur D., "The Hadoop Distributed File System: Architecture and Design", the Apache Software Foundation, (2007). [ SEQ Ref \* MERGEFORMAT 49]. Zaharia M., Konwinski A., Joseph A.D., Katz R. H., Stoica I., "Improving Mapreduce Performance in Heterogeneous Environments", In R. Draves and R. van Renesse, editors, Proceedings of Symposium on Operating Systems Design and Implementation, pp. 29–42, (2008). [ SEQ Ref \* MERGEFORMAT 50]. Zaharia M., Borthakur D., Sen Sarma J., Elmeleegy K., Shenker S., Stoica I., "Job Scheduling for Multi-user Mapreduce Clusters", Technical Report UCB/EECS, EECS Department, University of California, Berkeley, (2009). [ SEQ Ref \* MERGEFORMAT 51]. Zaharia M., Borthakur D., Sarma J., Elmeleegy K.,"Delay Scheduling:a Simple Technique for Achieving Locality and Fairness in Cluster Scheduling", In Proceedings of International Conference on EuroSys, pp. 265–278, (2010). [ SEQ Ref \* MERGEFORMAT 52]. Dryad, Web Published, Available online at: http://research.microsoft.com/en-us/projects/dryad/[Accessed 01/03/2013], (2011). [ SEQ Ref \* MERGEFORMAT 53]. Isard M., Prabhakaran V., Currey J., Wieder U., Talwar K., "Quincy: Fair Scheduling for Distributed Computing Clusters", In Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles, pp. 261–276, (2009). [ SEQ Ref \* MERGEFORMAT 54]. Radulescu A., van Gemund A. J. C., "On the Complexity of List Scheduling Algorithms for Distributed Memory Systems", Proc. of 13th International Conference on Supercomputing, pp. 68-75, (1999). [ SEQ Ref \* MERGEFORMAT 55]. Aggarwal A. K., Kent R.D., "An Adaptive Generalized Scheduler for Grid Applications", Proc. of the 19th Annual International Symposium on High Performance Computing Systems and Applications (HPCS’05), pp. 15-18, (2005). [ SEQ Ref \* MERGEFORMAT 56]. Kyriazis D., Tserpes K., Menychtas A., Litke A, Varvarigou T., ”An Innovative Workflow Mapping Mechanism for Grids in the Frame of Quality of Service", Future Generation Computation Systems, pp.498-511, (2008). [ SEQ Ref \* MERGEFORMAT 57]. Dong F., Akl S.G., "An Adaptive Double-layer Workflow Scheduling Approach for Grid Computing", Proc. of the 21st International Symposium on High Performance Computing Systems and Applications, pp. 7-13, ( 2007). [ SEQ Ref \* MERGEFORMAT 58]. Sakellariou R., Zhao H., Tsiakkouri E., Dikaiakos M.D., "Scheduling Workflows with Budget Constraints, CoreGRID Workshop on Integrated research in Grid Computing", Technical Report TR-05-22, University of Pisa, Dipartimento Di Informatica, Pisa, Italy, (2005). [ SEQ Ref \* MERGEFORMAT 59]. Bala A., Chana I., "A Survey of Various Workflow Scheduling Algorithms in Cloud Environment", Proc.of National Conference on Information and Communication Technology (NCICT), (2011). [ SEQ Ref \* MERGEFORMAT 60]. Marco D., Birattari M., Stutzle Th., "Ant Colony Optimization", Computational Intelligence Magazine IEEE 1.4, pp. 28-39, (2006). [ SEQ Ref \* MERGEFORMAT 61]. Yousef A., Abdullah A.H., Mohd nor S., Abdelziz A., "Scheduling Jobs on Grid Computing Using Firefly Algorithm", In Journal of Theoretical and Applied Information Technology, Vol. 33, No. 2, (2011). [ SEQ Ref \* MERGEFORMAT 62]. Liu C.L., Layland J.W., "Scheduling Algorithms for Multiprogramming in a Hard-real-time Environment", In Journal of the Association for Computing Machinery, pp. 46–61, (1973). [ SEQ Ref \* MERGEFORMAT 63]. Leung J.Y.T., Whitehead J., "On the Complexity of Fixed-priority Scheduling of Periodic, Real-time tasks", Performance Evaluation, pp. 237–250, (1982). [ SEQ Ref \* MERGEFORMAT 64]. Uthaisombut P., "Generalization of edf and llf: Identifying all Optimal Online Algorithms for Minimizing Maximum Lateness", Algorithmica, pp. 312–328, (2008). [ SEQ Ref \* MERGEFORMAT 65]. Hyman J.M., Lazar A.A., Pacifici G., "Real-time Scheduling with Quality of Service Constraints", IEEE Journal on Selected Areas in Communications, pp. 1052–1063, (1991). [ SEQ Ref \* MERGEFORMAT 66]. Tokuda H., Mercer C.W., "Arts: A Distributed Real-time Kernel", SIGOPS Operating Systems Review, pp. 29–53, (1989). [ SEQ Ref \* MERGEFORMAT 67]. Kato S., Rajkumar B., Ishikawa Y., "A Loadable Real-time Scheduler Suite for Multicore Platform", Technical Report 12, Carnegie Mellon University, Department of Electrical and Computer Engineering, (2009). [ SEQ Ref \* MERGEFORMAT 68]. Rajkumar B., S. Pandey, C. Vecchiola, "Cloudbus Toolkit for Market-oriented Cloud Computing", In Proceedings of the 1st International Conference on Cloud Computing, SpringerVerlag, pp. 24–44, (2009).