شکل210 ساختار زمانبند غیر متمرکز [24]
2-14 انواع صفبندی کارها
صف بندی کارها میتواند دستهای و یا برخط باشد که به شرح زیر میباشد[25]:
دستهای(برون خط): در این مدل، تمام کارها و نیازمندیهایی که دارند از همان ابتدا در دسترس است و بعد از شروع کار سیستم، هیچ کاری وارد نمیشود. در این مدل زمانبندی میتواند با در نظر گرفتن تمام کارها با هم، زمان پردازش کلی برای زمانبندی را به حداقل برساند. این مدل به این دلیل که دارای محیط پویا نمیباشد برای زمان بندیهایی که به صورت دستهای عمل میکنند مناسب است.
صفبندی کارها به صورت دستهای خصوصیاتی دارد که در ادامه به آنها اشاره میکنیم:
کارها نسبت به یکدیگر دارای نیازهای پردازشی متغیر و متنوعی میباشند.
کارها برای اجرا به یکدیگر وابسته نمیباشند و به صورت مستقل از هم اجرا میشوند.
کار قابل تجزیه به عناصر کوچکتر نیست.
منبعی که به هر کار واگذار میشود تا انتهای اجرای آن کار در اختیار کار مربوطه است و قابل واگذاری به کار دیگر در حین اجرا نیست.
تخمینی از زمان اجرای هر کار روی هر منبع قبل از زمانبندی وجود دارد.
برخط: در این مدل برعکس مدل قبلی کارها در هر بازهی زمانی میتوانند به سیستم وارد شوند و هیچ محدودیتی برای زمان ورود کارها وجود ندارد. در این مدل زمانبند باید این توانایی را داشته باشد که در هر زمانی کارهای جدیدی که وارد میشوند را مدیریت کند.
2-15 پیچیدگی محاسباتی عملیات زمانبندی
مسائل زمانبندی جزء مسائل NP-Hard میباشند[26]. با داشتن m منبع و n کار تعداد حالت مختلف از واگذاری کارها به منابع را می توانیم تولید نمائیم. از اینرو با افزایش تعداد کارها تعداد نگاشتهای موجود به صورت نمایی اضافه میشوند. به عنوان مثال با داشتن 10 کار و 4 منبع تعداد 1048576 نگاشت مختلف را میتوانیم برای واگذاری کارها به منابع داشته باشیم. از اینرو سعی در تولید یک نگاشت نزدیک به بهینه داریم و نمیتوانیم حالت بهینه را برای واگذاری کارها به منابع را تولید نمائیم.
2-16 جمع بندی
با توجه به توضیحاتی که در این فصل در رابطه با الگوریتم ژنتیک و مسئله زمانبندی داده شد؛ استفاده از الگوریتم ژنتیک یکی از گزینههای مناسب، برای حل مسئله زمانبندی میباشد. در سالهای اخیر به انواع مختلف از مزایای الگوریتم ژنتیک برای حل مسئله زمانبندی استفاده شده است. در فصل سوم به بررسی الگوریتمهای مختلفی که برای حل مسئله زمانبندی ارائه شده است از جمله الگوریتمهای تکاملی مثل الگوریتم ژنتیک میپردازیم.
پیشینه پژوهشی
3-1 مقدمه
در این فصل به بررسی روشهای مختلفی که برای مسئله زمانبندی ارائه شده است میپردازیم. روشهای حریصانه و تکاملی را شرح داده و پژوهشهایی که از این روشها برای حل مسئله زمانبندی استفاده کردهاند را بیان میکنیم.
برای زمانبندی در محیط گرید میتوان از روشهای مختلفی استفاده کرد. به طور کلی روشهای موجود را به دسته الگوریتمهای حریصانه و تکاملی تقسیم مینماییم. در روشهای حریصانه با هر بار اجرا به یک نتیجه میرسیم و با سرعت مطلوبی به جواب میرسیم ولی اگر از روشهای تکاملی استفاده کنیم میتوانیم به جوابهای بهتری دست پیدا کنیم ولی باید ضرری را به واسطه اجرای طولانیتر برای زمان اجرا بپردازیم.
3-2 الگوریتمهای حریصانه
در این قسمت به بررسی چند الگوریتم حریصانه که برای حل مسئله زمانبندی استفاده میشوند میپردازیم و چگونگی تولید نگاشت کارها به منابع در هر الگوریتم را مشخص میکنیم.
الگوریتم توازن بار فرصت طلب[27]:
در این الگوریتم برای هر کار نخستین منبع بیکار (آزاد) را بدون در نظر گرفتن زمان اجرای این کار روی آن منبع، انتخاب میشود. با استفاده ازاین روش بار کاری را روی منابع مختلف پخش میکنیم ولی از لحاظ کمینه کردن زمان اتمام آخرین کار عملکرد خوبی را ندارد.
الگوریتم حداقل زمان اجرا[27]:
در این الگوریتم کارها را، بر اساس کمترین زمان اجرای مورد انتظار بدون در نظر گرفتن در دسترس بودن منبع و بار کاری جاری، اختصاص داده میشود. استفاده از این الگوریتم باعث بهبود کمینه کردن زمان اتمام کلیه کارها نسبت به الگوریتم توازن بار فرصت طلب میشود ولی مسئله پخش بار کاری در نظر گرفته نمیشود.