Thread Scheduling Based On Multi-core Systems

Since microprocessor was born, the enhancement of its performance has been achieved by increasing its frequency, of which the upgrade requires a substantial increase of the number of the transistors, requiring more power consumptions and causing significant heat dissipation. When cpu's performance was restricted by the semiconductor craft, people turned to multi-process architecture and proposed a new concept of multi-core process.Nowadays,multicore processor has become the trend of microprocessor and the utilization of multicore technology increases the performance of microprocessors significantly. Furthermore, it puts forward higher requirements on the scheduling strategy.First, this thesis describes the background and the significance of the research, introduces briefly the basic theoretical knowledge on process, thread and multi-thread and scheduling policies on UP. After that, it outlines the implement of corresponding hardwares on mulit-core and the current study of multi-thread scheduling.And then,the O(1)scheduling algorithm and it's implementation in Linux 2.6 kernel are researched detailed.Data structure runqueue is added and it's separated into two parts:active and expired . Integrate with bitmap[],the time complexity of O(1) scheduler is reached to O(1).The reallocation of the process'timeslice becomes more timely and the calculation of process'priority becomes more simple than before. Then , it analyses the specific implementation of the SMP and focuses on the load balancing system in Linux. After that, three deficiencies of scheduler of linux2.6 are pointed out as follows: 1. no special considerations for the features of processes ,for the prices are different when migration occurs among CPUs. 2. the lack of relativity of processes dispatched by the scheduler.3. unnecessary load-balancing when the unbalance of loads is tiny in the system.Finally, this thesis proposes a general template for load balancing, which is signified with a four-dimension vector. The load balancing system of Linux is analysed according to the factors in the module, where L factor for loading evaluation and S factor for sheduling policy are concentrated. This thesis puts forward a Load balancing algorithm based on the utilization of resources for the shortages mentioned above. The algorithm selects process to be migrated by calculating the CPU utilization and memory utilization, statistic over load CPU and light load CPU, and matches the source CPU and the purpose CPU according to Donor algorithm or Receiver algorithm.