completely fair scheduler cfs - TarisMajor/5143-OpSystems GitHub Wiki

Completely Fair Scheduler (CFS) is the default process scheduler in the Linux kernel, designed to provide fair CPU time to all processes. It was implemented by Ingo Molnar and merged into the Linux kernel in version 2.6.23. CFS aims to maximize overall CPU utilization while ensuring interactive performance.

1. Fairness: CFS allocates CPU time to tasks based on their priority and the amount of CPU time they have used, ensuring that no task hogs the CPU while others wait in Linux](https://www.developerscoffee.com/blog/understanding-the-completely-fair-scheduler-cfs-in-linux/).
2. Red-Black Tree: CFS uses a red-black tree data structure to keep track of processes and their CPU time. The leftmost node in the tree represents the task with the least execution time.
3. Virtual Runtime: Each task has a virtual runtime value that represents when its next timeslice would start on an ideal multi-tasking CPU. The scheduler always tries to run the task with the smallest virtual runtime.
4. Dynamic Adjustment: CFS dynamically adjusts the CPU time allocated to tasks based on their behavior and system load.

1. Fair CPU Allocation: Ensures that all processes receive a fair share of CPU time, improving overall system responsiveness.
2. Efficient CPU Utilization: Maximizes CPU utilization by dynamically adjusting task priorities and CPU time allocation.
3. Interactive Performance: Provides better interactive performance by prioritizing tasks that need quick response times.

1. Complexity: The implementation of CFS is complex due to the dynamic nature of task scheduling and the use of red-black trees.
2. Overhead: Continuously monitoring and adjusting task priorities can introduce overhead, impacting system performance.
3. Tuning Requirements: Properly tuning the parameters of CFS, such as time slices and aging intervals, can be challenging.

1. General-Purpose Operating Systems: Ideal for general-purpose operating systems that need to handle a wide variety of processes with different priorities and requirements.
2. Interactive Systems: Suitable for interactive systems where responsiveness and fairness are critical.
3. High-Performance Computing: Effective in high-performance computing environments that require efficient CPU utilization and dynamic adjustment to varying workloads.

Consider a system with three processes:

1. Process P1: Interactive task with a high priority.
2. Process P2: Batch task with a medium priority.
3. Process P3: Background task with a low priority.

CFS will allocate CPU time to these processes based on their priorities and virtual runtime values, ensuring that each process receives a fair share of CPU time.

• CFS Scheduler - The Linux Kernel documentation
• Completely Fair Scheduler - Wikipedia
• Understanding the Completely Fair Scheduler (CFS) in Linux
• ChatGPT