Background
The primary responsibility of any scheduler is to share the limited resource of processor time between all threads that wish to use it. In a general purpose operating system, it tries to do so in a fair way, ensuring that all threads are allowed to make some progress.
Our scheduler is an evolution of LK’s scheduler. As such it started as a minimal scheduler implementation and was extended to meet our needs as the project grew.
Design
Overview
In essence there is a scheduler running on each logical CPU in the machine. These schedulers run independently and use IPI (Inter-Processor Interrupts) to coordinate. However each CPU is responsible for scheduling the threads that are running on it. See CPU Assignment below for how we decide which CPU a thread is on, and how/when it migrates.
Each CPU has its own set of priority queues. One for each priority level in the system, currently 32. Note that these are fifo queues, not the data structure known as a priority queue. In each queue is an ordered list of runnable threads awaiting execution. When it is time for a new thread to run, the scheduler simply looks at the highest numbered queue that contains a thread, pops the head off of that queue and runs that thread.See Priority Management below for more details about how it decides which thread should be in which queue. If there are no threads in the queues to run it will instead run the idle thread, see Realtime and idle threads below for more details.
Each thread is assigned the same timeslice size (THREAD_INITIAL_TIME_SLICE) when it is picked to start running. If it uses its whole timeslice it will be reinserted at the end of the appropriate priority queue. However if it has some of its timeslice remaining from a previous run it will be inserted at the head of the priority queue so it will be able to resume as quickly as possible. When it is picked back up again it will only run for the remainder of its previous timeslice.
When the scheduler selects a new thread from the priority queue it sets the CPU's preemption timer for either a full timeslice, or the remainder of the previous timeslice. When that timer fires the scheduler will stop execution on that thread, add it to the appropriate queue, select another thread and start over again.
If a thread blocks waiting for a shared resource then it's taken out of its priority queue and is placed in a wait queue for the shared resource. When it is unblocked it will be reinserted in the appropriate priority queue of an eligible CPU (CPU Assignment) and if it had remaining timeslice to run it will be added to the front of the queue for expedited handling.
Priority management
There are three different factors used to determine the effective priority of a thread, the effective priority being what is used to determine which queue it will be in.
The first factor is the base priority, which is simply the thread’s requested priority. There are currently 32 levels with 0 being the lowest and 31 being the highest.
The second factor is the priority boost. This is a value bounded between [-MAX_PRIORITY_ADJ, MAX_PRIORITY_ADJ] used to offset the base priority, it is modified by the following cases:
When a thread is unblocked, after waiting on a shared resource or sleeping, it is given a one point boost.
When a thread yields (volunteers to give up control), or volunteers to reschedule, its boost is decremented by one but is capped at 0 (won’t go negative).
When a thread is preempted and has used up its entire timeslice, its boost is decremented by one but is able to go negative.
The third factor is its inherited priority. If the thread is in control of a shared resource and it is blocking another thread of a higher priority then it is given a temporary boost up to that thread’s priority to allow it to finish quickly and allow the higher priority thread to resume.
The effective priority of the thread is either the inherited priority, if it has one, or the base priority plus its boost. When this priority changes, due to any of the factors changing, the scheduler will move it to a new priority queue and reschedule the CPU. Allowing it to have control if it is now the highest priority task, or relinquish control if it is no longer highest.
The intent in this system is to ensure that interactive threads are serviced quickly. These are usually the threads that interact directly with the user and cause user-perceivable latency. These threads usually do little work and spend most of their time blocked awaiting another user event. So they get the priority boost from unblocking while background threads that do most of the processing receive the priority penalty for using their entire timeslice.
CPU assignment and migration
Threads are able to request which CPUs on which they wish to run using a CPU affinity mask, a 32 bit mask where 0b001 is CPU 1, 0b100 is CPU 3, and 0b101 is either CPU 1 or CPU 3. This mask is usually respected but if the CPUs it requests are all inactive it will be assigned to another CPU. Also notable, if it is “pinned” to a CPU, that is its mask contains only one CPU, and that CPU becomes inactive the thread will sit unserviced until that CPU becomes active again. See CPU activation below for details.
When selecting a CPU for a thread the scheduler will choose, in order:
The CPU doing the selection, if it is idle and in the affinity mask.
The CPU the thread last ran on, if it is idle and in the affinity mask.
Any idle CPU in the affinity mask.
The CPU the thread last ran on, if it is active and in the affinity mask.
The CPU doing the selection, if it is the only one in the affinity mask or all cpus in the mask are not active.
Any active CPU in the affinity mask.
If the thread is running on a CPU not in its affinity mask (due to case 5 above) the scheduler will try to rectify this every time the thread is preempted, yields, or voluntarily reschedules. Also if the thread changes its affinity mask the scheduler may migrate it.
Every time a thread comes back from waiting on a shared resource or sleeping and needs to be assigned a priority queue, the scheduler will re-evaluate its CPU choice for the thread, using the above logic, and may move it.
CPU activation
When a CPU is being deactivated, that is shutdown and removed from the system, the scheduler will transition all running threads onto other CPUs. The only exception is threads that are “pinned”, that is they only have the deactivating CPU in their affinity mask, these threads are put back into the run queue where they will sit unserviced until the CPU is reactivated.
When a CPU is reactivated it will service the waiting pinned threads and threads that are running on non-Affinity CPUs should be migrated back pretty quickly by their CPUs scheduler due to the above rules. There is no active rebalancing of threads to the newly awakened CPU, but as it should be idle more often, it should see some migration due to the logic laid out above in CPU assignment and migration.
Realtime and idle threads
These are special threads that are treated a little differently.
The idle thread runs when no other threads are runnable. There is one on each CPU and it lives outside of the priority queues, but effectively in a priority queue of -1. It is used to track idle time and can be used by platform implementations for a low power wait mode.
Realtime threads (marked with THREAD_FLAG_REAL_TIME) are allowed to run without
preemption and will run until they block, yield, or manually reschedule.