محاسبات توزیع‌شده سنگین از ساده‌ترین کارهای اجراشده بر روی گرید است.

۲-۴ محاسبات گرید و نیاز به زمان‌بندی

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

الگوریتم‌های زیادی در رابطه با نحوه زمان‌بندی وظایف در سیستم‌های توزیعی و نیز محیط گرید ارائه شده‌اند[۱۱,۱۲,۱۳,۱۴,۱۵,۱۶,۱۷,۱۸]. هدف این الگوریتم‌ها، بهینه‌سازی عاملی از Qos و مغایرت معیارهای کیفی می‌باشد که این الگوریتم‌ها، سعی دارند آن‌ ها را بهینه‌سازی کنند. به عنوان‌مثال حداقل زمان اجرایی از دید یک سرویس‌دهنده توزیع بار به صورت متعادل در بین منابع وازدید یک سرویس‌گیرنده گرید محاسباتی، وظیفه یک محموله‌ی ایده آل می‌باشد. مشکلی که وجود دارد، توزیع نمودن متعادل بار بین منابع و زیر وظایف با در نظر گرفتن بهره‌وری منابع است [۱۱,۱۳,۱۵,۱۷]. بحث افزونگی در اختصاص دادن منابع به وظایف با به حداقل رساندن هزینه اجرای وظایف در تضاد است و این لزوم افزایش قابلیت اطمینان در شبکه می‌باشد.

در این مقاله، سعی بر این شده است که الگوریتمی کارآمد، برای توزیع نمودن زیر وظیفه‌ها در محیط گرید که هدف کاهش زمان اجرای وظایف و همچنین توزیع نمودن متوازن بارکاری در بین منابع و با بهره گرفتن از شبکه های صف ارائه شده است.

۲-۵ کارهای مرتبط

معمولاً زمان‌بندها سعی می‌کنند پارامترهای کیفیت سرویس را افزایش دهند. در مکان‌های مختلف جغرافیایی منابع گرید، توسط سازمان‌های مختلفی که زیر نظر سیاست‌های مختلفی اداره می‌شود، قرار دارد. جهت افزایش کارایی گرید ما به یک زمان‌بندی کارآمد احتیاج داریم. پویایی کارایی منابع ناشی از ناهمگونی خودمختاری و اشتراکی بودن منابع گرید است. هدف مسئله زمان‌بندی گرید، انتصاب بهینه کارها به منابع است.

X.He و همکاران او با بهره گرفتن از تغییر در الگوریتم Min-Min (الگوریتمی ‌در مورد زمان‌بندی وظایف در گرید)، روش جدیدی را ارائه داده‌اند که این روش پیشنهادی علاوه بر مزایای الگوریتم Min-Min دارای Qos بهینه‌ای در رابطه با تخصیص پهنای باند می‌باشد. الگوریتم مذکور با قائل شدن تفاوت برای وظایفی که نیاز به پهنای باند زیادتری هستند نسبت به وظایفی که پهنای باند در آن‌ ها مهم نیست، توانست یک الگوریتم سیستم‌گرا را باهدف افزایش توان عملیاتی سیستم گرید ارائه دهد. ما در این بحث ‌در مورد سیستم‌های توزیعی و تخت شبکه صحبت می‌کنیم و صرفاً خاص محیط گرید نمی‌باشد.A. Afzal و همکاران او، با کمک گرفتن از تئوری صف، الگوریتمی در جهت کاهش هزینه اجرای برنامه ها در محیط گرید ارائه داده‌اند. این الگوریتم سیستم‌گرا است که به موارد، عامل‌های کارایی و بهره‌وری، پارامتر هزینه (که در محیط‌های گرید تجاری مطرح است)، پرداخته است.

شکل ۲-۲- فرایند فیلتر کردن منبع [۱۰]

A: یک الگوریتم برای تولید فرایند و تخصیص منبع به آن

۱-فرآیندها را تولید می‌کند.

۲- RP فرایند را با توجه به فرمول محاسبه می‌کند.

۳- یک لیست از فراهم‌کنندگان منبع را که با بهره گرفتن از الگوریتم UM1 انتخاب‌شده‌اند را آماده می‌کند.

۴- فراهم‌کننده منبعی را انتخاب می‌کند که شرایط زیر را داشته باشد:

• • فراهم‌کنندگان منبع منابع درخواستی قابل‌دسترسی را داشته باشند.

• • فراهم‌کننده منبع بالاترین RP را داشته باشد.

• • فراهم‌کننده منبع بالاترین فاکتور قابلیت اطمینان را داشته باشد.

• • فراهم کنند منبع میان فراهم‌کنندگان انتخاب‌شده فعال‌ترین باشد.

• جستجوی بین فراهم‌کنندگان تا زمان پیدا کردن فراهم‌کننده‌ای که همه شرایط بالا را داشته باشد ادامه دارد.

۵- فرایند به فراهم‌کننده منبع انتخاب‌شده اختصاص می‌یابد.

پایان الگوریتم:

B: الگوریتم برای اجرای فرایند روی منبع و به‌روزرسانی RP ها.

۱- برای تمام فراهم‌کنندگان منبع و برای یک فراهم‌کننده منبع، مرحله ۲-۵ تکرار می‌شود تا جایی که تمام منابع اختصاص‌یافته اجرا شوند.

۲- یک فرایند از فرآیندها را واکشی می‌کند و به‌صف منبع وارد می‌کند.

۳- RP های تخصیص داده‌شده به فرآیندها توسط مصرف‌کنندگان بازبینی می‌شود. مقدار RP با یک مقدار منفی در صورت عدم تطابق و با یک مقدار مثبت اگر اطلاعات خوب باشد به‌روزرسانی می‌شود.

۴- اجرای فرایند آغاز می‌شود.

۵- اگر اجرا نیازمندی‌های زیرساخت، مهلت زمانی و درخواست‌های کیفیتی سرویس را برآورده کند، بعداً RP های فرایند به RP موجود فراهم‌کننده منبع اضافه می‌شود، در غیر این صورت RP فراهم‌کنندگان منبع کم می‌شود. از نتایج شبیه‌سازی نتیجه می‌گیریم که این استراتژی خطاهای ممکن را کاهش می‌دهد. در آزمایش‌ها از سیاست مدیریت مطمئن استفاده می‌کنیم، خطاها به میزان ۱۳% خطاهای کلی در مقایسه باسیاست‌های بدون مدیریت مطمئن کاهش می‌یابد. نتایج نشان می‌دهد که متد پیشنهادشده به طور قابل توجهی، تعداد شکست‌ها را در مقایسه با یک الگوریتم زمان‌بندی توزیع‌شده‌ای که بدون قابلیت اطمینان و سیاست مدیریت مطمئن اجرا می‌شود کاهش می‌دهد.

شکل ۲-۳ نتایج سیاست مدیریت درست زمان‌بندی [۷]

۲-۶ گردش‌کاری

یک گردش کاری، اتوماسیونی از پردازش‌ها است که به صورت کلی و جزئی در جریان اسناد، اطلاعات، یا وظایف از یکی به دیگری عبور می‌کند، بر اساس یک مجموعه از قوانین رویه‌ای، گردش‌کاری انجام می‌شود تا یک هدف کلی به دست آید. این گردش‌های کاری را می‌توان با DAG مدل‌سازی کرد[۱۱].