How are jobs stored?

Data structures in the Linux process scheduler

This question tests your understanding of how the Linux kernel organizes and prioritizes runnable processes. Specifically, it explores the Completely Fair Scheduler (CFS) and the data structure choices that make efficient scheduling decisions possible.

The scheduler must answer a recurring question: which process should run next? With hundreds or thousands of processes on a typical system, a naive linear search becomes prohibitively slow. This question probes whether you understand how CFS maintains process metadata in a way that makes O(log n) lookup and insertion efficient, and how that choice reflects the fairness guarantees the scheduler is trying to provide.

• Red-black trees and self-balancing search structures
• Priority queues and heap-like orderings
• The relationship between data structure choice and scheduling latency
• Virtual runtime as a fairness metric