Article Preview
TopIntroduction
Parallelism in the computing systems can be viewed at two levels viz. hardware and software. At hardware level, it can be realized in the form of multiplicity of the processing elements and/or functional units whereas for the software level it can be seen as the multiple modules of the job demanding execution that can run in parallel. The efficiency of a parallel system is governed by the degree of matching between the hardware and the underlying software parallelism. More is this match better is the efficiency (Barney, 2012; Foster, 1995; Steen, 2012; Brucker, 2007). The job should be scheduled in such a way that no resources are underutilized and that the turnaround time is minimized. This can be ensured by exploiting the inherent parallelism in the job by distributing the entire workload on the available computational job to run simultaneously. As per (Brucker, 2007) scheduling is defined as the method by which threads, processes or data flows are given access to system resources e.g. processor time, communications bandwidth. Scheduling has been broadly classified into local and global scheduling schemes with global scheduling further divided into static and dynamic schemes. The division further extends hierarchically downward as given by Casavant and Kuhl which gives the proper picture of hierarchical division of scheduling approaches (Casavant & Kuhl, 1988). Further refinement of dynamic scheduling approaches can be seen in Singhal and Shivaratri with flat classification (Shivaratri, Krueger & Singhal, 1992). However, based on above two classifications many approaches have emerged. The core of all these approaches is to achieve the objective functions of designing an optimum schedule. Scheduling of jobs should be done in such a way that each computing node has its proper share of work so that eventually the job turnaround time can be minimized. Dynamic Scheduling is a methodology to distribute workload across multiple computers, network links, central processing units, disk drives, or other resources, to achieve optimal resource utilization, maximize throughput, minimize response time while avoiding overload (Shivaratri, Krueger & Singhal, 1992). Dynamic scheduling approaches are concerned with load balancing resulting in effective utilization of the resources. An effective dynamic scheduling is very important for a system to balance the system effectively and achieve the target quality of services while addressing issues like synchronization, communication overhead, data locality and scalability. In order to achieve the above goals dynamic scheduling must exhibit the following features (Shivaratri, Krueger & Singhal, 1992):
- 1.
Effective information policy for decimations of load information among the computing nodes;
- 2.
Effective transfer policy which will decide the number of jobs to transfer with minimization of communication delays;
- 3.
Effective placement policy as to where to allocate the process in the best possible way.
This paper presents a centralized dynamic scheduling policy based on adaptive threshold values for the job reallocations on a parallel computing system consisting of multiprocessors. As the load on the system is bound to change dynamically, defining thresholds for the workload on the system with adaptive nature is a must. The system reacts by redistributing the load as soon as these threshold values get crossed, thereby ensuring a uniform distribution of the workload. The core of the policy is its approach to bring the load around the mean of available workload, with least number of job transfers in the minimum possible time.