Abstract
Scheduling tasks on heterogeneous resources distributed over a grid computing system is an NP-complete problem. The main aim for several researchers is to develop variant scheduling algorithms for achieving optimality, and they have shown a good performance for tasks scheduling regarding resources selection. However, using of the full power of resources is still a challenge. In this paper, a new heuristic algorithm called Sort-Mid is proposed. It aims to maximizing the utilization and minimizing the makespan. The new strategy of Sort-Mid algorithm is to find appropriate resources. The base step is to get the average value via sorting list of completion time of each task. Then, the maximum average is obtained. Finally, the task has the maximum average is allocated to the machine that has the minimum completion time. The allocated task is deleted and then, these steps are repeated until all tasks are allocated. Experimental tests show that the proposed algorithm outperforms almost other algorithms in terms of resources utilization and makespan
چکیده
زمانبندی وظایف در منابع ناهمگن که در یک سیستم محاسبات شبکه ای توزیع شده اند، یک مساله NP-کامل است. هدف اصلی بسیاری از محققان، توسعه الگوریتم های زمانبندی متنوع برای بهینه سازی این کار است، و این الگوریتمها در زمانبندی وظایف با توجه به انتخاب منابع عملکرد خوبی داشته اند. اما استفاده از توان کاملِ منابع هنوز هم یک چالش محسوب میشود. در این مقاله یک الگوریتم اکتشافی جدید به نام Sort-Mid ارائه میشود. هدف این الگوریتم، حداکثر کردن استفاده از ماشینها و حداقل کردن makespan است. استراتژی جدید Sort-Mid پیدا کردن منابع مناسب است. مرحله اصلی، میانگین گیری بوسیله لیست مرتب سازیِ زمان تکمیل هر وظیفه است. سپس بیشترین میانگین به دست می آید. در نهایت، وظیفه ای که بیشترین میانگین را دارد به ماشینی اختصاص مییابد که کمترین زمان تکمیل را دارد. وظیفه ی اختصاص داده شده حذف میشود، و این مراحل تا زمانی که تمام وظایف تخصیص یابند، تکرار میگردد. آزمایشات نشان می دهند که کارایی الگوریتم پیشنهادی از نظر استفاده از منابع و makespan تقریباً از الگوریتم های دیگر بیشتر است.
-1مقدمه
سیستم های محاسبات شبکه [1،2]، سیستم های توزیع شده ای هستند که اشتراک منابع بزرگ را بین میلیونها سیستم کامپیوتری در یک شبکه جهانی مانند اینترنت امکانپذیر میسازند. منابع شبکه به دلیل پویایی، ناهمگن بودن، و توزیع جغرافیایی با منابع سیستم های پردازشی توزیع شده ی معمولی تفاوت دارند. زیرساخت شبکه (گرید) چهار سطح دارد. اول: سطح مبنا که از مولفه های فیزیکی تشکیل شده است. دوم: سطح میان افزار که در واقع نرم افزارِ مسئولِ مدیریت منابع، اجرای وظایف، زمانبندی وظایف، و امنیت است. سوم: سطح سرویس (خدمات) که خدمات کارامدی را به فروشندگان/کاربران ارائه میکند. چهارم: سطح کاربرد که شامل خدماتی مانند ابزارهای عملیاتی و کسب و کار است.
زمانبندی به یکی از موضوعات تحقیقاتی اصلی تبدیل شده است زیرا بر کارایی اپلیکیشن های شبکه تاثیر مستقیم دارد. زمانبندی وظایف [3] مرحله اصلی مدیریت منابع شبکه است و با استفاده از الگوریتمها و سیاست های زمانبندی، کارها را مدیریت میکند تا به منابع مناسب تخصیص یابند. در زمانبندی ایستا فرض میشود اطلاعات تمام منابع و تمام وظایف، هنگام زمانبندی اپلیکیشن مشخص است. علاوه براین، هر وظیفه یک بار به یک منبع اختصاص مییابد. اما در زمانبندی پویا، تخصیص وظیفه همزمان با اجرای اپلیکیشن انجام می شود و تعیین زمان اجرا در آن ممکن نیست. وظایف به صورت پویا وارد میشوند و زمانبند باید برای تخصیص منابع، تصمیمات سختی بگیرد. مزیت زمانبندی پویا نسبت به زمانبندی ایستا این است که لازم نیست سیستم، رفتارِ زمان اجرای اپلیکیشن را قبل از اجرای آن بداند…