How does the scheduler find the highest prio thread in a partition?
It does it very quickly. Each partition has a bit map which tracks which of each of the 0 to 255 priority levels is in use by some ready-to-run thread in that partition. Each time the scheduler makes a thread ready to run, it sets the bit corresponding to that thread’s priority. When we run a thread, meaning we have just changed it’s state from ready-to-run, we examine the queue of threads in that partition which are ready to run and at the same priority. If there are no other threads of that priority, we clear the bit for that thread’s priority. When the scheduler needs to know the highest priority that is ready to run in a partition, it uses the bitmap to index a table which maps integers to number of their highest 1 bit. This is done clevery with a set of tables to avoid the need for 2 to 255th power table elements. The same mechanism is used in classic Neutrino scheduling. The macros are DISTPATCH_SET(), DISPATCH_CLEAR() and DISPATCH_HIGHEST_PRI().
