Research On Load Balancing Scheduling Of Heterogeneous Multi-core Processors Micro-kernel System

The development trend of today's processor will be heterogeneous multi-core processors.The heterogeneous processors are more popular in the market because of theirs high flexibility,high performance and other features that other multiprocessors do not have.In the research of key technologies of heterogeneous multiprocessor systems,the dependent task scheduling problem has been proved to be an NP-complete problem.Therefore,how to explore effective task scheduling algorithms to assign tasks for the heterogeneous processors efficiently and maintain each heterogeneous processor load balance are always difficult problems for scholars.In recent years,scholars have also begun to explore effective ways to solve such problems from various heuristic intelligent search algorithms.The problem of processors load imbalance during the period of task scheduling of heterogeneous multiprocessor systems was explored and researched by this paper.The main works are shown as follows:(1)Aiming at the problem of processor load imbalance in the scheduling process for the heterogeneous multi-core processors micro-kernel system,I ameliorated the formula of ant colony algorithm to make it suitable for task scheduling and proposed a Modified Ant Colony Optimization(MACO)based task scheduling algorithm.The algorithm was changed the formula of ant colony algorithm and deleted the process of iterations of generating an approximate solution.The probability matrix is generated by the ant colony probability formula,and the relative load balancing processor-task assignment mapping table is obtained after calculation.Experiments found this algorithm could obtain better load balancing scheduling effect when the number of dependent tasks is equal to or greater than 50.(2)Aiming at the problem of MACO based task scheduling algorithm's load balancing scheduling effect is poor when the number of dependent task is less than 50,I introduced genetic combination optimization method into MACO based task scheduling algorithm and proposed a Genetic Improvement Based Ant Colony Optimization(GI-ACO)task scheduling algorithm.The algorithm was made load balancing adjustment to the processor-task assignment mapping table,which can obtain a higher processors load balance rate in the scheduling process.Experiment proves that this proposed algorithm could achieve better load balancing scheduling effect when the number of dependent tasks is less than 50.The two proposed algorithms were tested by experiments.Firstly,the DAG dependent tasks were generated by TGFF software.The MACO-based heterogeneous multi-core processors task scheduling algorithm and the List Priority Task Scheduling for Heterogeneous(LSH)algorithm were compared by simulated experiment.Secondly,I tested the GI-ACO based,MACO based and LSH task scheduling algorithms under the same conditions.The experimental results show that the two scheduling algorithms' dependent task boundary value is 50.Therefore,two proposed algorithm could be deployed in the operating system and the system could achieve optimal load balancing scheduling effect in the scheduling process by switching the two algorithms when system encounters the boundary value of dependent tasks.This study provides theoretical reference value for solving the problem of processors load imbalance in the scheduling period of heterogeneous multi-core processors micro-kernel systems.