Scheduler run queue

Edit online

The scheduler maintains a run queue of all of the threads that are ready to be dispatched.

The following illustration depicts the run queue symbolically.

Figure 1. Run Queue. This illustration simply shows how threads with a lower priority value are passed through the run queue before threads with a higher priority value. The range of possible priority values is 0 - 127 which directly relate to a total of 128 total run queues.
Run Queue

All the dispatchable threads with priority occupy positions in the run queue.

The fundamental dispatchable entity of the scheduler is the thread. AIX® maintains 256 run queues. The run queues relate directly to the range of possible values (0 through 255) for the priority field for each thread. This method makes it easier for the scheduler to determine which thread is most favored to run. Without having to search a single large run queue, the scheduler consults a mask where a bit is on to indicate the presence of a ready-to-run thread in the corresponding run queue.

The priority value of a thread changes rapidly and frequently. The constant movement is because of the way the scheduler recalculates priorities. This is not true, however, for fixed-priority threads.

Starting with AIX Version 6.1, each processor has a run queue per node. The run queue values that are reported in the performance tools is the sum of all the threads in each run queue. Having a per-processor run queue saves overhead on dispatching locks and improves overall processor affinity. Threads tend to stay on the same processor more often. If a thread becomes executable because of an event on another processor than the executable thread that it is running on, then the thread gets dispatched immediately if there is an idle processor. No preemption occurs until the processor's state is examined such as an interrupt on the thread's processor.

On multiprocessor systems with multiple run queues, transient priority inversions can occur. It is possible that at any time one run queue has several threads with more favorable priority than another run queue. AIX has mechanisms for priority balancing over time, but if strict priority is required (for example, for real-time applications) an environment variable that is called RT_GRQ exists. The RT_GRQ environmental variable when set to ON, causes the thread to be on a global run queue. In that case, the global run queue is searched for the thread with the best priority. This can improve performance for threads that are interrupt driven. Threads that are running at fixed priority are placed on the global run queue, if the fixed_pri_global parameter of the schedo command is set to 1.

The average number of threads in the run queue is seen in the first column of the vmstat command output. If you divide this number by the number of processors, the result is the average number of threads that are run on each processor. If this value is greater than one, these threads must wait their turn for the processor the greater the number, the more likely it is that performance delays are noticed.

When a thread is moved to the end of the run queue (for example, when the thread has control at the end of a time slice), it is moved to a position after the last thread in the queue that has the same priority value.