Priority calculation

 

The kernel maintains a priority value (sometimes termed the scheduling priority) for each thread. The priority value is a positive integer and varies inversely with the importance of the associated thread. That is, a smaller priority value indicates a more important thread. When the scheduler is looking for a thread to dispatch, it chooses the dispatchable thread with the smallest priority value.

The formula for calculating the priority value is:

priority value = base priority + nice penalty + (CPU penalty based on recent CPU usage)

The recent CPU usage value of a given thread is incremented by 1 each time that thread is in control of the CPU when the timer interrupt occurs (every 10 milliseconds). The recent CPU usage value is displayed as the C column in the ps command output. The maximum value of recent CPU usage is 120.

The default algorithm calculates the CPU penalty by dividing recent CPU usage by 2. The CPU-penalty-to-recent-CPU-usage ratio is therefore 0.5. This ratio is controlled by a value called R (the default is 16). The formula is as follows:

CPU_penalty = C * R/32

Once a second, the default algorithm divides the recent CPU usage value of every thread by 2. The recent-CPU-usage-decay factor is therefore 0.5. This factor is controlled by a value called D (the default is 16). The formula is as follows:

C = C * D/32

The algorithm for calculating priority value uses the nice value of the process to determine the priority of the threads in the process. As the units of CPU time increase, the priority decreases with the nice effect. Using schedo -r -d can give additional control over the priority calculation by setting new values for R and D. See schedo command for further information.

Begin with the following equation:

p_nice = base priority + nice value

Now use the following formula:

If p_nice > 60,
   then x_nice = (p_nice * 2) - 60,
   else x_nice = p_nice.

If the nice value is greater than 20, then it has double the impact on the priority value than if it was less than or equal to 20. The new priority calculation (ignoring integer truncation) is as follows:

priority value = x_nice + [(x_nice + 4)/64 * C*(R/32)]