Grid computing is the advanced computing technique which lead to evolution of new revolutionary parallel processing concept. Grids are a form of distributed computing whereby a "super virtual computer" is composed of many networked loosely coupled computers acting together to perform large tasks. Most important task which determines the efficiency of parallel processing using grid computing is the scheduling policy used. Scheduling algorithms is the topic of concern since 1990s. Different scheduling algorithms have different advantages over other depending upon different situations. Priority algorithm is quite good because job are scheduled in accordance to the sequence of the priority. Jobs can be given priority according to the requirement and situations.The traditional priority algorithm schedule the jobs in accordance to the priority, jobs with higher priority is executed before the jobs with lower priority. If enough processors are not available, the incoming job must wait for some currently running job to terminate and free the processors. All subsequent jobs also wait so in order of the priority. This may lead to a waste of processing power as processors sit idle waiting for enough of them to accumulate.
FlexPrio scheduling algorithm is an optimization that tries to balance between the goals of utilization and maintaining priority order. It also ensure that higher priority jobs must not be starved in addition to high compaction and resource utilization.
KEYWORDS: Priority, Job Scheduling, Upper Bound, Grid Computing.
INTRODUCTION
COMPUTATION Grid technologies [1] are a latest trend and appear as a next generation of the distributed heterogeneous system. It combines physical dynamic resources and various applications. It can be used as potential technology that leads to the effective utilization of the idle resources. The complex problems such as financial modeling, earthquake simulation, climate/weather modeling and business need to utilize the huge resources. Therefore, grid can open the occlude path and can be considered as an ultimate solution to solve these problems. Scheduling algorithm is the most important issue of current implementation of grid computing. Typically, application of grid computing concept requires a set of jobs, where each job is considered as the atomic unit of computation [2]. Berman, Fox and Hey (2002) described scheduler as a responsible component of grid computing which selects the best suitable machines or computing resources among different distributed resources for processing jobs to achieve high system throughput. It suggests the important of job scheduling algorithm in grid computing. Therefore job scheduling algorithm must be capable enough to schedule the jobs with minimum expenses and maintain the balance with current status of the environment. As environment status may change frequently, traditional job scheduling algorithm such as First Come First Serve (FCFS), Shortest Job First (SJF), etc., may not be suitable for the dynamic environment in grids. Different algorithms have different advantages over other. Priority algorithm can be viewed as a key to schedule jobs according to our requirement because it schedules the jobs in order of the priority, all we have to do is to set the priority of jobs according to demand of the situation. Jobs with higher priority is executed before other jobs with lower priority. It may run smooth if enough processing capability is available to run the jobs, otherwise the incoming job must wait for higher priority job to complete its execution. All subsequent jobs also wait so in order of the priority. There may be the possibility that other job with relative lower priority and lower computinal requirement can complete its execution in available resource. The proposed 'FlexPrio' algorithm is focused to remedies this major drawback of traditional priority based algorithm. Proposed algorithm is explained in detail in Section III.
This paper is organized as follows. Section II, discusses related work, Section III the proposed algorithm and its model, Section IV presents experimental evaluation and Section V gives conclusion and future work and lastly, the references.
RELATED WORK
While executing the jobs over the grid, at times there are jobs which has to be executed first than others i.e. these jobs are of higher priority. For executing priority based jobs there were few algorithms proposed like Efficient Utilization of Computing Resources Using Highest Response Next Scheduling in Grid (HRN) [3]. This algorithm provides more responses with time, memory and CPU requirements. In this jobs are allocated to the number of processors based on the job's priority and processor's capability. The HRN is adaptive for local jobs as well as for remote jobs without the loss of performance and also highly adaptive for working in grid environment. The HRN removed the weakness of both First Come First Serve (which schedules job in order of there arrival) and Shortest Job First (SJF) but it had the weakness that, it also has higher turnaround time and both CPU and memory wastage. This algorithm is not well focused on high compaction i.e. maximum resource exploitation. Another job scheduling algorithm which gives better performance than some other traditional algorithms in terms of turnaround time and average waiting time is Optimal Resource Constraint (ORC) algorithm [4] allocates the jobs according to capability of processor. It applies best fit algorithm followed by Round Robin (RR) scheduling which distributes the jobs among the available processors. However it has communication overhead. Hierarchical Job Scheduling for Clusters of Workstations (HJS) [5] used hierarchical approach using two level scheduling consisting of global scheduling and local level. The global scheduler uses single or separate queue for different type of the jobs each queue exploits different scheduling policy (FCFS, SJF or First Fit). The local scheduler uses only one queue and one policy (FCFS, SJF or FF) for all types of jobs. The global scheduler has a many functions. One of these is suitable job-resource matching. Another is to obtain the best utilization of the available clusters. The use of SJF can result in extreme delays for long running jobs. As it is strongly biased against large number of jobs so there may be starvation problems, it is expensive to implement as job-resource matching is time consuming process.
PROPOSED ALGORITHM
FlexPrio algorithm provide flexibility to priority of jobs in order to give chance to lower priority jobs in case when higher priority job couldn't be executed in left amount of resources. In addition to effective utilization of resources it also ensures that jobs must not be starved in any case.
Input job_MI for n jobs;
Sort jobs in order of their priority
Mini_job:= job with minimum computational requirement MI
Input R_MIPS for all resources;
//MI (Million Instructions) gives computational capability of the resource.
Declare available = R_MI;
Input U_bound;
For (int i: =1; i <= n; i++)
{
If (available >= job_MI[i])
{
Allocate resouce to job //CPU allocation is in accordance of priority.
Available = available - job_MI[i];
}
Else if (available >= Min_job && U_bound > 0)
//to check whether enough computational capability is available to process lower priority job with minimum computational requirement.
{
For (int j= i+1;j<=n;j++)
{
If(job_MI[j]<= available )
{
Allocate resource to job[j];
U_bound --;
}//end
}//end for
}//end else
}// end for
Proposed algorithm initially schedule the jobs using traditional priority based algorithm. When it finds that next job can't be accommodated in left resource. Scheduler finds next job that can be accommodated in left resource. Before scheduler finds such job it has to undergo a check shown in step 8.f. This step has following to functions
Check whether currently available resource is capable enough to process Min_job. (available >= Min_job)
Ensure that high priority job must not wait more than a given amount of time.
(U_bound > 0)
Here Min_job denote job with minimum computational requirement and U_bound denote upper bound of the number of lower priority jobs that can be allocated resource before a higher priority job is scheduled.Thus it is clear that proposed algorithm provide flexibility in priority in accordance to demand of situation. In addition to preventing starvation of low priority job (problem in traditional priority) it also ensure that high priority job should not be starved.
Following fig.1 provide a clear comparison between traditional job scheduling policy and proposed job scheduling policy. We can see that using FlexPrio algorithm it is possible to achieve high compaction. Compaction can be termed as percentage of the time for which the resources are been used respect to the overall execution time. Thus, the higher the compaction degree is, the more exploited and less idle the resources are [6].
4. EXPERIMENTAL EVALUATION
GridSim simulation toolkit was to create the simulation environment. GridSim supports modeling and simulation of heterogeneous Grid resources, users and application models. It can be used to creation of application tasks, mapping of tasks to resources, and their management [7]. A simulation was conducted in heterogeneous environment where each cluster has machines having different characteristics. The processing time and compaction degree is taken into account to analyze the feasibility and to verify the improvement of proposed model over other traditional scheduling strategies.
Figure Simple view compaction difference between traditional algorithms and FlexPrio algorithm
Figure : Compaction Degree in Different Algorithms
Note: First Come First Served (FCFS), Short Jobs First (SJF), Priority Based Scheduling (PBS), Big Jobs First (BJF).
In this experimental study we defined a set of five synthetic workloads composed by 8 jobs each of different characteristics of computational requirements as in the previous experimental study. Then, the first workload WL-1 was designed to perform well with the techniques that try to match the available resources with the processing requirements. WL-2 was well focused to study traditional priority based scheduling in comparison to proposed policy. WL-3 to WL-5, designed without taking any particular criteria into account. Compaction degree is shown in following fig.3. It can be observed that each technique has a different behavior. Some techniques perform well in some situations but may have lower compaction degree thus, wastage of resources. But FlexPrio obtained good compaction results, irrespectively on the workload nature. Thus, by defining the correct job execution order and task to resource allocation, it is possible to obtain the better scheduling decisions that increasing the compaction degree and improving the resources usage.
Following table shown in fig.4 provide comparison of proposed algorithm with traditional FCFS and Priority based algorithms obtain in experimental conditions.
Number of jobs
Processing time
FlexPrio
FCFS
Priority based Scheduling
100
54
64
72
200
101
160
130
300
148
226
177
400
190
291
235
500
251
320
290
Figure : Comparison of proposed algorithm with other traditional algorithms
Note: above shown result is obtained at Upper bound = 20 % of total number of jobs
Figure : Comparison of Processing Time for Number of Jobs at different Upper Bounds
Figure : Snapshot at different values of Jobs at different upper bound
