Priority Inversion

Priority Inversion is a hybrid situation that involves both the involuntary and voluntary suspension of two threads.

Consider the following:

A high priority thread is blocked on a resource.

A low priority thread owns the resource on which the high priority thread is blocked.

An independent thread of intermediate priority is running.

  ┌─────────────────────────────────────────────────┐
  │                                                 │
  │   ┌──────────┐                                  │
  │   │ Thread 1 │                                  │
  │   │  High    │                                  │
  │   │  blk     │                                  │
  │   └──────────┘                                  │
  │                                                 │
  │       ║                                         │
  │       ║                                         │
  │       ║                                         │
  │ waits ║                                         │
  │  on   ║                   ┌─────────┐           │
  │ SEM   ║                   │Thread 3 │           │
  │ owned ║ < - - - - - - - - │ Medium  │           │
  │  by   ║                   │  run    │           │
  │ thd 2 ║                   └─────────┘           │
  │       ║                                         │
  │       V                                         │
  │                                                 │
  │    ┌─────────┐                                  │
  │    │Thread 2 │                                  │
  │    │  Low    │                                  │
  │    │  rdy    │                                  │
  │    └─────────┘                                  │
  │                                                 │
  └─────────────────────────────────────────────────┘

Thread 1 will not run until thread 2 gets a time-slice that allows it to run and release the semaphore thread 1 is waiting for.

Since thread 3 is a higher priority than thread 2 and is CPU bound, thread 2 never runs, nor does thread 1.

Thread 1's priority has effectively been reduced to that of thread 2's by a lower priority thread - thread 3. Thread 1 is said to have its priority inverted with respect to thread 3.

The Kernel implements an automatic inversion protection mechanism whenever a process blocks using a KSEM. Essentially this amounts to boosting the KSEM owner's thread priority by setting TCBPriorityMin to be just greater than the waiter's priority. This mechanism is implemented by the following three routines:

TKEnterInversion

Called to protect against priority inversion. For example, when a mutex KSEM is obtained increments TCBcBoostLock.

When an inversion protected KSEM is released TCBcboostlock is decremented. When TCBcBoostlock is zero and TCBPriorityMin and is not zero then it is set to zero and the priority recalculated.

Used to set the minimum priority of a thread to be waited on. If owner's TCBPriorityMin < waiter's TCBPriority and owner is in ready state then the owner's TCBPriorityMin to the waiter's TCBPriority+1.

For this mechanism to work, it must be possible to determine ownership from the semaphore so that TKDeclareInversion can determine which thread's priority to alter. It is also necessary to be able to determine whether raising the priority of thread will lead to other synchronisation problems or deadlocks through race conditions. Since the Kernel is a special case, and because pre-emption cannot occur while running in kernel mode, the kernel limits inversion protection to the KSEM only. Outside kernel mode, inversion is automatically protected against (for regular and foreground server threads) by application of the starvation priority boost.