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