Friday, 22 November 2013

Thread Quantum, Thread Priority Boosting and Processor Affinity

This blog post for a continuation of thread scheduling as discussed in my previous blog post, although in this blog post I'm going to explain the concept of Quantum and Boosts. These both are deciding factors for thread scheduling.

Thread Quantum

A thread quantum is the amount of time a thread is allowed to execute for, before Windows interrupts the thread and lets a different thread of the same priority level run and execute. A thread can run for another quantum, if there are no other threads at that priority level.

A thread quantum is around 2 clock intervals, and is governed by the HAL. We can check the length (in milliseconds) of a clock interval with the ClockRes program.

Threads do not run based upon clock intervals, this is translated into a the number of clock cycles in a quantum, and is stored inside the variable called KiCyclesPerQuantum. Threads run for a Target Quantum which is the the number of clock cycles passed before the thread should stop executing. The Target Quantum or Quantum Target can be found in the _KTHREAD data structure in the QuantumTarget field as seen here:

The Quantum Reset value can only be found in the same data structure. This value is used for creating new threads within the same process.

This is measured in Quantum Units, which is a third of a clock tick. A process windows which is brought to the foreground, is given a Quantum Boost, the threads within the process have their quantum targets tripled for obvious reasons.

Thread Priority Boosting

 There are six different reasons, the Kernel will increase the (boost) priority of threads. Boosts can never exceed the dynamic priority range and enter the real-time priority range. For example, a thread with a current priority of 15 will remain at 15 if it is boosted.
  • I/O Operation Completion
  • Executive Events and Semaphores
  • Executive Resources (wait was too long)
  • Foreground process threads complete a wait
  • Windowing activity for a GUI thread
  • CPU Starvation 
I/O Boosting:
  • Boost is always applied to the current thread priority level (never base priority)
  • Boost lasts for one quantum, and the priority level reduces by one for each quantum, until the base priority of that thread is met. 
Events and Semaphores Boosts:
  •  Thread base priority is boosted by 1
  • Thread will run at the higher priority level until the quantum ends, and then will decay (reduce by 1 each quantum) until the base priority is meet.
  • Special boosts are applied to special event functions (NtSetEventBoostPriority and KeSetEventBoostPriority), or gate objects. A special boost increases the thread priority one above, the thread priority of the thread setting the event object. This only applies if the thread priority of the woken thread is below 13.
Executive Resources:

Boosts here are slightly more in depth than the other mechanisms being discussed, due to the higher risks of CPU Starvation and Deadlocks.

A thread waiting upon a executive resource, will perform a wait in 5 second intervals, this prevents CPU Starvation and Deadlocks.If the thread is still waiting, then a boost may be applied to the owner thread.
  • The base priority of the owner thread is increased to 14.
  • Boost is only set, if the base priority isn't already 14 and the owner thread has a lower priority than the waiting thread.
  • Quantum is reset, so the thread is able to run at a boosted priority for a entire quantum, instead of the remaining quantum. The same decay rules apply here.
Depending upon if the executive resource is exclusive or shared, the owner thread will be boosted and then the other threads will be boosted. In a shared situation, the exclusive owner thread will be boosted first, and then all the shared owner threads will be boosted.

Foreground Boosts:

The current thread priority is boosted by the value of the PsPrioritySeparation.

GUI Thread Boosts:

The current priority level will be boosted by 2, when the thread calls KeSetEvent and completes a wait.

CPU Starvation:

The Balance Set Manager is used to scan the ready queues for any threads which haven't ran for 4 seconds. The Balance Set Manager check every second. If any threads haven't ran for the given time, then the Balance Set Manager boosts the current priority level to 15 (of 10 threads); if there were any remaining threads which needed boosting, then it will boost these threads on it's next scan. The Balance Set Manager also only scans 16 threads eligible for priority boost at a time, to ensure this process is quick and doesn't cause further delays. If there were 20 ready threads, then the Balance Set Manager will scan the remaining 4 on it's next scan.

Processor Affinity

The affinity mask is which processor a thread is allowed to run on, and is inherited from the process affinity. At first, the affinity mask is set to all the available processors, and the thread is able to run on any processor of it's choosing. However, this can be changed, with the SetThreadAffinityMask function (set for individual thread) and the the SetProcessAffinityMask (set for all threads for a process).

 Here, the affinity mask is set to 3, even though my system only has two processors, therefore I assume that if the affinity mask number is set to a non-existent processor number, then the affinity mask is set to all available processors.

Here the same concept stands, the Affinity Mask seems to be set to 6. Unless, the Group is the affinity mask for the thread, which would make more sense since the thread is currently running on processor 0.

1 comment:

  1. Nice Article ;> . I just want to add that QuantumReset is also used in resetting the thread's quantum target using something similar to the following pseudo line. CurrentThread->TargetQuantum = CurrentThreadCycleTime + ( KiCyclePerClockQuantum * QuantumReset );
    Where QuantumReset == 0x7F if the thread's priority is in the real time range , and CurrentThread->QuantumReset in the dynamic range.