Linux Kernel Architecture

Chapter 5: Locking and Interprocess Communication

There are two ways to define new mutexes:

1. Static mutexes can be generated at compile time by usingDEFINE_MUTEX(be sure not to con-
   fuse this withDECLARE_MUTEXfrom the semaphore-based mutexes!).


2. mutex_initdynamically initializes a new mutex at run time.

mutex_lockandmutex_unlockare used to lock and unlock a mutex, respectively. In addition, the kernel

also provides the functionmutex_trylock, which tries to obtain the mutex, but will return immediately

if this fails because the mutex is already locked. Finally,mutex_trylockcan be used to check if a given

mutex is locked or not.

Real-Time Mutexes

Real-time mutexes (RT-mutexes) are another form of mutex supported by the kernel. They need to be

explicitly enabled at compile time by selecting the configuration optionCONFIG_RT_MUTEX. In contrast

to regular mutexes, they implementpriority inheritance, which, in turn, allows for solving (or, at least,

attenuating) the effects ofpriority inversion. Both are well-known effects, respectively, methods and are

discussed in most operating systems textbooks.

Consider a situation in which two processes run on a system: A has high priority, and C has low priority.

Assume the C has acquired a mutex and is happily operating in the protected region, with no intention of

leaving it sometime in the near future. However, shortly after C has entered the protected region, A also

tries to obtain the mutex that protects it — and has to wait, because C has already acquired the mutex.

This causes thehigher-priority process A to wait for thelower-priority process C.

Things can get worse when a third process B with a priority between A and C enters the field. Suppose

that C still holds the lock, and A is waiting for it. Now B gets ready to run. Because it has a higher

priority than C, it can preempt C. But it has also effectively preempted A, although this process has a

higher priority than B. If B continues to stay runnable, it can prevent A from running for a long time,

because C will finish its operation only slowly. B therefore acts as if it had a higher priority than A. This

unfortunate situation is referred to asunbounded priority inversion.

This problem can be solved by priority inheritance: When a high-priority process blocks on a mutex that

is currently held by a low-priority process, the priority of C (in our example) is temporarilyboostedto the

priority of A. If B starts to run now, it will only get as much CPU time as if it were competing with A,

thus setting priorities straight again.

The definition of a RT-mutex is tantalizingly close to the definition of a regular mutex:

<rtmutex.h>

struct rt_mutex {

spinlock_t wait_lock;

struct plist_head wait_list;

struct task_struct *owner;

};

The mutex owner is denoted byowner,andwait_lockprovides the actual protection. All waiting pro-

cesses are enqueued onwait_list. The decisive change in contrast to regular mutexes is that the tasks

on the waiter lists are sorted by priority. Whenever the waiter list changes, the kernel can consequently

adjust the priority of the owner up or down. This requires an interface to the scheduler that is provided

by the functionrt_mutex_setprio. The function updates the dynamic prioritytask_struct->prio,but