Implementation of MaxMin Algorithm using Multilevel Queue

Abstract

The Focus of this work is on the independent task assignment problem which often occurs in applications related to heterogeneous computing system. For  heterogeneous computing systems there are certain  algorithms from which  MaxMin and MinMin  are used mostly, however these algorithms has disadvantage of starvation i.e. in case of MinMin the jobs with max(MCT) are beenn waiting list leading to starvation the same case arises in MaxMin algorithm where min(MCT)  jobs are starved .  The objective of assigning each task to a processor in such a way that will result in minimum turnaround time (make span). To solve the problem  related to MinMin and MaxMin scheduling algorithm is that jobs with min(MCT) is executed and jobs with  max(MCT) is executed respectively. We are proposing an algorithm for implementation of Heuristics MaxMin algorithm using multi-level queue for improving the performance of Task Assignment. For this implementation we are using Linux OS and multithreading and mutli-queuing concepts of Linux. Our initial finding is to overcome Starvation of job with minimum (MCT) in MinMin algorithm and vice versa in MaxMin. By implementing above concept we conclude that performance of the system will increase exponentially which was linear in traditional method as well as by isolating the system job and non-system jobs will reduce not-responding cases.