The Improvement And Implement Of Process Scheduling Algorithm Based On Linux

With the popularization of Linux operate system, it has been known and used by more and more users and most of governments are encouraging and support its'development. The O(1) process scheduling algorithm reduced the complexity of the time from O(n) to O(1). It interests researchers to research the scheduling algorithm based on Linux.The Linux system was introduced firstly. And the signification of this thesis and the research status of scheduling algorithm are introduced too.Then, the O(1) scheduling algorithm and it's implementation in Linux 2.6 kernel are researched detailed. Data structure runqueue was 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 re-allocating of process time-slice is more in time. The calculate course of process priority is more simple and the opportunity is more decentralization. The opportunity of process scheduling is more relaxed, so the real time performance was improved. The process of schedule is simpler too. And a lack of the O(1) scheduler is pointed too: different users run the same program will get the same timeslice and turnaround time. It's not fair to higher priority users.At last the concept user priority was introduced. The shortage mentioned above of O(1) scheduler was proved. The process scheduling policy based on user priority was presented. The policy dispatches different user priority to users, different timeslice and turnaround time of process that was forked by users with different priority. Compared with lower priority users, it lets the turnaround time of process forked by higher priority users shorter. The policy gives the process turnaround time according to its user's priority. So the process scheduling policy based on user priority is fairer. In common conditions, the process will get shorter turnaround time when run by 0 priority users in this policy.The research of the O(1) scheduler follows on the heels of the research in this field. The introduction of user priority and the process scheduling policy based on user priority broaden the techniques of the process scheduling algorithm and improved the research and development of OS in our country.