حال چند نمونه از الگوریتم‌های زمان‌بندی که در محاسبات گرید به کار گرفته می‌شود را توضیح می‌دهیم.
۲-۹-۱ الگوریتم Min-min با بار متعادل شده (LBMM^[15])
زمان‌بندی وظیفه با باری که تعادل باشد مسئله بسیار مهمی در محیط‌های محاسباتی است، الگوریتم زمان‌بندی Min-min^[16]، یک الگوریتم ساده‌ای است که یک زمان‌بندی را طوری می‌کند که مدت‌زمان اجرا را نسبت به سایر الگوریتم‌های قدیمی مینیمم می‌کند، اما در رعایت تعادل بار با شکست مواجه می‌شود، ازاین‌رو الگوریتم LBMM مطرح می‌شود که از مزایای دو الگوریتم MIN-MIN و MIN-MAX استفاده می‌کند و معایب خود را می‌پوشاند، این الگوریتم علاوه بر این‌که مدت‌زمان اجرا را به حداقل می‌رساند می‌تواند میزان بهره‌برداری از منبع را افزایش دهد.به‌طور خلاصه، LBMM دو فاز دارد، در فاز اول الگوریتم MIN-MIN را اجرا می‌کند و در فاز دوم وظایف برای استفاده کارا از منابع بهره‌برداری نشده زمان‌بندی مجدد می‌شوند.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

الگوریتم ابتدا از طریق اجرا کردن مراحل استراتژی Min-min شروع می‌شود، وظیفه‌ای که کم‌ترین زمان اجرا رادارند شناسایی می‌کند و منبع را به آن ارائه می‌دهد، یعنی اول وظیفه با کم‌ترین زمان اجرا در min-min زمان‌بندی می‌شود، پس‌ازآن این الگوریتم حداقل زمان تکمیل را بررسی می‌کند تا برخی از منابع با برخی از وظایف زمان‌بندی شوند.
با توجه به این‌که min-min ابتدا وظایف کوچک‌تر را انتخاب می‌کند، منبعی که سریع اجرا می‌کند را قبل از این‌که منابع غیرفعال دیگر را رها کند، فراخوانی می‌کند.این کار بسیار ساده و در مقایسه با دیگر الگوریتم‌ها زمان اجرای خوبی را دارد؛ بنابراین در نوبت اول LBMM الگوریتم min-min را اجرا می‌کند و در نوبت دوم منابعی با بار سنگین را انتخاب می‌کند تا مجدداً آن‌ ها را به منابعی با بار سبک واگذار کند.
۲-۹-۲ الگوریتم توزیع زمان – هزینه (DCT^[17] )
این الگوریتم مشخصات محاسبات گرید را برای سازگاری محدودیت هزینه گردش‌های کاری، توسط مصالحه هزینه و زمان اجرا با ورودی کاربر، بررسی می‌کند.
این الگوریتم روی چند نکته تمرکز می‌کند، درواقع این الگوریتم هزینه و زمان اجرا را به عنوان دو مورد مهم در نظر می‌گیرد، یعنی DCT هزینه را تحت محدودیت زمانی که کاربر می‌خواهد بین هزینه و زمان اجرا مصالحه صورت بگیرد.DCT اشتراک‌گذاری، مغایرت داشتن و رقابت سرویس‌ها را به‌وسیله چندین اجرای هم‌زمان در سکوی محاسبات گرید بسیار پویا، بررسی می‌کند.
بنابراین این الگوریتم جنبه‌های زیر را بررسی می‌کند:
۱-سابقه بارکاری: به‌منظور تخمین دقیق زمان اجرا، این سابقه هنگام محاسبه کردن زمان اجرا روی هر سرور خاصی بررسی می‌شود.
۲- تعدیل پویایی: به‌منظور پذیرش تغییرات پویای حجم کاری، بعدازاینکه وظایف روی یک سرور توزیع شدند، سرور ممکن است وظایف را هنگامی‌که با بار سنگینی مواجه می‌شوند مجدداً زمان‌بندی کند.
۳- چک کردن و زمان‌بندی مجدد کردن: به‌منظور سروکار داشتن با شکست‌های اجرا، وظایف کامل نشده با اولویت بالاتری در نوبت بعدی، مجدداً زمان‌بندی می‌شوند.
نتایج آزمایش‌ها نشان می‌دهد که این الگوریتم هزینه اجرا را به‌اندازه ۶% تقلیل می‌دهد درحالی‌که مهلت زمانی که توسط کاربر گرفته‌شده است را رعایت می‌کند و یا زمان اجرا را تقریباً ۱۹% با هزینه اجرای در نظر گرفته‌شده کاربر کاهش می‌دهد.
۲-۹-۳ الگوریتم بهینه‌سازی ازدحام ذرات(pso^[18])
buyya و همکارانش الگوریتم بهینه‌سازی ازدحام ذرات را برای زمان‌بندی برنامه کاربردی به منابع محاسباتی ارائه داده‌اند که هم هزینه انتقال داده و هم هزینه محاسبه را در نظر می‌گیرد، این الگوریتم برای برنامه‌های کاربردی گردش کاری از طریق متفاوت کردن هزینه‌های ارتباطی و محاسباتی مورداستفاده قرارمی‌گیرد. pso یک تکنیک بهینه‌سازی مبتنی بر جستجوی سراسری خود تطابقی است، این الگوریتم شبیه دیگر الگوریتم‌های مبتنی بر جمعیت از قبیل الگوریتم‌های ژنتیک است، اما هیچ ترکیب مجدد مستقیمی از اجزای جمعیت وجود ندارد، در عوض متکی بر رفتار اجتماعی ذرات است، در هر تولید، هر ذره خط مسیرش را بر اساس بهترین موقعیتش (بهترین محلی) و موقعیت بهترین ذره از کل جمعیت (بهترین سراسری) تنظیم می‌کند.
pso، برای حل مسئله np-hard از قبیل زمان‌بندی و تخصیص وظیفه به کار گرفته می‌شود، درواقع یک الگوریتم هوشمند مبتنی بر جمعیت است که بر اساس شبیه‌سازی رفتار اجتماعی حیواناتی از قبیل ماهی‌ها و پرندگان، در فضای جستجوی مسئله وقتی‌که به دنبال راه‌ حل ‌های بهینه یا نزدیک به بهینه می‌گردند، می‌باشد. موقعیت هر ذره در هرلحظه متأثر از بهترین موقعیت و موقعیت بهترین ذره در فضای جستجوی مسئله است.
در این الگوریتم هدف حداقل کردن زمان اجرا و بهبود گردش می‌باشد که متشکل از ذرات در فضای مسئله است. ذرات به‌طور تصادفی مقداردهی اولیه می‌شوند. هر ذره یک مقدار شایستگی را خواهد داشت که توسط تابع شایستگی ارزیابی می‌شود تا در هر تولید بهینه شود.
هر ذره بهترین موقعیتش و بهترین موقعیت میان تمام گروه ذرات را می‌شناسد، عملکرد ذرات توسط یک مقدار شایستگی اندازه‌گیری می‌شود.
ساختار کلی کارهایی که از pso استفاده می‌کنند معمولاً به این صورت است که ابتدا یک مدل برای نگاشت دادن وظیفه به منبع باهدفی خاص ارائه می‌شود. مثلاً هزینه نهایی اجرای گردش‌های کاری برنامه کاربردی را روی محیط‌های محاسبات گرید مینیمم کند، سپس اکتشافی طراحی می‌شود که از pso برای حل کردن مسئله نگاشت وظیفه - منبع بر اساس مدل پیشنهادشده استفاده کند. این اکتشاف، هزینه نگاشت دادن وظیفه به منبع را بر اساس راه‌حلی که تکنیک pso می‌دهد بهینه می‌کند. فرایند بهینه‌سازی از دو مؤلفه استفاده می‌کند: یک اکتشاف زمان‌بندی کردن که در یک الگوریتم لیست شده است و دو مرحله pso برای بهینه کردن نگاشت دادن وظیفه به منبع که در الگوریتم دیگری لیست شده است.پس الگوریتم pso یک نگاشت از تمام وظایف به یک مجموعه از منابع داده‌شده رابراساس مدل پیشنهادی فراهم می‌کند. نتایج آزمایش‌ها نشان می‌دهد که نگاشت منبع – وظیفه بر اساس pso، حداقل به‌اندازه سه برابر در مقایسه با نگاشت brs در هزینه صرفه‌جویی می‌کند و علاوه بر این تعادل خوبی از حجم کاری روی منابع محاسباتی را از طریق توزیع وظایف به منبع در دسترس فراهم می‌کند.
۲-۹-۴ الگوریتم زمان‌بندی منبع مجتمع و پویا (^[۱۹]daris)
daris برای زمان‌بندی مراکز داده گرید است که برخلاف الگوریتم‌های زمان‌بندی تعادل بار قدیمی که فقط یک فاکتور از قبیل بار CPU را در سرورهای فیزیکی بررسی می‌کند، daris با cpu، حافظه، پهنای باند شبکه در ماشین‌های فیزیکی و مجازی سروکار دارد.
منابعی که موردبررسی قرار گرفته‌اند عبارت‌اند از: سرور فیزیکی، کلاستر فیزیکی، سرور مجازی، کلاستر مجازی.
کارهای اصلی زمان‌بندی منبع عبارت‌اند از:
۱-درخواست‌های کاربر ۲-مدیریت زمان‌بندی کردن ۳-بازخوردها ۴-زمان‌بندی کردن اجرا ۵-به‌روزرسانی و بهینه‌سازی.
مراحل الگوریتم DAIRS عبارت است از:
۱-به دست آوردن اطلاعات مفید از دوره ملاحظه فعلی مثل بهره‌برداری از cpu، شبکه و حافظه.
۲- پذیرش درخواست وظیفه جدید.
۳- چک کردن صف انتظار.
۴- چک کردن صف درخواست.
۵- چک کردن صف بهینه‌سازی
۶- چک کردن صف پاک کردن.
۷- اجرای الگوریتم تخصیص.
۸- انتخاب کم‌ترین فرجه بهره‌برداری.
۹- اگر هیچ‌یک از سرورهای فیزیکی نتوانستند تخصیص یابند، وظیفه به‌صف توسط تابع^[۲۰]fcfs منتظر می‌ماند.
۱۰- فرایند مهاجرت.
۱۱- بعدازاینکه تمام صف‌ها چک شدند، به مرحله ۱ برمی‌گردد.
اندازه‌گیری‌های مجتمعی از سطح عدم تعادل نهایی مراکز داده گرید و هم‌چنین سطح عدم تعادل میانگین هر سرور برای ارزیابی dairs صورت گرفته است، نتایج آزمایش‌ها نشان می‌دهد که dairs عملکرد خوبی را در سطح عدم تعادل تمام سرورها و سطح عدم تعادل میانگین هر سرور دارد، علاوه بر این شامل عملکرد خوبی در زمان اجرا نیز می‌باشد.
۲-۹-۵ الگوریتم توافق زمان- هزینه (ctc^[21])
ctc، برای گردش‌های کاری گرید محدود به هزینه است، در الگوریتم ctc بین زمان و هزینه در طول پردازش زمان‌بندی کردن توافقی صورت می‌گیرد.
این الگوریتم می‌تواند به دو زیر الگوریتم تقسیم شود:
الگوریتم CTC – mc^[22] این الگوریتم هزینه را در مهلت تعیین‌شده‌ی کاربر و الگوریتم^[۲۳] ctc – mt که زمان اجرا را در بودجه تعیین‌شده‌ی کاربر به حداقل می‌رساند، هردوی این الگوریتم‌ها به کاربر اجازه می‌دهد تا یک توافق قابل‌قبول را بین زمان اجرا و سطح اجرا برقرار کنند. به‌هرحال، الگوریتم زمان‌بندی ctc یک‌قدم اولیه برای کشف و زمان‌بندی مجدد وظایفی است که به دلایل مختلفی روی سکوی محاسبات گرید شکست‌خورده و کامل نشده‌اند و یا برای توزیع وظایف به دیگر سرورهای سبک‌بار هنگامی‌که سرور میزبان با سنگینی بار مواجه می‌شود، است.
۲-۹-۵-۱ الگوریتم ctc – mc
به‌طورکلی الگوریتم زمان‌بندی ctc – mc شامل مراحل زیر است:
پیش‌گام: بررسی وظایف کامل نشده و اولین زمان‌بندی آن‌ ها در این مرحله صورت می‌گیرد.
مرحله ۱: تخصیص زیر مهلت‌ها به وظایف برای هر نمونه.
مرحله ۲: محاسبه زمان و هزینه اجرای تخمینی هر سرویس.
مرحله ۳: تخصیص وظایف به سرویس‌ها
مرحله ۴: تهیه به‌موقع گراف رابطه‌ی هزینه – زمان برای کاربر، به این منظور که به‌طور اختیاری یک مهلت توافقی به‌روز شده را برای زمان‌بندی کردن انتخاب کند.
مرحله ۵: زمان‌بندی نوبت بعدی.
در الگوریتم ctc – mc برای مرحله پیش‌گام، وظایف کامل نشده چک می‌شوند و برای اولین بار در این نوبت زمان‌بندی می‌شوند، به دلیل اینکه مقدار میانگین وظایف کامل نشده معمولاً بسیار کمتر از وظایفی است که به‌طور نرمال در مرحله بعدی می‌خواهند زمان‌بندی شوند، پیچیدگی محاسباتی این مرحله توسط مرحله بعدی پوشیده خواهد شد.برای مرحله اول الگوریتم ctc – mc، زیر مهلت‌ها را برای وظایف آخرین نمونه و وظایف نمونه‌های دیگر بر اساس آخرین نمونه محاسبه می‌کند. پیچیدگی محاسباتی O(t) را خواهد داشت، به‌طوری‌که t تعداد تمام وظایف است.