میانگین زمان اجرایی کار i بر روی تمام منابع موجود می باشد. تمام گره های متصل به یالهای خروجی از گره i و هزینه یال ورودی به گره j را مشخص می باشد رتبه گره آخر برابر با میانگین زمان اجرایی است (گره آخر یال خروجی ندارد).
بعد از مرحله رتبه بندی، کارها را از پایین به بالا سطح بندی می نمائیم ولی این سطح بندی از پایین به بالا صورت می گیرد در سطح اول کارهائی که دارای فرزند نیستند قرار می گیرد و در سطوح بعدی کارهایی قرار می گیرند که فرزندانشان در سطح های قبل تر قرار گرفته است. بطور مثال با توجه به گراف در شکل (۲-۷) در سطح اول فقط کار ۱۰ قرار می گیرد و در سطح دوم کارهای ۷ و ۸ و ۹ قرار می گیرد و در سطح سوم کارهای ۳، ۴، ۵ و ۶ قرار می گیرد و در سطح آخر فقط کار ۱ قرار می گیرد.
بعد از مرحله سطح بندی، از سطح آخر به سطح اول کارها را زمانبندی می نمائیم در هنگام زمانبندی کارها موجود در هر سطح، کار با بالاترین رتبه در سطح به منبعی تخصیص داده می شود که دارای کمترین زمان اتمام برای خود و فرزندانش همراه با کارهای موجود در آن سطح باشد. این روند ادامه پیدا می کند تا تمام کارها به منابع نگاشت داده شوند.
بعد از نگاشت کارها به منابع، با نظارت وضعیت منابع و کارها با رخداد رویداد تخمین نادقیق زمان اجرایی تمام کارهای که وابسته به این کار می باشند را از این زمان مطلع ساخته و در صورت امکان با انتقال آنها به فضای خالی تولید شده توسط تخمین نادقیق زمان اجرایی سعی در بهبود زمان اتمام کارها را داریم و با رخداد رویداد اضافه شدن منابع، تمام کارهایی که اجرایشان هنوز آغاز نشده است را مورد بررسی قرار داده که آیا با انتقال این کار به منبع جدید در زمان اتمامش بدون تاخیر در زمان شروع فرزندانش بهبود حاصل نمود و در صورت رخداد رویداد حذف منبع کارهای موجود در صف انتظار این منبع همراه با فرزندانشان را جمع آوری کرده و دوباره آنها را زمانبندی می نمائیم در حقیقت با این زمانبندی مجدد با حذف شدن منابع، کارها را به منابعی ارسال می کنیم که موجود هستند و قادر به اجرای کارها می باشند و در اینصورت ما می توانیم کارها را با قطعیت به اجرا برسانیم و همچنین در صورت اضافه شدن منابع با ارسال کارها به منبع جدید از میزان انتظار کارها جهت آزاد شدن منابع کاسته و همچنین باعث بهبود در زمان اجرای آخرین کار می گردیم و این خود باعث افزایش بهره وری از منابع و توازن بار می گردد. شکل (۳-۱) شبه کد الگوریتم DHLEFT را نشان می دهد.
| Input: T - Set of the jobs in the DAG R - Set of all available resources P - performance estimation matrix H - Heuristic used in scheduler ===>>> (DHLEFT) S – Schedule Set initial schedule = null While (DAG not finished) If(( == null OR any event occurred) #R is updated via the communication with Resource Manager update Resource Set R; update performance History Repository; #Predicator component will update performance estimation matrix P call P=estimate(T,R); #New schedule is made by applying the heuristics H on execution Status snapshot of and P =schedule( ,P,H); submit end If end While |
| شکل ۳-۱ : شبه کد الگوریتم DHLEFT |
فصل چهارم
نتایج حاصل از ارزیابی و مقایسه الگوریتم های پیشنهادی
۴-۱ مقدمه
در این قسمت ابتدا محک ارزیابی مورد استفاده جهت مقایسه الگوریتمهای زمانبندی کارهای مستقل با محیط ایستا و نتایج هر یک از الگوریتمها در مقایسه با الگوریتمهای دیگر بررسی میشوند و در ادامه محک ارزیابی مورد استفاده جهت مقایسه الگوریتم زمانبندی جریان کارها با محیط پویا و نتایج الگوریتم در مقایسه با الگوریتمهای دیگر بررسی میشوند. در مقایسه الگوریتمهای زمانبندی کارهای مستقل دو پارامتر را مورد توجه قرار میدهیم. پارامتر اول مقدار زمان اتمام آخرین کار میباشد. در نگاشتهای تولیدی سعی میکنیم نگاشتی از کارها به منابع را پیدا کنیم که زمان اتمام آخرین کار کمتری را داشته باشد. به دلیل اینکه در زمانبندی، تمامی منابع با هم آزاد میشوند مطلوبتر این خواهد بود که تمامی منابع تا زمان آزادی کلی، کاری برای انجام شدن داشته باشند و دارای بهره وری از منابع بالایی باشند.
۴-۲ محک ارزیابی براون
در سال ۲۰۰۱ آقای براون و همکارانش]۲۰[ به بررسی ۱۱ الگوریتم زمانبندی پرداختند و برای مقایسه این الگوریتمها محکی را تولید نمودند که از آن سال به بعد معیار ارزیابی الگوریتمهای زمانبندی در روشهای دستهای قرار گرفت. برای تولید این محک سعی شده که تا حد امکان شرایط موجود در محیط گرید برای کارها و منابع شبیهسازی شود. از جمله این موارد، میتوان به ناهمگن بودن کارها و منابع نام برد. علاوه بر این موضوع سازگار بودن یا نبودن منابع را نیز مورد بررسی قرار می دهند.
محک براون بر اساس سه معیار ناهمگنی کارها، ناهمگنی منابع و سازگاری منابع، ۱۲ نوع مختلف از ماتریس های ETC را ایجاد می کند.
هر نمونه به صورت u_x_yyzz برچسب گذاری می شود که :
u به معنای توزیع یکپارچه میباشد.
x نشان دهنده نوع سازگاری میباشد (c سازگار، i ناسازگار و s نیمه سازگار)
سازگار: اگر ماشین i کار t را سریعتر نسبت به ماشین j انجام دهد و برای کلیه کارها این شرط برقرار باشد.
نیمه سازگار: اگر شرط سازگاری برای بعضی از کارها برقرار باشد.
ناسازگار: اگر ماشین i برای بعضی کارها سریعترین و برای بقیه کارها کندترین باشد.
