کاهش زمان پاسخ و دریافت جواب نهایی یک برنامه.
انجام یک برنامه که اجرای آن از توانایی‌های یک معماری (ترتیبی یا موازی) خارج است.
محاسبات توزیع‌شده سنگین از ساده‌ترین کارهای اجراشده بر روی گرید است.
۲-۴ محاسبات گرید و نیاز به زمان‌بندی
گرید محاسباتی راهکاری برای گریز از پرداخت هزینه‌ی گزاف جهت استفاده از ابرکامپیوترها و به‌کارگیری توان محاسباتی شبکه‌ی گسترده‌ای از کامپیوترها می‌باشد. گرید محاسباتی با بهره گرفتن از قدرت پردازش کامپیوترهای موجود در شبکه خود و همچنین از طریق اشتراک‌گذاری منابع، سعی در بهینه‌سازی مسائل پیچیده و زمان‌بر دارد[۱]. نحوه‌ی توزیع کردن زیر وظایف در بین منابع و زمان‌بندی کردن آن‌ ها برای استفاده از حداکثر منابع موجود در محیط محاسبات گرید بسیار مهم است. شکستن وظایف و توزیع آن‌ ها بین منابع، بر عهده‌ی سیستم مدیریت منابع(Resource Management System) است. این سیستم وظایف را از کاربر گرفته و آن‌ ها را به زیر وظیفه‌هایی تقسیم می‌کند و سپس این زیر وظایف را با توجه به مشخصات و خصوصیات منابع، بین آن‌ ها توزیع می‌کند[۲,۳,۴,۵,۶,۷]. ازجمله‌ی این وظایف می‌توان به برنامه‌های توزیعی اشاره کرد که برای اجرا در قالب یک وظیفه و توسط کاربر به سیستم مدیریت منابع ارجاع می‌شوند. انتساب وظایف به منابع در بازه‌های زمانی مشخص را زمان‌بندی وظایف می‌نامند. الگوریتم‌های زمان‌بندی، وظیفه‌ی توزیع زیر وظایف بین منابع محاسبات گرید را بر عهده‌دارند. این نوع از زمان‌بندی مسلماً سطح کیفیت سرویس^[۱۴] را در نظر می‌گیرد تا انجام شود و سعی بر این دارد که در حین زمان‌بندی، زیر وظایف به نحوی در بین منابع پخش شوند که حداکثر Qos حاصل گردد [۸,۹,۱۰]. تعداد پارامترهای دخیل در Qos بسیار زیاد می‌باشند که از آن جمله می‌توان به قابلیت اطمینان، دسترس‌پذیری، توان عملیاتی، امنیت، امکان استفاده و کارایی اشاره کرد[۸].

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

الگوریتم‌های زیادی در رابطه با نحوه‌ی زمان‌بندی وظایف در سیستم‌های توزیعی و نیز محیط گرید ارائه‌شده‌اند[۱۱,۱۲,۱۳,۱۴,۱۵,۱۶,۱۷,۱۸]. هدف این الگوریتم‌ها، بهینه‌سازی عاملی از Qos و مغایرت معیارهای کیفی می‌باشد که این الگوریتم‌ها، سعی دارند آن‌ ها را بهینه‌سازی کنند. به‌عنوان‌مثال حداقل زمان اجرایی از دید یک سرویس‌دهنده توزیع بار به‌صورت متعادل در بین منابع وازدید یک سرویس‌گیرنده‌ی گرید محاسباتی، وظیفه‌ی یک محموله‌ی ایده آل می‌باشد. مشکلی که وجود دارد، توزیع نمودن متعادل بار بین منابع و زیر وظایف با در نظر گرفتن بهره‌وری منابع است [۱۱,۱۳,۱۵,۱۷]. بحث افزونگی در اختصاص دادن منابع به وظایف با به حداقل رساندن هزینه‌ی اجرای وظایف در تضاد است و این لزوم افزایش قابلیت اطمینان در شبکه می‌باشد.
در این مقاله، سعی بر این شده است که الگوریتمی کارآمد، برای توزیع نمودن زیر وظیفه‌ها در محیط گرید که هدف کاهش زمان اجرای وظایف و همچنین توزیع نمودن متوازن بارکاری در بین منابع و با بهره گرفتن از شبکه‌های صف ارائه‌شده است.
۲-۵ کارهای مرتبط
معمولاً زمان‌بندها سعی می‌کنند پارامترهای کیفیت سرویس را افزایش دهند. در مکان‌های مختلف جغرافیایی منابع گرید، توسط سازمان‌های مختلفی که زیر نظر سیاست‌های مختلفی اداره می‌شود، قرار دارد. جهت افزایش کارایی گرید ما به یک زمان‌بندی کارآمد احتیاج داریم. پویایی کارایی منابع ناشی از ناهمگونی خودمختاری و اشتراکی بودن منابع گرید است. هدف مسئله زمان‌بندی گرید، انتصاب بهینه کارها به منابع است.
X.He و همکاران او با بهره گرفتن از تغییر در الگوریتم Min-Min (الگوریتمی در مورد زمان‌بندی وظایف در گرید)، روش جدیدی را ارائه داده‌اند که این روش پیشنهادی علاوه بر مزایای الگوریتم Min-Min دارای Qos بهینه‌ای در رابطه با تخصیص پهنای باند می‌باشد. الگوریتم مذکور با قائل شدن تفاوت برای وظایفی که نیاز به پهنای باند زیادتری هستند نسبت به وظایفی که پهنای باند در آن‌ ها مهم نیست، توانست یک الگوریتم سیستم‌گرا را باهدف افزایش توان عملیاتی سیستم گرید ارائه دهد. ما در این بحث در مورد سیستم‌های توزیعی و تخت شبکه صحبت می‌کنیم و صرفاً خاص محیط گرید نمی‌باشد.A. Afzal و همکاران او، با کمک گرفتن از تئوری صف، الگوریتمی در جهت کاهش هزینه‌ی اجرای برنامه‌ها در محیط گرید ارائه داده‌اند. این الگوریتم سیستم‌گرا است که به موارد، عامل‌های کارایی و بهره‌وری، پارامتر هزینه (که در محیط‌های گرید تجاری مطرح است)، پرداخته است.

شکل ۲-۲- فرایند فیلتر کردن منبع [۱۰]
A: یک الگوریتم برای تولید فرایند و تخصیص منبع به آن
۱-فرآیندها را تولید می‌کند.
۲- RP فرایند را با توجه به فرمول محاسبه می‌کند.
۳- یک لیست از فراهم‌کنندگان منبع را که با بهره گرفتن از الگوریتم UM1 انتخاب‌شده‌اند را آماده می‌کند.
۴- فراهم‌کننده منبعی را انتخاب می‌کند که شرایط زیر را داشته باشد:
فراهم‌کنندگان منبع منابع درخواستی قابل‌دسترسی را داشته باشند.
فراهم‌کننده منبع بالاترین RP را داشته باشد.
فراهم‌کننده منبع بالاترین فاکتور قابلیت اطمینان را داشته باشد.
فراهم کنند منبع میان فراهم‌کنندگان انتخاب‌شده فعال‌ترین باشد.
جستجوی بین فراهم‌کنندگان تا زمان پیدا کردن فراهم‌کننده‌ای که همه شرایط بالا را داشته باشد ادامه دارد.
۵- فرایند به فراهم‌کننده منبع انتخاب‌شده اختصاص می‌یابد.
پایان الگوریتم:
B: الگوریتم برای اجرای فرایند روی منبع و به‌روزرسانی RP ها.
۱- برای تمام فراهم‌کنندگان منبع و برای یک فراهم‌کننده منبع، مرحله ۲-۵ تکرار می‌شود تا جایی که تمام منابع اختصاص‌یافته اجرا شوند.
۲- یک فرایند از فرآیندها را واکشی می‌کند و به‌صف منبع وارد می‌کند.
۳- RP های تخصیص داده‌شده به فرآیندها توسط مصرف‌کنندگان بازبینی می‌شود. مقدار RP با یک مقدار منفی در صورت عدم تطابق و با یک مقدار مثبت اگر اطلاعات خوب باشد به‌روزرسانی می‌شود.
۴- اجرای فرایند آغاز می‌شود.
۵- اگر اجرا نیازمندی‌های زیرساخت، مهلت زمانی و درخواست‌های کیفیتی سرویس را برآورده کند، بعداً RP های فرایند به RP موجود فراهم‌کننده منبع اضافه می‌شود، در غیر این صورت RP فراهم‌کنندگان منبع کم می‌شود. از نتایج شبیه‌سازی نتیجه می‌گیریم که این استراتژی خطاهای ممکن را کاهش می‌دهد. در آزمایش‌ها از سیاست مدیریت مطمئن استفاده می‌کنیم، خطاها به میزان ۱۳% خطاهای کلی در مقایسه باسیاست‌های بدون مدیریت مطمئن کاهش می‌یابد. نتایج نشان می‌دهد که متد پیشنهادشده به‌طور قابل‌توجهی، تعداد شکست‌ها را در مقایسه با یک الگوریتم زمان‌بندی توزیع‌شده‌ای که بدون قابلیت اطمینان و سیاست مدیریت مطمئن اجرا می‌شود کاهش می‌دهد.

شکل ۲-۳ نتایج سیاست مدیریت درست زمان‌بندی [۷]
۲-۶ گردش‌کاری
یک گردش کاری، اتوماسیونی از پردازش‌ها است که به‌صورت کلی و جزئی در جریان اسناد، اطلاعات، یا وظایف از یکی به دیگری عبور می‌کند، بر اساس یک مجموعه از قوانین رویه‌ای، گردش‌کاری انجام می‌شود تا یک هدف کلی به دست آید. این گردش‌های کاری را می‌توان با DAG مدل‌سازی کرد[۱۱].
در ابتدا گردش‌های کاری در گریدها پیاده‌سازی می‌شدند، به علت کاهش عملکرد گریدها نیاز شده که گردش‌های کاری در ابرها پیاده‌سازی شوند، مزیت اصلی حرکت به سمت ابرها مقیاس‌پذیری برنامه‌های کاربردی است. مقیاس‌پذیری منابع گرید، امکان‌پذیری منابع را جهت برآورده شدن نیازهای گرید، فراهم می‌کند؛ و این سیستم‌ها مدیریت گردش‌کاری را قادر می‌سازد تا به‌سرعت نیازمندی‌های کیفیت سرویس Qos برنامه کاربردی را فراهم کند، برخلاف رویکردهای سنتی که رزرو کردن پیشرفته منابع در محیط‌های گرید چندمنظوره را می‌طلبد، سرویس‌های گرید از قبیل منابع محاسباتی، پهنای باند و ذخیره‌سازی اساساً با هزینه‌های کمتری در دسترس هستند. برنامه‌های کاربردی گردش‌کاری، اغلب محیط‌های اجرای خیلی پیچیده‌ای را نیاز دارند.
۲-۷ زمان‌بندی گردش‌کاری
به عبارت ساده فرایند نگاشتن وظایف به منابع محاسباتی در یک گردش کاری، برای انجام، اجرای وظایف و بدون به هم خوردگی وابستگی بین آن‌ ها را زمان‌بندی گردش‌کاری می‌نامند.یکی از موضوعات مهم در مدیریت گردش‌کاری، زمان‌بندی گردش‌کاری، به‌ویژه در سیستم‌های گریدمی باشد. زمان‌بندی گردش‌کاری فرآیندی است که نگاشت و مدیریت اجرای وظایف وابسته به یکدیگر را روی منابع توزیع‌شده انجام می‌دهد، یعنی منابع مناسب را به وظایف گردش‌کاری اختصاص می‌دهد، ازاین‌رو اجرای می‌تواند کامل شود و توابع هدف قانع‌کننده‌ای توسط کاربران وضع شود.زمان‌بندی درست می‌تواند روی عملکرد سیستم اثر شدیدی داشته باشد، مسئله نگاشت کارها به منبع محاسباتی متعلق به کلاسی از مسائل است که به NP-Complet معروف می‌باشد[۱۵].
هدف زمان‌بندی کردن کار نگاشت کارها به منابع فیزیکی مشخص است، این نگاشت تلاش می‌کند که تابع هزینه مشخص‌شده توسط کاربر را مینیمم کند، در زمان‌بندی برای رسیدن به راه‌حل بهینه یا نزدیک به مطلوب ابتکارات مختلف ممکن است مورداستفاده قرار گیرد، محاسبه کارا و زمان‌بندی کردن کار به‌سرعت به یکی از چالش‌های اصلی در محاسبات گرید تبدیل‌شده است که برای موفقیت حیاتی می‌باشد، سیستم زمان‌بندی در شکل زیر آمده است:

شکل ۲-۴ اهداف زمان‌بندی گردش کاری [۷]
اهداف زمان‌بندی یک گردش‌کاری در هر برنامه کاربردی می‌تواند متفاوت باشد، اغلب گردش‌های کاری برنامه‌های کاربردی با این هدف زمان‌بندی می‌شوند تا هزینه و/ یا زمان انتقال داده، فضای ذخیره‌سازی استفاده‌شده، زمان اجرای نهایی و یا ترکیبی از این‌ها را به حداقل برساند.
زمان‌بندی وظیفه (فعالیتی که از مجموعه‌ای از ورودی‌ها استفاده می‌کند تا مجموعه‌ای از خروجی‌ها را تولید کند) یکی از مسائل بهینه‌سازی مشهور است و نقش کلیدی را در بهبود انعطاف‌پذیری و قابلیت اطمینان بازی می‌کند، در کل می‌خواهیم که وظایف زمان‌بندی شوند تا با منابع مناسب در زمان مناسب مطابق باشند و این شامل پیدا کردن توالی صحیح در وظایف است.
در رویکردهای زمان‌بندی، دو پیکره‌بندی مهم وجود دارد که استاتیک و دینامیک نامیده می‌شوند. هر دو محدودیت‌هایی رادارند، معمولاً مکانیسم دینامیک عملکرد بهتری را در مقایسه با استاتیک دارند، اما مقدار بالاسری زیادتری دارند، در استاتیک، تمام اطلاعات از قبل شناخته‌شده‌اند و وظایف بر اساس دانش قبلی تخصیص‌یافته‌اند و متأثر از حالت سیستم نخواهند شد ولی در مکانیسم دینامیک وظایف به پردازنده‌ها به‌طور پویا به‌محض اینکه وارد می‌شوند اختصاص می‌یابند.
۲-۸ پارامترهای الگوریتم‌های زمان‌بندی
الگوریتم‌های زمان‌بندی موجود پارامترهای متفاوتی دارند از قبیل مقیاس‌پذیری، توان خروجی، سرعت، برقراری تعادل بار میان منابع و بهره‌وری منابع را در همه منابع ماکزیمم کند تا توان خروجی سراسری افزایش یابد؛ اما بسیاری از آن‌ ها دو پارامتر قابلیت اطمینان و دسترس‌پذیری را نادیده گرفته‌اند.
الگوریتم زمان‌بندی کارا می‌تواند نیازمندی‌های کاربر را برآورده کند و بهره‌وری منبع را بهبود بخشد، به‌موجب آن عملکرد کلی محیط محاسبات گرید را افزایش می‌دهد. فاکتورهای مختلفی در الگوریتم‌های زمان‌بندی وجود دارد، درواقع برخی از معیارها متداول هستند مثل حداقل کردن زمان اجرا، متعادل کردن بار و توزیع خوب حجم کاری روی منابع، کاهش هزینه‌های محاسباتی و ارتباطی، کاهش پیچیدگی محاسباتی، افزایش توان خروجی و میزان بهره‌برداری از منبع و غیره.
خوب است بدانیم نرم‌افزارهای مختلفی نیز برای شبیه‌سازی محیط‌های گرید وجود دارد، از نرم‌افزارهایی مثل OpenNebule، Eucalyptus، Cloudsim و SwinDew-c برای پیاده‌سازی الگوریتم‌ها استفاده می‌شود، این‌ها بسیار مفید هستند، چراکه شرایط لازم برای تست الگوریتم‌های زمان‌بندی دریک محیط کنترل‌شده و تکراری را فراهم می‌کنند. محیط شبیه‌سازی توانایی مدل‌سازی، شبیه‌سازی و آزمایشات زیرساخت‌های محاسباتی و سرویس‌های برنامه کاربردی را دارد
۲-۹ چند نمونه الگوریتم زمان‌بندی معروف در زمینه‌ی محاسبات گرید
ازآنجایی‌که زمان‌بندی گردش‌کاری یکی از موارد کلیدی در مدیریت اجرای گردش‌کاری در محیط محاسبات گرید است، چند مورد از الگوریتم‌های زمان‌بندی موجود در محیط محاسبات گرید را مرور کرده و پارامترهای مختلف آن‌ ها را موردبررسی قرار می‌دهیم.وظایف معمولاً بر اساس درخواست‌های کاربر زمان‌بندی می‌شوند، لازم است که الگوریتم‌های زمان‌بندی جدیدی برای غلبه بر مسائلی که مطرح می‌شود، ایجاد شود، الگوریتم‌های زمان‌بندی جدید ممکن است از برخی مفاهیم زمان‌بندی قدیمی استفاده کنند و آن‌ ها را با برخی استراتژی‌های آگاه شبکه ادغام کنند تا راه‌ حل‌ هایی را برای زمان‌بندی کار بهتر و مؤثرتر فراهم کنند.