Skip to content

CFS: Completely fair process scheduling in Linux

statement

solution

  • CFS stands for a completely fair process; it is a complex algorithm for process scheduling which claims the most fairness between processes while preserving efficiency.

Definitions

  • Blocked process: a process that is waiting for an I/O request to complete.
  • Runnable process: a process ready to be run, whether on the CPU right now or queued to do so.
  • Processor-bound process: a process that does more computation than I/O requests; it is runnable most of the time.
  • I/O-bound process: a process that does more I/O than computations; it is blocked most of the time while waiting for I/O responses.

Classic scheduling

  • Classic scheduling uses The Multi-Level Feedback Queue (MLFQ), where each process is given a fixed time slice to run on the CPU, then it gets interrupted by a timer interrupt and then forced to leave the CPU and rescheduled to run later.
  • Each process (aka job) has a priority level; Processes are grouped into queues according to their priority level.
  • Once a new process is submitted to the system, it gets the maximum priority level; the OS constantly observes its behaviour and modifies its priority level accordingly.
  • Periodically, OS boosts the priority level for all processes by pushing them back to the maximum priority queue.
  • Each queue has its algorithm to prioritize one process in case of a tie in the priority level between two processes.
  • Information about MLFQ is retrieved from (Arpaci-Dusseau R, 2018).

CFS Scheduling

  • CFS treats multi-threaded processes as multi-process, where a job is created for every thread, and these threads are still related properly, e.g. all related threads use the same process memory address space.
  • CFS uses dynamically calculated time slices, where the shared time slice varies depending on the total workload of the system.
  • CFS periodically calculates the ideal time slice (usually 20 ms), allowing every job to run on the CPU during a single slice. CFS gives each job fraction (1/Nice) of the ideal time slice equals, where N is the total number of jobs, and Nice is the ideal time slice.
  • When many processes are runnable, the fraction (1/Nice) becomes too small to account for context-switching overhead between processes. Context-Switching requires carefully saving the current process’s PCB and flushing registers with the PCB of the following process.
  • It is important to note that the CPU is not usable during the time used in context-switching.
  • CFS has a threshold that (1/Nice) can not go under in the case of a significant workload. In such a case, CSF tracks the processes with the least runtime on the CPU and gives them more priority over the jobs with higher runtime.
  • CFS has unique features like Symmetrical multiprocessing (SMP) and Configurable scheduling groups.
  • CFS uses a time-ordered red-black tree as a data structure to efficiently run the run queue.
  • Information about CFS is retrieved from (Kalin M, 2019).

Why CFS is better than the traditional MLFQ

  • The dynamic assignment of the shared time slice makes the scheduling algorithm fairer and solves the problems where the predefined time slice may not suit the current workload.
  • Too high a time slice means more response time, and too low a time slice means worse response time and turnaround time (processes can not find time to work with context-switching taking over most of the CPU time.
  • CFS tracks the actual runtime of a job on the CPU, which gives the processes with the lower runtime a higher priority, which solves the issue of processes’ starvation (aka, a process does not have a turn on the CPU where other processes are taking over most of the CPU time).

References