Fair scheduling

$n$ processes, each running at $\frac{1}{n}$ rate: then CPU usage is divided equally among every process:

• 1 process time $n$, 3 processes time $1/3$, then we proportion it accordingly

In completely fair scheduling (CFS), we assign a “virtual runtime” for each runnable process. At each scheduling point (where the process runs for time $t$), we increase the virtual runtime by $t\times \text{weight}$ based on the priority. The virtual runtime will monotonically increase. The scheduler selects the process based on the lowest virtual runtime (whatever needs to catch up to the other processes). We then compute its dynamic time slice based on the IFS. Allow the process to run, and when the time slice ends, we repeat this process.

CFS are implemented with red-black trees, so it has $O(\log n)$ operations. By default, CFS tends to favour IO bound processes, since small CPU bursts translate to a low virtual runtime which translate to higher priority scheduling.