Synchronization scheduling

Programmers can control the execution scheduling of threads when there are constraints, especially time constraints, that require certain threads to be executed faster than other ones.

Synchronization objects, such as mutexes, may block even high-priority threads. In some cases, undesirable behavior, known as priority inversion, may occur. The threads library provides the mutex protocols facility to avoid priority inversions.

Synchronization scheduling defines how the execution scheduling, especially the priority, of a thread is modified by holding a mutex. This allows custom-defined behavior and avoids priority inversions. It is useful when using complex locking schemes. Some implementations of the threads library do not provide synchronization scheduling.

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 B has a very low priority, it may not be rescheduled for a long period, blocking thread A, although thread A 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.

Both protocols increase the priority of a thread holding a specific mutex, so that deadlines can be guaranteed. Furthermore, when correctly used, mutex protocols can prevent mutual deadlocks. Mutex protocols are individually assigned to mutexes.

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_setprotocol subroutines. The protocol attribute can have one of the following values:
Value Description
PTHREAD_PRIO_DEFAULT No value
PTHREAD_PRIO_NONE Denotes no protocol.
PTHREAD_PRIO_INHERIT Denotes the priority inheritance protocol.
PTHREAD_PRIO_PROTECT Denotes the priority protection protocol.
Note: The behavior of PTHREAD_PRIO_DEFAULT is the same as the PTHREAD_PRIO_INHERIT attribute. With reference to the mutex locking, the threads acting with the default attribute will temporarily boost the priority of a mutex holder when a user is locked and has a higher priority than the owner. Therefore, there are only three behaviors that are possible, although there are four values for the possible priority in the attribute structure.

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 and pthread_mutexattr_setprioceiling subroutines.

The prioceiling attribute of a mutex can also be dynamically controlled by using the pthread_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.

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.