Completely Fair Scheduler

Introduction

CFP uses a concept called "sleeper fairness",

• which considers sleeping or waiting tasks equivalent to those on the runqueue. This means that interactive tasks which spend most of their time 
• So that the interactive tasks which spend most the their time waiting for user input or other events get a comparable share of CPU time when they need it.

Algorithm

• The data structure used for the scheduling algorithm is a red-black tree in which the nodes are scheduler-specific structures, entitled "sched_entity". 
• These are derived from the general task_struct process descriptor, with added scheduler elements. These nodes are indexed by processor execution time in nanoseconds. 
• Idea Processor
• an "idea processor" would equally share processing power among all processes. 
• Maximum execution time
• Thus the maximum execution time is the time the process has been waiting to run, divided by the total number of processes, or in the other words, the maximum execution time is the time the process would have expected to run on an "ideal processor"
• A maximum execution is also calculated for each process. This time is based upon the idea that an "idea processor" would equally share processing power among all processes. 
• When the scheduler is invoked to run a new process, the operation o the scheduler is as follows
• The left most node of the scheduling tree is chosen (as it will have the lowest spent execution time), and sent for execution
• If the process simply completes execution, it is removed from the system and scheduling tree
• If the process reaches its maximum execution time or is otherwise stopped (voluntarily or via interrupt), it is reinserted into the scheduling tree based on its new spent executiom time.
• The new left-most node will then be selected from the tree, repeating the interation. 

Reference

[1] https://en.wikipedia.org/wiki/Completely_Fair_Scheduler