Priority Inversion

Priority Inversion

Priority inversion occurs when a low-priority thread holds a mutex, blocking a high-priority thread. Due to its low priority, the mutex owner may hold the mutex for an unbounded duration. As a result, it becomes impossible to guarantee thread deadlines.

The following example illustrates a typical priority inversion. In this example, the case of a uniprocessor system is considered. Priority inversions also occur on multiprocessor systems in a similar way.

In our example, a mutex M is used to protect some common data. Thread A has a priority level of 100 and is scheduled very often. Thread B has a priority level of 20 and is a background thread. Other threads in the process have priority levels near 60. A code fragment from thread A is as follows:

pthread_mutex_lock(&M);             /* 1 */ ... pthread_mutex_unlock(&M);

A code fragment from thread B is as follows:

pthread_mutex_lock(&M);          /* 2 */ ... fprintf(...);                    /* 3 */ ... pthread_mutex_unlock(&M);

Consider the following execution chronology. Thread B is scheduled and executes line 2. While executing line 3, thread B is preempted by thread A. Thread A executes line 1 and is blocked, because the mutex M is held by thread B. Thus, other threads in the process are scheduled. Because thread Bhas a very low priority, it may not be rescheduled for a long period, blocking thread A, although threadA has a very high priority.

Mutex Protocols

To avoid priority inversions, the following mutex protocols are provided by the threads library:

Priority inheritance protocol

Sometimes called basic priority inheritance protocol. In the priority inheritance protocol, the mutex holder inherits the priority of the highest-priority blocked thread. When a thread tries to lock a mutex using this protocol and is blocked, the mutex owner temporarily receives the blocked thread's priority, if that priority is higher than the owner's. It recovers its original priority when it unlocks the mutex.

Priority protection protocol

Sometimes called priority ceiling protocol emulation. In the priority protection protocol, each mutex has a priority ceiling. It is a priority level within the valid range of priorities. When a thread owns a mutex, it temporarily receives the mutex priority ceiling, if the ceiling is higher than its own priority. It recovers its original priority when it unlocks the mutex. The priority ceiling should have the value of the highest priority of all threads that may lock the mutex. Otherwise, priority inversions or even deadlocks may occur, and the protocol would be inefficient.

Choosing a Mutex Protocol

The choice of a mutex protocol is made by setting attributes when creating a mutex. The mutex protocol is controlled through the protocol attribute. This attribute can be set in the mutex attributes object by using the pthread_mutexattr_getprotocol and pthread_mutexattr_setprotocolsubroutines. The protocol attribute can have one of the following values:

PTHREAD_PRIO_NONE	Denotes no protocol. This is the default value.
PTHREAD_PRIO_INHERIT	Denotes the priority inheritance protocol.
PTHREAD_PRIO_PROTECT	Denotes the priority protection protocol.

The priority protection protocol uses one additional attribute: the prioceiling attribute. This attribute contains the priority ceiling of the mutex. The prioceiling attribute can be controlled in the mutex attributes object, by using the pthread_mutexattr_getprioceiling andpthread_mutexattr_setprioceiling subroutines.

The prioceiling attribute of a mutex can also be dynamically controlled by using thepthread_mutex_getprioceiling and pthread_mutex_setprioceiling subroutines. When dynamically changing the priority ceiling of a mutex, the mutex is locked by the library; it should not be held by the thread calling the pthread_mutex_setprioceiling subroutine to avoid a deadlock. Dynamically setting the priority ceiling of a mutex can be useful when increasing the priority of a thread.

The implementation of mutex protocols is optional. Each protocol is a POSIX option. For more information about the priority inheritance and the priority protection POSIX options, see Threads Library Options.

Inheritance or Protection

Both protocols are similar and result in promoting the priority of the thread holding the mutex. If both protocols are available, programmers must choose a protocol. The choice depends on whether the priorities of the threads that will lock the mutex are available to the programmer who is creating the mutex. Typically, mutexes defined by a library and used by application threads will use the inheritance protocol, whereas mutexes created within the application program will use the protection protocol.

In performance-critical programs, performance considerations may also influence the choice. In most implementations, especially in AIX, changing the priority of a thread results in making a system call. Therefore, the two mutex protocols differ in the amount of system calls they generate, as follows:

• Using the inheritance protocol, a system call is made each time a thread is blocked when trying to lock the mutex.
• Using the protection protocol, one system call is always made each time the mutex is locked by a thread.

In most performance-critical programs, the inheritance protocol should be chosen, because mutexes are low contention objects. Mutexes are not held for long periods of time; thus, it is not likely that threads are blocked when trying to lock them.