Runqueue

Conventionally, the runqueue contains all the processes that are contending for CPU time on a given CPU core (a runqueue is per-CPU). The generic scheduler is designed to look into the runqueue whenever it is invoked to schedule the next best runnable task. Maintaining a common runqueue for all the runnable processes would not be a possible since each scheduling class deals with specific scheduling policies and priorities.

The kernel addresses this by bringing its design principles to the fore. Each scheduling class defined the layout of its runqueue data structure as best suitable for its policies. The generic scheduler layer implements an abstract runqueue structure with common elements that serves as the runqueue interface. This structure is extended with pointers that refer to class-specific runqueues. In other words, all scheduling classes embed their runqueues into the main runqueue structure. This is a classic design hack, which lets every scheduler class choose an appropriate...