Linux: The Really Fair Scheduler | KernelTrap

Linux: The Really Fair Scheduler | KernelTrap: "o here all the mathematical details necessary to understand what the scheduler does, so anyone can judge for himself how solid this design is. First some basics: (1) time = sum_{t}^{T}(time_{t}) (2) weight_sum = sum_{t}^{T}(weight_{t}) Time per task is calculated with: (3) time_{t} = time * weight_{t} / weight_sum This can be also written as: (4) time_{t} / weight_{t} = time / weight_sum This way we have the normalized time: (5) time_norm = time / weight_sum (6) time_norm_{t} = time_{t} / weight_{t} If every task got its share they are all same. Using time_norm one can calculate the time tasks should get based on their weight: (7) sum_{t}^{T}(time_{t}) = sum_{t}^{T}(round(time / weight_sum) * weight_{t}) This is bascially what CFS currently does and it demonstrates the basic problem it faces. It rounds the normalized time and the rounding error is also distributed to the time a task gets, so there is a difference between the time which is distributed to the tasks and the time consumed by them. On the upside the error is distributed equally to all tasks relatively to their weight (so it isn't immediately visible via top). On the downside the error itself is weighted too and so a small error can be become quite large and the higher the weight the more it contributes to the"