Linux's "scheduler" is the component of Linux (or other kernels) which decides which programs are currently running on your computer at any given time.

From what I recall of it's code there are multiple schedulers (including ones for timers & deadlines), each of which falls back to the next one when they have no active tasks to schedule. Ultimately falling back to a thread which predicts how long it'll lack work, and what the most energy efficient "sleep" instruction would be.



There is plenty of complexity involved in letting threads move from one CPU core to the next, which I didn't understand. If a thread is waiting on something, it's removed from the schedulers.

When a kernel operation blocks, or the clock ticks, the scheduler is called to switch threads.

Most (not all) of the schedulers are "Min Heaps", which is a datastructure which always pops it's smallest item by some measure. (There's also max heaps which are implemented basically the same way)


To implement a min heap you build a binary tree where each "branch" holds a value smaller than either of it's children. Then store it in an array where index "i" has children 2i & 2i+1.

Add a value, first place it at the end of the array. Then swap it with it's parent until the invariant is reasserted.

To remove the smallest value (which is at the root), replace it with the last value removed from the end of the array and swap it with a child until the invariant is reasserted.


Show thread
Sign in to participate in the conversation

For people who care about, support, or build Free, Libre, and Open Source Software (FLOSS).