Research On Operating System Scheduling Architecture And Algorithm

The operating system technology is constantly promoted by the changes of the computer architecture and application requirements. Designing operating scheduling algorithm which can adapt the new changes in architecture and the application requirement is one of the important research directions, and it has been received widespread attention by the industry.Firstly, the new challenges of the scheduling algorithm design caused by the development of processor architecture and the application requirments are analyzed , then the major changes made in Linux operating system scheduling algorithm to adapt to these challenges are discussed. After that, the main design, implementation and evaluation methods and tools for scheduling algorithms adopted in some operating systems are summarized. Based on these analyses, a scheduling algorithm evaluation criteria system aimed at the current rapidly developed desktop applications is put forward.This evaluation criteria system can be referred as the basis for performance evaluation of the existing scheduling algorithms.Theory and test studies show that the existing algorithms still have shortcomings when they are used for the desktop applications, and the main obstacle for developing a new scheduling algorithm is the lacking of effective support platforms. Although some results can be produced by simulators, most of the time, simulation is unreliable and ineffective. Adding and modifying the scheduling algorithm in the kernel of a real system are sometimes limited by the copyright of the code and its high expenses because of the structural complexity. Therefore, a modular scheduler framework is presented in this paper. In the framework, the scheduler code is packed into ten modules to reduce the linkage between the various parts and improve code clarity. In Linux operating system, a set of simple algorithm interface is provided by the restructured modular scheduler, which can used by users to realize custom scheduling algorithms more easily without concern for the perplexing relationship between the scheduler and other parts of the operating system. By using the interface, one can not only realize his scheduling algorithm in system kernel easily but also obtain the real property of the algorithm accurately. As a result, the modular scheduler can be used as the foundation platform for algorithm implementation and research.Based on the principle, advantage and disadvantage analysis of the algorithm O(1), CFS and BFS , an ideal blind scheduling algorithm model aimed at the desktop applications is presented. The model can be used as reference when designing new scheduling algorithms. Based on this model, a dynamic priority scheduling algorithm(DPS) is designed and implemented. In DPS,the priority and the running time of different kinds of process can be dynamically adjusted in order to speed up the response of the interactive process. This algorithm is realized on the restructured Linux modular scheduler. Tests show DPS can improve the interactivity of the system while no incurring the performances degradation compared to the existing algorithms.