Article Preview
Top1. Introduction
In computing, scheduling is the scheme by which individual task by a few means is allocated to resources that complete the task. The task may be virtual computation elements such as threads, processes or data flows, which are in turn scheduled onto hardware resources such as processors, network links or extension cards. In other hands, scheduling is the process of allocating jobs in a particular way, mainly with the reference of sequence of their coming time or according to their computational time. An excellent scheduling strategy facilitates in growing the efficiency of a system performance and in utilization of available resources in the best possible way. A scheduler is what carries out the scheduling action. Schedulers are often executed so they stay all calculate resources busy (i.e., load balancing); allow several users to share system resources effectively, or to achieve an aim quality of service. But multiprocessor scheduler has to decide which process to run and which CPU to run it on. This additional dimension greatly complicates scheduling on multiprocessor systems. However, multiprocessor scheduling (MPS) algorithm is an NP-hard optimization problem. A scheduling algorithm (SDA) is the algorithm which states how much CPU time is assigned to Processes and Threads. The main aim of every scheduling algorithm is to complete a number of criteria: reduce the makespan or scheduling length, execution time and maximization of speedup. SDA can be classified as; deterministic and non-deterministic scheduling algorithm. In Deterministic scheduling, the scheduler has an exact knowledge of the all jobs properties beforehand such as data are dependent or independent between the tasks, running time, etc., Deterministic scheduling problem is also known as NP-Complete (Singh et al., 2015). In Non-deterministic scheduling (NDS), the scheduler has no idea of the all jobs properties because it takes decisions during run time and scheduling is based upon on dynamic parameters which change during run time while deterministic scheduling is used on static parameters. NDS algorithm can apply on heterogeneous system (HES) or homogeneous system (HOS). Therefore, multiprocessor system (MTS) is either HES or HOM (Samad et al., 2016).
1.1. Heterogeneous System
HES can be defined as the interconnection of a number of processors, having dissimilar computational speed, and are joined with dissimilar speed links used for solving group of problems which have dissimilar computational necessities. All the processors in this type of computing system, usually incorporates specialized processing capabilities and thus tasks are allocating to them accordingly. Heterogeneity can be planned in two types, such as, Functional- level heterogeneity and Performance – level heterogeneity (Alam et al., 2015; Karimi et al., 2009). In functional – level heterogeneity systems combine general use processors, likes vector units, floating-point co-processors and input/output processors. But all tasks may not be running on all functional units. In performance – level heterogeneity, system contain several interconnected common – use processors of varying speed. HES are commonly appropriate in the commercial and scientific research fields where, real-time security, robustness and high performance, is the main priority. A few examples of heterogeneous system are High Performance Computing (Cray XD1, SRC -6 and SRC-7) etc.