زمان بندی کارها یک فرایند کلیدی است که هدف آن، اجرای درخواست های وارد شده به سیستم، بروی منابع، به شیوه ای کارآمد، با در نظر گرفتن سایر خصوصیات محیط ابر می باشد. زمان بندی کارها، ماشین های مجازی را به عنوان واحدهای زمان بندی، جهت تخصیص منابع فیزیکی ناهمگون برای اجرای کارها در نظر می گیرد. هر ماشین مجازی یک واحد انتزاعی از ظرفیت های محاسباتی و ذخیره سازی تهیه شده در ابر می باشد. زمان بندی درست می تواند روی عملکرد سیستم تاثیر بسیار خوبی داشته باشد. الگوریتم زمان بندی کارا می تواند نیازمندی های کاربر را برآورده کند، و بهره وری منبع را بهبود بخشد، به موجب آن عملکرد کلی محیط ابرهای محاسباتی را افزایش می دهد]۳۴.[
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
۲-۳-۲ الگوریتم های زمان بندی در ابرهای محاسباتی
مسئله زمان بندی کارها به معنای نگاشت و تعیین ترتیب اجرای کارها بر روی منابع موجود است، به گونه ای که یک یا چند معیار کارآیی بهینه شوند. این مسئله جزو مسائل شناخته شده NP-کامل محسوب می گردد.
بنابراین هیچ الگوریتم شناخته شده با مرتبه زمانی چندجمله ای وجود ندارد، که بتواند جواب بهینه ای برای این مسئله پیدا کند. علاوه براین، مسئله زمان بندی در سیستم ابرهای محاسباتی به دلیل برخی از خصوصیات خاص آن همچون ناهمگونی، استقلال، و پویایی منابع، به مراتب پیچیده تر از سیستم های سنتی است. تحقیقات زیادی بر روی مسئله زمان بندی کارها در سیستم ابرهای محاسباتی انجام گرفته که در ادامه برخی از آنها را مورد بررسی قرار خواهیم داد. الگوریتم های زمان بندی ارائه شده به دو دسته پویا و ایستا تقسیم می گردند، مزیت الگوریتم های ایستا در آن است که می توانند با بهره گرفتن از امکان رزرو پیشاپیش منابع، مانع از ایجاد تاخیر در اجرای کارها گردند. معمولا هدف الگوریتم های ارائه شده حداقل کردن زمان اجرای برنامه است، بدون اینکه هیچ تضمین خاصی در مورد سقف زمان اجرا به کاربر داده شود (زمان بندی حداکثر تلاش). اما مسئله هنگامی پیچیده تر می شود که بحث کیفیت خدمت نیز مطرح گردد. در این مسئله، محیط ابرهای محاسباتی از چندین عرضه کننده تشکیل می گردد که هریک منابعی را در اختیار کاربران قرار می دهند. هریک از این منابع قادرند یک یا چند کار را با کیفیت خدمت متفاوت (همانند زمان اجرا، امنیت و قیمت متفاوت) اجرا نمایند. در زمان بندی مبتنی بر کیفیت خدمت، زمان بند باید به گونه ای عمل کند که حداقل کیفیت خدمت موردنیاز کاربر برآورده شود. به عنوان مثال کاربر مایل است که کارهای وی قبل از مهلت معین و با حداقل قیمت اجرا شود. اکنون زمان بند باید با توجه به زمان اجرا و قیمت پیشنهادی هر منبع برای هریک از کارها، منابع را به گونه ای انتخاب کند که کل کار در مهلت تعیین شده پایان یابد و قیمت نیز حداقل گردد. نکته ای که به پیچیدگی مسئله می افزاید این است که نحوه محاسبه کیفیت خدمت کل برنامه از روی کیفیت خدمت هر کار برای معیارهای مختلف، متفاوت است. به عنوان مثال برای قیمت برابر با حاصل جمع قیمت کارها، برای زمان اجرا برابر با زمان طولانی ترین مسیر بین کار ابتدایی و پایانی (مسیر بحرانی) برنامه، و برای قابلیت اطمینان برابرحاصل ضرب قابلیت اطمینان هر کار است. همان طور که قبلا نیز اشاره شد، این مسئله جزو مسائل چند هدفه یا چند معیاری می باشد و به دلیل پیچیدگی مسئله، الگوریتم های چندانی برای آن پیشنهاد نشده است. علاوه براین، اکثر محققین از روش های فوق ابتکاری همانند الگوریتم های ژنتیک برای حل آن استفاده کرده اند که زمان اجرای آنها معمولا طولانی است. اما به دو دلیل برای حل این مسئله نیاز به الگوریتم هایی داریم که زمان اجرای کوتاهی داشته باشند. دلیل اول آن است که در محیط های پویا همانند سیستم ابرهای محاسباتی، وضعیت منابع به سرعت تغییر می کند. بنابراین چنانچه زمان اجرای الگوریتم زمان بندی بالا باشد، ممکن است در این مدت وضعیت بسیاری از منابع تغییر کرده و از دسترس خارج شده باشند. دلیل دیگر آن است که معمولا زمان اجرای کارها یکی از پارامترهای مهم کیفیت خدمت برای کاربران است، و در بسیاری از موارد مهلت زمانی مشخصی برای اجرای برنامه وجود دارد. لذا بالا بودن زمان اجرای الگوریتم زمان بندی، باعث بالا رفتن زمان کل اجرای کار می شود که ممکن است باعث اجرا نشدن کار در مهلت مقرر شود. بنابراین به نظر می رسد برای حل این مسئله باید به دنبال الگوریتم های ابتکاری با مرتبه زمانی مناسب، و زمان اجرای کوتاه باشیم. از طرف دیگر، بسیاری از محققین از مدل زمان بندی ایستا برای زمان بندی مبتنی بر کیفیت خدمت استفاده کرده اند. با توجه به اینکه رزرو پیشاپیش منابع روش مناسبی برای تضمین کیفیت خدمت موردنیاز کاربران می باشد، به نظر می رسد زمان بندی ایستا کارآیی بهتری برای زمان بندی مبتنی بر کیفیت خدمت داشته باشد.
در خصوص مسئله زمان بندی، راهکارهای متعددی ارائه شده است: الگوریتم حریص^[۳۹] ، دوره گرد^[۴۰]، سیستم صف^[۴۱]، رزرو پیشرفته و پیش بینی زمان بندی^[۴۲]. اغلب این الگوریتم ها معیارهایی همچون، نرخ بهره وری استفاده از منابع، توازن بار و لزوم پاسخ دهی سریع به درخواست ها را در نظر نمی گیرند.
برای حل مسائل NP- کامل اغلب از الگوریتم های تکاملی و مکاشفه ای گوناگون استفاده می شود. برای حل مسائل زمان بندی در محیط های توزیع شده نیز از الگوریتم هایی مانند: Simulated Annealing، Tabu Search و Genetic algorithm بهره گرفته شده است]۸.[
الگوریتم های زمان بندی پارامتر های مختلفی، از قبیل سرعت، میزان بهره برداری از منبع، هزینه، عملکرد، مقیاس پذیری، قابلیت اطمینان، مدت زمان اجرا، دسترس پذیری و نرخ موفقیت زمان بندی را دارند]۳۴[.
حال به بررسی جنبه هایی از مسئله می پردازیم که بر روی فرایند زمان بندی تاثیر می گذارند:
اولین ویژگی در فرایند زمان بندی، تعدد معیارها است که بر این اساس مسائل زمان بندی به دو گروه تقسیم می گردند:

• • تک معیاره: بهینه سازی تنها برای یک معیار صورت می پذیرد.(معمولا زمان اجرا)

• • چند معیاره: زمان بند سعی می کند چندین معیار را به طور همزمان بهینه نماید.

بدیهی است که زمان بندی چند معیاره به مراتب پیچیده تر بوده ونیاز به استفاده از روش های بهینه سازی چند هدفه دارد. ویژگی بعدی میزان پویایی زمان بندی است، این ویژگی به رابطه بین فرایند زمان بندی و اجرای کار می پردازد. بدین معنا که آیا زمان بندی پیش از اجرای کار صورت می پذیرد، یا به طور همزمان با آن. براین اساس روش های زمان بندی به سه دسته تقسیم می گردند:

• • پویا: در این روش زمان بندی هر کار زمانی صورت می پذیرد که آماده اجرا باشد.

• • ایستا: در این روش پیش از شروع کار، زمان بندی به طور کامل صورت می پذیرد.

• • زمان بندی ترکیبی: این روش ترکیبی از دو روش فوق است. به این معنا که زمان بندی قسمتی از کار از پیش صورت می پذیرد، و به محض اتمام این قسمت، زمان بندی قسمت بعدی آغاز می گردد.

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

• • منابع همگون: در این مدل کلیه منابع ویژگی های ایستا و پویای یکسانی دارند (یعنی نوع، کارآیی، بار و … آنها مشابه است).

• • منابع ناهمگون: در این مدل منابع مختلف، دارای ویژگی های متفاوتی هستند.

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

• • غیر چند برنامه ای: در این مدل زمان بند در هرلحظه تنها می تواند یک کار را به یک منبع محاسباتی ارسال نماید.

• • چند برنامه ای: در این مدل زمان بند قادر است چندین کار را به طور همزمان بر روی یک منبع محاسباتی زمان بندی نماید.

از آنجا که بیشتر سیستم های فعلی، بر پایه سیستم های مدیریت منابع محلی بنا شده اند که از مدل غیر چند برنامه ای حمایت می کنند، تقریبا تمامی الگوریتم های زمان بندی کارها، بر پایه مدل غیر چند برنامه ای هستند.
کار الگوریتم های زمان بندی در ابرهای محاسباتی را می توان به دو گروه اصلی طبقه بندی کرد. الگوریتم حالت دسته ای برنامه ریزی اکتشافی (BMHA) و حالت برخط الگوریتم های اکتشافی. در BMHA، کار ها در مجموعه ی زمانی که به سیستم می رسند در صف جمع آوری می شوند. الگوریتم زمان بندی پس از یک دوره ثابت از زمان شروع خواهد شد.
نمونه های اصلی از الگوریتم هایی که بر اساسBMHA هستند؛ الگوریتم زمان بندی FCFS ، الگوریتم زمان بندی دوره گرد^[۴۳] (RR)، الگوریتم min-min و الگوریتم max-min. در الگوریتم زمان بندی حالت اکتشافی برخط، کارها هنگامی که به سیستم می رسند زمان بندی می شوند. از آنجا که محیط ابر یک سیستم ناهمگن است و سرعت هر پردازنده به سرعت تغییر می کند، الگوریتم های زمان بندی حالت اکتشافی برخط برای یک محیط ابر مناسب تر می باشد.
الگوریتم FCFS کارها در یک صف قرار می گیرند و به ترتیب ورود سرویس می گیرند، این الگوریتم سریع و ساده است.
الگوریتم RR فرآیندها در یک روش FIFO اعزام می شوند اما یک مقدار محدود از زمان پردازنده به نام زمان برش یا کوانتومی داده شده است. اگر یک فرایند کامل نباشد، قبل از آنکه زمان پردازش آن تمام شود، پردازنده پیش دستی می کند و به فرایند بعدی در صف می رود و فرایند کامل نشده را در پشت لیست آماده قرار می دهد.
الگوریتم min-min کارهای کوچک را انتخاب می کند تا ابتدا اجرا شوند، اما کارهای بزرگ می توانند تاخیر طولانی داشته باشند.
الگوریتم max-min کارهای بزرگ را انتخاب می کند تا ابتدا اجرا شوند، اما کارهای کوچک می توانند تاخیر مدت طولانی داشته باشد.
الگوریتم زمان بندی اولویت^[۴۴] به هر فرایند یک اولویت اختصاص می دهد و این اولویت برای اجرای مجاز است، فرآیندهای با اولویت برابر به ترتیب FCFS زمان بندی می شوند. کوتاهترین کار اول (SJF)^[45] انجام می شود، این الگوریتم حالت خاصی از الگوریتم زمان بندی اولویت کلی می باشد. یک الگوریتم SJF به سادگی یک الگوریتم اولویت است که در آن اولویت معکوس (پیش بینی شده) پشت سر هم CPU بعدی برود. به این معنا که، هرچه بیشتر پشت سر هم باشند در CPU، اولویت پایین تر است و بالعکس. اولویت می توانند به صورت داخلی و یا خارجی تعریف شده باشد. اولویت های تعریف شده داخلی از برخی از مقادیر قابل اندازه گیری و یا کیفیت برای محاسبه اولویت یک پردازنده استفاده می کنند.
۲-۳-۲-۱ مروری بر الگوریتم های زمان بندی حداکثر تلاش
زمان بندی حداکثر تلاش سعی دارد یک معیار را (که معمولا زمان اجرای کار می باشد) بهینه نماید، بدون اینکه هیچ تضمینی در مورد آن معیار به کاربر بدهد. اولین الگوریتم ها از این دسته در دهه ۱۹۶۰ میلادی ارائه شده اند. تا پایان دهه ۱۹۹۰ اکثر الگوریتم ها برای سیستم های چندپردازنده ای همگون (سیستم هایی که در آنها همه منابع یکسان هستند) پیشنهاد گردیده اند.]۱۹، ۳۴[
۲-۳-۲-۲ الگوریتم زمان بندی آگاه از منبع
الگوریتم زمان بندی آگاه از منبع^[۴۶] (RASA) از مزایای دو الگوریتم Min-Min و Min-Max استفاده می کند که ابتدا زمان اتمام کارها روی هر یک از منابع که در دسترس هستند را تخمین می زند، سپس الگوریتم های Min-Min و Min-Max متناوب بکار می گیرد. نتایج آزمایشات بکارگیری RASA در زمان بندی کارها مستقل حاکی از این است که قابلیت اجرای RASA در بدست آوردن زمان بندی با مدت زمان اجرای کمتر بطور قیاسی خوب است و نسبت به الگوریتم های زمان بندی موجود در سیستم های توزیع شده مقیاس بزرگ قدم را فراتر نهاده است. اما از جمله معایب این الگوریتم می توان به نادیده گرفتن نرخ ورود کار، هزینه های اجرای کار در هر یک از منابع و هزینه های ارتباطی در زمان اجرای هر کار اشاره کرد.
۲-۳-۲-۳ قیمت گذاری بر اساس فعالیت بهبود یافته (ABC)
این الگوریتم یک الگوریتم زمان بندی مبتنی بر هزینه بهبود یافته برای نگاشت موثر کارها به منابع در دسترس ابری است که هم هزینه منبع و هم هزینه عملکرد محاسباتی را در نظر می گیرد و نرخ ارتباطات/ محاسبه را از طریق گروه بندی کارهای کاربر، براساس توانایی پردازش یک منبع ابری خاص و فرستادن کارهای گروه بندی شده به منبع، بهبود می بخشد. هدف الگوریتم حداقل کردن زمان تکمیل کار نهایی و حداقل کردن هزینه است.
۲-۳-۲-۴ بهینه سازی ازدحام ذرات^[۴۷] (PSO)
این الگوریتم برای کارها از طریق متفاوت کردن هزینه های ارتباطی و محاسباتی مورد استفاده قرار می گیرد. در این الگوریتم هدف حداقل کردن زمان اجرا و بهبود انجام کار است. نگاشت منبع-کار بر اساس PSO در هزینه صرفه جویی می کند و علاوه بر این تعادل خوبی از حجم کاری روی منابع محاسباتی را از طریق توزیع کارها به منابع در دسترس فراهم می کند.
۲-۳-۲-۵ الگوریتم توافق زمان-هزینه^[۴۸] (CTC)