## 3 Background
### Completely Fair Scheduler  
The _completely fair scheduler_ (_CFS_) description is based on the description from book [3]. The Linux OS initially employed an exceptionally sophisticated MLFQ known as _O(1) scheduler_. However, [PERSON] deemed it overly complex and challenging to reason about. In Linux version 2.6.23 in 2007, the CFS, invented by [PERSON] [20], became the default scheduler. Unlike traditional schedulers that rely on fixed time slices, CFS prioritizes fairness by aiming to distribute the CPU's processing power among competing processes evenly. It achieves this through a dynamic counting-based approach known as virtual runtime_ (vruntime), where each process accumulates vruntime in proportion to its actual running time. To ensure a fair distribution of CPU resources during scheduling decisions, CFS chooses the process with the lowest vruntime to run next.  
CFS employs a parameter known as sched_latency to determine a process's duration before undergoing a context switch. The default setting for sched_latency is commonly configured at 48 ms, resulting in a corresponding time_slice of 48 ms. The actual time_slice is additionally influenced by the presence of other processes in the queue. When there are \(n\) processes, the time_slice is calculated as  
\[time\_slice=\frac{sched\_latency}{n} \tag{1}\]  
Here, time_slice represents the time a process runs before it is switched out. However, as the number of processes increases, sched_latency may become extremely small, potentially leading to the overhead of context switching outweighing the allocated time. To address this issue, CFS introduces a parameter called min_granularity, which establishes the minimum time slice a process will run before switching out. The default value for min_granularity in Linux is 6 ms. So, the time slice is calculated using Equation (2).  
\[time\_slice=max\left(\frac{sched\_latency}{n},min\_granularity\right) \tag{2}\]  
CFS prioritizes fair CPU scheduling and allows for fine-grained control over process priority using a mechanism known as _niceness_, which assigns a _nice_ value to each process in the system. The nice parameter can be modified to allocate a higher CPU share to specific processes. This parameter ranges from \(-20\) to \(+19\) for a process, with the default value being 0. A positive nice value assigns a lower priority to a process, whereas a negative value confers a higher priority. The concept of niceness provides a practical means for users or administrators to exert influence over the allocated CPU share for specific processes.  
Additionally, CFS adjusts its vruntime calculation based on the weight, ensuring fair distribution of CPU resources while considering niceness and process priorities. This intelligent adaptation maintains proportional CPU allocation, preserving fairness even when niceness values differ. For instance, a process with a higher niceness value will accrue vruntime at an increased rate compared with one with a lower niceness value. The accumulation of vruntime is depicted in Equation (4), where \(runtime_{i}\) represents the actual CPU time utilized by process \(i\), \(weight_{0}=1024\) is the default weight for niceness 0 as indicated in Table 1, and \(weight_{i}\) corresponds to the weight of process \(i\).  
\[\centering{runtime_{i}={runtime_{i}+\frac{{weight_{0}}}{{weight_{i}}}\cdot{ runtime_{i}}}}\@add@centering \tag{4}\]