Process Of Low-power Scheduling Algorithm

This thesis focuses on Low Energy Scheduling Algorithms for Operating Systems, which can be used to:1. make chips cooler and get rid of radiator and thus to make smaller, quieter and steadier computer ;2. prolong battery lifetime of battery-powered systems, such as mobile phone, notebook computer, GPS( global position system), etc.Low Energy Scheduling Algorithms are also called "DVS (Dynamic Voltage Scaling) algorithms". Compared with other low energy algorithms such as DPM algorithms, DVS can save more energy and are easier to plant.The key point of DVS algorithm is the balance of energy and real-time performance: a lower frequency is necessary to save energy, while a lower frequency may cause some bad effect on real-time performance.Lots of papers on DVS algorithms have been published since the literature [Mar94] was published. These DVS algorithms can be divided into two groups: on-line or off-line. Unfortunately, these algorithms are not practical because:1. The on-line algorithms count CPU utility ratio with "window", which leads to higher energy and impossibility to optimize window size;2. Both on-line and off-line algorithms suppose that processes run independently, which is not the truth in practice.This thesis is a set of struggles to solve the problems above. The basics of these struggles are to present and prove the Optimal Low Energy Scheduling theorem, and to present that an on-line algorithm can't be hard real-time.With the basics above, the thesis presents two new DVS algorithms. The first one is the Self-adaptive DVS, which is on-line, and featured by replacing CPU utility ratio with "frequency utility ratio" and counting the utility ratio without window. The features help the Self-adaptive DVS to solve the problem of known on-line algorithms. According to the experience data, the Self-adaptive DVS save more energy than not only on-line algorithms, but also off-line algorithms even. The real-time performance of this algorithm is acceptable: in experience generally the time constraint was broken less than twice per 1000 times the processes run.The second new algorithm is DP-DVS, which is off-line, and featured by noticing that processes can't run "independently", but be restricted by each other, orbe dependent on each other. This algorithm decides the proper sequence with Dependent Tree, and then decides the proper frequency according to the Optimal Low Energy Scheduling theorem. This algorithm can also avoid some deadlock, thus it helps to improve the system's reliability.The time cost of the two algorisms above is tiny. Both of them are of high application value.This thesis also studies the relation between DVS and battery performance. There have been some literatures on this topic. Their conclusions are not universal or convictive because they are based on the knowledge of chemistry or electronics. The thesis adopts a new method, which is based on the discharging curve of battery and basic physical knowledge, thus to make the conclusion universal and convictive. The main conclusion is that the higher a process' frequency is, the higher its priority should be. An actual discharging experience is showed in the thesis to verify the conclusion. The conclusion can be used to select or improve DVS algorithms. The thesis improves a known DVS as a demonstration.Besides the theorem, two algorithms and battery above, the thesis also discusses some other relative problems, such as how the energy is consumed, how the energy consumption distributes in a system, the processes schedule algorithm used by popular operating systems,, the effort of CPU performance on DVS algorithms' performance, the characteristic and advantage and disadvantage of known DVS algorithms, how the simulate and evaluate a DVS algorithm, etc.The thesis also shows that the system will take full advantage of DVS only when the CPU can change its frequency steplessly. Such CPU has not been invited yet, but it is worth to do so.