[ Previous | Next | Table of Contents | Index | Library Home | Legal | Search ]

General Programming Concepts: Writing and Debugging Programs


Synchronization Scheduling

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

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.

Mutex Protocols

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.

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

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. See Protocol Attribute for more information. Inheritance or Protection provides guidelines for choosing a protocol.

Protocol Attribute

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.

Inheritance or Protection

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.

Related Information

Thread Programming Concepts

Scheduling Overview

Threads Scheduling

"List of Scheduling Subroutines"

Threads Library Options

 


[ Previous | Next | Table of Contents | Index | Library Home | Legal | Search ]