بخشی از مقاله
چکیده
محاسبات ابری الگویی از محاسبات توزیع شده، مرکب از تعداد زیادی منابع و درخواستها با هدف به اشتراکگذاری منابع به صورت سرویس، بر روی بستر اینترنت است که استفاده بهینه از آنها یک چالش بیانتها محسوب می شود. مسئله زمانبندی وظایف و جریان کار در محاسبات ابری، به دلیل لزوم استفاده بهینه از منابع محاسباتی موجوداز اهمیت زیادی برخوردار است. الگوریتمهای زمانبندی سعی دارند تا زمانبندی بهینه را جهت افزایش بهرهوری از منابع و در نتیجه افزایش توان محاسباتی، ارائه نمایند. در این مقاله انواع الگوریتمهای زمانبندی را از لحاظ سراسری و محلی، پویا وایستا، بهینه و نیمه بهینه، توزیع شده و متمرکز، همکار و غیر همکار، طبقه بندی نموده است . در نهایت الگوریتمهایی که تاکنون در این زمینه ارائه شدهاند را ارزیابی کرده و ویژگیهای مختلف آنها را همراه با ابزارها و فاکتورهای زمانبندی و غیره جدول بندی نموده است.
کلید واژه- الگوریتمهای زمانبندی وظایف، دسته بندی، محاسبات ابری، مدیریت جریان کار
.1 مقدمه
با پیشرفت شرکت های مدیریتی جهان، محاسبات ابری توجه بیشتر و بیشتری از نظر فراهم کردن زیرساخت و محاسبات انعطافپذیر و بنا به تقاضا برای تعداد زیادی از برنامههای کاربردی فراهم میکند.[1] محاسبات ابری مزایای منحصر به فرد زیادی دارد که برای تسهیل اجرای جریان کار، به کار می-رود. جریان کار یعنی خودکارسازی فرایندهایی که اسناد، اطلاعات یا وظایفشان بین مشارکت کنندهها بر اساس مجموعهای از قوانین تعریف شده ارسال میشود. یک جریان کار، امکان ایجاد ساختار برنامه های کاربردی در قالب گراف چرخهای مستقیم، که هر گره نشاندهندهی وظیفهی تشکیل دهنده و یالها نشان دهندهی وابستگیهای برنامه است، را فراهم میکند. یک جریان کار واحد معمولا شامل مجموعهای از وظایف است که هر کدام ممکن است با وظیفهی دیگری در جریان کاری مرتبط باشد جریانهای کاری چندگانه متشکل از چندین جریان کاری را است که توسط سیستمهای مدیریت جریان کار پشتیبانی میشوند.[2]
.2 لایهها و خدمات محاسبات ابری
ابرهایی که در حال حاضر استفاده میشوند بر روی مراکز داده قرار دارند، این ابرها در واقع ترکیبی از زیرساخت به عنوان سرویس - 1 - Iaas، سکو به عنوان سرویس - 2 - Paas و همچنین نرمافزار به عنوان سرویس - 3 - Saas میباشد که بدین گونه امکانات را در اختیار کاربران نهایی قرار میدهد و به ازای مقدار استفادهای که از این سرویس ها دارند از آنها هزینه دریافت میشود. در واقع محاسبات ابری علاوه بر کاربران، برای توسعه-دهندگان نرمافزار هم نیز خدمات زیادی دارد که در اینجا سه مورد از خدمات این تکنولوژی که برای توسعه دهندگان نرم افزار دارد که در شکل 10 نشان داده شده است.
-:Saas در این نوع سرویس کاربران زیادی میتوانند از نرم-افزاری که فراهمکنندهی سرویس میزبان آن است استفاده نمایند. کم شدن هزینههای خرید، نگهداری، به روز نمودن نرمافزار و خرید سخت افزار مورد نیاز از مزایای این سرویس است. از معروفترین ارائهدهندگان این سرویس میتوان گوگل داک4 را معرفی نمود.
-:Paas فراهمآورندهی بستری برای پیادهسازی نرمافزارهای مورد نیاز و در واقع پشتیبانی از چرخه کامل حیات نرمافزار برای کاربر میباشد. Google appEngin نمونهای از یک paas است.
-:Iaas در این لایه سرویسهایی مانند پردازش، فضای ذخیرهسازی، شبکه و سایر منابع محاسباتی به عنوان سرویس ارائه میشود. سرویس ذخیرهسازی آمازون 5s3 نمونه معروفی از Iaas است.
محاسبات ابری
.3 جریان کار در محاسبات ابری
انتقال جریان کاری به محیط محاسبات ابری به کار بردن سرویسهای ابری مختلف را برای تسهیل اجرای جریان کار امکان پذیر میکند. مثالهای عمومی جریان کار شامل بانکداری آنلاین، پردازش بیمه و بسیاری از کارهای دیگر می-باشد. هدف اصلی سیستم مدیریت جریان کار پشتیبانی از تعریف، اجرا، ثبت و کنترل فرایندهای کسب و کار است. در زمان اجرا یک موتور اجرای جریان کار، اجرای جریان کار را با به کار بردن میانافزارها مدیریت میکند. سه جزء اصلی در یک موتور اجرای جریان کار، زمانبندی جریان کار، اجرای جریان کار انتقال دادهها و مدیریت خطاها میباشد.[2]
زمانبند جریان کار منابع را کشف کرده و وظایف را به منابع مناسب اختصاص میدهد. انتقال دادهها برای ارتباط منابع داده و مدیریت خطا برای مدیریت خطاها در طی اجرا به کار میرود. زمانبندی جریان کار نقش حیاتی در مدیریت جریان کار ایفا میکند. زمانبندی صحیح میتواند اثر قابل توجهی روی کارائی سیستم داشته باشد. برای زمانبندی مناسب در جریان کار، الگوریتمهای زمانبندی مختلفی باید مورد بحث قرار گیرد. به طور کلی برنامهای جریان کاری به صورت یک دنباله اجرا می-شوند زیرا به صورت یک مجموعه از وظایف مختلف برای رسیدن به یک نتیجهی خاص در نظر گرفته شدهاند. وظایف بر اساس وابستگی به دادهها اجرا میشوند. آن را به صورت یک گراف در نظر بگیرید که ابتدا والدها و درنهایت فرزندان باید اجرا شوند.[3]
.4 دستهبندی الگوریتمهای زمانبندی
زمانبندی در ابر به معنی انتخاب بهترین منبع برای یک وظیفه است یا اختصاص ماشینهای مجازی به وظایف به گونهای که زمان اجرای کل به حداقل برسد. به طور کلی در الگوریتمهای زمانبندی لیستی از وظایف وجود دارد که به ترتیب اولویت برای همهی وظایف ساخته شده است. وظایف بر اساس اولویت انتخاب میشوند و به پردازندهها تخصیص داده شده که تابع هدف آنها از پیش تعیین شده است. روشهای مختلفی برای مشکل زمانبندی در سیستمهای توزیع شده وجود دارد که در شکل 11 یک طبقه بندی برای الگوریتمهای زمانبندی توزیعی ارائه شده است. .[5 ,4]
.1-4 الگوریتمهای زمانبدی ایستا و پویا
دو نوع الگوریتم زمانبندی با نامهای ایستا و پویا وجود دارد. در زمانبندهای ایستا اطلاعات لازم در مورد همه منابع در لحظهی زمانبندی موجود است به همین دلیل زمان اجرا را میتوان تخمین زد، در مقابل آن در زمانبندهای پویا ایدهی اصلی تخصیص وظایف در زمان اجرای میباشد.[6]
.2-4 الگوریتمهای زمانبندی سراسری و محلی
در زمانبندی محلی در مورد تخصیص فرایندها به یک پردازنده ولی در زمانبندی سراسری تخصیص فرایندها به چندین پردازنده تصمیگیری میشود
