1
by Tim Gardner, Andy Whitcroft, Tim Gardner
[ Andy Whitcroft ] |
1 |
RT-mutex subsystem with PI support |
2 |
---------------------------------- |
|
3 |
||
4 |
RT-mutexes with priority inheritance are used to support PI-futexes, |
|
5 |
which enable pthread_mutex_t priority inheritance attributes |
|
6 |
(PTHREAD_PRIO_INHERIT). [See Documentation/pi-futex.txt for more details |
|
7 |
about PI-futexes.] |
|
8 |
||
9 |
This technology was developed in the -rt tree and streamlined for |
|
10 |
pthread_mutex support. |
|
11 |
||
12 |
Basic principles: |
|
13 |
----------------- |
|
14 |
||
15 |
RT-mutexes extend the semantics of simple mutexes by the priority |
|
16 |
inheritance protocol. |
|
17 |
||
18 |
A low priority owner of a rt-mutex inherits the priority of a higher |
|
19 |
priority waiter until the rt-mutex is released. If the temporarily |
|
20 |
boosted owner blocks on a rt-mutex itself it propagates the priority |
|
21 |
boosting to the owner of the other rt_mutex it gets blocked on. The |
|
22 |
priority boosting is immediately removed once the rt_mutex has been |
|
23 |
unlocked. |
|
24 |
||
25 |
This approach allows us to shorten the block of high-prio tasks on |
|
26 |
mutexes which protect shared resources. Priority inheritance is not a |
|
27 |
magic bullet for poorly designed applications, but it allows |
|
28 |
well-designed applications to use userspace locks in critical parts of |
|
29 |
an high priority thread, without losing determinism. |
|
30 |
||
31 |
The enqueueing of the waiters into the rtmutex waiter list is done in |
|
32 |
priority order. For same priorities FIFO order is chosen. For each |
|
33 |
rtmutex, only the top priority waiter is enqueued into the owner's |
|
34 |
priority waiters list. This list too queues in priority order. Whenever |
|
35 |
the top priority waiter of a task changes (for example it timed out or |
|
36 |
got a signal), the priority of the owner task is readjusted. [The |
|
37 |
priority enqueueing is handled by "plists", see include/linux/plist.h |
|
38 |
for more details.] |
|
39 |
||
40 |
RT-mutexes are optimized for fastpath operations and have no internal |
|
41 |
locking overhead when locking an uncontended mutex or unlocking a mutex |
|
42 |
without waiters. The optimized fastpath operations require cmpxchg |
|
43 |
support. [If that is not available then the rt-mutex internal spinlock |
|
44 |
is used] |
|
45 |
||
46 |
The state of the rt-mutex is tracked via the owner field of the rt-mutex |
|
47 |
structure: |
|
48 |
||
49 |
rt_mutex->owner holds the task_struct pointer of the owner. Bit 0 and 1 |
|
50 |
are used to keep track of the "owner is pending" and "rtmutex has |
|
51 |
waiters" state. |
|
52 |
||
53 |
owner bit1 bit0 |
|
54 |
NULL 0 0 mutex is free (fast acquire possible) |
|
55 |
NULL 0 1 invalid state |
|
56 |
NULL 1 0 Transitional state* |
|
57 |
NULL 1 1 invalid state |
|
58 |
taskpointer 0 0 mutex is held (fast release possible) |
|
59 |
taskpointer 0 1 task is pending owner |
|
60 |
taskpointer 1 0 mutex is held and has waiters |
|
61 |
taskpointer 1 1 task is pending owner and mutex has waiters |
|
62 |
||
63 |
Pending-ownership handling is a performance optimization: |
|
64 |
pending-ownership is assigned to the first (highest priority) waiter of |
|
65 |
the mutex, when the mutex is released. The thread is woken up and once |
|
66 |
it starts executing it can acquire the mutex. Until the mutex is taken |
|
67 |
by it (bit 0 is cleared) a competing higher priority thread can "steal" |
|
68 |
the mutex which puts the woken up thread back on the waiters list. |
|
69 |
||
70 |
The pending-ownership optimization is especially important for the |
|
71 |
uninterrupted workflow of high-prio tasks which repeatedly |
|
72 |
takes/releases locks that have lower-prio waiters. Without this |
|
73 |
optimization the higher-prio thread would ping-pong to the lower-prio |
|
74 |
task [because at unlock time we always assign a new owner]. |
|
75 |
||
76 |
(*) The "mutex has waiters" bit gets set to take the lock. If the lock |
|
77 |
doesn't already have an owner, this bit is quickly cleared if there are |
|
78 |
no waiters. So this is a transitional state to synchronize with looking |
|
79 |
at the owner field of the mutex and the mutex owner releasing the lock. |