بخشی از مقاله
چکیده – محاسبات ابري یکی از پدیده هاي نوظهور در دنیاي کامپیوتر و ارتباطات می باشد که می توان گفت از ترکیب علومی مانند سیستم هاي توزیع شده Grid، محاسبات عمومی و مجازي سازي مشتق شده است. محاسبات ابري منابع انواع مختلفی از منابع را مانند سخت افزار، نرم
افزار در اختیار کاربران قرار میدهد. هدف اولیه محاسبات ابري ارائه دسترسی کارا به این منابع است . زمانبندي کارها نقش کلیدي در محیط هاي ابري ایفا می کند. براي تخصیص کارها به منابع، ابر از مفهوم مجازي سازي که مقیاس پذیر است، استفاده میکند، اما زمانبندي کارها، یک مساله بزرگ است. در این بررسی ما به مطالعه انواع مختلفی از الگوریتم هاي زمانبندي کارها مبتنی بر کیفیت سرویس، اهداف و مسائل مربوط به آنها خواهیم پرداخت. این الگوریتم ها بر روي مواردي مانند تعادل بار، بهره وري منابع، حداقل زمان پاسخ و کاهش اتلاف حافظه تمرکز دارند.
کلید واژه- محاسبات ابري، زمانبندي کارها، کیفیت سرویس، تخصیص منابع، الگوریتم هاي زمانبندي.
-1 مقدمه
محاسبات ابري یک تکنولوژي جدید است که سرویس هـاي بی شماري از طریق مراکز ابر ارائه می کند. بـا محاسـبات ابـري کاربران می تواننـد قـدرت محاسـباتی و ذخیـره سـازي خـود را افزایش دهند.[1] در محیط هاي ابري کاربران می تواننـد بـدون نقض توافق سطح خـدمات(SLA)1 ، از منـابع بـه صـورت کـارا و مــوثر اســتفاده کننــد. هــدف اصــلی SLA، تــامین کیفیــت سرویس(QOS)2 تحویل منابع به کاربران است.[1]
QOS، میزان رضایتمندي کاربران از خدمات ارائـه شـده در محیط محاسبات ابري، تعریف میشـود. QOS، بـا انـدازه گیـري کیفی پارامترهایی مانند زمان اتمام کار، زمان پاسـخگویی، تـوان عملیاتی، قابلیت اطمینان بیان می شود .[2]
1 Service Level Aggreement 2 Quality Of Service
مدیریت کیفیت سرویس در محیط محاسـبات ابـري، بحـث مهم و جذابی براي محققان به چند دلیل است: اول اینکه محیط محاسبات ابري بسیار پویا و متغیر است، بنابراین تـامین کیفیـت سرویس بدون استراتژي براي مـدیریت کیفیـت سـرویس بسـیار مشکل است. دوم اینکه محیط محاسبات ابـري یـک مـدل بـازار محور است، بنابراین حفظ کیفیت بالاي سرویس به منظور بهبود رضایت مشتري و اجتناب از پرداخت جریمه بخاطر نقص خدمات الزامی است.[5]
زمانبندي کارها بحث مهمی است که به طور آشکارا، کارایی محیط هاي ابري را تحت تاثیر قرار می دهد. ارائه دهندگان ابر و کاربران اهداف و نیازمندي هاي مختلفی دارند. بحث کلیدي ایـن است که چگونه کارها زمانبندي شوند تا به صورت کارا و معقـول از منابع استفاده کنند که هم نیازهاي کاربران و هم اهداف ارائـه دهندگان ابر با توجه به QOS بر آورده شود.[4]
در ادامـه، بخـش هـاي بعـدي ایـن مقالـه بـه ایـن شـکل سازماندهی می شود:
در بخش 2 مقدمه اي از مفاهیم زمانبندي بیان میکنیم. در بخش 3 انواع روش هاي زمانبندي را بررسی میکنیم. در بخـش
4 به بررسی و مقایسه چندین الگوریتم زمانبندي کارها مبتنی بر کیفیت سرویس که پارامترهاي مختلفی را مورد توجه قرار دادند، خواهیم پرداخت و نهایتاً در بخش 5 نتیجه گیري و کارهاي آتی بیان می شود.
1
Most Fit Task Scheduling
-2 زمانبندي
زمانبندي به مجموعه اي از قوانین و سیاست ها براي کنترل ترتیب انجام کارها توسط سیستم کامپیوتري گفته می شود. انواع مختلفی از الگوریتم هاي زمانبندي در سیستم هاي توزیـع شـده وجــود دارد و زمانبنــدي کارهــا یکــی از آنهاســت.[3] مســاله زمانبندي کارها بحث مهمی است که به کارایی کـل محـیط ابـر مربوط می شود. بخاطر تنوع پارامترهاي کیفیت سـرویس ماننـد سرعت CPU3 ، بهره وري CPU، زمان پاسخ، تـوان عملیـاتی و...
زمانبنــدي کارهــا در محــیط محاســبات ابــري از محــیط هــاي محاسباتی توزیع شده معمولی متفاوت است. تقاضا براي منابع به صورت پویا درحال نوسان است بنابراین زمانبندي کارهـا مبتنـی بر کیفیت سرویس براي بهره وري کارا از منابع و تـامین رضـایت نیازهاي کاربر ضروري است. مزیت اصلی الگوریتم هاي زمانبندي رسیدن بـه کـارایی بـالاي محاسـباتی و بهتـرین تـوان عملیـاتی سیستم است.[4]
مسألهي زمانبندي در محیط محاسبات ابري امروزه به یکـی از مهم ترین چالش ها در بحث محاسبات ابري تبدیل شده است.
در سیسـتم محاسـبات ابـري، تخصـیص منـابع بـه پروسـه هـا، وظیفهي مهمی است که بر عهـدهي زمانبنـد مـیباشـد. بـا ایـن وضعیت، الگوریتم هاي زمانبندي نقش بسیار مهمی را بازي مـی کنند چرا که هدف از انجام زمانبندي در بسیاري از سیستم هاي محاسبات ابري این است که زمان را کاهش داده و بهـره بـرداري منبع را بهبود بخشد.[6]
الگوریتم هاي زمانبندي کار در محیط ابر را می تـوان بـه دو دسته اصلی تقسـیم کـرد: Batch Mode Heuristic Scheduling Algorithm(BHMA) و Online Mode Heuristic Scheduling .Algorithm
در BHMA کارها زمانیکه وارد سیستم میشوند بـه صـورت
یک صف در یک مجموعه جمع آوري میشوند و زمانبندي بعد از یک مدت زمان ثابت شروع میشود. الگوریتم هـاي First Come First Served(FCFS)، Round Robin(RR)، Max-Min و Min-Min مثالهایی از نوع هستند. در روش Online کارهـا بـه محـض ورود به سیستم، زمانبندي میشوند. این روش براي محیط هـاي ابري با سیستم هاي ناهمگون که سرعت پردازنده ها در آن بسیار
متغیر است، مناسب است. الگوریتم
