Programmers may want to 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 a facility, the mutex protocols, to avoid priority inversions.
Read the following to get more information about synchronization scheduling:
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. To make the example easier to understand, only the case of a uniprocessor system is considered. Priority inversions also occur on multiprocessor systems in a similar way.
A mutex M is used to protect some common data. Thread A has a priority level of 100. It should be scheduled very often. Thread B has a priority level of 20. It is a background thread. Other threads in the process have priority levels around 60. A code fragment from thread A is:
pthread_mutex_lock(&M); /* 1 */ ... pthread_mutex_unlock(&M);
A code fragment from thread B is:
pthread_mutex_lock(&M); /* 2 */ ... fprintf(...); /* 3 */ ... pthread_mutex_unlock(&M);
Consider the following execution chronology. Thread B is scheduled and executes line 2. When 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.
This figure illustrates the execution of the example. Each thin vertical line represents a thread. The number at the left side is the priority level. The thick line represents the execution path, that is, the instructions executed by the CPU in chronological order.
To avoid priority inversions, two mutex protocols are provided by the threads library:
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.
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.
In the preceding example, thread B would get a priority level of 100 when thread A tries to lock mutex M. Thus, thread B will be scheduled next, instead of the other threads, and will be able to unlock mutex M. This figure illustrates the execution chronology of this example.
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.
In the following example, mutex M has a priority ceiling of 120. Then, when thread B locks mutex M, it gets a priority level of 120 until it unlocks mutex M. Thus, thread B will not be preempted by other threads. This figure illustrates the execution chronology of this example.
The choice of a mutex protocol is made by setting attributes when creating a mutex. This section provides guidelines for choosing a protocol.
The mutex protocol is controlled through an attribute: the protocol attribute. This attribute can be set in the mutex attributes object using the pthread_mutexattr_getprotocol and pthread_mutexattr_setprotocol subroutines. 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, using the pthread_mutexattr_getprioceiling and pthread_mutexattr_setprioceiling subroutines.
The prioceiling attribute of a mutex can also be dynamically controlled using the pthread_mutex_getprioceiling and pthread_mutex_setprioceiling subroutines. Note that 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. See Threads Library Options for more information about the priority inheritance and the priority protection POSIX options.
Both protocols are similar and result in promoting the priority of the thread holding the mutex. If both protocols are available, a choice must be made. This information will help the programmer in choosing a protocol.
The choice depends on whether the priorities of the threads that will lock the mutex are available to the programmer 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.
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.
List of Scheduling Subroutines.
