Scheduling cont. #

CFS cont. #

Recall that vruntime is a function, not the actual runtime of the process. The progress rate depends on the priority of the process.

• faster progress rate for low priority process
• slower progress for high priority process

Since we are always looking for the leftmost node in the process run queue, we can maintain a pointer to get the min value in constant time. Adding a node to a red-black tree can be done in \( O(\lg n) \) time.

The overall time complexity for the CFS scheduler is \( O(\lg n) \) . So this is a slower time complexity than the prior scheduler before CFS, but it is a lot more fair of a scheduler.