Research About Multi-core System Task Scheduling Algorithm

The development of multi-core architecture technology has brought new challenges for the design of operation system.As a key factor affecting the performance of operation system,the design and optimization of task scheduling algorithm become an important research subject of multi-core systems and cause widespread attention by scholars at home and abroad.There are two major task scheduling algorithms in Linux at present:CFS task scheduling algorithm in Linux kernel and BFS task scheduling algorithm in Android mobile operation system.Due to algorithm design,CFS has low task response speed and scheduling fairness and expensive load balance cost,BFS has long schedule time while tasks or CPU number is large and is lack of extention and not suitable for complex multi-core environment.To solve these problems,this paper presents a series of research on the design,implementation and optimization of multi-core systems.Firstly,based on CFS and BFS,this paper proposes a new task scheduling algorithm GFS.GFS improves the performance of task scheduling algorithm through CPU group configuration and awakening task schedule.First,according to the hardware characteristics of multi-core systems,GFS allows to configure a group of CPUs with close affinity to share one task runqueue automatically so that the cost of runqueue competitive access inside the CPUs of the same group and task migration inside a group and load balance between runqueues can be weighed.What's more,since tasks which frequently sleep and wake up usually demand higher response speed,GFS gives priority to awakening tasks so that interactive performance of multi-core systems will be improved.Secondly,this paper uses cache competitively access behavior of tasks to optimize GFS.Based on count of cache competitively access behavior of tasks such as L2 cache reference,L2 cache miss and load/store instructions collected by PMU,scheduling algorithm makes model and classification of cache competitively access capacity of tasks.Tasks with different cache competitively access capacity are scheduled distinguished.Task pickup policy is optimized so that two or more tasks with strong cache competitively access capacity which share L2 cache are avoided to run at the same time,load balance policy is optimized so that processors which don't share L2 cache have balanced tasks weigh balanced cache competitively access capacity.These optimizations reduce competition for cache resources and improve the cache hit rate so that operational performance of tasks is improved.Finally,benchmarks are used to test the throughput,response time and turnaround time performance of task scheduling algorithms.Test results show that GFS improves throughput by 25%in low task load environment and-4%in high task load environment,improves response time by 40%,and improves turnaround time by 17%.In a word,GFS improves performance of multi-core systems effectively.