1 page.title=Avoiding Priority Inversion 2 @jd:body 3 4 <div id="qv-wrapper"> 5 <div id="qv"> 6 <h2>In this document</h2> 7 <ol id="auto-toc"> 8 </ol> 9 </div> 10 </div> 11 12 <p> 13 This article explains how the Android's audio system attempts to avoid 14 priority inversion, as of the Android 4.1 (Jellybean) release, 15 and highlights techniques that you can use too. 16 </p> 17 18 <p> 19 These techniques may be useful to developers of high-performance 20 audio apps, OEMs, and SoC providers who are implementing an audio 21 HAL. Please note that implementing these techniques is not 22 guaranteed to prevent glitches or other failures, particularly if 23 used outside of the audio context. 24 Your results may vary and you should conduct your own 25 evaluation and testing. 26 </p> 27 28 <h2 id="background">Background</h2> 29 30 <p> 31 The Android audio server "AudioFlinger" and AudioTrack/AudioRecord 32 client implementation are being re-architected to reduce latency. 33 This work started in Android 4.1 (Jellybean), continued in 4.2 34 (Jellybean MR1), and more improvements are likely in "K". 35 </p> 36 37 <p> 38 The lower latency needed many changes throughout the system. One 39 important change was to assign CPU resources to time-critical 40 threads with a more predictable scheduling policy. Reliable scheduling 41 allows the audio buffer sizes and counts to be reduced, while still 42 avoiding artifacts due to underruns. 43 </p> 44 45 <h2 id="priorityInversion">Priority Inversion</h2> 46 47 <p> 48 <a href="http://en.wikipedia.org/wiki/Priority_inversion">Priority inversion</a> 49 is a classic failure mode of real-time systems, 50 where a higher-priority task is blocked for an unbounded time waiting 51 for a lower-priority task to release a resource such as [shared 52 state protected by] a 53 <a href="http://en.wikipedia.org/wiki/Mutual_exclusion">mutex</a>. 54 </p> 55 56 <p> 57 In an audio system, priority inversion typically manifests as a 58 <a href="http://en.wikipedia.org/wiki/Glitch">glitch</a> 59 (click, pop, dropout), 60 <a href="http://en.wikipedia.org/wiki/Max_Headroom_(character)">repeated audio</a> 61 when circular buffers 62 are used, or delay in responding to a command. 63 </p> 64 65 <p> 66 In the Android audio implementation, priority inversion is most 67 likely to occur in these places, and so we focus attention here: 68 </p> 69 70 <ul> 71 72 <li> 73 between normal mixer thread and fast mixer thread in AudioFlinger 74 </li> 75 76 <li> 77 between application callback thread for a fast AudioTrack and 78 fast mixer thread (they both have elevated priority, but slightly 79 different priorities) 80 </li> 81 82 <li> 83 within the audio HAL implementation, e.g. for telephony or echo cancellation 84 </li> 85 86 <li> 87 within the audio driver in kernel 88 </li> 89 90 <li> 91 between AudioTrack callback thread and other app threads (this is out of our control) 92 </li> 93 94 </ul> 95 96 <p> 97 As of this writing, reduced latency for AudioRecord is planned but 98 not yet implemented. The likely priority inversion spots will be 99 similar to those for AudioTrack. 100 </p> 101 102 <h2 id="commonSolutions">Common Solutions</h2> 103 104 <p> 105 The typical solutions listed in the Wikipedia article include: 106 </p> 107 108 <ul> 109 110 <li> 111 disabling interrupts 112 </li> 113 114 <li> 115 priority inheritance mutexes 116 </li> 117 118 </ul> 119 120 <p> 121 Disabling interrupts is not feasible in Linux user space, and does 122 not work for SMP. 123 </p> 124 125 126 <p> 127 Priority inheritance 128 <a href="http://en.wikipedia.org/wiki/Futex">futexes</a> 129 (fast user-space mutexes) are available 130 in Linux kernel, but are not currently exposed by the Android C 131 runtime library 132 <a href="http://en.wikipedia.org/wiki/Bionic_(software)">Bionic</a>. 133 We chose not to use them in the audio system 134 because they are relatively heavyweight, and because they rely on 135 a trusted client. 136 </p> 137 138 <h2 id="androidTechniques">Techniques used by Android</h2> 139 140 <p> 141 We started with "try lock" and lock with timeout. These are 142 non-blocking and bounded blocking variants of the mutex lock 143 operation. Try lock and lock with timeout worked fairly well for 144 us, but were susceptible to a couple of obscure failure modes: the 145 server was not guaranteed to be able to access the shared state if 146 the client happened to be busy, and the cumulative timeout could 147 be too long if there was a long sequence of unrelated locks that 148 all timed out. 149 </p> 150 151 152 <p> 153 We also use 154 <a href="http://en.wikipedia.org/wiki/Linearizability">atomic operations</a> 155 such as: 156 </p> 157 158 <ul> 159 <li>increment</li> 160 <li>bitwise "or"</li> 161 <li>bitwise "and"</li> 162 </ul> 163 164 <p> 165 All of these return the previous value, and include the necessary 166 SMP barriers. The disadvantage is they can require unbounded retries. 167 In practice, we've found that the retries are not a problem. 168 </p> 169 170 <p> 171 Note: atomic operations and their interactions with memory barriers 172 are notoriously badly misunderstood and used incorrectly. We include 173 these here for completeness, but recommend you also read the article 174 <a href="https://developer.android.com/training/articles/smp.html"> 175 SMP Primer for Android</a> 176 for further information. 177 </p> 178 179 <p> 180 We still have and use most of the above tools, and have recently 181 added these techniques: 182 </p> 183 184 <ul> 185 186 <li> 187 Use non-blocking single-reader single-writer 188 <a href="http://en.wikipedia.org/wiki/Circular_buffer">FIFO queues</a> 189 for data. 190 </li> 191 192 <li> 193 Try to 194 <i>copy</i> 195 state rather than 196 <i>share</i> 197 state between high- and 198 low-priority modules. 199 </li> 200 201 <li> 202 When state does need to be shared, limit the state to the 203 maximum-size 204 <a href="http://en.wikipedia.org/wiki/Word_(computer_architecture)">word</a> 205 that can be accessed atomically in one bus operation 206 without retries. 207 </li> 208 209 <li> 210 For complex multi-word state, use a state queue. A state queue 211 is basically just a non-blocking single-reader single-writer FIFO 212 queue used for state rather than data, except the writer collapses 213 adjacent pushes into a single push. 214 </li> 215 216 <li> 217 Pay attention to 218 <a href="http://en.wikipedia.org/wiki/Memory_barrier">memory barriers</a> 219 for SMP correctness. 220 </li> 221 222 <li> 223 <a href="http://en.wikipedia.org/wiki/Trust,_but_verify">Trust, but verify</a>. 224 When sharing 225 <i>state</i> 226 between processes, don't 227 assume that the state is well-formed. For example, check that indices 228 are within bounds. This verification isn't needed between threads 229 in the same process, between mutual trusting processes (which 230 typically have the same UID). It's also unnecessary for shared 231 <i>data</i> 232 such as PCM audio where a corruption is inconsequential. 233 </li> 234 235 </ul> 236 237 <h2 id="nonBlockingAlgorithms">Non-Blocking Algorithms</h2> 238 239 <p> 240 <a href="http://en.wikipedia.org/wiki/Non-blocking_algorithm">Non-blocking algorithms</a> 241 have been a subject of much recent study. 242 But with the exception of single-reader single-writer FIFO queues, 243 we've found them to be complex and error-prone. 244 </p> 245 246 <p> 247 In Android 4.2 (Jellybean MR1), you can find our non-blocking, 248 single-reader/writer classes in these locations: 249 </p> 250 251 <ul> 252 253 <li> 254 frameworks/av/include/media/nbaio/ 255 </li> 256 257 <li> 258 frameworks/av/media/libnbaio/ 259 </li> 260 261 <li> 262 frameworks/av/services/audioflinger/StateQueue* 263 </li> 264 265 </ul> 266 267 <p> 268 These were designed specifically for AudioFlinger and are not 269 general-purpose. Non-blocking algorithms are notorious for being 270 difficult to debug. You can look at this code as a model, but be 271 aware there may be bugs, and the classes are not guaranteed to be 272 suitable for other purposes. 273 </p> 274 275 <p> 276 For developers, we may update some of the sample OpenSL ES application 277 code to use non-blocking, or referencing a non-Android open source 278 library. 279 </p> 280 281 <h2 id="tools">Tools</h2> 282 283 <p> 284 To the best of our knowledge, there are no automatic tools for 285 finding priority inversion, especially before it happens. Some 286 research static code analysis tools are capable of finding priority 287 inversions if able to access the entire codebase. Of course, if 288 arbitrary user code is involved (as it is here for the application) 289 or is a large codebase (as for the Linux kernel and device drivers), 290 static analysis may be impractical. The most important thing is to 291 read the code very carefully and get a good grasp on the entire 292 system and the interactions. Tools such as 293 <a href="http://developer.android.com/tools/help/systrace.html">systrace</a> 294 and 295 <code>ps -t -p</code> 296 are useful for seeing priority inversion after it occurs, but do 297 not tell you in advance. 298 </p> 299 300 <h2 id="aFinalWord">A Final Word</h2> 301 302 <p> 303 After all of this discussion, don't be afraid of mutexes. Mutexes 304 are your friend for ordinary use, when used and implemented correctly 305 in ordinary non-time-critical use cases. But between high- and 306 low-priority tasks and in time-sensitive systems mutexes are more 307 likely to cause trouble. 308 </p> 309 310
