In heterogeneous distributed computing schedulingof tasks plays an essential role.
By allocating the task to thesuitable processor the overall performance of the systemincreases because the execution time and communication delaywill be minimized. For task scheduling, different schedulingtechniques are discussed in this paper. Further, multi-level queue(MLQ) algorithm for task scheduling is discussed in detail. Themain objective MLQ for task scheduling is in terms of time span,complexity, resource utilization and system throughput.Index Terms—Distributed systems, Heterogeneous distributedsystem, Task scheduling.I. INTRODUCTIONNrecent years with the advancement of the technology weare surrounded by different multimedia devices like smartphones, smart TVs, tablets, computers and in variousdomains like education, health, scientific research etc.
Moreover, a large amount of heterogeneous data (audio,images, videos) is created and stored in a reliable and secureheterogeneous distributed system. Heterogeneous distributedsystems (HDS) are the combination of the cloud system,mobile system, desktop systems etc. HDS can handle thecurrent challenges of heterogeneous data in a limited amountof time 1, 2. In this context, dynamic resource distributionis a challenging task 2. Many times by allocating the tasks tothe unsuitable resources in HDS the execution of task fails 2.Also, a group of task can be represented by the directedacyclic graph (DAG) in which node represents the task anddirected edges represents the task dependencies andcommunication cost. Task scheduling is NP-hard problem ingeneral cases but by imposing some restriction task schedulingcan be solved in polynomial time 3.
It is a challenging taskfor HDS to assign task to suitable resource in order tominimize the makespan by imposing restriction. Therefore, inrecent years researchers have proposed many algorithms tosolve the DAG problem for task scheduling 5.Dynamic scheduling and static scheduling are the maincategories of these proposed methods. In dynamic schedulingtasks relation, completion time and communication are notknown in advance while in static scheduling tasks relation,completion time and communication time is known. Staticscheduling can be solved in polynomial time, and iscategorized in to two groups: heuristic scheduling and metaheuristic scheduling 4.Heuristic scheduling based on the application characteristicand depends on the effectiveness of the heuristics. Thesealgorithms use greedy heuristics approach and give the nearoptimal solution in polynomial time. But for complex DAGscheduling problems the result of heuristic algorithms is notconsistent.
On the other hand, meta heuristic approach uses theguided strategy which focus on the more promising searchspace and produce the optimal solution but with exponentialtime complexity. Meta heuristic approach first selects theinitial solutions and then selects step by step solution to reachthe desirable solution. The most popular examples of metaheuristic approach aregenetic algorithm, ant colonyoptimization, simulated annealing etc. 6, 7, 8.In distributed system resources are shared among differentnodes and these nodes also share their local resources in orderto complete the task in minimal time. Generally, anapplication is divided into smaller subtasks. These subtasksthen run on different processors concurrently according totheir dependent relationship of tasks 5.
In this paper, for taskscheduling problem in heterogeneous distributed system thetechnique of multi-level queue (MLQ) is purposed 11.The remainder of this paper is described as follows. SectionII describes the literature review, section III contains the detailof one selected algorithm. Finally section IV concludes thepaper.II. LITERATURE REVIEWThe min-min algorithm starts with the set of tasks T and Mset of machines.
The algorithm select the task according toexecution time and all tasks run on the all the machines, thenthe task with minimum completion time for its execution isselected and assign to the corresponding machine. Next, thattask is removed from the set and next task with minimum timeis selected. This process continuous until all the tasks isfinished.
Here, the completion time of the tasks are calculatedon all the machines and then task with maximum minimumtime is selected and assign to respective machine. The timecomplexity of min-min algorithm is O(MT2). Here, M is thenumber of machines and T is number of tasks.