Linux Kernel Scheduler Analysis And Simulation

Operating System scheduler is one of the most hot spots that for system performance improvement.Linux,as a mainstream operating system,showing excellent performance after improving for many times.It plays an important role in a growing number of areas gradually.The simulator based on linux scheduling algorthm is extremely rare,and most of them have disadvantage in simulate the scheduling process of linux.This paper analyzed three important scheduling algorithm in the history of the development of linux.Including the O(n) algorithm in 2.4 kernel,the O(1) algorithm in 2.6 kernel and the latest CFS algorithm.The complexity of scheduling algorithm in 2.6 kernel has been greatly reduced and the performance has been greatly improved,compared with the previous scheduling algorithm.CFS algorithm introduced a modular structrue,so that it's easily to add new algorithm.The design goal is to make the processor resources more equitable between processes.Then we analyzed common scheduling algorithm simulators,we focused on introducing schedsim which we used in our paper.On the basis of previous work,we improved schedsim simulator to better support the linux scheduling algorithm.This includes the multi-processor improvements,the global dispatching algorithm and the simulation of CFS scheduler.For multi-processor improvements,we made the simulator to support different processors,each processor has it's own ranqueue.For the global dispatching algorithm,we achived two simple methods,one is based on the number assigned to the processors,the other is based on the processing power of every processor.The implementation of CFS scheduler follows the linux kernel method.Finally,we show the effect under different input combinations of the new simulator.