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.
pthread_mutex_lock(&M); /* 1 */
...
pthread_mutex_unlock(&M);
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
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. |
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.
- 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.