libsched (/libĖskej/) encapsulates the main utilities of kernel scheduling. Despite its primary intended application within the kernel, this library aims to remain environment-agnostic, especially for exercise within non-kernel, testing contexts.
Bandwidth refers to the amount of execution time available to a thread over time, and the bandwidth model refers to the manner in which that time is modeled and allocated to threads.
A thread‘s work is framed as happening within fixed-width, recurring time intervals called activation periods. The duration is a property of the thread and is referred to as its period. When the current activation period expires, it is reactivated and the time allocated to the thread within it is reset. This chunking of work into periods arises naturally in many practical contexts like the duration between VSyncs in graphical contexts and the frequency of polling by device drivers. Accordingly, a period is better regarded as a looser, slack-encoding, often externally-prescribed duration in which a thread is expected to perform its work rather than a precise measure of the duration of that intended work, which is instead referred to as the thread’s capacity.
A thread‘s work has two components: firm and flexible. Firm work is that which is required to occur within a period; it is specified directly as the thread property of firm capacity. Flexible work is that which happens on a best-effort basis, utilizing remaining bandwidth - if any - after firm work has been accounted for; it is specified indirectly as the thread property of flexible weight. Flexible weight gives a conventional measure of the importance of the desired flexible work, with a thread’s flexible capacity being derived from the proportion of its weight to the sum of all such weights across the set of threads (naturally scaled by a firm utilization factor). The (total/effective) capacity of a thread is the sum of its firm and flexible capacities, giving the total duration of execution time a thread expects within an activation period.
All runnable threads (i.e., the currently running thread or those queued and ready to be run) contribute both firm and flexible demand. Further, threads that become blocked will contribute firm demand for the remainder of the activation period in which that took place. This allows threads that quickly unblock to complete the still-accounted-for firm work they set out to do in that period and not be penalized.
At all times, the thread that is selected next is the active one with the earliest finish time (if any). In the event of a tie of finish times, the one with the earlier start time is picked - and then in the event of a tie of start times, the thread with the lowest address is expediently picked (which is a small bias that should not persist across runs of the system).
This process is facilitated by sched::RunQueue.
When a thread is selected, the preemption time - the time at which the next selection process should take place, potentially preempting the currently executing thread - is calculated as well. This should be triggered as soon as there is a state transition affecting the bandwidth of the just-selected thread or the one that would become eligible next, and is calculated as the earlier of the following times: