Root/
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. |
80 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9