چکیده
امروزه محاسبات ابری شهرت زیادی پیداکرده و نمونه ای از محاسبات توزیع شده، متشکل از منابع و درخواست ها باهدف اشتراک گذاری منابع به صورت سرویس در بستر اینترنت است. این محیط تصوری از منابع بی نهایت را برای کاربران فراهم می کند؛ بنابراین کاربران می توانند مبنی بر تقاضا، میزان استفاده از منابعشان را افزایش یا کاهش دهند. به عبارتی محیط ابر، پرداخت به اندازه استفاده است. در ابر، فراهم کنندگان می خواهند بیش ترین بازده را از منابع خود ببرند و کاربران نیز می خواهند هزینه های خود را حداقل نمایند درعین حال، عملکرد مورد نیازشان را نیز به دست آورند. استفاده مناسب و بهینه از منابعی همچون حافظه، پردازشگر یک چالش است از این رو، چگونگی زمانبندی وظایف مسئله ای مهم محسوب می شود که تاثیر زیادی در عملکرد فراهم کنندگان سرویس ابر دارد. زمانبندی، انتخاب بهترین منبع مناسب باهدف انتشار بار در پردازنده ها و حداکثر بهره وری از منابع است. درحالی که باید زمان پاسخ و تکمیل هر وظیفه و همچنین هزینه سرویس را حداقل نماید. در این گزارش ابتدا به بیان مسئله و مشکل زمانبندی و ادبیات تحقیق اشاره می شود. سپس تعاریفی مرتبط با زمانبندی وظایف را مطرح کرده و ویژگی های یک زمانبند خوب را بیان می کنیم و در آخر به بررسی برخی از الگوریتم های موجود در ابر پرداخته و مقایسه ای از آن ها ارائه می شود.
کلمات کلیدی: محاسبات ابری، زمانبندی، زمانبندی در ابر، الگوریتم های زمانبندی
فهرست مطالب
عنوان شماره صفحه
تقدیم و تشکر …………………………………………………………………………………………………………….. ا
چکیده ……………………………………………………………………………………………………………………… ب
فهرست مطالب ………………………………………………………………………………………………………….. ج
فهرست اشکال …………………………………………………………………………………………………………… ز
فهرست جداول …………………………………………………………………………………………………………. ح
1- فصل اول: کلیات تحقیق
1-1 مقدمه …………………………………………………………1
1-2 بیان مسئله …………………………………………………………1
1-3 اهمیت و ضرورت تحقیق …………………………………………………………2
1-4 ادبیات تحقیق …………………………………………………………2
1-5 ساختار گزارش …………………………………………………………5
2- فصل دوم: مقدمه ای بر رایانش ابری
2-1 مقدمه ……………………………………………………… 7
2-2 تعریف رایانش ابری ……………………………………………………… 7
2-3 سیر تکامل محاسبات ……………………………………………………… 8
2-4 عناصر زیربنایی محاسبات ابری ………………………………………………………………………………………………… 9
2-4-1 محاسبات گرید …………………………………………………………………………………………………………………. 9
2-4-2 مجازی سازی …………………………………………………………………………………………………………………. 10
2-4-3 وب 2 ……………………………………………………………………………………………………………………………. 10
2-4-4 معماری مبتنی بر سرویس(SOA) ……………………………………………………………………………………….. 10
2-5 سرویس های محاسبات ابری ……………………………………………………………………………………………………. 11
2-5-1 نرم افزار به عنوان سرویس (SaaS) …………………………………………………………………………………….. 11
2-5-2 پلتفرم به عنوان سرویس (PaaS)………………………………………………………………………………………… 11
2-5-3 زیرساخت به عنوان سرویس (IaaS)…………………………………………………………………………………… 11
2-6 بررسی اجمالی از معماری ابر سطح بالا …………………………………………………………………………………… 11
2-6-1 لایه کاربر……………………………………………………………………………………………………………………….. 12
2-6-1-1 زیر لایه کاربردی………………………………………………………………………………………………… 12
2-6-1-2 زیر لایه محیط برنامه نویسی…………………………………………………………………………………….. 13
2-6-2 لایه مدیریت سیستم ابر …………………………………………………………………………………………………….. 13
2-6-2-1 ناظر SLA ………………………………………………………………………………………………………… 14
2-6-2-2 تامین منابع ………………………………………………………………………………………………………… 14
2-6-2-3 ترتیب دهنده و زمانبند …………………………………………………………………………………………… 14
2-6-2-4 توزیع کننده ………………………………………………………………………………………………………… 14
2-6-2-5 حسابداری …………………………………………………………………………………………………………. 14
2-6-2-6 اندازه گیری …………………………………………………………………………………………………………. 15
2-6-2-7 متعادل کننده بار …………………………………………………………………………………………………… 15
2-6-2-8 مدیریت سیاست ………………………………………………………………………………………………….. 15
2-6-2-9 ناظر ذخیره منابع پیشرفته ……………………………………………………………………………………….. 16
2-6-2-10 مدیریت امنیت و تشخیص منابع ……………………………………………………………………………. 16
2-6-2-11 مدیریت خودمختار ………………………………………………………………………………………….. 16
2-6-2-12 اقدامات سبز…………………………………………………………………………………………………….. 17
2-6-3 لایه ماشین مجازی …………………………………………………………………………………………………………… 17
2-6-3-1 ماشین های مجازی ……………………………………………………………………………………………….. 17
2-6-3-2 ناظر ماشین مجازی ………………………………………………………………………………………………. 17
2-6-4 لایه مرکز داده ………………………………………………………………………………………………………………… 18
2-6-4-1 سخت افزار ………………………………………………………………………………………………………… 18
2-7 مدلهای پیادهسازی محاسبات ابری …………………………………………………………………………………………. 18
2-7-1 ابر خصوصی…………………………………………………………………………………………………………………….. 18
2-7-2 ابر عمومی………………………………………………………………………………………………………………………. 19
2-7-3 ابر گروهی………………………………………………………………………………………………………………………. 19
2-7-4 ابر آمیخته……………………………………………………………………………………………………………………….. 19
3- فصل سوم: تعاریف مرتبط با زمانبندی وظایف
3-1 زمانبندی در سیستمهای توزیع شده…………………………………………………………………………………………….. 21
3-2 ویژگی های زمانبند وظایف………………………………………………………………………………………………………. 22
3-3 هدف زمانبندی وظایف……………………………………………………………………………………………………………. 23
3-3-1 تعادل بار ……………………………………………………………………………………………………………………….. 23
3-3-2 کیفیت خدمات ……………………………………………………………………………………………………………….. 23
3-3-3 اصول اقتصادی ……………………………………………………………………………………………………………… 23
3-3-4 بهترین زمان اجرا …………………………………………………………………………………………………………….. 24
3-3-5 توان عملیاتی سیستم ………………………………………………………………………………………………………… 24
3-4 ساختارهای زمانبندی……………………………………………………………………………………………………………….. 24
3-4-1 زمانبندی متمرکز ……………………………………………………………………………………………………………… 24
3-4-2 زمانبندی توزیع شده …………………………………………………………………………………………………………. 24
3-4-3 زمانبندی غیرمتمرکز ………………………………………………………………………………………………………… 25
3-5 طبقه بندی سلسله مراتبی…………………………………………………………………………………………………………… 25
3-5-1 زمانبندی محلی در برابر عمومی ……………………………………………………………………………………….. 26
3-5-2 زمانبندی ایستا در برابر پویا ……………………………………………………………………………………………… 26
3-5-3 بهینه در برابر غیر بهینه …………………………………………………………………………………………………… 27
3-5-4 توزیع شده در برابر غیر توزیعی ………………………………………………………………………………………… 27
3-5-5 تقریبی در برابر اکتشافی ………………………………………………………………………………………………….. 27
3-5-6 همکار در برابر غیر همکار ………………………………………………………………………………………………. 27
3-6 مقدمه ای بر جریان کار…………………………………………………………………………………………………………….. 28
3-6-1 تعریف جریان کار……………………………………………………………………………………………………………. 28
3-6-2 زمانبندی جریان کار…………………………………………………………………………………………………………. 28
3-6-3 معماری سیستم مدیریت جریان کار…………………………………………………………………………………….. 28
4- فصل چهارم: الگوریتم های زمانبندی
4-1 مقدمه ……………………………………………………………………………………………………………………………………. 31
4-2 مدلهای اکتشافی برای زمانبندی وظایف ………………………………………………………………………………… 31
4-2-1 استراتژیهای ایستا…………………………………………………………………………………………………………… 32
4-2-1-1 الگوریتم موازنه بار فرصت طلبانه (OLB)…………………………………………………………………. 32
4-2-1-2 الگوریتم زمان اجرا کمینه (MET)…………………………………………………………………………… 32
4-2-1-3 الگوریتم زمان اتمام کمینه (MCT) …………………………………………………………………………. 32
4-2-1-4 الگوریتم Min-Min …………………………………………………………………………………………….. 33
4-2-1-5 الگوریتم Min-Max ……………………………………………………………………………………………. 33
4-2-1-6 الگوریتم GA ……………………………………………………………………………………………………. 33
4-2-1-7 الگوریتم گرمایشی SA ………………………………………………………………………………………… 34
4-2-1-8 الگوریتم Tabu …………………………………………………………………………………………………. 34
4-2-1-9 الگوریتم A* ……………………………………………………………………………………………………. 35
4-2-2 استراتژیهای پویا ………………………………………………………………………………………………………….. 35
4-2-2-1 حالتOn-line ………………………………………………………………………………………………… 35
4-2-2-2 حالت Batch ……………………………………………………………………………………………………. 36
4-2-3 زمانبندهای اکتشافی ……………………………………………………………………………………………………….. 37
4-2-3-1 هادوپ …………………………………………………………………………………………………………. 37
4-2-3-2 درایَد …………………………………………………………………………………………………………… 39
4-2-4 الگوریتمهای زمانبندی جریان کار ……………………………………………………………………………………. 39
4-2-4-1 الگوریتم مسیر بحرانی سریع (FCP) ……………………………………………………………………… 40
4-2-4-2 الگوریتم زمانبند کلی تطبیقی (AGS)…………………………………………………………………….. 40
4-2-4-3 مکانیزم نگاشت جریان کار(WMM) …………………………………………………………………….. 41
4-2-4-4 الگوریتم انشعاب جریان کار تطبیقی (AWS)……………………………………………………………..41
4-2-4-5 رویکرد سود و زیان …………………………………………………………………………………………….42
4-2-5 الگوریتم بهینه سازی اجتماع ذرات(PSO) …………………………………………………………………………….. 43
4-2-6 الگوریتم بهینهسازی کلونی مورچگان(ACO) ………………………………………………………………………. 43
4-2-7 مقایسه الگوریتمهای اکتشافی …………………………………………………………………………………………….. 43
4-2-8 نتیجهگیری …………………………………………………………………………………………………………………….. 45
4-3 الگوریتمهای زمانبندی وظایف بلادرنگ ………………………………………………………………………………… 45
4-3-1 استراتژی اولویت ایستا……………………………………………………………………………………………………… 46
4-3-2 استراتژی اولویت پویا……………………………………………………………………………………………………… 46
4-3-3 زمانبندهای بلادرنگ………………………………………………………………………………………………………… 46
5- فصل پنجم: نتیجه گیری و کارهای آینده
5-1 نتیجهگیری ……………………………………………………………………………………………………………………………… 49
5-2 کارهای آینده …………………………………………………………………………………………………………………………. 49
منابع ………………………………………………………………………………………………………………………………………………….. 50
فهرست اشکال
عنوان شماره صفحه
شکل 2-1 تعریف NIST از محاسبات ابری …………………………………………………………………………………………………. 8
شکل 2-2 سیر تکامل محاسبات ………………………………………………………………………………………………………………… 9
شکل 2-3 معماری سطح بالای محاسبات ابری با مسائل امنیتی ……………………………………………………………………… 12
شکل 3-1 زمانبندی محلی و عمومی در یک سیستم توزیع شده …………………………………………………………………….. 21
شکل 3-2 طبقه بندی الگوریتم های زمانبندی ……………………………………………………………………………………………….. 25
شکل 3-3 مدل مرجع جریان کار ……………………………………………………………………………………………………………… 29
شکل 4-1 انواع الگوریتم های زمانبندی …………………………………………………………………………………………………….. 31
فهرست جداول
عنوان شماره صفحه
جدول 1-1 مقایسه پارامترهای مختلف در الگوریتم های زمانبندی …………………………………………………………………… 4
جدول 4-1 مقایسه الگوریتم های زمانبندی………………………………………………………………………………………………….. 43
فصل اول
کلیات تحقیق
1-1 مقدمه
با توجه به پیشرفت در عرصه رایانش، روش های بسیاری جهت توزیع منابع و استفاده از داده ها از قبیل خوشه بندی داده ها، رایانش گرید و سیستم مدیریت پایگاه داده های توزیع شده معرفی شده اند. رایانش ابری، بخش عظیمی از صنعت فناوری اطلاعات را دگرگون کرده و با ویژگی هایی که دارد شکل دیگری از خدمات را به کاربران ارائه کرده است. این فناوری یک مکانیزم در حال ظهور برای محاسبات سطح بالا تلقی می شود که در آن ابرها از کاربران خود بر مبنای میزان استفاده از منابع، هزینه دریافت کرده و منابع خود را در اختیار آنها قرار می دهند. این عمل شبیه پرداخت صورت حساب برق در هر ماه است که مشتریان به ازای برقی که مصرف می کنند هزینه پرداخت می کنند.
رایانش ابری، داده ها را به اشتراک گذاشته شده و سرویس ها را به صورت شفاف از طریق اینترنت ارائه می شوند. با افزایش تعداد کاربران ابر، وظایفی که باید زمانبندی شوند نیز افزایش می یابد. زمانبندی در ابر، یک مکانیزم است که وظایف کاربران را به منابع مناسب برای اجرا تخصیص میدهد و به طور مستقیم بر عملکرد ابر تاثیر میگذارد [1]..
1-2 بیان مسئله
ابر یک مدل محاسباتی است که نرم افزارها، میان افزارها و منابع محاسباتی مبتنی بر وب را هنگام تقاضای کاربران ارائه میکند. با پیشرفت فناوری، کاربران فقط به منابعی که برای انجام کارشان نیاز دارند دسترسی پیدا میکنند، بنابراین فقط به ازای منابعی که استفاده کردند هزینه پرداخت میکنند.
در محیط ابر، نیاز است منابع محاسباتی طوری زمانبندی شوند که هم ارائه دهندگان، حداکثر استفاده را از منابعشان ببرند و هم کاربران برنامه های کاربردی مورد نیاز خود را با کمترین هزینه در اختیار بگیرند. زمانبندی، یکی از مهم ترین مسائل در ابر محسوب میشود. محدودیت و موقتی بودن منابع دو شرطی هستند که به زمانبندی تحمیل شده اند. برای مثال ممکن است وظایف ترتیب اجرای مشخصی داشته باشند یا یک منبع در یک زمان فقط یک وظیفه را اجرا کند. اهمیت مشکل زمانبندی باعث شده که تحقیقات وسیعی در این زمینه انجام شود.
هنگامی که فراهم کننده منابع درخواستی را از کاربر دریافت میکند، برنامه کاربردی تصمیم به زمانبندی میگیرد. زمانبندکار مسئول تخصیص منابع به کارها است به طوری که از منابع محاسباتی به صورت کارآمد استفاده شود. برنامه کاربردی همچنین مطمئن میشود که به هر کار، یک مقدار مساوی از منابع داده شود. در محیط ناهمگون، یک تصمیم زمانبندی، پیچیدهتر نیز میشود.
1-3 اهمیت و ضرورت تحقیق
از آنجایی که منابع موجود در ابر در هر زمان در حال تغییر هستند مسئله زمانبندی وظایف امر مهمی است که تاثیر زیادی در عملکرد محیط محاسبات ابری دارد. الگوریتم زمانبندی روشی است که به وسیله آن وظایف به منابع موجود در مراکز داده تخصیص داده می شود. انتخاب یک زمانبندی نامناسب می تواند باعث ناکارآمدی سخت افزار یا کند شدن برنامه ابر شود. در مواردی انتخاب نادرست الگوریتم باعث می شود مسئله ای که چند ثانیه زمان می برد در چندین ساعت حل شود؛ بنابراین یک زمانبند خوب باید در شرایط مختلف رفتار مناسبی داشته باشد. کارآمدی یک الگوریتم را توسط مقدار زمانی که برای اجرای آن لازم است ارزیابی می کنند. در این تحقیق به بررسی برخی از الگوریتم های موجود در ابر می پردازیم تا با شناخت بهتر آن ها بتوانیم الگوریتمی کارا برای محیط ابر طراحی کنیم.
1-4 ادبیات تحقیق
انواع متنوعی از الگوریتمهای زمانبندی در سیستمهای توزیع شده وجود دارد. هدف اصلی الگوریتمهای زمانبندی به دست آوردن عملکرد محاسباتی بالا و بهترین توان عملیاتی سیستم است. الگوریتم های زمانبندی کار سنتی قادر به فراهم کردن زمانبندی در محیط ابر نیستند زیرا سربار هزینه دارند و فراهمکنندگان به سمت استفاده از الگوریتمهای اکتشافی یا ترکیبی میروند. در این قسمت به بررسی چندین الگوریتم زمانبندی میپردازیم. در ضمن در جدول 1-1 نیز به مقایسه آنها پرداخته خواهد شد.
در [2] یک الگوریتم بهبودیافته مبتنی بر هزینه برای زمانبندی وظیفه ارائه شده است. این الگوریتم به منظور نگاشت کارآمد وظایف به منابع موجود در ابر مطرح شده است. دو فاز اصلی در این الگوریتم شامل استفاده از الگوریتم لانه زنبور1 بهبودیافته برای اختصاص اولویت به وظایف و سپس از الگوریتمی به منظور گروه بندی وظایف بر اساس اولویت آنها می باشد. این الگوریتم زمانبندی، هزینه صرف شده بابت در اختیار گرفتن منابع و کارایی محاسبات انجام شده برای اتمام وظایف جریان کار را محاسبه می نماید. در این الگوریتم نسبت هزینه صرف شده برای در اختیار گرفتن منابع به هزینه ارتباط کارآمد برای انجام وظایف جریان کار، بهبود قابل توجهی داشته است.
در [3] الگوریتم توازی زمان- هزینه ارائه شده که عملکرد آن با در نظر گرفتن ویژگی های محاسبات ابری می باشد. به عنوان مثال، فشرده سازی جریان کار به منظور کاهش زمان اجرا و هزینه بر اساس اطلاعات ورودی کاربر که کاربر در هر زمانی وارد سیستم می کند، صورت می گیرد.
در [4] یک الگوریتم اکتشافی زمانبندی جریان کار، مبتنی بر بهینه سازی گروهی وظایف ارائه شده است. الگوریتم گروهی وظایف، از رفتار گروهی حیوانات، مانند حرکت دسته جمعی پرندگان و ماهی ها الهام گرفته شده است. به این جهت که این الگوریتم نیز با یک ماتریس جمعیت تصادفی اولیه، شروع می شود، عملکرد آن مشابه بسیاری دیگر از الگوریتم های تکاملی همچون الگوریتم ژنتیک پیوسته و الگوریتم های مبتنی بر رقابت می باشد اما برخلاف الگوریتم ژنتیک، الگوریتم گروهی وظایف هیچ عملگر تکاملی همانند جهش و تزویج ندارد. الگوریتم اکتشافی زمان بندی جریان کار، مبتنی بر بهینه سازی گروهی وظایف به منظور بهینه سازی گروهی وظایف، بر اساس رویکرد اکتشافی برنامه های کاربردی و با توجه به منابع موجود در ابر و با هدف کاهش زمان انجام محاسبات و کاهش زمان انتقال داده ها طراحی شده است. این الگوریتم از دو جزء اصلی که شامل استفاده از الگوریتم اکتشافی به منظور کشف صحیح منابع و سپس استفاده از الگوریتم بهینه سازی گروهی وظایف به منظور نگاشت صحیح این منابع به وظایف می باشد، تشکیل شده است. نتایج تجربی نشان می دهد که استفاده از این الگوریتم صرفه جویی در هزینه ها و توزیع متعادل حجم کار بر روی منابع را در برداشته است.
در [5] یک الگوریتم بهینه زمان بندی جریان کار ارائه شده است. این الگوریتم، به منظور زمانبندی جریان های کار در محیط ابر مطرح شده و ساختار کلی آن بر اساس یک درخت بیان می شود. این الگوریتم متشکل از دو فاز اصلی است که در فاز اول آن با استفاده از الگوریتم کشف منابع، تمامی منابع موجود برچسب خورده و سپس هر کدام از منابع، اطلاعات خود را به گره پدر خود که مستقیماً به آن متصل است ارسال می کند، بدین ترتیب کنترل منابع توسط هر گره پدر آسان تر خواهد شد، سپس در فاز دوم با توجه به فاکتور کیفیت سرویس2 (QOS) که توسط کاربر تعیین می شود، اختصاص منابع برای انجام وظایف جریان کار صورت می گیرد. به طور کلی این الگوریتم، راه حلی را به منظور زمانبندی جریان های کاری، با توجه به فاکتورهای QOS درخواستی کاربر ارائه می دهد. با استفاده از این الگوریتم، بهبود قابل توجهی در استفاده از CPU مشاهده شده است.
یک الگوریتم بهبود هزینه برای زمانبندی جریان کار در ابرهای ترکیبی در [6] ارائه شده و دارای دو مرحله اصلی الگوریتم، انتخاب وظایف و انتخاب منابع، از ابر عمومی و تشکیل ابر ترکیبی میباشند. درحالی که زمانبند تصمیم میگیرد که کدامیک از وظایف باعث کاهش زمان اجرا با استفاده از منابع ابر عمومی میشوند، تعیین کارایی و هزینههای اجرا، نقش عمدهای را در زمانبندی جدید ایفا می کنند.
در [7] یک استراتژی پویا توازن بار مبنی بر الگوریتم ژنتیک3 (GA) ارائه شده است. سرعت زمانبند افزایش و تغییر بین پردازندهها کاهش مییابد، وظایف برای اجرا انتخاب و در حالت پیشرفته خصوصیات وظایف شناخته میشود. آستانه سازگاری به توازن بار پویا پردازندهها کمک میکند.
در [8] الگوریتم بهینهسازی ژنتیک-فازی برای زمانبندی کار به منظور بهبود منابع در چارچوب هادوپ پیشنهاد شده است. در الگوریتم زمانبندی، تجدیدنظر شده و زمان اجرای وظایف را پیش بینی میکند تا توازن بار بهتری در میان گرهها در ابر داشته باشد، اما انتخاب بردار وظیفه تاثیر زیادی در کارآمدی پیش بینی دارد.
در [9] یک الگوریتم بهینهسازی اجتماع ذرات4(PSO)، برای زمانبندی وظایف در محیط ابر پیشنهادشده که زمان پردازش را حداقل میکند. این الگوریتم با مجموعه وظایف بزرگتر همگرایی سریعتری دارد. فقدان تنوع PSO در همگرایی نابجای آن نقش دارد؛ بنابراین از PSO ترکیبی با عملیات متفاوت برای جلوگیری از همگرایی نابجا در مشکل زمانبندی وظایف استفاده میشود. تمرکز این مقاله، بر حداقل سازی زمان تکمیل کارها و همچنین حداکثر استفاده منابع است.
در [10] یک الگوریتم که ترکیبی ازFCFS و GA ارائه شده است. تا بار وظایف ترتیبی در محیط گرید را متوازن کند و زمان اجرا را حداقل و حداکثر استفاده از منابع را داشته باشد. یک تکنیک ارائه شده که تفاوت بین ژنتیک و FCFS را برطرف و به تخصیص وظایف سریع نیز کمک میکند.
مدل
پارامترها
ابزار
کارایی
زمان اجرا
بهرهوری منابع
هزینه
Improved Cost-Based Algorithm for Task Scheduling
*
*
CloudSim
A Compromised-Time-Cost Scheduling Algorithm
*
*
SwinDeW-C
A Particle Swarm Optimization-based Heuristic for Scheduling Workflow Applications
*
*
Amazon EC2
An Optimal Workflow Based Scheduling and Resource Allocation in Cloud
*
Open Nebula
A Cost optimization algorithm for workflow Scheduling in Hybrid Clouds
*
*
*
GloBus
Observations on Using Genetic Algorithms for Dynamic Load-balancing
*
*
Java Environment
Tasks Scheduling Optimization for the Cloud Computing Systems
*
*
Amazon EC2
Task Scheduling Optimization in cloud Computing based on Heuristic Algorithm
*
*
*
Amazon EC2
A Hybrid Load balancing Strategy of Sequential Tasks for Grid Computing Environments
*
*
*
OmNet ++
جدول 1- 1 مقایسه پارامترهای مختلف در الگوریتمهای زمانبندی
1-5 ساختار گزارش
در این فصل به بیان مساله زمانبندی و ضرورت تحقیق پرداختیم. بقیه این گزارش به شرح زیر است:
در فصل دوم به مقدمهای از محاسبات ابری شامل تعریف، سیر تکامل محاسبات و عناصر زیربنایی محاسبات ابری میپردازیم. در ضمن سرویسهای متفاوت ابر از قبیل، نرم افزار به عنوان سرویس، پلتفرم به عنوان سرویس و زیرساخت به عنوان سرویس و مدلهای استقرار ابر را مورد بررسی قرار میدهیم. همچنین یک معماری سطح بالا از ابر نیز در این فصل ارائه می شود.
در فصل سوم تعاریف مرتبط با مشکل زمانبندی وظایف را شرح میدهیم. ویژگی های زمانبندی وظایف را بیان و هدف از زمانبندی را بررسی میکنیم. همچنین یک طبقه بندی سلسله مراتبی مرسوم شامل استراتژیهای ایستا، پویا را شرح می دهیم و تعاریفی در رابطه با زمانبندی جریان کار بیان میکنیم.
در فصل چهارم الگوریتم های زمانبندی وظایف مطرح میشود. به عنوان مثال الگوریتم های پویا و ایستا و همچنین الگوریتم های زمانبندی بلادرنگ را بیان میکنیم. در ضمن برخی از چارچوبها و زمانبندهای اکتشافی و مبتنی بر بلادرنگ را نیز شرح میدهیم. همچنین بین الگوریتمها مقایسه انجام و نتایج نیز شرح داده شده است.
در فصل پنجم نتیجه گیری و کارهای آینده ارائه خواهند شد.
فصل دوم
مقدمهای بر رایانش ابری
2-1 مقدمه
امروزه فناوری اطلاعات و اینترنت عنصر جدایی ناپذیر زندگی مردم شده است. با تغییر شیوه زندگی افراد جامعه نیازهای مانند امنیت اطلاعات، پردازش سریع، دسترسی فوری به اطلاعات و از همه مهمتر صرفه جویی در هزینهها نیز تغییر پیدا کرده است. به طبع با گسترش این نیازها سازمانها و افراد نیازهای کاملاً متفاوت در زمینه خدمات الکترونیکی با گذشته دارند. محاسبات ابری یک فناوری توسعهیافته است که صنایع IT را قادر میسازد هزینههای محاسباتی را کاهش دهند. کاربران ابر بر حسب تقاضا منابع را در اختیار میگیرند و به اندازهای که از سرویسها استفاده میکنند هزینه را پرداخت میپردازند؛ بنابراین محاسبات ابری یک نوع محاسبات سودمند شناخته میشود.
2-2 تعریف رایانش ابری
به دلیل آن که هنوز تعریف یکسانی از محاسبات ابری ارائه نشده در زیر به چند مورد اشاره می کنیم:
ابر از دید زیرساخت به نوعی از سیستمهای موازی و توزیعشده گفته میشود که شامل مجموعهای از کامپیوترهای مجازی به هم متصل شده است [11]. رایانش ابری به معنای استفاده اشتراکی از برنامهها و منابع میباشد. ابرها انبار بزرگی از منابع مجازی هستند که به راحتی قابل استفاده و در دسترساند (مانند سخت افزار، پلتفرمهای توسعه یافته و/یا سرویسها(. این منابع میتوانند به صورت پویا پیکربندی مجدد شوند تا یک بار متغیر (مقیاس) را تنظیم و همچنین بهره برداری مطلوبی از منابع را فراهم میکنند. این انبار منابع معمولاً به وسیله یک مدل پرداخت به اندازه هزینه که در آن حداقل تضمینهای دادرسی توسط ارائهدهنده زیرساخت بر اساس توافقات سطح سرویس بهره برداری میشود [12].
موسسه ملی فناوری و استانداردها5(NIST) نیز این گونه تعریف کرده است:
رایانش ابری مدلی است برای فراهم کردن دسترسی آسان بر اساس تقاضای کاربر از طریق شبکه به مجموعهای از منابع رایانشی قابل تغییر و پیکربندی (مثل شبکهها، سرورها، فضای ذخیره سازی، برنامه های کاربردی و سرویسها) که این دسترسی بتواند با کمترین نیاز به مدیریت منابع و یا نیاز به دخالت مستقیم فراهم کننده سرویس به سرعت فراهم شده یا آزاد گردد. بر اساس این تعریف پنج ویژگی ضروری شامل اشتراک منبع رایانش مجازی، دستیابی به شبکه گسترده، قابلیت انعطاف سریع، سلف سرویس درخواستی (بنا بر سفارش و تقاضا)، خدمات اندازهگیری شده را برای ابر در نظر گرفته است مدل ها و خصوصیات اساسی ابر در شکل 2-1 نشان داده شده است[13].
شکل2-1تعریف NIST از محاسبات ابری[13]
2-3 سیر تکامل محاسبات
برای شناخت بهتر رایانش ابری از دید زیرساخت، ابتدا نگاهی به سیر تکاملی سیستمهای محاسباتی از ابتدا تا کنون می اندازیم تا بتوانیم جایگاه آن را در بین دیگر سیستمها تشخیص دهیم. اگر کامپیوترهای مرکزی را به عنوان نسل اول سیستمهای محاسباتی در نظر بگیریم، ما با یک سیستم بسیار بزرگ مواجه بودیم که کاربران از طریق یک ترمینال واحد به آن دسترسی پیدا می کردند. به مرور این سیستمها کوچک تر شدند و با توان پردازشی بیشتری به صورت رایانههای شخصی در اختیار همه کاربران قرار گرفتند. سپس این امکان فراهم شد که با اتصال مجموعهای از این سیستمهای کوچک، شبکه ای با توان پردازشی بیشتر فراهم نمود تا پاسخگوی نیازهای پردازشی بیشتر و سنگینتر باشند؛ اما نیازهای پردازشی به شکل فزایندهای در حال افزایش بودند و نیاز به سیستمهای محاسباتی بزرگتر و قویتر احساس شد؛ بنابراین تعداد زیادی از این شبکه ها به صورت اختصاصی در سرتاسر اینترنت به هم متصل شدند و شبکه محاسبات توری را به وجود آوردند. در این بین مشاهده شد که میلیونها کاربر در اینترنت وجود دارند که در اکثر اوقات از تمام توان رایانه خود استفاده نمیکنند و سیستم محاسباتی دیگری شکل گرفت تا کاربرانی که تمایل داشته باشند، زمانهای بیکار سیستم خود را برای کارهای محاسباتی عام المنفعه هدیه کنند؛ بنابراین تعداد بسیار زیادی منبع محاسباتی کوچک در شبکه ای تحت عنوان محاسبات داوطلبانه به هم پیوستند و توان پردازشی عظیمی را به وجود آوردند؛ اما هنوز منابع بسیار زیاد دیگری در سازمان ها و مراکز داده اینترنتی وجود داشت که تمام ظرفیت آنها به طور کامل بکار گرفته نشده بود. این منابع نمی توانستند در شبکه محاسبات توری به صورت اختصاصی بکار گرفته شوند، زیرا برای آنها وظیفه دیگری تعریف شده بود. درعین حال امکان استفاده از آنها در شبکه داوطلبانه هم وجود نداشت، چون فلسفه وجودی آنها، کاربردهای تجاری بود. در شکل 2-2 روند تکامل محاسبات را مشاهده میکنید.
شکل 2-2 سیر تکامل محاسبات
به این ترتیب رویکرد جدیدی شکل گرفت که بتوان با استفاده از فناوری های مجازی سازی این منابع را به صورت قابل انعطاف و پویا برای کاربردهای مختلف مورد استفاده قرار داد و از تمام ظرفیت آ نها به طور موثر استفاده کرد. این فناوری رایانش ابری در لایه زیرساخت نام داشت که امکان استفاده از منابع محاسبات و ذخیره سازی را به صورت یک سرویس بر حسب نوع نیاز فراهم می آورد. در حقیقت با ایجاد یک لایه انتزاعی بر روی کلیه منابع فیزیکی خود به کمک مجازی سازی امکان مدیریت پویای منابع فیزیکی حاصل می شود.
رایانش ابری از دید زیرساخت، به گونهای سیستمهای توزیعشده و موازی اطلاق میگردد که مجموعهای از رایانه های مجازی را که به یکدیگر متصل هستند، شامل می شود. این رایانه ها به طور پویا عرضه شده و به عنوان یک یا چند منبع محاسباتی یکپارچه بر اساس توافقات سطح سرویس ارائه می شوند.
2-4 عناصر زیربنایی محاسبات ابری
2-4-1 محاسبات گرید
محاسبات گرید یک فناوری جدید است و شامل اصول، مفاهیم، تئوریها، روش ها و کاربردهای مختلف در زمینههای گوناگون است. یک شبکه از کلیه قابلیت های سخت افزاری و نرم افزاری موجود که به صورت یک سیستم جامع و کامل در خدمت موسسات تجاری و سازمان ها است تا بدین وسیله حداکثر استفاده را از این منابع ببرند.
گرید یک سیستم توزیعی و موازی است؛ که قابلیت اشتراکگذاری، انتخاب و اجماع منابع توزیع شده در گستره جغرافیا را به صورت پویا و در زمان اجرا بر اساس ویژگیهای منابع، مانند در دسترس بودن، قدرت محاسباتی، هزینه و کیفیت سرویس مورد نیاز کاربران، فراهم میآورد [11]. گرید دارای ابزارهای خاصی است که امکان حل مسائل پیچیده، در زمینه علم، مهندسی و تجارت را برای سازمانهای خاص فراهم میکند. حل مسائل علمی نیاز به حجم بالای محاسبات و پردازش دارند و منابعی در یک دامنه مدیریتی را میطلبد که گرید این توانایی را برآورده کرد.
2-4-2 مجازی سازی
فراهم کنندگان سرویس ابر به طور اساسی میلیونها کامپیوتر را که از مراکز داده با مقیاس بالا تشکیل شده اند را فراهم میکند. این قبیل مراکز داده به مشتریان زیادی با برنامه های کاربردی تفاوت سرویسدهی میکند. مجازی سازی میتواند برای این هدف در نظر گرفته شود. ایده مجازی سازی از سیستم عامل توزیع شده می آید اگرچه مجازی سازی سخت افزار اجازه میدهد چندین سیستم عامل ماشین مجازی را فراخوانی کند و پشته نرم افزار در یک پلتفرم فیزیکی منفرد قرار بگیرند [14].
2-4-3 وب 2
پدیدآورندگان این فناوری به دنبال نسل جدیدی از وب بودند که بتواند جذاب، کاربردی و قابل گسترش باشد. این از جمله عواملی بود که بحث های زیادی پیرامون این پدیده مطرح شود. وب 2 در نظر دارد اینترنت را به صورت پلتفرم درآورد. بدین معنی که هدف وب 2، بی نیاز کردن ما از سیستم عامل است، اگرچه این ادعایی بزرگ است اما وب 2 تا حد زیادی به این هدف دست یافته است. اینجا بود که مفهومی بنام سیستم عامل جهانی شکل گرفت. کاربران با داشتن یک مرورگر روی هر دستگاهی و با اتصال به اینترنت می توانند از کلیه سرویس های لازم جهت کارهای روزمره خود بهره گیرند. یکی از پیامدهای سیستم عامل جهانی، پایان چرخه ی سنتی تولید و عرضه نرم افزار است. می توان گفت اینترنت و به طور مشخص وب 2 مهم ترین عامل در شکل گیری پردازش ابری می باشد. وب 2 جزیی از پردازش ابری است.
2-4-4 معماری مبتنی بر سرویس6(SOA)
سبکی از معماری که از اتصال سست سرویسها جهت انعطاف پذیری و تعامل پذیری کسب وکار و به صورت مستقل از فناوری، پشتیبانی میکند و از ترکیب مجموعه سرویسهای مبتنی بر کسب وکار تشکیل شده که این سرویسها انعطاف پذیری و پیکربندی پویا را برای فر آیند ها محقق میکند [15]. به عبارتی معماری سرویس گرا برای پیاده سازی استانداردهای سرویس وب و یک مکانیزم تحویل سرویس به کار میرود.
2-5 سرویس های محاسبات ابری
مدلهای سرویس دهی یا اشکال ارائه خدمات رایانش ابری، در واقع نوعی منابع است که در این فناوری از طریق اینترنت در اختیار کاربران گذاشته میشود. تمام سرویس های ابری را میتوان بر اساس این منابع طبقه بندی کرد و معمولاً با لفظ "به عنوان سرویس" آورده شده و مورد استفاده قرار میگیرند.
سرویس های اصلی ابر شامل نرم افزار به عنوان سرویس7(SaaS)، پلتفرم به عنوان سرویس8(PaaS)، زیرساخت به عنوان سرویس9(IaaS) میباشند [16].
2-5-1 نرم افزار به عنوان سرویس (SaaS)
در این مدل نرم افزارهای کاربردی تجاری به عنوان سرویس به کاربران/مشتری عرضه می شود؛ زیرا مشتری بر حسب نیاز از اجزاء نرم افزاری فراهم کننده های متفاوت استفاده می کند؛ بنابراین هدف اصلی حفاظت از اطلاعاتی است که به وسیله این سرویس ها تشکیل شده اند. به عنوان مثال تعدادی از فراهم کنندگان نرم افزار به عنوان سرویس می توان به Google App, Salesforce نام برد.
2-5-2 پلتفرم به عنوان سرویس (PaaS)
در این مدل برنامه های کاربردی روی یک پلت فرم یا سیستم عامل توسعه داده می شوند؛ و به کاربر این امکان را می دهند که برنامه های خود را در ابر اجرا کنند.Microsoft Azure, Google AppEngine مثال هایی از فراهم کنندگان پلت فرم به عنوان سرویس هستند.
2-5-3 زیرساخت به عنوان سرویس (IaaS)
در این مدل سختافزار کامپیوتر مشابه سرورها، تکنولوژی شبکه، ذخیرهسازی و فضای مراکز داده به عنوان سرویس ارائه می شوند. برای مدیریت بهتر منابع می تواند شامل سیستم عامل و تکنولوژی مجازی سازی باشد. مثل Amazon S3, EC2 و Open Nebula [16].
2-6 بررسی اجمالی از معماری ابر سطح بالا
بر طبق شکل 2-3 یک معماری سطح بالا [18]، [17] از سرویس های محاسبات ابری همراه با مسائل امنیتی در لایه های مختلف مشاهده میکنید. در این قسمت ما جزئیات هر لایه و مسائل امنیتی هر کدام را شرح می دهیم.
شکل 2-3 معماری سطح بالای محاسبات ابری با مسائل امنیتی [17]
2-6-1 لایه کاربر
انواع مختلفی از کاربران مثل مشتریان، برنامه نویسان کاربردی و مدیرها از طریق لایه کاربر با نرم افزارهای ابر ارتباط برقرار می کنند. این لایه از دو زیر لایه تشکیل شده است.
2-6-1-1 زیر لایه کاربردی
برنامه های کاربردی ابر از طریق لایه کاربر برای کاربران نهایی ابر قابل مشاهده است. به طور معمول، برنامه های کاربردی از طریق پورتال وب توسط کاربران را دیده و تا در زمان مورد نیاز از آنها استفاده کنند. سربار تعمیر و نگهداری نرم افزار است که توسط این لایه فرعی و همچنین عملیات در حال انجام و هزینه های پشتیبانی انجام می شود. علاوه بر این، آن وظایف محاسباتی را از ترمینال کاربر به سرور در مراکز داده که در آن برنامه های کاربردی ابر مستقر هستند، انتقال میدهد. این به نوبه خود، سخت افزار مورد نیاز از دیدگاه کاربر را به حداقل می رساند و به آنها اجازه به دست آوردن عملکرد بیشتر می دهد. این رویکرد از پردازش موثر حجم کار در CPU های فشرده و حافظه فشرده کاربران بدون هیچگونه سرمایه گذاری عظیم در ماشین محلی خود، پشتیبانی میکند.
بنابراین این لایه فرعی حتی کار، درجه بندی کد و تست را ساده میکند. توسعه دهندگان میتوانند ویژگی های جدید را از طریق تکه ها به راحتی و بدون توزیع کاربران نهایی، به عنوان نرم افزار ابر در زیرساخت های محاسبات ارائه دهنده و نه در ماشین کاربر توسعه داده شود. از آنجایی که توسعه محیط باعث محدود شدن ارائه دهنده مرکز داده میشود، پیکربندی و تست برنامه با استفاده از قابلیت این زیر لایه، پیچیدگی کمتری دارد.
با وجود همه فواید و مزایای استفاده از قابلیت این زیر لایه، تعدادی از مسائل مربوط به توسعه به مانع برمیخورد. به طور خاص، دسترس پذیری و امنیت برنامه های کاربردی ابر دو چالش عمده ای هستند که تاثیر مستقیمی بر موافقت نامه سطح خدمات10 (SLAs) دارند [19].
2-6-1-2 زیر لایه محیط برنامه نویسی
کاربران این لایه، توسعه دهندگان کاربردی ابر هستند که مسئول توسعه و به کارگیری برنامه های کاربردی بر روی ابرمی باشند. ارائه دهندگان خدمات ابر از محیط توسعه با مجموعه ای لازم از تعریف رابط های برنامه کاربردی حمایت میکنند. توسعه دهندگان با محیط از طریق رابط های برنامه کاربردی موجود، ارتباط برقرار میکنند که با پشتیبانی از مقیاس پذیری توسعه و حمایت را شتاب میبخشند.
موتور App گوگل [20] یک مثال از این گروه است که از محیط زمان اجرا پایتون و رابط های برنامه کاربردی برای ارتباط برقرار کردن با محیط زمان اجرا ابر گوگل پشتیبانی میکند. از طریق این روش پیاده سازی، پراکنده شدن اتو ماتیک و تعادل بار برای توسعه دهندگان در توسعه برنامه های کاربردی شان در یک محیط برنامه نویسی آسان میشود.
2-6-2 لایه مدیریت سیستم ابر
این لایه مدیریت برنامه های کاربردی و زیرساخت های مجازی را برای راه حل های کسب وکار فراهم می کند. این لایه مسئول ارائه منابع مجازی برای سرویس های مانند مدیریت سطح سرویس، مدیریت سیاست های استفاده، مدیریت مجوز و بازیابی فاجعه است. این لایه پشتیبانی از پراکندگی برنامه های کاربردی از طریق تخصیص پویا منابع برنامه های کاربردی پشتیبانی میکند، در نتیجه تقاضا استفاده از منابع به حداقل میرسد. مولفه های کلیدی از لایه مدیریت خدمات ابر در زیر فهرست شده است.
2-6-2-1 ناظر SLA
هنگامی که یک مشتری برای اولین بار درخواست سرویس را میفرستد، درخواست توسط ناظرSLA به منظور بررسی نیازمندیهای کنترل کیفیت سرویسQOS))برای اینکه تعیین کند آیا درخواست قبول یا رد شود. آن همچنین مسئول نظارت بر پیشرفت میباشد. اگر هر گونه تخلف از SLA، توسط ناظر SLA مشاهده شود، آن فوراً برای اقدامات اصلاحی عمل میکند.
2-6-2-2 تامین منابع
دسترس پذیری ماشینهای مجازی11(VMs) و منابع مورد نیاز را از طریق این مکانیزم دنبال میشوند. آن درخواست های مختلفی که از سرورهای مجازی میآیند را با ایجاد نسخه های متعدد ازVM ها مدیریت میکند. تامین کننده منابع به صورت پویا تنظیم میشود به طوری که پردازش، حتی در اوج بار کامل میشود.
2-6-2-3 ترتیب دهنده و زمانبند
بر اساس اطلاعات ناظرSLA و تامین منابع، ترتیب دهنده کارها را بر اساس اهداف ارائه دهنده خدمات، مرتب یا اولویت بندی میکند. زمانبند با داشتن آخرین وضعیت اطلاعات تامین منابع، از جمله دسترس پذیری منابع و پردازش حجم کار، باعث ایجاد تخصیص منابع موثر میشود.
2-6-2-4 توزیع کننده
این ماژول وظیفه کنترل منابعی را دارد که توسط زمانبند انتخاب و به فرآیند اختصاص داده میشود. این شامل تغییر متن، تغییر کاربر، توزیع زمان تاخیر (به عنوان مثال زمان مورد نیاز پخش کننده برای توقف و شروع یک فرآیند). همچنین این مسئول شروع اجرای درخواست سرویس به ماشین های مجازی اختصاص داده شده می باشد.
2-6-2-5 حسابداری
آن سابقهای از منابع واقعی مورد استفاده توسط درخواست خدمات را نگهداری میکند تا به منظور محاسبه هزینه نهایی و هزینه کاربران از آن استفاده کند. علاوه بر این، تصمیم گیری در مورد تخصیص منابع می تواند با استفاده از اطلاعات تاریخی بهبودیافته شود.
2-6-2-6 اندازهگیری
حسابداری کاربران مبتنی بر استفاده از سیستم ها است. معمولاً، صدور صورت حساب مبتنی بر استفاده از CPU در ساعت و یا نرخ انتقال داده در هر ساعت است. این مکانیزم همچنین اطلاعاتی در مورد سیاست های قیمت گذاری و انواع خدمات به مشتری فراهم می کند. مشتری سطح و یا کیفیت خدمات مورد نیاز را انتخاب میکند، بدون نیاز به این که بداند چگونه فراهم کننده ابر، سرویس را تامین میکند.
2-6-2-7 متعادل کننده بار
این مکانیزم برای شناسایی ماشینهای مجازی بیکار و برای مهاجرت ماشین های مجازی به سایر گره های فیزیکی، شامل الگوریتمهایی برای نگاشت ماشینهای مجازی به ماشین های فیزیکی در یک محیط محاسبات ابری است. هر گاه یک کاربر حجم کاری را به سیستم ابرمی فرستد، می تواند یک ماشین مجازی جدید ایجاد میکند. در حال حاضر الگوریتم نگاشت متعادل کننده بار، یک طرح جایگزینی ماشین مجازی را تولید میکند، منابع لازم را به آن اختصاص و ماشین مجازی را به منابع فیزیکی شناخته شده توسعه میدهد. مدیریت نکردن و فراموشی ماشین های مجازی، میتواند منابع مرکز داده را مصرف و باعث اتلاف انرژی شود. الگوریتم دیگری از متعادل کننده بار، ماشینهای مجازی غیرفعال را شناسایی و آنها را خاموش میکند. روند بهینه قرار دادن ماشین مجازی در مقصد، ما نیاز به انتقال ماشین های مجازی موجود داریم. برای انجام این عملیات، الگوریتم مهاجرت ماشین مجازی از متعادل کننده بار فراخوانی می شود. به طور خلاصه متعادل کننده بار سه زیر ماژول های دارد که در زیر به آنها میپردازیم.
* مدیریت مهاجرت: این با توجه به اطلاعات ارائه شده توسط نگارنده VM، باعث مهاجرت زنده VM ها به سرور فیزیکی میشود. به نظر می رسد که سرور روشن یا خاموش است.
* ناظر سرویس: این ماژول پارامترهایی مانند وضعیت برنامه، حجم کار، استفاده از منابع، مصرف انرژی و غیره را جمع آوری میکند. این سرویس مانند ارائه کننده اطلاعات جهانی عمل نظارت دادهها را برای حمایت از اقدامات هوشمند گرفته شده توسط نگارنده VM فراهم میکند. اطلاعات وضعیت به توقف عدم مدیریت و فراموشی ماشین های مجازی کمک میکند.
* نگارنده ماشین مجازی: این الگوریتم به طور بهینه حجم کار ورودی (VMs)را به ماشینهای فیزیکی در دسترس مینگارد. این اطلاعات را از زمان نظارت بر سرویس جمع آوری و در مورد قرار دادن ماشین های مجازی تصمیم گیری میکند [18].
2-6-2-8 مدیریت سیاست
این برای سازمان الزامی است که تعریف روشن و بدون ابهامی از حکومت، سیاست (به عنوان مثال تنظیم کننده)، امنیت، حفظ حریم خصوصی [21] و غیره داشته باشد تا مطمئن شود که برنامه های کاربردی بر روی ابر اداره می شود نقیض SLAs نیست. به منظور مقابله با کسب وکار در درون یک ابر، مصرف کنندگان و ارائه دهندگان ابر، SLAs تضمین شده و مدل های قیمت گذاری معادل تراز وسط قرار دارد. مدیر سیاست در داخل و در سراسر مرزهای سازمان، سیستم عامل های IT و برنامه های کاربردی ثابت شده، مرسوم شده است. از این رو، در سطح جهان گسترش کسب وکار نیاز به استفاده از روش های جدید برای ترکیب و تکمیل سیاست در داخل و در سراسر شبکه خارجی و زنجیر تامین دارد.
2-6-2-9 ناظر ذخیره منابع پیشرفته
این مکانیزم برای تضمین کیفیت سرویس در دسترسی به منابع در سراسر مراکز داده است. ذخیره منابع پیشرفته، کاربران را قادر میسازد تا برنامه های کاربردی را با توجه به زمان، مانند برنامه های جریان کار موازی که بیدرنگ در آینده ای نزدیک نیاز به تعدادی از منابع به اجرا دارند، تکمیل کنند. پیش بینی تقاضا در آینده و استفاده میتواند توسـط ارائه دهنده دقیقتر انجام شود. با استفاده از ایـن اطلاعات، ارائه دهنده میتواند درآمد در زمان های مختلف را، با استفاده از سیاستهای مدیریت قیمت گذاری به حداکثر برساند. در [22] یک مکانیزم برای مذاکره ذخیره منابع پیشرفته با استفاده از جایگزین پروتکل فوق ارائه میدهد.
2-6-2-10 مدیریت امنیت و تشخیص منابع
محیط های ابر باید هویت و زیرساخت های امنیتی را به منظور تامین انعطاف و پیاده سازی سیاستهای امنیتی در سراسر ابرها کنترل کنند [23]. همچنین لازم است از اطلاعات حساس که در برابر SLAs محافظت شده، به عنوان تامین منابع خارج از مرزهای قانونی شرکت های ارائه دهنده ابر، کنترل و اطمینان حاصل شود. مسائلی که باید توسط ارائه دهنده ابر قبل از متقاعد کردن کاربران نهایی برای مهاجرت برنامه های کامپیوتری به برنامه های کاربردی ابر در نظر گرفته شود، ایمنی و امنیت اطلاعات محرمانه ذخیره شده بر روی ابراست. همچنین مسائل دیگری مانند احراز هویت و اعطای مجوز کاربر و عملکرد برنامه های کاربردی و در نهایت، تهیه نسخه پشتیبان از داده ها و بازیابی آنها برای ارائه SLAs قابل اعتماد برای خدمات ابر مورد نیاز است [24].
2-6-2-11 مدیریت خودمختار
هر عنصر در معماری سرویس ابری، شامل قابلیت مدیریت خودکار میشود. مدیران خودکار وظیفه انتساب کار به هر یک از منابع موجود، انتقال وظایف مبنی بر پیشرفت کلی درخواستهای انجام شده در طول اجرای حجم کار را بر عهده دارد. همچنین مدیران خودکار انطباقی، به منظور به حداقل رساندن زمان اجرای کل و بهینه سازی QOS، وظایف حجم کار را به سایتهای اجرایی اختصاص میدهند. سیستم خودمختار می تواند یک کار را برای اجرا در یک تاریخ و زمان خاص، به صورت پویا در حجم کار رویدادهای کسب وکار غیرمنتظره، در حجم کار از طریق یک سرویس وب، گرفتن هشدار موفقیت یا عدم موفقیت کامل شدن کار، تولید گزارش تاریخچه کار و غیره زمانبندی کند.
2-6-2-12 اقدامات سبز
رایانش سبز به اجرای سیاستها و روشهایی که از طریق استفاده بهتر از منابع محاسباتی، تاثیر زباله محاسبات بر محیط را کاهش میدهد، اشاره دارد. فناوری سبز عامل محرکی برای صنعت فناوری اطلاعات است و ناحیه مورد توجه در فناوری سبز، "مرکز داده" است. در این شرایط، رفتن به سمت فناوری سبز در مرکز داده، نه فقط یک مسئولیت اجتماعی است، بلکه یک ضرورت کسب وکار نیز محسوب میشود.
برای داشتن یک مرکز داده های سبز، استفاده از متعادل سازی قدرت، ظرفیت خنک کننده و زیرساختهای کارآمد مولفه های کلیدی میباشد. به منظور ایجاد یک مرکز داده های سبز، درک چگونگی استقرار این اجزا در یک مرکز داده به طور سنتی و دانستن اقدامات گرفته شده برای ایجاد مرکز داده سبز مهم است.
2-6-3 لایه ماشین مجازی
2-6-3-1 ماشین های مجازی
ماشین مجازی یک واحد از منابع محاسبات است. کاربران ابری در صورت دسترسی به ماشین های مجازی خود، عملکرد و بهرهوری بیشتری خواهند. کاربران می توانند نرمافزار پشته ماشین های مجازی را سفارشی کنند. اغلب این خدمات به عنوان زیرساخت به عنوان سرویس (IaaS) نامیده می شود. مجازی سازی فناوری اولیه در محیط ابر است که به کاربران کمک میکند، بدون اینکه اخلالی در زیرساخت های فیزیکی مراکز داده ارائه دهندگان ایجاد کنند، با انعطاف پذیری فوق العاده ای به پیکربندی تنظیمات بپردازند.
2-6-3-2 ناظر ماشین مجازی12
این یک لایه انتزاعی سخت افزار است که به عنوان یک رابط بین ماشین های مجازی و سخت افزار عمل می کند. این لایه دسترسی به منابع را با تمام ماشینهای مجازی هماهنگ میکند.VMM سازمان را قادر می سازد که از طریق تثبیت منابع محاسباتی، کسب وکار را سرعت بدهند. نهایتاً در مدیریت نتایج پیچیدگی کمتری وجود دارد. بهبود بهره برداری از منابع و کاهش مصرف برق از جمله چالش های کلیدی برای موفقیت است.
2-6-4 لایه مرکز داده
مراکز داده، در معماری سرویس ابر پایین ترین لایه است. به طور معمول شرکتهای بزرگ کاربران این لایه هستند و سخت افزار مورد نیازش را از سخت افزار به عنوان سرویس13(HaaS) اجاره میکنند. ارائه دهنده سخت افزار به عنوان سرویس در طول مدت اجاره عملیات مدیریت، ارتقاء سختافزار مشتریان را بر عهده دارد. این به شرکتها کمک میکند که به سرمایه گذاری در ساخت و مدیریت مراکز داده اعتقاد پیدا کنند.
چالشهای تکنیکی که ارائه دهنده سخت افزار به عنوان سرویس باید در نظر بگیرد، کارایی، آسانی و سرعت تامین سیستمهای مقیاس بالا است. همچنین مدیریت مراکز داده، زمانبندی و بهینه سازی مصرف انرژی از دیگر چالشهایی است که در این لایه باید برآورده شود.
2-6-4-1 سخت افزار
منابع محاسباتی سخت افزارهایی اساسی مانند منابع CPU، منابع حافظه، دستگاههایI / O و سوئیچها که به صورت ستون فقرات از ابر هستند، ارائه میدهند [23].
2-7 مدلهای پیادهسازی محاسبات ابری
ابرها در زیرساختهای فیزیکی به کار میروند جایی که ابرهای میان افزار برای تحویل سرویس به مشتریان مورد استفاده قرار میگیرد. چنین زیرساختها و میان افزاری از لحاظ سرویس، حوزهی اجرایی و دستیابی به کاربران باهم متفاوت اند؛ بنابراین استقرار ابر به سه نوع تقسیمبندی میشود که عبارت اند از: ابر عمومی، ابر خصوصی و ابر آمیخته.
2-7-1 ابر خصوصی14
زیرساخت ابری تنها برای یک سازمان کار می کند و ممکن است توسط خود سازمان یا شرکتی دیگر مدیریت شود، نیز میتواند درون یا بیرون سازمان جای بگیرد. این نوع از ابر برای سازمانهای با وسعت بزرگ استفاده میشود و میتواند توسط یک سازمان ثالث مدیریت شود [25]. مزیت آن را مدیریت در نگهداری، امنیت، به روزرسانی بهتر و کنترل بیشتر در توسعه و کاربرد دانسته اند.
2-7-2 ابر عمومی15
ابر عمومی به کاربر این امکان را میدهد تا از طریق مرورگر اینترنتی به واسط کاربری دسترسی پیدا کند. کاربران مانند قبض برق، به ازای مدت زمان استفاده، هزینه را میپردازند. این امکان کمـک میکـند تا هزینههای عملیاتی IT کاهش یابد، با این وجود از لحاظ امنیتی ابرهای عمومی نسبت به سایر مدلها بیشتر در معرض حملات و سوءاستفاده هستند، یکی از راهکارهای جلوگیری از وقوع حوادث استفاده از کنترلهای امنیتی در هر دو طرف مشتری و فراهم آورنده ابر است. لازم به ذکر است که هر دو طرف نیاز به شناسایی حدود و اختیارات به همراه محدودیتهای عملیاتی خوددارند.
2-7-3 ابر گروهی16
ابر گروهی درجایی به وجود می آید که چندین سازمان نیازهای یکسان دارند و به دنبال این هستند که با به اشتراک گذاردن زیرساخت از مزایای رایانش ابری بهرهمند گردند. به دلیل اینکه هزینهها بین کاربران کمتری نسبت به ابرهای عمومی تقسیم می شود، این گزینه گرانتر از ابر عمومی است اما میزان بیشتری از محرمانگی، امنیت و سازگاری باسیاست ها را به همراه میآورد [26].
2-7-4 ابر آمیخته17
ترکیبی از ابر عمومی و خصوصی و گروهی است. در این مدل یک ابر خصوصی به یک یا چند سرویس ابر خارجی متصل میشود. سازمانها فعالیتهای اصلی که منجر به ایجاد مزیت رقابتی برای آن ها میشود را توسط ابر خصوصی انجام داده درحالی که فعالیتهای جانبی توسط سایر ابرها (عمومی یا گروهی) کامل میشوند [27].
فصل سوم
تعاریف مرتبط با زمانبندی وظایف
3-1 زمانبندی در سیستمهای توزیع شده
در یک سیستم توزیع شده ممکن است برخی از گره ها غیرفعال و یا به آرامی بارگذاری شوند و این در حالی است که گرههای دیگر به سختی بار میشوند. یک فرصت برای بهبود عملکرد یک سیستم توزیعی، اجرای از راه دور و مهاجرت وظایف از گرههای سنگین به بیکار و یا گره سبک است. این وظیفه زمانبند توزیعی است که با استفاده از روشهای بهینه، فرآیندها را به گرهها (پردازندهها) زمانبندی کند. اغلب یک تمایز ضمنی بین زمانبندی وظایف و تخصیص وجود دارد. اگرچه میتوان استدلال کرد که این دو کلمه جایگزین یک مشکل هستند. از دیدگاه منابع، مشکل این است که چگونه پردازنده ها را به فرآیندها تخصیص دهیم. از دیدگاه کاربر، مشکل این است که چگونه فرآیندها در پردازنده ها زمانبندی شوند.
زمانبندی در سیستمهای توزیع شده به طور عمده، پیچیده تر از سیستمهای تک پردازندهای است. سیاست زمانبندی توزیع شده برای یک سیستم همه منظوره را میتوان منطقاً به دو بخش تقسیم کرد: یک زمانبندی محلی که نشان میدهد، چگونه فرآیندهای موجود در یک گره، به منبع CPU اختصاص داده میشود، درحالی که یک سیاست توزیع عمومی (بار)، حجم کاری سیستم را در میان گره ها، از طریق انتقال فرآیند و/ یا جایگزینی اولیه گسترش میدهد. یک زمانبندی بار، فرآیندهای جدید را به گرهها تخصیص میدهد و ممکن است زمانی که فرآیندها سیستم را ترک میکنند، دوباره زمانبندی شود.
شکل 3-1 نشان میدهد که هر پردازنده دارای مجموعه فرآیندهای خود است و زمانبند محلی هر پردازنده، باتوجه به یک زمانبندی محلی تعیین میکند که کدامیک از فرآیندها، ممکن است اجرا شوند [28].
شکل3- 1 زمانبندی محلی و عمومی در یک سیستم توزیع شده [28]
3-2 ویژگی های زمانبند وظایف
در محیط محاسبات ابری، زمانبندی وظیفه و تخصیص منبع، توسط ارائه دهندگان خدمات از طریق فناوری مجازی مدیریت میشود. آنها برای مخفی و کامل کردن وظایف کاربران به صورت شفاف استفاده میشوند. زمانبندی وظیفه به دلیل شفافیت و انعطاف پذیری سیستم محاسبات ابری و نیازهای مختلف برای منابع، پیچیدهتر نیز میشود. استراتژیهای زمانبند وظیفه بر عدالت یا بهرهوری منابع تمرکز دارند که هزینه زمان، فضا و توان عملیاتی افزایش و کیفیت سرویس در محاسبات ابری بهبود خواهد داشت. ویژگیهای زمانبندی وظیفه در ابر محیط محاسبات به شرح زیر است [29]:
* زمانبندی وظیفه یک پلت فرم واحد و یکپارچه منابع تهیه میکند: ما فرض میکردیم که محاسبات ابری با استفاده از فناوری های مجازی، منابع فیزیکی (همه نوع میزبان، ایستگاه های کاری و یا حتی PC و غیره) را به عنوان یک استخر منابع واحد، محافظ ناهمگن و عرضه برای استفاده بالا قرار داده است. این در حالی است که به طور عمده در تعداد زیادی از رایانههای توزیع شده، پخش شده اند و منابع در قالب یک مرکز داده عرضه میشوند.
* زمانبندی وظیفه، عمومی و متمرکز شده است: محاسبات ابری یک مدل محاسباتی است که منابع متمرکز را توسط سرویس منعکسی، به چند برنامه توزیع شده تامین میکند و این به کارگیری معکوس میتواند روش های ناهمگن اجرای عملیاتی را سادهتر توسعه دهد؛ بنابراین، با فناوری مجازی سازی و خدمات معکوس، زمانبندی وظیفه محاسبات ابری، یک زمانبندی متمرکز جهانی به دست میآورد.
* هرگره در ابر مستقل است: در محیط محاسبات ابری، زمانبندی داخلی هر گره ابر مستقل است و زمانبندها در ابر هیچ دخالتی باسیاست زمانبندی گرههای دیگر نخواهند داشت.
* مقیاس پذیری زمانبندی وظیفه: مقیاس از تامین منابع ارائه دهنده ابر ممکن است در مراحل اولیه محدود باشد. علاوه بر این، انواع منابع محاسباتی و اندازه منابع مجازی انتزاعی ممکن است بزرگ شوند و تقاضای برنامه افزایش یابد. در ابر، زمانبندی وظیفه باید ویژگیهای مقیاس پذیری داشته باشد، به طوری که توان عملیاتی زمانبندی وظیفه در ابر، کم نشود.
* زمانبندی وظیفه می تواند به صورت پویای خود تطبیقی باشد: گسترش و کاهش برنامههای کاربردی در ابر ممکن است بسته به نیاز لازم باشد. منابع محاسباتی مجازی در سیستم ابر همچنین ممکن است در همان زمان گسترش یابند و یا کوچک شوند. منابع همواره در حال تغییرند، برخی منابع ممکن است خراب شوند، منابع جدیدی ممکن است به ابرها بپیوندند و یا راه اندازی مجدد شوند.
* مجموعه زمانبندی وظیفه: زمانبندی وظیفه به دو بخش تقسیم میشود: یک بخش به عنوان زمانبندی یک استخر منابع واحد مورد استفاده قرار میگیرد و در درجه اول مسئول زمانبندی برنامه های کاربردی و ابر API است و دیگری برای زمانبندی منابع پورت واحد در ابر، به عنوان مثال، زمانبندی وظیفه Map Reduce. با این حال، هر زمانبندی شامل دو فرآیند دو طرفه است: زمانبند منابع را از ابر اجاره و بعد از استفاده، منابع درخواست شده را بر میگرداند. فرایند اول استراتژی زمانبندی و دومی استراتژی بازگشت است، ترکیبی از زمانبندی و استراتژی بازگشت منابع، مجموعه زمانبندی وظیفه را تشکیل میدهند.
3-3 هدف زمانبندی وظایف
اهداف زمانبندی وظیفه محاسبات ابری، ارائه زمانبندی بهینه برای کاربران و در همان زمان، ارائه توان عملیاتی سیستم ابر و QOS است. اهداف خاص زمانبندی شامل: تعادل بار، کیفیت خدمات، اصول اقتصادی، بهترین زمان اجرا و توان عملیاتی سیستم میباشند.
3-3-1 تعادل بار
تعادل بار و زمانبندی وظیفه در محیط ابری ارتباط نزدیکی با یکدیگر دارند، مکانیزم زمانبندی وظیفه مسئول تطبیق بهینه وظایف و منابع است. از آنجا که وابستگی الگوریتم زمانبندی وظیفه، تعادل بار را به یکی دیگر از معیارهای مهم در ابر تبدیل میکند. از آنجا که سطح حالت متعادل کننده بار در زمانبندی وظیفه تحت محیط محاسبات ابری، دو نوع بارگذاری دارد: در مرحله اول بار ماشین مجازی است، دوم بار لایه منابع است.
3-3-2 کیفیت خدمات
ابر عمدتاً به کاربران، محاسبات و سرویس های ذخیره سازی ابر را ارائه میدهد، کاربران منابع را تقاضا و منابع توسط ارائه دهنده در قالب کیفیت خدمات عرضه میشوند. هنگامی که مدیریت زمانبندی وظیفه به سمت تخصیص وظیفه میرود، تضمین کیفیت سرویس منابع ضروری است.
3-3-3 اصول اقتصادی
منابع محاسبات ابری به طور گستردهای در سراسر جهان توزیع شده اند. این منابع ممکن است به سازمان های مختلف تعلق داشته باشند. آنها سیاستهای مدیریتی خودشان را دارند. به عنوان یک مدل کسب وکار، محاسبات ابری، با توجه به شرایط مختلف، خدمات مربوطه را ارائه میدهد؛ بنابراین تقاضای عوارض معقول است. اقتصاد بازار زمانبندی وظایف و مدیریت منابع هدایت میکند، ما باید مطمئن شوید به نفع هر دو (مصرف کننده و ارائه دهنده) باشد، به طوری که محاسبات ابری بتواند بیشتر و بیشتر به جلو حرکت کند.
3-3-4 بهترین زمان اجرا
در درجه اول برای برنامه های کاربردی، وظایف را می توان با توجه به نیازهای کاربران، به دسته های مختلف تقسیم و پس از آن بهترین زمان اجرا را، بر اساس اهداف مختلف برای هر وظیفه تنظیم کرد. آن QOS زمانبندی وظایف را به طور غیرمستقیم در محیط ابر بهبود خواهد بخشید.
3-3-5 توان عملیاتی سیستم
عمدتاً برای سیستم های محاسبات ابری، توان عملیاتی، اندازه گیری عملکرد بهینه زمانبندی وظیفه سیستم است و آن نیز یک هدف است که باید در توسعه مدل کسب وکار در نظر گرفته شود. افزایش توان عملیاتی برای کاربران و ارائه دهندگان ابر سودی برای هر دو آنها خواهد داشت [29].
3-4 ساختارهای زمانبندی
معماری زیرساخت های زمانبندی با توجه به مقیاس پذیری، استقلال و عملکرد سیستم بسیار مهم است. این را می توان به سه دسته تقسیم کرد: متمرکز، توزیع شده و غیرمتمرکز.
3-4-1 زمانبندی متمرکز
در یک معماری زمانبندی متمرکز، تصمیم گیری های زمانبندی توسط یک کنترل کننده مرکزی برای تمام وظایف گرفته میشوند. زمانبند تمام اطلاعات را در مورد وظایف را نگهداری و وضعیت همه منابع موجود در سیستم را دنبال میکند. سازمان زمانبندی متمرکز به سادگی قابل اجرا و توسعه است. با این حال، به دلیل ماهیت محیط محاسبات گرید/ ابر برای آنها کافی نیست.
3-4-2 زمانبندی توزیع شده
در زمانبندی توزیع شده، یک مدیر مرکزی و چند نهاد سطح پایین تر وجود دارد. این مدیر مرکزی مسئول اجرای کامل یک وظیفه و تخصیص وظایف منحصربه فرد به ارائه دهندگان سطح پایین است. هر یک از موجودیتهای سطح پایینتر زمانبند، مسئول نگاشت وظایف منحصربه فرد به منابع گرید/ ابر است. این رویکردها کفایت نمیکنند، از آنجا که موجودیتها برای توسعه به سیاستهای زمانبندی مدیر مرکزی نیاز دارند. شکست مدیر مرکزی باعث خرابی در کل سیستم میشود.
3-4-3 زمانبندی غیرمتمرکز
در مقابل، زمانبند غیرمتمرکز، محدودیتهای ساختارهای متمرکز یا توزیع شده را با توجه به تحمل خطا، مقیاس پذیری، استقلال و مهمتر از همه، کفایت برای محیط محاسبات گرید/ ابر نفی میکند. در یک روش زمانبندی غیرمتمرکز فرض میشود که هر یک از موجودیت ها مستقل هستند و تصمیم گیری زمانبندی از سیاست های خودش ناشی میشود. با این حال، تصمیم گیریهای مستقل، ممکن است بهینه سازی اهدافشان را به جای عملکرد سیستم به عنوان هدف کلی در نظر بگیرند. این مواقع، از مدل ها و تکنیک هایی استفاده میکنند که کنترل واحدهای خود را داشته باشند و به طور همزمان عملکرد عمومی سیستم را نیز نگه میدارند [30].
3-5 طبقه بندی سلسله مراتبی
روشهای متنوعی برای مشکل زمانبندی در سیستمهای محاسبات توزیع شده وجود دارد. این تنوع مقایسه سیستمهای مختلف را مشکل میکند. در [31] یک طبقه بندی زمانبندی توزیعی ارائه شده و در آن از اصطلاحات رایج و مکانیزم کلاس بندی برای مقابله با این مشکل استفاده شده است. این طبقهبندی ترکیبی از طبقهبندی سلسله مراتبی و مسطح است. طبقه بندی را میتوان، دستهبندی بر اساس یک مجموعه کوچک مناسب از ویژگیهای اساسی مشخص تعریف کرد. طبقه بندی سلسله مراتبی در شکل 3-1 نشان داده شده است.
شکل3- 2 طبقه بندی الگوریتم های زمانبندی [31]
3-5-1 زمانبندی محلی در برابر عمومی
زمانبند محلی تخصیص زمان پردازنده به فرآیندهاست و زمانبندی عمومی، درباره محلی است که فرآیند میخواهد اجرا شود، تصمیم میگیرد. به عبارتی در زمانبندی محلی، به راحتی میتوان ترتیب اجرای پروسه های مختلف بر روی یک پردازنده خاص را مدیریت کرد. درحالی که در حالت عمومی، یا آگاهی از تعداد پروسهها و پردازندهها میتوان راحتتر شاخصهای بهینه سازی را بهبود بخشید.
3-5-2 زمانبندی ایستا در برابر پویا
سطح بعدی در طبقه بندی، انتخاب بین زمانبندی ایستا و پویا است که از جمله عوامل موثر در بهینه سازی محسوب میشوند. تصمیم گیری در این مرحله مبنی بر زمان است. زمانبندی ایستا به معنای تخصیص فرآیندها به پردازندهها در زمان کامپایل یا زودتر است. زمانبندی پویا به این معنی است که فرآیندها در زمان شروع اجرا به پردازنده تخصیص داده میشوند (تخصیص در زمان اجرا) و ممکن است در حین اجرا تخصیص دوباره انجام شود. تفاوت دیگر این است که زمانبند ایستا، فقط بر اساس اطلاعات فرآیند و سیستم ایستا تصمیمگیری میکند، درحالی که زمانبند پویا، وضعیت فعلی سیستم را نیز در نظر میگیرد. الگوریتم های زمانبندی ایستا و پویا در ادامه مورد بحث قرار می دهیم.
* الگوریتم های زمانبندی ایستا: در زمانبندی ایستا، اطلاعاتی درباره ترتیب کلی فرآیندها در سیستم و همچنین همه زیر وظایف مستقل مرتبط با یک کار را نگه میدارد [28]. در این روش هر وظیفه فقط یک بار به منبع اختصاص داده میشود. در نتیجه محل قرارگیری وظیفه ثابت است و تخمین هزینهها به راحتی انجام میگیرد. همچنین زمانی که حجم کاری قبل از تصمیمگیری به خوبی توصیف شده باشد، میتواند موثر باشد. با این حال، آن در هنگام تغییرات بار سیستم با شکست مواجه میشود [31].
* الگوریتم های زمانبندی پویا: در زمانبندی پویا، دانش پیشین درباره نیازهای منابع یک فرآیند کم است و محیطی که فرآیند در طول حیات خود در آن اجرا میشود، مشخص نیست. در این روش مجموعه کارها یا منابع ثابت نیستند، به عنوان مثال، زمان ورود وظایف یکسان نیست یا امکان دارد برخی منابع در زمانهایی فعال نباشند. همچنین در این نوع زمانبندی از سیاست تعادل بار استفاده میشود تا بار کاری منابع را متعادل نماید و تصمیم بگیرد چه وظایفی به کجا منتقل شوند [32].
3-5-3 بهینه در برابر غیر بهینه
حداقل کردن زمان تکمیل فرآیندها، حداکثر استفاده از منابع و حداکثر توان عملیاتی سیستم را به عنوان معیارهای بهینه سازی در نظر میگیرند [28]. در زمانبندی نکته ای که عموماً لحاظ میگردد نگهداری اطلاعات مربوط به منابع است. روش بهینه سعی دارد هدف را به بهترین شکل برآورده سازد در صورتی که روشهای نیمه بهینه تنها به یک هدف نمیپردازد بلکه سعی بر بهبود نسبی چندین هدف به صورت توام دارند. با توجه به ساختار شبکههای ابر روش های نیمه بهینه بیشتر مورد استفاده قرار میگیرند [33].
3-5-4 توزیع شده در برابر غیر توزیعی
در روشهای زمانبندی پویا و توزیع شده، مسئولیت اصلی به عهده یک زمانبند مرکزی و یا چندین زمانبند توزیع شده است. روشهای متمرکز، روشهایی هستند که از سادگی خاصی برخوردارند اما دو مشکل اساسی دارند که عبارت اند از تحمل خطا و غیرقابل گسترش بودن. در مقابل روشهای توزیع شده با اهداف سیستمهای موازی منطبق هستند.
3-5-5 تقریبی در برابر اکتشافی
در روش تقریبی از یک واحد و معیار تعریف شده برای تخمین بهینه بودن استفاده میشود. هر گاه مقدار مورد نظر برآورده شد، هدف نیز حاصل گردیده است. این روش در صورتی که هدف، کاهش زمان مربوط به زمانبندی باشد، مناسب است. روش مورد استفاده دیگر روشهای اکتشافی است که با فرضهای واقعی در مورد سیستم و گسترده کردن دامنه جستجو، ضمن لحاظ کردن اطلاعات سیستمی نظیر پردازندهها، بارکاری و غیره تمام راهحلهای ممکن را یافته و جواب نزدیک به بهینه را پیدا میکند. روش اخیر در الگوریتمهای زمانبندی بیشتر استفاده میشود [34]. از دسته الگوریتمهای اکتشافی میتوان به MIN-MIN،MAX-MIN و… اشاره نمود.
3-5-6 همکار در برابر غیر همکار
در زمانبندی عمومی پویای توزیع شده، مکانیزمهایی هستند که با اجزای توزیع شده سروکار دارند (همکار) و نیز مکانیزم هایی که در آن پردازنده های فردی مستقل از اعمال پردازنده های دیگر تصمیم گیری میکنند (غیر همکار)[28]. در سیستمهای زمانبندی ارتباط گرههایی است که کارها بر روی آن قرار دارند، باید در نظر گرفته شود. در حالتی که ارتباط به صورت غیر همکار باشد زمانبندهای منفرد به تنهایی عمل میکنند و تصمیمات زمانبندی را با توجه به هدف بهینه سازی خودشان، بدون توجه به دیگر بخشها انجام میدهند. مثالی خوب از این حالت زمانبندی در سطح برنامه کاربردی است که اهداف را به صورت خصوصی بهینه میسازد. در حالت همکار هر زمانبند مسئولیت خاص خود را در زمانبندی کارها دارد اما تمام زمانبندها در جهت هدف کلی سیستم عمل میکنند. سیاست زمانبند محلی، به جای برآوردن نیازمندیهای کارایی محلی و یا یک کار مخصوص، ایجاد تصمیمی است که هدف سراسری را بهبود ببخشد.
3-6 مقدمه ای بر جریان کار
3-6-1 تعریف جریان کار
جریان کار به معنای مجموعه ای از وظایف به همراه وابستگی بین آنها است. در مدل جریان کار، یک فرآیند متشکل از مراحلی ساده است که باعث کاهش پیچیدگی طراحی و نیازهای مدیریتی برنامه های کاربردی می شود. پیشرفت های اخیر در فناوری های مجازی سازی و رشد سریع خدمات ابر در سال های اخیر، باعث ایجاد یک الگوی جدید برای توزیع محاسبات بر روی ابرها، به منظور استفاده از منابع موجود و مقیاس پذیر شده است. سیستم مدیریت فرآیندهای کسب وکار18 به منظور انطباق با این الگوی جدید و جهت استفاده از مزایای خدمات ابر ایجاد شده است. در این راستا بستر به عنوان سرویس در محاسبات ابری، محیطی اجرایی به منظور ایجاد و استقرار برنامه های جریان کار در زیرساخت های ابر را فراهم می سازد [35].
3-6-2 زمانبندی جریان کار
فرآیند زمانبندی جریان های کار به نگاشت وظیفه (گروهی از وظایف) به منابع محاسباتی موجود و زمانبندی اجرای آنها به طوری که وابستگی میان آنها حفظ شود اطلاق می گردد. ساختار جریان های کاری اغلب به صورت یک گراف بدون دور19 و همانند یک ساختار درختی تعریف می شود [36]. تصمیم گیری برای نگاشت وظایف به یک منبع را می توان بر اساس اطلاعات موجود در یک زمانبند انجام داد. نحوه تصمیم گیری به دو صورت محلی و جهانی می باشد. تصمیم گیری های محلی تنها بر اساس اطلاعات مربوط به یک وظیفه (گروهی از وظایف) که توسط زمانبندی خاص به کار گرفته شده اند، اتخاذ می شوند اما در مقابل، تصمیم گیری های جهانی با توجه به کل جریان کاری و نه تنها بر اساس یک وظیفه خاص گرفته می شوند [37].
3-6-3 معماری سیستم مدیریت جریان کار
یک مدل مرجع در [38] منتشرشده که در این مدل تعریف سیستم مدیریت جریان کار و رابطهای مهم سیستم را نشان داده است. شکل 3-2 را مشاهده کنید.
شکل3- 3 مدل مرجع جریان کار [38]
* موتور جریان کار: یک سرویس نرمافزاری است که محیطی زمان-اجرا به منظور ایجاد، مدیریت و اجرای نمونه جریان کار فراهم میکند.
* تعریف فرآیند: ارائه یک فرآیند جریان کار به شکلی که از دست کاری خودکار حمایت کند.
* قابلیت همکاری جریان کار: واسط هایی برای اینکه از همکاری در سیستم های جریان کاری مختلف حمایت کنند.
* برنامههای کاربردی درخواست شده: واسط هایی برای اینکه از تعامل با انواع برنامه های کاربردی IT حمایت کنند.
* برنامههای کاربردی مشتری: واسط هایی برای اینکه از تعامل با واسط کاربر حمایت کنند.
* مدیریت و نظارت: واسطهایی برای ارائه سیستم نظارت و توابع استاندارد که مدیریت ترکیبی محیط برنامههای کاربردی جریان کار را آسان میکنند.
این گونه به نظر میرسد که زمانبندی یک تابع ماژول از موتورهای جریان کار است، در نتیجه آن بخش قابل توجهی از سیستم مدیریت جریان کار است.
فصل چهارم
الگوریتمهای زمانبندی وظایف
4-1 مقدمه
روش های سنتی که در بهینه سازی استفاده می شوند، قطعی و سریع هستند و معمولاً جواب دقیقی می دهند اما اغلب به صورت محلی عمل می کنند. زمانبندی وظایف در فضای جستجوی بزرگ مشکل تر است و تعداد راه حل های موجود زیاد است و وظایف برای یافتن راه حل بهینه باید زمان بیشتری صرف کنند. برای حل این مشکل در این موقعیت، روش خوبی تعریف نشده است. با این وجود در ابر، پیدا کردن راه حلی نزدیک به بهینه هم کارآمد است. در زمینه مشاغل IT بر روی روش های اکتشافی تمرکز دارند. در این فصل به بررسی انواع الگوریتم های زمانبندی از جمله الگوریتم های اکتشافی، بلادرنگ که در شکل 4-1 نشان داده شده، می پردازیم.
شکل4- 1 انواع الگوریتمهای زمانبندی
4-2 مدلهای اکتشافی برای زمانبندی وظایف
در محاسبات ابری، یک مرکز داده معمولی از ماشینهای با سرعت بالا تشکیل شده است. این محیط، گروه متنوع و بزرگ از وظایف را محاسبه میکند. وظایف مربوط به کاربران مختلف از یکدیگر متمایز میشوند. در چنین شرایطی مشکل زمانبندی تطبیق چند وظیفه به چند ماشین است. به طور کلی حالت اکتشافی به عنوان یک الگوریتم نیمه بهینه در جهت به دست آوردن راه حل های خوب است.
4-2-1 استراتژیهای ایستا
روش اکتشافی ایستا هنگامی استفاده میشود که مجموعه کامل از وظایف قبل از اجرا شناخته شوند. این استراتژی ها تحت دو فرض اجرا میشوند. اول اینکه وظایف به طور همزمان میرسند و فرض دوم این است که زمان ماشینهای موجود، بعد از هر زمانبندی وظیفه بروز میشوند.
4-2-1-1 الگوریتم موازنه بار فرصت طلبانه20 (OLB)
ایده اصلی الگوریتم توازن بار فرصت طلبانه، اشغال نگه داشتن همه پردازندهها تا حد ممکن است. در این الگوریتم، بدون توجه به زمان اجرای وظایف بر روی منابع، به طور مرتب همه منابع را چک میکند و اختصاص وظایف به منابع صورت میگیرد. الگوریتم در صورت تمام شدن کار منبع و وجود وظیفههای زمانبندی نشده، آن وظیفه را به منبع مورد نظر اختصاص میدهد. در واقع وظایف به هنگام رسیدن به سیستم مدیریت منابع، وارد صف شده و هر منبع به محض آزاد شدن، به وظیفه موجود در سر صف تخصیص داده میشود. این الگوریتم تلاش میکند تا در حد امکان همه منابع را مشغول نگه دارد و به این ترتیب، از منابع حداکثر استفاده را کرده و بار کاری را بین آنها به طور متوازن پخش میکند. یکی از مزیتهای OLB سادگی آن است اما از آنجائیکه این الگوریتم زمانهای اجرای مورد انتظار کار را در نظر نمیگیرد، معمولاً زمان تکمیل بالایی دارد. در مقابل الگوریتم OLB، الگوریتمهای MCT و MET قرار دارند که هدف آنها کم کردن زمان اجرایی و زمان تکمیل وظیفه است [39].
4-2-1-2 الگوریتم زمان اجرا کمینه21 (MET)
الگوریتم زمان اجرای کمینه، بر خلاف OLB، هر وظیفه را به ترتیب دلخواه به ماشینی با بهترین زمان اجرای مورد انتظار آن وظیفه اختصاص میدهد بدون اینکه به دسترس بودن آن ماشین توجه کند. هدف MET این است که به هر وظیفه بهترین ماشین مربوطه به آن داده شود. این میتواند باعث عدم توازن جدی بین ماشینها شود. به طور کلی این الگوریتم برای محیطهای محاسباتی ناهمگن مناسب نیست [40].
4-2-1-3 الگوریتم زمان اتمام کمینه22 (MCT)
ایده اصلی الگوریتم زمان اتمام کمینه، ترکیب مزایای دو روش OLB و MET می باشد. الگوریتم MCT یک وظیفه را به پردازندهای که کمترین زمان تکمیل را برای آن داشته باشد اختصاص میدهد. این امر باعث میگردد که برخی از کارها به پردازندههایی انتساب شوند که زمان اجرای خوبی نداشته باشند. به محض ورود یک وظیفه به زمانبند، تمام پردازندههای موجود در سیستم بررسی میشوند تا پردازندهای که کمترین زمان تکمیل را برای آن کار دارد، مشخص شود [41].
4-2-1-4 الگوریتم Min-Min
این رویکرد اولویت بندی وظایف و تولید زمانبندی بر اساس اولویت است. این اولویت بر اساس زمان اتمام وظیفه مورد انتظار بر روی یک منبع تولید میشود. این روش وظایف را در چند گروه وظایف مستقل تنظیم میکند. پس از آن این گروهها مکرراً زمانبندی میشوند. هر تکرار مجموعه ای از وظایف مستقل نگاشت نشده را میگیرد و برای هر وظیفه، حداقل زمان تکمیل مورد انتظار23 (MECT) را تولید میکند. وظیفهای که کوچک ترین مقدار MECT، بیش از تمام وظایف انتخاب شده به منابع مربوطه را دارد، در این تکرار اول زمانبندی میشود. این تا زمانی که تمام وظایف زمانبندی شوند، ادامه می یابد [42]. هدف این الگوریتم، رسیدن به کمترین پاسخ است و برای رسیدن به این هدف، ابتدا وظایفی با زمان تکمیل کم و سپس وظایفی با زمان بیشتر را زمانبندی میکند.
4-2-1-5 الگوریتم Min-Max
این روش مشابه با روش Min-Min، است. الگوریتم Min-Maxبا مجموعهای از تمام وظایف زمانبندی نشده شروع و سپس برای هر وظیفه در مجموعه زمان تکمیل کمینه را محاسبه میکند. تفاوت این الگوریتم با روش قبلی، وظایف با بیشترین زمان تکمیل انتخاب و به ماشین نگاشت میشود. بعد وظیفه زمانبندی شده از مجموعه حذف میشود. این فرآیند تا زمانی که همه وظایف زمانبندی شوند ادامه مییابد.
4-2-1-6 الگوریتم GA
الگوریتم ژنتیک از مجموعه تکنیکهای تکاملی برگرفته از طبیعت است که کاربرد فراوانی در مسائل بهینه سازی دارد و برای جستجو در فضاهای حل بزرگ استفاده میشود [43].
در ابتدا برای زمانبندی یک وظیفه خاص، یک جمعیت اولیه از کروموزوم ها به صورت تصادفی تولید میشود. هر کروموزوم یک مقدار تناسب دارد که در اینجا زمان کل اجرای وظیفه متناظر با کروموزوم میباشد. بعد از تولید جمعیت اولیه، برای تمام کروموزومهای موجود در جمعیت مقدار تناسب ارزیابی میشود و کروموزومی که کمترین مقدار تناسب را داشته باشد، بهترین نگاشت خواهد بود. سپس الگوریتم وارد یک حلقه شامل 4 مرحله: انتخاب، تولیدمثل24، جهش25 و ارزیابی میشود. در مرحله انتخاب، برخی کروموزومها را تکثیر و برخی را حذف میشوند، به شکلی که نگاشتهای بهتر احتمال تکثیر بیشتری در نسل بعد داشته باشند. سپس ویژگیهای تضمین بقای بهترین راهحل در جمعیت پیادهسازی شده و اندازه جمعیت ثابت میماند. سپس در عملیات تولیدمثل، یک جفت کروموزوم را انتخاب و یک نقطه تصادفی را در کروموزوم اول بر میگزیند. بعد از عملیات تولیدمثل، عملیات جهش ژنی انجام میشود. جهش ژنی یک کروموزوم را انتخاب کرده و سپس یک وظیفه در آن کروموزوم را برمیگزیند و به یک ماشین جدید اختصاص میدهد. در این مرحله هر سه عمل به صورت تصادفی انجام میشوند. نهایتاً، کروموزومهای این جمعیت تغییریافته دوباره ارزیابی میگردند. این مراحل تا زمان رسیدن به شرایط توقف حلقه، تکرار خواهند شد [41].
4-2-1-7 الگوریتم گرمایشی26 SA
الگوریتم گرمایشی، یک تکنیک با روش تکرار است که فقط یک راه حل نگاشت ممکن را برای هر فرا وظیفه در یک زمان بررسی میکند. این راه حل از همان نمایش کروموزومها در الگوریتم ژنتیک استفاده میکند. الگوریتم SA از روالی استفاده میکند که بر اساس احتمالات به راه حل های ضعیف تر اجازه پذیرش داده و تلاش میکند تا جستجوی بهتری در فضای راه حل انجام دهد. این احتمال بر اساس دمای سیستم است که در هر دور کاهش مییابد. با خنک شدن سیستم پذیرش برای راه حل های ضعیف تر سخت تر خواهد شد. دمای اولیه سیستم، زمان اجرای کلی نگاشت اولیه میباشد.
در پیاده سازی این الگوریتم نگاشت اولیه از یک توزیع تصادفی یکنواخت تولید خواهد شد. نگاشت به همان شکل الگوریتم ژنتیک، جهش ژنی مییابد و زمان اجرای کلی جدید ارزیابی میشود. اگر زمان اجرای کلی جدید بهتر باشد، نگاشت جدید جایگزین قدیمی میشود. اگر زمان اجرای کلی جدید بدتر یا به عبارتی طولانی تر باشد، یک عدد تصادفی یکنواخت انتخاب و بررسی بر اساس آن انجام میشود [44].
4-2-1-8 الگوریتم Tabu
جستجوی Tabu، یک جستجوی فضای راهحل است که ناحیههایی از فضای راهحل را که قبلاً جستجو شدهاند، یادداشت میکند تا در جستجوی بعدی حوالی این ناحیه ها را جستجو نکند. یک راه حل نگاشت، از همان نمایش کروموزوم در الگوریتم ژنتیک استفاده میکند. پیاده سازی جستجوی Tabu، با یک نگاشت تصادفی تولیدشده از یک توزیع یکنواخت به عنوان راهحل ابتدایی آغاز میگردد. برای دستکاری راهحل فعلی و حرکت در فضای راهحل یک گام کوتاه برداشته میشود. هدف از گام کوتاه پیدا کردن نزدیکترین راهحل کمینه محلی در فضای راهحل است [45].
4-2-1-9 الگوریتم A*
الگوریتم A*، یک روش اکتشافی جستجو بر اساس درخت شروع است و از یک گره ریشه که یک راه حل تهی است شروع میشود. همان طور که درخت رشد می کند، گرهها نشان دهنده زمانبندی جزئی (زیرمجموعه ای از وظایف به ماشین ها اختصاص داده شده است) و برگ نشان دهنده زمانبندی نهایی (همه وظایف که به ماشین ها اختصاص داده شده است)، هستند. راه حل جزئی از یک گره فرزند، یک وظیفه زمانبندی شده از گره پدر دارد. هر گره پدر می تواند توسط فرزندانش جایگزین شود. برای نگه داشتن زمان اجرای اکتشافی، یک فرآیند هرس به منظور محدود کردن حداکثر تعداد گره فعال در درخت در هر زمان وجود دارد. اگر درخت هرس نشده باشد، این روش معادل جستجوی کامل است. این روند تا زمانی که برگ به زمانبندی کامل رسیده باشد، ادامه مییابد [41].
4-2-2 استراتژیهای پویا
روش اکتشافی پویا زمانی که مجموعه وظایف و یا مجموعه ماشینها ثابت نیستد، ضروری است. به عنوان مثال، همه وظایف به طور همزمان نرسند و یا برخی از ماشینهای در فواصل زمانی به حالت آفلاین بروند. روش اکتشافی پویا در دو حالت، آنلاین و دسته ای استفاده میشود. در حالت اول، زمانی که یک وظیفه برسد به یک ماشین زمانبندی میشود، در حالت دوم، وظایف ابتدا در یک مجموعه جمع آوری شده و زمانبندی در زمان از پیش برنامه ریزی شده، اجرا میشود.
4-2-2-1 حالتOn-line
در حالت اکتشافی آنلاین، هر وظیفه تنها یک بار زمانبندی شده و نتیجه زمانبندی نمی تواند تغییر کند. حالت اکتشافی آنلاین برای مواردی با نرخ ورود کم مناسب است.
* الگوریتم OLB: یک نوع از روشهای اکتشافی پویا است که یک وظیفه را به اولین ماشینی که آماده است، تخصیص میدهد بدون اینکه زمان اجرای آن وظیفه در آن ماشین را در نظر بگیرد.
* الگوریتم MET: یک نوع استراتژی اکتشافی پویا است که هر وظیفه را به ماشینی که انجام محاسبات مربوط به وظیفه را در کمترین زمان اجرا بدون در نظر گرفتن زمان در دسترس ماشین، اختصاص میدهد.
* الگوریتم MCT: یک نوع استراتژی اکتشافی پویا است که هر وظیفه را به ماشینی که زودترین زمان اتمام را دارد تخصیص میدهد. این روش اکتشافی به عنوان یک معیار برای حالت آنلاین، استفاده میشود [46].
* الگوریتم SA: نوع استراتژی پویا اکتشافی در حالت آنلاین است. این الگوریتم از هر دو روش اکتشافی MET و MCT به شیوه ای دوره ای بر اساس توزیع بار در سراسر ماشین ها استفاده میکند. الگوریتم MET، بهترین ماشین را انتخاب میکند اما وظایف زیادی را به آن تخصیص میدهد. اکتشافی MCT، بار را متوازن میکند ولی در همان زمان آن وظیفه را به ماشین که دارای کمترین زمان اجرا است، تخصیص نمیدهد. برای مثال، اگر وظایف به طور تصادفی برسند، ما میتوانیم از MET برای رسیدن توازن بار به یک مقدار آستانه داده شده و سپس از MCT، برای ایجاد سطح بار در سراسر ماشینها استفاده کنیم.
* الگوریتم بهترین درصد 27K (KPB): این الگوریتم فقط زیرمجموعه ای از پردازندهها را برای تخصیص در نظر میگیرد. یک وظیفه به پردازندهای که نزدیکترین زمان تکمیل را در زیرمجموعه مزبور داشته باشد، تخصیص داده میشود. اگر k=100 باشد، آنگاه الگوریتم به MTC تقلیل پیدا میکند[46].
4-2-2-2 حالت Batch
در حالت دسته ای، وظایف تنها در برخی از لحظات از پیش تعریف شده زمانبندی میشوند. این دسته ای اکتشافی را قادر می سازد تا در مورد زمان اجرای واقعی تعداد زیادی از وظایف اطلاع داشته باشد.
* الگوریتم Min-Min: به این صورت عمل میکند که در هر مرحله، از وظایف و مجموعه پردازندهها مجموعهای از زوجهای وظیفه/پردازنده را انتخاب میکند که نزدیکترین زمان تکمیل مورد انتظار را داشته باشند. سپس از این مجموعه زوج وظیفه/پردازندهای که کمترین زمان تکمیل مورد انتظار را دارد انتخاب میکند و آن وظیفه را به آن پردازنده اختصاص میدهد. این روش مانند روش MTC بر اساس حداقل زمان تکمیل است [47]. به هر حال روشMin-Min همه وظایف تخصیص داده نشده را طی هر رخداد تخصیص بررسی میکند درحالی که روش MTC تنها یک وظیفه را در هر زمان بررسی میکند.
* الگوریتم Max-Min: این الگوریتم به این صورت عمل میکند که در هر مرحله از وظایف و مجموعه پردازندهها، مجموعهای از زوجهای وظیفه/پردازنده را انتخاب میکند که نزدیک ترین زمان تکمیل مورد انتظار را داشته باشند [46]؛ اما برخلاف قبلی این زوج وظیفه/پردازندهای را که بیش ترین زمان تکمیل مورد انتظار را دارد انتخاب میکند و آن کار را به پردازنده اختصاص میدهد. در مواقعی که تعداد وظایف کوتاه از تعداد وظایف بلند بیشتر باشد، انتظار میرود نسبت به الگوریتم قبلی بهتر عمل کند.
* الگوریتم حق رای28: یک نوع روش اکتشافی است و هر وظیفه بر اساس مقدار رای، به منبع اختصاص داده میشود. مقدار رای، تفاوت بین اولین و دومین زودترین زمان اتمام تعریف میشود. وظیفه با مقدار انتظار بیشتر به ماشینی با زودترین (کمترین) زمان اتمام تخصیص داده میشود [46].
4-2-3 زمانبندهای اکتشافی
یکی از مزایای محاسبات ابری است این است که وظایف ممکن است دشوار، وقت گیر و یا گران قیمت باشند که برای یک کاربر خاص در مرکز داده انجام میشوند. مرکز داده در ابر، جدایی عملی بین قدرت پردازش و ذخیره سازی داده ها که هر دو در تعداد زیادی از دستگاه های از راه دور قرار دارند را پشتیبانی میکند. از این رو، زمانبندی پیچیده تر و چالش برانگیز تر از قبل میشود. از آنجا که زمانبند فقط یک جزء اساسی برای تمام زیرساخت است، به طور کلی هیچ زمانبندی نمیتواند برای همه معماری ابر، مناسب باشد.
4-2-3-1 هادوپ29
هادوپ یک چارچوب محاسباتی مهم است. آن فقط پردازش مقدار زیادی از دادهها را در ابرهای خصوصی و عمومی پردازش میکند و برای پیادهسازی ابر اهمیت بسیاری دارد. هادوپ از گسترده ترین و برجستهترین پیاده سازی های نگاشت-کاهش است که برای تولید و یا کاربردهای آموزشی استفاده میشود. آن قادر است برنامه های کاربردی بسیاری را برای کار با پتابایت داده و هزاران گره بسازد.
یک خوشه از هادوپ چند گرهای از دو لایه تشکیل شده است. در لایه پایین سیستم فایل توزیع شده هادوپ30(HDFS)، قرار دارد که دارای قابلیت فراهم کردن اطلاعات در مورد آگاهی از محل داده برای انجام زمانبندی موثر کار است. لایه بالا دارای موتور نگاشت-کاهش است که دارای چندین دنبال کننده وظیفه و یک رد گیر کار است و هر رد گیر میتواند یک گره را نگه دارد. کارهای نگاشت-کاهش توسط مشتریان به رد گیر کار ارسال خواهند شد و سپس رد گیر کار، کارها را به گره دنبال کننده وظیفه که در حال حاضر در خوشه هستند، میدهد [48].
هادوپ برای کارهای دسته ای بزرگ طراحی شده است. زمانبند پیش فرض از روش اکتشافی FIFO، برای زمانبندی استفاده میکند، جایگزینهای دیگری نیز برای این زمانبند وجود دارد که زمانبند عادلانه، زمانبند ظرفیت و زمانبند تاخیر هستند که در زیر آنها را شرح میدهیم.
* زمانبند FIFO: یک نوع زمانبند اکتشافی است که برای اولین بار در اولین روش اکتشافی بکار برده شد. زمانبند یک کار جدید در صف را بر اساس زمان ورود آن نگه میدارد. کاری که در ابتدای لیست انتظار قرار دارد برای اجرا انتخاب میشود. از آنجا که این زمانبند حداقل سربار را دارد و پیاده سازی آن بسیار آسان میباشد اما وظایف با زمان اجرای طولانی، توان عملیاتی ماشینها را پایین میآورد [48].
* زمانبند عادلانه: نوعی زمانبند اکتشافی است که سهم برابری از منابع را به تمام کارها اختصاص میدهد. وقتی کارهای جدید میرسند، بین وظایف یک مقدار آزاد به اشتراک گذاشته میشود، به طوری که هر وظیفه تقریباً همان مقدار از زمان CPU را میگیرد. زمانبند عادلانه از اولویت های کار که به عنوان وزنهای برای تعیین کسری از زمان محاسبه کل که هر کار باید بگیرد، پشتیبانی میکند. همچنین اجازه می دهد یک خوشه در میان تعدادی از کاربران به اشتراک گذاشته شود. به طور پیش فرض به هر کاربر یک مجموعه جداگانه داده میشود، به طوری که هر کس سهم مشابهی از خوشه میگیرد و مهم نیست که چگونه بسیاری از کارها فرستاده میشوند. در هر مجموعه، به اشتراک گذاری عادلانه برای به اشتراک گذاشتن ظرفیت بین کارهای در حال اجرا استفاده میشود. علاوه بر این، سهم حداقل تضمین را فراهم میکند. هنگامی که یک مجموعه شامل کارها، به سهم خود به طور کامل نیاز ندارد، مقدار اضافی در میان کارهای دیگر در حال اجرا تقسیم میشود [49].
* زمانبند ظرفیت: نوعی زمانبند اکتشافی است که مقداری از ظرفیت خوشه را به صف های متعدد که هر کدام از آنها شامل بخشی از ظرفیت هستند، اختصاص میدهد. هر کار که به یک صف فرستاده میشود، میتواند به کل به ظرفیت اختصاص داده شده به صف دسترسی داشته باشد. صفها در هر زمان، محدودیتهایی را بر روی درصد منابع اختصاص داده شده به یک کاربر، اعمال میکنند؛ بنابراین هیچ کاربری نمیتواند به صورت انحصاری منابع را در اختیار بگیرد. صف به صورت اختیاری از اولویت های کار پشتیبانی میکند. در یک صف، کارهای با اولویت بالا برای دسترسی به منابع ترجیح داده میشوند. با این حال، هنگامی که یک کار در حال اجرا است، آن برای یک کار با اولویت بالاتر قبضه نخواهد شد [50].
* زمانبند تاخیر: نوعی زمانبند اکتشافی است که بین زمانبندی عدالت و محلیت داده برخورد ایجاد میکند. این نوع به طور موقت، برای بهبود محلیت، عدالت را رها میکند. برای اینکه یک گره با داده های محلی را زمانبندی کند، از کارها درخواست انتظار مینماید. هنگامی که این کار باید بعداً با توجه به عدالت زمانبندی شود، نمیتواند یک کار محلی را راه اندازی کند، آن را برای مدت کوتاهی انتظار میکشد، اجازه میدهد دیگر کارها بجای آن، وظایف خود را راه اندازی کنند. با این حال، اگر یک کار به مدت طولانی نادیده گرفته شود، آن مجاز است برای جلوگیری از قحطی، کارهای غیر محلی را راه اندازی کند. زمانبند تاخیر موثر است اگر وظایف در مقایسه با کارها کوتاه و شکافهای بسیاری در هر گره وجود داشته باشد، کارآمد است [51].
4-2-3-2 درایَد31
دراید یک موتور اجرای توزیع شده برای برنامههای موازی داده است و به نظر می رسد با چارچوبهای برنامه نویسی مایکروسافت، قابلیتهایی مشابه هادوپ را فراهم میکند. دراید برای برنامههای کاربردی، گراف بدون دور را بکار میبرد [52].
زمانبند کوئینسی32، به برخورد بین محلیت و زمانبندی در چارچوب دراید، میپردازد. این نشان میدهد مشکل زمانبندی، یک مسئله بهینه سازی است. جریان حداقل هزینه، تصمیم گیری زمانبندی، ارتباط وظایف و گرهها را میگیرد. ایده اساسی این است که برخی از وظایف در حال اجرا کشته و سپس وظایف جدید در محل خوشه در پیکربندی بازگردانده شده توسط حل کننده جریان راه اندازی شوند [53].
4-2-4 الگوریتمهای زمانبندی جریان کار
زمانبندی جریان کار یکی از مسائل کلیدی در مدیریت جریان کار، به خصوص در گرید و سیستمهای جریان کار ابر است [54]. این یک فرایند است که اجرای وظایف وابسته در منابع توزیع شده را مدیریت میکند. این تخصیص مناسب منابع برای وظایف جریان کار، میتواند برای رضایت توابع هدف اعمال شده توسط کاربران تکمیل شود.
4-2-4-1 الگوریتم مسیر بحرانی سریع33 (FCP)
الگوریتم مسیر بحرانی سریع (FCP) سعی در کاهش پیچیدگی زمانبندی وظیفه دارد و این در حالی است که عملکرد زمانبندی را نیز حفظ میکند، این پیچیدگی میتواند به طور موثر کاهش یابد اگر لیست وظایف آماده مرتب شده، اندازه ثابتی داشته باشد. در این حالت، بقیه وظایف در یک لیست ساده و نامرتب FIFO که زمان دسترسی O(1) دارد، ذخیره میشوند. وقتی که یک وظیفه آماده میشود، اگر جایی برای آن وجود داشت به لیست مرتب شده اضافه میشود، در غیر این صورت به لیست FIFO اضافه میشود. وظایف همیشه از لیست مرتب شده برداشته میشوند، بعد از آن، اگر لیست FIFO خالی نبود، یک وظیفه به لیست مرتب شده نقل مکان میکند. پیچیدگی زمان مرتب سازی وظایف با استفاده از یک لیست به اندازه H بهO(HlogH) کاهش مییابد و همه وظایف، فقط یک بار در لیست مرتب شده صف بندی و برداشته میشوند.
نقطه ضعف احتمالی، استفاده از اندازه ثابت برای لیست مرتب شده است که این امکان وجود دارد وظیفه با بالاترین اولویت در لیست مرتب شده قرار نگیرد، اما به طور موقت در لیست FIFO ذخیره میشود؛ بنابراین اندازه لیست مرتب شده باید به اندازه کافی بزرگ باشد که عملکرد الگوریتم بیشتر شود. در همان زمان، پیچیدگیزمانی آن نباید بیش ازحد زیاد باشد. آزمایشهای نویسنده نشان میدهد که یک لیست اولویت به اندازه p (تعداد پردازنده ها) یک انتخاب خوب برای الگوریتم FCP است. اندازههای کوچک تر با مشکلات موازیسازی محدود، درحالی که اندازه بیشتر، به معنای بهبود عملکرد بیشتر نیست [54].
4-2-4-2 الگوریتم زمانبند کلی تطبیقی34 (AGS)
در الگوریتم زمانبند تطبیقی کلی (AGS) یکی از کلاس های مهم، ذخیره فایل است که به عنوان یک بردار زمان گپ پیادهسازی شده است؛ بنابراین، برای دسترسی کامل راه اندازی شده، در مورد تمام گرههای محاسباتی برای زمانبندی وظایف موجود میباشد. اگر برخی از گره برای دوره معینی از زمان ذخیره شده باشند یا با صاحب منابع یا با وظایف دیگر که به گرههای محاسباتی اختصاص داده شده بود، بردار زمان گپ، زودتر از یک چرخه زمانبندی، شامل اطلاعات است.
اول، برای هر وظیفه، زمان شروع توسط زمان پایان آخرین فرآیند والد تعیین میشود. در گام بعدی، گره محاسباتی که در آن آخرین والد پردازش شد، مشخص میشود. تاخیر انتقال دادهها از والدهای دیگر به گره محاسبه شده و زمان شروع به روز میگردد. اگر گرهای از زمان شروع به روز شده وظیفه تا پایان زمان پردازش وظیفه، در دسترس بود، وظیفه به گره اختصاص داده میشود. در غیر این صورت برای هر گره زمان شروع پس از ارزیابی تاخیر از تمام فرآیندهای والد محاسبه میگردد. با استفاده از زمان آغاز به روز شده، زمان پایان این فرآیند را برای گره یافت میشود. از همه گرههای در دسترس، وظیفه، به گره محاسباتی که زمان پایان نزدیکتری دارد نگاشت داده میشود. پس از نگاشت، بردار زمان گپ، به روز میگردد [55].
4-2-4-3 مکانیزم نگاشت جریان کار35(WMM)
هدف اصلی مکانیزم نگاشت جریان کار(WMM) ، پیدا کردن انتخاب بهینه با توجه به معیارهای کیفیت سرویس درخواست شده توسط کاربر و ارائه توسط ارائه دهندگان خدمات است. مراحل اصلی الگوریتم به طور خلاصه در زیر بیان شده است:
1) محاسبه مقادیر کمکی برای تکمیل الگوریتم، تعریف معیارهایی که سطح QOS ارائه شده توسط موارد خدمات را تعریف میکنند.
2) نگاشت جریان کار با نمونه سرویس، متناسب با نیاز کاربر به منظور دسترس پذیری، بدون نقض محدودیت هزینه مقداردهی اولیه میکند.
3) نمونه خدمات (کاندید) را برای هر نوع خدمات تعریف میکند. دلیل این کار در این مرحله این است که برای ارائه سطح بالاتری از کیفیت سرویس کاندیدها را برای هر نوع خدمات در یک جریان کار کشف کند.
4) در جهت پیدا کردن جایگزین های ممکن یک لیست با "بهترین کاندیدها "برای هر نوع خدمات ایجاد میکند.
5) یک طرح که اجازه می دهد بیشتر از یک سرویس نمونه در هر نوع خدمات انتخاب شود و کاربر با محدودیت زمانی مواجه نشود، زمانبندی میکند [56].
4-2-4-4 الگوریتم انشعاب جریان کار تطبیقی36 (AWS)
در الگوریتم تقسیم جریان کار تطبیقی(AWS)، هنگامی که یک زمانبند یک وظیفه را دریافت میکند، برای گراف DAG وظایف، نسبت محاسبه به ارتباطات37 (CCR) و تعداد خوشههای منبع (به عنوان مثال N) را محاسبه میکند. مقدار CCR بالا به این معنی است که گراف وظیفه فشرده محاسباتی است. سپس، زمانبند N خوشه منبع که دارای بالاترین رتبه با توجه به دانش خود است را انتخاب میکند. یک گراف تکرار پارتیشن هر گره باقی مانده در G را برای تعیین اینکه آیا گره را می توان به یک زیر گراف G 'قرار داد بررسی میکند. آن به دنبال یالی با بزرگ ترین ارتباطات که دو گره متصل به آن هنوز بررسی نشده است، میگردد. در صورتی که چنین یالی وجود نداشت، این بدان معنی است که تمامی گرههای بررسی نشده در حال حاضر از G 'و یکدیگر جداشده و این وظایف در صورت امکان با زیر گراف ادغام خواهند شد. در غیر این صورت، اگر این یال بتواند باG' ادغام شود، پیمایش اولین عمق گراف از دو راس این یال به ادغام گرههای وظایف بیشتر شروع خواهد شد. هدف از پیمایش گراف، در صورت ممکن وظایف بدون نقض محدودیت آستانه منابع به زیر گراف ادغام شوند و در همان زمان، برای جلوگیری از شکستن غیرضروری، ترتیب اولویت در میان وظایف حفظ میکند که میتواند موازیسازی را افزایش ندهد، اما ممکن است هزینه ارتباط بین خوشهای را افزایش دهد.
یک پشته برای دست کاری گره وظیفه در پیمایش استفاده میشود. اگر این یال تحت محدودیت نتواند در G ' ادغام شود، گره مسئول مشخص خواهد شد. این به معنی ایجاد یک زیر گراف جدید میباشد. زمانبند تا زمانی که همه گرهها درG به خوشه منبع اختصاص داده شوند این حلقه را تکرار میکند. بعد از اتمام الگوریتم، زمانبند هر زیر گراف را به خوشه منبع تعیین شده خود توزیع خواهد کرد [57].
4-2-4-5 رویکرد سود و زیان38
رویکرد سود و زیان، مکرراً زمانبندی را که توسط یک زمان اکتشافی بهینه یا اکتشافی بهینه شده از نظر هزینه تولیدشده را برای مقابله با محدودیتهای بودجه تنظیم میکند. زمانبندی با انتساب اولیه وظایف بر روی ماشینها شروع میشود و تغییر هر وظیفه به یک ماشین متفاوت را بر اساس مقدار وزن مرتبط با آن تغییر خاص محاسبه میکند. این مقادیر وزنها، جدولبندی میشوند، بنابراین، یک جدول وزن برای هر وظیفه در DAG و هر ماشین ایجاد میشود. دو روش جایگزین برای محاسبه مقادیر وزن، با توجه به دو انتخاب برای انتساب اولیه، پیشنهاد شده است: یا داشتن زمان تکمیل بهینه و یا هزینه بهینه. با استفاده از جدول وزن، وظایف بارها و بارها برای انتقال به یک ماشین، (در مورد زیان) تا زمانی که هزینه زمانبندی فعلی بیش از بودجه باشد و یا (در مورد سود) تا زمانی که همه انتقالات ممکن از بودجه تجاوز کند، در نظر گرفته میشوند. در هر صورت، الگوریتم تلاش می کند تا انتقال هر جفت از وظایف تنها یک بار اتفاق بیفتد و زمانی که هیچ انتقالی نبود، الگوریتم خاتمه خواهد یافت [58].
4-2-5 الگوریتم بهینه سازی اجتماع ذرات (PSO)
الگوریتم بهینه سازی اجتماع ذرات برای زمانبندی برنامه کاربردی به منابع محاسباتی ارائه شده که هم هزینه انتقال داده و هم هزینه محاسبه را در نظر میگیرد، این الگوریتم برای برنامههای کاربردی جریان کاری از طریق متفاوت کردن هزینههای ارتباطی و محاسباتی مورد استفاده قرار میگیرد [59].
در این الگوریتم هدف حداقل کردن زمان اجرا و بهبود جریان کاری است، نتایج آزمایش ها نشان میدهد که نگاشت وظیفه به منبع براساس این الگوریتم در هزینه صرفهجویی میکند و علاوه بر این تعادل خوبی از بار کاری روی منابع محاسباتی را از طریق توزیع وظایف به منابع در دسترس فراهم میکند.
4-2-6 الگوریتم بهینهسازی کلونی مورچگان39(ACO)
الگوریتم اکتشافی جامعه مورچگان از رفتار اجتماعی مورچهها الهام گرفته است. مورچهها با اینکه نابینا هستند ولی میتوانند کوتاهترین مسیر بین لانه و منبع غذایشان را پیدا کنند. مورچهها مسیر بین غذا و لانه خود را در ابتدا به صورت کاملاً تصادفی انتخاب میکنند و کم کم پس از طی چندین دوره رفت و برگشت بین غذا و لانه و افزایش اثر به جای مانده در مسیر کوتاهتر، در نهایت همگی در کوتاهترین مسیر حرکت میکنند. وقتی مورچهای دنبال غذا میگردد، در طول مسیر حرکت، ماده شیمیایی به نام فرومون از خود بر جای میگذارند [60]. با استفاده از این فرومون، کوتاهترین مسیر پیدا میشود. از این مفهوم برای تخصیص کارها استفاده میشود. زمانی که یک منبع به کاری تخصیص و کامل میکند مقدار فرومون آن افزایش مییابد. اگر منبعی نتواند کاری را تمام کند برای مجازات از فرومون آن کاسته میشود [61].
4-2-7 مقایسه الگوریتمهای اکتشافی
به منظور شناخت بیشتر الگوریتمهای اکتشافی در جدول 4-1 به مقایسه این الگوریتمها میپردازیم. در این جدول، m به معنای تعداد پردازندهها و T تعداد وظایف میباشد.
جدول 4- 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 و MCT
O(m)
– زمان تکمیل تقریباً مشابه MCT و KPB
الگوریتم حق رای
– اختصاص هر وظیفه بر اساس مقدار رای
– مقدار رای: تفاوت بین دو مقدار کمینه زمان تکمیل
O(T2×m)
– توان عملیاتی بالا
– سرعت تکمیل بالا
– امکان وجود گرسنگی
الگوریتم ژنتیک
– تکنیکی برای جستجو در فضاهای حل بزرگ
– دارای چهار مرحله: انتخاب، تولیدمثل، جهش و ارزیابی
– ساده و سریع
– روشی بهینه برای حل مسائل بهینه سازی
4-2-8 نتیجهگیری
در این قسمت به مقایسه الگوریتمهای ایستا و پویا در ماشینهای سازگار و ناسازگار میپردازیم. ماشین سازگار، ماشینی است که همه وظایفش را سریعتر از ماشین دیگر اجرا کند. با مقایسه الگوریتمهای اکتشافی در [41] از نظر زمان تکمیل کار، نتایج زیر به دست آمده است. در ماشینهای ناسازگار، الگوریتم GA بهترین نتیجه و این در حالی است که OLB بدترین نتیجه را میدهد. در ماشینهای سازگار نیز GA بهترین عملکرد و MET بدترین عملکرد را دارد. دلیل اینکه MET در محیط سازگار بدتر از OLB عمل میکند این است که در این محیط تخصیص کار به سریعترین پردازنده بدترین انتخاب است چرا که منجر به نگاشت تعداد زیادی کار به تعداد محدودی از پردازندهها میگردد. به طور کلی الگوریتمهای Min-Min و GA می توانند به عنوان استراتژیهای جستجوی امید بخشی با زمان تکمیل کار نسبتاً کم به کاربرده شوند.
با توجه به نتایج آزمایش ها در [42] برای مقایسه الگوریتمهای پویا و حالت بر خط از نظر زمان تکمیل کار، در هر دو محیط، الگوریتم KBT دارای بهترین عملکرد و OLB و MET ضعیفترین عملکردها را در مقابل بقیه داشتند. همچنین نتایج مقایسه برای الگوریتمهای دستهای، الگوریتم حق رای نتیجه بهتری نسبت به دو الگوریتم دیگر دارد. به طور کلی، در بین الگوریتمهای پویا، الگوریتم حق رای زمان تکمیل کار بهتری نسبت به دیگر الگوریتمها دارد.
4-3 الگوریتمهای زمانبندی وظایف بلادرنگ
گروهی از برنامههای کاربردی وجود دارند که زمان برای آنها اهمیت زیادی دارد. در مورد این برنامههای بحرانی که دارای مهلت زمانی هستند، وجود هر تاخیری باعث خرابی در کل سیستم میشود. برای مثال، مراکز کنترل ترافیک با استفاده از سنسورها، اطلاعاتی را درباره وضعیت اخیر جادهها جمع آوری کرده و در پایگاه داده ذخیره میکنند. اگر کاربری درخواستی در مورد وضعیت جادهها به مرکز داده بدهد، یک تصمیم بلادرنگ به کمک اپراتورها، اطلاعات کنترلی مناسب را به کاربر برمیگرداند؛ اما توافقنامه سطح سرویس جاری ابر، کنترل بلادرنگ تحت رفتار زمانی برنامهها را برای کاربران فراهم نمیکنند، بنابراین در آینده یک توافقنامه سرویس که شفافتر، انعطاف پذیرتر و قابل اطمینان تر باشد، مورد نیاز است.
محدودیت زمانی از جمله در برنامههای بلادرنگ، نقش مهمی در محیط ابر ایفا میکند. با این وجود زمانبندهای موجود به دلیل توجه نکردن به فاکتور مهلت زمانی، برای کاربردهای بلادرنگ مناسب نیستند. یک زمانبند بلادرنگ باید علاوه بر بار سیستمها و زمان تکمیل به مهلت زمانی نیز توجه نماید.
اولویت برای این گونه وظایف دورهای با مهلت زمانی به کار میرود. زمانبند وظایف را بر طبق سیاست اولویت به منابع میدهد. بر این اساس زمانبندی اولویت در دو گروه تقسیم بندی میشوند: استراتژی اولویت ایستا و استراتژی اولویت پویا.
4-3-1 استراتژی اولویت ایستا
یک وظیفه بلادرنگ، از مجموعهای از نمونهها تشکیل شده است. در زمانبندی اولویت ثابت، همه نمونههای یک وظیفه، اولویت یکسانی دارند. قدرتمندترین الگوریتم برای وظایف اولویت، الگوریتم میزانیکنواختی40(RM) است. در این الگوریتم، اولویت یک وظیفه خاص به نرخ رهایی آن بستگی دارد. اگر آن نرخ بالا باشد، اولویت وظیفه هم بیشتر است [62].
در الگوریتم (RM) مهلت زمانی وظیفه دقیقاً برابر با دوره آن نبود. برای تخصیص اولویت بهینه نبوده و یک الگوریتم ضعیف محسوب میشد. از این رو الگوریتم یکنواختی مهلت زمانی41(DM) به عنوان سیاست بهینه برای این سیستمها پیشنهاد شد. این الگوریتم به وظایف با مهلت زمانی کوتاهتر، اولویت بیشتری نسبت به مهلت زمانی طولانیتر، میدهد [63].
4-3-2 استراتژی اولویت پویا
روش تخصیص اولویت پویا از رفتار ثابت، کارامدتر است زیرا این استراتژی میتواند از کل پردازنده برای پردازش وظیفه بهره ببرد. اولویت به طور پیوسته با زمان و از یک درخواست به درخواست دیگر یا در همان درخواست در حال تغییر است. بیشترین الگوریتمهای استفادهشده نزدیک ترین مهلتزمانی42(EDF) و کمترین سستی43(LLF) هستند [64]. الگوریتم نزدیک ترین مهلت زمانی، اولویت به وظایف به طور معکوس و متناسب با مهلت زمانی کارهای فعال میدهد. الگوریتم کمترین سستی، پردازنده را به وظیفه فعالی که کمترین سستی را دارا باشد میدهد و این سستی ممکن است چندین بار تغییر کند.
4-3-3 زمانبندهای بلادرنگ
یک زمانبند پویا تصمیم زمانبندی را در زمان اجرا اتخاذ میکند و ممکن است وظیفهای را خارج از مجموعه جاری وظایف آماده انتخاب کند. زمانبند ایستا تصمیمات زمانبندی را قبل از زمان اجرا میگیرد. به طور کلی زمانبندهای بلادرنگ به منظور رویکردهای زمان بندی شان در هستهها جای داده شده اند. هدف هسته MARS [65] در سیستمهای بلادرنگ سخت رسیدن به شرایط باری بالاست. با رویکردهای زمانبندی ثابت سازگار شده است. زمانبندی کاملاً آفلاین محاسبه شده و به عنوان قسمتی از ورودی سیستم به گرهها داده می شود. همه ارتباطات زمانبندی و درخواستهای زمانبندی شامل این زمانبندی هستند. گرهها ممکن است به طور همزمان زمانبندی را با زمانبندی از قبل محاسبه شده تغییر دهند.
هسته ART در فراهم کردن یک سیستم توزیعی قابل پیشبینی، قابل آنالیز و قابل اطمینان کمک میکند. این هسته از الگوریتمهای RM،EDF یا LLF برای آنالیز و تضمین فرآیندهای بلادرنگ سخت آفلاین استفاده میکند. فرآیندهای بلادرنگ سخت غیر دورهای با استفاده از زمان اجرای یک سرور قابل تاخیر زمانبندی میشوند. همه فرآیندهای دیگر با استفاده از مقدار عملکردی به صورت پویا زمانبندی میشوند [66].
با افزایش سرویسهای بلادرنگ، هستههای بلادرنگ به طور گسترده در محیط ابر مورد نیاز میشوند. با این وجود تعداد زیادی از هستهها قادر به تامین رضایت سیستمهای بلادرنگ خصوصاً سیستمهای چند هسته ای نیستند. صرف نظر از پیکربندی هستهها، قرار دادن زمانبند بلادرنگ به عنوان یک افزونه در سیستم عامل یک راهحل محسوب میشود. یک مثال RESCH برای هسته لینوکس است [67].
وقتی زمانبندها قدم به محیط ابر گذاشتند، مجازی سازی یک ابزار قدرتمند شد، ماشینهای مجازی توانستند برنامههای بلادرنگ را زمانبندی نمایند، زیرا آنها به یک پلتفرم مستقل اجازه میدهند که نرمافزار را توسعه و انزوا را بین برنامهها فراهم کنند [68].
فصل پنجم
نتیجه گیری و کارهای آینده
5-1 نتیجهگیری
با توجه به توسعه فناوری اطلاعات و ارتباطات بحثهایی مانند کاهش هزینه، کارایی و افزایش سرعت باعث ایجاد تحولی روزافزون در دنیای اینترنت شده است. محاسبات ابری شیوهای از محاسبات کامپیوتری است که قابلیتهای مرتبط با فناوری اطلاعات را به عنوان سرویس، به کاربران عرضه میکند و به آنها این امکان را میدهد تا در بستر اینترنت، بدون داشتن اطلاعات تخصصی یا کنترل کردن زیرساخت، به این سرویسها دسترسی داشته باشند. این فناوری مزایای زیادی را فراهم کرده و مورد استقبال کاربران زیادی قرار گرفته است؛ اما با معایب و چالشهایی نیز روبرو است. یکی از این چالشها، بهرهوری منابع و واگذاری کارهاست که همان مسئله زمانبندی است. زمانبندی، به معنی واگذاری کارآمد و مناسب منابع به کارها است. هدف اصلی آن، کوتاه کردن زمان تکمیل کار، بالا بردن توان عملیاتی سیستم و ایجاد تعادل بار روی منابع است. این مسئله در ابر به دلیل مقیاس بزرگ منابع، پیچیدهتر هم میشود؛ بنابراین شناخت بهتر الگوریتمها میتواند در انتخاب الگوریتم مناسب کمک زیادی کند. در این گزارش در ابتدا به معرفی رایانش ابری و خصوصیات آن و سپس به بررسی مسائل مرتبط با زمانبندی و برخی از الگوریتمهای رایج در محیط ابر پرداختیم.
5-2 کارهای آینده
رایانش ابری شیوه جدیدی از ارائه خدمات را برای کاربران در سراسر دنیا فراهم آورده است. هر دستوری که از طرف کاربران به ارائه دهندگان خدمات فرستاده شود بخشی از منابع آنها را به خود اختصاص میدهد. مسئله زمانبندی امر مهمی است و رابطه مستقیمی با سود فراهم کنندگان و هزینه کاربران دارد. در زمانبندی، مسئله هزینه اعم از هزینه زمان اجرا، هزینه مهاجرت، هزینه ارتباطی و … اهمیت زیادی دارد. انتخاب الگوریتم مناسب که بتواند باعث کاهش این هزینهها شود از جمله مواردی است که به آن توجه زیادی شده است. تحقیقات نشان میدهد استفاده از الگوریتمهای اکتشافی عملکرد بهتری نسبت به سایر الگوریتمها دارد. یکی از این الگوریتمها، PSO است و مشاهده شده که هزینه اجرای وظایف کم و وظایف برای اجرا به حداقل تعداد منابع نیاز دارند بنابراین بهرهوری منابع نیز بهتر میشود؛ اما استفاده به تنهایی این الگوریتم کافی نیست. با استفاده از الگوریتم ACO، نیز میتوان قابلیت اطمینان را تضمین و امنیت را بالا برد در ضمن زمان پاسخ و تا حدودی هزینهها را کاهش داد؛ بنابراین استفاده ترکیبی از این دو الگوریتم به همراه الگوریتم GA که سرعت نسبتاً مناسبی دارد، میتواند در طراحی یک الگوریتم موثر و کارآمد به منظور کاهش هزینه و قابلیت اطمینان در ابر مناسب باشد.
منابع
[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).
[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).
[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).
[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).
[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).
[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).
[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).
[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).
[9]. Lizheng Guo, Shuguang, shigen, changyuan, "Task Scheduling Optimization in cloud Computing based on Heuristic Algorithm", Journal of Networks, Vol 7, (2012).
[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).
[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).
[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).
[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].
[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).
[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).
[16]. Goyal A., Dadizadeh S., "A Survey on Cloud Computing", In University of British Columbia Technical Report for CS, Vol. 50,No.8, (2009).
[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).
[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).
[19]. Krutz R.L., Vines D. R, "Cloud Security: A Comprehensive Guide to Secure Cloud Computing", Wiley Publishing, Inc., (2010).
[20]. Google App Engine, http://appengine.google.com (2008).
[21]. Mather T., Kumaraswamy S, Latif Sh., "Cloud Security and Privacy", O'Reilly Media, (2009).
[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).
[23]. Jensen M., Schwenk J., Gruschka N., Iacono L., "On Technical Security Issues in Cloud Computing", IEEE International Conference on Cloud Computing, (2009).
[24]. Hawald S. C. , "Cloud Computing with Software as a Service (SaaS): How It Is Changing the Business and Organization Today", IT Today ,(2010).
[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).
[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).
[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).
[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).
[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).
[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).
[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).
[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).
[33]. Bruckner P., Scheduling algorithms, 5th Edition, Springer, 2007.
[34]. Blazewicz J., "Scheduling in Computer and Manufacturing Systems", Springer-Verlag NewYork. Secaucus, (1996).
[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).
[36]. Yu J., Rajkumar B., "Taxonomy of scientific workflow systems for grid computing", Sigmod Record, pp. 34-44,(2005).
[37]. Ullman JD., "NP-complete scheduling problems", In Journal of Computer and System sciences, pp. 384-393 ,(1975).
[38]. Workflow Management Coalition, Workflow Management Coalition Terminology & Glossary, (1999).
[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).
[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).
[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).
[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).
[43]. Sivanandam S., Deepa N., "Introduction to Genetic Algorithms", Springer Publishing Company, Incorporated, (2007).
[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).
[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).
[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).
[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).
[48]. Borthakur D., "The Hadoop Distributed File System: Architecture and Design", the Apache Software Foundation, (2007).
[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).
[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).
[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).
[52]. Dryad, Web Published, Available online at: http://research.microsoft.com/en-us/projects/dryad/[Accessed 01/03/2013], (2011).
[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).
[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).
[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).
[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).
[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).
[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).
[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).
[60]. Marco D., Birattari M., Stutzle Th., "Ant Colony Optimization", Computational Intelligence Magazine IEEE 1.4, pp. 28-39, (2006).
[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).
[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).
[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).
[64]. Uthaisombut P., "Generalization of edf and llf: Identifying all Optimal Online Algorithms for Minimizing Maximum Lateness", Algorithmica, pp. 312-328, (2008).
[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).
[66]. Tokuda H., Mercer C.W., "Arts: A Distributed Real-time Kernel", SIGOPS Operating Systems Review, pp. 29-53, (1989).
[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).
[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).
1 -Bee Colony Optimization (BCO)
2 – Quality Of Service(QOS)
3 – Genetic Algorithm(GA)
4 – Particle Swarm Optimization(PSO)
5- National Institute of Standards and Technology(NIST)
6 -Service Oriented Architecture(SOA)
7 – Software as a Service(SaaS)
8 – Platform as a Service(PaaS)
9 – Infrastructure as a Service(IaaS)
10 -Service Level Agreements(SLA)
11 -Virtual Machins(VMs)
12 -Virtual Machine Monitor(VMM)
13 -Hardware As A Service(HaaS)
14- Private cloud
15- Public cloud
16- Community cloud
17- Hybrid cloud
18 -Workflow Management System
19 -Directed Acyclic Graph(DAG)
20 – Opportunistic Load Balancing(OLB)
21 – Minimum Execution Time(MET)
22 – Minimum Completion Time(MCT)
23 – Minimum Expected Completion Times(MECT)
24 – Crossover
25 – Mutation
26 – Simulated Annealing(SA)
27 – K-Percent Best(KPB)
28 – Sufferage
29 – Hadoop
30 – Hadoop Distributed File System(HDFS)
31 -Dryad
32 -Quincy
33 – Fast Critical Path (FCP)
34 – Adaptive Generalised Scheduler (AGS)
35 – Workflow Mapping Mechanism (WMM)
36 – Adaptive Workflow Splitting (AWS)
37 – Communication-toComputation Ratio(CCR)
38- Loss and Gain Approach
39 – Ant Colony Optimization(ACO)
40 – Rate Monotonic (RM)
41 – Deadline Monotonic(DM)
42 – Earliest Deadline First(EDF)
43 – Least Laxity First (LLF)
—————
————————————————————
—————
————————————————————
ط
3
19
27
31
49